重点总结
Merkle 树是一种加密资料结构，它将资料组织成杂凑对，向上组合这些哈希，直到得到一个单独的杂凑（即 Merkle 根），该杂凑代表整个资料集。
Merkle 根允许区块链网路在不下载整个区块的情况下验证交易是否包含在区块中，它使用紧凑的 Merkle 证明，其规模随交易数量呈对数增长。
比特币将梅克尔根嵌入到每个区块头中，使轻量级客户端能够仅使用区块头而不是整个区块链来验证交易。
以太坊使用更复杂的 Merkle Patricia Trie 演算法来储存帐户余额和智慧合约状态，使得轻客户端和 Layer-2 Rollup 的状态证明成为可能。
介绍
梅克尔树是区块链系统高效且可大规模验证的基础概念之一。它允许网路将整个资料集概括为一个单一的加密指纹，同时也能证明特定交易或资讯包含在其中。为了理解梅克尔树在区块链设计中的重要性，让我们来看看它的工作原理、不同网路如何使用它，以及像维克尔树这样的新型结构未来可能如何改进它。
梅克尔树的工作原理
梅克尔树（Merkle tree）以计算机科学家拉尔夫·默克尔（Ralph Merkle）的名字命名，他于1979年获得了该概念的专利。梅克尔树是一种用于高效汇总和验证大型资料集完整性的资料结构。在区块链中，梅克尔树将数千笔交易压缩成一个紧凑的值，并储存在区块头中。
这棵树是从下往上建构的，使用加密杂凑函数。每个叶子节点包含一条资料（例如一笔交易）的杂凑值。这些叶子节点的杂凑值两两配对：每对杂凑值的计算方法是将两个子节点的杂凑值连接起来，然后对结果进行杂凑运算。这个过程逐层向上重复，直到树顶只剩下一个哈希值，即默克尔根。
由于每个父节点都依赖其两个子节点，因此对单一叶节点的任何变更都会向上级联，并产生完全不同的默克尔根。这项特性使得梅克尔树成为侦测窜改的有效工具：如果资料集的两个副本产生相同的梅克尔根，则这两个资料集极有可能相同。
梅克尔根
Merkle 根是一个固定大小的杂凑值，在区块链应用中通常为 32 个位元组（256 位元），它充当整个资料集的数位指纹。大多数区块链网路的区块头都包含 Merkle 根以及其他元数据，例如时间戳记和前一个区块的杂凑值，这既能保持区块头的简洁，又能以加密方式确保区块内所有交易的完整资讯。
为了简单说明，我们来看一个 8GB 的文件，它被分割成八个片段。我们把这些片段分别称为 A 到 H。然后，每个片段都经过一个杂凑函数处理，得到八个不同的杂凑值。
有了所有片段的杂凑值，如果其中一个片段有误，你可以透过将其与原始档案的杂凑值进行比较来发现，对吗？或许如此，但这效率极低。如果你的档案有成千上万个片段，你会对它们全部进行哈希处理并仔细比较结果吗？
梅克尔根提供了一种更优雅的解决方案。取每一对杂凑值，将它们组合起来，然后再进行哈希运算。这样就得到了杂凑值 hA + hB、hC + hD、hE + hF 和 hG + hH，最后得到四个杂凑值。
然后，再进行一轮哈希运算，你会得到两个结果：hABCD 和 hEFGH。最后，将剩下的两个结果进行杂凑运算，得到主杂凑值，也就是梅克尔根（或根杂凑值）：hABCDEFGH。
梅克尔证明与验证
Merkle 树最实用的功能之一是能够在不泄露整个资料集的情况下证明特定资料属于资料集。这被称为 Merkle 证明。为了验证某个交易是否包含在区块中，轻客户端只需要交易本身、沿著路径到达根节点的一小部分兄弟哈希值，以及来自区块头的 Merkle 根节点。验证器重新计算路径上的杂凑值，并检查结果是否与已知的根节点相符。如果匹配，则从数学上证明该交易是区块的一部分。
我们来看一个验证交易 ID 为 hD 的交易的场景。如果提供了 hC，就可以计算出 hCD。然后，使用 hAB 计算 hABCD。最后，使用 hEFGH 检查产生的 Merkle 根是否与区块头中的 Merkle 根相符。如果匹配，则证明该交易已包含在区块中。使用不同的资料几乎不可能产生相同的杂凑值。
在上面的例子中，你只需要哈希三次。如果没有梅克尔证明，则需要哈希七次。由于现在的区块包含数千笔交易，使用梅克尔证明可以节省大量时间和运算资源。
证明的大小随叶子节点的数量呈对数增长：对于一百万笔交易（深度为 20 的二叉树），只需要大约 20 个哈希值，约 640 位元组。这使得轻量级节点（有时称为简化支付验证 (SPV) 用户端）无需下载整个区块链即可验证交易，否则下载整个区块链将需要数百 GB 的资料。
区块链网路中的梅克尔树
比特币和交易验证
在比特币中，每个区块头都包含一个 32 个位元组的梅克尔根，它承诺该区块中的所有交易。比特币矿工根据他们包含的交易建立梅克尔树，并将生成的梅克尔根与工作量证明机制一起嵌入区块头中。这种设计意味著，通常约 80 位元组的区块头足以验证任何特定交易是否包含在该区块中，而无需验证其他交易。
比特币在其 MAST（默克尔化抽象语法树）提案中也使用了梅克尔树，这使得比特币脚本中复杂的支出条件能够以梅克尔树的形式表示。这样一来，只需要公开脚本中已执行的分支，从而保护未使用的条件的隐私性并减少交易规模。
以太坊和状态证明
以太坊使用了一种更复杂的变体，称为 Merkle Patricia Trie，它是一种十六进制（16 路）树状结构，用于储存帐户余额、合约代码和储存资料。与比特币交易使用的简单二叉 Merkle 树不同，Merkle Patricia Trie 旨在支援频繁的状态更新：当帐户余额发生变化时，只需重新计算从该叶节点到根节点的路径，而无需重建整棵树。
基于 Merkle-Patricia-Trie 产生的状态证明允许以太坊轻客户端和 Layer-2 Rollup 在无需运行完整节点的情况下验证帐户余额和合约储存。这些证明对于需要从一条链验证另一条链上事件的跨链桥也至关重要。
限制和未来发展
尽管梅克尔树提供了高效的验证方式，但证明的大小仍然会随著资料集呈对数增长。对于以太坊而言，随著状态的成长，区块见证（即验证区块所需的证明）的大小可能会达到数兆位元组。这给无状态客户端带来了可扩展性挑战，因为它们需要接收并验证每个区块的这些证明。
Verkle 树使用基于多项式（Kate-Zaverucha-Goldberg，简称 KZG）承诺的向量承诺，而非传统的杂凑演算法，提供了潜在的解决方案。透过在每个节点下分组多个子节点（分支因子为 256），Verkle 树产生的证明大小几乎恒定，约为 170 位元组，无论资料集有多大。以太坊正在积极开发 Verkle 树集成，预计将在未来的升级中部署。这项转变将显著降低轻客户端的资料负载，并提升整个网路的可扩展性。
常问问题
简单来说，什么是默克尔树？
梅克尔树是一种组织资料的方法，它使得一个很小的资讯单元（梅克尔根）可以代表一大组资料。其工作原理是反复对资料对进行杂凑运算，直到只剩下一个杂凑值为止，这样就可以在不逐个检查每个资料项的情况下，验证某个特定资料项是否属于该集合。
什么是梅克尔根？
默克尔根是默克尔树顶端的单一哈希。它就像一个紧凑的数位指纹，代表其下的所有数据。在区块链网路中，梅克尔根储存在区块头中，并提交到该区块中的每笔交易，从而可以有效地验证交易是否属于某个区块。
梅克尔证明是如何运作的？
Merkle 证明提供了一个交易以及重新计算从该交易到 Merkle 根的路径所需的最小兄弟哈希集合。验证者对交易进行杂凑处理，将其与提供的兄弟杂凑按正确顺序组合，并检查最终结果是否与区块头中已知的 Merkle 根匹配。如果匹配，则证明该交易包含在 Merkle 根中。
为什么梅克尔树对区块链很重要？
Merkle树允许区块链网路将区块头与完整的交易资料分开。轻客户端只需下载区块头（每个区块约80位元组），即可使用简洁的Merkle证明验证交易是否包含在内。如果没有Merkle树，验证交易则需要下载完整的区块或整个链。
Merkle树和Verkle树有什么差别？
两者都是用来证明资料成员关系的加密累加器，但它们使用的数学原理不同。梅克尔树使用杂凑函数，产生的证明档案大小随资料集呈对数增长（O(log n)）。而维克尔树使用多项式（KZG）承诺，产生的证明档案大小几乎恒定，无论资料集大小如何，都只有几百字节，因此更适合大规模区块链状态证明。
结语
Merkle树是区块链架构的基石，它能够实现大规模的无需信任的验证。透过将整个交易区块压缩成一个32位元组的杂凑值，Merkle树允许参与者在无需下载所有资料的情况下验证资料。这项原理支撑著从比特币SPV钱包到以太坊状态证明和跨链桥等各种技术。随著区块链网路的不断发展，诸如Verkle树之类的新型加密结构最终可能会补充或取代Merkle树，但其底层概念——高效的、基于哈希的数据完整性——很可能在未来几年内仍将是分散式系统的基本构建模组。
延伸阅读
什么是区块链共识演算法？
密码学史
区块链第一层与第二层扩展解决方案
什么是分片？它是如何运作的？
免责声明：本内容仅供一般资讯和教育用途，按「原样」提供，不作任何形式的陈述或保证。本内容不应被视为财务、法律或其他专业建议，亦不旨在推荐购买任何特定产品或服务。您应向合适的专业顾问寻求建议。如内容由第三方贡献者提供，请注意，其表达的观点仅代表该第三方贡献者，并不一定反映币安学院的观点。数位资产价格可能波动。您的投资价值可能下跌或上涨，您可能无法收回全部投资金额。您对您的投资决策负完全责任，而币安学院对您可能遭受的任何损失概不负责。更多信息，请参阅我们的使用条款、风险提示和币安学院条款。