# Understanding PLONK

[PLONK](https://eprint.iacr.org/2019/953.pdf) 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](https://aztec.network/) version coming soon). This is the scheme that we use at [Mina](https://minaprotocol.com/) 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](https://www.cryptologie.net/article/507/the-missing-explanation-of-zk-snarks-part-1/)):
$$f(z) = t(z) \cdot Z_H(z)$$

To prove the last statement, the prover uses of polynomial commitment scheme (specifically, the [KZG scheme](https://cryptologie.net/article/525/pairing-based-polynomial-commitments-and-kate-polynomial-commitments/)) 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.

Prover->Verifier: com(f), com(t)
Note right of Verifier: generates random z
Verifier->Prover: z
Prover->Verifier: f(z), t(z)
Prover->Verifier: proofs of opening
Note right of Verifier: checks that \n sum f(z) = t(z)z_H(z)

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](https://www.cryptologie.net/article/526/maller-optimization-to-reduce-proof-size/)) 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**.

Prover->Verifier: com(f), com(t)
Note right of Verifier: generates random z
Verifier->Prover: z
Prover->Verifier: f(z), r(z) = 0
Prover->Verifier: proofs of opening
Note right of Verifier: reconstruct r(x) and \n validate opening proofs

<details>
<summary>Click to see how it looks in round 5 in the paper.
</summary>


If we remove the other openings that have been aggregated here it is indeed an opening proof of $r(z) = 0$:

$$\frac{r(X) - 0}{X - z}$$

</details>

<br>

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:

Prover->Verifier: com(f)
Prover->Verifier: com(t_lo), com(t_mid), com(to_hi)
Note right of Verifier: generates random z
Verifier->Prover: z
Prover->Verifier: f(z), r(z) = 0
Prover->Verifier: proofs of opening
Note right of Verifier: reconstruct r(x) and \n validate opening proofs

## 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:

Prover->Verifier: com(a), com(b), com(c)
Prover->Verifier: com(t_lo), com(t_mid), com(to_hi)
Note right of Verifier: generates random z
Verifier->Prover: z
Prover->Verifier: a(z), b(z), c(z), r(z) = 0
Prover->Verifier: proofs of opening
Note right of Verifier: reconstruct r(x) and \n validate opening proofs

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 :)