**Launch your smart contract idea in just 4 days**

5,511 reads

by Sin7YFebruary 21st, 2022

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, *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

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

As a result, when * f_0=P*, there exist polynomials

**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

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

For polynomial * f1(y)*, since

- 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)**L_0**in the Group**mod p**, which satisfies**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 * P* shall prove whether the order of polynomial

- The verifier
selects three points**V**from the Group**y,s0,s1**and the Group**L_1**to satisfy**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**V**of order**g(x)**according to**d<2**.**f0(s0) , f0(s1)** - Verifier
verifies**V**, and if not equal, the verification fails.**g(s0)=f1(y)** - //2022-01-11 Error description
was modified.**g(x^0)=f1(y)**

**Reliability analysis:** if the function * f1* is not converted from the function

Repeat the above process for the function * f1* until the polynomial

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

- The verifier
sends the random number**V**to the prover**x0***;***P** - The prover
generates a new polynomial**P****fi** - The verifier
generates the point sets**V**of queries and sends them to the prover**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 * Commit* and

**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**q0(x) = x^2^η, Li+1 = q0(Li),**to the Group**Li****Li+1**

**Prover input**

represents the function input of the cycle by the**fi**time**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**Sy**corresponding to the element set of the Group**Li+1****Li**: Polynomial interpolated based on the value of**Py^i (X)**on**fi(x)****Sy**: Indicating the consistency between polynomials**fi+1(y)==Py^i (xi)**: and**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)** **l**: query times, repeated multiple times to reach the required security level$

**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 l times**

**i = {0∼r−1}**

* Si* satisfies the set of

For example, starting from the Group * L0*, randomly select an element

**i={0∼r−1}**

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

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:

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.

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.

L O A D I N G

. . . comments & more!

. . . comments & more!