data-structures - 哈希树有什么用？

Question

我在维基百科上阅读关于 hash trees ，而且我不明白这种结构的好处或目的——它们似乎需要更多的散列，而不是每个叶子只需要一个散列，而没有大量使用额外的散列。

例如，维基百科上的用例是它们用于验证在 P2P 系统中接收到的数据。但是为什么这比没有树结构的块编号及其哈希的一对一映射更好？

有人可以解释一下哈希树如何以及为什么有用吗？

提前致谢，

摩西

Answer 1

哈希树可以并行计算。如果您有两个数据块要散列，则可以使用两个处理器以两倍的速度计算散列。这仅在您的哈希速度低于您的 IO 速度时才有效，这不太可能。

哈希树可以从单个块的哈希计算，或者从正确对齐的较大部分的哈希计算。这个很重要。

例如，如果我想向您发送一个文件，我可以将其分成 1 MiB 的块，然后将每个块及其 SHA-256 哈希值发送给您。如果任何单个块的哈希不正确，那么您可以再次请求该块。最后，我可以签署文件的树哈希并将签名的哈希发送给您。您可以通过散列每个块散列(您已经验证过)来验证散列，这比重新散列整个文件要快得多。

为什么要使用树哈希？

任何时候，当您想要计算文件的一部分和整个文件的哈希时，树哈希都是有利的。使用像 SHA-256 这样的常规散列，您必须分别散列文件块和整个文件。如果文件是 8 GiB，这可能需要相当长的时间。使用树散列，因为块的散列用于计算文件的散列，所以不需要额外的工作来计算两个散列。

树哈希需要多少额外的工作？

计算树哈希的“额外工作”实际上很少。是的，它确实需要计算额外的哈希值——但只需要 O(1) 额外的工作。如果您的块大小为 1 MiB，那么如果您的文件为 1 MiB 或更小，则额外工作大约为零。随着数据大小的增加，额外的工作量将接近每个数据块的两个哈希的 1 个额外哈希——对于 SHA-256，核心将最多每 1 MiB 数据评估两次(一次用于输入哈希，一次用于填充)。那不是很多。