david wong

Hey! I'm David, the author of the Real-World Cryptography book. I'm a crypto engineer at O(1) Labs on the Mina cryptocurrency, previously I was the security lead for Diem (formerly Libra) at Novi (Facebook), and a security consultant for the Cryptography Services of NCC Group. This is my blog about cryptography and security and other related topics that I find interesting.

Understanding PLONK posted last month

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.

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

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

Well done! You've reached the end of my post. Now you can leave a comment or read something else.

Comments

leave a comment...