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

Question

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

我目前的想法是:

    #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];
    }

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

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

好吧，问题是，我们有没有更好的解决方案

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

Answer 1

一个选项是树状校验和层次结构。

如果有两层，您可以将 block 放在树的第一层(底部)。树的第 2 层是一个字节数组，通过连接较低层的校验和创建。

这适用于任何哈希函数。