Polynomial commitment is polynomial P, Q, given three polynomial commitments h_P= commit), h_Q = commit), h_R = commit), and then: If P = R, prove its relationship with h_P, h_Q, h_R; if P = R, prove its relationship with h_P, h_Q, h_R; if P you can use polynomial commitment

Disclaimer: This article is intended to convey more market information and does not constitute any investment advice. The article only represents the author's views and does not represent the official position of Mars Finance.

Editor: Remember to follow

Source: Babbitt

Original title: Vitalik: Ethereum state explosion problem, polynomial commitment solution can solve

Author: Vitalik Buterin

Translation: Free and easy to see

Write in the previous article: In order to deal with the state explosion problem of Ethereum, Ethereum co-founder Vitalik proposed a new solution, which proposed to use polynomial commitments solution to replace Merkle tree, so as to greatly reduce witness data (witnesses) of stateless Ethereum clients.

(Figure: Vitalik Buterin, co-founder of Ethereum)

(Tip: There are many formulas in the article, and the translation is for reference only, and the original text shall prevail)

The following is the translation:

Regarding this research, I would like to thank many people for their help, especially (1) The AZTEC team introduced me to the copy constraint parameters, sorting parameters and effective batch scope proof methods; (2) The solutions provided by Datery Khovratovich and Justin Drake in the Kate Commitment Section, (3) Eli ben Sasson’s feedback on FRI, and (4) Justin Drake’s review work. This post is only the first attempt, and if there is further important thinking, I do hope that the program will be replaced by a similar but better one.

is too annoying to read the version summary:

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

What are polynomial commitments?

Polynomial promise is a kind of 'hash' of the polynomial P(x) that has properties that can perform arithmetic checks on the hash.

For example, on three polynomials P(x), Q(x), R(x), given the three polynomials promise 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 constructs 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 (called open proof opening proof or opening for short) for

You can use polynomial commitments as vector commitments, similar to Merkle tree. A major advantage of polynomial commitment is that it is much easier to generate complex proofs due to its mathematical structure. What are the popular polynomial commitment schemes for

?

currently has two front-runners, namely Kate Commitment (search for “Kate” in this post) and FRI-based Commitment. You may also have heard of Bulletproofs and DARKs algorithms, which are alternative polynomial commitment solutions. And to learn more about polynomial commitments, there are relevant content on YouTube (part 1, part 2, part 3, and slideshows). What are the easy scenarios for

polynomial commitments in Ethereum?

We can replace the Merkel root of the current block data with polynomial commitments (such as the sharded block of Ethereum 2.0) and replace the Merkle branches (Merkle branches) with open proof. This brings us two great advantages. First, data availability checking becomes easy and there is no fraud, as you can simply request open in a random way (such as 40 of the 2N coordinates of an N-order polynomial). Non-interactive hosting proofs may also be easier.

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

1. interpolation polynomials through interpolation of all these points I(x);
2. zero polynomials in x_1, ..., x_k equals 0 Z(x)=(x-x_1)*... *(x-x_k);
3. quotient polynomial Q(x) = (P(x)-I(x))/Z(x);

quotient polynomial Q(x) exists, meaning that 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, i.e. P(x_i) = y_i. Verifiers can generate interpolated polynomials and zero polynomials. Proof consists of a commitment to the quotient, plus the open proof on the random point z, so we can have a constant-sized witness content (witness) for any number of points.

technology can provide some benefits for multiple access to block data. However, for a different use case, the advantage exists is much greater: Proof of block transaction accounts witness. On average, each block will access hundreds of accounts and storage keys, which will result in a 0.5 MB size for the potential stateless client. Multi-witness, depending on the scheme, can reduce the size of block witness from tens of thousands of bytes to hundreds of bytes.

Then can we use polynomial commitments to store state?

Generally speaking, we can do it. Compared to storing the state as a Merkle tree, we choose to storing the state as two polynomials S_k(x) and S_v(x) , where S_k(1),..., S_k(N) represents the key (key), and S_v(1),.... , S_v(N) represents the values ​​on these keys (keys) (if the value is greater than the field size, it represents at least the hash of these values).

To prove that the key value pairs (k_1, v_1),..., (k_k, v_k) are part of the state, we will provide the index i_1, ..., i_k and (using the interpolation technique mentioned above) display the keys and values ​​that match the index, i.e. 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 certain keys, we can try to construct a strange proof that the key is not in S_k(1),…, S_k(N). Instead, we just sort the keys so that proving non-membership is enough to prove the membership of two adjacent keys, one smaller than the target key and one larger than the target key.

and this has similar benefits to Justin Drake's proposed use of SNARKs/STARKs to compress witness and related ideas. Another benefit of is that since the proof is native to accumulator cryptography rather than a proof built on accumulator cryptography, this eliminates an order of magnitude overhead and removes the need for zero-knowledge proof-friendly hash functions .

But there are two big problems here:

1. takes time to generate witness for k keys O(N), where N is the size of the state. It is expected that the status data corresponding to N will have about 50 GB, so it is not practical to generate such a proof in a single block;
2. 2, and the time spent updating S_k(x) and S_v(x) with k new values ​​also requires O(N). This is impractical in a single block, especially considering complexities such as witness updates and reordering.

