与 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的复杂度为 ，branched-k的复杂度为 。 log_2(n) (k−1)log_k (n) 同样，验证者需要从基层到上层进行大量的 Hash 计算。因此，Tree 的深度和宽度的增加导致验证者的工作量增加，这是不可接受的。 Verkle 树-概念 简单地增加树的宽度可以减少它的深度，但是证明大小不会减少，因为证明大小从原来的 变成了 。 log_2(n) (k−1)log_k(n) 也就是说，对于每一层，证明者需要提供 个额外的节点信息。在论文 Verkle Tree 中，John Kuszmaul 提到了一种将证明复杂度降低到 的方案。 (k-1) 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 中，这种存在承诺的方法被称为 。如果使用向量承诺方案对原始数据执行存在承诺，则会得到复杂度为 ) 的 Proof，而 Construct Proof 和更新 Proof 的复杂度为 分别。 向量承诺 O(1 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 和 是常见的多项式承诺方案（此时，承诺是椭圆曲线上的一个点，大小通常在 32 到 48 字节之间）。 KZG10 IPA 基础 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 证明一个元素的存在，证明者仍然需要提供 大小的证明相比，Verkle Tree 在证明大小上做了很大的改进。 O(log_2n) 让我们看看 Verkle Tree 的一个简单示例。 可以看出，与Merkle Patricia Tree结构类似，节点可以分为三种类型——空节点、内节点和叶节点。 每个内部节点树的宽度为 16（十六进制的 0000->1111）。为了证明叶子节点的状态是（0101 0111 1010 1111 -> 1213），我们需要对内节点A和内节点B进行承诺： 证明Inner节点B的commitment值是索引1010处的hash(0101 0111 1010 1111, 1213)。 证明Inner节点A的commitment值是索引0111处的hash(cm_B)。 证明节点Root的commitment的值是索引0101处的hash（cm_A）； 用 来表示上面提到的commitments，分别对应多项式 。 C_0(InnernodeB),C_1(InnernodeA),C_2(Root) f_i(x) 因此，Prover 需要证明： 压缩多个多边形 为方便起见，我们将使用 来表示索引。 z_i 证明者需要证明对于多项式集合 在点 ，分别： 根据前面的描述（KZG for Single point），对于每个多项式，都存在一个商多项式满足： Prover 需要对原多项式和商多项式进行承诺，并发送给 Verifier： f_0(x),f_1(x),....,f_m−1(x) z_0,z_1,....,z_m− 1 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， 验证者执行以下验证： 计算 核实 关键属性 在不改变证明大小的情况下，可以使用该方案证明任意数量的点。 （对于每个承诺，都有一个证明 。） π 的值不需要显式提供，因为它是下一层值的哈希值。 y_i 的值不需要显式提供，可以通过 Key 来判断。 x_i 使用的公开信息包括要证明的键/值对以及从基层到上层的相应承诺。 参考 Dankrad Feist，“使用随机评估的 PCS 多重证明”， ://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html，访问时间：2022-05-10。 https Vitalik Buterin，“Verkle 树”， ://vitalik.ca/general/2021/06/18/verkle.html，访问时间：2022-05-10。 https John Kuszmaul，“Verkle 树”， ://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf，访问时间：2022-05-10。 https

Ethereum

Twitter

2022 - HackerNoon Contributor of the Year - Algorithms

2022 - HackerNoon Contributor of the Year - Architecture

2022 - HackerNoon Contributor of the Year - Blockchain

2022 - HackerNoon Contributor of the Year - Optimization

2022 - HackerNoon Contributor of the Year - Privacy

Nominated for 2022 - HackerNoon Contributor of the Year - Optimization

Nominated for 2022 - HackerNoon Contributor of the Year - Algorithms

Nominated for 2022 - HackerNoon Contributor of the Year - Privacy

Nominated for 2022 - HackerNoon Contributor of the Year - Architecture

Nominated for 2022 - HackerNoon Contributor of the Year - Blockchain

該音頻是用故事的原始語言製作的！

太長; 讀書

深入了解以太坊的 Verkle 树

深入了解以太坊的 Verkle 树

太長; 讀書

People Mentioned

Company Mentioned

Coin Mentioned

@sin7y

相關故事