为我们所有人解读 Verkle 树：第一部分

所以，你一定听过以太坊社区的人谈论“Verge”升级——这个升级在Vitalik的路线图中发生在The Merge和The Surge之后——你也知道它与一个叫“Verkle trees”的东西有关。但你仍然感到疑惑，并想要回答以下问题：

1. Verkle trees是什么？

2. 为什么以太坊需要Verkle trees？

3. 以太坊目前使用的是什么“树”类型，为什么需要切换？

4. 以太坊将如何过渡到使用Verkle trees？

5. 升级到Verkle trees对以太坊生态系统有什么影响？

好吧，你运气不错。在花了很多时间阅读Dankrad Feist/Vitalik Buterin关于Verkle trees的帖子，并观看Guillaume Ballet在这个主题上的演讲后（如果只为了那些memes和笑话，我强烈推荐观看），我可能知道一些关于Verkle trees的事情，足以为此写一系列文章。

请注意，我会在这篇文章和后续帖子中过于简化许多事情；我的目的是提供关于Verkle trees的速成课程，而不是讲座，因此你知道只是足够了解Verkle trees以及Verge如何融入以太坊的技术路线图。关于密码学的讨论数量相当庞大，但相信我，我不是密码学家，阅读这篇文章不需要计算机科学学位。

这也意味着：如果你是密码学家，在阅读时发现错误，请原谅我：

设置舞台：以太坊如何与“树”合作？

以太坊通常被描述为一个“状态机”（除了“世界计算机”、“全球结算层”或更为生动的称谓如“无限机器”）与比特币被描述为“分布式账本”的不同在于如何存储信息。尽管比特币只存储UTXOs（未花费的交易输出）——这些输出与用户控制的私钥相关联——以太坊则有“账户”的概念，并在键值存储中存储关于以太坊账户的特定信息：

• 合约账户（智能合约） : storageRoot, nonce, balance, 和 codeHash
• 外部拥有账户（EOAs） : Balance, nonce（在EOAs的情况下storageRoot和codeHash是空的）

这些数据共同构成以太坊的“状态”，当我们谈论状态时，通常指的是账户的余额（合同和EOAs）、合约代码、合约存储值等等。为了更详细地理解以太坊的这一方面，我鼓励阅读以太坊到底是如何运作的? 由Preethi Kasireddy撰写。

使以太坊成为“（基于交易的）状态机”的原因在于，当交易在以太坊虚拟机（EVM）中被处理时，区块链的状态会发生变化。EVM将与账户相关的信息存储在“树”中，以便有效检索数据（以及其他好处）。一个树是一种层次数据结构，由一组相互连接的节点组成；根据其在树中的位置，节点可以是“子”节点或“父”节点；父节点可以有多个子节点（根据树的类型），但每个子节点都有且仅有一个父节点。

一个“普通”的树数据结构。 (来源)

以太坊使用模块化架构存储状态数据，因此一棵树存储关于交易的信息（transaction trie）；另一棵树存储关于账户存储的信息（storage trie）；而第三棵树则存储关于交易收据的信息（receipt trie）。正如你可以预期的那样，将关于账户的信息存储在截然不同的地方会很笨拙——这就是为什么还有一棵状态树（state trie），用于保存所有与以太坊账户（EOAs和合约账户）相关的信息。

状态树为以太坊的全球状态提供了单一的真实性来源，并在每个区块更新时（与transaction trie和receipts trie一起）被更新：

(来源)

一次交易通常会导致对一棵或多棵树的修改——例如，将ETH存入Uniswap池需要在池合约的存储中创建一个新的插槽，并在存储树中插入一个新值（即与该用户相关的总存款）。这样将导致EVM更新与池合约账户相关联的存储根的值，从而进一步导致状态树的根值也发生变化。

上面提到的每棵“树”都是Modified Merkle Patricia Trie（MPT），这是Merkle树的变种（以1979年发明它的Ralph Merkle命名）。在接下来的部分，我们将深入了解Merkle树，并理解为什么在像以太坊这样的公有区块链上下文中它们是有用的。

什么是Merkle树？

Merkle树是一种具有某些属性的特定树结构，例如保证数据的不可变性和有效性。在基础层面上，Merkle树由叶节点（即俗称的leaves）组成，这些叶节点存储一块数据的加密哈希值，以及父节点（即俗称的branches），这些父节点存储叶节点的哈希。

为了构建Merkle树，需将一块数据进行哈希以形成叶节点，将两个（或更多）叶节点进行哈希以形成一个父节点，并继续这个过程，直到最终得到一个单一的父节点，没有剩余的叶（子）节点。最后的父节点称为树的根；你可以从下面的图片中看到最终的数据结构看起来像一个倒过来的树：

