本文由尘埃科技整理编辑发布，请拖动至文章底部查看更多精彩内容
编辑｜RR
FTX倒闭后，交易所纷纷自证清白，想要留住用户的心，在重构之前的文章中，我们介绍过很多交易所都选择了用默克尔树的方法（交易所如何自证清白，CZ和孙割都在用默克尔树储备证明是什么？）。
其实在谈论区块链行业中许多基础设施项目的内部运作时，默克尔树是最常提到的数据结构。它们以拉尔夫·默克尔的名字命名。拉尔夫·默克尔在他的论文《A Certified Digital Signature》中介绍了这一概念，并在1979年为其申请了专利。
事实上，它们在加密行业受到如此多的关注并不奇怪，因为它们一直是区块链全球状态和交易根源承诺中的关键数据结构。这方面最明确的例子是默克尔树在最初的比特币白皮书的第4页首次被提及。在区块头中使用·默克尔树的主要优点是允许节点丢弃已消费的的交易，从而节省磁盘空间。
▵ 比特币白皮书中首次提到默克尔树
作为可扩展性研究的一部分(包括无状态研究)，大量的资源被投入到改变默克尔树上。这是因为当我们试图以一种允许人们继续运行节点的方式扩展区块链时，必须尽量减少资源的使用。从这个角度来看，默克尔树的各种风格都是区块链和基础设施项目中用于扩展和安全性的迷人创新。
在我们深入探讨我们要展示的各种数据结构之前，有一件事需要说明，那就是其中一些数据结构有不同的用途。例如，JMT、Patricia(在ETH中)和Verkle树被用于提交到全局状态根，而NMT和MMR则用于交易默克尔根。然而，这两者的根(顶部节点)通常会在区块头中提供。在以太坊的情况下，标准的默克尔树被用于交易数据，而Patricia树则被用于全局状态树。
命名空间默克尔树
命名空间默克尔树也被称为NMT，是一种用于组织和验证区块链上的大型数据集合的数据结构。作为前面提到的更著名的默克尔树数据结构的变体，当涉及到请求特定数据的应用程序和rollup时，它们在效率和可扩展性方面提供了许多优势。它们最初是由Celestia的Mustafa Al-Bassam在2019年作为他博士论文的一部分发表在了LazyLedger论文中的。
NMT的主要优点之一是它们能够将数据组织成层次结构，在这种结构中，你可以有效地验证应用程序请求的单个或单独的数据片段。作为用户，你只需要检索相应的叶节点及其父节点，而不需要检索整个数据集。
另一个优势是它能够扩展到非常大的数据集合。这是通过使用允许分层组织的多级“名称空间”节点实现的。
与任何默克尔树结构一样，它们使用加密的哈希函数来组合每个节点中的数据，这确保了在没有被发现的情况下不能修改数据。此外，它们的层次结构允许对所述数据的完整性进行有效和安全的验证。
在Celestia之上的每条链("rollup”)都有自己的命名空间，其中的数据被默克尔化和排序。最终结果是一个短的默克尔根，其中每个rollup都有自己可以从中提取和观察数据的子树(命名空间)。这对于每个区块可能有更多区块空间的区块链来说尤其重要，因为它允许你在无需拉取整个区块的情况下拉取数据。
因此，Celestia上的NMT是一个默克尔树，其中的节点按命名空间ID排序，哈希函数经过修改，以便树上的每个节点都包括其所有子节点的命名空间范围。如果应用程序或rollup请求特定命名空间的数据，DA层(Celestia)将根据其独特的命名空间ID和树中提供的节点，提供与该应用程序相关的特定数据集。这使得我们可以检查所提供的数据在Celestia区块中是否可用，因此称为数据可用性(DA)。
NMT的另一种实现是一个由Sovereign Labs使用的ZK主权rollup。
默克尔树山脉(MMR)
默克尔树山脉(MMR)是一种用于维护无需提供整个树即可轻松访问的一致大型数据日志的数据结构。它同样基于默克尔树的概念。在MMR中，每个叶节点代表一段数据，树的每一层的哈希值都是通过附加子节点的哈希值并应用哈希函数来计算的。
MMR结构允许有效地插入新数据，并能够证明树中现有的不同数据片段的存在。“山脉”是指树的具体构造;其构造方式总是试图保持最大可能的一致性单一二进制树(意味着每个节点最多有两个子节点)，这可能导致树结构具有多个“山峰”(因此称为山)或姐妹树。当需要MMR的根节点时，必须将各个树的山峰处理在一起，以计算整个MMR的根哈希值。这使得MMR成为维护一致、长期安全和可验证的数据记录的有用工具，其中某些部分可以根据需要更新和引用。
▵ 默克尔树山脉的艺术性表现
有效地证明MMR中特定数据存在的能力使它可以与Verkle树一起用于非交互式状态证明，状态证明是一种不需要与系统直接交互就能验证系统当前状态的方法。在MMR和Verkle树的背景下，可以使用状态证明来验证树中数据的当前状态，而不必直接访问树本身。
这意味着你可以允许验证者提供证明MMR中包含了特定数据片段的紧凑证明。然后，验证者可以使用MMR的根哈希和所需数据树的适当级别的哈希(子节点)对该证明进行验证。通过使用这种方法，它允许验证者在不必直接访问MMR中数据的情况下确认证明的真实性。将一个元素添加到MMR中的效率要高得多，因为你不需要浏览整个树来纳入一个新的数据集。所有这些都可以在链上实现，从而实现完全透明。然而，MMR在gas方面比默克尔树证明要昂贵得多。在大多数用例中，MMR会变得无限大，并且无法在链上验证，因此在许多情况下会通过开源的“无信任”ZKP设置进行链下验证。
Herodotus是一个利用MMR进行非交互式状态证明的项目的例子，其中所需的数据被计算到ZKP中，然后可以根据需要对其进行验证。这使他们能够保持根据需要进行刷新和访问的一致的可验证数据状态。
Jelly Merkle Tree(JMT)
和Tiered Commitment Tree(TCT)
最初由Libra/Diem团队为Facebook/Meta链开发的Jellyfish Merkle Trees(JMT)是AR16MT的修改版本。JMT有几个特点，这些特点将它们与默克尔树的其他实现区别了开来。即平均允许较小密钥大小的基于版本的节点密钥、通过更少的节点类型降低复杂性，以及简洁的证明格式。它们的作用是提供所谓的“包含/排除证明”，跟踪指向目标节点的二进制路径。
Penumbra是另一个正在利用JMT的项目。Penumbra使用它们来记录valset、提案、资产等与链相关的的所有值。尽管链提供了隐私，但显然仍然需要将其存储并提供给客户端，以便他们可以验证信息是否确实正确。稀疏的默克尔树(如JMT)是实现这种目的的理想选择。
全节点在任何其他区块链上处理所有的交易，并保存整个链的状态记录。客户端可以通过默克尔树承诺来检查数据的准确性。然而，在Penumbra上，链只存储对私人用户数据的加密承诺，并让客户端处理交易执行，而不是提供ZKP以确保交易被正确计算。这意味着客户端必须创建默克尔证明以供全节点验证，但随着链上用户数量的增长，客户端处理每笔交易的负担将变得不可持续。为了解决这个问题，他们使用了Tiered Commitment Tree(TCT)，一种轻量级的SNARK友好型默克尔树，它的子树可以使客户端能够忽略对他们没有影响的交易。
请注意，根指的是“顶部”节点(这是在块头中提供的)，而子节点也称为叶(leaf)——因此是树。
Verkle Tree集成
现在我们已经讨论了默克尔树的各种风格/变化，可以再看看Verkle树可以实现的集成。如前所述，默克尔树可以改善节点的资源使用，这就是为什么它们首先被用于比特币。这一领域的一大进步是使用Verkle Trees实现所谓的“无状态”。无状态是指允许节点忽略它们不感兴趣的状态。然而，这种状态将在以后的时间里通过多项式承诺保持可恢复性。这将极大地降低节点的资源需求。Verkle树是其中的一个关键组成部分，因为它能够支持更小的证明规模，从而使得无状态可行。这些优势是由于父节点是向量承诺的一个分支，而不是哈希函数的结果。然而，正如我们之前的文章中提到的，这是以计算效率为代价的。
其他利用Verkle树来降低节点资源使用并提高其对链的数据承诺的项目包括Polymer和Lagrange。Lagrange正在将默克尔树编译为Verkle树，以实现更小的承诺，这样，最终在另一个链上发布的零知识证明ZKP)就会比最初小得多，成本也更低。此外，比起在zkSNARK中的默克尔证明，基于向量承诺的证明可以在用户的浏览器中更容易地聚合。出于同样的原因，Polymer最终希望转移到Verkle树。他们都在使用Plonky2作为ZKP方案进行链上验证。
这只是说明你可以用Merkle树的改动做一些很酷事情的例子。我们希望它能激起你对数据结构的兴趣，或者促使你研究区块链基础结构中你可能以前没有研究过的部分。
信息来源自substack，略有修改，作者foobar
尘埃科技
看墙外更多信息，推特账号指路「Allrecode」
为Web3从业者建立内部链接，了解「重构研究院」
“商务合作”、“内容转载”请直接在后台回复关键字
更多DAO、Web3、NFT、Metaverse
专业研究请关注尘埃科技旗下「老雅痞」
Web3知识点、干货类内容
请关注尘埃科技旗下「Allrecode重构」