Computational cryptography › Live on mainnet today › Pairing curves
ZK PROOFPrimitiveGGMAGMFS

Groth16 / PLONK verifiers

In plain words

Tiny proofs of correct computation that Ethereum can check cheaply.

The idea: First the computation is rewritten as a set of polynomial equations that hold only if every step was done right. The prover commits to those polynomials, and the verifier checks them at a random secret point hidden in curve points from the setup. Two different polynomials almost never agree at a random point, so passing the check there convinces the verifier that the equations hold everywhere, and a pairing makes the check take milliseconds. Extra randomness mixed in hides the inputs.

Why it matters: Most ZK rollups and privacy apps use them.

The details

On the map: BN254 precompiles 0x06-0x08 (FS: PLONK only)

Groth16 and PLONK proofs are tiny[1, 2] (a few hundred bytes) and cheap to check onchain with Ethereum's BN254 precompiles, which have existed since 2017[3, 4]. That makes them the default final step for many ZK rollups and privacy apps, even when the main prover uses STARKs.

They need a trusted setup and rest on q-type and knowledge assumptions that are only proven in idealized models (GGM, AGM)[5]. Shor's algorithm breaks them.

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

About the tags

GGM
Its security proof only covers attackers who use the group as a black box (the generic group model), an idealization.
AGM
Its security proof assumes attackers only produce group elements by combining ones they were given (the algebraic group model), an idealization.
FS
Made non-interactive with the Fiat-Shamir transform, so it falls if Fiat-Shamir fails for it. Fiat-Shamir is proven only for an idealized hash, see its box.

References

  1. Jens Groth. On the Size of Pairing-Based Non-interactive Arguments. Advances in Cryptology – EUROCRYPT 2016. doi:10.1007/978-3-662-49896-5_11
  2. Ariel Gabizon, Zachary J. Williamson and Oana Ciobotaru. PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge. IACR Cryptology ePrint Archive, Paper 2019/953. eprint.iacr.org/2019/953
  3. Christian Reitwiessner. EIP-196: Precompiled contracts for addition and scalar multiplication on the elliptic curve alt_bn128. Ethereum Improvement Proposals (Final), 2017. eips.ethereum.org/EIPS/eip-196
  4. Vitalik Buterin and Christian Reitwiessner. EIP-197: Precompiled contracts for optimal ate pairing check on the elliptic curve alt_bn128. Ethereum Improvement Proposals (Final), 2017. eips.ethereum.org/EIPS/eip-197
  5. Craig Gentry and Daniel Wichs. Separating succinct non-interactive arguments from all falsifiable assumptions. Proceedings of the forty-third annual ACM symposium on Theory of computing, 2011. doi:10.1145/1993636.1993651