While Groth16 achieved theoretical optimality in proof size and verification time, its circuit-specific setup represented a severe operational vulnerability: deploying a new smart contract or updating a single circuit gate required a completely new ceremony. In 2019, Ariel Gabizon, Zachary Williamson, and Oana Ciobotaru published Plonk (Permutations over Lagrange-bases for Oecumenical Non-interactive arguments of Knowledge), revolutionizing zero-knowledge systems by introducing a Universal and Updatable Structured Reference String (SRS) combined with a radical permutation argument.
1. Plonk Gate Arithmetization
Unlike R1CS, which models circuits as matrix equations, Plonk models computation as an execution trace organized into rows (i in {0, dots, n-1}) on roots of unity (mathbb{H} = {omega^0, omega^1, dots, omega^{n-1}}), with three wire columns: Left (a_i), Right (b_i), and Output (c_i). Each row is governed by five public selector polynomials ((q_L, q_R, q_O, q_M, q_C)):
[
q_L(X) a(X) + q_R(X) b(X) + q_O(X) c(X) + q_M(X) a(X) b(X) + q_C(X) = 0 pmod{Z_{mathbb{H}}(X)}
]
This formulation provides unprecedented flexibility:
- Addition Gate: Set (q_L = 1, q_R = 1, q_O = -1, q_M = 0, q_C = 0 implies a_i + b_i – c_i = 0).
- Multiplication Gate: Set (q_L = 0, q_R = 0, q_O = -1, q_M = 1, q_C = 0 implies a_i cdot b_i – c_i = 0).
- Custom Gates (TurboPlonk): High-degree gates like elliptic curve additions or Poseidon hash S-boxes can be evaluated in a single row without decomposing into elementary operations.
2. The Permutation Argument (Enforcing Copy Constraints)
While gate equations guarantee that individual gates compute correctly, they do not enforce that the output of gate 5 feeds into the left input of gate 12. Plonk enforces these copy constraints across all (3n) wires via a permutation (sigma in S_{3n}) using a Grand Product Argument.
Let (beta, gamma leftarrow mathbb{F}_p) be random challenges from the verifier. The prover constructs an accumulator polynomial (Z(X)) satisfying the recursive relation on (mathbb{H}):
[
Z(omega X) = Z(X) cdot rac{(a(X) + beta X + gamma)(b(X) + beta k_1 X + gamma)(c(X) + beta k_2 X + gamma)}{(a(X) + beta S_{sigma 1}(X) + gamma)(b(X) + beta S_{sigma 2}(X) + gamma)(c(X) + beta S_{sigma 3}(X) + gamma)}
]
with boundary condition (Z(omega^0) = 1). If any wire assignment violates the permutation mapping, the product collapses and the polynomial fails to vanish over (mathbb{H}), exposing the cheater by the Schwartz-Zippel lemma.
3. Plookup & Lookup Arguments
Bitwise operations (XOR, bit-shifts, range checks) are notoriously expensive in arithmetic circuits, requiring thousands of gates per SHA-256 compression block. In 2020, Gabizon and Williamson introduced Plookup: allowing a prover to demonstrate that a set of wire values ({f_i}) is contained within a precomputed public lookup table ({t_j}) without evaluating the arithmetic function.
Plookup sorts the concatenated vector of wire values and table entries, proving multiset equality via randomized polynomial roots. A single 8-bit XOR lookup replaces 16 arithmetic constraints, accelerating cryptographic hash proofs by more than an order of magnitude.
