Zero-Knowledge Proof Algorithm, PLONK —Circuit: Sin7Y Tech Review (16)

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 illustrates the current status of the Zero-Knowledge proof 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.

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.

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:

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.

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:

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:

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:

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.