DeFi之道丨V神发文详述Verkle树结构，比以太坊现使用的Patricia树的证明大小降低30倍

原文作者：以太坊创始人Vitalik Buterin。

V神认为Verkle 树正在成为以太坊即将进行的扩展升级的重要组成部分。Verkle 树是 Merkle 证明的强大升级，允许更小的证明尺寸。不需要在每个层级提供所有“姐妹节点”，证明者只需要提供一个证明来证明沿着从每个叶节点到根的路径的所有承诺之间的所有父子关系。这使得证明大小与理想的 Merkle 树相比减少了约 6-8 倍，与以太坊今天使用的十六进制 Patricia 树相比减少了 20-30 倍以上（！！）。

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

Verkle 树正在成为以太坊即将进行的扩展升级的重要组成部分。它们具有与默克尔（Merkle） 树相同的功能：您可以将大量数据放入 Verkle 树中，并对可以通过以下方式验证的任何单个或一组数据进行简短证明（“见证witness”），并且仅拥有树根的人都可以对此进行验证。然而，Verkle 树提供的关键特性是它们在证明大小方面效率更高。如果一个树包含 10 亿条数据，在传统的二叉 Merkle 树中进行证明将需要大约 1 KB，但在 Verkle 树中，此证明将少于 150B——这一减少足以使无状态客户端最终在实践中可行。

Verkle 树仍然是一个新想法；它们由 John Kuszmaul 在 2018 年发表的 论文 中首次提出，但它们至今仍然不如许多其他重要的新密码结构那样为人所知。这篇文章将解释什么是 Verkle 树以及它们背后的密码学魔法是如何工作的。其短证明大小的代价是对更复杂的密码学的依赖程度更高。也就是说，在我看来，密码学仍然比现代 ZK SNARK 方案中的高级密码学简单得多。在这篇文章中，我将尽我所能来解释它。

Merkle Patricia树 vs. Verkle树节点结构

就树的结构（树中节点的排列方式以及它们包含的内容）而言，Verkle 树与目前以太坊中使用的 Merkle Patricia 树非常相似。每个节点要么是 (i) 空的，要么是包含一个密钥（key）和值的叶节点，要么是 (iii) 具有固定数量子节点（树的“宽度”）的中间节点。中间节点的值计算为其子节点值的哈希。

值在树中的位置基于其key：在下图中，要到达key为 4cc 的节点，从根开始，然后向下到达位置 4 处的子节点，然后向下到达子节点在位置 c（记住：十六进制中的 c = 12），然后再次下降到位置 c 的子位置。要到达带有key baaa 的节点，请转到根节点的位置 b 子节点，然后是该节点的位置 a 子节点。路径 (b,a) 处的节点直接包含key为 baaa 的节点，因为树中没有其他以 ba 开头的key。

Verkle 树和 Merkle Patricia 树结构的唯一真正区别在于 Verkle 树在实践中更广泛。 当宽度（width） = 2 时，Patricia 树的效率最高（因此以太坊的十六进制Patricia 树实际上是次优的）。 另一方面，Verkle 树的宽度越高，证明越短； 唯一的限制是，如果宽度变得太高，则证明的创建时间会过长。 为以太坊提议的 Verkle 树的宽度为 256，有些人甚至赞成将其提高到 1024 (!!)。

承诺(Commitments)和证明

在 Merkle 树（包括 Merkle Patricia 树）中，值的证明由整个姐妹节点集组成：证明必须包含树中的所有节点，这些节点与路径中的任何节点共享一个父节点 您要证明的节点。 理解起来可能有点复杂，所以这里有一张证明 4ce 位置值的图片。 必须包含在证明中的姐妹节点以红色突出显示。

这是很多节点！您需要在每个级别提供姐妹节点，因为您需要一个节点的整个子节点集来计算该节点的值，并且您需要继续这样做直到到达根节点。您可能认为这并没有那么糟糕，因为大多数节点都是零，但这只是因为这棵树的节点很少。如果这棵树有 256 个随机分配的节点，则顶层几乎可以肯定所有 16 个节点都已满，而第二层将平均满 63.3%。

