Technical Guide | Understanding Zk-stark for Zero Knowledge Proof Algorithms

Concept: zk-stark vs zk-snark

When it comes to the ZKP algorithm, everyone may have heard of some, such as zk-snark, zk-stark, bulletproof, aztec, plonk, and so on. Today, let's talk to everyone about the similarities and differences between the "surface brothers", zk-stark and zk-snark algorithms.

Why not start with the name? After all, both Yazi look great ^ _ ^!

As shown in the following figure, we divided the names zk-stark and zk-snark into four parts according to their functional characteristics, and then compared and analyzed them one by one.

• Popular science | Worry about privacy protection? Encrypted data warehouse shows its strength (core use cases and requirements analysis)
• Understanding Zk-stark of Zero Knowledge Proof Algorithm-Arithmetization
• Smart Contract Entry Series | Important Links in Smart Contract Engineering: Formal Verification Methods

Zk-stark => zk-st ark

• zk: Zero-knowledge, indicating that the privacy input will be hidden, and no one will see it except the prover;
• s: Scalable, compared with the verification time of Replay Computation, zk-stark's proof and verification time have a quasi-linear relationship and a logarithmic relationship, respectively;
• t: transparent, zk-stark algorithm has no CRS setup by Trusted party;
• arg: knowledge demonstration, only if you know the private input prover can you generate an effective proof;

Zk-snark => zk-sn ark

• zk: Zero-knowledge, indicating that the privacy input will be hidden, and no one will see it except the prover;
• s: Concise, which means that the generated proof is small enough and the verification time is short enough;
• n: non-interactive, there is no interaction with verifier during the process of Prover generating the certificate;
• arg: knowledge demonstration, only if you know the private input prover can you generate an effective proof;

Compare

• Same point

1. All achieve the reliable hiding of privacy input;
2. All are based on knowledge demonstration. I don't know if the private input prover cannot generate effective proof;
3. Both interactive and non-interactive algorithms can be implemented, but it depends on who generates randomness;

• difference

1. zk-stark is scalable, that is, the time spent for certification and verification is in a quasi-linear relationship (and the linear factor is constant) and logarithmic in the original calculation time, which means that if the original input data set increases 1000000 times, zk-stark's proof takes a linear multiple of time, but the verification time only increases 21 * log1000000 = ~ 420 times. It is proved that the linear relationship of time consumption basically meets all the ZKP algorithms, but the verification time has a logarithmic relationship. This is the only one. Therefore, zk-stark is superior in scalability.
2. zk-stark is also concise, but it is verification simplicity. The so-called conciseness usually means that even if the verification procedure is large, the generated proof size will not be very large, and the verification can be completed quickly (much faster than native computation). Compared to zk-snark, the proof size of zk-stark is much larger, so in terms of simplicity, zk-snark is better.

ALG compare

The zk-stark and zk-snark algorithms were compared conceptually. The similarities and differences can be summarized as follows:

• ZKP algorithms based on knowledge demonstration;
• zk-stark does not require zk-snark's Trusted party to set CRS, so it is Transparent;
• The verification time of zk-stark is logarithmic to the time of native computation, so it is Scalable;

Below, we will do a relatively deeper comparative analysis from the algorithm level:

• zk-snark ALG [4]

1. Algorithm idea: The problem of proving the establishment of a CI statement is turned into a problem of proving the establishment of a polynomial equation, and the conversion process uses an arithmetic loop and a QAP method;
2. What does the polynomial equation hold? (Yellow part in the picture)
   1. The two sides of the equation can be regarded as two polynomials of equal degree. Assume that n has at most n intersections. If a point is randomly selected in a large range, if the two polynomials have equal values ​​at this point, Then prove that the two polynomials are equal.
   2. We can see that the polynomial factor Z on the right side of the equation is the target polynomial. Its zero point is the zero point of the global polynomial on the right side, which is the zero point of the global polynomial on the left side of the equation. The first-order linear constraint equation (R1CS) corresponding to each multiplication gate in the arithmetic circuits is established, that is, the original calculation equation is established (Note: R1CS is decomposed from the original calculation equation);
