命名空间默克尔树

我们在文章 "Beyond IBC" 中已经相对深入地讨论了 Merkle 树和 Verkle 树的工作原理。然而，还有其他 Merkle 树的应用和衍生物，我们认为它们值得独立成文，因为它们具有独特的特性。

在本文中，我们将讨论命名空间 Merkle 树 (NMT)、Merkle 树 Ranges (MMR) 和Jelly Merkle 树 (JMT)。因此，本文将解释它们的一些有趣方面、使用案例，并希望你会想进一步探索数据结构。

数据结构的历史

在谈论区块链行业许多基础设施项目的内部工作时，Merkle 树是最常被提及的数据结构。它们以 Ralph Merkle 的名字命名，后者在 1979 年获得这一概念的专利，并在他的论文 "A Certified Digital Signature" 中引入了它们。

Ralph Merkle 在《A Certified Digital Signature》中展示的 Merkle 树

它们在加密行业受到如此多的关注，这并不令人惊讶，因为它们在区块链的全球状态和交易根的承诺中是关键的数据结构。最明显的例子是，Merkle 树在原始 比特币白皮书 的第 4 页首次被提及。使用 Merkle 树在区块头中的主要优势被陈述为允许节点丢弃已支出的交易，从而节省磁盘空间。

原始比特币白皮书中提到的 Merkle 树

作为可扩展性研究的一部分（包括无状态性），许多资源被用于改变 Merkle 树。这是因为在尝试以允许人们继续运行节点的方式扩展区块链时（为什么？请参见 终端用户验证），必须最小化资源使用。从这个角度看，Merkle 树的各种“变体”是扩展和安全领域中引人入胜的创新。

在我们深入探讨希望展示的各种数据结构之前，有一点是值得一提的，即它们中的一些有不同的用途。例如，JMTs、Patricia 树（在 ETH 中）和 Verkle 树用于承诺全球状态根，而 NMTs 和 MMRs 则用于事务 Merkle 根。然而，两者的根（顶节点）通常会在区块头中提供。在以太坊的案例中，标准的 Merkle 树用于事务数据，而 Patricia 树则用于全局状态树。

命名空间 Merkle 树

命名空间 Merkle 树，也称为 "NMTs"，是一种用于在区块链上组织和验证大量数据集合的数据结构。作为上述更知名的 Merkle 树数据结构的一种变种，它们在效率和可扩展性方面提供了许多优势，特别是在应用和请求特定数据的 rollups 方面。它们最初在 2019 年由 Celestia 的 Mustafa Al-Bassam 在其博士论文 LazyLedger 中提出。

Mustafa Al-Bassam 在其博士论文中展示的 NMT 原始图

NMT 的一个主要好处是它们能够将数据组织成层次结构，允许有效地验证应用程序请求的单个或独立数据片段。作为用户，你只需要检索相应的叶节点及其父节点，而不是整个数据集。

另一个优势是它能够扩展到非常大的数据集合。这是通过使用多级的“命名空间”节点来实现的，这使得层次化组织成为可能。

与任何 Merkle 树结构一样，它们使用加密哈希函数组合（哈希）每个节点中的数据，这确保了数据在未被检测的情况下无法被修改。此外，它们的层次结构允许有效且安全地验证这些数据的完整性。

在 Celestia 上的每条链（“rollup”）都有自己的命名空间，因此数据被 Merkle 化并排序。最终结果是一个短的 Merkle 根，每个 rollup 都有自己的子树（命名空间），可以从中提取和观察数据。这对于具有潜在更多区块空间的区块链特别相关（同时通过 DAS 使轻客户端成为第一公民），因为它允许你提取数据而不必提取整个区块。

因此，Celestia 上的 NMT 是一个按照命名空间 ID 排序的 Merkle 树，其哈希函数已修改，使得树中的每个节点包含所有子节点的命名空间范围。如果某个应用或 rollup 请求特定命名空间的数据，DA 层（Celestia）将根据其唯一的命名空间 ID 及树中提供的节点提供与该应用相关的特定数据集。这使我们能够检查所提供的数据是否已在 Celestia 块中提供，因此称之为数据可用性（DA）。

NMT 的另一个实现是 Sovereign Labs 使用的，它们是一种 ZK 主权 rollup，已经在 Rust 中实现了它们。

Merkle 树Ranges (MMR)

