Vitalik: Ethereum state explosion problem, polynomial promise solution can solve

Written in front: In order to cope with the state explosion of Ethereum, Ethereum co-founder Vitalik proposed a new solution, which proposed to replace the Merkle tree with a polynomial commitments scheme, which greatly improved Reduce witnesses for stateless Ethereum clients.

(Photo: Ethereum co-founder Vitalik Buterin)

(Hint: the article has many formulas, the translation is for reference only, the original text shall prevail)

• How to correctly understand DAO tokens?
• Data Increment: New Business Opportunities for Enterprise Services + Blockchain
• DeFi pattern or big change, Tether announces entry into DeFi, integrates Lightning loan agreement Aave

The following is a translation:

Regarding this research, I would like to thank many people for their help, especially (1) the AZTEC team introduced me to copy constraint parameters, sorting parameters, and effective batch range proof methods; (2) Datery Khovratovich and Justin The solution provided by Drake in the Kate Promise section, (3) Eli Ben Sasson's feedback on the FRI, and (4) the review performed by Justin Drake. This article is just the first attempt, and if there is any further important thinking, I do hope that this solution can be replaced by a similar but better plan.

Too annoying not to see the summary of the edition:

We propose to replace the Merkle tree with a magical mathematics called "polynomial commitments" to accumulate the state of the blockchain. Benefits include: reducing the size of witnesses for stateless clients to near zero. This article presents the challenges of state accumulation using polynomial commitments, and proposes specific construction methods.

What are polynomial commitments?

A polynomial promise is a type of 'hash' of a polynomial P (x) that has attributes that can perform arithmetic checks on the hash.

For example, on three polynomials P (x), Q (x), R (x), given three polynomial commitments h_P = commit(P(x)) , h_Q = commit(Q(x)) , h_R = commit(R(x)) , then:

