ZKP— PlonK Algorithm Introduction

PlonK is the acronym forPermutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge. PlonK ia an implementation of the Universal Zero-Knowledge proof algorithm. Universal means that the trusted setup only needs to be initiated once. For folks familiar with Groth16, you must already know that every circuit in Groth16 needs a separate Trusted Setup.

You can access the paper for PlonK here:

https://eprint.iacr.org/2019/953.pdf

This paper about Plonk has clear technical logic explained in 8 chapters. My recommendation on the reading order: chapter1 (overview). chapter 5 (circuit design), chapter 2/3/4 (background theory), chapter 6/7/8 (constraint system and agreement). I highly recommend you to take a look at the paper.

This article talks about principle of Plonk algorithm and the proof process of the agreement Proof/Verify phase.

Initial Parameters SRS

Polynomial Commitment

Single-Polynomial Commitment

Step 1: generate SRS. Assume the highest order of the polynomial is d. Take a random value x, generate SRS, corresponds to the points on two elliptic curves of each term in the polynomial.

Step 2: generate commitment for a polynomial. With SRS, multiplied by the coefficient of the polynomial, then eventually we get the commitment of the polynomial.

Step 3: Verifier sends gamma to the certifier. The certifier constructs h polynomial, and comes up with the associated point value for the SRS related to the polynomia. Verifier then validates if the value of polynomials is equal to the commitment value:

{cmi} — commitment of a polynomial, {zi} — polynomial value (multiple polynomial with the same value), {si} — polynomial result. Vpc is the verifier. Ppc is the certifier. Vpc chooses a random number and sends it to Ppc. Ppc calculates h(X), gets the point W on elliptic curve and sends to Vpc. Vpc calculates F, through pairing verify if the paired function has equal value and commitment. After you understand the calculation of paired function, the credibility and completeness proof becomes rather straight forward. Feel free to check out the paper if you are interested.

Look closely at the F calculation of Vpc — it is simply calculating the last commitment and polynomial. Public information is the polynomial commitment and the polynomial “unfolded” at certain point. Certifier gets to know about the knowledge of polynomial through calculating h(X). That is to say, with trusted SRS, certifier does not leak any specific information regarding the polynomial, and the verifier can consolidate that value of certain polynomial can be trusted.

Multi-Polynomial Commitment

The principle is pretty straight forward: (cm-si) + z*(cm-si)/(x-z) = x/(s-z)*(cm-si).

Polynomial Permutation

Li(X)

With Li(X), we can set the check of equal polynomials to a range check.

Li(a)(Z(a) — Z*(a)) = 0. This is true for all elements in H, if and only if Li(a)=Z*(g^i). If a belongs to g^i, Li(a)=1, then Z(g^i) must be equal to Z*(g^i). If a doesn’t belong to g^i, Li(a) =0, the equation is proven true.

ID and Permutation

Permutation protocol

Permutation of a polynomial value’s correspondence.

The protocol could also have two different cases: 1/ permutation on input of the same polynomial 2/ permutation on inputs of multiple polynomials. These two cases are differentiated by number of polynomials in need of permutation.

Permutation protocol of single polynomial:

f’ and g’ are new functions, which accumulates the input and out value of function f and g. It uses beta and gamma random factors in order to prevent information leak of f function. Here we need to understand the Z function: Z function is the multiplication function of f’/g’(b), and Z(g)=1 (a). Through simple deduction we can get Z(g^n) = 1, if only permutate the input information.

According to the above definition of Z function, we can know that Z(g^n) = 1. This is to say, f/g function permutates following the agreement.

Permutation agreement of multiple polynomials:

Point marking can extend to multiple polynomials. In another word, input information of multiple polynomials are indexed consecutively.

Based on the agreement of single polynomial, we multiply the polynomials, then calculate the function Z. In short, we can make sure of the polynomial permutation by verifying two polynomials. The permutation agreement is also the basis of “copy constraint” which will come later.

Fiat-Shamir Heuristic Algorithm

https://en.wikipedia.org/wiki/Fiat–Shamir_heuristic

Interactive Type:

Non-interactive Type:

PlonK uses the interactive type algorithm.

Circuit Principle and Constraint System

https://vitalik.ca/general/2019/09/22/plonk.html

The so called constraint system is just the constraint rules of circuits. Each gate in the circuit represents a constraint. The paper has given a circuit with 2 inputs and unlimited output. Assume one circuit contains n gates and m wiresm where n<=m<=2n. The constraint system has two parts: 1/ input information of each gate 2/ coefficient vector of the gate constraint.

