默克尔树

默克尔树（也称哈希树）是一种层次结构数据结构，其中每个叶子节点都代表一个层级。节点每个非叶子（父）节点都包含一个数据块的加密哈希值，并且每个非叶子（父）节点都包含其所有子节点哈希值连接后的加密哈希值。这种二叉树结构使得大型数据集的完整性和一致性验证异常高效——验证者无需检查每个单独的数据，只需检查从叶子节点到根节点的单个分支上的少量哈希值即可。位于树顶的单个哈希值，称为默克尔根，充当其下方整个数据集的唯一指纹。如果树中任何位置的哪怕一个数据位被篡改，这种更改都会向上级联，直至默克尔根本身也发生改变，从而立即表明数据已被篡改。

在区块链技术中，默克尔树是区块存储和验证交易的基础。比特币、以太坊以及几乎所有其他区块链协议中的每个区块头都包含一个默克尔根，它概括了该区块中包含的所有交易。这种设计使得轻量级客户端（通常称为简化支付验证 (SPV) 节点）无需下载整个区块的内容即可确认特定交易是否包含在区块中。客户端只需要区块头（包含默克尔根）以及一小段称为默克尔证明或默克尔路径的同级哈希序列。对于包含 4,096 笔交易的区块，此证明仅需 12 个哈希值，而不是全部 4,096 个交易哈希值——这种对数级的减少使得移动钱包和资源受限的设备也能参与到网络中。

除了简单的交易包含之外，默克尔树还支撑着加密货币生态系统中一些最先进的架构。以太坊使用一种名为默克尔帕特里夏树（Merkle Patricia Trie）的改进版本来存储其整个世界状态——包括每个账户余额、智能合约存储槽位和代码片段。零知识汇总（Zero-nowledge rollup）使用默克尔树将批量链下交易提交到单个链上根节点。空投分发合约使用默克尔树，使数千个地址能够以最少的链上数据领取代币。这种结构的精妙之处在于其简洁性：通过递归应用哈希算法，将任意大的数据集转换为单个固定大小的承诺，并且可以在对数时间内验证。

起源与历史

1979年： 拉尔夫·默克尔 (Ralph Merkle) 在其斯坦福大学博士论文中首次描述了哈希树，随后为该概念申请了专利（美国专利号 4,309,569，申请日为 1979 年 9 月 5 日，授权日为 1982 年 1 月 5 日）。默克尔开发这种结构是他公钥密码学和数字签名领域开创性工作的一部分，旨在寻找一种高效的大型数据结构认证方法。

1987-1988： Merkle 将他的哈希树结构与一次性签名方案相结合，并在早期的 Lamport-Diffie 一次性签名构造的基础上进行了改进。他在 87 年的 CRYPTO 会议上发表了一篇论文，该论文于 1988 年发表在会议论文集中。这种组合现在通常被称为 Merkle 签名方案，它证明了单个哈希树可以在一个公钥下验证多个一次性密钥对，从而有效地管理大量的加密密钥。

1990 年代后期： 随着点对点文件共享系统的出现，哈希树结构被应用于让节点独立验证已下载文件片段的完整性，从而无需重新下载整个文件即可检测出损坏或恶意数据。这种模式后来被正式写入诸如树哈希交换（THEX）格式之类的规范中。

2008年： 中本聪将默克尔树集成到了比特币协议设计中。比特币白皮书第 7 节“回收磁盘空间”描述了默克尔树如何允许在保留紧凑的根哈希的同时，对旧的交易数据进行修剪。第 8 节“简化支付验证”则单独解释了同样的结构如何让轻量级客户端仅使用区块头和默克尔证明来确认交易是否包含在区块中。

2009年： 比特币网络启动时，每个区块头都嵌入了默克尔根。创世区块（区块 0）包含一笔交易，其默克尔根等于该交易的哈希值，从而确立了所有后续区块的模式。

2015年： 以太坊在每个区块头中都包含了三种不同的默克尔树变体——交易树、收据树和状态树——全部以默克尔帕特里夏树的形式实现。这种设计将默克尔树的功能从简单的交易验证扩展到了完整的世界状态认证。

2017-2019： Merkle树成为二层扩容方案设计的核心。Plasma链使用Merkle承诺将子链状态锚定到以太坊主网上，而早期的Rollup设计则使用Merkle根将数百笔交易批量打包成单个链上证明。