3. The algorithm is divided into three steps, CRS generation; prover proof; verifier verification;
4. It can be seen that during the proof generation process of the prover, there is no interaction with the verifier, so it is non-interative;
5. How to ensure that the A / B / C / H used by the prover to generate the proof is polynomial and less than a certain degree?
   1. Guaranteed by a trusted party, because it is trustworthy, so the A / B / C, etc. it uses to generate pk, vk must be polynomial and less than a certain degree;
   2. If the prover does evil, the verifier will have a high probability of failing the verification;
   3. Mainly used mathematical knowledge such as homomorphic encryption HH and coefficient knowledge hypothesis KCA and elliptic curve bilinear pairing;

• zk-stark ALG [1] [2] [3]

1. Algorithmic idea: The problem of proving the establishment of a CI statement is transformed into a problem that proves that the polynomial is less than a certain degree, and the conversion process uses a polynomial interpolation method;
2. What does the polynomial equation hold? (Yellow part in the picture)
   1. The idea is the same as zk-snark. T is also the target polynomial. Its zero point is known and open. It is also the zero point of the polynomial Q on the left side of the equation. The value of each zero point of the polynomial Q corresponds to the establishment of an execute trace. In zk-stark, the original calculation statement is transformed into multiple execute traces, which is similar to R1CS in zk-snark). Therefore, the polynomials are equal, which means that the execute trace is correct, indicating that the original CI is true.
3. What does it mean for a polynomial to be less than a certain degree?
   1. Similar to zk-snark, both convert the CI statement into a problem that proves that the polynomial equation holds (? It can be so abstracted that zk-stark must not only prove that the polynomials are equal, but also prove that the corresponding polynomial is less than a certain This is the core of the zk-stark algorithm, so we have the first point). In order to prevent the verifier from doing evil, it is necessary to ensure that the polynomial is below a certain degree. (There is a possibility that the attacker can deliberately generate some points that satisfy the verification equation. These points are not points on the true polynomial, but The evidence generated from these points can also be verified by the verifier). The difference is that zk-snark uses mathematical methods such as trusted party mechanism and homomorphic encryption, while zk-stark uses mathematical methods such as low-level testing. If and only if the polynomial is really less than a certain degree, the equality of the polynomials is truly equal, which means that the execute trace of the generated polynomial is correct, that is, the original CI is true.
4. The algorithm is divided into two major steps, arithmeticization and low-level testing;
   1. Arithmetic: is to convert the problem into polynomial form
   2. Low degree test: It is proved that the combination polynomial (yellow in the figure) and trajectory polynomial (green in the figure) are less than a certain degree-> FRI algorithm
5. In the process of generating a proof, there is interaction (shown in red in the figure), so the figure describes an interactive zero-knowledge proof algorithm;

Summary

The above has introduced the similarities and differences between the zk-snark and zk-stark algorithms from the concept and algorithm perspectives. As a citation, subsequent articles will detail the principles of the zk-stark algorithm. If there are errors, please criticize and correct me, thank you.

Appendix

1. V Trilogy, read with tears https://vitalik.ca/general/2017/11/09/starks_part_1.html
2. zk-stark paperchrome-extension: //cdonnmffkdaoajfknoeeecmchibpmkmg/assets/pdf/web/viewer.html? file = https% 3A% 2F% 2Feprint.iacr.org% 2F2018% 2F046.pdf
3. starkware official explanation series https://medium.com/starkware/stark-math-the-journey-begins-51bd2b063c71
4. zk-snark thesis chrome-extension: //cdonnmffkdaoajfknoeeecmchibpmkmg/assets/pdf/web/viewer.html? file = https% 3A% 2F% 2Feprint.iacr.org% 2F2013% 2F879.pdf

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