c-用于数据完整性检查的可并行散列函数

Question

在以下情况下，我需要检查数据的完整性：数据以不同大小的块写入存储（对于每个块，我们知道它在最终文件中的偏移量）。然而，块以任意顺序出现，并且在多个线程中。它们以完全不同的顺序从存储器中读回（并且块具有不同的大小）。

我目前的想法是：

    #define MODEST_PRIME 1021
    unsigned char checkbuf[MODEST_PRIME];
    void check_function(unsigned char *chunk, size_t offset, size_t length, unsigned char *result)
    {
       size_t i;
       for(i=0; i<length; i++)
           result[(i+offset)%MODEST_PRIME]^=chunk[i];
    }

这似乎提供了防止任何单个字节更改的保护，并且（在某种程度上）防止块的交换（交换块之间的距离不太可能被大素数整除）。该函数对不同块的结果可以直接异或在一起，因此它是完全可并行的。

然而，与md5 sum或任何其他现代哈希函数相比，这个函数看起来非常简单。但据我所知，md5和sha-1和的计算不能按任意顺序进行。

问题是，我们有比更好的解决方案吗

1. 如果我们知道块的大小和偏移量，就可以按任意顺序计算（就像我上面概述的简单算法一样）
2. 可以提供至少与md5 sum相当的数据完整性检查

Answer 1

一个选项是类似树的检查汇总层次结构。

有了两个层次，你可以把块放在树的第一层（底部）。树的第二级是一个字节数组，它通过连接较低级别的校验和来创建。

这适用于任何哈希函数。

Answer 2

你不能只计算每个区块的连接偏移量、长度和内容的SHA1和，然后将它们异或在一起吗？