互联网校验和

在构成现代互联网的持续数据洪流中，我们如何确保发送和接收的信息完好无损地到达？维护数据完整性最古老、最基本的一种工具就是互联网校验和。它是一种简单、快速且设计精妙的算法，旨在检测数据包在网络中传输时发生的意外损坏。虽然这看起来只是一个微不足道的技术细节，但校验和的设计选择揭示了在速度、简单性和魯棒性之间的深刻权衡，这些权衡几十年来一直在塑造着计算机系统。本文将深入探讨使校验和得以工作的巧妙算術和数学原理。

本次探索将揭示互联网校验和的内部工作原理，从其独特的反码算術应用到其固有的漏洞。我们不仅将剖析校验和是如何计算的，还将探讨其设计初衷，并将其与更安全的加密哈希函数区分开来。我们的旅程始于第一章 ​​原理与机制​​，审视其核心数学概念以及校验和计算与验证的逐步过程。随后，​​应用与跨学科联系​​ 章节将揭示这个简单算法的影响如何远远超出了错误检测的范畴，推动了硬件和软件中关键的性能优化，甚至在数据结构和文件系统等领域产生共鸣。

要理解互联网如何在混乱的数据洪流中维持表面的秩序，我们必须审视其最古老、最精妙的技巧之一：​​互联网校验和​​。这是一种简单而巧妙的方法，用于检查数据包在传输过程中是否被意外损坏。但要领会其设计之妙，我们不能只看最终的公式，还必须深入其内部，探究它所采用的独特算術方法。

当我们学习加法时，我们学到了进位。如果我们将 $9$ 和 $3$ 相加，我们得到 $12$，也就是一个 $2$ 加上一个进位到十位的 $1$。计算机处理二进制数时也做类似的事情。你的计算机处理器用于日常任务的算術称为​​补码算術​​。它的设计旨在高效且无缝地处理正数和负数。当一个（比如说）$16$ 位数的加法产生一个 $17$ 位数的结果时，处理器通常会丢弃那第 $17$ 位（即进位位）。这相当于在一个大小为 $2^{16}$ 的圆上进行算術运算。

然而，互联网校验和的做法有所不同。它使用的是所谓的​​反码算術​​。规则简单却奇特：如果产生了进位位，不要丢弃它。相反，将它“回卷”并加到结果的最低有效位上。

假设我们必须对三个 $16$ 位的数据字计算校验和。为了举一个真正有启发性的例子，我们选择字 $w_1 = \text{0xFFFF}$、$w_2 = \text{0xFFFF}$ 和 $w_3 = \text{0x0001}$。用十进制来说，这就像把 $65535$、$65535$ 和 $1$ 相加。总和是 $131071$。

在 $16$ 位二进制中，$\text{0xFFFF}$ 是由十六个 1 组成的字符串。将前两个字相加，$\text{0xFFFF} + \text{0xFFFF}$，得到 $\text{0x1FFFE}$。这是一个 $17$ 位的结果：低 $16$ 位是 $\text{0xFFFE}$，并且有一个 $1$ 的进位。在反码加法中，我们将这个进位回卷：$\text{0xFFFE} + 1 = \text{0xFFFF}$。现在，我们加上第三个字 $w_3 = \text{0x0001}$。所以，我们计算 $\text{0xFFFF} + \text{0x0001}$，得到 $\text{0x10000}$。我们又得到了一个 $17$ 位的结果：和为 $\text{0x0000}$，进位为 $1$。我们将其回卷：$\text{0x0000} + 1 = \text{0x0001}$。这就是我们最终的折叠和。

這種​​回卷进位​​是校验和机制的核心。如果我们使用标准的补码算術，我们就会直接丢弃进位。那么和将是 0xFFFF。结果显然是不同的。那么，为什么要使用这个奇怪的规则呢？这仅仅是早期网络工程师的一个任意怪癖吗？完全不是。这背后有一个优美的数学原因。

