Verkle 树

特别感谢 Dankrad Feist 和 Justin Drake 的反馈和审查。

Verkle 树正在成为以太坊即将到来的扩容升级的重要组成部分。它们的功能与 Merkle 树相同：你可以将大量数据放入 Verkle 树中，并制作任何单个数据或数据集的简短证明（“证人”），这些证明可以由只拥有树根的人进行验证。然而，Verkle 树提供的关键属性是它们的证明大小 更高效。如果一棵树包含十亿个数据，传统的二进制 Merkle 树生成的证明大约需要 1 千字节，但在 Verkle 树中，证明的大小 少于 150 字节 - 这种减少足以使 无状态客户端 在实践中最终变得可行。

Verkle 树仍然是一个新概念；它们最初由 John Kuszmaul 在 2018 年的这篇论文 中引入，目前还不是许多其他重要新加密构造中最广为人知的。这篇文章将解释 Verkle 树是什么以及其背后的加密魔法是如何工作的。它们短证明大小的代价是对更复杂的加密学的更高依赖性。但是，我认为，这种加密学仍然比 现代 ZK SNARK 方案 中所包含的高级加密学简单得多。在本文中，我将尽最大努力解释。

Merkle Patricia 与 Verkle 树节点结构

从树的 结构（树中节点的排列和内容）来看，Verkle 树与以太坊当前使用的 Merkle Patricia 树 非常相似。每个节点要么是 (i) 空的，要么是 (ii) 包含键和值的叶子节点，或 (iii) 一个具有固定数量子节点（树的“宽度”）的中间节点。中间节点的值是其子节点值的哈希值。

树中值的位置基于其键：在下面的图示中，要到达键 4cc 的节点，你需要从根节点开始，然后到达位置为 4 的子节点，然后再到达位置为 c 的子节点（记住：c 在十六进制中是 12），最后再到达位置为 c 的子节点。要到达键为 baaa 的节点，你首先要到达根节点的位 b 子节点，然后是该节点的位 a 子节点。路径 (b,a) 中的节点直接包含键为 baaa 的节点，因为树中没有其他以 ba 开头的键。

Verkle 树与 Merkle Patricia 树的真正区别在于 Verkle 树在实践中更宽。更宽。当 width = 2 时，Patricia 树是最有效的（因此以太坊的十六进制 Patricia 树实际上是相当不理想的）。另一方面，Verkle 树的证明随着宽度的增加变得越来越短；唯一的限制是，如果宽度变得 过于 高，生成证明会开始耗时过长。为以太坊提出的 Verkle 树 宽度为 256，有人甚至支持将其提高到 1024 (!!)。

托管与证明

在 Merkle 树（包括 Merkle Patricia 树）中，一个值的证明由整个 姐妹节点 集组成：证明必须包含所有与证明路径上任何节点共享父节点的节点。理解这一点可能有些复杂，因此下面是针对 4ce 位置上值的证明的图片。必须包含在证明中的姐妹节点以红色高亮显示。

那有很多节点！你需要在每一层提供姐妹节点，因为你需要节点的整个子节点集来计算该节点的值，并且你需要不断这样做，直到到达根节点。你可能会认为这不是太糟糕，因为大多数节点都是零，但这仅仅是因为这棵树的节点非常少。如果这棵树有 256 个随机分配的节点，顶部层几乎肯定会有所有 16 个节点都满，而第二层平均约为 63.3% 满。

另一方面，在 Verkle 树中，你不需要提供姐妹节点；相反，你只需提供路径，并附加一些额外的信息作为证明。 这就是 Verkle 树受益于更大宽度而 Merkle Patricia 树不受益的原因：宽度更大的树会导致在两种情况中都出现较短的路径，但在 Merkle Patricia 树中，这种效果被提供所有 width - 1 姐妹节点的高耗费所掩盖。在 Verkle 树中，该成本并不存在。

那么，我们作为证明需要的那一点额外信息是什么呢？要理解这一点，我们首先需要回到一个关键细节：用于从子节点计算一个内部节点的哈希函数并不是常规的哈希。相反，它是一个 向量承诺。

