4.2　Merkle树

Merkle哈希树是一类基于哈希值的二叉树或多叉树，其叶子节点上的值通常为数据块的哈希值，而非叶子节点上的值是 将该节点的所有子节点的组合结果的哈希值。如图4-4所示为一个Merkle哈希树，节点A的值必须通过节点C、D上的值计算而得到。叶子节点C、D分别 存储数据块001和002的哈希值，而非叶子节点A存储的是其子节点C、D的组合的哈希值，这类非叶子节点的哈希值被称作路径哈希值，而叶子节点的哈希值 是实际数据的哈希值。

在计算机领域，Merkle树大多用来进行完整性验证处理。在处理完整性验证的应用场景中，特别是在分布式环境下进行 这样的验证时，Merkle树会大大减少数据的传输量以及计算的复杂度。例如，以图4-4为例，若C、D、E和F存储了一组数据块的哈希值，当把这些数据 从Alice传输到Bob后，为验证传输到Bob的数据完整性，只需要验证Alice和Bob上所构造的Merkle树的根节点值是否一致即可。如果一 致，表示数据在传输过程中没有发生改变。假如在传输过程中，E对应的数据被人篡改，通过Merkle树很容易定位找到（因为此时，根节点、B、E所对应的 哈希值都发生了变化），定位的时间复杂度为O（log（n））。比特币的轻量级节点所采用的SPV验证就是利用Merkle树这一优点。

图4-4　Merkle哈希树

利用一个节点出发到达Merkle树的根所经过的路径上存储的哈希值，可以构造一个Merkle证明，验证范围可以是单个哈希值这样的少量数据，也可以是验证可能扩至无限规模的大量数据。

区块链中的Merkle树是二叉树，用于存储交易信息。每个交易两两配对，构成Merkle树的叶子节点，进而生成整个Merkle树。

Merkle树使得用户可以通过从区块头得到的Merkle树根和别的用户所提供的中间哈希值列表去验证某个交易是否包含在区块中。提供中间哈希值的用户并不需要是可信的，因为伪造区块头的代价很高，而中间哈希值如果伪造的话会导致验证失败。

如图4-4所示，为验证数据块003所对应的交易包含在区块中，除了Merkle树根外，用户只需要节点A对应的哈希 值Hash（C，D）以及节点F所对应的哈希值Hash（004）。除了数据块003外，他并不需要其他数据块所对应的交易明细。通过3次哈希计算，用户 就能够确认数据块003所对应的交易是否包含在区块中。实际上，若区块包含图4-4所对应的Merkle树，且区块所包含的4个交易的容量均达到最大值， 下载整个区块可能需要超过400000个字节，而下载两个哈希值加上区块头部仅需要120个字节。就我们的验证例子而言，可以减少很大的传输量。

来源：我是码农，转载请保留出处和链接！

本文链接：http://www.54manong.com/?id=1023