使用循环冗余校验（CRC）作为摘要来检测文件之间的重复。

Question

使用循环冗余校验（CRC）作为摘要来检测文件之间的重复。

4

CRC和类似计算（如Fletcher和Adler）的主要用途似乎是检测传输错误。因此，我看到的大多数研究似乎都是解决在两个数据集之间检测小规模差异的概率问题。我的需求略有不同。

以下是该问题的非常粗略的描述。细节比这复杂得多，但下面的描述说明了我正在寻找的功能。这个小免责声明是为了防止出现“为什么你要用这种方式解决你的问题，而不是我提出的更容易解决的其他方式？”这样的答案 - 我需要以这种方式解决我的问题，原因很多，与这个问题或帖子无关，请不要发布此类回答。

我正在处理分布式网络上的数据集合（大小约为1MB）。这些数据集上执行计算，速度/性能至关重要。我想要一个机制来避免重新传输数据集。也就是说，我需要一种方法为给定大小的每个数据集生成唯一标识符（UID）。（然后，我将数据集大小和UID从一台机器传输到另一台机器，接收机只需要根据UID判断是否已经在本地拥有它，如果没有，则请求传输数据。）

这类似于使用CRC检查文件的更改，以及使用CRC作为摘要来检测文件之间的重复。我没有看到任何关于后一种用法的讨论。

我不关心篡改问题，即我不需要具有加密强度散列的哈希。

我目前正在使用序列化数据的简单32位CRC，这在目前为止已经为我服务了很好。但是，我想知道是否有人可以推荐哪个32位CRC算法（即哪个多项式？）最适合在这种情况下最小化碰撞的概率？

我另外一个问题有点微妙。在我的当前实现中，我忽略了我的数据集的结构，并有效地仅对表示我的数据的串进行CRC。然而，出于各种原因，我想按以下方式更改我的CRC方法。假设我的顶级数据集是一些原始数据和几个从属数据集的集合。我的当前方案基本上将原始数据和所有从属数据集连接起来，然后CRC结果。然而，大多数时候我已经拥有从属数据集的CRC，我宁愿通过连接原始数据和从属数据集的CRC来构建我的顶级数据集的UID，然后CRC这个构造。问题是，使用这种方法会影响碰撞的概率吗？

为了更好地讨论我的想法，我将定义一些符号。将我的顶层数据集称为T，假设它由原始数据集R和从属数据集S1，S2，...，Sn组成。我可以写成T = (R, S1, S2, ..., Sn)。如果&表示数据集的连接，则我的原始方案可以被看作是：

UID_1(T) = CRC(R & S1 & S2 & ... & Sn)

我的新方案可以被认为是：

UID_2(T) = CRC(R & CRC(S1) & CRC(S2) & ... & CRC(Sn))

那么我的问题是：（1）如果 T 和 T' 非常不同，哪个CRC算法能最小化 prob（UID_1（T）= UID_1（T'）），哪个CRC算法能最小化

 prob（UID_2（T）= UID_2（T'）），并且这两个概率如何比较？