(来源)

那构建Merkle树的意义何在？首先，Merkle树通过存储对数据的加密承诺（使用抗碰撞哈希函数生成）来实现对数据结构内容的高效验证。这些对于一篇ELI5文章来说似乎是一堆行话，因此我将重要的术语分解如下：

1. 加密承诺 : 承诺方案允许一方（证明者）对特定消息m进行承诺，稍后向另一方（验证者）揭示m。加密承诺之所以称为如此是因为它们是绑定的——假设Alice生成对一条消息m的承诺C并发送给Bob；如果Alice随后揭示m，Bob应该有信心承诺C中承诺的消息m与Alice揭示的消息是相同的。

承诺方案也可能具有隐藏属性：如果Alice在承诺阶段发送C，则Bob不应该能够从C中提取出原始消息m。然而，承诺方案的隐藏属性不像绑定属性那样严格重要，除非在保留交换信息隐私至关重要的情况下。

1. 哈希函数 : 哈希函数是一种算法，它以任意大小的数据块作为输入，并将其映射到固定大小的字符串，输出字符串代表对原始数据的加密承诺（即h(x) → y）。哈希函数是单向的：你可以通过将数据通过哈希函数运行来找到数据块的哈希，但逆向提取原始数据则在计算上是不可行的。哈希函数也是抗碰撞的：对于不同的数据块生成相同哈希是计算上不可行的（即你不能找到两个输入a和b，它们生成相同的哈希值输出，其中a ≠ b）。

哈希函数的属性使其在创建Merkle树结构时非常有用；事实上，Merkle树也称为“哈希树”。使用哈希函数构建的Merkle树有许多应用，例如验证计算机之间传输的数据和验证从对等方接收的数据块，在分布式存储系统（如星际文件系统/IPFS）中有效。

Merkle树也作为加密累加器功能。简单而言，加密累加器允许你存储一组值，并稍后向另一方证明一个或多个值是最初存储在累加器中的数据的一部分。以太坊的状态树就是一个加密累加器的例子；任何人都可以通过向第三方验证者提供证据来证明其在该树中的特定数据的知识（例如，账户余额和存储值）。

在Merkle树的上下文中，“提供证据”的过程就等同于证明特定的叶节点是树的一部分——根被视为一个承诺，叶节点被揭示为原始承诺的一部分。我们会详细解释这个过程如何运作，但让我们先理解为什么这在第一时间内是可能的：

如前所述，Merkle树通过对数据块进行哈希以创建叶节点，通过对叶节点进行哈希以创建父节点，并通过对父节点进行哈希以创建一个更高一级的父节点——直到到达根节点。然而，与简单哈希函数仅将任意大小数据块映射到固定大小字符串（玩转哈希生成器示例，来查看这个概念如何工作）不同，用于构建树的哈希函数有一点不同，它作为一种向量承诺方案（尽管是一种弱的向量承诺；这个细节会在这篇文章中逐渐清晰）。

向量承诺方案允许你（以加密的方式）对一个向量或数值列表（x1、x2、x3、……xn）进行承诺，并通过在特定位置打开承诺C（x1、x2、x3、……xn）向另一方证明某个值x存在于向量中（也称为索引i）。在Merkle树中，这种向量承诺是通过哈希函数生成的，该函数输入一系列哈希列表h(x1、x2、x3、……xn)并输出C，这个哈希是输入数据的哈希。像其他承诺方案一样，向量承诺是绑定的（证明者不能在相同位置或索引上打开相同承诺两个不同值）且选择性地隐匿（验证者即使在证明者打开承诺以揭示某些值后也不应该学习到整个向量）。

证明xn是向量承诺C(x1、x2、x3、……xn)的一个成员的方法之一是向验证者发送原始长度的数据时承诺给C。然后，你可以在索引i的位置揭示x1，并让验证者比对你提供的xn值和在原始数据中与xn相关的值。

但是这并未解决使用加密承诺方案的初衷——我们这样做主要是为了让第三方能够验证单个数据的真实性，而无需发送所有数据（如果他们已经拥有数据，他们可以轻松验证你是否在说实话）。重要的是，在某些情况下，例如区块链网络中，我们希望减少同行之间共享的数据量，并保持带宽需求最低。

那么，我们该怎么办？