2020-2024： 零知识证明系统（例如 zkSync 和 StarkNet）采用了专门的 Merkle 树变体——包括基于 Poseidon 哈希的稀疏 Merkle 树——这些变体针对零知识证明电路内部的高效计算进行了优化。Merkle 空投合约成为以太坊上代币分发的标准模式。

“哈希树允许独立检查哈希树的任何分支，而无需节点存储完整的数据集。”
——拉尔夫·默克尔，斯坦福大学博士论文（1979 年）

简单来说

想象一下体育锦标赛的赛程表。第一轮每场比赛都会产生一名获胜者。这些获胜者两两配对进行第二轮比赛，以此类推，直到决出最终的冠军。默克尔树的工作原理与之类似——只不过，它不是从体育队伍开始，而是从数据块开始；也不是进行比赛，而是使用加密哈希算法将成对的数据组合起来，直到在树的顶端得到一个被称为默克尔根的“冠军哈希值”。

把它想象成一棵反向的家谱树。最底层是数百个独立的家庭成员（数据块）。每一对兄弟姐妹组合起来代表他们的父母。这些父母组合起来代表他们的祖父母，以此类推，直到顶端的祖先。如果任何一位家庭成员发生变化，他/她上面的每一代都会随之改变，一直到顶端的祖先。

想象一下这样的图书馆目录系统。图书管理员不必逐一检查每个书架上的每本书来确认是否有遗漏，而是为每个书架创建一个概要，将书架概要汇总成通道概要，再将通道概要汇总成楼层概要，最后维护一个涵盖整个图书馆的总概要。要确认某本书是否存在，只需检查从书架到总概要的路径上的概要即可，无需检查其他所有书籍。

想象一下法庭案件中证据的密封过程。每件证据都装在一个防篡改信封里。两个信封依次放入更大的信封，再放入更大的信封，直到所有证据都被装进一个带有单一封条的总信封里。如果有人篡改了任何一件证据，它上面的所有信封都会出现篡改痕迹，最终总封条也会失效。

重要提示： 默克尔树能够证明数据的包含性和完整性，但它并不加密数据，也不提供保密性。任何有权访问该树的人都可以查看数据——该树仅保证数据未被篡改。此外，默克尔树的安全性完全取决于底层哈希函数的强度；如果哈希函数被破解，则该树的完整性必然会崩溃。

关键技术特征

二叉哈希树结构

叶子节点包含各个数据块（例如，交易）的哈希值。
内部节点包含其两个子节点哈希值连接后的哈希值： H(parent) = Hash(H(left) || H(right))
这棵树始终保持平衡；如果叶子的数量为奇数，则最后一片叶子会复制一份以形成一对。
树的深度是 log2(n) 协调 n 是叶节点的数量
根哈希（默克尔根）是整个数据集的固定大小指纹，与数据集大小无关。

Merkle证明验证的工作原理

验证者想要确认特定交易。 Tx_k 包含在一个块中
验证者获取区块头，其中包含默克尔根。
验证器提供哈希值 Tx_k 以及它的默克尔证明——从叶节点到根节点的路径上的兄弟哈希序列。
验证器哈希 Tx_k然后，使用相同的哈希函数将其与第一个同级哈希值合并。
将结果与下一个兄弟哈希值合并，依此类推，逐层向上遍历树。
如果最终计算出的哈希值与区块头中的默克尔根匹配，则验证该交易已包含在区块中。
对于一棵树 n 只有叶子 log2(n) 需要哈希值——例如，在 1,048,576 笔交易中，需要 20 个哈希值来验证 1 笔交易。

Merkle Patricia Trie（以太坊）

以太坊将基本的默克尔树扩展为帕特里夏树（基数树），该树将键映射到值。
状态树将账户地址映射到账户状态（余额、随机数、存储根、代码哈希）。
存储树将 256 位存储槽映射到每个智能合约对应的值。
路径压缩通过将单子链折叠成扩展节点来减少存储开销。
三种节点类型：分支节点（16 个子节点 + 值）、扩展节点（共享前缀 + 下一个节点）、叶节点（剩余路径 + 值）

用于零知识证明的稀疏默克尔树

稀疏默克尔树（SMT）是一种叶子节点大多为空（默认哈希值）的默克尔树。
用于 ZK-rollups 中，以高效的成员资格和非成员资格证明来表示账户状态。
像 Poseidon 和 Pedersen 这样的优化哈希函数用于 ZK 电路友好的计算。
深度为 256 的 SMT 可以表示所有可能的 256 位密钥，同时保持计算上的可行性。
证明不包含关系很简单，只需证明给定位置的叶子节点包含默认值即可。

