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

For those of you know about Groth16 should be somewhat familiar with CRS — Common Reference String. In a similar fashion, SRS only has Universal data, the Structured Reference String.

Polynomial Commitment

Batched Polynomial Commitment is based on a very simple theory, which happens to be the most important foundation of PlonK. Polynomial commitment is to prove multiple polynomials. The paper has explained single-type polynomial commiement and multi-type polynomial (batched) algorithms.

Single-Polynomial Commitment

On page 11, the paper breaks down in details principles of single polynomial commiement. There are three steps:

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

Basing on single-polynomial commitment, let’s move on to the mult-polynomial commitment. Multi-polynomial means that multiple polynomials are given, and we need to prove their value matches the commitment. In PlonK algorithm, we use two types of polynomial commitment. Unlike single polynomial commitment, this needs Vpc to provide two random messages.

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

Polynomial Permutation

PlonK algorithm relies on the proof of polynomial permutation. Here the polynomial permutation means that swapping the input of a specific polynomial, the output doesn’t change.

Li(X)

Li(X) refers to the Lagrange function value of the ith term in a polynomial. In a finite subgroup H, the generator is g, and the power is n. If a=g^i, then Li(a)=1; otherwise, Li(a) = 0.

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

Before we get into polynomial permutation, we need to define the ID for the input of polynomial. Because in a definite field, the input is g^i, the input can be represented indirectly with i. SID is an order index. Sigma(i) is permutation function.

Permutation protocol

Permutation could happen following situations:

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

Fiat-Shamir Heuristic Algorithm has two different types: interactive and non-interactive. You can check out the wiki if interested:

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

Interactive Type:

To prove Peggy knows one specific value x. and y=g^x, Peggy and Victor both choose a random number: v and c. Peggy provides g^v and r=v-cx, so that Victor can verify.

Non-interactive Type:

In interactive type algorithm, Victor has to provide a random number. In non-interactive type, this random number is substituted by public hash value.

PlonK uses the interactive type algorithm.

Circuit Principle and Constraint System

Vitalik posted on his blog this article about PlonK, which covers the princicple of circuit.

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

Last chapter of the paper, chapter 8 gives an conclusion of the whole PlonK agreement. PlonK agreement is based on polynomial commitment andFiat-Shamir heuristic algorithm. Given 3n witness, and coefficient vector and permutation function of a polynomial, prove that the constraint exists for each gate:

Public Information

PlonK agreement public information, including gate coefficient, permutation function and public input.

Proving Process:

The proving process has 5 rounds.

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:

Verification process has some simple data check. Main steps listed below:

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?

For those of you paying attention, you might be curious how all these calculations guarantee to meet the circuit constraint? Even if multi-polynomial commitment matches the challenge, it only garantees the following function’s polynomial form:

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

The paper also gives performance comparison in first chapter.

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.