回卷进位不是一个硬件技巧；它是一个数学原理的绝妙实现。对于 $k$ 位字来说，反码加法是计算​​模​​ $(2^k - 1)$ 和的一种快速方法。

这是什么意思呢？思考数字 $2^k$。在我们的 $k$ 位系统中，一个进位位的值是 $2^k$。现在，考虑模数 $M = 2^k - 1$。在这个系统中，$2^k$ 是多少？嗯，$2^k = (2^k - 1) + 1$，所以当我们用 $2^k$ 除以 $(2^k - 1)$ 时，我们得到余数 $1$。用模算术的语言来说，我们写成：

$2^k \equiv 1 \pmod{2^k - 1}$

这个小小的等价关系是解开一切的关键。它告诉我们，在这个数学世界里，进位位的值就是 $1$！这就是为什么我们把它加回到最低有效位上。这个“回卷”不是一个技巧；它是在这个特定的模系统中算術上正确的操作。

这个性质有一个深远的 consequence。一个由多个 $k$ 位块（$b_m, ..., b_1, b_0$）组成的数字 $x$，其值为 $x = \sum b_i (2^k)^i$。但由于 $(2^k)^i \equiv 1^i \equiv 1 \pmod{2^k - 1}$，这个数模 $(2^k - 1)$ 的和就等于其各块之和！

$x \pmod{2^k - 1} \equiv \sum b_i \pmod{2^k - 1}$

这意味着我们可以取一大块数据，将其分解成 $16$ 位的字，然后用反码加法将它们全部加起来。最终的和在数学上等同于整个数据块模 $(2^{16}-1)$ 的和。校验和并不将报文视为一个结构化的序列，而是一个简单的“词袋”，其中词的顺序不影响最终的总和。这既是一种精妙的简化，正如我们将看到的，也是一个显著的弱点。

现在我们有了这个特殊的和，我们如何形成并使用校验和呢？完整的流程如下：

1. ​​准备数据​​：数据被视为一个 $16$ 位字的序列。由于互联网必须在各种类型的计算机之间工作，因此使用了一种称为​​网络字节序​​（即大端序）的标准格式。这意味着一个字的第一个字节是最重要的。一个在小端序机器上工作的程序员如果忘记了这一点，将会计算出一个完全错误的校验和！。如果数据有奇数个字节，则添加一个零值填充字节以形成最后一个 $16$ 位字。

2. ​​计算总和​​：所有的 $16$ 位字都使用反码加法（带回卷进位）相加。在现代软件中，这通常是通过将字累加到一个 $32$ 位的累加器中，然后将高 $16$ 位（进位）“折叠”到低 $16$ 位，直到没有进位为止。

3. ​​形成校验和​​：校验和是最终和的​​反码（按位取反）​​。如果和是 $S$，那么校验和就是 $C = \sim S$。

4. ​​验证​​：发送方将这个校验和 $C$ 放入数据包的头部。当接收方收到数据包时，它对所有数据字 以及 收到的校验和值执行完全相同的反码求和。如果没有发生错误，一个值与其反码的和总是一个全为 1 的字：$\text{0xFFFF}$（这是该系统中“负零”的表示）。因此，如果最终的和是 $\text{0xFFFF}$，则认为数据包是有效的。

认识到整个过程与数据含义无关是至关重要的。负载可以是有符号整数、图像或文本；校验和逻辑只看到一串待加的比特。

互联网校验和被设计得简单而快速，用于检测由噪声或硬件故障引起的常见意外错误。而且它在这方面做得相当不错。例如，报文中的任何单比特翻转都会改变和，因此会被检测到。

然而，它的简单性也带来了局限性。校验和对任何不改变最终反码和的错误都是“盲目”的。形式上，如果对字整数和的总改变是 $2^{16}-1$ 的倍数，则错误不会被检测到。

哪些类型的错误符合这种描述？

