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, , or , 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. Fast RS IOPP Fast Reed—Solomon Interactive Oracle Proofs of Proximity There exists a multiplicative group of order on a Galois Field F. L_0 2^n At this point, the prover asserts that the codeword satisfies the coding parameter, that is, the majority of the points in lie on a polynomial of order ; here *)*; f_0: L_0−>F RS[F,L_0,ρ] f_0 P(x) ρ=2^(−R As a result, when , there exist polynomials whose order satisfy the relationship of and satisfy the following equation: f_0=P deg(P1,P2)<1/2∗ρ∗2^n f_0(x) = P(x) = P1(x^2) + x∗P2(x^2)(1) Set we can see the order of binary polynomial concerning for variable ; The order . of variable , and when , there is ; At this time, the verifier randomly selects a value x0x0 and sends it to the prover . The prover calculates and sets: Q(x, y)=P1(y)+x∗P2(y) d<2 Q(x, y) x d<1/2∗ρ∗2^n y y=x^2 Q(x, y)=f_0(x) V P P Q(x_0,y) f1(y)=Q(x_0, y)=P1(y)+x_0*P2(y)(2) For polynomial , since and has a value range of the Group , thus there is the equation , which can be further converted to . Therefore, if the value range of the independent variable y is defined as the Group , then should have the following properties: f1(y) y=x^2 x L_0 x^(2^n)=1 (x^2)^n=1 L1 L1 The order of the group is ; 2^(n−1) Each element of the Group L1 corresponds to two elements of the Group ; that is, for any element y of the Group L1, there are two elements x and (−x) in the Group , which satisfies ; L_0 mod p L_0 x^2 mod p = y&&(−x)^2 mod p = y So far, the issue is transformed into the one in which the prover shall prove whether the order of polynomial satisfies or not; at the same time, the consistency of function and shall be ensured. Specific steps are as follows: P f1(y) d<1/2∗ρ∗2^n f1 f0 The verifier selects three points from the Group and the Group to satisfy V y,s0,s1 L_1 L_0 s0!=s1&&s0^2 = s1^2 = y The prover returns three values of P f0(s0) , f0(s1) , f1(y). The verifier interpolates a polynomial of order according to . V g(x) d<2 f0(s0) , f0(s1) Verifier verifies , and if not equal, the verification fails. V g(s0)=f1(y) //2022-01-11 Error description was modified. g(x^0)=f1(y) if the function is not converted from the function according to the above process, then it is in large probability that the polynomial and of formula (1) and the polynomial and of formula (2) are not equal to each other. Considering that the order of the polynomial satisfies , and the value range of the variable is , the probability of equality of the polynomial is if a value is randomly selected within this range according to Schwartz Zippel theorem. ρρ represents coderates. If , then the probability of successful verification for just one time is merely . If it is verified for kk times, the probability of success in operating with bad manners is equal to With the increase of the value of kk, the probability is infinitely close to 0. Reliability analysis: f1 f0 P1(x2) P2(x2) P1(y) P2(y) d<1/2∗ρ∗2n 2(n−1) ( 1/2∗ρ∗2^n/2^(n−1))=ρ ρ=2^−8 2^−8 . 2^−8k Repeat the above process for the function until the polynomial becomes a form that can effectively judge the order, and the whole LDT process is completed. f1 fr 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: and . As can be seen from the previous simple scenario example, an interaction process requires: commit query The verifier sends the random number to the prover *;* V x0 P The prover generates a new polynomial P fi The verifier generates the point sets of queries and sends them to the prover V s0,i,s1,i,yi P The prover calculates the corresponding polynomial values of P , fi(yi) fi−1(s0,i), fi−1(s1,i) The verifier conducts a validity check. V Next, we’ll introduce the meaning of parameters and steps in and protocols and then summarize the relevant processes. Commit Query Commit: Common input : coding ratio parameter R : number of cycle times index i {: cycle times, value r (k0−R)/η : spatial mapping parameter η x=>x^2^η Order of L0:2^k0 : Encoding parameters [Galois Field, scope field, encoding ratio] RS[F,Li,ρ] Represent the mapping from the Group to the Group q0(x) = x^2^η, Li+1 = q0(Li), Li Li+1 Prover input represents the function input of the cycle by the time fi i represents the group corresponding to the cycle by the ii time, with the order of Li 2n−i : Coding parameters corresponding to RSi fi LOOP i ≤ r : The random number sent by the verifier xi V : Each element of the Group corresponding to the element set of the Group Sy Li+1 Li : Polynomial interpolated based on the value of on Py^i (X) fi(x) Sy : Indicating the consistency between polynomials : and . fi+1(y)==Py^i (xi) fi+1 fi i==r Generating polynomial fr Interpolate a polynomial Pr(x) Calculate the order of a polynomial Pr(x) Save coefficients of a polynomial a0,…,ad Pr(x) End of Commit stage i<r Generate according to the calculation method in step 2 fi+1 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) : query times, repeated multiple times to reach the required security level$ l Reconstruct fr Access oracle to obtain and reconstruct polynomial a0,…,ad Pr(x) Calculate all values of on the Group Lr and assign values to P^r(x) fr Repeat times l i = {0∼r−1} satisfies the set of in Si si si+1=q0(si) For example, starting from the Group , randomly select an element and calculate then is the element of the Group . However, there is also satisfying the above relationship on the Group , so there is ; Similarly, continue to repeat the above calculations with for times, and a series of sets of will be obtained. L0 s0 s1=q0(s0), s1 L1 −s0(assuming q0(x)=x2q0(x)=x2) L0 S0={s0,−s0} s1 r S0,S1,…,Sr−1 i={0∼r−1} On the set of obtained in step 1, respectively QUERY the value of polynomial S0,S1,…,Sr−1 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 in turn P0(x),P1(x),…,Pr−1(x) round consistency check i={0∼−1} Verify in sequence fi+1(si+1)=Pi(xi) If all verifications are successful, the verification passes. Next, set as an example to describe the two-stage process of FRI protocol, as shown in the following figure: η=1 (i.e. q0(x)=x2) 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 times, the probability of success of the people operating with bad manners can be greatly reduced. l 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: The algorithm is divided into two parts: Arithmeticalization and LDT Arithmeticalization converts the issue to polynomial equality and polynomial LDT issue. The FRI protocol is used in the LDT stage to ensure the complexity of linear proof and the complexity of logarithmic verification The zero-knowledge attribute ensures that the verifier cannot access the points in the trajectory polynomial and that the trajectory polynomial contains privacy values. 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. CRS is not required as a third party throughout the process. The entire process does not depend on any mathematical problems. Appendix Official Brief Introduction of FRI FRI Paper DEEP-FRI Paper Reed-Solomen WIKI

Oracle

Design Concept and Applications of Custom Gate: Sin7Y Tech Review (19)

Zero-Knowledge Proof Algorithm, PLONK—Protocol: Sin7Y Tech Review (17)

Nominated for 2022 - HackerNoon Contributor of the Year - Optimization

Nominated for 2022 - HackerNoon Contributor of the Year - Algorithms

Nominated for 2022 - HackerNoon Contributor of the Year - Privacy

Nominated for 2022 - HackerNoon Contributor of the Year - Architecture

Nominated for 2022 - HackerNoon Contributor of the Year - Blockchain

Too Long; Didn't Read

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

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

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

A Study on Parallel Execution: Everything You Need to Know

(1/100) Crypto Countdown: Golem

A Research Report on the Trader $JOE DeFi Platform

07/03/2018: Biggest Stories in the Cryptosphere

05/02/2018: Biggest Stories in the Cryptosphere

01/06/2018: Biggest Stories in the Cryptosphere

A Study on Parallel Execution: Everything You Need to Know

(1/100) Crypto Countdown: Golem

A Research Report on the Trader $JOE DeFi Platform

07/03/2018: Biggest Stories in the Cryptosphere

05/02/2018: Biggest Stories in the Cryptosphere

01/06/2018: Biggest Stories in the Cryptosphere

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps