Verkle 树

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

在以太坊未来的可扩展性提升中，Verkle tree（下文音译为 “沃克尔树”）正日益显现出重要性。其作用与当前的默克尔树（Merkle tree）无二：可以使用沃克尔树存储大量的数据，并为任意一个或一组数据对象生成一个短小的证据，任何只需拥有这棵树结构的根节点，就可以验证这些证据（验证这些对象确实存储在这棵树上）。

不过，沃克尔树所能提供的关键特性，是其在证据的大小上 效率更高。如果一棵树包含了 100 万个数据对象，在传统的二叉默克尔树上，一个证据的大小大概是 1 kb，但如果是沃克尔树，则只需不到 150 字节 —— 这样大的节约效果，足以使 “无状态客户端” 成为可能。

沃克尔树还是一个新想法：Kuszmaul 在 2018 年的这篇论文中首次提出了这个概念，它还不像其它重要的新密码学结构那样广为人知。本文尝试解释沃克尔树的结构及其背后的密码学原理。短小证据的代价是，它更加依赖更复杂的密码学。不过，在我看来，这里的密码学比起现代的 ZK SNARK 方案，还是简单很多的。在本文中我会尽可能地解释其中的原理。

默克尔树 vs. 沃克尔树 节点结构

讲到树的结构（树上的节点包含哪些内容、是如何安排的），沃克尔树和当前以太坊所用的 “默克尔帕特里夏树” 非常相似。树上的一个节点，要么是 (i) 空的，要么是 (ii) 一个叶子节点，包含一个键和对应的值，或者是 (iii) 一个中间节点，拥有固定数量个子节点（这个数量也即是树的 “宽度”）。一个中间结点的值是由其子节点的值经过哈希计算得出。

一个值在树上的位置由其键决定：在下图中，为了读取键为 4cc 的那个节点，你要从根节点开始，往下走到位置 4 的节点，再往下走到位置 c 的结点（在十六进制中 c = 12） ，然后是位于 c 的子节点。至于键为 baaa 的节点，也一样，先是根节点的位于 b 的子节点，然后是该子节点的位于 a 的子节点。这条 (b, a) 的路径直接包含着键为 baaa 的节点，因为没有别的键以 ba 开头。

- 一个十六进制的沃克尔树（每个父节点都有 16 个子节点）。这棵树存储了 6 个键值对。 -

结构上，沃克尔树和默克尔帕特里夏树的唯一区别在于，沃克尔树实用的时候更宽。帕特里夏树在最有效率的时候，宽度为2（所以以太坊的十六叉帕特里夏树是非常低效的）。沃克尔树则相反，宽度越大则证据越小；唯一的限制在于，如果宽度太大，证据的生成时间可能太久。为以太坊提议的沃克尔树宽度为 256，某些人甚至希望拓宽到 1024（！！）。

承诺与证据

在默克尔树上（包括默克尔帕特里夏树），一个值的证据是所有 姐妹节点 的完整集合：从根节点到目标节点会形成一条路径，所有与该路径上的节点 共享父节点 的节点都必须包含其中。可能有点复杂，那就以下图为例。 下图是一个证明 4ce 节点值的证据。所有以红色标记的节点都要包含在证据中。 - 译者注：从根节点到目标节点（下方的绿色节点）的路径涉及两个以黄色标记的节点，那么，绿色节点的证据必须包含三个以深红色标记的节点和一个以浅红色标记的节点（分别是 4ce、 4c 和 4 的姐妹节点）。 -

那要包含的节点可太多了！你需要提供树上每一层的姐妹节点，因为你需要一个节点的完整子节点集合来计算该节点的值；每一层都需要这样做，直至你上溯到根节点。你可能觉得这也不算什么，因为大部分节点都是空的。但这只是因为这棵树的节点比较少而已。如果一棵树有 256 个随机分配的节点，那么顶层几乎必然是满的，而第二层平均而言也有约 63.3% 的几率是满的。

而在沃克尔树上，你不需要提供姐妹节点；相反，你只需要提供路径，再加一些额外的数据作为证据。这就是为什么沃克尔树可以从更大的宽度中获得好处，而默克尔树就不行：宽度更大，路径必然较短（树高较矮），但在默克尔树上，好处就被增加的姐妹节点数量盖过去了（每层都有提供 宽度 - 1 个姐妹节点），所以证据的规模并不能缩小。但在沃克尔树上，这一开销并不存在。

那我们还需要哪些数据作为证据呢？要理解这一点，我们要回到一个关键的细节：用来计算一个内部节点值的哈希函数并不是常规的哈希函数，它是一种 “向量承诺”。

向量承诺方案是一种特殊类型的哈希函数，是哈希一个列表$h(z_1,z_2,...,z_n)\rightarrow C$ 。但是向量承诺有一个特殊的性质，对于一个承诺值 $C$ 和一个值 $z_i$ ，可以提出一个简短的证据，证明 $C$ 是对一组数值的承诺，其改组数值中第 i 个位置的值为 $z_i$ 。在一个沃克尔证据中，这个简短的证明替代了默克尔证明中的姐妹节点，给了验证者以信心：某个数值确实是其父节点在给定位置的子节点。

