哈希树有什么用处？

Question

我在维基百科上看到 哈希树，但我不理解这种结构的好处或目的-它们似乎需要比每个叶子节点只有一个哈希更多的哈希值，而没有显着利用额外的哈希值。

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

是否有人能够解释哈希树如何以及为什么有用？

提前致谢，

摩西

- Moshe

Answer 1

1. 哈希树可以并行计算。如果您有两个数据块要哈希，您可以使用两个处理器以两倍的速度计算哈希。但前提是哈希速度低于IO速度，这不太可能。

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

例如，如果我想向您发送文件，可以将其分成每个1 MiB的块，并将每个块及其SHA-256哈希发送给您。如果任何单个块的哈希不正确，那么您可以要求再次发送该块。最后，我可以签署文件的树哈希并发送签署的哈希给您。您只需哈希每个块哈希（已验证）即可验证哈希，这比重新哈希整个文件要快得多。

为什么使用树哈希？

无论何时您想要计算文件部分和整个文件的哈希，使用树哈希都很有优势。使用常规哈希（如SHA-256），您必须分别对文件块和整个文件进行哈希。如果文件大小为8 GiB，则这可能需要相当长的时间。使用树哈希，因为块的哈希用于计算文件的哈希，所以计算两个哈希不需要额外的工作。

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

计算树哈希的“额外工作”实际上非常小。是的，确实需要计算额外的哈希 - 但只需要O（1）的额外工作量。如果您的块大小为1 MiB，则如果文件大小小于或等于1 MiB，则额外工作量大约为零。随着数据大小的增加，额外工作量将接近于每个数据块的两个哈希的1个额外哈希 - 对于SHA-256，核心最多只会评估每个1 MiB的数据两次（一次用于输入哈希，一次用于填充）。这并不多。

- Dietrich Epp

---

你可以通过哈希每个块的哈希值（你已经验证过了）来验证树哈希。这比重新哈希整个文件要快得多。那么，为什么不直接从我们拥有的所有块哈希中集体查找哈希，而不是构造一棵树呢？例如，如果block1...blockN的哈希值为h1...hn，为什么不只执行hash(h1+h2+...+hn)，而不是使用不必要的中间内部哈希（内部节点）构造一棵树？能否请您解释使用树的必要性？ - Gokul NC

@GokulNC：那需要存储和传输所有中间哈希值。使用树结构，您只需要存储或传输父节点的哈希值。当然，您可以按照您描述的方式实现，但我不知道其中的好处是什么。 - Dietrich Epp

我觉得我没有用正确的措辞表达我的问题。我的意思是问，为什么我们要逐层计算哈希值（在树中使用中间层）来获取父节点哈希值，而不是通过将所有块/叶子的哈希值组合在一个步骤中并计算组合的哈希值来完成呢？为什么要使用树结构？ - Gokul NC

@GokulNC：这正是我认为你所问的。仅使用一个中间级别意味着您必须存储/传输所有中间哈希以计算整个文件的哈希，即您需要保留h1...hn直到您可以将它们合并。对于1TB的文件，您需要大约32MB的空间来验证哈希。这是很多额外的存储空间，但有什么好处呢？然后，您将被限制为1 MiB块大小，无法像树哈希一样将其更改为2或4。 - Dietrich Epp