Zero-Knowledge Proof Algorithm, PLONK—Protocol: Sin7Y Tech Review (17)

Note:

• PLONK’s new paper has been published. The highest order in the common input has been changed from n+2 to n+5 because when calculating t(x), the highest order can reach (3n+5=3(n+1)+n+2-n).
• The reason for increasing the binding of a(x), b(x), c(x), z(x) has been explained in KZG10. When the number of open points is greater than the order of the polynomial, it will expose the polynomial. The order of these polynomials, which are interpolated by witnesses, cannot be guaranteed to be large enough.
• The new paper has optimized the calculation process of the polynomial commitment CreateWitness (divided into a constant part and other parts), thereby simplifying the verification process.

The previous paper PLONK-Circuit investigates a critical part of the PLONK protocol----using the permutation check to prove the consistency among the circuit gates. In this report, Sin7Y will analyze the details of the protocol and elaborate on how the constraint relationship of the gate is valid.

Gate constraint

For example, if there is a circuit with only three multiplication gates, the corresponding constraints are:

L1 * R1 - O1 = 0
L2 * R2 - O2 = 0
L3 * R3 - O3 = 0

Compress the polynomial: define polynomial functions L(X), R(X), O(X) satisfying:

L(1) = L1, R(1) = R1, O(1) = O1
L(2) = L2, R(2) = R2, O(2) = O2
L(3) = L3, R(3) = R3, O(3) = O3

Then, define a new polynomial function F(X),and let F(X) = L(X) * R(X)-O(X)

Then:

F(1) = L(1) * R(1) - O(1) = 0
F(2) = L(2) * R(2) - O(2) = 0
F(3) = L(3) * R(3) - O(3) = 0

If the polynomial function F(X) has zeros at X=1,2,3, then the constraint relationship of the gates is valid.

If the polynomial function F(X) has zeros at X=1,2,3, then the polynomial F(X) can be divisible by (X-1)(X-2)(X-3). To be consistent with the paper, we set this polynomial function as Z(X):

F(X) = T(X) * Z(X) ==> T(X) = F(X) / Z(X)

If we can prove T(X) is a polynomial, then polynomials F(X) and Z(X) share the same zeros. Therefore, the constraint relationship of the gate is valid.

Here is the process:

1. P computes F(X) and sends F(X) to V;
2. V directly verifies F(X) / Z(X) based on Z(X).

However, there are two issues in this process. One is complexity. If the order of F(X) is n, then the communication complexity is O(n). The other is the security issue. The polynomial F(X) will be completely exposed to V.

How to solve these two problems? The best answer might be polynomial commitment.

Polynomial Commitment

What is the polynomial commitment? That is, the prover P uses a short string of data to represent a polynomial F. These short strings of data can be used by the verifier V to verify that the value of the polynomial F at a certain point is indeed the value z claimed by the prover P.

Let’s examine the definition in the paper:

Elaborate the definition:

1. Setup: initialize and generate some necessary parameters required to compute the polynomial commitment.
2. Commit: compute the polynomial commitment, and the result is a value.
3. Open: return to the polynomial function corresponding to the polynomial commitment.
4. VerifyPoly: verify whether the polynomial commitment is consistent with the polynomial function.
5. CreateWitness: verify whether the value of the polynomial function at a certain point is the value claimed by the prover P. The mathematical method is to confirm whether the polynomial is divisible.
6. VerifyEval: the verifier V verifies whether the value of the polynomial function at a certain point is the value claimed by the prover P. The mathematical method uses bilinear pairing to prove its mathematical multiplication logical relationship.

Back to our question above:

To prove T(X) = F(X) / Z(X), let Z(X) = X-1. Then:

T(X) = F(X) / (X - 1) ==> T(X) * (X - 1) = F(X) ==> T(X) * X = F(X) + T(X)

Based on the polynomial commitment protocol, the prover P wants to prove that the value of the polynomial function F(X)=0 when X=1. Therefore, the verifier V only needs to prove that:

e(Commit(T(x)), x*G) =？ e(Commit(F(x)) +Commit (T(x)), G) (the nature of bilinear pairing)

In summary, the polynomial commitment can achieve complexity optimization and privacy protection.

Protocol

Next, we will analyze the details of the PLONK protocol.

Relation

Figure 2 illustrates the proof relation in the PLONK algorithm. To elaborate:

1. w represents the input and output in the circuit, with a total of 3n. n is the number of multiplication gates in the circuit, and each gate has a left input, right input, and output, so there are 3n w in total.
2. q* represents the selection vector, and its value corresponds to a multiplication gate, an addition gate, or other similar constraints.
3. σ represents the permutation polynomial and refers to the consistency constraint index among the gates.
4. The last formula represents the constraint relationship among the gates is valid.
5. The penultimate formula represents the constraint relationship of the gate is valid.

