深入了解以太坊的 Verkle 树

与 Merkle Tree 相比，Verkle Tree 作为 ETH2.0 升级的关键部分，在 Proof 大小上得到了很大提升。对于 10 亿大小的数据，Merkle Tree 证明需要 1kB，而 Verkle Tree 证明只需要不超过 150 个字节。

Verkle 树的概念是在 2018 年提出的（更多细节可以在这里找到。）。 Sin7Y 的第 23 次技术评论将展示 Verkle Tree 的原理。

默克尔树

在深入研究 Verkle 树之前，了解 Merkle 树的概念很重要。 Merkle Tree 是一种常见的 Accumulator，可以用来证明 Accumulator 中存在一个元素，如下图所示：

为了证明 (key: value) = (06: 32) 存在于 Tree（绿色标记）中，Proof 必须包含图中所有红色标记的节点。

验证者可以按照图 1 所示的方法计算出 Root，然后与期望的 Root（灰色标记）进行比较。

可以预见，随着Tree的深度和宽度越来越大，Proof size也会越来越大（branched-2的复杂度为log_2(n) ，branched-k的复杂度为(k−1)log_k (n) 。

同样，验证者需要从基层到上层进行大量的 Hash 计算。因此，Tree 的深度和宽度的增加导致验证者的工作量增加，这是不可接受的。

Verkle 树-概念

简单地增加树的宽度可以减少它的深度，但是证明大小不会减少，因为证明大小从原来的log_2(n)变成了(k−1)log_k(n) 。

也就是说，对于每一层，证明者需要提供(k-1)个额外的节点信息。在论文 Verkle Tree 中，John Kuszmaul 提到了一种将证明复杂度降低到logk(n)的方案。

如果我们设置k=1024 ，证明将减少log_2(k) = 10 倍。

Verkle 树设计如下图所示：

对于每个节点，有两条信息：（1）值； (2) 存在证明π 。例如，绿色标记的(H(k,v),π_03)表明H(k,v)存在于承诺C_0中，而π_03是该论点的证明。

类似地， (C_0,π_0)表示C_0存在于承诺C_Root中，而π_0是该论点的证明。

在论文 Verkle Tree 中，这种存在承诺的方法被称为向量承诺。如果使用向量承诺方案对原始数据执行存在承诺，则会得到复杂度为O(1 ) 的 Proof，而 Construct Proof 和更新 Proof 的复杂度为O(n^2),O(n)分别。

因此，为了取得平衡，论文Verkle Tree（如图2所示）中使用了K-ary Verkle Tree方案，使构造Proof、更新Proof和Proof的复杂度为O(kn),O(klogk n ),O(logk n)分别。

具体性能对比见表1：

在本文中，我们不打算详细介绍一些特定的向量承诺方案，John Kuszmaul 在他的论文中已经很好地解释了这些方案。

幸运的是，与向量承诺相比，我们有一个更有效的工具，称为多项式承诺。

给定一组坐标集(c_0,c_1,....,c_n)和一个值集(y_1,y_2,....,y_n) ，可以构造一个多项式（拉格朗日插值），满足P(c_i )=y_i ，并对这个多项式进行承诺。

KZG10和IPA是常见的多项式承诺方案（此时，承诺是椭圆曲线上的一个点，大小通常在 32 到 48 字节之间）。

基础

KZG 单点

以KZG10为例。对于多项式P(x) ，我们使用[P(s)]_1来表示多项式承诺。

众所周知，对于P(x) ，如果P(z)=y ，则(x−z)|(P(x)−y) 。也就是说，如果我们设置Q(x)=(P (x)−y)/(x−z) ，则Q(x)是多项式。

现在，我们为 P(x)P(x) 生成满足 P(z)=yP(z)=y 的证明。即计算[Q(s)]1[Q(s)]1并发送给需要验证的验证者：

因为 s 是有限域 F 中的一个随机选择的点，所以证明者成功的邪恶行为的概率是 degree(Q)/P（ Schwartz-Zippel 引理）。

多点 KZG