[Merkle 树Ranges (MMR)](https://docs.rs/merklemountainrange/latest/merklemountainrange/#:~:text=A%20Merkle%20mountain%20range(MMR,existence%20inside%20of%20the%20tree.) 是一种数据结构，用于维护一个一致的大型数据日志，该日志无需提供整个树即可轻松访问。它也是基于 Merkle 树概念的。在 MMR 中，每个叶节点表示一片数据，树中每一层的哈希是通过附加子节点的哈希并应用哈希函数来计算的。

MMR 结构允许特别有效地插入新数据，并能够证明树中某一独特数据片段的存在。"Mountain Range" 这个名字指的是树的特定构造；它以这样的方式构造，使其始终试图维护可能的最大一致单一二叉树（binary 意味着每个节点最多有两个子节点），这可能导致树结构具有多个“峰”（因此称为Ranges）或姐妹树。当需要 MMR 的根节点时，必须将各个树的峰汇集在一起，以计算整个 MMR 的根哈希（例如 Merkle 树的区块头，根（顶）节点）。这使 MMR 成为维护一致、长期安全和可验证数据记录的有用工具，其中某些部分可以根据需要进行更新和引用。

一小部分简单 MMR 的表示

现在想象一下更大规模的情形，你就得到了 MMR 的概念。

Merkle 树Ranges的艺术表现

能够有效证明 MMR 中特定数据片段的存在，使其与 Verkle 树一起用于非交互式状态证明，这一点非常有用。状态证明是一种的方法，用于验证系统的当前状态，而无需与该系统进行直接交互。在 MMR 和 Verkle 树的上下文中，状态证明可能用于验证树中数据的当前状态，而无需直接访问树本身。

这意味着你可以让证明者提供对 MMR 中某一特定数据片段包含性的紧凑证明。然后，验证者可以使用 MMR 的根哈希（在区块承诺中称为区块头）和树中适当层级的数据哈希（子节点）来验证该证明。通过使用这种方法，验证者可以在无需直接访问 MMR 中的数据的情况下确认证明的真实性。将元素附加到 MMR 的效率更高，因为你不需要遍历整个树来包含新的数据集。所有这些都可以在链上实现，从而确保完全透明。然而，MMR 的链上验证的 gas 成本远高于 Merkle 树证明（比较，请注意追加 gas 和验证 gas 具有不同的成本，虽然承诺到 MMR 更便宜）。在大多数使用案例中，MMR 将变得无限大且无法链上验证（由于 gas 消耗），因此在许多情况下通过开源“无信任”ZKP 设置进行链下验证。

Herodotus 是一个使用 MMR 进行非交互式状态证明的项目示例，其中需要的数据被计算为一个 ZKP，可以根据需要进行验证。这使他们能够保持可验证数据的一致状态，可以根据需要刷新和访问。

Jelly Merkle 树 (JMT) 和分层承诺树 (TCC)

最初由 Libra/Diem 团队为本应成为 Facebook/Meta 链的项目开发的 Jelly鱼 Merkle 树 (JMTs) 是 AR16MT 的一种改进版本。JMT 具有多个特性使其与其他 Merkle 树的实现相区别。具体而言，基于版本的节点密钥允许平均较小的密钥大小，减少了复杂性且节点类型更少，并且提供紧凑的证明格式——意味着占用的空间更少，计算速度更快。它们用于提供所谓的“包含/排除证明”。这条证据跟踪到目标节点的二进制路径。

Penumbra 是另一个利用 JMTs 的项目，尽管有一些变化。Penumbra 使用它们记录与链相关的所有值，例如 valset、提案、资产等。尽管该链提供了隐私，但显然仍然需要存储并供客户访问，以便他们能够验证信息确实是正确的。像 JMTs 这样的稀疏 Merkle 树非常适合这种目的。

在任何其他区块链上，完整节点处理所有交易并保留整个链状态的记录。客户可以使用 Merkle 树承诺来检查数据的准确性。然而，在 Penumbra 中，该链仅存储对用户私密数据的加密承诺，并让客户处理事务执行，同时提供 ZKP 以确保事务被正确计算。这意味着客户必须为完全节点创建 Merkle 证明，但随着链上用户数量的增加，客户处理每一笔交易的负担变得不可持续。为了解决此问题，他们使用 分层承诺树 (TCT)，这是一个轻量化的适合 SNARK 的 Merkle 树，具有子树，使客户能够忽略不影响他们的交易。

Penumbra 中使用的分层承诺树 (TCT) 表示

请注意，根指的是“顶”节点（即在 区块头 中提供的内容），而子节点也被称为叶子（leaf）——因此称为树。

Verkle 树集成

现在我们已经讨论了各种 Merkle 树的变体/修改，看看 Verkle 树 能实现的集成会很有趣。如前所述，Merkle 树能够改善节点的资源使用，这也是它们最初在比特币中被使用的原因。这个领域的一项重大努力是使用 Verkle 树实现所谓的“无状态性”。无状态性是允许节点忽略其不感兴趣的状态的概念（了解更多）。一个实际实例可以是，节点可以忽略一年内未更新的状态。然而，该状态在稍后可以通过多项承诺恢复。这将大大减少节点的资源需求。Verkle 树是这一过程的重要组成部分，因为它们使得较小的证明大小成为可能，这使得无状态性（无论是弱的还是完全的）变得可行。这些优势源于父节点是向量承诺的分支，而不是哈希函数。然而，正如我们在 上一篇文章 中提到的，这会导致计算效率下降。

有效的 Verkle 树 (VT) 构造，在正常的 VT 中，每条路径都有一个证明。

其他利用 Verkle 树降低节点资源消耗并使其对链的数据承诺更高效的项目包括 Polymer 和 Lagrange。Lagrange 将 Merkle 树编译成 Verkle 树以获得较小的承诺，从而使最终发布在其他链上的零知识证明 (ZKP) 远比最初要小和便宜。此外，基于向量承诺的证明（Verkle 树的类型）在用户的浏览器中比在 zkSNARKs 中的 Merkle 证明更容易聚合。正因如此，Polymer 最终希望迁移到 Verkle 树，如我们在 "Beyond IBC" 中所述。他们都使用 Plonky2 作为其链上验证的 ZKP 方案。

这只是你可以通过修改 Merkle 树实现的酷应用的一个示例。我们希望这要么激发了你对数据结构的兴趣，要么促使你研究区块链基础设施中你可能从未关注过的部分。如果你在这个领域有任何工作，欢迎与我们联系！

同时，非常感谢 Mathijs van Esch 对本文部分内容的帮助，以及促进相关讨论的贡献。

Maven11 Twitter

Writer Twitter

• 原文链接： maven11.substack.com/p/f...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～