Merkle Tree

用途

使大规模数据的完整性验证可高效定位到具体数据块。

机制

叶节点为数据块哈希 H(d_i)。内部节点为子节点哈希拼接再哈希 H(left||right)。根哈希代表整体。验证某块只需从根到叶的 O(log n) 个兄弟哈希（Merkle proof）。改动任何数据块改变根哈希。

用例

• Git 对象树验证
• 区块链交易验证
• IPFS 内容寻址
• 分布式存储一致性

示例

• 输入

  4 data blocks → a 2-level Merkle tree

  输出

  The root hash represents all of them

  O(log n) verification

常见错误

Weak hashes enable collision forgery

Use a secure hash such as SHA-256