1. If P(x) + Q(x) = R(x) , you can generate a proof that proves its relationship with h_P, h_Q, h_R (in some constructions, you can simply check h_P + h_Q = h_R） ;
2. If P(x) * Q(x) = R(x) , you can generate a proof to prove its relationship with h_P, h_Q, h_R ;
3. If P(z) = a , you can produce a proof for h_P (called an opening proof or opening for short)

You can use polynomial promises as vector promises, similar to a Merkle tree. One of the main advantages of polynomial promises is that it is much easier to generate complex proofs due to their mathematical structure (see below for a detailed explanation).

What are the popular polynomial commitment schemes?

There are currently two frontrunners, Kate Promise (search for "Kate" in this article ) and FRI- based Promise. You may also have heard of Bulletproofs and DARKs algorithms, these are alternative polynomial commitment schemes. And to learn more about polynomial promises, there is related content on YouTube ( part 1 , part 2 , part 3 , and slides ).

What are the easy applications of polynomial promises in Ethereum?

We can replace the Merkel root of the current block data with polynomial promises (such as the shard block of Ethereum 2.0), and replace the Merkle branches with open proofs . This gives us two great advantages. First of all, data availability checks will become easy and there will be no fraud, because you can simply request opening in a random manner (such as 40 of the 2N coordinates of an N-degree polynomial). Non-interactive hosted proofs may also become easier.

Second, it becomes easier to persuade light clients with multiple data fragments, because you can make a valid proof that covers multiple indexes simultaneously. For any set {(x_1, y_1), ..., (x_k, y_k)} , define three polynomials:

1. An interpolation polynomial I(x) through all these points;
2. At x_1，...，x_k equal to zero zero polynomial Z（x）=（x-x_1）* ... *（x-x_k） ;
3. Quotient polynomial Q（x）=（P（x）-I（x））/Z（x） ;

The existence of the quotient polynomial Q（x） means that P(x) - I(x) P（x）-I（x） is a multiple of Z（x） , so P（x）-I（x） is zero, where Z(x) is zero. This means that for all i , we have P(x_i) - y_i = 0 , that is, P(x_i) = y_i . The verifier can generate interpolation polynomials and zero polynomials. Proof (proof) consists of a commitment to the quotient, plus an open proof at a random point z , so we can have a constant size witness content for any number of points.

This technique can provide some benefits for multiple accesses to block data. However, it has a much greater advantage for a different use case: proof of block trading account witness. On average, hundreds of accounts and storage keys are accessed per block, which results in a potential stateless client witness content size of 0.5 MB. The polynomial promises multi-witness. Depending on the solution, the size of the block witness can be reduced from tens of thousands of bytes to hundreds of bytes.

Can we use polynomial promises to store state?

In general, we can. S_v(x) storing the state as a Merkle tree, we choose to store the state as two polynomials S_k(x) and S_v(x) , where S_k（1），...，S_k（N） represent the keys (Key), while S_v（1），.. 。，S_v（N） S_v（1），.. 。，S_v（N） represents the values ​​on these keys (if the value is greater than the field size, at least the hash value of these values).

In order to prove that the key-value pairs （k_1，v_1），...，（k_k，v_k） are part of the state, we will provide the indexes i_1, ..., i_k and (using the interpolation technique mentioned above) show that they match the index Keys and values ​​of k_1 = S_k(i_1), ..., k_k = S_k(i_k) and v_1 = S_v(i_1), ..., v_k = S_v(i_k) .

In order to prove the non-membership of some keys, you can try to construct a peculiar proof that the keys are not in S_k（1），…，S_k（N） . Instead, we only need to sort the keys so that non-membership is sufficient to prove the membership of two adjacent keys, one smaller than the target key and one larger than the target key.

This has similar benefits to the idea of ​​using SNARKs / STARKs to compress witness and related ideas justified by Justin Drake. Another benefit is that because the proof is native to accumulator cryptography, rather than a proof built on accumulator cryptography, This therefore eliminates an order of magnitude overhead and removes the need for a zero-knowledge proof-friendly hash function .

But there are two big problems here:

1. The time required to generate witnesses for k keys is O（N） , where N is the size of the state. The state data corresponding to N is expected to be about 50 GB , so it is not practical to generate such a proof in a single block;
2. 2. The time it takes to update S_k(x) and S_v(x) with k new values ​​also requires O（N） . This is impractical in a single block, especially considering complexity such as witness updates and reordering.

Below we introduce solutions to these two problems.

Efficient reading

We offer two solutions, one designed for Kate commitments and the other for FRI-based commitments. Unfortunately, these schemes have different advantages and disadvantages, which can lead to different properties.

1.Kate promises

First, please note that for N-degree polynomial f, there is a scheme that generates N corresponding to each q_i(x) = (f(x) - f(i)) / (X - i) in O(N * log(N)) time q_i(x) = (f(x) - f(i)) / (X - i) Open Proof.

Also note that we can merge witnesses as follows. Considering the fact that q_i(x) is just a sub-constant term leaving f（x）/（Xi） , usually, f/((X - x_1) * ... * (X - x_k)) is a linear combination of f /（X-x_1），...，f /（X-x_k） f/((X - x_1) * ... * (X - x_k)) , f /（X-x_1），...，f /（X-x_k） using partial fraction decomposition. You only need to know the x coordinate to determine the specific linear combination: just propose a linear combination c_1 * (x - x_2) * ... * (x - x_k) + c_2 * (x - x_1) * (x - x_3) * ... * (x - x_k) + ... + c_k * (x - x_1) * ... * (x - x_{k-1}) , where there are no non-constant terms, which are k unknowns K equations in.

Given such a linear combination, what we get is just a sub-constant term leaving f/((x - x_1) * ... * (x - x_k)) (since all original errors are sub-constants, so The combination of linear errors must be sub-constant), so it must be the quotient f(x) // ((x - x_1) * ... * (x - x_k)) which is equal to the expected value (f(x) - I(x_1 ... x_k, y_1 ... y_k)) / ((x - x_1) * ... * (x - x_k)) .

A possible challenge is that for large states, a single, realistically computable single trusted setting (for example, more than 100 independent participants, so as long as any one of them is honest, the solution is secure) is not large enough: The PLONK setting can only hold about 3.2 GB. Instead, we can have a state consisting of multiple Kate promises.

We make a single witness to many promises as follows. For proof , First let (This is a linear combination of fi and 1 so the verifier verifier can calculate this promise in real time). witness is ; If Q is a polynomial, then F is actually zero at those positions, so fi has the expected value at its position.

2.FRI-based commitments

We store the state in the evaluation of a two-dimensional polynomial F（x，y） (the order of each variable is sqrt（N） ), and we work on 4*sqrt(N) by 4*sqrt(N) square evaluates F

We store all the values ​​we care about at position (x, x**sqrt(N)) , so they all have unique x coordinates. (Note that in many cases, these positions will exceed 4*sqrt(N) by 4*sqrt(N) square , which we promise to evaluate, and it doesn't matter.)

In order to prove the evaluation on a set of points x_1, ..., x_k , we construct a k-degree polynomial path （x） whose evaluation at x_i ** sqrt（N） is x_i ** sqrt（N） .

We then create a polynomial h(t) = F(t, path(t)) that contains all the expected evaluations of (x_i, y_i) and has k*（1+sqrt（N）） times.

We select 30 random columns c_1 ... c_k in the evaluation domain, and query 30 random rows for each column. We promise to h (use FRI to prove that it is actually a polynomial), provide a multi-opening for z_i = h(c_i) ), and give the column quotient (R_i - z_i) / (X - path(c_i)) Perform FRI random linear combination to verify that the declared value of h（c_i） is correct, so h(t) actually equal to F(t, path(t)) .

The reason for using a two-dimensional polynomial is that this ensures that we do not have to perform any calculations on all F ; instead, we only need to calculate the random 30 rows of F we choose (ie 30*sqrt（N） ), plus the order is p * (sqrt(N) + 1) h , the calculation performed to create the FRI is approximately p * sqrt(N) . This technique can be extended to polynomials above two dimensions to reduce the sqrt factor to lower exponents.

Efficient writing

We use a series of commitments to address the challenges associated with updating a single commitment that includes the entire state. The larger the commitment, the less frequent it is:

1. The block itself has "read witnesses" (R_k(x) , R_v(x)) and "write witnesses" （W_k（x） , W_v（x） ), indicating the value of the status to be written. Note that we can set W_k = R_k and calculate W_v at runtime.
2. The first cache C1 =（C1_k（x），C1_v（x）） stores the updated content of the last day;
3. The second cache C2 is equal to the last C1 of the previous day;
4. Full state S = （S_k（x），S_v（x）） contains values ​​longer than 1-2 days;

