Sin7Y Tech Review (18): 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->\mathbf{F}$ satisfies the
  $RS[F,L_0,\rho ]$ coding parameter, that is, the majority of the points in
  $f_0$ lie on a polynomial
  $P(x)$ of order ; here
  $\rho =2^{(-R)}$;

As a result, when

$f_0=P$, there exist polynomials

$\mathrm{deg}(P_1,P_2)<1/2\ast \rho \ast 2^n$ whose order satisfy the relationship of and satisfy the following equation:

$f_0(x)=P(x)=P_1\left(x^2\right)+x\ast P_2\left(x^2\right)(1)$

Set

$Q(x,y)=P_1(y)+x\ast P_2(y)$ we can see the order

$d<2$ of binary polynomial

$Q(x,y)$ concerning for variable

$x$; The order

$d<1/2\ast \rho \ast 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

$x_0$ and sends it to the prover

$P$. The prover

$P$ calculates

$Q(x_0,y)$ and sets:

$f_1(y)=Q(x_0,y)=P_1(y)+x_0\ast P_2(y)(2)$

For polynomial

$f_1(y)$, since

$y=x^2$ and

$x$ has a value range of the Group

${\mathbf{L}}_0$, thus there is the equation

$x^{\left(2^n\right)}=1$, which can be further converted to

${\left(x^2\right)}^n=1$. Therefore, if the value range of the independent variable

$y$ is defined as the Group

$L_1$, then

$L_1$ should have the following properties:

• The order of the group is
  $2^{(n-1)}$;
• Each element of the Group
  $L_1$ corresponds to two elements of the Group
  $L_0$; that is, for any element
  $y$ of the Group
  $L_1$, there are two elements
  $x$ and
  $(-x)modp$ in the Group
  $L_0$, which satisfies
  $x^{2}modp=y\mathrm{\&}\mathrm{\&}(-x{)}^{2}modp=y_{;}$

So far, the issue is transformed into the one in which the prover

$P$ shall prove whether the order of polynomial

$f_1(y)$ satisfies

$d<1/2\ast \rho \ast 2^n$ or not; at the same time, the consistency of function

$f_1$ and

$f_0$ shall be ensured. Specific steps are as follows:

• The verifier
  $V$ selects three points
  $y,s_0,s_1$ from the Group
  $L_1$ and the Group
  $L_0$ to satisfy
  $s0!=s1\mathrm{\&}\mathrm{\&}{s}_0^2=s_1^2=y$
• The prover
  $P$ returns three values of
  $f_0\left(s_0\right),f_0\left(s_1\right),f_1(y)$.
• The verifier
  $V$ interpolates a polynomial
  $g(x)$ of order
  $d<2$ according to
  $f_0\left(s_0\right),f_0\left(s_1\right)$.
• Verifier
  $V$ verifies
  $g\left(s_0\right)=f_1(y)$, and if not equal, the verification fails.
• //2022-01-11 Error description
  $g\left(x^0\right)=f_1(y)$ was modified.

Reliability analysis: if the function

$f_1$ is not converted from the function

$f_0$ according to the above process, then it is in large probability that the polynomial

$P_1\left(x^2\right)$ and

$P_2\left(x^2\right)$ of formula (1) and the polynomial

$P_1(y)$ and

$P_2(y)$ of formula (2) are not equal to each other. Considering that the order of the polynomial satisfies

$d<1/2\ast \rho \ast 2^n$, and the value range of the variable is

$2^{(n-1)}$, the probability of equality of the polynomial is

$\frac{1/2\ast \rho \ast 2^n}{2^{(n-1)}}=\rho$ if a value is randomly selected within this range according to Schwartz Zippel theorem.

$\rho$ represents coderates. If

$\rho =2^{-8}$, then the probability of successful verification for just one time is merely

$2^{-8}$. If it is verified for

$\mathrm{k}$ times, the probability of success in operating with bad manners is equal to

$2^{-8\mathrm{k}}$. With the increase of the value of

$k$, the probability is infinitely close to 0 .

Repeat the above process for the function

$f_1$ until the polynomial

$f_r$ 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
   $x_0$ to the prover
   $P$;
2. The prover
   $P$ generates a new polynomial
   $f_i$