• ​​交换字​​：由于加法是可交换的，交换报文中任意两个字的顺序将产生完全相同的和。校验和永远不会检测到这一点。
• ​​补偿性错误​​：如果一个字中位置 $k$ 的比特从 $0$ 翻转到 $1$（使和增加 $2^k$），而另一个字中相同位置 $k$ 的比特从 $1$ 翻转到 $0$（使和减少 $2^k$），那么和的净变化为零。这种错误是不可见的。
• ​​添加零​​：在反码算術中，全为 1 的字（$\text{0xFFFF}$）的作用类似于零。在报文中任何位置插入这个字都不会改变和，从而产生一个简单的“碰撞”，即两个不同的报文具有相同的校验和。

这使我们得出了一个关键的区别：互联网校验和是一种​​检错码​​，而不是​​加密哈希函数​​。它旨在捕获随机、意外的错误，而不是抵御有决心的、智能的对手。

定义其模算術的“溢出”本身是一个特性，而不是一个缺陷。正是回卷使其得以工作。但这种可预测的线性结构从安全角度看是一个致命缺陷。因为报文和校验和之间的关系是简单的加法，攻击者可以轻易地对报文进行修改（例如，将“Pay Alice $10”改为“Pay Alice$90”），然后计算出在数据包另一部分所需的相应微小改动，以使校验和结果正确。这是轻而易举就能做到的。

像 SHA-256 这样的真正加密哈希函数被设计成一个单向函数。其内部操作是高度非线性的，会产生雪崩效应，即改变单个输入比特会混沌地改变整个输出。找到两个产生相同哈希值（碰撞）的报文在计算上是不可行的。输出空间的巨大规模说明了部分原因。由于“生日悖论”，你期望在测试仅仅几百条随机报文后就能在 $16$ 位校验和中找到一个碰撞。而对于一个 $256$ 位的哈希，你需要测试大约 $2^{128}$ 条报文——这个数字远大于我们银河系中估计的恒星数量。

因此，互联网校验和是工程权衡的一个绝佳例子。它不是一个加密保险库。它是一个轻量级、高效的筛子，完美地适应了它的工作：捕获数据包在全球网络上疯狂旅程中遭受的意外失误和磕绊。

在普通观察者看来，互联网校验和是一个 humble 的仆人，一种简单的算術技巧，用于发现网络上传输的数据中的错误。其主要工作——检测数据损坏——当然很重要。但如果止步于此，就会错过真正的故事。互联网校验和的故事不仅仅是关于发现错误；它是对现代计算核心的一次盛大巡礼，是关于对性能不懈追求的一课，也是一个美丽的例证，说明一个单一、精妙的想法如何在系统的每一层产生回响，从你使用的应用程序一直到蚀刻在硅片上的逻辑门。

正如我们所见，反码算術的原理虽然奇特但很直接。真正的天才之处在于如何利用这些原理。让我们踏上一段旅程，看看这个简单的算法将我们带向何方。

想象一下，你的计算机正试图通过一个快速的 10 Gb/s 网络发送一个大文件。CPU，这个通用计算的奇迹，可以尽职尽责地读取文件的每一个字节，执行那些小的反码加法，并为每个数据包计算校验和。但这就像让一个钟表大师整天在装配线上拧螺丝一样。这是对宝贵、多功能资源的浪费。在高速下，这个简单、重复的任务可能会消耗 CPU 的大部分能力，留给真正重要的应用程序的资源寥寥无几。一个假想但现实的计算表明，在现代处理器上，为 10 Gb/s 的数据流进行基于软件的校验和计算，可能单枪匹马地占用一个 CPU 核心超过 60% 的周期。

这就是系统设计最基本的原则之一发挥作用的地方：专业化。我们将任务​​卸载​​给专家。CPU，作为总经理，将繁重的工作委托给网络接口控制器 (NIC)，这个专职的收发专家。