优点缺点

优势	缺点
对数验证：证明规模和验证时间尺度 `O(log n)`即使面对数百万笔交易，也能实现高效验证。	存储开销：存储所有中间哈希值大约需要 `2n - 1` 节点 `n` 叶节点使原始数据存储需求大致翻倍
篡改检测：对任何叶节点的任何更改都会向上传播，改变默克尔根，并立即揭示数据损坏或篡改。	重新计算成本：更新单个叶子节点需要重新计算到根节点路径上的所有哈希值—— `O(log n)` 每次更新的哈希操作
轻量级客户端支持：SPV 节点仅需区块头和默克尔证明即可验证交易是否包含在内，从而支持移动钱包和嵌入式钱包。	哈希函数依赖性：整个安全模型依赖于所选哈希函数的抗碰撞性；一个失效的哈希函数会导致树结构失效。
带宽效率：默克尔证明仅传输 `log2(n)` 使用哈希值而非完整数据集，可大幅降低验证所需的网络带宽。	平衡要求：标准二叉默克尔树需要偶数个叶子节点；奇数个叶子节点的数据集需要重复，这可能会引入一些不易察觉的实现错误。
可组合性：默克尔树可以嵌套——默克尔根可以是更高层树中的叶子——从而支持用于汇总和分片的多层数据承诺方案。	字典树的复杂性：Merkle Patricia 字典树（如以太坊中的字典树）的实现比基本的二叉 Merkle 树复杂得多，因为它包含多种节点类型和路径编码。
并行构造：叶子哈希可以独立且并行地计算，这使得默克尔树的构造在现代硬件上高度可并行化。	状态膨胀：在有状态区块链中，默克尔树会随着每个新账户和存储槽位的增长而增长，这会导致长期状态膨胀并增加同步时间。
标准化且经过实战检验：数十年的学术研究和生产部署（比特币自 2009 年起）使我们对该结构的安全性充满信心。	证明规模的增长：虽然呈对数增长，但证明规模仍然会随着数据集规模的增长而增长；对于非常大的树（数十亿个叶子节点），证明的规模可能会变得非常庞大。

风险管理

哈希函数漏洞风险

Merkle 树继承了其底层哈希函数的安全特性（比特币通常使用 SHA-256，以太坊通常使用 Keccak-256）。
如果针对哈希函数的碰撞攻击变得可行，攻击者就可以构造两个具有相同默克尔根的不同数据集。
缓解措施：密切关注密码学研究，寻找针对 SHA-256 和 Keccak-256 的改进方案；区块链社区如有必要，可以通过硬分叉来升级哈希函数。
量子计算对哈希函数的安全性构成长期威胁，但目前的估计表明，SHA-256 在未来几十年内仍然是安全的。

实施缺陷风险

Merkle树实现中的一些细微错误——例如对奇数叶节点的处理不当、证明路径中的差一错误或字节序不匹配——都可能造成可被利用的漏洞。
2018 年比特币现金的“分裂”暴露了区块验证过程中默克尔树验证的极端情况。
缓解措施：使用经过充分审核的开源库（例如，OpenZeppelin 的 MerkleProof.sol 用于 Solidity）；对关键实现进行形式化验证。
使用对抗性输入进行测试，包括空树、单叶树和最大深度树。

类型歧义攻击风险

在朴素的默克尔树中，攻击者有可能创建一个与合法叶节点相冲突的欺诈性内部节点。
更准确的说法是类型歧义攻击或跨节点攻击，可以通过在哈希之前添加域分隔符（叶子节点为 0x00，内部节点为 0x01）来缓解。
比特币的默克尔树实现采用了双重 SHA-256 哈希算法，这提供了额外的抗干扰能力。
缓解措施：始终区分叶子节点和内部节点的哈希；遵循既定标准，例如 RFC 6962（证书透明度）。

国家增长和绩效风险

在以太坊中，状态树会随着每个新账户和合约存储槽位的增长而增长，从而随着时间的推移增加证明生成和验证的成本。
节点同步时间受状态树大小（数百GB）的显著影响。
缓解措施：状态过期提案（EIP-4444、Verkle树）旨在修剪历史状态；无状态客户端研究侧重于为每个数据块提供状态证明。

文化相关性

Merkle 树在加密货币文化中占据着独特的地位，它是少数几种在计算机科学界之外也广为人知的数据结构之一。“Merkle 证明”一词经常出现在 Discord 服务器、Twitter 推文和治理论坛的讨论中，参与者可能并不完全理解其背后的数学原理，但他们都意识到这个术语的重要性。

