Merkle 树

定义

Merkle 树（默克尔树、哈希树）由 Ralph Merkle 于 1979 年提出：叶子节点是数据块的哈希，每个内部节点是其子节点哈希拼接后的哈希，树根（Merkle root）成为整个数据集的紧凑指纹。

原理

要证明某个数据块属于该集合，只需提供从该叶子到根路径上的兄弟哈希（Merkle proof），验证者做 O(log n) 次哈希即可核对，无需下载全部数据。任何数据被篡改都会导致根哈希变化。

应用

比特币用 Merkle 树聚合区块内交易，使轻钱包能做简化支付验证（SPV）；以太坊使用其变体 Merkle Patricia Trie 维护全局状态；Git 的对象模型、证书透明度日志、Amazon DynamoDB 与 Cassandra 的反熵同步、BitTorrent 和 IPFS 的分块校验都建立在同一思想上。

扩展

哈希签名方案（如 XMSS、SPHINCS+）用 Merkle 树把大量一次性签名密钥压缩为单个公钥，是后量子签名的重要路线。