zk-SNARKs: Succinct Non-Interactive Arguments

A zk-SNARK (Zero-Knowledge Succinct Non-interactive ARgument of Knowledge) is a proof that: (1) is zero-knowledge, (2) is succinct (tiny proof, fast verification regardless of computation size), (3) is non-interactive (single proof string).

Sigma protocols work for simple statements (discrete log knowledge). For complex computations — "I ran this function correctly on private inputs" — we need a general-purpose proof system. SNARKs prove arbitrary computations in O(1) verification time.

The computation is first expressed as an arithmetic circuit: a directed acyclic graph of addition and multiplication gates over a finite field. Example: proving you know x such that x^3 + x + 5 = 35 without revealing x=3. The circuit has ~5 gates.

An arithmetic circuit is converted to R1CS: a set of constraints (A*z)*(B*z) = C*z where z is a vector of all wire values. Each multiplication gate becomes one constraint. The prover must find z satisfying all constraints without revealing private wires.

R1CS is converted to a QAP: polynomials A(x), B(x), C(x) such that A(x)*B(x)-C(x) is divisible by a target polynomial t(x) iff the constraints are satisfied. The prover shows they know a polynomial quotient H(x) without revealing the witness.

Groth16 (2016) is the most efficient general SNARK. After a trusted setup (CRS generation), the prover outputs a proof of 3 group elements (~192 bytes for BLS12-381). Verification: 3 pairing operations. Constant-size proof regardless of circuit size.

Groth16 requires a trusted setup per-circuit: sample toxic waste (a random secret), compute the Common Reference String, then destroy the toxic waste. If the waste survives, an adversary can forge proofs. Multi-party ceremonies (Powers of Tau) distribute trust.

PLONK (2019) uses a universal trusted setup: one ceremony works for all circuits up to a size bound. No per-circuit setup needed. Trade-off: slightly larger proofs than Groth16. Used in ZK-EVM implementations (Polygon Hermez, zkSync Era).

STARKs (Scalable Transparent ARguments of Knowledge) require no trusted setup and use hash functions (post-quantum secure). Trade-off: larger proofs (10s of KB vs 200 bytes). Used in StarkWare/StarkNet, Cairo language. SNARKs smaller; STARKs quantum-safe.

Groth16 uses bilinear pairings: e: G1 × G2 → GT where e(a*P, b*Q) = e(P,Q)^{ab}. This allows checking polynomial identities in the exponent without revealing values. BLS12-381 curve is optimized for efficient Groth16 pairings.

Groth16 proving time for a 10^6-gate circuit: ~10 seconds on a modern CPU. Verification: ~1 ms. This asymmetry is intentional: the prover (who did the heavy computation) does the work; the verifier (blockchain node) does near-zero work.

zk-SNARKs prove arbitrary computations in constant-size proofs. Pipeline: computation → arithmetic circuit → R1CS → QAP → SNARK proof. Groth16 is most efficient (trusted setup per circuit); PLONK uses universal setup. Next: ZKP applications in blockchain.