Understanding PLONK posted July 2021

PLONK is the state of the art when it comes to general-purpose proof system. While it was released in 2019, the paper has recently received some updates, and the scheme is still evolving (with Aztec announcing an UltraPLONK version coming soon). This is the scheme that we use at Mina to compress the size of the blockchain from gigabytes to a fixed size of a dozen kilobytes.

While I don't think the core ideas are the hardest to understand, the scheme compresses a myriad of optimization which makes it hard to parse. In this post I hope to add some clarity to some aspects of the scheme. Note that I assume that you have some knowledge of how PLONK works.

How PLONK works, the short version

Eventually, the idea of PLONK is to prove that some polynomial $f(x)$ vanishes on some domain $H \subset \mathbb{F}$ (and I will ignore the permutation argument, which is just another proof). To prove that, we reduce the problem to some other problem. Incrementaly, it looks like this:

• Proving the previous statement is equivalent to proving that the polynomial is divisible by $Z_H(x)$, the polynomial that has all the elements of $H$ as roots (also called vanishing polynomial).
• Which is equivalent to proving the following identity (for some quotient polynomial $t$): $$f(x) = t(x) \cdot Z_H(x) \; \; \; \forall x \in \mathbb{F}$$
• Which is equivalent to proving the identity on some random point $z$ (thanks to the Schwartz-Zippel lemma): $$f(z) = t(z) \cdot Z_H(z)$$

To prove the last statement, the prover uses of polynomial commitment scheme (specifically, the KZG scheme) to commit to the polynomial $f$ and $t$. The prover then sends the commitments to the verifier. At that point, the verifier has to check that for some random point $z$

$$ f(z) = t(z) \cdot Z_H(z) $$

This is done by sending a random point $z$ to the prover and doing an "opening" of the commitments at this point: the prover sends the values $f(z)$ and $t(z)$ as well as a proof that these are the correct evaluations.

This is in essence the PLONK protocol, except that this is not really what happens in the paper...

More reductions

The newer PLONK actually does one more reduction of the last statement:

• As per the previous section: we want to prove that $$f(z) = t(z) \cdot Z_H(z)$$
• Which is equivalent to proving that $z$ is a root of the polynomial $$f(x) - t(x) \cdot Z_H(x)$$
• Since the verifier already knows one of the polynomial ($Z_H$), they can evaluate it in advance. So the previous statement is equivalent to proving that $z$ is a root of $$r(x) = f(x) - t(x) \cdot Z_H(z)$$

The last two steps is an optimization (called Maller's optimization) that removes the need for the prover to send $t(z)$, as the verifier can use the commitment to $t$ to produce a commitment to $r$ (to verify the opening proof).

These additional reductions moved us from a protocol in which the prover sends openings to let the verifier check an identity by themselves, to a protocol where the prover simply sends openings.

To verify the opening of $r$ for $x = z$, the verifier will have to reconstruct a commitment to $r$ first. That's easy, it is:

$$com(r) = com(f) - com(t) \cdot Z_H(z)$$

which will use:

• the commitment to $f$ received during the protocol
• the commitment to $t$ received during the protocol
• the evaluation of $Z_H(x)$ at $x=z$ which they can do by themselves

Not so fast... t is too large

If you've read PLONK, you've noticed that the prover actually doesn't send a commitment to $t$ directly, because $t$ is too large and polynomial commitment schemes have an upperbound fixed during the trusted setup. (By the way, $t$ is too large because the permutation argument makes it three times as large due to the three witness polynomials.) To circumvent that limitation, the polynomial $t$ is split into three smaller polynomials $t_{lo}, t_{mid}, t_{hi}$ such that:

$$ t(x) = t_{lo}(x) + x^n \cdot t_{mid}(x) + x^{2n} \cdot t_{hi}(x) $$

This means that in our previous protocol, we can't prove directly that $z$ is a root of

$$r(x) = f(x) - t(x) \cdot Z_H(z)$$

instead we have to prove the equivalent that $z$ is a root of

$$r(x) = f(x) - [t_{lo}(x) + x^n \cdot t_{mid}(x) + x^{2n} \cdot t_{hi}(x)] \cdot Z_H(z)$$

This is not great, as the prover cannot produce a commitment to $r$ anymore. The reason is that $x^n$ and $x^{2n}$ cannot be committed as they're larger than the upperbound of our polynomial commitment. Instead, notice that since the verifier already knows these values, so they can pre-evaluate them at $z$ and ask instead for a proof that:

$$r(x) = f(x) - [t_{lo}(x) + z^n \cdot t_{mid}(x) + z^{2n} \cdot t_{hi}(x)] \cdot Z_H(z)$$

which is a fine request, as the verifier can produce the commitment of $r$ needed to verify the opening proof:

$$ com(r) = com(f) - [com(t_{lo}) + z^n \cdot com(t_{mid}) + z^{2n} \cdot com(t_{hi})] \cdot Z_H(z) $$

At this point, the protocol looks more like this:

Uh-oh, what about f?

The big proof in PLONK really boils down to two things:

1. The permutation argument, which links the wires in our circuit. I ignore this proof in the post.
2. the main polynomial $f$, which is our circuit.

Since the polynomial $f$ needs to be constructed such that:

• it does not leak any non-public information to the verifier
• it does not allow the prover to change fixed parts of the circuit

the prover and the verifier perform a "polynomial dance" to construct the polynomial together. The end product sorts of looks like this:

$$ f(x) = a(x) q_L(x) + b(x) q_R(x) + q_M(x) a(x) b(x) + q_O(x) c(x) + q_C(x) $$

where $a, b, c$ are private polynomials that the prover constructs, commits, and sends to the verifier; and $q_L, q_R, q_M, q_O, q_C$ are public polynomials (the selector polynomials) that both the verifier and the prover can construct (and commit to if necessary).

So the end protocol looks more like this:

And as in the previous section, the verifier needs to reconstruct a commitment to $r$ before being able to ask for an opening, which is now impossible as we're dealing with multiplication of commitments

$$ \begin{align} r(x) = \; &a(x) q_L(x) + b(x) q_R(x) + a(x) b(x) q_M(x) + c(x) q_O(x) + q_C(x) \\ & - [t_{lo}(x) + x^n \cdot t_{mid}(x) + x^{2n} \cdot t_{hi}(x)] \cdot Z_H(z) \end{align} $$

but since the prover sends the evaluations of $a, b, c$ at $z$ (with proofs), the verifier can use that to simplify the polynomial $r$ to:

$$ \begin{align} r(x) = \; &a(z) q_L(x) + b(z) q_R(x) + a(z) b(z) q_M(x) + c(z) q_O(x) + q_C(x) \\ & - [t_{lo}(x) + x^n \cdot t_{mid}(x) + x^{2n} \cdot t_{hi}(x)] \cdot Z_H(z) \end{align} $$

Finally, the verifier can produce the commitment of $r$ as:

$$ \begin{align} com(r) = \; &a(z) com(q_L) + b(z) com(q_R) + a(z) b(z) com(q_M) + c(z) com(q_O) + com(q_C) \\ & - [com(t_{lo}) + z^n \cdot com(t_{mid}) + z^{2n} \cdot com(t_{hi})] \cdot Z_H(z) \end{align} $$

There's much more to PLONK. I've skipped the circuit part, the permutation argument, I've also ignored the big pairing equation at the end. These will be subjects for another post :)