How PLONK Works: Part 1

PLONK is a state-of-the-art zk-SNARK proof system. Previous zk-SNARKs such as Groth16 have circuit-specific setup, which requires a new trusted setup for any new circuit. PLONK’s trusted setup is universal, meaning it can be initiated once and reused by all circuits¹. It is also updatable: one can always add new randomness till one is convinced the setup is not compromised.

This article will explain the core ideas on how to prove a computation using PLONK. The figure below illustrates the steps to take in order to prove a computation using PLONK.

We will explain each step in details.

Arithmetic circuit

PLONK does not understand a program one wants to prove. It first has to be converted to a format called arithmetic circuit. Arithmetic circuits are circuits made out of two types of gates: addition and multiplication.

Suppose we want to prove we know the solution to the equation P(x) = x³ + x + 5 = 35 (the solution is 3). We can convert it to the following circuit.

Figure 1: Circuit

Constraint system

Next, we transform an arithmetic circuit to a constraint system. There are two categories of constraints on the circuit wires.

These are constraints within each gate of a circuit. The above circuit has four gates and the following constraints, i.e., equations with certain format.

Figure 2: constraints

In PLONK, all constraints are normalized/standardized into the following form²:

Figure 3

a, b, c are left, right, and output wire of a gate. All Qs are constants.

Figure 4: Plonk generic gate, each circle is a Q

It can be regarded as a generalized gate, which can be configured by tweaking Qs. For example, setting Qs as follows turns the generic gate into an addition gate.

Figure 5: addition gate

To see how, we set QL = 1, QR = 1, QO = -1, QM = 0, QC=0, Fig. 3 becomes

Similarly, the following configuration represents a multiplication gate.

Figure 6: multiplication gate

Fig. 2 is normalized to the following:

Figure 7: Plonk constraints

We can rewrite Qs in vector forms:

QL​=(0,0,1,1), QR​=(0,0,1,0), QO​=(−1,−1,−1,0), QM​=(1,1,0,0), QC​=(0,0,0,−30).

The Q vectors are called selectors and encode the circuit structure, i.e., the program.

Similarly, we can collect all a, b, and c’s into vectors:

a = (a0, a1, a2, a3), b = (b0, b1, b2, b3), c = (c0, c1, c2, c3).

These vectors are called witness assignments and represent all wire values derived from user inputs, some of which may be private and only known by the prover.

These are constraints across different gates, e.g., c0=a1. We will defer to Part 2 to explain it.

Polynomials

We can turn a vector into a list of points by using its index as the x-coordinate. For example, QL can convert to (0, 0), (1, 0), (2, 1), and (3, 1). There is a unique degree-3 polynomial passing through these points. {0, 1, 2, 3} is called the evaluation domain. QL is in “evaluation form”, while its “coefficient form” can be obtained using interpolation³.

QL(x)

Likewise, we can convert other vectors to polynomials, evaluated at the same domain. Let us define f(x) to be:

Figure 8

f(0) evaluates to 0, since

Similarly, you can evaluate f at 1, 2, 3, which all result in 0.

All the constraints in Fig. 7 will be met if and only if the following holds:

Figure 9

We have compressed all constraints to a single polynomial f(x), which can be expressed as follows.

Figure 10

This is because 0, 1, 2, and 3 are roots of f(x). Fig. 9 holds as long as there exists such polynomial H(x) that makes f(x) divide Z(x) without any remainder. Z(x) is called the vanishing/zero polynomial, H(x) the quotient polynomial.

We can define another polynomial g(x):

Figure 11

We only need to show g(x) is 0 everywhere, i.e., it is a zero polynomial.

Schwartz-Zippel lemma

Schwartz–Zippel lemma states: let f(x) be a non-zero polynomial of degree d over a field F of size n, then the probability that f(s) = 0 for a randomly chosen s is at most d/n​. Intuitively, this is because f(x) has at most d roots. In practice, d is usually no larger than 100 million, while n is close to 2²⁵⁶, meaning d/n = 1/10⁶⁹.

This means if we evaluate a polynomials at some random point and the evaluation is 0, it suggests that the polynomials are in fact zero everywhere with overwhelming probability.

A corollary is if we evaluate two polynomials at some random point and they are equal, they are equal everywhere almost surely.

Polynomial commitment scheme

A polynomial commitment

To prove a polynomial P(x) is 0, we use a polynomial commitment scheme (PCS). A PCS can be regarded as sort of “hash” of some polynomial P(x), and the committer can prove that P evaluates to a certain value at a certain point through a proof without revealing the polynomial P.

A PCS consists of three rounds between a prover and a verifier:

  1. Commit: a prover commits to a certain polynomial P and sends it to a verifier
  2. Challenge: the verifier wants to evaluate P at a random point s and sends it to the prover
  3. Open: the prover evaluates P at s and sends back the result y, along with a evaluation proof. The verifier checks the proof and if it is valid, he concludes P(s) = y. The polynomial equation itself is efficiently verified by evaluating at a random value.

We can use PCS to prove g(x) is zero in Fig. 11. The PLONK paper uses Kate commitments, based on pairing. Other PCSs can be used as well.

We will cover the remaining copy constraint part in the next article. Stay tuned. Please let us know if there is any error.

References

https://github.com/sCrypt-Inc/awesome-zero-knowledge-proofs#plonk

[1] As long as the new circuit is not bigger than the original circuit.

[2] The Plonk constraint system is similar to rank-one constraint system (R1CS), in that they both can have only one multiplication in each gate. The difference is R1CS allows unlimited additions in a gate, while Plonk can only do one, excluding the addition of a constant.

[3] In practice, the coefficients will all be integers, since all operations are done not over integers, but a prime field.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
sCrypt

sCrypt (https://scrypt.io) is a company with a mission to provide integrated on-chain smart contracting solutions on Bitcoin Satoshi Vision