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（灰色标记）进行比较。
Verkle Trees - concept
Basis
KZG for single point
因为s是有限域F上随机选取的⼀个点，因此，prover作恶成功的概率为 degree(Q)/P （Schwartz‒Zippel lemma）。
KZG for multi-points
Verkle Tree - ETH
Compress for multi-polys
很明显，我们并不想让Verifier执行这么多次的配对操作（这个是昂贵的步骤）。因此，我们需 要进行一次Compress，具体如下：
Key properties
a. 该方案允许Prove任意个数的points，且Proof的大小是恒定的（一个承诺，⼀个proof: π ）
b. yi 的值可不显式提供，因为它就是下一层值的hash;
c. xi 的值可不显式提供，可以根据Key判断；
d. 所用到的公开信息就是被证明的key/value对，和由下而上的没层级对应的承诺；
参考
1. PCS multiproofs using random evaluation - Dankrad Feist；
关于我们
Sin7y成立于2021年，由顶尖的区块链开发者组成。我们既是项目孵化器也是区块链技术研究团队，探索EVM、Layer2、跨链、隐私计算、自主支付解决方案等最重要和最前沿的技术。
微信公众号：Sin7Y
GitHub | Twitter | Telegram | Medium| Mirror | HackMD | HackerNoon
IOS
Android