“默克尔树是区块链中默默无闻的英雄。每次验证交易时，都要感谢拉尔夫·默克尔。”
– Andreas M. Antonopoulos，《掌握比特币》（2017 年）

在2022年FTX倒闭期间，“储备金证明”的概念开始在主流加密文化中占据重要地位，这一概念也随之进入公众视野。币安和Kraken等交易所实施了基于默克尔树的储备金证明系统，使用户能够独立验证其资金是否包含在交易所公布的持仓中。“默克尔树储备金证明”在FTX倒闭后的环境中成为信任的象征，展现了这项1979年的计算机科学发明如何成为金融问责制的文化标志。

在 NFT 和空投社区，“Merkle 空投”已成为标准术语。Uniswap、ENS 和 Optimism 等项目使用基于 Merkle 树的分发合约，允许符合条件的地址通过提供 Merkle 证明来领取代币，证明其地址已列入分发列表。这种模式由 OpenZeppelin 库推广，已被数百个项目效仿，如今已成为链上代币分发的实际标准。

开发者社区经常就 Merkle 树与 Verkle 树（以太坊无状态路线图提出的一种新型替代方案）的优劣进行辩论，这反映出 Merkle 树结构在区块链架构讨论中根深蒂固。

实际例子

比特币SPV钱包验证

场景： 一位在存储空间有限的智能手机上运行移动比特币钱包的用户想要验证收到的 0.5 BTC 付款是否合法，但又不想下载整个 500+ GB 的区块链。

实施： SPV钱包仅下载区块头（每个区块头80字节，整个区块链历史记录总计约60MB）。当用户收到付款时，钱包会向完整节点请求默克尔证明——一组10-12个同级哈希值，用于追踪从交易到区块头中默克尔根的路径。

结果： 钱包通过重新计算直至默克尔根的哈希值来验证交易是否包含在区块中，从而确认支付的合法性。这只需几毫秒，且仅使用几千字节的数据，使得比特币能够在资源受限的移动设备上使用。这正是中本聪在比特币白皮书第 8 节中描述的用例。

Uniswap UNI 代币空投（2020）

场景： Uniswap需要向大约150万历史用户分发250,000亿枚UNI代币。将所有250,000万个地址存储在链上将耗费数百万美元的gas费。

实施： Uniswap 的工程师构建了一棵默克尔树，每个符合条件的地址及其可申领的代币数量都作为叶节点。链上仅存储了唯一的默克尔根节点（32 字节），位于分发合约中。每个用户都可以通过提交默克尔证明（250,000 万个地址大约需要 18 个哈希值）来申领其代币，该证明需证明其地址包含在默克尔树中。

结果： 空投合约占用的链上存储空间极少，同时允许任何符合条件的用户无需许可即可领取代币。每次领取所需的 Gas 费用约为 80,000 万至 100,000 万，而预先将所有地址加载到链上则需要数百万美元。这种模式此后已成为代币分发的行业标准。

币安储备证明（FTX 之后，2022 年）

场景： FTX倒闭后，币安面临着证明客户资金得到充分保障的迫切压力。该交易所持有大量用户账户的资产，因此逐个账户披露信息既不切实际，也侵犯了用户隐私。

实施： 币安实施了基于默克尔树的储备金证明系统，其中每个用户的账户余额都被哈希处理，形成一个叶子节点。用户可以通过登录并申请个人默克尔证明来验证其账户是否包含在内，并可独立地将其与已发布的默克尔根节点进行比对。第三方审计机构负责验证总储备金是否与默克尔根节点的承诺相符。

结果： 用户能够验证其账户是否包含在储备树中，从而恢复了人们对中心化交易所的一定程度的信任。虽然这种方法并非完美无缺（它并不能证明不存在负债），但它确立了基于默克尔树的透明度，并将其作为交易所问责制的一项广泛采用的标准。

DeFi协议的以太坊状态验证

场景： 以太坊上的 DeFi 借贷协议在处理清算之前，需要验证用户账户在二层汇总层上的当前抵押品余额。

实施： 该汇总系统将其状态根（所有账户余额的默克尔根）发布到以太坊主网。以太坊上的清算合约接受一个默克尔证明，该证明展示了用户在汇总系统状态树中的抵押余额。该证明包含大约 20-30 个哈希值，对应于一个稀疏的默克尔树，代表了非常庞大的可能账户空间。