向量承诺方案是一种特殊类型的哈希函数，散列一个列表 h(z1,z2...zn)→C。向量承诺具有特殊的属性，对于一个承诺 C 和一个值 zi，可以制作一个简短的证明，证明 C 是某个列表的承诺，其中位置 i 的值为 zi。在 Verkle 证明中，这个简短的证明取代了 Merkle Patricia 证明中姐妹节点的作用，使验证者有信心一个子节点确实是其父节点的给定位置的子节点。

在实践中，我们使用一种比向量承诺更强大的原语，称为 多项式承诺。多项式承诺允许你散列一个多项式，并为在 任何 点上评估散列后的多项式创建证明。你可以将多项式承诺用作向量承诺：如果我们就一组标准化坐标 (c1,c2...cn) 达成一致，给定列表 (y1,y2...yn)，你可以承诺多项式 P，使得 P(ci)=yi 对于所有 i∈[1..n] （你可以通过 拉格朗日插值 找到这个多项式）。我在 ZK-SNARKs 的文章 中详细讲解了多项式承诺。最容易使用的两种多项式承诺方案是 KZG 承诺 和 bulletproof 风格的承诺（在这两种情况下，承诺是一个单独的 32-48 字节的椭圆曲线点）。多项式承诺为我们提供了更大的灵活性，使我们能够提高效率，而恰好可用的最简单和最有效的向量承诺 就是 多项式承诺。

这个方案本身已经非常强大：如果你使用 KZG 承诺和证明，证明大小为每个中间节点 96 字节，几乎是简单 Merkle 证明的 3 倍空间效率，如果我们将宽度设置为 256。 然而，事实证明，我们甚至可以进一步提高空间效率。

合并证明

不需要为路径上的每个承诺要求一个证明，通过利用多项式承诺的额外属性，我们可以制作一个固定大小的证明，证明路径上所有承诺之间的 所有 父子链路，适用于无限数量的键。我们采用一种 通过随机评估实现多重证明的方案。

但要使用这个方案，我们首先需要将问题转化为一个更结构化的形式。我们在 Verkle 树中有一个或多个值的证明。这个证明的主要部分由通往每个节点的路径上的中间节点组成。对于提供的每个节点，我们还需要证明它实际上是上方节点的子节点（以及在正确的位置）。在我们之前的单值证明示例中，我们需要证明：

• key: 4ce 节点确实是 prefix: 4c 中间节点的位 e 子节点。
• prefix: 4c 中间节点确实是 prefix: 4 中间节点的位 c 子节点。
• prefix: 4 中间节点确实是根节点的位 4 子节点。

如果我们有一个证明多个值（例如 4ce 和 420）的证明，我们将有更多的节点和更多的链接。但无论如何，我们证明的都是形如“节点 A 实际上是节点 B 的位 i 子节点”的一系列语句。如果我们使用多项式承诺，这就变成了方程：A(xi)=y，其中 y 是对 B 的承诺的哈希值。

这个证明的细节是技术性的， Dankrad Feist 比我更好地解释。证明生成中最繁琐和耗时的步骤涉及计算一个形如：

g(X)=r0A0(X)−y0X−x0+r1A1(X)−y1X−x1+...+rnAn(X)−ynX−xn

只有当那个表达式是多项式（而不是分数）时才可以计算每个项 riAi(X)−yiX−xi。而这需要 Ai(X) 在点 xi 的值等于 yi。

我们可以通过一个例子来看这一点。假设：

• Ai(X)=X2+X+3
• 我们正在证明 (xi=2,yi=9)。 Ai(2)确实等于9，因此这将有效。

Ai(X)−9=X2+X−6，且 X2+X−6X−2 给出一个干净的 X−3。但如果我们尝试适应 (xi=2,yi=10)，这将不起作用； X2+X−7 不能 干净地被 X−2 除，而没有一个分数余数。

证明的其余部分涉及提供 g(X) 的多项式承诺，然后证明该承诺实际上是正确的。一如既往，查看 Dankrad 更为技术性的描述 以获取证明的其余部分。

这就是最大效率的 Verkle 证明的样子。

使用此方案的证明大小的关键属性