我关于这个问题的想法很天真和无知。假设 T 和 T' 之间的差异仅在一个从属数据集中，WLOG说 S1！= S1'。如果发生 CRC（S1）= CRC（S1'），那么显然我们将有 UID_2（T）= UID_2（T'）。另一方面，如果 CRC（S1）！= CRC（S1'），那么 R＆CRC（S1）＆CRC（S2）＆...＆CRC（Sn）与 R＆CRC（S1'）＆CRC（S2）＆...＆CRC（Sn）之间的差距只有4个字节，因此UID_2检测差异的能力实际上与CRC检测传输错误的能力相同，即它能够检测到仅有几个未被广泛分离的位中的错误。由于这就是CRC的设计目的，所以我认为只要我使用的CRC能够很好地检测传输错误，UID_2就非常安全。用我们的符号表示，
prob( UID_2(T)=UID_2(T') ) = prob(CRC(S1)=CRC(S1')) + (1-prob(CRC(S1)=CRC(S1'))) * probability of CRC not detecting error a few bits.


我们称CRC未检测到少量错误的概率为P，未检测到大量差异的概率为Q。以上可以近似表示为：

prob( UID_2(T)=UID_2(T') ) ~ Q + (1-Q)*P

现在我将进一步修改我的UID，具体如下。对于一个“基本”数据，即数据集T=(R)，其中R只是一个double、integer、char、bool等，定义UID_3(T)=(R)。然后对于一个由下级数据集T = (S1, S2, ..., Sn)组成的数据集T，定义：
UID_3(T) = CRC(ID_3(S1) & ID_3(S2) & ... & ID_3(Sn))

假设一个特定的数据集 T 包含嵌套的子数据集，嵌套深度为 m 级别，那么在某种模糊的意义下，我认为
prob( UID_3(T)=UID_3(T') ) ~ 1 - (1-Q)(1-P)^m

鉴于这些概率在任何情况下都很小，因此可以近似为：
 1 - (1-Q)(1-P)^m = Q + (1-Q)*P*m + (1-Q)*P*P*m*(m-1)/2 + ... ~ Q + m*P

如果我知道我的最大嵌套层数“m”，并且我知道各种CRC的“P”和“Q”，那么我想要选择给我最小值的CRC“Q+m*P”。如果像我怀疑的那样，“P~Q”，则以上简化为：UID_1的错误概率是“P”。UID_3的错误概率是“(m+1)P”，其中“m”是最大嵌套（递归）级别。这一切看起来合理吗？

- David I. McIntosh

3个回答

1

马克·阿德勒的回答非常准确。如果我摘下程序员的帽子，戴上数学家的帽子，其中一些内容应该是显而易见的。他没有时间解释数学问题，所以我在这里为那些感兴趣的人解释。

计算CRC的过程本质上是进行多项式除法的过程。多项式的系数模2，即每个项的系数为0或1，因此N次多项式可以由一个N位数字表示，每个位表示一个项的系数（进行多项式除法的过程相当于进行一系列的异或和移位操作）。在对数据块进行CRC时，我们将“数据”视为一个大多项式，即一长串比特，每个比特表示多项式中一项的系数。我们称数据块多项式为A。对于每个CRC“版本”，都选择了用于CRC的多项式，我们将其称为P。对于32位CRC，P是一个32次多项式，因此它有33个项和33个系数。因为最高系数始终为1，所以它是隐含的，我们可以用一个32位整数表示32次多项式。（从计算上讲，这实际上非常方便。）计算数据块A的CRC是找到A除以P的余数的过程。也就是说，A总是可以写成

A = Q * P + R

其中R是一个次数小于P的多项式，即R的次数小于等于31，因此可以用32位整数表示。 R本质上是CRC。(小注：通常在A之前加上0xFFFFFFFF，但这里不重要。)现在，如果我们连接两个数据块A和B，则对应于两个块连接的“多项式”是A的多项式，“向左移动”位于B中的位数，再加上B。换句话说，A&B的多项式是A*S+B，其中S是一个1后面跟着N个零的多项式，N是B中的位数。(即S=x**N)。那么，关于A&B的CRC，我们能说什么呢？假设我们知道A=Q*P+R和B=Q'*P+R'，即R是A的CRC，R'是B的CRC。假设我们还知道S=q*P+r。然后

A * S + B = (Q*P+R)*(q*P+r) + (Q'*P+R')
          = Q*(q*P+r)*P + R*q*P + R*r + Q'*P + R'
          = (Q*S + R*q + Q') * P    + R*r + R'

因此，要找出A*S+B被P除的余数，我们只需要找到R*r+R'被P除的余数。因此，要计算两个数据流A和B的连接的CRC，我们只需要知道数据流的单独CRC，即R和R'，以及尾部数据流B的长度N（这样我们就可以计算r）。这也是Mark另一个评论的内容：如果尾部数据流B的长度受到限制，我们可以为每个长度预先计算r，使得两个CRC的组合非常简单。（对于任意长度的N，计算r并不容易，但比重新对整个B进行除法运算要快得多（log_2 N））。

注意：上述并不是CRC的精确阐述。有一些位移发生。要精确，如果L是由0xFFFFFFFF表示的多项式，即L=x*31+x*30+...+x+1，而S_n是“左移n位”的多项式，即S_n = x**n，则具有N位多项式A的数据块的CRC是当（L * S_N + A）* S_32除以P时的余数，即当（L&A）*S_32除以P时的余数，其中&是“连接”运算符。

此外，我认为我不同意Mark的评论，如果我错了他可以纠正我。如果我们已经知道R和R'，则使用上述方法计算A&B的CRC所需的时间与直接计算它并不取决于len(A)与len(B)的比率 - 要以“直接”方式计算它，实际上不需要在整个连接数据集上重新计算CRC。使用我们上面的符号，我们只需要计算R*S+B的CRC。也就是说，我们不是在B前面添加0xFFFFFFFF并计算其CRC，而是在B前面添加R并计算其CRC。因此，这是计算B的CRC花费的时间与计算r的时间的比较，(然后通过将R*r+R'除以P来完成，这在时间上是微不足道且无关紧要的)。

- David I. McIntosh

你是正确的——我的评论假设需要再次计算整个东西的CRC，但如果你有第一部分的CRC，那么你就不需要这样做。我已经删除了那条评论。 - Mark Adler

0

Mark Adler的答案解决了技术问题，所以我在这里不会重复。在这里，我要指出OP问题中提出的同步算法中存在一个主要潜在缺陷，并建议进行小改进。

校验和和哈希为某些数据提供单个签名值。然而，由于长度有限，如果数据更长，则校验和/哈希可能的唯一值数量始终小于原始数据的可能组合数。例如，4字节CRC只能采用4 294 967 296个唯一值，而即使是可能是数据的5字节值也可以采用8倍的值。这意味着对于任何比校验和本身更长的数据，总是存在一个或多个具有完全相同签名的字节组合。

当用于检查完整性时，假设稍微不同的数据流产生相同的签名的可能性很小，因此我们可以假设如果签名相同，则数据相同。重要的是要注意，我们从一些数据d开始，并验证给定使用校验和函数f计算的校验和c时，f(d) == c。

在OP算法中，不过，不同的用途引入了一种微妙但有害的置信度降低。在OP算法中，服务器A将从原始数据开始生成校验和集（其中dnA是服务器A上的第n个数据项）。然后，服务器B将接收此校验和列表并检查其自己的校验和列表以确定是否有任何遗漏。假设服务器B具有列表。然后应该发生的是它从服务器A请求d4，并且在理想情况下同步已经正常工作。

如果我们回想一下碰撞的可能性，以及并不总是需要太多数据就能产生一个（例如 CRC("plumless") == CRC("buckeroo")），那么我们很快就会意识到，我们方案提供的最好保证是服务器 B 绝对没有 d4A，但它不能保证它有 [d1A,d2A,d3A]。这是因为即使 d1A 和 d1B 是不同的，我们希望两个服务器都拥有它们，但是可能出现 f(d1A) = c1 和 f(d1B) = c1 的情况。在这种方案中，任何一个服务器都无法知道同时存在 d1A 和 d1B。我们可以使用更多抗碰撞校验和和哈希函数，但这种方案永远无法保证完全同步。这在网络必须跟踪的文件数量越多时变得更加重要。我建议使用像 SHA1 这样的加密哈希函数，因为目前还没有发现碰撞。

一种可能的缓解这种风险的方法是引入冗余哈希。一种做法是使用完全不同的算法，因为虽然可能存在，但同时出现的概率更小。但是，这paper表明，用这种方式收获的好处并不那么大。使用OP符号表示，和同时为真的概率也更小，所以您可以使用“盐”来减少碰撞。不过，我认为你可能还是应该使用一个抗碰撞哈希函数，比如SHA512，在实践中对性能影响不大。

- jeteon

你说的一切都是正确的。但是，这个特定问题的两个方面使得你的评论并不适用。首先，使用你的符号表示，数据集dnA和dnB（对于固定的n）的某些特殊性质使得f(dnA) = f(dnB)几乎不可能，除非dnA = dnB。具体来说，dnA和dnB只会以有限的方式不同，它们的CRC几乎肯定是不同的。这是我们问题的一个特殊之处 - 我们不是为某个产品创建通用工具。其次，在我的原始帖子中，我没有充分强调性能的重要性。 - David I. McIntosh

特别需要注意的是，在上述工作和其他简化措施的基础上，给定CRC（A）和CRC（B），可以几乎瞬间计算出CRC（A＆B），特别是在现代Intel处理器上使用CRC指令时（这也允许非常快速地计算CRC（X））。然而，您的评论将作为警告，提醒任何试图将此方法用于一般同步的人。 - David I. McIntosh

我想我没有说清楚，但是担心的更多是可能出现 f(dnA) = f(dmB)（可能有不同的索引）。然而，既然你说你的问题构造得不能发生这种情况，我同意这个答案比你寻求的更通用。有趣的是，我一直在运行通用实现的基准测试中发现，MD5 和 CRC32 之间的性能差异可能只有不到 2 倍的因子。 - jeteon

CRC32是如何实现的？特别是它是否使用英特尔机器指令，并且是否采用了Mark建议的并行和组合方案？我问这个问题是出于兴趣，而不是挑战，因为在我们的情况下，我们可以在串行化时几乎免费计算CRC32。对于MD5也可能是如此-我对此不够了解。此外，如果我们比较f(dnA)和f(dmB)，那么确实会有非常严重的退化问题，可能会出现数量级更多的碰撞可能性。 - David I. McIntosh

基准测试中的CRC32通常使用C实现，而不使用机器指令。根据http://www.strchr.com/crc32_popcnt，CRC32指令似乎比普通实现快5倍以上。MD5哈希表示在哈希结束时达到的“状态”。据我所知，您只需按顺序对文件进行哈希以获取组合哈希（每次从最后一个哈希值开始）。但是，我认为没有办法给出组件总和得到完整的MD5总和。不过，您可以对连接的哈希进行哈希。 - jeteon

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mark Adler · Accepted Answer

我希望有一种机制可以避免我重新传输数据集。 rsync已经解决了这个问题，通常使用你概述的方法。

然而，我想知道是否有人推荐哪个32位CRC算法（即哪个多项式？）最适合在这种情况下最小化碰撞的概率？

在精心选择的CRC多项式中，您不会看到太大的差异。速度可能对您更重要，在这种情况下，您可能需要使用硬件CRC，例如现代Intel处理器上的指令。该指令使用CRC-32C（Castagnoli）多项式。您可以通过在同一循环中在单个核心上使用三个算术单元计算三个缓冲区上的CRC，然后将它们组合起来，使其真正快速。请参见下面如何组合CRC。

然而，大部分时间我已经有了子数据集的CRC值，我更愿意通过将原始数据与子数据集的CRC值连接起来构建顶层数据集的UID，然后对此构造进行CRC计算。

或者，您可以快速计算整个集合的CRC，就像对整个内容进行CRC一样，但使用已计算出的片段的CRC。请参考zlib中的crc32_combine()。这比取一堆CRC的CRC要好。通过组合，您保留了CRC算法的所有数学优势。