现在，我们要证明(z0,z1,....,zk−1)上的多项式P(x)的值分别为(y1,y2,....,yk−1) 。因此，我们需要定义两个多项式：

根据上面的描述，我们需要满足V(x)|(P(x)-I(x)) 。也就是说，存在一个多项式Q(x) ，满足：

因此，Prover 需要为P(x)和Q(x)提供承诺[P(s)]_1,[Q(s)]_1 ，并将承诺发送给验证者。

Verifier 在本地计算[I(s)]_1,[V(s)]_2 ，并验证方程：

很明显，无论有多少点，证明大小都是恒定的。如果我们选择 BLS12-381 曲线，Proof 大小只有 48 字节，效率很高。

Verkle 树 - ETH

与 Merkle Tree 证明一个元素的存在，证明者仍然需要提供O(log_2n)大小的证明相比，Verkle Tree 在证明大小上做了很大的改进。

让我们看看 Verkle Tree 的一个简单示例。

可以看出，与Merkle Patricia Tree结构类似，节点可以分为三种类型——空节点、内节点和叶节点。

每个内部节点树的宽度为 16（十六进制的 0000->1111）。为了证明叶子节点的状态是（0101 0111 1010 1111 -> 1213），我们需要对内节点A和内节点B进行承诺：

1. 证明Inner节点B的commitment值是索引1010处的hash(0101 0111 1010 1111, 1213)。

   
   

2. 证明Inner节点A的commitment值是索引0111处的hash(cm_B)。

   
   

3. 证明节点Root的commitment的值是索引0101处的hash（cm_A）；

用C_0(InnernodeB),C_1(InnernodeA),C_2(Root)来表示上面提到的commitments，分别对应多项式f_i(x) 。

因此，Prover 需要证明：

压缩多个多边形

为方便起见，我们将使用z_i来表示索引。

证明者需要证明对于多项式集合f_0(x),f_1(x),....,f_m−1(x)在点z_0,z_1,....,z_m− 1 ，分别：
根据前面的描述（KZG for Single point），对于每个多项式，都存在一个商多项式满足：
Prover 需要对原多项式和商多项式进行承诺，并发送给 Verifier：

Verifier 执行验证：
很明显，我们不希望验证者执行这么多的配对操作（这很昂贵）。因此，我们需要按如下方式执行 Compress。

生成一些随机数r_0,r_1,....,r_m−1 ，并将上述商多项式收集在一起：
假设当且仅当每个q_i(x)是多项式时， g(x)将是一个多项式（由于随机数， q_i(x ) 之间的分数完全偏移的概率非常低）。

证明者对多项式g(x)进行承诺并将[g(s)]_1发送给验证者。

接下来，让验证者相信[g(s)]_1是对多项式g(x)的承诺。

观察多项式 g(x)g(x) 的形式，可写为：

随机选择一个值 tt 有：

定义多项式：

其承诺可用以下方法计算：

那么多项式 h(x)-g(x)h(x)-g(x) 在点 tt 的值是：

计算商多项式q(x)=(h(x)−g(x)−y)/(x−z) 。

计算承诺π = [q(s)]_1=[(h(s)−g(s)−y)/(s−t)]_1，发送给验证者。

验证者执行以下验证：

1. 计算

   

2. 核实

   

关键属性

1. 在不改变证明大小的情况下，可以使用该方案证明任意数量的点。 （对于每个承诺，都有一个证明π 。）

   
   

2. y_i的值不需要显式提供，因为它是下一层值的哈希值。

   
   

3. x_i的值不需要显式提供，可以通过 Key 来判断。

   
   

4. 使用的公开信息包括要证明的键/值对以及从基层到上层的相应承诺。

参考

1. Dankrad Feist，“使用随机评估的 PCS 多重证明”， https ://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html，访问时间：2022-05-10。

   
   

2. Vitalik Buterin，“Verkle 树”， https ://vitalik.ca/general/2021/06/18/verkle.html，访问时间：2022-05-10。

   
   

3. John Kuszmaul，“Verkle 树”， https ://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf，访问时间：2022-05-10。