Zero-Knowledge Proof Algorithm: ZK-Stark-FRI Protocol

Preface

Finally, we reach the conclusion of the series “Understanding the value of a zero-knowledge proof algorithm - Zk-stark”. We discussed the overall structure of the Zk-stark algorithm, the first part of the algorithm, Arithmetization, and the second part of the algorithm, Low Degree Testing, in the previous three articles. I believe that after reading these articles, you will have a general understanding of the outline of the Zk-stark algorithm. However, you may question the accuracy of some sentences or illustrations in the article. Indeed, a more specific introduction and explanation are required for certain contents. Otherwise, misunderstandings may occur.

In the third article, we have discussed the importance of conducting LDT on polynomials to ensure that the values returned by the prover satisfy the equality of polynomial equations are indeed calculated using effective polynomials. In the meantime, to minimize the complexity of the verifier, we have transformed the original polynomial and thus the polynomial to be verified by the verifier is only half the original polynomial. Repeat until the degree of the polynomial can be determined directly. This is the fundamental concept of the FRI protocol. Now, let us go over the FRI protocol in detail.

FRI Protocol

FRI, Fast RS IOPP, or Fast Reed—Solomon Interactive Oracle Proofs of Proximity, is a more effective proximity test method that is used to determine whether a set of points is mostly on a polynomial with a degree less than a specified value and can achieve linear proof complexity and logarithmic verification complexity or not. Before we introduce the FRI protocol in its entirety, let us consider a simple scenario.

There exists a multiplicative group L_0 of order 2^n on a Galois Field F.

• At this point, the prover asserts that the codeword f_0: L_0−>F satisfies the RS[F,L_0,ρ] coding parameter, that is, the majority of the points in f_0 lie on a polynomial P(x) of order ; here ρ=2^(−R*)*;

As a result, when f_0=P, there exist polynomials deg(P1,P2)<1/2∗ρ∗2^n whose order satisfy the relationship of and satisfy the following equation:

f_0(x) = P(x) = P1(x^2) + x∗P2(x^2)(1)

Set Q(x, y)=P1(y)+x∗P2(y) we can see the order d<2 of binary polynomial Q(x, y) concerning for variable x; The order d<1/2∗ρ∗2^n. of variable y, and when y=x^2, there is Q(x, y)=f_0(x); At this time, the verifier V randomly selects a value x0x0 and sends it to the prover P. The prover P calculates Q(x_0,y) and sets:

f1(y)=Q(x_0, y)=P1(y)+x_0*P2(y)(2)

For polynomial f1(y), since y=x^2 and x has a value range of the Group L_0, thus there is the equation x^(2^n)=1, which can be further converted to (x^2)^n=1. Therefore, if the value range of the independent variable y is defined as the Group L1, then L1 should have the following properties:

• The order of the group is 2^(n−1);
• Each element of the Group L1 corresponds to two elements of the Group L_0; that is, for any element y of the Group L1, there are two elements x and (−x) mod p in the Group L_0, which satisfies x^2 mod p = y&&(−x)^2 mod p = y;

So far, the issue is transformed into the one in which the prover P shall prove whether the order of polynomial f1(y) satisfies d<1/2∗ρ∗2^n or not; at the same time, the consistency of function f1 and f0 shall be ensured. Specific steps are as follows:

• The verifier V selects three points y,s0,s1 from the Group L_1 and the Group L_0 to satisfy s0!=s1&&s0^2 = s1^2 = y
• The prover P returns three values of f0(s0) , f0(s1) , f1(y).
• The verifier V interpolates a polynomial g(x) of order d<2 according to f0(s0) , f0(s1).
• Verifier V verifies g(s0)=f1(y), and if not equal, the verification fails.
• //2022-01-11 Error description g(x^0)=f1(y) was modified.

Reliability analysis: if the function f1 is not converted from the function f0 according to the above process, then it is in large probability that the polynomial P1(x2) and P2(x2) of formula (1) and the polynomial P1(y) and P2(y) of formula (2) are not equal to each other. Considering that the order of the polynomial satisfies d<1/2∗ρ∗2n, and the value range of the variable is 2(n−1), the probability of equality of the polynomial is (1/2∗ρ∗2^n/2^(n−1))=ρ if a value is randomly selected within this range according to Schwartz Zippel theorem. ρρ represents coderates. If ρ=2^−8, then the probability of successful verification for just one time is merely 2^−8. If it is verified for kk times, the probability of success in operating with bad manners is equal to 2^−8k. With the increase of the value of kk, the probability is infinitely close to 0.

Repeat the above process for the function f1 until the polynomial fr becomes a form that can effectively judge the order, and the whole LDT process is completed.

Next, let’s take a look at the specific contents of the FRI protocol, as shown in Figure 1:

FRI protocol is divided into two stages: commit and query. As can be seen from the previous simple scenario example, an interaction process requires:

