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 and relies only on collision-resistant hash functions, making it post-quantum secure.

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

There exists a polynomial-time extractor $\mathcal{E}$ such that for all efficient $\mathcal{A}$: if $\mathcal{A}(\mathsf{crs})$ outputs $(x,\pi )$ with $\mathsf{Vrfy}(\mathsf{crs},x,\pi )=1$, then ${\mathcal{E}}^{\mathcal{A}}(\mathsf{crs})$ outputs $w$ with $(x,w)\in \mathcal{R}$, except with negligible probability. 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}(\secpar)$}
\begin{algorithmic}
\State $\crs \gets \Setup(1^\secpar)$
\State $(x, \pi) \gets \calA(\crs)$
\State $w \gets \calE^{\calA}(\crs)$
\Comment{Extractor runs $\calA$ as a subroutine}
\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}$ such that $\mathrm{Pr}[{\mathbf{G}}_{\mathcal{A},\mathcal{E}}^{\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 relies only on collision-resistant hash functions, so STARKs are post-quantum secure. Proof size is $O({\log }^{2}T)$ for a computation of size $T$, larger than pairing-based SNARKs but still sublinear — BBHR18.

The core component of STARKs is the FRI (Fast Reed-Solomon IOP of Proximity) protocol, which is a transparent polynomial commitment scheme based on proximity testing to Reed-Solomon codes.

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.

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

• KEA ⇒ SNARK
• Hash function ⇒ SNARK
• SNARK ⇒ Hash function
• Arithmetization + NIZK + PCS ⇒ SNARK
• IP + ROM ⇒ SNARK
• SNARKs are constructed via two steps: (1) arithmetization — convert the computation to polynomial constraints; (2) a polynomial commitment scheme — commit and open evaluations — standard
• Falsifiable assumption ⇒ SNARK
• No fully-black-box reduction from Falsifiable assumption to SNARK

Participates in

Builds on Succinct argument

• SNARK ⇒ Hash function
• SNARK ⇒ NIZK
• SNARK ⇒ Recursive SNARKs

Produces Succinct argument

• Arithmetization + FRI (Fast Reed-Solomon IOP of Proximity) ⇒ SNARK
• Arithmetization + NIZK + PCS ⇒ SNARK
• Arithmetization + PCS ⇒ SNARK
• Arithmetization ⇒ SNARK
• Bilinear pairing ⇒ SNARK
• Falsifiable assumption ⇒ SNARK
• FRI (Fast Reed-Solomon IOP of Proximity) ⇒ SNARK
• Hash function ⇒ SNARK
• interactive protocol + ROM ⇒ SNARK
• IP + ROM ⇒ SNARK
• KEA ⇒ SNARK
• KZG (Kate-Zaverucha-Goldberg) ⇒ SNARK
• PCS ⇒ SNARK

Barriers

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