The method we will use is as follows. In order to read some keys k from the state, we will read C1 , C2 , S . If the key is at C1_k（x） , the corresponding value C1_v（x） stores the value, if the key is at C2_k（x） , then C2_v（x） stores the value, and so on, if the key is at S_k（x） , Then S_v（x） stores the value. If none of these checks have a return key, the value is 0.

Introduction to copy constraint parameters

Copy constraint parameters are a key component of the witness update proof we will use; for more information on how copy constraint parameters work, see here . In short, the idea is to choose a random r and generate a "cumulative" polynomial ACC（x） where ACC（0）= 1 and ACC（x + 1）= ACC（x）*（r + P（x）） . You can read point accumulators in the range of x .... y-1 by open reading ACC(y) / ACC(x) . You can use these accumulator values ​​to compare these evaluations with other evaluation sets (as multiple sets), regardless of permutations.

You can also prove that some random tuples of r and r2 are evaluated by setting ACC(x+1) = ACC(x) * (r + P_1(x) + r2 * P_2(x)) (that is, multiple sets {(P_1(0), P_2(0)), (P_1(1), P_2(1)), ...} ). Polynomial promises can be used effectively to prove claims about ACC.

To prove the subset, we can do the same thing, except that we also provide an index polynomial ind（x） , prove that the ind(x) is equal to 0 or 1 in the whole range, and set ACC（x + 1）= ACC（x ）*（ind（x）*（r + P（x））+（1-ind（x））） (ie, if the index is 1, then multiply by r + P（x） at each step, otherwise No accumulator value is used).

summary:

1. We can prove that the evaluation of P (x) between a and b is a permutation of Q (x) evaluation between a and b (or some different c and d);
2. We can prove that the P (x) evaluation between a and b is a subset of the Q (x) evaluation permutation between a and b (or some different c and d);
3. We can prove that the evaluation of P (x) and Q (x) is R (x) and S (x) permutation, where P-> Q and R-> S are the same permutation;

In the following, unless explicitly stated otherwise, we will lazily express it as "P is a permutation of Q", which means "the evaluation of P between 0 and k, which is the appropriate k between 0 and k Evaluated Permutation. " Please note that in the following, we will also refer to the "size" of each witness to determine the coordinates in any C_k we accept, and of course C_k（x） values ​​that are out of range are not counted.

Map merging argument

To update the cache, we use "merge merge parameters". Given two maps A=（A_k（x），A_v（x）） and B=（B_k（x），B_v（x）） , generate a merge map C=（C_k（x），C_v（x）） so that :

1. The keys in C_k are classified;
2. For 0 <= i <size (B), (B_k (i), B_v (i)) is in C;
3. For 0 <= i <size (A), only when A_k (i) is not in the evaluation set of B, (A_k (i), A_v (i)) is in C;

We do this with a series of replication constraint parameters. First, we generate two auxiliary polynomials U（x） and I（x） , which represent the "union" and "intersection" of A_k and B_k , respectively. A_k，B_k，C_k，U，I as sets, we first need to show:

1. A_k ⊆ U ;

2. B_k ⊆ U ;

3. I ⊆ A_k ;

4. I ⊆ B_k ;

5. A_k + B_k = U + I ;

We assume in advance that there is no duplication in A_k and B_k , which means A_k（i）！= A_j（j） A_k（i）！= A_j（j） for i！= j range i！= j i！= j is the same as B_k (because this has been verified before using this algorithm). Since I is a subset of A_k and B_k , we already know that I has no duplicate values. By using another replication constraint parameter to prove the equivalence relationship between U and C_k , it is proved that there are no duplicates in U , and that C_k is ordered and has no duplicates. We use a simple replication constraint parameter to prove the A_k + B_k = U + I statement.

To prove that C_k is sorted and not duplicated, we prove that C_k（x + 1）> C_k（x） a range of 0 ... size（C_k） . We generate polynomials D_1（x），...，D_16（x） and prove that C（x + 1）-C（x）= 1 + D_1（x）+ 2 ** 16 * D_2（x）+ 2 ** 32 * D_3（x）+... to do this. In essence, D_1（z），...，D_16（z） store the differences in the base 2**16 . Then, we generate a polynomial E（x） that satisfies all the replication constraints of D_1，...，D_16 and f（x）= x and satisfies E(x+1) - E(x) = {0, 1} Restriction (2nd constraint on E). We also checked that E（0）= 0 and E（size（C_k）* 16 + 65536）= 65535 .

The constraint on E shows that all values ​​in E are sandwiched between 0 and 65535 (including 0 and 65535). For D_i 's replication constraint, prove that all values ​​in D_i（x） are between 0 and 65535 (inclusive), which proves that it is a correct hexadecimal representation, which proves C_k（x+1）-C_k（x） actually a positive number.

Now we need to prove the value. We add another polynomial U_v（x） and verify:

1. (U, U_v) at 0...size(B) is equal to (B_k, B_v) at 0...size(B) (B_k, B_v) ;
2. (U, U_v) at size(B) ... size(A)+size(B) a (U, U_v) of （A_k，A_v） at 0...size(A) ;

The goal is that in U , we place all the values ​​from B first, then the values ​​from A , and use the same substitution parameters to ensure that the key and value are copied correctly. We then verify that （C_k，C_v） is a permutation of （U，U v） .

Merge parameters using mapping

We use the map merge parameters as follows, assuming that there are BLOCKS_PER_DAY blocks per day.

1. If block.number % BLOCKS_PER_DAY != 0 , we verify that (C1_k, C1_v) = merge((W_k, W_v), (C1_old_k, C1_old_v)) (Merge blocks to C1);
2. If block.number % BLOCKS_PER_DAY == 0 , we verify that (C1_k, C1_v) = (W_k, W_v) and (C2_k, C2_v) = (C1_old_k, C1_old_v) (that is, we "clear" C1 and move its content into C2);

Note that C2 has a full day, during which it stays the same. We provide a reward for the proof that anyone produces （S_k，S_v）= merge（（S_old_k，S_old_v），（C2_k，C2_v）） ; after providing this proof, we will promise to update （S_k，S_v） to the new value and will （C2_k，C2_v） reset to null. If S is not updated on the same day, we delay C1-> C2 transmission until the update; please note that the protocol does depend on whether S is updated fast enough. If this is not possible, then we can solve this problem by adding more layers of cache hierarchy.

Recovering from a bad FRI

In the case of FRI, note that there may be cases where someone-generated FRI is not valid in some locations, but this is not enough to prevent verification. This does not immediately pose a security risk, but may prevent the next updater from generating witnesses.

We solve this problem in the following ways. First, someone who notices that some FRIs generate errors can provide their own FRIs. If it passes the same check, it will be added to the list of valid FRIs that can build the next update. We can then use interactive computing games to detect and punish creators of bad FRIs. Second, they can provide their own FRI and STARK to prove its validity, thus immediately punishing the creator of the invalid FRI. It is very expensive to generate STARK through FRI, especially on larger scales, but it is worth doing so because it can earn a large portion of the margin bonus of invalid proposers.

So we have a mechanism to use polynomial promises as a valid read and write witness to store state. This allows us to significantly reduce the size of witnesses, while also bringing some benefits, such as giving us the ability to check the availability of data, and implementing escrow proof of status .

Future work

1. Submit FRI certification, requiring less than 900 queries (more formally, security parameters are less than square);
2. Theoretically, if you calculate and store the Lagrange basis in advance, you can theoretically update the Kate promise quickly. Can this be extended to (i) quickly update all witnesses, and (2) work for key-value mapping instead of a vector?

We will continue to update Blocking; if you have any questions or suggestions, please contact us!