Succinct argument

A succinct non-interactive argument of knowledge (SNARK) is a proof system in which a prover can convince a verifier that a statement $x\in L$ is true using a single short message, where the proof is short relative to the witness size and verification is fast. The “knowledge” variant (SNARK) additionally requires that the prover must “know” a witness — formalized via an extractor. A STARK (Scalable Transparent ARgument of Knowledge) is a SNARK variant that requires no trusted setup, is secure in the random oracle model, and is plausibly post-quantum.

Syntax

A succinct argument system for a relation $\mathcal{R}$ is a tuple of efficient algorithms $(\mathsf{Setup},\mathsf{Prove},\mathsf{Vrfy})$:

• $\mathsf{Setup}(1^{\lambda },C)\to \mathsf{crs},$ takes a security parameter and a circuit $C$ (or a bound on circuit size for universal schemes) and produces a common reference string $\mathsf{crs}$. For transparent systems, $\mathsf{Setup}$ is public-coin (no trapdoor).
• $\mathsf{Prove}(\mathsf{crs},x,w)\to \pi ,$ takes the CRS, instance $x$, and witness $w$ with $(x,w)\in \mathcal{R}$, and produces a proof $\pi$.
• $\mathsf{Vrfy}(\mathsf{crs},x,\pi )\to \{0,1\},$ verifies the proof.

Properties

Completeness

For all $(x,w)\in \mathcal{R}$ and all $\mathsf{crs}\leftarrow \mathsf{Setup}(1^{\lambda },C)$: $\mathrm{Pr}[\mathsf{Vrfy}(\mathsf{crs},x,\mathsf{Prove}(\mathsf{crs},x,w))=1]=1.$

Knowledge soundness

For all efficient $\mathcal{A}$ there exists a polynomial-time extractor ${\mathcal{E}}_{\mathcal{A}}$ such that: if $\mathcal{A}(\mathsf{crs};r)$, run on coins $r$, outputs $(x,\pi )$ with $\mathsf{Vrfy}(\mathsf{crs},x,\pi )=1$, then ${\mathcal{E}}_{\mathcal{A}}(\mathsf{crs},r)$ outputs $w$ with $(x,w)\in \mathcal{R}$, except with negligible probability — Gro16. Knowledge soundness is strictly stronger than plain soundness (which only requires the prover cannot convince the verifier of a false statement).

Succinctness

The proof size $|\pi |$ and verifier runtime are $\mathrm{poly}(\lambda ,|x|)\cdot \mathrm{polylog}(|w|,|C|)$ — sublinear in the witness and circuit size.

Zero-knowledge (optional)

A zk-SNARK additionally satisfies zero-knowledge: there exists a simulator that produces proofs indistinguishable from real proofs without knowing the witness.

Security game

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{ks}}_{\calA,\calE_\calA}(\secpar)$}
\begin{algorithmic}
\State $\crs \gets \Setup(1^\secpar, C)$
\State $r \getsr \bits^{*}$; $(x, \pi) \gets \calA(\crs; r)$
\State $w \gets \calE_{\calA}(\crs, r)$
\Comment{$\calE_\calA$ gets $\calA$'s input and coins}
\If{$\Vrfy(\crs, x, \pi) = 1$ and $(x, w) \notin \calR$}
\Return $1$
\Comment{$\calA$ wins: valid proof but extractor failed}
\EndIf
\Return $0$
\end{algorithmic}
\end{algorithm}

A succinct argument is knowledge-sound if for all efficient $\mathcal{A}$ there exists a polynomial-time extractor ${\mathcal{E}}_{\mathcal{A}}$ such that $\mathrm{Pr}[{\mathbf{G}}_{\mathcal{A},{\mathcal{E}}_{\mathcal{A}}}^{\mathrm{ks}}(\lambda )=1]$ is negligible.

Variations

zk-SNARK

A SNARK with zero-knowledge. The verifier learns nothing about the witness beyond the validity of the statement. Groth16 is the canonical pairing-based zk-SNARK with constant proof size (3 group elements) and millisecond verification — Gro16.

STARK

A Scalable Transparent ARgument of Knowledge achieves succinctness without any trusted setup: the $\mathsf{Setup}$ algorithm is public-coin (the CRS is just a random oracle / hash function). Security is proven in the ROM — BCS16; the same compiler is sound in the quantum ROM when the IOP is round-by-round sound — CMS19 — so STARKs are plausibly post-quantum. Proof size is $O({\log }^{2}T)$ for a computation of size $T$, larger than pairing-based SNARKs but still sublinear — BBHR18a.

The core component of STARKs is the FRI (Fast Reed-Solomon IOP of Proximity) protocol, an interactive oracle proof of proximity to Reed-Solomon codes — BBHR18b. Combined with Merkle-tree commitments, FRI yields a transparent (list) polynomial commitment scheme — KPV22.

Universal/updatable SNARKs

Systems like Plonk and Marlin use a single universal trusted setup for all circuits up to size $N$, rather than a per-circuit setup. Plonk uses PLONKish arithmetization and KZG polynomial commitments (KZG10) — GWC19.

Recursive SNARKs

A SNARK that can verify its own proofs, enabling incremental verifiable computation (IVC) and proof aggregation. Used in zkRollups and zkVMs.

Other results

• CRHF ⇒ STARK
• The Fiat–Shamir transform removes interaction from a public-coin protocol but keeps its communication, so in the random oracle model it yields succinct arguments only from succinct protocols: Merkle-committed PCPs (CS proofs) — Mic00; public-coin IOPs with state-restoration soundness — BCS16
• Many SNARKs (e.g. Plonk, Marlin) compile a polynomial IOP, obtained from an arithmetization, with a polynomial commitment scheme — CHM+20
• Bilinear pairing ⇒ zk-SNARK: Groth16 is knowledge-sound in the generic bilinear group model — Gro16; in the algebraic group model its knowledge soundness reduces to a $q$-type discrete-logarithm assumption — FKL18
• No fully-black-box reduction from Falsifiable assumption to SNARK

Participates in

Builds on Succinct argument

• SNARK + OWF ⇒ NIZK
• SNARK ⇒ Recursive SNARKs

Produces Succinct argument

• Bilinear pairing ⇒ zk-SNARK (via zk-SNARK)
• CRHF ⇒ STARK (via STARK)
• Extractable PCS ⇒ SNARK
• SNARK ⇒ Recursive SNARKs (via Recursive SNARKs)

Barriers

• No fully-black-box reduction from Falsifiable assumption to SNARK
• No fixed-construction reduction from Fiat-Shamir + GKR to SNARK