结果： 跨层清算无需信任即可执行——无需信任任何预言机或桥接中继器。默克尔证明以加密方式将汇总状态绑定到主网合约，从而在不牺牲安全性的前提下实现 L1 和 L2 之间的可组合性。这种通用模式被广泛应用于多种汇总和跨链借贷设计中。

对比表

特性	默克尔树（二叉树）	Merkle Patricia Trie（以太坊）	维克尔树（拟定）
结构	哈希二叉树	带哈希承诺的基数树	带有向量承诺的树
校样尺寸	`O(log n)` 哈希值（每个约 32 字节）	`O(log n)` 但由于分支因子16而更大	`O(log n)` 但比默克尔证明要小
主要用途	交易包含（比特币）	完整的世界状态存储（以太坊）	无状态客户端验证（未来以太坊）
按键对应	位置（基于索引）	键值对（地址到状态）	键值对（地址到状态）
更新成本	`O(log n)` 重新散列	`O(log n)` 但会带来 trie 树重构的开销。	`O(log n)` 更便宜的承诺
证明验证	简单哈希重计算	更复杂（多种节点类型）	需要椭圆曲线运算
国家膨胀	最小（事务列表有界）	严重（状态无限增长）	较小的校样尺寸缓解了这一问题。
量子电阻	基于哈希的（相对量子安全的）	基于哈希的（相对量子安全的）	依赖于椭圆曲线（易受量子效应影响）
到期日	自 2009 年起部署（比特币）	自 2015 年起部署（以太坊）	研究/推广阶段（EIP-6800）

常见问题解答

问：什么是默克尔树？它对区块链为何如此重要？ 默克尔树是一种数据结构，它将数据组织成一棵加密哈希二叉树，生成一个代表整个数据集的根哈希。它对区块链至关重要，因为它能够实现高效的交易验证——轻量级客户端只需检查一个很小的默克尔证明（大小呈对数级），即可确认交易是否包含在区块中，而无需下载每笔交易。

问：默克尔证明是如何运作的？ Merkle 证明由从特定叶节点到 Merkle 根节点的路径上的同级哈希值组成。验证过程如下：首先对目标数据进行哈希运算，然后将其与第一个同级哈希值组合，再对结果进行哈希运算，与下一个同级哈希值组合，如此重复，直到到达根节点。如果计算出的根节点与已知的 Merkle 根节点匹配，则验证数据包含在树中。对于一棵拥有 1 万个叶节点的树，这只需要大约 20 个哈希值。

问：默克尔树和默克尔帕特里夏·特里有什么区别？ 标准的默克尔树是一种简单的二叉哈希树，用于存储有序数据列表（例如比特币区块中的交易）。以太坊使用的默克尔-帕特里夏树则是一种更复杂的结构，它结合了基数树（前缀树）和默克尔哈希，从而创建了一个具有可验证完整性的键值存储。

问：什么是Verkle树？它们会取代Merkle树吗？ Verkle 树是以太坊的一项升级提案（EIP-6800），它用多项式（向量）承诺取代了基于哈希的承诺，从而生成更小的证明，这对于以太坊的无状态客户端路线图至关重要。然而，Verkle 树依赖于椭圆曲线密码学，这可能容易受到量子计算机的攻击，而基于哈希的 Merkle 树则被认为更具抗量子攻击能力。

问：默克尔树是如何应用于NFT和代币空投的？ 项目会构建一个默克尔树，将符合条件的钱包地址（及其可申领的代币数量）作为叶子节点。链上仅存储默克尔树的根节点，从而节省 gas 费用。每个符合条件的用户都可以通过提交其默克尔证明来申领代币——默克尔证明是一组哈希值，用于证明其地址存在于默克尔树中。这种模式由 OpenZeppelin 的 MerkleProof 库推广开来，已被 Uniswap、ENS、Optimism 和数百个其他项目采用。

问：默克尔树可以用于保护隐私吗？ 标准的默克尔树不具备隐私保护功能——所有数据都是可见的。然而，隐私保护系统会使用一些专门的变体。零知识默克尔证明允许在不泄露叶子节点数据的情况下证明包含关系，从而实现私密交易和机密状态验证。

问：如果两个不同的数据集产生相同的默克尔根会发生什么？ 这将构成哈希碰撞——两个不同的输入通过哈希函数产生相同的输出。使用 SHA-256（比特币使用的哈希算法），找到这样的碰撞大约需要 2^128 次运算，这在当前和可预见的计算技术条件下是无法实现的。