# Sin7Y Tech Review (16): Zero-Knowledge Proof Algorithm：PLONK ---Circuit
![](https://i.imgur.com/CBZnsdU.jpg)
We recently investigated the Zero-Knowledge proof algorithm-PLONK and would like to share our learning experience.
## Status quo
In recent years, various new Zero-Knowledge proof algorithms have emerged one after another, each with its unique characteristics and advantages. The following figure from [Vitalik’s article](https://vitalik.ca/general/2019/09/22/plonk.html) illustrates the current status of the Zero-Knowledge proof algorithm.
![](https://i.imgur.com/H6dqidf.png)
*Figure 1 ZKP Algorithm*
The figure presents three key points:
1. Theoretically, the safest algorithm is STARKs, which does not rely on the assumption of mathematical problems and is quantum-resistant.
2. SNARKs is of the smallest Proof size, such as Groth16.
3. PLONK is designed between the two items above regarding security and Proof size.
One outstanding issue of SNARKs is the centralized Trust Setup, also known as the Common Reference String (CRS). Whether PGHR13, Groth16, or GM17 algorithm, their CRS are for one-time use and non-updateable. Different problems will correspond to different CRS, becoming more problematic in some scenarios. In contrast, PLONK and SONIC have competitive advantages in response to these problems. Although they also require centralized Trust Setup, their CRS has a certain degree of universality. As long as the size of the circuit does not exceed the upper threshold of the CRS, some proof problems can share a CRS, which is called the Universal Structured Reference String (SRS). For the definition of SRS, please refer to section 3 in the SONIC protocol.
PLONK adopts the SRS concept of SONIC but dramatically improves the efficiency of the proof. Next, we will elaborate PLONK in the following four sections:
1. Circuit design----circuit description of PLONK
2. Permutation argument or permutation verification----use copy constraints to prove the consistency between the gates in the circuit
3. Polynomial commitment----prove the validity of polynomial equation effectively
4. PLONK protocol analysis
## Circuit
PLONK and SONIC share the same circuit description. In short, we would like to share two inputs:
1. Regardless of the circuit description, a circuit is satisfied by two points: the validity of the constraint relationship within the gate and among the gates.
2. In SNARKs, a circuit is composed of effective wires. In PLONK, SONIC, and HALO, a circuit is formed of gates.
The different description methods of these two circuits have provided some reflection. When we studied SNARKs previously, we all believed in the fact that "the validity of polynomial equations proves that the constraint of each gate is valid" and then inferred that the entire circuit logic is valid. In this process, we did not prove the validity of the consistency between the gates. But in PLONK, in addition to the verification of the polynomial equation, a mathematical method of permutation argument is adopted to verify the constraint relationship between the gates, that is, the copy constraint. Why is there such a difference? Feel free to discuss it in the comment section if interested. Our understanding is that the difference results from different circuit descriptions:
1. In PLONK, the gate is the unit circuit description that defines its own L, R, and O for each gate. Therefore, it’s necessary to prove the consistency between the gates.
2. In SNARKs, the wire is the unit description that the values between the wires share the same witness. Therefore, there’s no need to prove consistency.
## Permutation argument
As mentioned in PLONK, it is necessary to prove the validity of the constraint relationship between the gates. Before explaining the specific principles, we will go over the process of the PLONK protocol, shown in the following figure.
![](https://i.imgur.com/OImdB5W.jpg)
*Figure 2 PLONK Protocol*
The figure displays three points briefly:
1. Generate three polynomials based on the circuit, which represents the left input, right input, and output of this circuit, respectively.
2. Use the permutation verification protocol to prove the validity of the copy constraint relationship.
3. Steps 3 and Step 4 verify the validity of the constraint relationship within the gate.
The first point has already been explained in the circuit section. Next, we will analyze the principles of the polynomial permutation verification process. We will start with a simple scenario:
### （1）Permutation verification of one polynomial
It is to prove that there are two different points for a specific polynomial f, x and y, where f(x) = f(y). We will examine the particular principles.
![](https://i.imgur.com/RVrLttH.jpg)
*Figure 3 Permutation Check-1*
In the above figure, example P and counterexample A have been provided to help understand the principle of permutation verification. There are a few points that need to be addressed:
1. After a thorough analysis of Z, it is not difficult to find that Z(n+1) is the ratio between the cumulative multiplication product value of the two functions (We wonder if it is equivalent to the coordinate pair accumulator in Vitalik’s article). In theory, it is equal to 1. Therefore, we need to come up with a polynomial Z, which satisfies:
1. deg(Z) < n
2. Z(n+1) = 1
2. The multiplicative cyclic group can satisfy this condition. If we design a multiplicative cyclic group H with an order of n, Z(g)=Z(g^(n+1)) can be known based on the properties of the group. Therefore, when designing Z, we will ensure that Z(g) = 1. The value of the independent variable in the above figure will also change from {1...n} to {g...g^n}. So, in the verification part of the figure above, a has been replaced with all the components in group H.
3. According to the protocol in the paper, the polynomial Z will be sent to a trusted third party I. The verifier V will obtain all the values of the polynomial Z at each a from I and then check respectively.
Let's examine the definition in the paper:
![](https://i.imgur.com/M0A6gvw.png)
Based on the definition: polynomials f and g share the same set of values in response to the range of [n]. We will go through the specific part of the protocol combined with the three points explained above.
![](https://i.imgur.com/UmBWcBY.jpg)
*Figure 4*
Note: the f and g in Figure 4 correspond to the f in Figure 3. In other words, f and g are the same polynomials. As long as it is a set of the same value, it may not be the same polynomial. Figure 3 is just a particular case.
### （2）Permutation verification across polynomials
It is to prove that for specific polynomials f, g, there are two points x, y where f(x) = g(y). There are two distinctions compared to (1):
1. There are multiple polynomials.
2. The relationship between x and y is not compulsory; it can be equal or not.
With the foundation of section (1), we will first look at the related definitions:
![](https://i.imgur.com/KUAFwUL.jpg)
Based on the definition, it is the permutation verification between two polynomials. It can be seen from the underlined part:
1. The two sets of polynomials still have the same values.
2. To distinguish the polynomials in the set, the index of the independent variable must be distinguished.
Therefore, if there are two polynomials f and g, and you want to prove f(x) = g(y), according to the above description, you can deduct {f1,f2} = {f,g} = {g1, g2}, which also ensures the validity of the first point above.
Let's examine the specific principles:
![](https://i.imgur.com/zuhXuXJ.jpg)
Compared with section (1), the workload of prover P has been increased while the workload of verifier V remains the same. According to the above description, the mathematical principles can also be easily understood.
Note: In fact, we have gradually stepped into the core part of the PLONK algorithm. As we mentioned earlier, the satisfiability of the circuit is not only the constraint relationship within the gate but also the constraint relationship between the gates.
For example, an input x is both a left input of a multiplication gate and a right input of another multiplication gate. Therefore, it is necessary to prove L(m)=R(n), which is called the permutation verification across polynomials.
The figure below presents the protocol details in the paper:
![](https://i.imgur.com/XcWlfER.jpg)
## Conclusion
This article has discussed two critical topics of PLONK, the circuit design and the verification process of the copy constraint. We will analyze the validity of the gate constraint and details of the protocol in the following article.

TL;DR We are working on building the first ZKVM based on a parallel execution architecture and achieving higher TPS through the improvement of ZK-friendly design and ZK algorithms. The technical features are as follows: Fast proof generation ZK-friendly: smaller circuit scale and simplified bottom constraint units Fast ZK: further optimization on Plonky2 Fast execution: Utilizing parallel execution to significantly shorten the proof generation time

11/14/2022ZKEVM is a programmable virtual machine based on ZK technology. It can generate a ZK proof for all operations perfwormed by the virtual machine to prove the correctness of the operations performed by the virtual machine. For the introduction of several implementation schemes of ZKEVM and the comparison of advantages and disadvantages, you can refer to the article of Vitalik Buterin: The different types of ZK-EVMs. If you want more design details, you can also read PSE's ZKEVM Scheme (native-level)： privacy-scaling-explorations/zkevm-specs Polygon's ZKEVM Design (bytecode-level)： Polygon zkEVM Documentation. Sin7y’s ZKEVM Design (language-level)：OlaVM: An Ethereum compatible ZKVM. Regardless of the scheme, zk is required to constrain all VM behaviors, including: Executing contract computational logic Executing memory access Executing hash calculation Executing world state updates It is well known that ZK has great application prospect in the field of computing compression. No matter how complex the original computation is, the verification process is very efficient, which is fundamental to all zk algorithms. Therefore, ZK works well for computational parts of VM execution (such as contract logic, hash calculation, etc.). In the process of VM execution, in addition to the computing itself, there are also some memory access operations. We need to place some data in the memory in advance, and then pull it out when the computation is performed.

9/9/2022References Zcash - Zcash protocol specification Aleo - Zexe protocol specification Zcash 1. About Zcash ? A short video to learn about Zcash. Features:

9/2/2022Last month we were pleased to announce the OlaVM Whitepaper, an EVM-compatible ZKVM solution, released the 25th of July, 2022. ZKEVM has been a hot topic itself over the past couple of weeks, and upon the release of OlaVM, the paper managed to receive some honorable attention from prominent people in the industry, amongst them, one being Daira Hopwood (who also is the main author of the Zcash protocol), we would like to thank Daira for her feedback. Daira brought up a few important questions in regards to the design decisions, one of them relating to the choice of hash function in ECDSA and Schnorr signature algorithms. The exact comment can be seen in the tweet attached below. What Daira is referencing can in simple terms be described with the following: The security level of Sinsemilla hash is collision resistant, so it cannot be regarded as a Random Oracle. For the ECDSA and Schnorr signature algorithms, in order to satisfy sufficient security, the choice of hash function needs to be regarded as Random Oracle. In order to understand this better, we need to understand some cryptographic concepts first. 1. Security properties of a cryptographic hash function (CHF) According to the definition in the paper Cryptographic Hash-Function Basics, the security properties corresponding to a CHF are divided into the following three categories: Preimage Resistance - Given H(x), it is computationally difficult to determine x, i.e., it is computationally infeasible to discover any input which created a specific output. Second Preimage Resistance - Given x, it is computationally difficult to find some different value x' such that H(x) == H(x'), i.e., it is computationally infeasible to find any second input which has the same output as any specified input. Collision Resistance - Expanding the concept of Second Preimage Resistance, it is computationally infeasible to find any two arbitrary inputs, x and y such that H(x) == H(y), i.e., different inputs which hash to the same output.

8/5/2022
Published on ** HackMD**