verkle树结构比目前以太坊的验证尺寸小30倍

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

特别感谢dankrad Feist和Justin Drake的反馈和评论。

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

Verkle树仍然是一个新概念；它们最早是由John kuszmaul在2018年发表的一篇论文中提出的，但它们仍然不如其他许多重要的新密码结构那样广为人知。本文将解释什么是verkle树以及它们背后的密码魔法是如何工作的。它的证明长度短的代价是它更依赖于更复杂的密码学。换句话说，在我看来，密码学仍然比现代ZK-snark方案中的高级密码学简单得多。在这篇文章中，我将尽我所能来解释它。

Merkle-Patricia树与verkle树节点结构

就树的结构（树中节点的排列及其包含的内容）而言，verkle树与目前在以太坊中使用的Merkle Patricia树非常相似。每个节点要么是（I）空的，要么是包含键和值的叶节点，或者（III）具有固定数量量子节点（树的“宽度”）的中间节点。中间节点的值计算为其子节点值的哈希。

该值在树中的位置基于其键：在下图中，要到达键为4cc的节点，请从根开始，然后向下到位置4处的子节点，然后向下到位置C处的子节点（请记住：十六进制中的C=12），然后再次向下到位置C处的子节点。要使用baaa键访问节点，请转到根节点的位置B子节点，然后转到节点的位置a子节点。路径（B，a）处的节点直接包含密钥为baaa的节点，因为树中没有其他以BA开头的密钥。

十六进制（每个父节点有16个子节点）verkle树中的节点结构，其中填充了6个（键、值）对。

verkle树与Merkle-Patricia树结构的唯一区别在于verkle树在实际应用中更为广泛。当width=2时，Patricia树的效率最高（因此以太坊的十六进制Patricia树实际上是次优的）。另一方面，verkle树的宽度越大，证明越短；唯一的限制是，如果宽度变得太高，证明的创建时间将太长。为以太坊提议的verkle树的宽度是256，有些人甚至赞成将其增加到1024（！）。

承诺和认证

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

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

另一方面，在verkle树中，不需要提供姐妹节点；相反，您只需提供路径和一些额外的证据。这就是为什么verkle树受益于更大的宽度，而Merkle Patricia树却没有：在这两种情况下，更大的树会导致更短的路径，但在Merkle Patricia树中，提供所有宽度的成本更高，这一效果不堪重负，因为必须在每个证明级别中提供一个所有宽度为1的姊妹节点。在verkle树中，成本不存在。

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

向量承诺方案是一种特殊的哈希函数，它对一个列表进行哈希运算。但向量承诺有其特殊的性质，即对于一个承诺和一个值，我们可以做一个简短的证明，即承诺到一个列表，即该值的第i位的位置。在verkle证明中，这个简短的证明取代了Merkle-Patricia证明中姐妹节点的作用，使得验证者相信子节点确实是父节点给定位置上的子节点。

树中值的证明不需要姐妹节点；它只是路径本身，用一些简短的证明将路径中的每个承诺连接到下一个承诺。

在实践中，我们使用了比向量承诺更强大的原语，称为多项式承诺。多项式承诺允许您哈希多项式，并提供证明哈希多项式的评估在任何时候。你可以使用多项式承诺作为向量承诺：如果我们同意一组标准坐标（C1，C2，。。。CN），然后给出一个列表（Y1，Y2，。。。Yn），你可以保证多项式P，其中P（CI）=Yi，I属于[1。。。N] （你可以通过拉格朗日插值找到这个多项式）。我在关于zksnarks的文章中详细讨论了多项式承诺。两种最容易使用的多项式承诺方案是kzg承诺和防弹承诺（在这两种情况下，承诺都是32-48字节的椭圆曲线点）。多项式承诺为我们提供了更大的灵活性和效率，而最简单有效的向量承诺就是多项式承诺。

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

公司许可证