- 不需要给沃克尔证据提供姐妹节点；只需要提供路径，再为路径上的每个承诺提供一个简短的证明即可 -

在实践中，我们使用一种比向量承诺更强大的密码学元件，叫做 “多项式承诺”。多项式承诺让你可以哈希一个多项式，并为这个被哈希的多项式在 任意点 的值提出证明。你可以使用多项式承诺来充当一个向量承诺：假设我们都同意一组标准化的坐标值 $(c_1, c_2 ... c_n)$ ，给定一组值 $(y_1, y_2 ... y_n)$ ，你可以承诺有一个多项式 P，P 对任意 $i \in [1..n]$ 都有 $P(c_i) = y_i$（至于这个 P 本身，你可以用拉格朗日插值法来获得）。我在论述 ZK-SNARK 技术的文章中，对多项式承诺有详细的讲解。最容易使用的两种多项式承诺方案是 “KZG 承诺” 和 “bulletproof 类型的承诺”（在两种方案中，一个承诺都是单个 32 ～ 48 字节的椭圆曲线点）。多项式承诺可以给我们更多的灵活性、让我们能提高效率，而碰巧，最简单最高效的向量承诺 就是 多项式承诺。

这种方案已经非常厉害了：如果你使用 KZG 承诺和证据，每个中间节点的证据只有 96 字节，比起简单默克尔树有接近 3 倍的空间节约（假设宽度为 256）。不过，事实证明，我们还可以进一步提高空间效率。

合并证据

如果不是给路径上的每个承诺都提供一个证明，而使用多项式承诺额外的属性，我们就可以为一条路径上 所有 承诺间的父子链接制作一个固定大小的证据，可以容纳的键的数量是无限的。这需要用到一个通过随机求值来实现的多数值证明（multiproof）。

但为了使用这种方案，我们先要把这个问题转化为一个更加结构化的问题。我们有一个证据，可以证明一棵沃克尔树上有一个或多个值。这个证据的主要组成部分，是从根节点到每个叶子的路径上的中间节点。对这个证据所涉及的每个节点，我们都要证明它是上一层节点的子节点（而且对位置的声明也是对的）。在我们上面那个单数值证据的案例中，我们需要证据来证明：

• key: 4ce 这个节点恰是 prefix: 4c 中间节点的位置 e 处的子节点
• prefix: 4c 中间节点恰是 prefix: 4 中间节点位于 c 处的子节点
• prefix: 4 中间节点恰是根节点位于 4 处的子节点

如果我们要让一个证据同时证明多个数值（例如，4ce 和 420），那就会有更多的节点和更多的链接。但无论怎么说，我们需要做的都是按顺序证明一系列形式如 “节点 A 恰是节点 B 位于 i 处的子节点” 的语句。如果我们使用多项式承诺，这些语句就可以转化为等式：$A(x_i) = y$，而 y 是对 B 承诺的哈希值。

这个证据的细节是技术上的，而且 Dankrad Feist 解释得比我好。到目前为止，在证据的生成中最庞大也最耗时的一步是计算一个如下形式的多项式 g：

$g(X) = r^0\frac{A_0(X) - y_0}{X - x_0} + r^1\frac{A_1(X) - y_1}{X - x_1} + ... + r^n\frac{A_n(X) - y_n}{X - x_n}$

每一项 $ r^i\frac{A_i(X) - y_i}{X - x_i}$ 都必须是一个多项式才能计算出来。这就要求 $A_i(X)$ 在点 $x_i$ 处等于 $y_i$ 。

我们可以用一个例子来理解。假设：

• $A_i(X) = X^2 + X + 3$
• 我们想证明 $(x_i = 2, y_i = 9)$ 。而 $A_i(2)$ 恰等于 9，所以这是对的。

$A_i(X) - 9 = X^2 + X - 6$ ，而 $\frac{X^2 + X - 6}{X - 2}$ 这个式子的结果很清楚是 $X - 3$ 。但如果我们尝试把 $(x_i = 2, y_i = 10)$ 放进去，那就不行了， $X^2 + X - 7$ 无法 被 $X - 2$ 整除，一定会有分数形式的余数。

证据其余的部分还要提高一个对 $g(X)$ 的多项式承诺，并证明这个承诺是正确的。这个证明过程，还是去看 Dankrad 的技术讲解好一些。

- 单个证据可以证明无数个父子关系。 -

这就是最有效率的沃克尔证据。

这种方案在证据大小上的关键特性

