引言
VerkleTree作为ETH2.0升级的一个重要部分,其相比于MerkleTree,在Proof的大小上,有着很大的提升;对于规模在十亿级别的数据,MerkleTree的proof大约需要1kB,而对于VerkleTree,它将小于150Bytes。
VerkleTree的概念在2018年推出,具体的可以参考论文VerkleTree;本文将主要介绍VerkleTree的原理。
MerkleTree?
MerkleTree是一种常见的Accumulator,它可以用来证明某个元素存在于Accumulator中,如下图所示:
如果想要证明=(06:32)在这个Tree中,那图中所有红色标记的node都需要包含在Proof中,然后verifier根据图中所示的路径计算出Root,并和期望的Root进行比较。
VerkleTrees-concept
Basis
KZGforsinglepoint
因为s是有限域F上随机选取的?个点,因此,prover作恶成功的概率为degree(Q)/P。
KZGformulti-points
VerkleTree-ETH
Compressformulti-polys
很明显,我们并不想让Verifier执行这么多次的配对操作。因此,我们需要进行一次Compress,具体如下:
Keypropertie
参考?
1.PCSmultiproofsusingrandomevaluation-Dankrad?Feist:?
https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html
2.?Verkletrees-vitalik:https://vitalik.ca/general/2021/06/18/verkle.html??
3.?VerkleTreespaper:?
https://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf?
4.?Vectorcommitment:https://eprint.iacr.org/2011/495.pdf
5.?Lagrangeinterpolation: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–Zippellemma: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
来源:金色财经
郑重声明: 本文版权归原作者所有, 转载文章仅为传播更多信息之目的, 如作者信息标记有误, 请第一时间联系我们修改或删除, 多谢。