利用多项式承诺的附加性质，我们不需要为路径上的每个承诺提供一个证明，而是可以做一个固定大小的证明，证明路径上承诺之间的所有父子链接的密钥数不限。我们通过随机评估使用多个证明来实现这一点。

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

key:4ce节点实际上是前缀为：4C的中间节点的位置e子节点。

Prefix:4C中间节点实际上是Prefix:4中间节点的位置C子节点。

前缀：4中间节点实际上是根的位置4子节点

如果我们有多个值的证明（例如，4ce和420），我们将有更多的节点和更多的链接。然而，我们要证明的是一系列“节点a实际上是节点B的位置I子节点”形式的语句。如果我们使用多项式承诺，这就变成了方程：a（XI）=y，其中y是承诺的散列值。

这个证明的细节是技术性的，丹克拉德费斯特解释得比我好。到目前为止，证明生成过程中最麻烦、最耗时的步骤是计算以下形式的多项式：

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

. 这要求AI（x）在位置Xi处等于Yi。

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

Ai（X）=X²+ X+3级

我们证明了（席＝2）；如果AI（2）=9，那么这将起作用。

Ai（X）-9=X²+ X+6和（X）²+ X-6）（X-2）可以用X-3来划分，如果使用（席＝2，Yi＝10），则公式不成立（x）。²+ X-7）不能被X-2整除，并且没有小数余数。

其余的证明包括提供一个多项式承诺g（x），然后证明该承诺实际上是正确的。再次，请参阅丹克拉德的更多技术说明，以获取其余的证据。

一个证明可以证明无穷多的亲子关系。

我们有它，这就是最大效率的verkle证明。

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

丹克拉德的多重随机评估证明允许证明者证明任意数量的固定值AI（XI）=Yi，给定每个AI的承诺和被证明的值。证明的大小是恒定的（一个多项式承诺，一个数字和两个证明；128-1000字节（取决于使用的方案）。

不需要显式地提供Yi值，因为它们可以直接从verkle证明中的其他值计算出来：每个Yi值本身就是路径中下一个值的哈希值（承诺或叶）。

也不需要显式地提供Xi值，因为路径（和Xi值）可以通过键和从路径派生的坐标来计算。

因此，我们所需要的只是我们正在证明的叶子（关键和价值），以及从每片叶子到根的道路上的承诺。

假设一棵树的宽度为256，节点数为32的2次方，证明将需要证明密钥和值，加上（平均）从值到根的路径上每个值的三个承诺。

如果我们想证明许多值，我们可以进一步保存：不管您想证明多少值，您不需要提供超过256个顶级值。

校样大小（字节）。行：树的大小；列：经验证的键/值对

假设kzg承诺/证明的宽度为256和48字节。还要注意的是，这假设树的最大数目是偶数；对于真正的随机树，添加~0.6的深度（因此每个元素~30字节）。如果使用防弹样式代替kzg，则可以安全地将大小减少到32字节，因此这些大小可以减少1/3。

验证程序和验证器计算负载

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

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

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

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

验证证明是非常有效的。为了证明n个值，验证器需要执行以下步骤。对于数千个值，所有这些步骤都可以在100毫秒内完成：

大小为n的椭圆曲线的快速线性组合

大约4N个字段操作（即256位模运算）

与校样尺寸无关的少量恒定功

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

结论

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

Verkle树确实需要更复杂的密码学来实现，但它们在可伸缩性方面提供了巨大的好处。从中期来看，snark可以进一步改进：我们可以snark已经有效的verkle-proof验证器，以将见证大小减少到接近零，或者在snark变得更好时（例如，通过GKr）切换回snark-Merkle-proof，或者非常snark友好的hash函数或ASIC）。此外，量子计算的兴起将迫使使用hash的starked-Merkle证明发生改变，因为它使得verkle树所依赖的线性同态不安全。但就目前而言，它们为我们提供了与使用这些更先进技术相同的扩展优势，我们已经拥有有效实施这些技术所需的所有工具。