另一方面，在 Verkle 树中，您不需要提供姐妹节点；相反，您只需提供路径，并提供一点额外的证明。 这就是为什么 Verkle 树受益于更大的宽度而 Merkle Patricia 树则没有：在这两种情况下，更大宽度的树会导致更短的路径，但在 Merkle Patricia 树中，这种效果被需要提供所有宽度的更高成本所淹没，因为需要提供一个证明中每级中所有width-1的姐妹节点。在 Verkle 树中，该成本不存在。

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

向量承诺方案是一种特殊类型的哈希函数，对一个列表进行哈希化。 但是向量承诺具有特殊属性，即对于一个承诺和一个值 ，可以做一个简短的证明，即对某个列表的承诺，也就是第 i 个位置的值的位置 。 在 Verkle 证明中，这个简短的证明取代了 Merkle Patricia 证明中姐妹节点的功能，让验证者相信子节点确实是其父节点给定位置上的子节点。

在实践中，我们使用比向量承诺更强大的原语，称为多项式承诺。多项式承诺让您可以对多项式进行哈希，并在任何时候为哈希多项式的评估提供证明。您可以使用多项式承诺作为向量承诺：如果我们就一组标准化坐标（c1,c2,......cn）达成一致，则给定一个列表（y1,y2,...yn），您可以承诺多项式P，其中P（ci）=Yi，i属于[1...n]（您可以通过拉格朗日插值找到这个多项式）。我在关于 ZK-SNARKs 的文章中详细讨论了多项式承诺。最容易使用的两种多项式承诺方案是 KZG 承诺和防弹式（bulletproof）承诺（在这两种情况下，一个承诺都是一个 32-48 字节的椭圆曲线点）。多项式承诺为我们提供了更大的灵活性，让我们能够提高效率，而且恰好可用的最简单和最有效的向量承诺是多项式承诺。

该方案已经非常强大：如果您使用 KZG 承诺和证明，则证明大小为每个中间节点 96 字节，如果我们设置宽度 = 256，则空间效率比简单的 Merkle 证明高近 3 倍。然而，它事实证明，我们可以进一步提高空间效率。

合并证明

通过使用多项式承诺的额外属性，我们不需要为路径上的每个承诺提供一个证明，而是可以制作一个固定大小的证明，以为无限数量的密钥证明路径上承诺之间的所有父子链接。我们使用通过随机评估实现多重证明的方案来做到这一点。

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

• key: 4ce 节点实际上是前缀: 4c 中间节点的位置e 子节点。
• 前缀（prefix）：4c中间节点实际上是前缀：4中间节点的位置c子节点。
• 前缀(prefiex)：4中间节点实际上是根的位置4子节点

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

这个证明的细节是技术性的，Dankrad Feist比我自己解释得更好。到目前为止，证明生成中最笨重和耗时的步骤涉及计算以下形式的多项式：

如果该表达式是多项式（而不是分数），则只能计算每个项

。 这需要Ai（X）在位置xi上等于yi。

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

Ai（X）=X²+X+3

我们正在证明（xi=2;y2=9） . 如果Ai（2）=9，则这会起作用。

Ai（X）-9=X²+X+6，且（X²+X-6）/（X-2）能被X-3整除。如果我们用（xi=2,yi=10），公式不成立。(X²+X-7)并不能被X-2整除且没有小数余数。

证明的其余部分涉及提供一个多项式承诺g(X)，然后证明承诺实际上是正确的。 再一次，请参阅 Dankrad 的更多技术说明以了解证明的其余部分。

一个证明可以证明无限数量的父子关系。

我们有了它，这就是最大效率的 Verkle 证明的样子。

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

