Introduction to Technology | Deep Understanding of Zk-stark of Zero Knowledge Proof Algorithm——FRI Protocol

Foreword

Finally, the end of the "Understanding Zero Knowledge Proof Algorithm Value Zk-stark" series. In the previous three articles, we introduced the overall structure of the zk-stark algorithm ( https://www.8btc.com/article/512859 ), and the first part of the algorithm: Arithmetization ( https: //www.8btc. com / article / 516674 ), the second part of the algorithm: Low Degree Testing ( https://www.8btc.com/article/522057 ). I believe that after reading these articles, everyone can have a general understanding of the outline of the zk-stark algorithm; in the process of reading, you may question the correctness of some sentences or pictures in the article (it is true that some The content needs more specific introduction and explanation, otherwise there will be misunderstanding), welcome to email 163 email exchange (oceanjune512).

Looking back at the third article, we have said that in order to ensure that the value returned by the prover that satisfies the polynomial equality is indeed calculated based on valid polynomials, we need to perform an LDT test on the polynomials; at the same time, in order to make the verifier complex To achieve the optimal, we transform the original polynomial. After the transformation, the polynomial to be proved by the prover is only half of the original polynomial. This process is repeated continuously until the degree of the polynomial can be directly judged. This is actually the core idea of ​​the FRI protocol. Below, let us introduce the process of the FRI protocol in detail.

FRI agreement

Maybe we should first talk about what the FRI agreement is? FRI, Fast RS IOPP, full name Fast Reed-Solomen Interactive Oracle Proofs of Proximity, is a more effective proximiary test method. Most of the test points are set on a polynomial with a degree less than a certain value, which can be linear Level of proof complexity and logarithmic level of verification complexity. Before we formally introduce the FRI protocol, let's look at a simple scenario.

• On the finite field F, there is a multiplicative group L0, the order of the group is 2 ^ n;
• At this time, the prover claims that the codeword f0: L0-> F is a codeword that satisfies the encoding parameters of RS [F, L0, ρ], that is, a polynomial with most points of f0 at a degree d <ρ * 2 ^ n On P (x), where ρ = 2 ^ (-R);

Therefore, when f0 = P, according to the IFFT principle, there are P1 and P2 and deg (P1, P2) <1/2 * ρ * 2 ^ n, which satisfies:

• Babbitt Original | Mainstream exchanges support Lightning Network, what does this have to do with ordinary users?
• Babbitt Column | Ethereum developers arrested, showing that the carrier that disrupts U.S. financial hegemony may be the public chain
• Suggested that the SEC "cut off" IPO underwriters, the NYSE also played IEO?

f0 (x) = P (x) = P1 (x ^ 2) + x * P2 (x ^ 2) (1)

Let Q (x, y) = P1 (y) + x * P2 (y). It can be seen that the degree of Q (x, y) with respect to x d <2; the degree of d with respect to d <1/2 * ρ * 2 ^ n; at this time, the verifier randomly selects a value x0 and sends it to the prover, and then

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

For f1 (y), y = x ^ 2, because the value range of x is the element in group 1, so x ^ (2 ^ n) = 1 ==> (x ^ 2) (2 ^ (n-1) ) = 1 ==> y (2 ^ (n-1)) = 1. Let the scope of y be group L1, then L1 has the following properties:

• The order of the group is 2 ^ (n-1);
• Each element of group L1 corresponds to two elements of group L0, that is, any y of group L1. Group L0 has two x and (-x) mod F, satisfying x ^ 2 mod F = y && (-x) ^ 2mod F = y;

Therefore, the problem is transformed to prove that the degree d <1/2 * ρ * 2 ^ n of f1 (y). It is also necessary to ensure the consistency of the functions f1 and f0. The process can be divided into the following steps:

• The verifier selects three points y from group L1 and group L0, s0, s1 satisfying s0! = S1 && s0 ^ 2 = s1 ^ 2 = y
• The prover returns three values ​​of f0 (s0), f0 (s1), and f1 (y)
• The verifier interpolates a polynomial g (x) of d <2 about x according to f0 (s0), f0 (s1)
• The verifier verifies that g (s0) = f1 (y), if not equal, it fails

Reliability analysis: If the function f1 is not converted from the function f0, then the polynomials P1 (x ^ 2) and P2 (x ^ 2) of formula (1) and the polynomials P1 (y) and P2 (y of formula (2) ) Are not equal to each other. Considering the degree of the polynomial d <1/2 * ρ * 2 ^ n, the value range of the variable is 2 ^ (n-1), then a value is randomly selected within this range, and the probability of the polynomial being equal is 1/2 * ρ * 2 ^ n / 2 ^ (n-1) = ρ. ρ is coderates. If ρ = 2 ^ (-8), then the probability of a successful check is only 1/256. If it has been verified many times, the probability of successful evil will be close to zero wirelessly.

It can be known from the foregoing that the above process is repeated for the function f1 until fr becomes a degree that can be directly verified, and the entire test verification process is completed.

Below, we look at the specific content of the FRI protocol, as shown in Figure 1:

The FRI protocol is divided into two phases: the Commit phase and the Query phase. As can be seen from the previous simple scenario, a simple loop requires

1. Verifier sends random number x0
2. The post prover generates a new function f1,
3. Perform consistency check.

The FRI protocol classifies the first two steps of each cycle into the Commit phase and the third step into the Query phase. That is, in the Commit phase, all functions f0 ~ fr are generated, and r is the number of loops, and then in the Query phase, unified verification is performed.

The following first introduces the meaning of each parameter and each step in the Commit and Query protocols, and then summarizes the relevant processes.

Commit:

• Common input
  • R RS coding ratio
  • i loop number index, value {0 ~ r}
  • r Cycle number k0-R / η
  • η space mapping parameter x-> x ^ (2 ^ η)
  • Order 2 ^ k0 of the L0 group
  • RS [F, Li, ρ] encoding parameters [finite field, scope, encoding ratio]
  • q0 (x) = x ^ (2 ^ η) (the definition of the actual implementation is not consistent with the figure), L (i + 1) = q0 (Li), which represents 2 ^ from group Li to group L (i + 1) η-> 1 mapping
• Prover input
  • function input for fi i th cycle
  • Group of the i th cycle, order 2 ^ (ni)
  • RSi fi corresponding encoding parameters
• LOOP i <= r
  • 1
    • xi Random number sent by validator
  • 2
    • Each element of the Sy group L (i + 1) corresponds to the set of elements of the group Li
    • f (i + 1) (y) computes all values ​​of f (i + 1) on group L (i + 1)
  • 3 i == r
    • Define the output of fr step 2
    • Interpolate out P (x)
    • d is the degree of the polynomial P (x)
    • Save the coefficients a0 ~ ad of d + 1 polynomials P (x)
    • Commit phase terminated
  • 4 i <r
    • Define f (i + 1) as calculated in step 2
    • Save the value of f (i + 1) in group L (i + 1)
    • Go to the next cycle

Query

• verifier input
  • R / η / Li / RSi / xi / fi / P (x) See Commit
  • l query times
• Refactoring fr
  • Get a0 ~ ad and reconstruct P` (x)
  • Calculate all values ​​of P` (x) on group Lr and assign it to fr. Note that fr satisfies RSr
• repeat l times
  • i = {0 ~ r-1}
    • Set of x such that Si satisfies s (i + 1) = q0 (x)
  • i = {0 ~ r-1}
    • On Si, interpolate Pi (x)
  • round consistency check i = {0 ~ r-1}
    • f (i + 1) (s (i + 1)) = Pi (xi)
  • If both are successful, the verification is passed

Below, taking η = 1 (that is, q0 (x) = x ^ 2) as an example, the two-phase process of the FRI protocol is shown in Figure 2:

It can be seen from the above process:

• The consistency check for each round ensures that the original polynomial f0 does satisfy d <ρ * 2 ^ n
• The above protocol is repeated l times, which can greatly reduce the probability of success of the perpetrator.

to sum up

The above is the specific process of the FRI protocol. It can be seen that the verification complexity satisfies the logarithmic relationship r = Log2 (ρ * 2 ^ n). The algorithm guarantees that all round consistency checks will pass if and only if the original polynomial f0 is less than ρ * 2 ^ n. The actual implementation may be slightly different. For details, refer to the DEEP-FRI paper. Compared to FRI, DEEP-FRI improves the reliability of the system while maintaining the optimal complexity of proof and verification.

Combining the first three articles in this series, the ZK-STARK algorithm is summarized as follows:

1. The algorithm is divided into two parts: arithmeticization and LDT
2. Arithmetically transforms the problem into bit polynomial equality and polynomial LDT problems
3. The LDT phase uses the FRI protocol to ensure the proof complexity of the linear level and the verification complexity of the logarithmic level.
4. The zero-knowledge attribute guarantees that the verifier cannot access the points in the trajectory polynomial, and the trajectory polynomial holds the privacy value
5. At the same time, in order to ensure the zero-knowledge attribute, it is necessary to add a few rows of random values ​​to the trajectory polynomial, which is determined by the verifier and the prover through negotiation.
6. The entire process does not require a third party CRS
7. The entire process does not rely on any mathematical problems

appendix

1. Brief introduction of official FRI https://medium.com/starkware/low-degree-testing-f7614f5172db
2. FRI paper https://eccc.weizmann.ac.il/report/2017/134/
3. DEEP-FRI paper chrome-extension: //cdonnmffkdaoajfknoeeecmchibpmkmg/assets/pdf/web/viewer.html? File = https% 3A% 2F% 2Farxiv.org% 2Fpdf% 2F1903.12243.pdf
4. Reed-Solomen WIKI https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction

We will continue to update Blocking; if you have any questions or suggestions, please contact us!