我在 Wikipedia 上阅读了有关哈希树的信息，但我不明白这种结构的好处或目的——它们似乎需要更多的哈希，而不仅仅是每片叶子一个，而没有大量使用额外的哈希。
例如，维基百科上的用例是它们用于验证 P2P 系统中接收到的数据。但是，为什么这比在没有树结构的情况下对块编号及其哈希进行一对一映射要好呢？
有人可以解释一下哈希树如何以及为什么有用吗？
提前致谢，
摩西
问问题
5543 次
1 回答
11
哈希树可以并行计算。如果您有两个数据块要散列，则可以使用两个处理器以两倍的速度计算散列。这仅在您的哈希速度低于您的 IO 速度时才有效，这不太可能。
哈希树可以从单个块的哈希计算，或者从正确对齐的较大部分的哈希计算。这个很重要。
例如，如果我想向您发送一个文件，我可以将其分成 1 MiB 的块，然后将每个块及其 SHA-256 哈希发送给您。如果任何单个块的哈希不正确，那么您可以再次请求该块。最后，我可以对文件的树形哈希进行签名并将签名的哈希发送给您。您可以通过散列每个块散列（您已经验证）来验证散列，这比重新散列整个文件要快得多。
为什么使用树哈希？
每当您想要计算文件的一部分和整个文件的哈希时，树哈希都是有利的。使用像 SHA-256 这样的常规哈希，您必须分别对文件块和整个文件进行哈希处理。如果文件为 8 GiB，这可能需要相当长的时间。使用树哈希，因为块的哈希用于计算文件的哈希，所以计算两个哈希都不需要额外的工作。
树哈希有多少额外的工作？
计算树哈希的“额外工作”实际上是最少的。是的，它确实需要计算额外的哈希值——但只需要 O(1) 额外的工作。如果您的块大小为 1 MiB，那么如果您的文件为 1 MiB 或更小，那么额外的工作量大约为零。随着数据大小的增加，每个数据块的额外工作量将接近两个哈希值中的 1 个额外哈希值——对于 SHA-256，每 1 MiB 数据最多只对核心进行两次额外评估（一次为输入哈希，一次用于填充）。那不是很多。
于 2012-11-12T01:53:09.027 回答