Next we will introduce solutions to these two major problems.

Efficient reading

We provide two solutions, one designed for the Kate commitment and the other for the FRI-based commitment. Unfortunately, these schemes have different advantages and disadvantages, which lead to different attributes.

1, Kate promises

First, please note that for the N-order polynomial f, there is a scheme to generate N open proofs corresponding to each q_i(x) = (f(x) - f(i)) / (X - i) in O(N * log(N)) time.

Please also note that we can merge witness as follows. Consider the fact that q_i(x) is just a sub-constant term that leaves f(x)/(X-i). Generally, f/((X-x_1) * ... * (X-x_k)) is some linear combination of f/(X-x_1),...,f/(X-x_k) using partial fraction decomposition. Just 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 extraordinary terms, this is a system of k equations among k unknown numbers.

Given such a linear combination, what we get is just a sub-constant term for f/((x - x_1) * ... * (x - x_k)) (because all the original errors are sub-constant, 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)).

One possible challenge is that for large states, a single trusted setting that is actually computable (e.g., more than 100 independent participants, so the scheme is safe as long as any of them are honest) is not big enough: for example, the PLONK setting can only accommodate about 3.2 GB. Instead, we can have a state composed of multiple Kate commitments.

We make a single witness to many promises. To prove

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

To prove the evaluation on a set of points x_1, ..., x_k, we construct a k-order polynomial path (x), which evaluates at x_i as x_i **sqrt(N).

Then we create a polynomial h(t) = F(t, path(t)) which contains all expected evaluations for (x_i, y_i) and has k*(1+sqrt(N)) times.

We select random 30 columns c_1 ... c_k in the evaluation field, querying 30 random rows for each column. We promise to h (prove it is actually a polynomial with FRI), provide a multi-opening for z_i = h(c_i), and perform FRI random linear combination of column quotient (R_i - z_i)/(X - path(c_i)) to verify that the declared value of h(c_i) is correct, so h(t) is actually equal to F(t, path(t)). The reason why

uses a two-dimensional polynomial is that this ensures that we don't have to do any calculations for all F; instead, we just need to calculate the random 30 rows of F we selected (i.e. 30*sqrt(N)), plus h with order p*(sqrt(N) + 1), and the calculations made by creating the FRI are about p*sqrt(N) . This technique can be extended to polynomials above two-dimensional to lower the sqrt factor to a lower exponent.

Efficient writing

We solve the challenges related to updating a single commitment containing the entire state through a series of commitments. For larger commitments, the update frequency is lower: the

1. block itself has "read witness" (R_k(x), R_v(x)) and "write witness" (W_k(x), W_v(x)), indicating the value to be written to. 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 status S = (S_k(x), S_v(x)) contains values ​​that have been over 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 in turn. If the key is located at a certain C1_k(x), the corresponding value C1_v(x) stores the value. If the key is located at C2_k(x), then C2_v(x) stores the value, and so on, if the key is located at S_k(x), then S_v(x) stores the value. If none of these checks return the key, the value is 0. Introduction to the

copy constraint parameters

copy constraint parameters are a key component of the witness update proof we will use; see here for details on how the copy constraint parameters work. In short, the idea is to select a random r and generate an "accumulative" polynomial ACC(x) where ACC(0) = 1 and ACC(x+1) = ACC(x)*(r+P(x)) . You can read the point accumulator in the range of x .... y-1 by openly reading ACC(y)/ACC(x). You can use these accumulator values ​​to compare these evaluations with other evaluation sets (as multi-sets) without considering permutation.

You can also prove the equivalence of some random r and r2 by setting ACC(x+1) = ACC(x) * (r + P_1(x) + r2 * P_2(x)) to prove the equivalence of some random r and r2 (i.e. multi-set {(P_1(0), P_2(0)), (P_1(1), P_2(1)), ...}). Polynomial commitments can be effectively used to demonstrate claims about ACC.

To prove the subset, we can do the same thing, besides we also provide an index polynomial ind(x), prove that the ind(x) is equal to 0 or 1 in the entire range, and set ACC(x+1)=ACC(x)*(ind(x)*(r+P(x))+(1-ind(x))) (i.e. if the metric is 1, multiply by r+P(x) at each step, otherwise the accumulator value is not used).

summary:

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

In the following content, unless explicitly stated, we will lazily express it as "P is a permutation of Q", which means "P's evaluation between 0 and k is a permutation of appropriate k evaluation between 0 and k". Note that in the following, we will also involve the "size" of each witness to determine the coordinates in any C_k we accept, and the C_k(x) value outside the range is of course not counted.

Map merge argument (Map merge argument)

In order to update the cache, we use "map merge arguments". Given two maps A=(A_k(x), A_v(x)) and B=(B_k(x), B_v(x)) , generate merge map C=(C_k(x), C_v(x)) so that:

1. C_k is classified;
2. for 0
3. for 0

We use a series of replication constraint parameters to achieve this. First, we generate two auxiliary polynomials U(x), I(x), which represent the "union" and "intersection" of A_k and B_k, respectively.Consider A_k, B_k, C_k, U, I as a collection. We first need to show: