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
