Compared to Merkle Tree, Verkle Tree has been improved a lot in the Proof size as a critical part of the ETH2.0 upgrade. When it comes to data with the size of one billion, the Merkle Tree proof will take 1kB, while the Verkle Tree proof only needs no more than 150 bytes. The Verkle Tree concept was proposed in 2018 (More details can be found .). The 23rd tech review by Sin7Y will demonstrate the principle of Verkle Tree. here Merkle Tree Before digging into Verkle Tree, it is important to understand the Merkle Tree concept. Merkle Tree is a common Accumulator, which can be used to prove that one element exists in the Accumulator as shown in the following figure: To prove that (key: value) = (06: 32) exists in the Tree (green-marked), the Proof must contain all red-marked nodes in the figure. The verifier can calculate the Root according to the method shown in Figure 1, and then compare it with the expected Root (grey-marked). It is predictable that with the depth and width of the Tree getting greater, the Proof size will also be larger (for branched-2, the complexity is , while for branched-k, it is . log_2(n) (k−1)log_k(n) As well, the verifier needs to conduct a great number of Hash calculations from the basic level to the upper level. Thus, the increase in the depth and width of the Tree leads to the increase in the verifier’s workload, which is unacceptable. Verkle Tree - Concept Simply increasing the Tree’s width can reduce its depth, but the proof size will not be reduced because the proof size changes from the original to . log_2(n) (k−1)log_k(n) That is, for each layer, the prover needs to provide additional node information. In the paper Verkle Tree, John Kuszmaul mentioned a scheme to reduce the proof complexity to . (k−1) logk(n) If we set , the proof will be reduced by . k=1024 log_2(k) = 10 times The Verkle Tree design is shown as follows: For each node, there are two pieces of information: (1) value; (2) existence proof . For example, the green-marked shows that exists in commitment and is the proof of this argument. π (H(k,v),π_03) H(k,v) C_0 π_03 Similarly, means that exists in commitment and is the proof of this argument. (C_0,π_0) C_0 C_Root π_0 In the paper Verkle Tree, the method of such existence commitment is called . If the Vector commitment scheme is used to execute existence commitment for the original data, the Proof with ) complexity will be obtained while the complexity of Construct Proof and that of update Proof are respectively. Vector commitment O(1 O(n^2),O(n) Therefore, to strike a balance, the K-ary Verkle Tree scheme is used in the paper Verkle Tree (as shown in Figure 2) to make the complexity of construct Proof, update Proof and Proof be respectively. O(kn),O(klogk n),O(logk n) The specific performance comparison is shown in Table 1: In this article, we are not intended to provide a detailed introduction to some specific vector commitment schemes, which John Kuszmaul has explained well in his paper. Fortunately, compared to the vector commitment, we have a more efficient tool called polynomial commitment. Given a group of the coordinate set and a value set , you can construct a polynomial ( ), satisfying , and conduct a commitment to this polynomial. (c_0,c_1,....,c_n) (y_1,y_2,....,y_n) Lagrange interpolation P(c_i)=y_i and are common polynomial commitment schemes (At this point, the commitment is a point on the elliptic curve, typically between 32 and 48 bytes in size). KZG10 IPA Basis KZG for Single Point Take KZG10 as an example. For the polynomial , we use to represent the polynomial commitment. P(x) [P(s)]_1 As we all know, for , if , then .That is to say, if we set , then is a polynomial. P(x) P(z)=y (x−z)|(P(x)−y) Q(x)=(P(x)−y)/(x−z) Q(x) Now, we generate a proof for P(x)P(x) to satisfy P(z)=yP(z)=y. That is, calculate [Q(s)]1[Q(s)]1 and send it to the verifier, who needs to verify: Because s is a randomly-chosen point in the finite domain F, the probability of the prover’s succesful evil behavior is degree(Q)/P ( ). Schwartz–Zippel lemma KZG for Multiple Points Now, we want to prove that the values of the polynomial on are , respectively. Therefore, we need to define two polynomials: P(x) (z0,z1,....,zk−1) (y1,y2,....,yk−1) According to the description mentioned above, we need to satisfy . That is, there exists a polynomial , satisfying: V(x)|(P(x)−I(x)) Q(x) Therefore, the Prover needs to provide the commitments for and , and send the commitments to the verifier. [P(s)]_1,[Q(s)]_1 P(x) Q(x) The Verifier calculates locally, and verifies the equation: [I(s)]_1,[V(s)]_2 It is clear that the proof size is constant no matter how many Points there are. If we choose the BLS12-381 curve, the Proof size is only 48 bytes, which is very efficient. Verkle Tree - ETH Compared to Merkle Tree, in which to prove the existence of an element, the prover still needs to provide the proof with size, Verkle Tree has made a great improvement on the proof size. O(log_2n) Let’s check out a simple example of Verkle Tree. It can be seen that, similar to the Merkle Patricia Tree structure, nodes can be divided into three types - empty node, inner node, and leaf node. The width of each inner node tree is 16 (0000->1111 in hexadecimal). To prove that the state of the leaf node is (0101 0111 1010 1111 -> 1213), we need to conduct the commitment to Inner node A and Inner node B: Prove that the value of Inner node B’s commitment is hash (0101 0111 1010 1111, 1213) at index 1010. Prove that the value of Inner node A’s commitment is hash (cm_B) at index 0111. Prove that the value of node Root’s commitment is hash (cm_A) at index 0101; Use to represent the commitments mentioned above and correspond them to the polynomial respectively. C_0(InnernodeB),C_1(InnernodeA),C_2(Root) f_i(x) Therefore, the Prover needs to prove: Compress for Multiple Polys To make it easy, we will use to represent the index. z_i The prover needs to prove that for the polynomial set , it satisfies the following conditions at points , respectively: According to the previous description (KZG for Single point), for each polynomial, there exists a quotient polynomial satisfying: Prover needs to conduct the commitment to the original polynomial and the quotient polynomial, and send it to the Verifier: f_0(x),f_1(x),....,f_m−1(x) z_0,z_1,....,z_m−1 Verifier executes the verification: It is obvious that we don’t want the verifier to execute so many pairing operations (it’s expensive). Therefore, we need to execute a Compress as follows. Generate some random numbers , and gather the above quotient polynomials together: Assume that if and only if each is a polynomial, will be a polynomial (The probability that the fractions between ) exactly offset is very low because of random numbers). r_0,r_1,....,r_m−1 q_i(x) g(x) q_i(x The prover conducts commitment to the polynomial and send to the verifier. g(x) [g(s)]_1 Next, let the verifier believe that is the commitment to the polynomial . [g(s)]_1 g(x) Observe the form of the polynomial g(x)g(x), which can be written as: Choose a value tt randomly and there is: Define the polynomial: Its commitment can be calculated with the following method: Then the value of the polynomial h(x)−g(x)h(x)−g(x) at point tt is: Calculate the quotient polynomial . q(x)=(h(x)−g(x)−y)/(x−z) Calculate the commitment and send it to the verifier. π = [q(s)]_1=[(h(s)−g(s)−y)/(s−t)]_1, Verifier performs the following verification: Calculate Verify Key Properties Any number of points can be proved using this scheme without changing the Proof size. (For each commitment, there is a proof .) π The value of do not need to be provided explicitly as it is the hash of the next layer value. y_i The value of do not need to be provided explicitly as it can be judged from Key. x_i The public information used includes the key/value pair to be proved and the corresponding commitments from the basic level to the upper level. References Dankrad Feist, “PCS multiproofs using random evaluation,” , accessed: 2022-05-10. https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html Vitalik Buterin, “Verkle trees,” , accessed: 2022-05-10. https://vitalik.ca/general/2021/06/18/verkle.html John Kuszmaul, “Verkle Trees,” , accessed: 2022-05-10. https://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf

Take a Deep Dive Into Verkle Tree For Ethereum

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

A Study on Parallel Execution: Everything You Need to Know

06/09/2018: Biggest Stories in the Cryptosphere

07/09/2018: Biggest Stories in the Cryptosphere

0x Protocol, Waves, and EtherDelta: Solutions and Limitations of Distrust

03/09/2018: Biggest Stories in the Cryptosphere

A Study on Parallel Execution: Everything You Need to Know

06/09/2018: Biggest Stories in the Cryptosphere

07/09/2018: Biggest Stories in the Cryptosphere

0x Protocol, Waves, and EtherDelta: Solutions and Limitations of Distrust

03/09/2018: Biggest Stories in the Cryptosphere

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps