The PLONK verification algorithm is a cornerstone of modern zk-SNARKs, enabling succinct, non-interactive proofs of arbitrary computations. Here we break it down step by step.
At a high level, PLONK verification ensures that the proof generated by the prover is valid for a specific computation. The verifier performs various checks, using cryptographic commitments and field operations to validate the proof without re-executing the computation.
Before diving into the steps, let's clarify the inputs:
- Verifier preprocessed input: Commitments to the selector polynomials $[q_M]_1, [q_L]_1, [q_R]_1, [q_O]_1, [q_C]_1$, commitments to the permutation polynomials $[s_{\sigma_1}]_1, [s_{\sigma_2}]_1, [s_{\sigma_3}]_1$, and $[x]_2$, the secret point of the setup in $\mathbb{G}_2$.
- Proof elements ($\pi_{\text{SNARK}}$): The commitments $[a]_1, [b]_1, [c]_1, [z]_1, [t_{lo}]_1, [t_{mid}]_1, [t_{hi}]_1, [W_\zeta]_1, [W_{\zeta\omega}]_1$, and the field elements $\bar{a}, \bar{b}, \bar{c}, \bar{s}_{\sigma_1}, \bar{s}_{\sigma_2}, \bar{z}_\omega$.
- Challenges ($\beta, \gamma, \alpha, \zeta, v, u$): Generated deterministically from the circuit, the public inputs and the proof.
Step-by-Step Breakdown
1. Validate the proof components. The verifier starts by checking that the proof elements are well formed:
- All nine commitments are valid points of $\mathbb{G}_1$.
- All six evaluations are elements of $\mathbb{F}$.
- The public inputs $(w_i)_{i \in [\ell]}$ are elements of $\mathbb{F}$.
2. Compute the challenges. The challenges $\beta, \gamma, \alpha, \zeta, v, u$ are derived by replaying the transcript exactly as the prover did.
3. Evaluate polynomials. Three evaluations are computed:
- Zero polynomial, which vanishes on the roots of unity: $Z_H(\zeta) = \zeta^n - 1$
- First Lagrange polynomial: $L_1(\zeta) = \dfrac{\omega (\zeta^n - 1)}{n (\zeta - \omega)}$
- Public input polynomial, using the sign convention from the prover: $\text{PI}(\zeta) = -\sum_{i \in [\ell]} w_i L_i(\zeta)$
4. Split $r$, and compute the batched commitment $[D]_1$. The verifier splits the polynomial $r$ into a constant part and a part that depends on commitments. The constant part is:
$$r_0 = \text{PI}(\zeta) - L_1(\zeta)\alpha^2 - \alpha (\bar{a} + \beta \bar{s}_{\sigma_1} + \gamma)(\bar{b} + \beta \bar{s}_{\sigma_2} + \gamma)(\bar{c} + \gamma) \bar{z}_\omega$$
The remaining terms of $r(X)$, along with a term for the $z$ opening, form the batched commitment:
$$ \begin{aligned} [D]_1 = {} & \bar{a}\bar{b} [q_M]_1 + \bar{a} [q_L]_1 + \bar{b} [q_R]_1 + \bar{c} [q_O]_1 + [q_C]_1 \\ & + \big( (\bar{a} + \beta\zeta + \gamma)(\bar{b} + \beta k_1 \zeta + \gamma)(\bar{c} + \beta k_2 \zeta + \gamma)\alpha + L_1(\zeta)\alpha^2 + u \big) [z]_1 \\ & - (\bar{a} + \beta \bar{s}_{\sigma_1} + \gamma)(\bar{b} + \beta \bar{s}_{\sigma_2} + \gamma) \alpha\beta \bar{z}_\omega [s_{\sigma_3}]_1 \\ & - Z_H(\zeta) \big( [t_{lo}]_1 + \zeta^n [t_{mid}]_1 + \zeta^{2n} [t_{hi}]_1 \big) \end{aligned} $$
5. Compute the full batched commitment $[F]_1$. The verifier aggregates the commitments into a single point:
$$[F]_1 = [D]_1 + v [a]_1 + v^2 [b]_1 + v^3 [c]_1 + v^4 [s_{\sigma_1}]_1 + v^5 [s_{\sigma_2}]_1$$
6. Compute the group-encoded batch evaluation $[E]_1$. The verifier encodes the claimed evaluations into another group element:
$$[E]_1 = \left( -r_0 + v\bar{a} + v^2\bar{b} + v^3\bar{c} + v^4\bar{s}_{\sigma_1} + v^5\bar{s}_{\sigma_2} + u\bar{z}_\omega \right) [1]_1$$
7. Pairing check. The final step is a single pairing equation:
$$e\big([W_\zeta]_1 + u [W_{\zeta\omega}]_1,\ [x]_2\big) = e\big(\zeta [W_\zeta]_1 + u\zeta\omega [W_{\zeta\omega}]_1 + [F]_1 - [E]_1,\ [1]_2\big)$$
This confirms the consistency of all the evaluations, and through them, all the constraints.
Why PLONK Verification Is Efficient
- Batched evaluations: Multiple checks are combined into one equation, needing just two pairings.
- Scalability: The work is independent of the circuit's size, apart from the public input evaluation, which grows with the number of public inputs.
- Zero knowledge: The verifier learns nothing beyond the validity of the proof.
By combining polynomial commitments, batched evaluations and pairings, PLONK provides a secure and scalable way to validate computations in zk-SNARKs.