Verkle Tree作为ETH2.0升级的一个重要部分,其相比于Merkle Tree,在Proof的大小上,有着很大的提升;对于规模在十亿级别的数据,Merkle Tree的proof大约需要1kB,而对于Verkle Tree, 它将小于150Bytes。
Verkle Tree的概念在2018年推出,具体的可以参考论文Verkle Tree;本文将主要介绍Verkle Tree的原理。
Merkle Tree
Merkle Tree是一种常见的Accumulator,它可以用来证明某个元素存在于Accumulator中,如下图所示:
如果想要证明(key: value)= (06: 32)在这个Tree中(绿色标记),那图中所有红色标记的 node都需要包含在Proof中,然后verifier根据图中所示的路径计算出Root,并和期望的Root(灰色标记)进行比较。
可以预见的是,随着Tree的深度和宽度变大,则Proof的大小同样会变大(对于branched-2,复杂度为 ,对于branched-k,复杂度为;而且,verifier需要从Tree的底层逐步向上进行大量的Hash计算,一直到顶层,随着Tree的深度和宽度的增加,verifier的工作量也将会变得可观(这是难以接受的)。
Verkle Trees - concept
前面章节提到,单纯的增加Tree的宽度,虽然能减小Tree的深度,但不能降低proof的大小,那是因为Proof的大小由最初的变为了 ; 即, 对于每一层, prover都需要提供 k-1 个额外的节点信息, 论文Verkle Tree给出了⼀个方案, 使得proof的复杂度降低到, 如果令 k=1024 , 则Proof将会缩 倍。
Verkel Tree的设计如下图所示:
每一个节点都包含了两个信息(1)Value;(2)存在性证明π,比如图中的绿色标记表示H(k,v)存在于承诺中,为这个表述的proof;同理,表示存在于承诺中,为这个表述的证明。
在论文Verkle Tree中,这种存在性证明的方式称为Vector commitment;若直接采用Vector commitment的方案对原始数据进行存在性证明,其可以获得O(1)复杂度的Proof,但是构建Proof的复杂度和更新Proof的复杂度分别为O(n²),O(n)。因此,为了在它们之间保持一个平衡,论文Verkle Tree里采用的K-ary的Verkle Tree的方案(如上图所示),使得构建Proof,,更新Proof,Proof的复杂度分别为O(kn),O(),O(),具体性能对比如表1所示:
本文并不打算详细的去介绍vector commitmenr的一些具体方案,有兴趣的可以直接去阅读论文;庆幸的是,我们有比vector commitment更有效的工具 - polynomial commitment(多项式承诺)。给定一组坐标集合和值集合 ,你可以构建一个多项式(Lagrange interpolation)满足 ,然后对这个多项式进行承诺。常见的多项式承诺方案有KZG10 和 IPA(此时,承诺就是椭圆曲线上的一个点,大小一般在32-48Bytes之间)。
Basis
KZG for single point
以KZG10承诺为例,对于多项式P(x),我们用表示多项式承诺。我们知道,对于多项式P(x),如果(z)=y,则有(x−z)|(P(x)−y),即如果令Q(x)=(P(x)−y)/(x−z),则Q(x)是一个多项式。
现在,你为多项式P(x)满足P(z)=y 生成一个证明:即,计算,并且发送给Verifier,Verifier需要验证:
因为s是有限域F上随机选取的一个点,因此,prover作恶成功的概率为 degree(Q)/P(Schwartz–Zippel lemma)。
KZG for multi-points
现在,你想证明多项式P(x)在上的值分别为。为此,你需要定义两个多项式:
则,根据前面的描述,需满足V(x)|(P(x)−I(x)),即,存在多项式Q(x)满足:
Q(x)∗V(x)=P(x)−I(x)。
因此,Pover需要提供对多项式P(x)和Q(x)的承诺,并发送给Verifier;Verifier本地计算,然后校验等式:
可以看到,无论Points有多少个,proof的大小是恒定的,如果选择Bls12-381曲线,Proof的大小只有48Bytes,这一点非常高效。
Verkle Tree - ETH
相比于Merkle Tree,为了证明一个元素的存在性,prover仍然需要提供大小的proof,Verkle Tree在proof大小上实现了巨大的提升。
让我们看一个Verkle Tree的简单示例:
可以看出, 和Merkle Patricia Tree结构类似, node可以分为三类:empty node、inner node和leaf node,每个inner node tree的宽度为16(16进制表示0000->1111);为了证明leaf node的状态为(0101 0111 1010 1111 -> 1213),我们需要对Inner node A和 Inner node B进行承诺:
a. 证明Inner node B的承诺在索引1010处的值为hash(0101 0111 1010 1111, 1213);
b. 证明Inner node A的承诺在索引0111处的值为hash(cm_B);
c. 证明node Root的承诺在索引0101处的值为hash(cm_A);
把上述承诺分别用表示,且分别对应多项式,因此,Prover需要证明的是:
a.
b.
c.
Compress for multi-polys
为了简单, 我们将用来表示索引, 则prover需要证明, 对于多项式集合,分别在点处满足:
根据前面的描述(KZG for single point),对于每一个多项式,都存在一个商多项式满足:
Prover需要对原多项式和商多项式进行承诺,并发送给Verifier:
Verifier执行校验:
很明显,我们并不想让Verifier执行这么多次的配对操作(这个是昂贵的步骤)。因此,我们需要进行一次Compress,具体如下:
我们随机生成一些随机数,然后把上述商多项式组合在一起:
我们假设,当且仅当每个为多项式时,g(x)才是一个多项式(因为随机数的引入,之间的分数部分正好抵消的概率很低)。
prover对多项式g(x)进行承诺,并发送给verifier。
接下来,只需要让verifier相信是对多项式g(x)的承诺:
观察多项式g(x)的形式,其可以写成:
随机选择一个值t,则有:
定义多项式:
其承诺可以用以下方式计算:
则有:多项式h(x)−g(x)在点t的值为:
令:
计算商多项式
计算其承诺,发送给verifier。
Verifier验证:
a. 计算
b. 校验
Key propertie
a. 该方案允许Prove任意个数的points,且Proof的大小是恒定的(一个承诺,一个proof: π);
b. 的值可不显式提供,因为它就是下一层值的hash;
c. 的值可不显式提供,可以根据Key判断;
d. 所用到的公开信息就是被证明的key/value对,和由下而上的没层级对应的承诺。
参考
1. PCS multiproofs using random evaluation - Dankrad Feist; https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html
2. Verkle trees - vitalik :https://vitalik.ca/general/2021/06/18/verkle.html
3. Verkle Trees paper :https://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf
4. Vector commitment:https://eprint.iacr.org/2011/495.pdf
5. Lagrange interpolation:https://en.wikipedia.org/wiki/Lagrange_polynomial
6. KZG10:https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html
7. IPA:https://twitter.com/VitalikButerin/status/1371844878968176647
8. Schwartz–Zippel lemma:https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma
关于我们
Sin7Y成立于2021年,由顶尖的区块链开发者和密码学工程师组成。我们既是项目孵化器也是区块链技术研究团队,探索EVM、Layer2、跨链、隐私计算、自主支付解决方案等最重要和最前沿的技术。
微信公众号:Sin7Y
GitHub:Sin7Y
Twitter:@Sin7Y_Labs
Medium:Sin7Y
Mirror:Sin7Y
HackMD:Sin7Y
HackerNoon:Sin7Y
Email:contact@sin7y.org