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

Incrementally verifiable computation (IVC) for a step function $F$ and an initial state $s_0$ lets a prover holding only $(s_t,{\pi }_t)$ compute a proof ${\pi }_{t+1}$ for $s_{t+1}=F(s_t)$ in time $\mathrm{poly}(\lambda ,|F|,|s_t|)$ independent of $t$, such that the verifier accepts honest proofs of $(t,s_t)$, proof size and verification time are $\mathrm{poly}(\lambda )$ independent of $t$, and for every polynomial $t$ no efficient prover makes the verifier accept $(t,s)$ with $s\ne F^t(s_0)$, except with negligible probability — Val08. A recursive SNARK proves that earlier proofs verify. Extraction cost grows polynomially with each level of nesting, so such composition is proved sound only to constant depth; a depth reduction then gives IVC for any fixed polynomial bound on the number of steps — BCCT13.

Interactive succinct arguments

An interactive argument system for $\mathbf{NP}$ whose total communication is $\mathrm{poly}(\lambda ,\log T)$ for statements whose $\mathbf{NP}$ verification takes time $T$, with soundness against efficient provers and no common reference string — Kil92.

SNARGs for P

A publicly verifiable non-interactive argument in the CRS model for deterministic computations, with no knowledge extractor. For a polynomial $T=T(\lambda )$, a statement is a pair $(M,x)$ of a deterministic Turing machine and an input, true when $M$ accepts $x$ within $T$ steps. $\mathsf{Setup}(1^{\lambda },T)$ outputs $\mathsf{crs}$; $\mathsf{crs}$ and proofs have size $\mathrm{poly}(\lambda ,\log T)$, and $\mathsf{Vrfy}$ runs in time $(|M|+|x|)\cdot \mathrm{poly}(\lambda ,\log T)$. Soundness is adaptive: for all efficient $\mathcal{A}$, the probability that $\mathcal{A}(\mathsf{crs})$ outputs $(M,x,\pi )$ with $\mathsf{Vrfy}(\mathsf{crs},(M,x),\pi )=1$ although $M$ does not accept $x$ within $T$ steps is negligible. CJJ21 construct one from LWE with a common random string (LWE with polynomial ratio ⇒ SNARG for P). The bound on verification time is what makes the notion non-trivial: a verifier allowed $T$ steps runs $M$ itself and needs no proof — standard.

Batch arguments for NP

A batch argument (BARG) for $\mathbf{NP}$ is a non-interactive argument in the CRS model for statements $(C,x_1,\dots ,x_k)$, true when every $x_i$ has a witness $w_i$ with $C(x_i,w_i)=1$, for a Boolean circuit $C$. A proof has size $\mathrm{poly}(\lambda ,|C|,\log k)$ and $\mathsf{Vrfy}$ runs in polynomial time. Soundness is non-adaptive: for every false statement $(C,x_1,\dots ,x_k)$, some $x_i$ having no witness, fixed before $\mathsf{crs}$ is sampled, every efficient prover makes $\mathsf{Vrfy}$ accept with negligible probability — CJJ21. Without the size bound the $k$ witnesses form a proof — standard. CJJ21 construct one from LWE (LWE with polynomial ratio ⇒ BARG for NP).

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 argument
• SNARK ⇒ Recursive SNARKs

Produces Succinct argument

• Bilinear pairing ⇒ zk-SNARK (via zk-SNARK)
• CRHF ⇒ Succinct arguments for NP (Kilian) (via Interactive succinct arguments)
• CRHF ⇒ STARK (via STARK)
• Extractable PCS ⇒ SNARK
• LWE with polynomial ratio ⇒ BARG for NP (via Batch arguments for NP)
• LWE with polynomial ratio ⇒ SNARG for P (via SNARGs for P)
• ROM ⇒ SNARK (Micali’s CS proofs)
• 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