V is made up by left input a, right input b, and output c vectors. Note that a/b/c are just indexes. qL, qR, qO, qM, qC is selection operator vector of gates. L stands for left. R is right. O is output, M is multiplication, C is constant.

The entire circuit satisfies the above equation. That is to say, each constraint represents one addition and one multiplication. Based on this definition, the paper has given three ways to represent a specific circuit: 1/ arithmetic circuit (addition and multiplication) 2/ boolean value only 3/ public input value only. Public input only can be interpreted as fixing the input to a public value.

In conclusion, PlonK constraint system in nutshell:

fL/fR/fO are left/right/output function. This constraint system has 2 constraint logics:

1/ copy contraint — gate and wires shared by gates are correct

2/ each gate constraint is valid

Here I have a few clarification on the logic. For a circuit with 2 inputs, unlimited output, if it has n gates, then there exist at most 2n inputs, for which we write as m. Each gate has left, right input and output. We mark them with ai, bi and ci, where 0<=i<=n. i is the index of gate, and ai is the index for an input or output inX. Xai is the value for that input or output. With permutation, we swap the i. In short, when we calculate the function of a certain input or output value, the function value will be the same at two different points. This limits input/output of one gate to connect with another gate’s input/output. PLONK has less representation forms in circuit — each gate only has one addition/multiplication in PLONK. R1CS supports accumulate and multiplication.

PlonK protocol

Public Information

Proving Process:

Round 1:

Calculate a(X), b(X), c(X) in their polynomial form, and the ellipse point of corresponding SRS. a/b/c corresponds to fL/fR/fO in the agreement.

Round 2:

Generate random number with Fiat-Shamir heuristic algorithm, and calculate the z(X) polynomial and the ellipse point of corresponding SRS.

Round 3:

Generate random number with Fiat-Shamir heuristic algorithm, and calculate the t(X) polynomial and the ellipse point of corresponding SRS.

Note that t(X) is the core, and merged 3 polynomial into equations:

1/ the first equation puts constraint on gate circuit

2/ the second and third equation satisfies “copy contraint“ and the link between gates meets the equation

Round 4:

Round 1 to 3 are calculating polynomial commitment. Start from round 4 we are calculating the ellipse point of certain points.

Generate random number with Fiat-Shamir heuristic algorithm. Calculate a/b/c/t/z and the value of its corresponding permutation function value.

Define and calculate r function and its value. Note that r function is related to t function, and we will talk about this relationship in the verification process.

Round 5:

Generate random number with Fiat-Shamir heuristic algorithm. Calculate the proof of multi-polynomial commitment. The proof polynomial has two types: 1/ a/b/c/t/r and the permutation function 2/ z function.

Verification Process:

We start from step 12. The whole verification process only needs to verify a multi-polynomial commitment. The core calculation is F — E. F is the value of multiple polynomial commitment. E is the value of multiple polynomial challeges. Multi-polynomial commitment garantees challenge value is equal to commitment value. D in F calculation process is formed by r and z functions.

How to constrain?

  1. a/b/c 2. r 3. z 4. t 5. Permutation function

Take a close look at calculation of D (including the r function in proof). We can find that D is not provided by the certifier. That is also to say, r function commitment value is not provided in the proving process. Verifier calculates the D commitment value by himself, therefore limit the polynomial expression of D.

After defining polynomial expression of D, we have also indirectly defined r function expression.

From the calculation in step 8, the formula of t function challege value is given. Because now we have r function expression, we can also get t function expression. Then we have a closer look at t function expression in the proving process. Since t function can be divided by ZH function, the value will be 0 at the roots. This also proves that 3 polynomials of the circuit are equal.

Performance Comparison

Performance

Assume there are n multiplication gates, and the number of addition gate is equal to multiplication gate (a=n). Number of wire (m) is twice total number of gates (m=4n). The G2 calculation is three times of G1. Then:

1/ PlonK SRS size is 1/4 of Groth16.

2/ Amount of calculation for PlonK proof is about 1.8 times of Groth16.

3/ PlonK proof size is about2.5 times of Groth16.

Verify Performance

PlonK verification takes pretty much same ammount of time as Groth16.

Conclusion:

PlonK algorithm implements Universal zero knowledge proof. The trusted setup (SRS) needs once. PlonK circuit is composed by gates, which supports only multiplication and addition. The circuit needs proving validity of input/output of the gates, as well as wire’s relationship. PlonK’s fondation is polynomial commitment. PlonK uses smart ways to prove circuits through polynomial commitment.

Founder of Trapdoor Tech (Blockchain & zk-SNARK solution provider) — www.trapdoortech.com