CRS &P_Input&V_Input

Figure 3 displays the CRS settings in the PLONK algorithm and the inputs by the prover P and the verifier V. To clarify:

1. The entire protocol is dependent on polynomials, so it’s necessary to construct the respective polynomial form.
2. The order of the polynomial σ is 3n. Since the highest order of CRS related to the polynomial commitment is n+2, it is necessary to split σ into three polynomials S and record each polynomial’s permutation relationship (L, R, O).
3. To reduce communication complexity and protect privacy, the protocol is constructed based on polynomial commitments, so the input of the verifier V is the commitment value.

Prove

Figure 4 displays the operations of the prover in the PLONK algorithm. To clarify:

1. b1,…b9 are random numbers for security purposes.
2. a(X), b(X), c(X) respectively represent the left input, right input, and output in the circuit.
3. [a],[b],[c] represent the commitment value of the polynomial. Refer to the commitment computing method in the polynomial commitment section.

Figure 5 displays the operations of the prover in the PLONK algorithm, mainly permutation check. Refer to the permutation verification process to generate polynomial z(X) in the previous article PLONK-Circuit. To clarify:

1. Both β and ϒ are used to generate the parameters of the permutation verification function. Please refer f(x) and g(x) in the previous article.
2. The generation method of z(X) corresponds to the generation process of cross-polynomials in permutation check. Li(X) is a Lagrange polynomial satisfying that when x=i, it is 1 and 0 for others.
3. Distinguish between ω and w. ω is the generator of the group H and the value of the independent polynomial variable. w is the left input, right input, and output of the circuit, and is the value of the polynomial L, R, O corresponding to group H.

Figure 6 presents the operations of the prover P in the PLONK algorithm, mainly the combination of the constraint relationship of the gate and the constraint relationship among the gates through α. To elaborate:

1. As mentioned above, the values of the gate-constrained polynomial and the consistency-constrained polynomial corresponding to all elements in group H are all 0, by which the polynomial ZH(X) is divisible. This is equivalent to the T(X) mentioned above.
2. Therefore, if the prover can prove that the result of the division is indeed a polynomial, it can prove the values of the gate-constrained polynomial and the consistency-constrained polynomial corresponding to all elements in group H are all 0. All the constraint relationships are valid, which means the circuit logic is valid.
3. The order of t(X) is up to 3n. Still, the CRS used to compute the commitment only reaches the level of n, so it is necessary to split the polynomial t(X) and then calculate the commitment value separately.

Figure 7 displays the operations of the prover P in the PLONK algorithm. Previously P computed the value of multiple polynomials when x=z based on the polynomial commitment protocol. We need to prove this computing is correct utilizing the polynomial commitment protocol. To clarify:

1. In order to reduce the operational complexity of the verifier V, the value of the numerator r(X) of t(X) at x=z should be computed by P, and then the verifier directly verifies it. Other operations are similar.
2. The value of v ensures more security.
3. Based on the CreateWitness operation in the polynomial protocol, Wz(X) needs to prove that when x=z, the values of these polynomials r(X), a(X), b(X), etc. are equal to r, a, b, etc. respectively. The same logic applies to Wzw(X) and returns the commitment value.

Verify

Prover P has completed all the operations. The following operations are performed by the verifier V.

Figure 8 shows the operations of the verifier V in the PLONK algorithm, mainly generating the relevant parameters to ensure the operations by the prover P. To clarify:

1. From the input perspective, they are public inputs and proof outputs by the prover P, which are relatively straightforward.

2. According to the input, some parameters are required to establish the permutation verification process.

   
   

Figure 9 displays the operations of the verifier V in the PLONK algorithm. For less complex polynomials, it’s more convenient to compute the value at x=z directly. To clarify:

1. According to the process of the prover P, the main job of the verifier V is to verify two polynomial commitments.
2. The verification of two polynomial commitments requires two pairs. Each pair can be done by a parameter, namely μ.
3. Before the verification, compute the value of the denominator of Wz(x) and Wzw(x) at x=z. The subtrahend and the minuend correspond to [F] and [E], respectively. μ, as a coefficient, corresponds to polynomial Wzw(X).
4. Lastly, complete the verification of the two polynomial commitments through a bilinear pairing operation.

Conclusion

We have analyzed all the protocol principles of the PLONK algorithm. If you have any questions or would like to share your thoughts, please contact us directly through Telegram.