• Dankrad 的多随机评估证明允许证明者 证明任意数量的评估 Ai(xi)=yi，给定对每个 Ai 的承诺和正在证明的值。 该证明是恒定大小（一个多项式承诺，一个数字和两个证明；根据使用的方案有所不同，为 128-1000 字节）。
• yi 值不需要显式提供，因为它们可以直接从 Verkle 证明中的其他值计算：每个 yi 本身是路径中下一个值的哈希（无论是承诺还是叶子）。
• xi 值也不需要显式提供，因为可以根据路径（因此也可以通过键和从路径派生的坐标计算 xi 值）。
• 因此，我们需要的只是要证明的叶子（键和值），以及每个叶子到根的路径上的承诺。
• 假设宽度为 256 的树，和 232 个节点，证明将要求被证明的键和值，以及（平均）每个值的三个承诺，沿着从该值到根的路径。
• 如果我们要证明多个值，还会有进一步的节省：不管你证明多少值，你不需要提供超过顶层的 256 值。

证明大小（字节）。行：树的大小，列：证明的键/值对

假设宽度为 256，和 48 字节的 KZG 承诺/证明。还要注意，这假定树是尽可能均匀的；对于一个现实的随机树，添加约 0.6 的深度（即每个元素 ~30 字节）。如果使用 bulletproof 风格的承诺而不是 KZG，则可以安全地减少到 32 字节，因此这些大小可以减少 1/3。

证明者和验证者计算负载

生成证明的 主要成本 是计算每个 riAi(X)−yiX−xi 表达式。这大约需要四个字段运算（即 256 位模算术操作）乘以树的宽度。这是限制 Verkle 树宽度的主要约束。幸运的是，四个字段运算是很小的成本：单个椭圆曲线乘法通常需要数百个字段运算。因此，Verkle 树的宽度可以相当高；宽度在 256 到 1024 之间似乎是最优范围。

为了 编辑 树，我们需要从叶子向上“走树”，在每一步上更改中间承诺以反映底层发生的变化。幸运的是，我们不需要从头重新计算每个承诺。相反，我们利用同态性质：给定多项式承诺 C=com(F)，我们可以通过取 C′=C+com(G) 来计算 C′=com(F+G)。在本例中，G=Li∗(vnew−vold)，其中 Li 是与我们试图更改的位置相等于 1 而在其他地方等于 0 的多项式的预计算承诺。

因此，单个编辑需要约四次椭圆曲线乘法（每次包含根节点，这次包括根节点的每个承诺），尽管这些可以通过预计算和存储每个 Li 的 多个倍数 而大大加速。

证明验证非常高效。对于 N 个值的证明，验证者需要执行以下步骤，所有这些步骤都可以在即使是成千上万的值中也能在一百毫秒内完成：

• 一个大小为 N 的 椭圆曲线快速线性组合
• 约 4N 次字段运算（即 256 位模算术运算）
• 一个小的与证明大小无关的常数工作量

还要注意，像 Merkle Patricia 证明一样，Verkle 证明给验证者提供了足够的信息来 修改 被证明的树中值并在应用更改后计算新的根哈希。这对验证区块中的状态更改是否被正确处理至关重要。

结论

Verkle 树是对 Merkle 证明的强大升级，允许证明大小大幅缩小。证明者只需提供一个证明，证明所有父子关系，而不是在每层提供所有“姐妹节点”，这使得证明大小比理想的 Merkle 树减少约 6-8 倍，而且比以太坊今天使用的十六进制 Patricia 树减少超过 20-30 倍 (!!)。

它们确实需要更复杂的加密实施，但它们也为可扩展性带来了巨大的提升机会。在中期，SNARKs 可以进一步改善：我们可以将已经有效的 Verkle 证明验证器 SNARK 化，以将证人大小减少到接近零，或者在 SNARKs 得到显著改进时恢复 SNARKed Merkle 证明（例如通过 GKR 或非常 SNARK 友好的哈希函数，或者ASIC）。进一步往后，量子计算的兴起将迫使使用基于哈希的 STARKed Merkle 证明进行更改，因为这使得 Verkle 树所依赖的线性同态不再安全。但就目前而言，它们为我们提供了与这些更高级技术所获得的同样的扩展收益，并且我们已经拥有实施它们所需的所有工具，并且能够高效使用。

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