原文作者：以太坊创始人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。
十六进制（每个父节点 16 个子节点）Verkle 树中的节点结构，此处填充了六个（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 树所依靠的线性同态变得不安全。但就现在而言，它们为咱们供给了与运用这些更先进的技能相同的扩展好处，而且咱们现已具有有用施行它们所需的一切工具。
视野开拓
在批评者看来，经济学家对模型的依赖，是经济学几乎所有问题之所在：把复杂的社会生活简化为一些简单的关系，轻易做出明显不符合现实的假设，过度追求数学的严谨性而不顾现实，经常从典型化的抽象推导直接跳到政策结论。-《经济学规则》
