Merkle 哈希树是一类基于哈希值的二叉树或多叉树，其叶子节点 上的值通常为数据块的哈希值，而非叶子节点上的值是将该节点的所有子节点的组合结果的哈希值。如图 4-4 所示为一个 Merkle 哈希树，节点 A 的值必须通过节点 C、D 上的值计算而得到。叶子节点 C、D分别存储数据块 001 和 002 的哈希值，而非叶子节点 A 存储的是其子节点 C、D 的组合的哈希值，这类非叶子节点的哈希值被称作路径哈希值，而叶子节点的哈希值是实际数据的哈希值。
在计算机领域，Merkle 树大多用来进行完整性验证处理。在处理完整性验证的应用场景中，特别是在分布式环境下进行这样的验证时，Merkle 树会大大减少数据的传输量以及计算的复杂度。
例如，以图例，若 C、D、E 和 F 存储了一组数据块的哈希值，当把这些数据从 Alice 传输到 Bob 后，为验证传输到 Bob 的数据完整性，只需要验证 Alice 和 Bob 上所构造的 Merkle 树的根节点值是否一致即可。如果一致，表示数据在传输过程中没有发生改变。假如在传输过程中，E 对应的数据被人篡改，通过 Merkle 树很容易定位找到（因为此时，根节点、B、E 所对应的哈希值都发生了变化），定位的时间复杂度为 O（log（n））。比特币的轻量级节点所采用的 SPV 验证就是利用 Merkle 树这一优点。
分享到:
閱讀更多 scryinfo 的文章