• Dankrad 的多随机评估证明允许证明者证明任意数量的定值Ai（xi）=yi，给定对每个Ai承诺以及正在证明的值。此证明大小恒定（一个多项式承诺、一个数字和两个证明；128-1000 字节取决于所使用的方案）。
• 不需要明确提供yi值，因为它们可以直接从 Verkle 证明中的其他值计算出来：每个yi值本身就是路径中下一个值的哈希值（一个承诺或一个叶（leaf））。
• 也不需要明确提供xi值，因为可以从key和从路径导出的坐标计算路径（以及xi值）。
• 因此，我们所需要的只是我们正在证明的叶（key和值），以及从每个叶到根的路径上的承诺。
• 假设一个宽度为 256 的树和2的32次方个节点，证明将需要被证明的key和值，加上（平均）从该值到根的路径上的每个值的三个承诺。
• 如果我们要证明许多值，则可以进一步节省：无论您要证明多少个值，您都不需要提供超过 256 个顶层值。

证明大小（字节）。行：树大小；列：已证明的key/值对

假设宽度为 256 和 48 字节的 KZG 承诺/证明。 另请注意，这假设树最大为偶数； 对于现实的随机树，添加 ~0.6 的深度（因此每个元素 ~30 字节）。 如果使用防弹风格的承诺而不是 KZG，那么减少到 32 字节是安全的，因此这些大小可以减少 1/3。

证明者和验证者计算负载

生成证明的大部分成本是计算每个

表达式。 这需要大约四次字段运算（即 256 位模算术运算）乘以树的宽度。 这是限制 Verkle 树宽度的主要约束。 幸运的是，四个字段操作的成本很小：单个椭圆曲线乘法通常需要数百个字段操作。 因此，Verkle 树的宽度可以非常高； 宽度 256-1024 似乎是最佳范围。

要编辑树，我们需要从叶子到根“沿着树向上走”，在每一步更改中间承诺以反映发生在较低位置的更改。 幸运的是，我们不必从头开始重新计算每个承诺。 相反，我们利用同态性质：给定一个多项式承诺 C=com（F） ，我们可以通过取C‘=C+com（F）来计算C’=com（F+G）。 在我们的例子中，G=Li *（Vnew-Vold），其中Li是多项式的预先计算的承诺，在我们试图改变的位置等于 1，在其他地方等于 0。

因此，单次编辑需要约 4 次椭圆曲线乘法（叶和根之间的每个承诺一个，这次包括根），尽管可以通过预先计算和存储每个Li 的许多倍数来大大加快速度。

证明验证非常有效。 对于 N 个值的证明，验证者需要执行以下步骤，对于甚至数千个值，所有这些步骤都可以在一百毫秒内完成：

• 一种大小为N的椭圆曲线快速线性组合
• 大约 4N 个字段操作（即 256 位模算术运算）
• 不依赖于证明大小的少量恒定工作量

另请注意，与 Merkle Patricia 证明一样，Verkle 证明为验证者提供了足够的信息来修改被证明的树中的值，并在应用更改后计算新的根哈希。 这对于验证例如。 区块中的状态更改已正确处理。

结论

Verkle 树是 Merkle 证明的强大升级，允许更小的证明尺寸。不需要在每个层级提供所有“姐妹节点”，证明者只需要提供一个证明来证明沿着从每个叶节点到根的路径的所有承诺之间的所有父子关系。这使得证明大小与理想的 Merkle 树相比减少了约 6-8 倍，与以太坊今天使用的十六进制 Patricia 树相比减少了 20-30 倍以上（！！）。

Verkle树确实需要更复杂的密码学来实现，但它们提供了获得可扩展性巨大收益的机会。从中期来看，SNARK 可以进一步改进：我们可以对已经高效的 Verkle 证明验证器进行 SNARK 以将见证大小减少到接近于零，或者如果/当 SNARK 变得更好时（例如通过 GKR）切换回 SNARKed Merkle 证明，或非常 SNARK 友好的哈希函数，或 ASIC）。更进一步，量子计算的兴起将迫使使用哈希的 STARKed Merkle 证明进行更改，因为它使 Verkle 树所依赖的线性同态变得不安全。但就目前而言，它们为我们提供了与使用这些更先进的技术相同的扩展好处，而且我们已经拥有有效实施它们所需的所有工具。