Written in front: In order to cope with the state explosion of Ethereum, Ethereum cofounder 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 cofounder Vitalik Buterin)
 Let the transaction speed reach 1 million TPS in the future, and the Ethereum expansion solution officially released
 Market Analysis: Doomsday ETC is soaring, the market is still far away
 Market analysis: funds are afraid of the situation, no trend opportunities
 Ethereum “Lego” mode: talk about interoperability and composability in Ethereum
 BTC shortterm trend is weak, is it a dishwashing or a downward trend?
 Analysis: Ethereum, the largest "air coin" in the industry?
(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:
 If
P(x) + Q(x) = R(x)
, you can generate a proof that proves its relationship withh_P, h_Q, h_R
(in some constructions, you can simply checkh_P + h_Q = h_R）
;  If
P(x) * Q(x) = R(x)
, you can generate a proof to prove its relationship withh_P, h_Q, h_R
;  If
P(z) = a
, you can produce a proof forh_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 Ndegree polynomial). Noninteractive 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:
 An interpolation polynomial
I(x)
through all these points;  At
x_1，...，x_k
equal to zero zero polynomialZ（x）=（xx_1）* ... *（xx_k）
;  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 multiwitness. 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 keyvalue 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 nonmembership 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 nonmembership 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 zeroknowledge prooffriendly hash function .
But there are two big problems here:
 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. The time it takes to update
S_k(x)
andS_v(x)
with k new values also requiresO（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 FRIbased commitments. Unfortunately, these schemes have different advantages and disadvantages, which can lead to different properties.
1.Kate promises
First, please note that for Ndegree 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 subconstant term leaving f（x）/（Xi）
, usually, f/((X  x_1) * ... * (X  x_k))
is a linear combination of f /（Xx_1），...，f /（Xx_k）
f/((X  x_1) * ... * (X  x_k))
, f /（Xx_1），...，f /（Xx_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_{k1})
, where there are no nonconstant terms, which are k unknowns K equations in.
Given such a linear combination, what we get is just a subconstant term leaving f/((x  x_1) * ... * (x  x_k))
(since all original errors are subconstants, so The combination of linear errors must be subconstant), 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.FRIbased commitments
We store the state in the evaluation of a twodimensional 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 kdegree 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 multiopening 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 twodimensional 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:
 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 setW_k = R_k
and calculateW_v
at runtime.  The first cache
C1 =（C1_k（x），C1_v（x））
stores the updated content of the last day;  The second cache C2 is equal to the last C1 of the previous day;
 Full state
S = （S_k（x），S_v（x））
contains values longer than 12 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 .... y1
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））+（1ind（x）））
(ie, if the index is 1, then multiply by r + P（x）
at each step, otherwise No accumulator value is used).
summary:
 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);
 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);
 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 :
 The keys in
C_k
are classified;  For 0 <= i <size (B), (B_k (i), B_v (i)) is in C;
 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:

(U, U_v)
at0...size(B)
is equal to(B_k, B_v)
at0...size(B)
(B_k, B_v)
; 
(U, U_v)
atsize(B) ... size(A)+size(B)
a(U, U_v)
of（A_k，A_v）
at0...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.
 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);  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 someonegenerated 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
 Submit FRI certification, requiring less than 900 queries (more formally, security parameters are less than square);
 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 keyvalue mapping instead of a vector?