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)

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.

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.

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?

Share:

93 out of 132 found this helpful

Discover more

News

Blockchain User Activity Survey Ethereum Still Reigns, Who is Using Litecoin and Tron?

Cryptocurrency KOL Ignas conducted a survey on blockchain user engagement and compiled 7 important insights.

Blockchain

UAE adopts Cardano Blockchain to boost security in criminal investigations.

The UAE has taken the significant step of implementing Cardano's blockchain technology to enhance security in crimina...

Market

Evolution of demand, yield, and products in the ETH Staking market after Shanghai upgrade

Currently, we are still in the dividend period of ETH Staking, so it is advisable for ETH holders to participate in S...

Market

Bitcoin ETFs See Strong Inflows as Bitcoin Bulls Charge Ahead ðŸ’ªðŸš€

Bitcoin and several other altcoins have successfully surpassed their previous overhead resistance levels, demonstrati...

Market

Bitcoin, Ethereum, Solana, Binance Coin, XRP, Cardano, Avalanche, Dogecoin, Chainlink, Polkadot price analysis for 2/16

Bitcoin's strong upward momentum may encounter resistance around \$52,000, but any potential decrease is expected to b...

News

Interpreting the Performance of 14 L1 Public Chains in Q1: Stacks Emerges as Dark Horse, Network Usage Rate Generally Decreases

After the running-in period, various public chains have entered the "internal competition" stage.