Merkle 树详解：Merkle Tree、Patricia Trie 与 Search Tree
区块链、BitTorrent、Git 各自的可信性，归根结底都建立在同一种「哈希之树」结构之上。本文从最基础的 Merkle Tree 讲起，进而深入支撑以太坊状态管理的 Merkle Patricia Trie，最后介绍面向 P2P 副本同步而生的 Merkle Search Tree，梳理三者的构造、证明机制与各自的适用场景。
Merkle Tree 基础:把海量数据捆成一个哈希
Merkle 树由 Ralph Merkle 于 1979 年提交专利申请（相关论文发表于 1987 年），是一种用哈希把海量数据捆成一个短小「指纹」的树形结构。做法很简单：把原始数据切分成若干块，对每一块单独求哈希作为叶节点；每两个（或若干个）子节点的哈希拼接后再求一次哈希，作为其父节点；如此逐层向上合并，直到只剩下一个节点，即Merkle 根。哈希函数的输出通常只有 32 字节左右，但它却是对整棵树、也就是对全部原始数据的一份承诺（commitment）：只要数据有一丝改动，重新计算出的根就会截然不同。
Merkle 证明（也称包含证明，inclusion proof）是这一结构最实用的性质：要证明「某个数据块确实属于这棵树」，无需提供全部数据，只需要提供从该叶节点到根的路径上，每一步兄弟节点的哈希即可，数量为 log₂n 个。举例来说，即使原始数据多达一百万块，证明也只需约 20 个哈希、几百字节大小，验证者手里只要有一个已经确认可信的根，就能在本地重新计算路径上的哈希并比对是否与根一致，而完全不必下载或信任其余的数据。
- 防篡改：因哈希函数的雪崩效应，数据中任意一比特的变化都会一路传导、改变最终的根，篡改无处遁形。
- 证明大小为 O(log n)：无论原始数据集多大，单条包含证明的长度都只随数据规模的对数增长，非常适合在带宽受限的环境中传递。
- 支持分块校验与并行下载：因为每个叶节点都能独立验证，接收方每收到一块数据就能立即核实，不必等待全部数据到齐，这正是 BitTorrent、IPFS 等系统能够并行、乱序下载的基础。
- 二次原像攻击的防范：若不加区分地对叶节点与内部节点使用同一种拼接方式，攻击者有可能把一个内部节点误当作叶节点提交伪造证明。RFC 6962（Certificate Transparency）等规范的做法是，在哈希前给叶节点加上
0x00前缀、给内部节点加上0x01前缀，以此从结构上杜绝这类混淆。
| 系统 | 对什么做 Merkle 化 | 目的 |
|---|---|---|
| Bitcoin | 一个区块内的全部交易 | 把根写入区块头，支持 SPV 轻节点的轻量验证 |
| BitTorrent v2（BEP 52） | 按文件构建分片哈希树 | 逐片即时校验，发现损坏时只需重新获取受影响的分片 |
| IPFS | Merkle DAG 中的各个对象 | 以内容本身的哈希作为地址（CID），天然去重 |
| Certificate Transparency | 证书日志 | 仅追加的日志结构，提供包含证明与一致性证明，防止证书被悄悄篡改或撤下 |
| Git | commit → tree → blob 的哈希链 | 保障整个版本历史的完整性，任何历史节点被篡改都会改变后续所有哈希 |
校验「一份固定不变的数据列表」，朴素的 Merkle Tree 已经足够优雅。但现实中的很多场景需要按键（key）随机存取、需要频繁更新其中一小部分、抑或需要高效比较两份不断变化的副本之间到底差在哪里。面对这些需求，朴素的 Merkle Tree 会显得力不从心。下面两种结构，分别是针对「可更新的键值存储」与「可比较的副本同步」演化出的答案。
Merkle Patricia Trie:可验证的键值存储（以太坊）
区块链的「状态」，即账户余额、合约存储，本质上是一个不断更新的键值映射。如果每次有一笔交易改变了状态，就要把全部数据重新构建成一棵 Merkle Tree 再求根，开销显然无法接受。以太坊等系统采用的 Merkle Patricia Trie（MPT） 解决了这个问题：更新一个键时，只需要重新计算该键所在路径上的少数几个节点，树的其余部分原封不动；而且树的最终形状只取决于「有哪些键」，与插入顺序无关。
其底层结构是带有路径压缩（Patricia）的基数树（radix trie）。以太坊的做法是把键（通常是账户地址或存储槽位的哈希）按十六进制拆成一个个半字节（nibble），沿着 0〜15 这 16 个分支逐位向下遍历，因此整棵树呈 16 叉结构。
- branch 节点
- 拥有 16 个子节点槽位，分别对应下一个 nibble 的 16 种取值，此外还额外保留一个槽位存放「路径恰好在此终止」时的值。
- extension 节点
- 当某一段路径上没有任何分支、多个键共享同一段前缀时，把这段共享前缀压缩进单个节点，避免为每个 nibble 都单独建一层，从而节省深度与存储。
- leaf 节点
- 存放剩余未消耗的键路径与对应的值，是查找路径的终点。
为了在共享的节点编码格式中区分 leaf 节点与 extension 节点、并处理 nibble 路径长度奇偶不定的问题，MPT 采用一种被称为 hex-prefix 编码 的前缀标记方案，用编码后首字节的高位标志位记录节点类型与路径的奇偶性。
区块头中携带的 stateRoot 就是整个「世界状态」trie 的根，此外交易 trie 与回执（receipt）trie 也各自有自己的根；每个合约账户还拥有一棵独立的 storage trie，专门保存该合约的存储槽内容。有了这套结构，轻客户端不必同步整条链的全部状态，只要拿到一个可信的 stateRoot，再向全节点索取一份针对该账户的 Merkle 证明，就能独立验证「某地址的余额确实是多少」。此外，以太坊实际使用的是所谓 secure trie：键并非地址本身，而是 keccak256(地址)，这是为了防止攻击者故意构造出以相近字节开头的地址，人为拉长树的某条路径来发起拒绝服务攻击。
- I/O 放大：树中的每个节点经 RLP（Recursive Length Prefix，以太坊使用的一种二进制序列化编码）编码后，以「哈希 → 节点内容」的形式存入 LevelDB 等普通键值数据库。逻辑上的一次读写，在物理上往往要沿路径依次访问多个节点，造成显著的 I/O 放大。
- 状态膨胀（state bloat）：账户与合约存储只增不减，MPT 的节点数随之持续累积，给全节点的存储与同步带来长期压力，是以太坊生态长期关注的课题之一。
- 后继方案的讨论：为压缩证明尺寸、缓解无状态客户端（stateless Ethereum）场景下证明过大的问题，业界正在讨论以基于向量承诺的 Verkle 树，乃至更朴素的 binary trie 取代当前的 MPT，两者都致力于让「只凭证明即可验证状态」的成本进一步降低。
Merkle Search Tree:与插入顺序无关的「收敛之树」（2019）
在 P2P 副本同步（anti-entropy）的场景中，两个节点常常需要回答这样一个问题：「我们各自持有的集合是否相同？如果不同，差在哪里？」理想的做法是像 Merkle Tree 那样先比较根，一旦不一致就只往下追踪分歧所在的子树，从而以 O(log n) 的代价定位差异，而不必逐条比对整个集合。问题在于，普通的 B 树或平衡二叉搜索树，其形状会随插入顺序而变化：同样的一组键，以不同顺序插入可能得到完全不同的树，连带根哈希也不同，这就使得「比较根哈希」这件事从根本上失去了意义。
Merkle Search Tree（MST，Auvolat & Taïani，2019 年提出）解决了这一矛盾。做法是对每个键求哈希，并数出哈希值开头（在某个基数 B 下）连续为零的位数，以此决定该键所处的「层（layer）」：出现连续零越多的键，层级越高、越靠近树的上层。由于层级完全由键的哈希决定，树的整体形状便只取决于「有哪些键」，与插入顺序无关，这就是它的确定性。整体外观与 B 树相似，层级的概率分布也保证了树在期望意义上是平衡的。
- 唯一性：只要两个节点持有的键集合相同，无论各自是以什么顺序插入构建的，最终得到的树结构与根哈希必然完全一致，这正是可以直接「比较根哈希」的前提。
- 期望深度 O(log n)：层级由哈希的分布决定，与随机平衡树类似，期望深度维持在对数级别，不会因为特定的插入顺序退化成链表状的最坏情况。
- 差异同步：两节点先比较各自的根哈希，只要不一致就沿着分歧的子树继续下探比较，最终只需要传输实际存在差异的那部分子树，而不是整个数据集。
- 与 CRDT、[流言协议](/gossip) 的天然契合：MST 本身就是为基于状态的 CRDT 合并与 gossip 式的 anti-entropy 传播而设计的，节点之间可以周期性地互相交换根哈希，一旦发现不一致就用差异同步机制补齐缺失的部分。
Bluesky 的 AT Protocol 是 MST 广为人知的一个落地案例。每个用户账号的仓库（repository），也就是帖子、点赞、关注关系等全部记录，都组织成一棵 MST，用户对当前的根哈希（commit）签名，既能为单条记录出具「确实存在于仓库中」的证明，也让 relay（中继）之间只需交换根哈希、按差异同步的方式即可高效地复制彼此的数据。
三种结构如何选择
| 维度 | Merkle Tree | Merkle Patricia Trie | Merkle Search Tree |
|---|---|---|---|
| 数据模型 | 静态的列表或集合 | 持续更新的键值映射 | 有序的集合或映射 |
| 结构确定性 | 取决于具体的构建方式（分块顺序等） | 由键集合唯一确定，与插入顺序无关 | 由键集合唯一确定，与插入顺序无关 |
| 擅长操作 | 包含证明与批量数据校验 | 更新与证明兼顾的状态管理 | 两份副本之间的差异检测与同步 |
| 证明/同步成本 | 证明大小为 O(log n) | 证明沿路径逐节点累积，单条证明往往比 Merkle Tree 更大 | 只需传输实际存在差异的子树 |
| 代表性应用 | Bitcoin SPV、Certificate Transparency、BitTorrent v2 | 以太坊状态（账户、合约存储） | AT Protocol（Bluesky） |
三者并非互相替代的关系，而是回答不同问题的工具：如果要验证的是「一份固定不变的数据是否包含某个元素」，朴素的 Merkle Tree 最简洁高效；如果要管理的是「持续变化、需要随时按键更新与证明」的状态，Merkle Patricia Trie 这类可更新的树形键值存储更合适；如果目标是「两份不断演化的副本之间，如何用最少的通信量对齐」，Merkle Search Tree 这类确定性结构才是正解。
常见误解与注意事项
- 「有了根哈希就能找回数据」是误解：Merkle 树能证明的只是「数据完整、未被篡改」，并不保证持有数据的节点愿意或者能够把数据交出来。「数据本身是否仍然可获取」是另一个独立的问题，即所谓的数据可用性（data availability）问题，也是 rollup 类扩容方案设计中的核心议题之一。
- 「有 Merkle 证明就代表内容为真」也是误解：证明所验证的，始终是「这份数据与某个给定的根一致」，而这个根本身是否可信，证明本身无法回答。根的可信性必须另外由共识机制、签名、可信通道等方式来背书。
- 「MPT 是 Merkle Tree 的全面升级版」并不准确：为了支持更新与按键查找，MPT 付出了证明尺寸更大、实现更复杂的代价。对于本来就不会变化的静态数据集，朴素的 Merkle Tree 依然是更精简、更容易实现的选择。
- 一切都建立在哈希函数的抗碰撞性之上：一旦所用的哈希函数被找到碰撞，整套「根哈希即可信凭证」的逻辑就会崩溃。SHA-1 碰撞被证实可行后，Git 与早期的 Certificate Transparency 部署都不得不正视这一现实，这也是 SHA-1 逐步被 SHA-256 等更强哈希函数取代的原因之一。
相关页面
Merkle 树的思想几乎渗透在本站介绍的每一项技术之中：DHT 详解中，内容寻址本身就是一种「用哈希作地址」的思路；BitTorrent 详解里，BEP 52 引入的按文件分片哈希树正是本文开篇所讲的 Merkle Tree 在实践中的直接应用；流言协议所依赖的 anti-entropy 同步，与 Merkle Search Tree 的差异检测机制可以说是天造地设的一对；而根哈希本身的可信性，最终要靠分布式共识中的机制来背书；运行在以太坊 stateRoot 之上的 智能合约，其每一次状态变更都会反映到 Merkle Patricia Trie 中；至于围绕哈希树可能出现的构造性攻击手法，可参阅攻击手段与防御。