这种合作是效率的奇迹。当一个应用程序想要发送一大塊数据时，操作系统的内核并不会费力地将其切成数千个 1500 字节的小数据包。那样太慢了。相反，得益于一种称为 TCP 分段卸载 (TSO) 的特性，内核会创建一个单一的、巨大的逻辑数据包——可能高达 64KB——以及一个相应的头部模板。然后它将这个捆绑包交给 NIC。至关重要的是，由于校验和卸载 (CSO)，内核甚至懒得去计算完整的校验和。它可能只计算一小部分，或者干脆将校验和字段留为零。然后它设置一个标志，基本上是告诉 NIC：“接下来交给你了。”

NIC 硬件使用自己的直接内存访问 (DMA) 引擎，直接从计算机主存中拉取大数据块和头部模板。然后，其专用电路执行分段，创建出一连串大小完美的网络数据包。对于每一个数据包，它都会更新头部（如序列号），并使用其专用的校验和单元，在发送数据包之前即时计算并插入正确的校验和。

性能提升是惊人的。CPU 成本从一个核心的 60% 骤降至也许仅仅 1%——仅仅是准备描述符告诉 NIC 该做什么的小开销。这个想法与并行计算中的一个深刻概念相联系：Amdahl 定律。该定律告诉我们，系统的总加速受限于其顽固的串行、不可并行的部分。通过卸载校验和计算——一个必须为每个数据包完成的任务——我们正在缩小一个显著的串行瓶颈，从而釋放了远超以往的整体系统性能和可伸缩性。

所以我们把工作交给了硬件。但硬件是如何做得这么快的呢？让我们再放大一点，一直到处理器本身。设计 CPU 的架构师可能会注意到，这个“相加并折叠进位”的操作是如此普遍和重要，以至于它应该在算术逻辑单元 (ALU)——处理器的计算器——中占有一席之地。可以创建一个专门的指令，在一个闪电般快速的时钟周期内执行这种反码加法，这证明了该算法的重要性已 literally 蚀刻在硅片上。

但是，如果你没有一个花哨的 NIC 或自定义的 ALU 指令呢？你仍然可以在意想不到的地方找到并行性。现代 CPU 拥有所谓的单指令多数据 (SIMD) 单元。这就像拥有一个宽敞的工作台，让你能同时对多片数据执行相同的操作。一个 256 位的 SIMD 寄存器可以容纳十六个 16-位的字。

在这里，校验和的一个优美的数学特性——结合律——拯救了我们。回想一下，反码加法等同于整数加法后跟折叠进位。因为加法是满足结合律的，所以你以何种顺序添加一列数字并不重要。这意味着我们不必加两个字，折叠进位，再加下一个字，再折叠进位，等等。相反，我们可以使用我们宽大的 SIMD 寄存器一次性加起比如说十六个字，让部分和在更宽的 32 位或 64 位通道中累积以防止溢出。只有在对大块缓冲区求和之后，我们才对这些通道进行最后的“水平”求和，并从这个总和中折叠进位。这个策略，也涉及到处理内存对齐和字节序（endianness）等实际考虑，通过利用细粒度的数据并行性，极大地加速了软件中的校验和计算。

聪明才智并不止于硬件。智能软件扮演着同样重要的角色。现代编译器，这个将人类可读代码翻译成机器指令的工具，是优化的主人。如果它看到一个程序在循环处理一批数据包以计算校验和，它可能会注意到数据包头的某些部分（如源地址和目的地址）对于批次中的每个数据包都是相同的。应用一种称为循环不变代码外提的经典技术，编译器可以将这些不变部分的校验和计算“提升”出循环，只计算一次，并在循环内将这个部分和添加到每个数据包的唯一校验和中。同样，这只有因为加法的结合律特性才成为可能。

