Merkle 树：大规模交易完整性

一个比特币区块包含约 2000 笔交易。要证明交易 T 被包含其中，而不下载全部 2000 笔交易，我们需要一种紧凑的证明。默克尔树解决了这个问题：证明大小是 O(log n) 个哈希值，而不是 O(n) 笔交易。

叶节点：对每笔交易执行 SHA256d（双重 SHA-256）。父节点：SHA256d(left_child_hash || right_child_hash)。重复此过程，直到得到一个根哈希值。如果节点数量为奇数，则复制最后一个节点。根就是存储在区块头中的默克尔根（32 字节）。

import hashlib def sha256d(x): return hashlib.sha256(hashlib.sha256(x).digest()).digest() def merkle_root(txids): if len(txids)%2: txids.append(txids[-1]) while len(txids)>1: txids=[sha256d(txids[i]+txids[i+1]) for i in range(0,len(txids),2)] return txids[0].hex()

要证明交易 T 位于位置 i，需要提供从 T 的叶节点到根的每一层上的兄弟哈希值（O(log n) 个哈希值）。验证者根据 T 和兄弟路径重新计算根。如果计算出的根与区块头中的默克尔根匹配，就证明了 T 被包含其中。

1024 笔交易 → 默克尔证明 = 10 个哈希值 = 320 字节。完整区块 = 约 1 MB。SPV 客户端只需为其关注的每笔交易下载 80 字节的区块头 + 320 字节的默克尔证明；与下载完整区块相比，可节省 99.97% 的带宽。

如果树中的任何交易发生变化，其叶哈希值就会改变，并逐层向上传播，最终改变默克尔根。修改后的根将不再匹配区块头中的根（区块头由 PoW 封存）。通过根据交易计算根，就能检测出任何修改。

Ethereum 通过字典树扩展了默克尔树（Patricia 默克尔字典树）：这是一种采用十六进制前缀编码的基数树，每个节点都经过默克尔哈希处理。它用于：状态字典树（账户余额）、交易字典树和收据字典树。这样无需完整的节点数据，就能高效证明账户状态。

默克尔山脉（MMR）是一种用于日志式数据的只能追加的默克尔结构。新元素会被追加，同时维护各个峰值（大小为 2 的幂的子树的根）。它用于 Grin/MimbleWimble 和 ZCash，以便针对只能追加的日志生成高效、紧凑的证明。

在 Ethereum 的路线图（EIP-6800）中，Verkle 树将取代默克尔树：它使用向量承诺（KZG 多项式承诺）代替哈希值。证明大小为 O(1)，而默克尔树为 O(log n)。这样，无状态客户端无需存储完整字典树即可验证状态。

证书透明度（RFC 6962）使用只能追加的默克尔日志：每个 CA 签发的证书都是一个叶节点。包含证明用于验证某个证书是否已记录。一致性证明用于验证日志是否只能追加（没有删除或插入）。浏览器厂商通过该日志验证 SCT。

Git 树（目录快照）就是默克尔树：每个树节点都会对其文件对象和子树取哈希。提交哈希唯一标识整个代码库的状态。这就是为什么 git checkout 总能得到完全相同的文件。

默克尔树支持 O(log n) 的包含证明。比特币将默克尔根存储在区块头中，SPV 客户端使用这些证明。Ethereum 将其扩展为 Patricia 默克尔字典树。Verkle 树将以 O(1) 证明取代默克尔树。下一节：工作量证明挖矿与难度。