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

Concept:zk-stark vs zk-snark

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

Why not let us start with the name? After all, the two seemingly powerful sons ^_^!

As shown in the figure below, we divide the names zk-stark and zk-snark into four parts according to their functional characteristics, and then compare and analyze them one by one.

• Dialogue with Hong Ning: The areas where the blockchain is most likely to have a disruptive impact are banks and media.
• Popular science | Privacy protection is worrying? Encrypted data warehouses show their talents (core use cases and requirements analysis)
• Jianan will be listed, and these 20 A-share “mining concept stocks” will know in advance?

Zk-stark => zk – st ark

• Zk: Zero knowledge, indicating that privacy input will be hidden, except for the prover, no one else will see it;
• s: Scalable, compared with the time-consuming verification of Replay Computation, zk-stark's proof and verification time-consuming are respectively linear and logarithmic;
• t: transparent, zk-stark algorithm does not have CRS setup by Trusted party;
• Arg: knowledge argument, only know the provider of private input, can generate a valid proof;

Zk-snark => zk – sn ark

• Zk: Zero knowledge, indicating that privacy input will be hidden, except for the prover, no one else will see it;
• s: concise, meaning that the generated proof is small enough and the verification time is short enough;
• n: Non-interactive, Prover does not interact with verifier during proof generation;
• Arg: knowledge argument, only know the provider of private input, can generate a valid proof;

Compare

• Same point

1. Both achieve reliable hiding of privacy input;
2. It is based on knowledge argumentation, and it is not known that the provider of private input cannot generate a valid proof;
3. Both interactive and non-interactive algorithms can be implemented, depending on who generated the randomness;

• difference

1. Zk-stark is scalable, that is, the time-consuming and time-consuming calculations of the proof and verification are in a quasi-linear relationship (and the linear factor is constant) and the logarithmic relationship, which means that if the original input data set is increased 1000000 times, the proof of zk-stark takes time to increase the linear multiple, but the verification time only increases by 21*log1000000 =~ 420 times. Prove that the time-consuming linear relationship basically satisfies all ZKP algorithms, but the verification time is logarithmic, only this one, so in terms of scalability, zk-stark is superior.
2. Zk-stark is also simple, but it is simple to verify. The so-called simplicity, usually means that even if the verification program is large, the generated proof size will not be very large, and at the same time it can be verified quickly (much faster than native computation). Compared to zk-snark, zk-stark's proof size is much larger, so in terms of simplicity, zk-snark is better.

ALG compare

In the foregoing, the zk-stark and zk-snark algorithms are conceptually compared, and their similarities and differences can be summarized as follows:

• Both are based on the knowledge-based ZKP algorithm;
• Zk-stark does not require zk-snark's Trusted party to set CRS, so it is Transparent;
• The verification time consumption of zk-stark is logarithmically related to native computation, so it is Scalable;

Below, we will do a relatively more in-depth comparative analysis from the algorithm level:

• Zk-snark ALG [4]

1. The idea of ​​the algorithm: the problem of proving the CI statement is converted into the proof polynomial equation, and the conversion process uses the arithmetic loop and QAP method;
2. What does the polynomial equation mean? (yellow part in the picture)
   1. Both sides of the equation can be regarded as two polynomials with equal degrees. If it is assumed to be n, there are at most n intersections. If a point is randomly selected within a large domain, if the two polynomials have the same value 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 right overall polynomial, which is the zero point of the global polynomial on the left side of the equation, and the polynomial to the left of the equation is the value of these zero points. Converted into a single arithmetic circuit, the first-order linear constraint equation (R1CS) corresponding to each multiplication gate is established, that is, the original calculation equation is established (Note: R1CS is decomposed by the original calculation equation);
3. The algorithm is divided into three steps, CRS generation; proof of prover; verifier verification;
4. It can be seen that during the prover generation proof process, there is no interaction with the verifier, so it is non-interative;
5. How to ensure that A/B/C/H used by prover to generate proof is polynomial and is less than a certain degree?
   1. Guaranteed by the trusted party, because it is trusted, so it generates pk, the A/B/C used by vk is definitely a polynomial and is less than a certain degree;
   2. If the prover does evil, then the verifier will have a high probability of verifying failure;
   3. Mainly used the homomorphic encryption HH and coefficient knowledge hypothesis KCA and elliptic curve bilinear pairing and other mathematical knowledge;

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

1. Algorithm idea: the problem of proving the CI statement is transformed into a problem that the proof polynomial is less than a certain degree, and the polynomial interpolation method is used in the conversion process;
2. What does the polynomial equation mean? (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 public, and it is also the zero point of the polynomial Q on the left side of the equation. The value of polynomial Q at each zero point corresponds to the establishment of an execute trace (yes) In zk-stark, the original calculation statement is converted into multiple execute traces, which is similar to R1CS in zk-snark. Therefore, the polynomials are equal, meaning that the execute trace is correct, indicating that the original CI is true.
3. What does it mean to have a polynomial less than a certain degree?
   1. Similar to zk-snark, both convert the CI statement into a problem that proves that the polynomial equation is true (? It can be so abstracted that zk-stark not only proves that the polynomials are equal, but also proves that the corresponding polynomials are smaller than some Degree, this is the core of the zk-stark algorithm, so there is a description of the first point). In order to prevent the verifier from doing evil, it must be ensured that the polynomial is below a certain degree (? There is such a possibility that the attacker can deliberately generate some points that satisfy the verification equation, these points are not true polynomial points, but 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 equal in the true sense, indicating that the execute trace that generates the trajectory polynomial is correct, that is, the original CI is true.
4. The algorithm is divided into two major steps, arithmetic and low-level testing;
   1. Arithmetic: is to convert the problem into a polynomial form
   2. Low test: It is proved that the combined polynomial (yellow in the figure) and the trajectory polynomial (green in the figure) are smaller than a certain degree–>FRI algorithm
5. In the process of generating the proof, there is interaction (shown by the red line in the figure), so the interactive zero-knowledge proof algorithm is described in the figure;

Summary

The above is introduced from the concept and algorithm respectively. The similarities and differences between the zk-snark and zk-stark algorithms are used as citations. Subsequent publications will go into detail on the principle of the zk-stark algorithm. If there is an error, trouble criticism, thank you.

Appendix

1. V God trilogy, read with tears https://vitalik.ca/general/2017/11/09/starks_part_1.html
2. Zk -stark paper chrome-extension://cdonnmffkdaoajfknoeeecmchibpmkmg/assets/pdf/web/viewer.html?file=https%3A%2F%2Feprint.iacr.org%2F2018%2F046.pdf
3. Starkware official tutorial series https://medium.com/starkware/stark-math-the-journey-begins-51bd2b063c71
4. Zk -snark paper 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!