• Dankrad 的多重随机求值证据（multi-random-evaluation proof）让证明者可以证明任意数量个求值关系 $A_i(x_i) = y_i$ （给定对每个 $A_i$ 和尝试证明的数值的承诺）。证据的大小是恒定的（一个多项式承诺、一个数字，和两个证据；128 ～ 1000 字节，取决于所用的方案）。
• $y_i$ 并不需要显式提供， 因为可以从沃克尔证据中的其它数值直接计算得出：每个$y_i$ 都是路径中下一个数值（无论是一个叶子还是一个承诺值）的哈希值。
• $x_i$ 也不需要显式提供，因为路径（以及 $x_i$ 的数值）可以从它们的键以及从路径中推导出的坐标值计算得出。
• 因此，我们需要提供的只有我们想证明的叶子节点（键和值），还有每个叶子到根节点路径上的所有承诺值。
• 假设树的宽度为 256，我们有 2^32 个节点，一个证据只需提供（要证明的）键和值，以及（平均而言）为每个值提供三个承诺值。
• 如果我们要同时证明很多值，还有更进一步的节约：无论我们要证明多少个值，在顶层你最多只需提供 256 个值。

证据大小（字节）。行为树的规模，列为要证明的 键值对 数量

假设宽度为 256，KZG 承诺值的大小为 48 字节。此外，假设了这是最大限度的偶树（a maximally even tree）；比起现实中的随机树，其深度要深约 0.6 倍（所以每个元素要多约 30 字节）。如果使用的是 bulletproof 类型的承诺方案，（承诺值）可以安全地降低到 32 字节，而证据的规模也可以缩小 1/3。

证明者和验证者的计算开销

生成证据的开销的大头是计算每个 $r^i\frac{A_i(X) - y_i}{X - x_i}$ 表达式。这需要大概四次域操作（field operation）（即 256 位的模块化的算术运算）乘以树的宽度。这也是限制沃克尔树宽度的主要因素。好就好在，四次域操作的开销不大：一次椭圆曲线乘法通常需要几百次的域操作。因此，沃克尔树的宽度可以非常大；从 256 到 1024 似乎都是理想的范围。

在编辑树的时候，我们需要从根节点一路向上走到根节点，改变每一个步骤遇到的中间承诺值，以反映更底层发生的变更。不过，我们不需要重新开始计算每一个承诺值。我们可以利用同态属性：给定一个承诺值 $C = com(F)$ ，我们可以通过$C' = C + com(G)$ 来计算$C' = com(F + G)$ 。在我们的案例中， $G = Li * (v{new} - v_{old})$ ，而 $L_i$ 是一个预先计算好的承诺值，在我们更改的位置等于 1， 而在别的位置都等于 0。

因此，单次编辑需要约 4 次椭圆曲线乘法（在叶子节点和根节点之间每个承诺值都需要一次编辑，包括根节点），不过这些计算可以通过预计算和存储每个 $L_i$ 的 许多乘数 来大幅加速。

证据验证是非常高效的。对一个证明了 N 个值的证据，验证者需要做下列步骤，所有操作都可以在 100 毫秒内完成，即使数值有几千个：

• N 次 椭圆曲线快速线性组合
• 大概 4N 次域操作（即 256 位的模块化的算术运算）
• 一小部分恒定的工作，不依赖于证据的规模

此外，就像默克尔帕特里夏证据，沃克尔证据也会给验证者足够的信息来 修改 树上被证明的位置的值并计算（执行更改后）新的根哈希值。这对于验证诸如区块的状态更改得到正确的执行之类的事项非常重要。

结论

对比默克尔树，沃克尔树是非常强大的升级，它使我们可以做出小得多的证据。运用沃克尔树之后，证明者不再需要提供路径上所以层级的所有 “姐妹节点”，只需为从根节点到目标叶子节点路径上的所有承诺值之间的父子关系提供一个证据。只此一点，就可以让证据的大小缩小约 6 ～ 8 倍（对比理想的默克尔树），若是对比以太坊当前所用的默克尔帕特里夏树，可缩小超过 20 ～ 30 倍（！！）。

沃克尔树需要更复杂的密码学来实现，但它有机会给可扩展性带来巨大收益。从中期来看，SNARK 可以提升更多：我们既可以 SNARK 化已经很有效率的 沃克尔证据验证者，把见证数据的大小降低到近于零；或者切换回 SNARK 化的默克尔证据，只要 SNARK 可以变得更好（例如，通过 GKR、或者 SNARK 极度友好型的哈希函数，或者 ASIC）。更进一步地说，量子计算的兴起会让沃克尔树所依赖的线性同态属性变得不安全，所以我们必须转向 SNARK 化的默克尔证据。但从目前来看，沃克尔树给了我们同样的可扩展性收益（比起其他更高级的技术），而我们已经具备了高效实现沃克尔树所需的所有工具。

（完）

原文链接: https://vitalik.ca/general/2021/06/18/verkle.html 作者: Vitalik 翻译: 阿剑

本文首发于：https://ethfans.org/posts/verkle-trees-and-verkle-proofs-by-Vitalik#render