From Sigma Protocols to SNARKs and STARKs —
Proving Knowledge Without Revealing It
ZK-SNARKs ZK-STARKs Bulletproofs PLONK
A zero-knowledge proof allows a prover (P) to convince a verifier (V) that a statement is true, without revealing any information beyond the truth of the statement itself. Formally, a ZKP for language L must satisfy three properties.
If the statement is true and both parties follow the protocol, the verifier always accepts.
x ∈ L ⇒ Pr[V accepts] = 1
If the statement is false, no cheating prover can convince the verifier, except with negligible probability.
x ∉ L ⇒ Pr[V accepts] ≤ negl(λ)
The verifier learns nothing beyond the statement's validity. There exists a simulator that produces indistinguishable transcripts.
View_V[P(w) ↔ V](x) ≈ Sim(x)
A circular cave with a magic door. The prover enters from a random side, the verifier calls out which side to exit from. If the prover knows the secret word, they always emerge correctly. After n rounds, probability of cheating = 2-n.
You have two balls — one red, one green. Your colour-blind friend cannot tell them apart. You prove they are different by having the friend hide them behind their back, optionally swap, then show you one. You always correctly say whether they swapped. After n rounds, the friend is convinced.
Multiple rounds of communication between prover and verifier. Verifier sends random challenges; prover responds.
Pros: Simpler construction, information-theoretic ZK possible
Cons: Requires live interaction, not transferable
Sigma Protocols Schnorr ID
Single message from prover to verifier. No interaction needed. Uses a Common Reference String (CRS) or random oracle.
Pros: Publicly verifiable, composable, blockchain-friendly
Cons: Stronger assumptions (CRS or ROM)
SNARKs STARKs Fiat-Shamir
The foundational interactive ZK proof of knowledge of a discrete logarithm. Prover knows x such that h = gx in group G of order q.
a = gz · h-e. These are indistinguishable from real transcripts — so the verifier learns nothing about x.
A Sigma (Σ) protocol is a three-move interactive proof: commit → challenge → response. The Schnorr protocol is the canonical example, but the structure generalizes to many relations.
Given two accepting transcripts (a, e, z) and (a, e', z') with e ≠ e', one can extract the witness w. This gives proof of knowledge, not just proof of existence.
Honest-Verifier Zero-Knowledge: a simulator exists when the verifier picks challenges uniformly at random. Sufficient for Fiat-Shamir transformation.
| Sigma Protocol | Relation Proved | Witness | Applications |
|---|---|---|---|
| Schnorr | h = gx | x (discrete log) | Digital signatures, authentication |
| Guillou-Quisquater | y = xe mod n | x (e-th root) | RSA-based identification |
| Pedersen OR | DL(h₁) OR DL(h₂) | One of x₁, x₂ | Ring signatures, deniability |
| Chaum-Pedersen | DL equality | x: gx=h, fx=v | VRFs, re-encryption proofs |
Transforms any Sigma protocol into a non-interactive proof by replacing the verifier's random challenge with a hash of the commitment. Secure in the Random Oracle Model (ROM).
Provably secure in the ROM. In the standard model, Fiat-Shamir can be insecure for some protocols (Goldwasser-Kalai counterexample). In practice: universally deployed.
Applying Fiat-Shamir to the Schnorr ID protocol yields the Schnorr signature scheme — the basis of EdDSA (Ed25519) and BIP-340 (Bitcoin Taproot).
Succinct Non-interactive ARguments of Knowledge
A ZK-SNARK is a proof system where the proof is succinct (small and fast to verify), non-interactive, and an argument of knowledge (extractable under computational assumptions).
Assumptions typically required: knowledge-of-exponent (KEA), q-SDH (Strong Diffie-Hellman), and the Generic Group Model (GGM). Relies on elliptic curve pairings (BN254, BLS12-381).
The first step in building a SNARK is expressing the computation as an arithmetic circuit over a finite field F_p, then converting it to a Rank-1 Constraint System (R1CS).
Each multiplication gate becomes a constraint:
(a_i · s) * (b_i · s) = (c_i · s)
Variables: s = [1, x, y, v1, out]
Gate 1 (multiply):
a = [0, 1, 0, 0, 0] (x)
b = [0, 0, 1, 0, 0] (y)
c = [0, 0, 0, 1, 0] (v1 = x*y)
Gate 2 (add-as-constraint):
a = [1, 0, 0, 1, 0] (1 + v1)
b = [1, 0, 0, 0, 0] (1)
c = [0, 0, 0, 0, 1] (out)The Quadratic Arithmetic Program converts R1CS constraints into a polynomial identity check. Instead of verifying m constraints individually, the verifier checks one polynomial equation.
For m constraints over n variables, interpolate each column of the a, b, c matrices into polynomials using Lagrange interpolation at points {r₁, ..., r_m}:
A(x) = Σ s_i · a_i(x) // left input polynomial
B(x) = Σ s_i · b_i(x) // right input polynomial
C(x) = Σ s_i · c_i(x) // output polynomial
QAP Satisfaction: A(x) · B(x) - C(x) = H(x) · Z(x)
where Z(x) = (x - r_1)(x - r_2)...(x - r_m) (vanishing polynomial)
and H(x) = quotient polynomial (exists iff constraints satisfied)Schwartz-Zippel lemma: two distinct degree-d polynomials agree on at most d points. Checking at a random point τ gives soundness error d/|F| — negligible over large fields.
Instead of checking m constraints, verify one evaluation: A(τ)·B(τ) - C(τ) = H(τ)·Z(τ). The evaluation point τ is hidden in the CRS — this is where trusted setup enters.
Pairing-based SNARKs require a structured reference string (SRS) containing encrypted evaluations of secret powers τ. If anyone learns τ, they can forge proofs.
SRS = {[τ0]₁, [τ1]₁, ..., [τd]₁, [τ0]₂, [τ1]₂, ...} where [x]₁ = x·G₁ (group elements). Each participant contributes randomness multiplicatively. 1-of-N honest assumption.
If τ is known, an adversary can construct H(τ) to satisfy A(τ)·B(τ) - C(τ) = H(τ)·Z(τ) for any false statement. The entire system collapses. This motivates transparent alternatives (STARKs, Bulletproofs).
Groth16 (Eurocrypt 2016) achieves the smallest proof size and fastest verification of any known pairing-based SNARK. Used in Zcash Sapling, Filecoin, and most EVM ZK circuits.
π = (A ∈ G₁, B ∈ G₂, C ∈ G₁)
~192 bytes on BN254, ~288 bytes on BLS12-381
Verify: e(A, B) = e(α, β) · e(L, γ) · e(C, δ)
Constant-time regardless of circuit size
Setup: Circuit-specific SRS from Powers of Tau
Prove: 1. Compute QAP polynomials A(x), B(x), C(x), H(x)
2. Multi-scalar multiplication (MSM) on G₁ and G₂
A = [α + A(τ) + r·δ]₁
B = [β + B(τ) + s·δ]₂
C = [H(τ)·Z(τ)/δ + witness terms + ...]₁
3. Dominant cost: two MSMs of size |witness|Scalable Transparent ARguments of Knowledge
Introduced by Ben-Sasson et al. (2018). STARKs replace elliptic curve pairings with hash functions and Reed-Solomon codes, achieving transparency (no trusted setup) and plausible post-quantum security.
No secret parameters. The CRS is just a hash function description. Anyone can verify the setup. No toxic waste to destroy.
Trust-minimized
Security relies only on collision-resistant hashing. No discrete log or pairing assumptions. Survives quantum computers (assuming hash security).
Quantum-safe
Prover runs in quasi-linear time O(n · log n). Verifier runs in O(log² n). Both are polylogarithmic in the computation size.
Efficient
| Property | ZK-SNARKs (Groth16) | ZK-STARKs |
|---|---|---|
| Proof Size | ~200 B | ~50-200 KB |
| Verification Time | ~3 ms (constant) | ~10-50 ms (log²n) |
| Prover Time | O(n log n) — MSM-heavy | O(n log n) — hash-heavy |
| Trusted Setup | Required (circuit-specific) | None (transparent) |
| Post-Quantum | No (pairing-based) | Yes (hash-based) |
| Crypto Assumptions | KEA, q-SDH, pairings | Collision-resistant hash |
| Arithmetization | R1CS → QAP | AIR (Algebraic Intermediate Rep.) |
| Commitment Scheme | KZG (pairing-based) | FRI (hash-based) |
| Notable Users | Zcash, Filecoin, Tornado Cash | StarkNet, StarkEx, Polygon Miden |
FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity) is the polynomial commitment scheme underlying STARKs. It proves that a function is close to a low-degree polynomial using only hash queries.
Prover: O(n log n) hash operations
Verifier: O(log² n) hash queries
Proof size: O(log² n) field elements + Merkle paths
FRI achieves soundness error (d/|D|)r where d is the claimed degree, |D| is the domain size, and r is the number of query rounds. Typically 30-80 queries for 128-bit security.
PLONK (Gabizon, Williamson, Ciobotaru, 2019) introduces a universal SRS — one trusted setup works for any circuit up to a given size. The SRS is also updatable — new participants can strengthen it.
PLONK uses a custom gate format instead of R1CS:
q_L·a + q_R·b + q_O·c
+ q_M·(a·b) + q_C = 0
where q_* are selector polynomials
and a, b, c are wire valuesSupports addition and multiplication in a single gate. Custom gates (e.g., Poseidon hash) dramatically reduce constraint count.
PLONK connects gates via a permutation argument. Wire values are constrained to be equal across gates using a grand product polynomial:
Z(x) = Π (f_i + β·σ(i) + γ)
/ (f_i + β·i + γ)
Check Z(ω^0) = 1 and Z(ω^n) = 1
(grand product is identity permutation)Bulletproofs (Bunz et al., 2018) are short non-interactive zero-knowledge proofs that require no trusted setup. Proof size is O(log n) group elements. Optimal for range proofs and small circuits.
vs. ~4 KB for Sigma protocol range proof
Linear in circuit size — not succinct for large circuits
Uses Pedersen commitments + discrete log assumption only
Bulletproofs reduce proving an inner product relation <a, b> = c for vectors of length n to a proof of size O(log n) via recursive halving:
1. Split vectors: a = (a_L, a_R), b = (b_L, b_R)
2. Compute cross-terms: L = <a_L, b_R>, R = <a_R, b_L>
3. Verifier sends challenge x
4. Fold: a' = a_L·x + a_R·x⁻¹, b' = b_L·x⁻¹ + b_R·x
5. Recurse on half-size vectors until n = 1Used in: Monero (confidential transactions), Mimblewimble/Grin, Halo (without trusted setup). Bulletproofs+ reduces proof size by ~16%.
Blockchain · Identity · Private Computation
ZK proofs address two fundamental blockchain problems: privacy (hiding transaction details) and scalability (compressing computation off-chain).
First production deployment of ZK-SNARKs. Shielded transactions hide sender, receiver, and amount. Sprout (2016, Groth16) → Sapling (2018, optimized) → Orchard (2022, Halo 2, no trusted setup).
Privacy Groth16 → Halo 2
Layer-2 scaling: batch thousands of transactions, generate one proof, verify on Ethereum. zkSync Era uses custom SNARK. Polygon zkEVM proves EVM execution. Reduces gas costs ~100x.
Scalability EVM-compatible
STARK-based L2 on Ethereum. No trusted setup. Uses Cairo language compiled to AIR. SHARP (Shared Prover) amortizes proving costs across applications. Post-quantum ready.
STARKs Transparent
ZK proofs enable selective disclosure: prove properties about your identity without revealing the identity itself.
Prove "I am over 18" without revealing your birthdate, name, or any other ID field. The ZK circuit checks: current_date - birth_date ≥ 18 years against a signed government credential.
W3C Verifiable Credentials + ZK: prove you hold a valid diploma from a specific university without revealing your name, GPA, or student ID. BBS+ signatures enable efficient selective disclosure. Semaphore protocol enables anonymous group membership proofs.
ZK proofs extend beyond simple identity: they enable verifiable computation where a server proves it executed a program correctly without revealing inputs.
A weak client delegates computation f(x) to a powerful server. The server returns y = f(x) along with a ZK proof π that y is correct. The client verifies π in O(log |f|) time — far cheaper than recomputing.
Applications: Cloud computing, database queries, trustless oracles
Prove that a neural network inference was computed correctly on a specific model without revealing model weights or input data.
Use cases:
• Prove an AI model produced a specific output
• Verify model fairness without exposing training data
• On-chain AI inference attestation
A proof that verifies another proof. Recursive SNARKs enable incrementally verifiable computation (IVC): each step proves "the previous proof was valid AND I did one more step correctly."
First recursive proof without trusted setup (Bowe, Grigg, Hopwood, 2019). Uses IPA (Bulletproof-style) commitment on Pasta curves. Deployed in Zcash Orchard. Amortizes verification via accumulation.
Kothapalli, Setty, Tzialla (2022). Uses folding instead of full SNARK verification. Folds two R1CS instances into one without proving. Orders of magnitude faster than recursive SNARKs. Dominant IVC scheme.
ZK-rollup state compression, blockchain light clients, verifiable delay functions, incrementally verifiable MapReduce, proof aggregation for batch settlement.
Benchmarks for proving a SHA-256 preimage (~25K constraints). Times on modern hardware (AMD Ryzen 9 / Apple M2). Real-world performance varies significantly with circuit size and optimization.
| System | Proof Size | Prove Time | Verify Time | Setup | Assumption |
|---|---|---|---|---|---|
| Groth16 | 192 B | ~1.5 s | ~3 ms | Circuit-specific | Pairings |
| PLONK | ~600 B | ~3 s | ~5 ms | Universal | Pairings (KZG) |
| Halo 2 | ~5 KB | ~4 s | ~15 ms | None | DLOG |
| STARK | ~100 KB | ~2 s | ~20 ms | None | Hash (PQ-safe) |
| Bulletproofs | ~1.5 KB | ~10 s | ~1.5 s | None | DLOG |
| Plonky2 | ~45 KB | ~0.5 s | ~3 ms | None | Hash (PQ-safe) |
| Nova (folding) | ~10 KB* | ~20 ms/step | ~50 ms* | None | DLOG |
*Nova proof requires a final SNARK compression step for succinctness. Per-step cost is amortized.
A simplified Schnorr-style ZK proof of discrete log knowledge, showing the Fiat-Shamir transformation. This is real cryptographic structure, not abstraction.
def prove_dlog(G, H, x, q):
"""Prove knowledge of x such that H = x*G (elliptic curve)"""
# 1. Commit: pick random nonce
r = random_scalar(q) # r ← Z_q
A = r * G # commitment A = r·G
# 2. Challenge: Fiat-Shamir hash
e = H_to_scalar(G, H, A) # e = Hash(G || H || A) mod q
# 3. Response
z = (r + e * x) % q # z = r + e·x mod q
return Proof(A, z) # π = (A, z)
def verify_dlog(G, H, proof, q):
"""Verify proof that prover knows x with H = x*G"""
A, z = proof.A, proof.z
# Recompute challenge
e = H_to_scalar(G, H, A) # e = Hash(G || H || A) mod q
# Verification equation: z·G == A + e·H
lhs = z * G # z·G
rhs = A + e * H # A + e·H = r·G + e·x·G
return lhs == rhs # True iff prover knows xz·G = (r + e·x)·G = r·G + e·x·G = A + e·H. The simulator picks z, e randomly, computes A = z·G - e·H — indistinguishable from a real proof. This is the foundation on which Ed25519 and Taproot signatures are built.
How a modern ZK framework (e.g., Circom, Halo2, Noir) defines constraints. This example proves knowledge of two numbers whose product equals a public output.
pragma circom 2.1.0;
template Multiply() {
signal input a; // private
signal input b; // private
signal output c; // public
// R1CS constraint: a * b === c
c <== a * b;
}
// Range proof (a is n bits)
template RangeProof(n) {
signal input a;
signal bits[n];
var sum = 0;
for (var i = 0; i < n; i++) {
bits[i] <-- (a >> i) & 1;
bits[i] * (1 - bits[i]) === 0;
sum += bits[i] * (1 << i);
}
sum === a;
}// Aztec's Noir language
fn main(
a: Field, // private
b: Field, // private
c: pub Field // public
) {
// Constraint: a * b == c
assert(a * b == c);
}
// SHA-256 membership proof
fn verify_membership(
leaf: Field,
path: [Field; 32],
root: pub Field
) {
let computed = merkle_root(
leaf, path
);
assert(computed == root);
}Compilation: Circom → R1CS → Groth16/PLONK proof. Noir → ACIR → Barretenberg backend. Both produce a binary proof file and a verification key.
The ZK proof landscape is evolving rapidly. Key research threads in 2025-2026 focus on efficiency, expressiveness, and new paradigms.
Nova, SuperNova, HyperNova, ProtoStar. Replace expensive recursive SNARK verification with cheap folding of relaxed R1CS instances. Nova folds in ~10ms vs ~seconds for recursive Groth16. Sangria extends folding to PLONK.
IVC Dominant paradigm
Plookup, Caulk, Baloo, Lasso. Prove that values appear in a lookup table without expanding into binary constraints. Critical for efficient hash functions (Poseidon, Keccak) and VM execution.
Expressiveness 10-100x gains
Generalization of R1CS, PLONK, and AIR into a single framework. Enables folding schemes to work across different arithmetizations. HyperNova folds CCS instances directly.
Unification
MSM and NTT are the bottlenecks. GPU provers (Icicle, cuZK) achieve 10-50x speedup. FPGA designs target real-time proving. ASICs for ZK (Cysic, Ingonyama) target 100x+ improvement over CPU.
Performance GPU/FPGA/ASIC
Foundations — Zero-knowledge proofs satisfy completeness, soundness, and zero-knowledge. Sigma protocols provide the three-move (commit, challenge, response) interactive framework. Fiat-Shamir heuristic converts interactive proofs to non-interactive via hashing.
SNARKs — Arithmetic circuits compiled to R1CS, encoded as QAP polynomials, committed via KZG pairings. Groth16 achieves 192-byte proofs with 3ms verification. Requires circuit-specific trusted setup (toxic waste, Powers of Tau ceremonies).
STARKs & alternatives — Hash-based, transparent, post-quantum. FRI protocol for polynomial commitment. Larger proofs (~100KB) but no trust assumptions. PLONK provides universal setup. Bulletproofs offer logarithmic proof size without setup.
Applications — Blockchain privacy (Zcash) and scalability (zkRollups, StarkNet). Identity (selective disclosure, age proofs). Verifiable computation and zkML. Recursive composition enables infinite proof compression.
Frontier — Folding schemes (Nova, HyperNova) transform IVC. Lookup arguments accelerate complex operations. Hardware acceleration (GPU/FPGA/ASIC) targets real-time proving. The field converges toward unified, efficient, transparent proof systems.