Proof systems and succinct arguments
Protocols by which a prover convinces a verifier that a statement is true, possibly revealing nothing else and with proofs far shorter than the computation they certify.
What it is
A proof system for an NP relation lets a prover holding an instance and a witness with convince a verifier that belongs to the language. Completeness: the honest verifier accepts. Soundness: no prover makes the verifier accept a false statement, except with small probability; it is statistical for proofs and computational for arguments. Knowledge soundness strengthens this: an extractor recovers a witness from any convincing prover. Zero knowledge: a simulator produces the verifier's view from alone ().
Core notions
- Interactive, public-coin, non-interactive: in a public-coin protocol the verifier sends only random challenges. The Fiat–Shamir transform replaces them by hashes of the transcript, with soundness argued in the random-oracle model (). Non-interactive zero knowledge (NIZK) can also use a common reference string (, ).
- SNARG and SNARK: a succinct non-interactive argument for a circuit has proof size and verification time , possibly after preprocessing. A SNARK is a SNARG of knowledge; a zkSNARK is also zero knowledge.
- Setup: a circuit-specific structured reference string from a trusted ceremony (); a universal, updatable one reused across circuits (, ); or a transparent setup that uses only public randomness ().
- PCP and IOP: in a probabilistically checkable proof (PCP) the verifier reads a few positions of a long proof. An interactive oracle proof (IOP) allows several rounds of such oracles; in a polynomial IOP the oracles are polynomials. Kilian commits to a PCP with a Merkle tree to obtain a succinct argument ().
- Polynomial commitment scheme (PCS): commit to a polynomial, then prove its evaluations at chosen points. Instances: pairing-based KZG with constant-size openings and a trusted setup (), discrete-log inner-product arguments (), hash-based Reed–Solomon proximity tests (), and lattice schemes ().
- Arithmetization: the constraint language for the computation, such as R1CS/QAP, AIR, PLONKish constraints, or CCS. Sum-check () is the basic protocol for multilinear statements.
- Recursion, accumulation, folding: incrementally verifiable computation (IVC) and proof-carrying data (PCD) prove long computations step by step. Accumulation () and folding () defer expensive checks to one final decider.
- Simulation extractability: knowledge soundness that survives the adversary seeing simulated proofs; it rules out mauling proofs.
Main approaches
- Pairing-based QAP SNARKs: three-group-element proofs with a circuit-specific setup ().
- Polynomial IOP plus PCS: universal-setup systems compiled with KZG (, ).
- Hash-based coded oracles: transparent, plausibly post-quantum systems from Reed–Solomon proximity testing and Merkle commitments (, ).
- Inner-product arguments: logarithmic proofs without trusted setup, but linear-time verification for general circuits (); recursion without trusted setup ().
- Sum-check and multilinear systems: transparent R1CS arguments () and lookup-based zkVMs (, ).
- Folding: , , .
- Security of deployed configurations: knowledge soundness of PLONK in the random-oracle model from falsifiable assumptions (), simulation extractability of universal zkSNARKs (), and post-quantum soundness of IOP-based arguments ().
Notation used in the comparison table
Parameters below occur in efficiency or security bounds. Each meaning is scoped to its stated regime. Measured quantities are named in words; protocol objects are defined where used. Source aliases do not equate different regimes.
| Symbol | Meaning | Regime | Paper aliases |
|---|---|---|---|
| λ | Computational security parameter. | Arguments and cryptographic compilers. | No paper spelling asserted. |
| |C| | Circuit size in the stated gate/constraint model. | Circuit arguments. | No paper spelling asserted. |
| T | Time bound of the claimed computation. | Time-bounded succinct arguments. | No paper spelling asserted. |
| n | Reed-Solomon evaluation-domain size (code block length). | Proximity testing. | writes N |
| ρ | Reed-Solomon code rate. | Proximity testing. | writes ρ |
| η | Positive distance gap below the specified decoding/agreement threshold. | Proximity gaps; fixed or shrinking regime must be stated. | No paper spelling asserted. |
| q | Cardinality of the evaluation field. | Reed-Solomon proximity. | No paper spelling asserted. |
| δ | Relative distance from a word to the code. | Proximity testing. | writes δ |
| δ0 | Distance threshold in the FRI soundness bound. | Original FRI analysis. | writes δ0 |
| τ | Exponent in the exceptional-challenge bound. | Correlated agreement/proximity. | No paper spelling asserted. |
| γ | Relative disagreement parameter in the stated agreement conclusion. | Correlated agreement. | No paper spelling asserted. |
| ε∗ | Additional error/slack in the correlated-agreement conclusion. | Correlated agreement. | No paper spelling asserted. |
| |x| | Public-instance length in bits in the SNARG proof-size bound. | SNARG succinctness. | No paper spelling asserted. |
| c(η) | Exponent depending on the fixed proximity slack; not a universal constant. | Prime-field proximity-gap bound. | writes C(η) |
| ε | Fixed positive exponent in the witness-compression target. | SNARG boosting; distinct from proximity slack. | No paper spelling asserted. |
This topic covers general-purpose proofs and arguments: interactive and Fiat–Shamir-compiled systems, pairing, discrete-log, and hash-based backends, arithmetizations, polynomial commitments, lookups, recursion, folding, and zkVMs, plus security analyses of concrete configurations. Quantum proofs, designated-verifier proofs, MPC-in-the-head, and lattice proof systems are not yet covered as subfields.