Plonk: A Mathematical Overview of this Proof System

Plonk is one of the most widely used proof systems.

It is at the core of the proof systems used by ZKsync, Mina, Halo2 (by Zcash), Plonky2 (Polygon), and Succinct Labs SP1’s compression proof, gnark, due to its versatility and efficient prover.

Since it's introduction, the Plonk protocol has been improved, and some components have been changed.

Plonk stands for Permutations over Lagrange basis for Oecumenical, Non-interactive arguments of Knowledge.

It was introduced by Williamson & Gabizon in this paper.

The paper introduced a new arithmetization scheme (which we call Plonkish) and interactive oracle proof (IOP) and used KZG as a polynomial commitment scheme (PCS).

The original Plonk protocol offered constant-sized proofs, consisting of 7 or 9 points of a pairing-friendly elliptic curve and 6 field elements. However, the commitment schemes used by Halo2, Mina, and zkSync have evolved to cater to different needs.

Halo2 and Kimchi (Mina) now utilize an inner product-based PCS, while Plonky2 and Boojum (zkSync) have adopted FRI.

These transparent PCS eliminate the need for a trusted setup and pairing-friendly elliptic curves, showcasing Plonk's adaptability.

Plonkish (Plonk arithmetization), is a complex yet fascinating concept.

Let's start by working with fan-in-2 gates: each gate has left and right input (a and b) and the output (c).

We can later create more complex gates like the ones we have in Kimchi (which can take 15 variables). We will construct a table where each row contains elements a,b,c.

This table, known as the execution trace, is a key component of Plonkish.

Each gate can be represented by selector variables, q_i.

Using different values of q_i lets us tailor the type of gate. The general Plonk gate has the form q_L a + q_R b + q_M a b + q_O c + q_C = 0.

Setting q_M = 1, q_O = -1, and the rest to zero, we get a simple multiplication gate, a*b = c.

We can create more complex gates by adding selector variables and extra terms: for example, lookup tables, elliptic curve addition, foreign field, etc.

If the gate’s input and output are correctly related, the gate equation will evaluate to zero.

However, even if every gate’s equation evaluates to zero, this does not mean that we computed things correctly. For example, the output of gate 1 could be the right input to gate 2, but the system of equations does not enforce those conditions! We have all the gates disconnected.

To solve this, we need to provide the wirings or connections between the variables.

Plonk uses a permutation check to ensure the correctness of the wirings. The original version is based on the grand product check.

Execution is valid if the trace assignment satisfies wiring constraints & the gate constraints.

To prove, we encode the equations using polynomials: we interpret each value of each selector and trace column as the evaluations of a univariate polynomial over a smooth domain D0.

As the selectors and wiring are fixed for each circuit, we can have them already interpolated and committed (preprocessing).

The prover will have to interpolate the trace and build polynomials for the gate constraints and the permutation checks.

If all hold, the resulting polynomials should be divisible by the vanishing polynomial over the interpolation domain.

The prover produces the quotient polynomial, resulting from the division of a linear combination of the constraint’s polynomials and the vanishing polynomial.

Afterward, the prover will receive a random point z where to evaluate the polynomials, so that the verifier can then check the validity of the computations.

The final proof size depends on the PCS: with KZG, proofs will be short, but we need a trusted setup.

For inner product arguments, proofs will be longer, but with transparent setup. With FRI, proof sizes will be polylogarithmic in the degree of the polynomials, but need no setup.

For more details, check the implementation at lambdaworks by LambdaClass or watch the videos by Dan Boneh.

Stay tuned:  🐦 Twitter | 🗨️ Telegram | 👾 Discord | 🌐 Website | 🌌 Galxe | 📝 Manifesto