操作系统，作为总指挥，也展现出其独特的智慧。考虑接收数据。在一个高性能的“零拷贝”系统中，NIC 的 DMA 引擎将传入的数据包数据直接放入应用程序拥有的内存中，完全绕過内核以节省时间。但 NIC 也已经在硬件中验证了校验和。它如何将这种“好”或“坏”的状态传達给应用程序，而无需 CPU 接触有效负载呢？解决方案是一场优雅的元数据之舞。NIC 将数据包写入应用程序的缓冲区，并同时将一个小的描述符写入一个单独的共享内存环。这个描述符包含数据包长度和一个关键比特：校验和有效性标志。内核唯一的工作就是看到这个新的描述符，将这个微小的元数据复制到一个应用程序可见的“完成环”中，然后继续。应用程序轮询其完成环，看到元数据，并立即知道其缓冲区中的数据是否有效，所有这一切都无需 CPU 为验证目的而读取有效负载的任何一个字节。

科学中一个真正深刻的想法从不满足于待在一个地方。它会回响、重现，并在最不可能的角落找到新的生命。校验和也是如此。快速、“滚动”哈希的基本概念太有用了，以至于不能局限于网络领域。

让我们离开数据包的世界，进入​​数据结构​​的抽象领域。想象你有一个巨大的动态数字数组，你需要能够快速验证其内容是否已更改。每次微小修改后重新扫描整个数组会非常低效。取而代之的是，我们可以将数组的元素存储在一个“增强”的平衡二叉搜索树中。树中的每个节点不仅存储其子节点的信息，还存储其整个子树中数据的预计算校验和。得益于滚动校验和（互联网校验和的近亲）的代数结构，当插入或删除一个元素时，我们不需要重新计算所有东西。我们只需要更新从被修改的叶子节点到根节点路径上少数几个节点的校验和值。一个原本需要线性时间的操作现在只需要对数时间——这是一个指数级的改进。允许 NIC 高效处理数据包的相同数学递推关系，也允许我们高效地管理动态数据结构的完整性。

这个想法在​​文件系统和数据库​​的世界中再次回响。当你向硬盘写入一个文件时，你怎么能确定在你几个月后读回它时，没有宇宙射线或 subtle 硬件故障翻转了某个比特？你添加一个校验和！在像 B+ 树这样的现代存储系统中，它们在磁盘上组织数据，每个数据块（一个“页”）的头部通常都包含一个校验和。当从磁盘读取页面时，系统会重新计算校验和并与存储的值进行比较。这能立即标记出任何磁盘上的损坏。将此校验和放在何处的设计选择至关重要。将其存储在页面本身内部，而不是在父节点或单独的文件中，是一种更优的设计。它使验证自成一体，避免了在修改页面时产生级联更新，并且对性能的影响最小——这正是我们在网络硬件卸載中看到的原则。

互联网校验和是最好的检错码吗？绝对不是。对于给定的有效负载大小，其未能检测到随机损坏的概率约为 $2^{-16}$，这远弱于 32 位 CRC 或像 SHA-256 这样的加密哈希。在要求极高可靠性的应用中，互联网校验和可能不够强大。对一个远程过程调用 (RPC) 系统的分析可能会显示，虽然校验和很快，但它未能满足例如每小时未检测错误率低于十亿分之一的严格可靠性目标，而 CRC-32 则会成功。

那么为什么它如此普遍和重要呢？因为它达到了一个光荣的平衡点。它在算法上很简单，使其在硬件和软件中计算都极其快速。而其优美的代数特性，尤其是结合律，使其非常适合各种各样的优化：硬件卸载、SIMD 向量化、编译器提升，甚至在其原始目的之外的领域中的应用。

互联网校验和的故事本身就是计算机科学的一个缩影。这是一个关于权衡、关于实用主义、关于利用数学的精妙来获得实际性能的故事，也是关于一个简单、“足够好”的想法如何在我们数字世界的每一层泛起涟漪，为我们数据的完整性提供着无声而持续的守护。