3. The verifier
   $V$ generates the point sets
   $s_{0,i},s_{1,i},y_i$ of queries and sends them to the prover
   $P$
4. The prover
   $P$ calculates the corresponding polynomial values of
   $f_i\left(y_i\right),f_{i-1}\left(s_{0,i}\right),f_{i-1}\left(s_{1,i}\right)$
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
  $\frac{k_0-R}{\eta }$
• $\eta$ : spatial mapping parameter
  $x=>x^{2^{\eta }}$
• Order of
  ${\mathrm{L}}_0:2^{k_0}$
• $RS[F,L_i,\rho ]$ : Encoding parameters [Galois Field, scope field, encoding ratio]
• $q_0(x)=x^{2^{\eta }},L_{i+1}=q_0\left(L_i\right),$ Represent the mapping from the Group
  $L_i$ to the Group
  $L_{i+1}$

Prover input

• $f_i$ represents the function input of the cycle by the
  $i$ time
• $L_i$ represents the group corresponding to the cycle by the
  $i$ time, with the order of
  $2^{n-i}$
• $R{S}_i$ : Coding parameters corresponding to
  $f_i$

LOOP

$i\le r$

• $x_i$ : The random number sent by the verifier
  $V$

• $S_y$ : Each element of the Group
  $L_{i+1}$ corresponding to the element set of the Group
  $L_i$
• $P_y^i(X)$ : Polynomial interpolated based on the value of
  $f_i(x)$ on
  $S_y$
• $f_{i+1}(y)==P_y^i\left(x_i\right):$ Indicating the consistency between polynomials
  $f_{i+1}$ : and
  $f_i$.

3. $i==r$

• Generating polynomial
  $f_r$
• Interpolate a polynomial
  $P^r(x)$
• Calculate the order of a polynomial
  $P^r(x)$
• Save coefficients
  $a_0,\dots ,a_d$ of a polynomial
  $P^r(x)$
• End of Commit stage

4. $\mathrm{i}<\mathrm{r}$

• Generate
  $f_{i+1}$ according to the calculation method in step 2
• Calculating commitment to polynomials
  $f_{i+1}$
• Update relevant parameters and enter the next cycle

$Query$:

Verifier input

• See Commit for
  $R/\eta /L_i/R{S}_i/x_i/f_i/P(x)$
• $l:$ query times, repeated multiple times to reach the required security level$

Reconstruct

$f_r$

• Access oracle to obtain
  $a_0,\dots ,a_d$, and reconstruct polynomial
  $P^r(x)$
• Calculate all values of
  $P^r(x)$ on the Group
  $L_r$ and assign values to
  $f_r$

Repeat

$l$ times

• $\mathrm{i}=\{0\sim \mathrm{r}-1\}$

$S_i$ satisfies the set of

$s_i$ in

$s_{i+1}=q_0\left(s_i\right)$

For example, starting from the Group

$L_0$, randomly select an element

$s_0$ and calculate

$s_1=q_0\left(s_0\right)$, then

$s_1$ is the element of the Group

$L_1$. However, there is also

$-s_0$ (assuming

$q_0(x)=x^2$ ) satisfying the above relationship on the Group

$L_0$, so there is

$S_0=\{s_0,-s_0\}$; Similarly, continue to repeat the above calculations with

$s_1$ for

$\mathrm{r}$ times, and a series of sets of

$S_0,S_1,\dots ,S_{r-1}$ will be obtained.

• $\mathrm{i}=\{0\sim \mathrm{r}-1\}$

On the set of

$S_0,S_1,\dots ,S_{r-1}$ obtained in step 1, respectively QUERY the value of polynomial

$f_i$

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

$P_0(x),P_1(x),\dots ,P_{r-1}(x)$ in turn

• round consistency check
  $\mathrm{i}=\{0\sim -1\}$

Verify

$f_{i+1}\left(s_{i+1}\right)=P_i\left(x_i\right)$ in sequence

• If all verifications are successful, the verification passes.

Next, set

$\eta =1$ (i.e.

$q_0(x)=x^2$ ) as an example to describe the two-stage process of FRI protocol, as shown in the following figure:

$d<\rho \ast 2^n$

As can be seen from the above process:

• For the consistency check of each round, it is ensured that the original polynomial
  $f_0$ does satisfy the order
  $d<\rho \ast 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