我们只发送验证者需要的最少量数据（称为证人），以检查“在向量x1、……xn中的索引i处，xn的值为真”。如果你将证人视为在法庭上站着并说“是的，我看到X先生在某个时刻做某事的人”，你就能捉住证人与向量承诺之间的联系；特别是，证人证明xn在向量中，并帮助验证证明者打开了一个有效值的向量承诺（其中“有效”意味着“是原始数据的一部分”）。

证人是如何创建的各不相同，但为了简单起见，我们将坚持最初的Merkle树示例。下面是一个二叉Merkle树（二叉意味着每个父节点最多可以有两个子节点），其中Alice想向Bob证明一个承诺为叶子x1的数据是树数据的一部分：

如果你回想一下对Merkle树的初步介绍，你会记得我说，树中的每一级父节点是通过将子节点一起哈希创建的，而树底部的子节点是通过哈希数据块创建的。这意味着整棵树在每一层都是通过哈希连接的，因此可以轻松检测两个树是否相同。你只需要比较两个树的根节点；如果根节点不同，这两棵树也会不同。

因此，若要检查Alice声称的叶子xn在树中具有特定值x，Bob只需以下数据（请注意，在此方案中，Bob不需存储Merkle树所表示的底层数据）：

• 当前Merkle树的根节点（它已经引用了Alice试图证明的数据，因之前描述的父子关系）
• 计算从叶xn到根节点路径上父节点所需的所有数据（包括叶节点xn自己的数据）

Bob需要的数据用于计算从叶xn到Merkle树根节点路径上父节点的，是属于叶子节点x1的兄弟（或“姐妹节点”）的哈希集合。以下是前一个例子的同一树——但现在我们高亮（红色）表明证明叶子x1包含在原始Merkle树中所需的节点：

你可能已经看到了这些关系；如果没有，这里有个大致的解释：

• Bob将叶子x1的数据进行哈希，并将叶子x1和叶子xn进行哈希以得到父节点y1的哈希
• 为了获得根节点y3的哈希，Bob需要将兄弟节点y1和y2组合在一起进行哈希
• Bob将新计算出的根节点y3的哈希与他手中现有的根节点哈希进行比较。

使用Alice提供的证人数据计算的根节点哈希与Bob手中根节点值（哈希）之间的值不同只能意味着一件事情：Alice试图证明的叶子数据不正确且缺失于原始（规范）Merkle树。此外，树中向上到根节点的每一层由哈希所表示的父子链接及加密承诺方案的确定性自然排除这种情况，即Alice拥有正确的叶数据，但以某种方式生成的证人未能说服Bob揭示的叶值（x1）是正确的。

Merkle树的问题：大的证人尺寸

现在我们已经看到了证人的工作原理，是时候理解Merkle树的一个关键问题：大的证人尺寸。证明某个特定值存在于树的一些叶子中需要提供所有兄弟节点的哈希；当树的深度（指的是从叶节点到根节点的层数）较小时，证人尺寸是可以管理的，正如在前面的例子中：

这是深度=2的二叉Merkle树；叶子x1的证人只需要两个兄弟哈希（叶节点x2和父节点y1的哈希）。

然而，当Merkle树的深度增加时，证人尺寸会显著增加。在下面深度=4的二叉Merkle树示例中，叶子x1的证人需要提供三个兄弟哈希（叶子x2和节点y2，y6的哈希）以及根哈希：

你可以看到这种趋势是如何展开的：随着更多的叶子（数据）添加到树中，我们需要更多数据来创建证明特定叶子是树的一部分的证人。如果你此刻觉得你是个超智者，此时你可能会问：“我们不能通过增加父节点的孩子数量来减少树的深度（高度）吗？”

由于证人尺寸似乎与树的高度k成比例增长，减少k理论上可以导致尺寸较小的证人——尤其是，如果它能减少我们需要提供证人的兄弟哈希数量。这种方法在理论上听起来不错，但在实践中并不是那么简单（在某些情况下，它确实有效，我们稍后将涉及）。

以下是一个_3_元二叉Merkle树的示例，每个父节点最多可以有三个子节点：

乍一看，我们已经成功解决了存储更多叶子而不增加树的高度（此树总共包含9个叶节点，深度=3，而前一个例子中的二叉树包含8个叶节点，深度为4）。但在新的树中，叶子（例如x1）的证人会有多大呢？_非常_大，如示意图所示（计算路径所需的哈希从x1到根节点y4显示为红色）：

我们现在需要为四个兄弟（叶节点x2、x3及内部节点y2、y3）提供哈希，以创建叶子x1在Merkle树中包含的证人。将分支因子（父节点在树中可以拥有的孩子数量的正式名称）增加到八——这将给我们一个_8_元（八叉）Merkle树——会使问题更糟：

我们进一步增加了树的大小，而没有增加高度，但证明针对x1的值现在需要总共九个哈希值（叶节点x2、x3、x4、x5、x6、x7、x8、x9的哈希和分支节点y2的哈希）。这个简短的“教程”展示了为什么Merkle树被认为是一种脆弱的向量承诺形式：证人的大小与数据结构（树）的大小（宽度和高度）成正比。但我们希望证人的大小在一定数量上保持不变，无论树的大小如何——而更有用的向量承诺方案将在很大程度上保证这一特性。

我们关注的向量承诺方案是成员资格证明对向量大小的独立性；在Merkle树中，这意味着一个叶子的证人不应等于树的大小。Dario Catalano和Dario Fiore在他们的论文向量承诺及其应用中提出的向量承诺方案满足这一要求，对创建“理想”的Merkle树（具有小型证人）很有用。

在基于这种类型向量承诺的Merkle树中：

• 每个分支（父）节点存储对一个向量（序列值）的承诺C，表示与其相关联的所有子节点。承诺C是使用加密协议生成的（重要的是），它不依赖于哈希函数来保证位置绑定（即，证明者P无法在相同位置打开相同的承诺给两个不同的值）。
• 每个叶节点（树的每一层）包括其在父节点所承诺向量中的成员资格证明π。该成员资格证明π是相对于承诺C生成的（向量）——允许证明者P向验证者V证明叶的值等于该特定位置的向量承诺C的开口。

我们关注于上述的向量承诺方案，因为它可以在不提供兄弟节点数据的情况下证明叶子在Merkle树类似结构中的包含。 在原始Merkle树示例中，父节点通过将子节点一起哈希的形式存储对孩子的承诺；证明特定子节点被包含在父节点存储的承诺中，需要提供所有其他相关子节点的哈希。

然而，在这种情况下，父节点存储了一个固定大小的孩子节点承诺字符串——且证明儿童节点与父节点之间的连接只需验证同伴性证明π的有效衍生自承诺C。因为C是在与父节点连接的节点集上生成的，一个有效的证人证明子节点的值确实代表该特定位置的承诺的开口。

由于每个叶节点存储一份成员资格证明，验证者只需在树的路径上沿途检查每个中间级别的证明，以求顺利从叶子升至根——而不是在向上移动树时通过将子节点一起哈希来重建根。这在我们的情况下非常有用，因为这改变了证明者和验证者之间的相互作用：为已提交父节点的值创建承诺C(x1,…x1)，推导一个叶的重要性证明π（称为x1），并将这组数据作为对叶x1包含的证人的证据。

以下是使用向量承诺的新（二叉）Merkle树的样子：

如你所见，每个叶子存储一个成员资格证明π，每个父（分支）节点存储对其子项的承诺C。现在，如果Alice需要向Bob验证特定值存在于Merkle树的叶子x1中，她只需作为见证向Bob提供以下数据：

• x1的值（这是存储在叶子中的数据的常规哈希）
• 证明x1在其父节点承诺的向量（x1、x2）中的成员资格证明π1
• 引用与分支节点y1连接的所有子节点的成员资格证明C1
• 证明y1在根节点y3存储的向量承诺C3中的成员资格证明π5（注意：我们假设Bob已经拥有C3）

在以前的示例中，Bob需要通过访问中间哈希来重建根节点，然后再验证Alice是否正确开启承诺。然而，使用VC时，Bob不需要显式了解从叶到根的路径上除了内部（分支）节点之外的其他节点，因为成员资格证明提供了足够的信息来验证中间级别树上的父子关系。 （根承诺C3承诺一个包括y1和y2的向量，并且分支节点y1和y2的成员资格证明（π5和π6）是从C3推导出来的）。

引入Verkle树：具有小型见证的Ver(y短Mer)kle树

上述描述的向量承诺——尽管甚至那可以改进——赋予我们在Merkle树结构中所需的属性：小型证人。基于向量承诺的树结构被正式称为Verkle树（“Verkle”是Vector承诺和Merkle树的混合词），是由John Kuszmaul发明的。

Verkle树中叶子的证人通常具有以下（理想）特性：

1. 简明性 : 叶子的证人（即向量值）应当写的容易且比完全验证整个向量更快。简明性也确保证人尺寸只随基础数据的亚线性增长，尽管原始数据指数增长。我们可以通过将前面示例的标准八元Merkle树——能有多少个子节点——与Verkle树对比来说明这一特性：

原始八元Merkle树（使用哈希）

