Bilinear pairing + q-DLOG ⇒ Universal SNARK (PLONK)

Algebraic group model + random oracle model · GWC19

Statement

In the algebraic group model, with the verifier’s challenges derived from a random oracle, PLONK is a knowledge-sound SNARK for PLONKish circuits under a $q$-type discrete-logarithm assumption in an asymmetric bilinear group: gate constraints are checked over a multiplicative subgroup in the Lagrange basis, copy constraints are enforced by a permutation argument in the style of Bayer–Groth, and the resulting polynomial protocol is compiled with batched KZG commitments. Its structured reference string, powers of a secret $\tau$ up to a size bound $N$, is universal and updatable: the keys of every circuit of size at most $N$ are derived from it by a deterministic public preprocessing, so PLONK is a universal SNARK; proofs are a constant number of ${\mathbb{G}}_1$ and field elements, and verification is fully succinct — GWC19.

Notes

• The SRS is linear in $N$, and with a fully succinct verifier the prover uses roughly 7.5 to 20 times fewer group exponentiations than Sonic in its fully succinct mode, depending on circuit structure — GWC19.
• The original specification was not even statistically witness-indistinguishable; the scheme as patched in 2022 is statistically zero-knowledge — Sef24.
• Without random oracles, PLONK is knowledge-sound in the algebraic group model and computationally zero-knowledge in the standard model under a falsifiable zero-testing assumption — FS26; in the random-oracle model without the algebraic group model it is knowledge-sound from falsifiable assumptions — LPS25.
• PLONK compiles a polynomial IOP with a polynomial commitment scheme, an instance of Extractable PCS ⇒ SNARK — CHM+20.