1. The verifier V sends the random number x0 to the prover P*;*
2. The prover P generates a new polynomial fi
3. The verifier V generates the point sets s0,i,s1,i,yi of queries and sends them to the prover P
4. The prover P calculates the corresponding polynomial values of fi(yi) , fi−1(s0,i), fi−1(s1,i)
5. The verifier V conducts a validity check.

Next, we’ll introduce the meaning of parameters and steps in Commit and Query protocols and then summarize the relevant processes.

Commit:

Common input

• R : coding ratio parameter
• i : number of cycle times index
• r{: cycle times, value (k0−R)/η
• η : spatial mapping parameter x=>x^2^η
• Order of L0:2^k0
• RS[F,Li,ρ] : Encoding parameters [Galois Field, scope field, encoding ratio]
• q0(x) = x^2^η, Li+1 = q0(Li), Represent the mapping from the Group Li to the Group Li+1

Prover input

• fi represents the function input of the cycle by the i time
• Li represents the group corresponding to the cycle by the ii time, with the order of 2n−i
• RSi : Coding parameters corresponding to fi

LOOP i ≤ r

• xi : The random number sent by the verifier V

• Sy : Each element of the Group Li+1 corresponding to the element set of the Group Li
• Py^i (X) : Polynomial interpolated based on the value of fi(x) on Sy
• fi+1(y)==Py^i (xi): Indicating the consistency between polynomials fi+1: and fi.

3. i==r

• Generating polynomial fr
• Interpolate a polynomial Pr(x)
• Calculate the order of a polynomial Pr(x)
• Save coefficients a0,…,ad of a polynomial Pr(x)
• End of Commit stage

4. i<r

• Generate fi+1 according to the calculation method in step 2
• Calculating commitment to polynomials fi+1
• Update relevant parameters and enter the next cycle

Query:

Verifier input

• See Commit for R/η/Li/RSi/xi/fi/P(x)
• l: query times, repeated multiple times to reach the required security level$

Reconstruct fr

• Access oracle to obtain a0,…,ad and reconstruct polynomial Pr(x)
• Calculate all values of P^r(x) on the Group Lr and assign values to fr

Repeat l times

• i = {0∼r−1}

Si satisfies the set of si in si+1=q0(si)

For example, starting from the Group L0, randomly select an element s0 and calculate s1=q0(s0), then s1 is the element of the Group L1. However, there is also −s0(assuming q0(x)=x2q0(x)=x2) satisfying the above relationship on the Group L0, so there is S0={s0,−s0}; Similarly, continue to repeat the above calculations with s1 for r times, and a series of sets of S0,S1,…,Sr−1 will be obtained.

• i={0∼r−1}

On the set of S0,S1,…,Sr−1 obtained in step 1, respectively QUERY the value of polynomial fi

Verify that the returned value is consistent with the corresponding polynomial commitment (if the commitment in the COMMIT stage is the merkle-based hash calculation, then here multiple hash calculations are required to obtain the root)

Interpolate P0(x),P1(x),…,Pr−1(x) in turn

• round consistency check i={0∼−1}

Verify fi+1(si+1)=Pi(xi) in sequence

• If all verifications are successful, the verification passes.

Next, set η=1 (i.e. q0(x)=x2) as an example to describe the two-stage process of FRI protocol, as shown in the following figure: d<ρ∗2^n

As can be seen from the above process:

• For the consistency check of each round, it is ensured that the original polynomial f0 does satisfy the order d<ρ∗2^n .
• If the above protocol is repeated for l times, the probability of success of the people operating with bad manners can be greatly reduced.

Summary

The process described above is the FRI protocol. As can be seen, the complexity of the verification satisfies the logarithmic relationship . The algorithm ensures that the round consistency verifications can be passed if and only if the initial polynomial satisfies . The actual implementation may vary slightly. For more information, please refer to the DEEP-FRI paper. In comparison to FRI, DEEP-FRI increases the system’s reliability while maintaining an optimal level of proof and verification complexity.

Based on the previous three articles in this series, the Zk-STARK algorithm can be summarized as follows:

1. The algorithm is divided into two parts: Arithmeticalization and LDT
2. Arithmeticalization converts the issue to polynomial equality and polynomial LDT issue.
3. The FRI protocol is used in the LDT stage to ensure the complexity of linear proof and the complexity of logarithmic verification
4. The zero-knowledge attribute ensures that the verifier cannot access the points in the trajectory polynomial and that the trajectory polynomial contains privacy values.
5. Simultaneously, to ensure the zero-knowledge attribute, random values for rows must be added to the trajectory polynomial, which is determined by the verifier and prover after negotiation.
6. CRS is not required as a third party throughout the process.
7. The entire process does not depend on any mathematical problems.

Appendix

1. Official Brief Introduction of FRI
2. FRI Paper
3. DEEP-FRI Paper
4. Reed-Solomen WIKI