This post was first published on Medium.

PLONK is a state-of-the-art zk-SNARK proof system. Previous zk-SNARKs such as Groth16 have a circuit-specific configuration, which requires a new trust configuration for any new circuit. PLONK’s trusted configuration is universalmeaning it can be thrown once and reused by all circuits[1]. It is also updatable: one can always add a new random character until one is convinced that the configuration is not compromised.

This article explains the basic ideas on how to prove a calculation using PLONK. The figure below illustrates the steps to follow to prove a calculation with PLONK.

We will explain each step to you in detail.

Arithmetic circuit

PLONK does not understand a program that you want to prove. It must first be converted into a format called an arithmetic circuit. Arithmetic circuits are circuits made up of two types of gates: addition and multiplication.

Suppose we want to prove that 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.

How PLONK works
Figure 1: circuit

System of constraints

Next, we transform an arithmetic circuit into a constraint system. There are two categories of stresses on circuit wires.

1. Gate Constraints

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

How PLONK works
Figure 2: Constraints

In PLONK, all constraints are normalized/standardized in the following form[2]:

How PLONK works
picture 3

a, b, c are the left, right and output wires of a gate. All Q’s are constants.

How PLONK works
Figure 4: Generic Plonk gate, each circle is a Q

It can be considered as a generalized gate, which can be configured by adjusting Qs. For example, defining Qs as follows turns the generic gate into an addition gate.

How PLONK works
Figure 5: addition gate

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

How PLONK works

Similarly, the following configuration represents a multiplication gate.

How PLONK works
Figure 6: multiplication gate

Figure 2 is normalized as follows:

How PLONK works
Figure 7: Plonk Constraints

We can rewrite Qs in vector form:

Q.L.​=(0,0,1,1), QR​=(0,0,1,0), QA​=(−1,−1,−1,0), QM​=(1,1,0,0), QC​=(0,0,0,−30).

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

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

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

These vectors are called cookie assignments and represent all thread values ​​derived from user input, some of which may be private and only known to the Prover.

2. Copy Constraints

These are constraints across different gates, for example, c0=a1. We will refer to part 2 to explain it.

Polynomials

We can turn a vector into a list of points 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 polynomial of degree 3 passing through these points. {0, 1, 2, 3} is called the rating domain. QL is in “evaluation form”, while its “coefficient form” can be obtained by interpolation[3].

How PLONK works
QL(x)

How PLONK works

Similarly, we can convert other vectors into polynomials, evaluated in the same domain. Let’s define f(x) as:

How PLONK works
Picture 8

F(0) is 0, since

How PLONK works

Likewise, you can evaluate F to 1, 2, 3, which all give 0.

All the constraints in Fig. 7 will be satisfied if and only if the following conditions are met:

How PLONK works
Figure 9

We have compressed all the constraints into a single polynomial F(x), which can be expressed as follows.

How PLONK works
Picture 10

This is because 0, 1, 2 and 3 are the roots of F(X). Figure 9 is valid as long as there is such a polynomial H(x) who does 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):

How PLONK works
Picture 11

We just need to show that g(x) is 0 everywhere, ie it is a zero polynomial.

Schwartz–Zippel lemma

The Schwartz-Zippel lemma states: let F(X) or a nonzero polynomial of degree D on a size F body notthen the probability that F(s) = 0 for one chosen at random s is at most d/n​. Intuitively, this is because f(x) has at most d roots. In practice, d is usually no more than 100 million, while n is close to 2²⁵⁶, which means d/n = 1/10⁶⁹.

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

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

Polynomial Commitment Scheme

How PLONK works
A polynomial commitment

To prove that a polynomial P(x) is equal to 0, we use a polynomial commitment scheme (PCS). A PCS can be thought of as a sort of “hash” of a polynomial P(x), and the committer can prove that P evaluates to some value at some 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: verifier wants to evaluate P at a random point s and send it to the prover
  3. Open: the prover evaluates P at s and returns the result there, accompanied by proof of assessment. The verifier checks the proof, and if it is valid, it concludes P(s) = y. The polynomial equation itself is effectively checked by evaluating to a random value.

We can use PCS to prove that g(x) is zero in Figure 11. The PLONK paper uses matching-based Kate commitments. Other PCS can also be used.

We’ll cover the remaining part of the copy constraint in the next article. Stay tuned. Please let us know if there is an error.

References

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

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

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

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

Watch: BSV Global Blockchain Convention Presentation, Academic Accreditation and Certification on BSV Blockchain

width=”562″ height=”315″ frameborder=”0″ allowfullscreen=”allowfullscreen”>

New to Bitcoin? Discover CoinGeek bitcoin for beginners section, the ultimate resource guide to learn about bitcoin – as originally envisioned by Satoshi Nakamoto – and blockchain.