八元Verkle树（使用向量承诺）

之前，Alice需要提供确切的d-1个哈希（其中d是树的宽度和每个分支的叶子数量）和路径到根的其他中间兄弟哈希——总加起来在八元Merkle树示例中需提供共八个哈希——相反，在Verkle树中，x1的证人只需三个承诺：向量承诺C1，成员证明π1（用于验证x1和y1之间的关系）和成员证明π17（用于验证y1和根之间的关系）。

Alice的确不需提供路径从根节点y3到叶子x1的未访问兄弟节点的信息——Bob需要的证据来验证Alice正确开启根承诺C3是每一层树只需准确的一个证明（以及作为额外数据的向量承诺C1）。与之前的例子一样，我们假设验证者（Bob）已经拥有根节点的承诺。

请不要在家说“谁需要兄弟姐妹”。

这一特性的一个影响是增加每个分支（父节点）的孩子数量对整体证人大小的影响微乎其微。如果我们想存储更多数据（即在树中添加更多节点），同时保持证人大小小型，我们可以增加宽度使树变得更短并减少叶土与根之间的级别。以下是一个六叉的Verkle树（宽度=16）示例，其中每个分支父节点最多可以有16个子节点：

具有每个父节点16个子节点的Verkle树

新的Verkle树共有38个节点，相较于前面的例子有18个节点——但对于叶子x1的证人仍然相同，仅需提供三个承诺（π1、π33和C3）。虽然这个示例是为显现使用向量承诺的效率提升而进行的强行示例，它暗示了向量承诺在Ethereum这样的生产网络中的重要性，后者（目前）使用一个六叉Merkle树来存储状态，见下图：

(来源)

2. 常量大小 : 叶子的证人大小不应与向量长度（即我们承诺的数据大小）相关。Verkle树满足这一要求，因为相对于一个向量承诺C（x1、x2、……xn）相关会员资格证明π总是使用相同数量的组构件，原因在于向量承诺方案的性质。这与传统Merkle树中使用的向量承诺形成较大对比：证明资格的证明永远是d-1该叶子直接的兄弟节点的哈希以及树中其他中间节点的兄弟节点。

注意：说“加密机制”可能听起来模糊，但对不懂数学的人来说，这是解释其最好的方法。如果你勇敢的话，可以阅读关于椭圆曲线配对（我们“加密机制”的正式名称）获取更多底层细节。

但这还不是全部：向量承诺还确保树的宽度增加——从最低叶子到Merkle树根的层数——对证人大小的影响微乎其微。让我们将其背景化：

在之前的示例八元Merkle树中，Alice需要在朝着根节点途中为证人逐渐减少地提供哈希——Alice在Merkle树的第一级提供给Bob七个哈希，而在第二级只提供一个哈希。与八元Verkle树的例子形成鲜明对比，Alice在朝向要证明值的叶子路径每一层都只需提供一个证明（以及承诺字符串作为附加数据）：

创建有效证人的叶子x1所需的承诺（哈希）以红色圈住。

创建有效证人的叶子x1所需的向量承诺和成员资格证明以红色圈住。

到目前为止，我们已经确定与Merkle树中的加密哈希相比，向量承诺具有一些优良特性——例如，你无须无访问状态下的兄弟节点作为叶子的证人——但这在实际中有什么帮助？ 你会记得我早前提到想要相较于Merkle树中使用的哈希的更好向量承诺方案这是出于什么原因：

“这个简短的教程展示了为什么Merkle树被认为是一种脆弱的向量承诺形式：证人的大小与数据结构（树）的大小（宽度和深度）成正比。但我们希望证人（成员资格证明）的大小与树的大小保持不变——更好用的向量承诺方案几乎总会保证这一点。”

在本系列关于Verkle树的下一篇文章中，我将（正式）阐明希望使用产生小型证人的Merkle树，以存储以太坊状态的原因。由于减少证人尺寸是转向Verkle树的主要理由之一——也是Verge的关键原因之一——下一篇文章将会侧重于基于本文讨论的不同概念（向量承诺、证人等）进行更为实用的应用。

目前你可以尝试通过观看Vitalik的路线图信息图中The Verge的一些目标来猜测Verkle树对以太坊路线图的重要性：

如果你觉得这篇文章对你有价值，可以考虑与其它希望了解以太坊（雄心勃勃）路线图下一阶段的人分享。你可以通过Twitter/X 和 LinkedIn与我联系——就像说“为了内容而来，留驻于memes”。哦，别忘了订阅Ethereum 2077，获取更多与以太坊研发相关的深度分析。

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