zk-SNARKs

The core idea: prove the computation, hide the input

Imagine you want to prove to a server that you know the password for an account — without sending the password, and without the server storing anything it could leak. Or prove you own enough cryptocurrency to cover a transfer without revealing your balance. Or prove that a 30-minute batch of 10,000 transactions all executed correctly, by handing a chain a 200-byte receipt instead of replaying every transaction. zk-SNARKs do all three with the same machinery.

A zk-SNARK — Zero-Knowledge Succinct Non-interactive ARgument of Knowledge — is a proof that some statement of the form "I know a secret w such that f(x, w) = y" is true. Here f is a public program (the circuit), x and y are public inputs and outputs, and w is the secret witness. The prover convinces the verifier of three things at once:

• The computation ran correctly — every gate of f produced consistent outputs.
• The prover actually knows w — it isn't a lucky guess (the "of knowledge" part).
• The verifier learns nothing about w — beyond the bare fact that a valid one exists (the "zero-knowledge" part).

The magic is the asymmetry: the proof is succinct. Whether the circuit has a thousand gates or a billion, a Groth16 proof is three elliptic-curve points — about 200 bytes — and verification is a fixed number of pairing checks taking single-digit milliseconds. The proof size and verify time do not grow with the computation. That is what lets a blockchain verify an enormous off-chain batch in one cheap on-chain call.

From program to polynomials: the precise pipeline

The construction proceeds through a well-defined chain of reductions. Each step turns "did this program run correctly?" into a more algebraic question.

1. Arithmetic circuit. The program f is compiled into a circuit of addition and multiplication gates over a large prime field 𝔽_p (typically a 254-bit prime for the BN254 curve, or 255-bit for BLS12-381). Booleans, comparisons, and hashes all become field arithmetic.
2. R1CS (Rank-1 Constraint System). The circuit becomes a list of constraints, each of the form (A·s) × (B·s) = (C·s), where s is the full assignment vector (public inputs plus the witness) and A, B, C are constant matrices. One multiplication gate = one constraint.
3. QAP (Quadratic Arithmetic Program). The m constraints are interpolated into polynomials. The constraint system becomes a single divisibility check: a target polynomial A(z)·B(z) − C(z) must be divisible by a known vanishing polynomial Z(z) that is zero at all m constraint points. So "the program ran correctly" becomes "this polynomial division has no remainder."
4. Polynomial commitment + pairing. The prover commits to its polynomials as elliptic-curve points using the trusted-setup parameters, then proves the divisibility identity holds at one secret evaluation point τ chosen during setup. The verifier checks the identity with a bilinear pairing e(·, ·) — a map that lets you multiply in the exponent without learning the exponents.

The Schwartz–Zippel lemma is what makes the last step sound. Two distinct degree-d polynomials can agree at most d points. Over a field of size p ≈ 2²⁵⁴, checking them at one random point fails to catch a discrepancy with probability at most d / p — astronomically small. So if the prover cheated, the committed polynomials almost certainly disagree at τ, and the pairing equation fails.

Two more standard ingredients finish the construction. The Fiat–Shamir transform replaces the verifier's random challenges with the hash of the transcript so far, turning an interactive protocol into a single non-interactive message. And blinding factors — random offsets added to the prover's polynomials — give the zero-knowledge property: the committed points look uniformly random, so they leak nothing about w.

When to reach for a zk-SNARK (and when not to)

• Verification must be cheap and the proof must be small. On-chain rollups (zkSync, Polygon zkEVM, StarkNet's relatives) verify one tiny proof instead of re-executing thousands of transactions. Constant-size proofs are the whole point.
• You're hiding a private input. Private payments (Zcash), private voting, age/credential checks ("I am over 18" without a birth date), proof of solvency without revealing balances.
• The circuit is fixed and reused. Setup and circuit compilation are expensive; they amortize beautifully when the same circuit verifies millions of proofs.

Avoid zk-SNARKs when the statement is small enough to just send and check directly — a SNARK adds enormous prover cost for no benefit. Avoid Groth16's per-circuit trusted setup if you can't run or trust a ceremony; prefer PLONK (universal setup) or a STARK (no setup). And avoid them when you need post-quantum security from a pairing-based scheme — elliptic-curve pairings fall to a quantum computer, whereas hash-based STARKs do not.

zk-SNARK vs other proof systems

	Groth16	PLONK	zk-STARK	Bulletproofs	Interactive ZK (Σ-protocol)
Proof size	≈ 200 B (constant)	≈ 400–500 B	tens–hundreds of KB	O(log n), ~1–2 KB	O(n) rounds of messages
Verify time	O(1), 3 pairings	O(1)	O(log² n)	O(n)	O(n)
Prover time	O(n log n)	O(n log n)	O(n log n)	O(n)	O(n)
Trusted setup	Per-circuit (toxic waste)	Universal, updatable	None (transparent)	None	None
Crypto assumption	Pairings + knowledge-of-exponent	Pairings / KZG	Collision-resistant hash	Discrete log	Discrete log
Post-quantum	No	No	Plausibly yes	No	No
Non-interactive	Yes	Yes	Yes	Yes	No (needs Fiat–Shamir to make it so)
Typical use	Zcash Sapling, rollups	Aztec, many zkEVMs	StarkNet, scaling	Monero range proofs	Identification protocols

The headline trade-off is setup versus proof size. Groth16 is the smallest, fastest-to-verify proof in production — but it pays for that with a trusted ceremony you must run once per circuit. PLONK trades a slightly larger proof for a single universal setup you can reuse and update. STARKs throw out trusted setup entirely and lean only on hashes, at the cost of proofs that are hundreds of times larger.

What the numbers actually say

• A Groth16 proof is exactly 3 group elements: two points in G₁ and one in G₂. On BN254 a compressed G₁ point is 32 bytes and a compressed G₂ point is 64 bytes, so the proof is 2×32 + 64 = 128 bytes compressed, or 256 bytes uncompressed (2×64 + 128) — usually quoted loosely as "a couple hundred bytes." Either way it does not grow with circuit size.
• Verification is 3 pairings plus a small multi-scalar multiplication over the public inputs. On a laptop that is a few milliseconds; on the Ethereum Virtual Machine, the pairing precompile makes it cost on the order of ~200,000 gas regardless of how big the proven computation was.
• Proving is the expensive side. It scales as O(n log n) in the number of constraints n, dominated by an FFT and several multi-scalar multiplications. A circuit with a few million constraints can take seconds to a couple of minutes to prove on a single machine, and is the part teams throw GPUs and ASICs at.
• Soundness error ≈ 2⁻¹²⁸. Forging a proof for a false statement is as hard as guessing a random 128-bit key — you would expect to need about 3.4 × 10³⁸ attempts. That is why a verifier can accept the proof on a single check.
• The amortization win: a rollup that batches 10,000 transactions into one proof lets the chain verify all 10,000 in one ~200k-gas call instead of, say, 21,000 gas × 10,000 = 210 million gas of re-execution — a roughly 1,000× reduction in on-chain cost.

JavaScript: a Schnorr-style zero-knowledge proof of knowledge

A full SNARK prover is thousands of lines and needs a pairing library, so it's not something to hand-roll in a snippet. But the essence — proving you know a secret without revealing it — is captured by a non-interactive Schnorr proof (a Σ-protocol made non-interactive with Fiat–Shamir). It proves "I know the discrete log x behind the public point P = x·G" — the same shape of claim a SNARK generalizes to arbitrary circuits. This uses BigInt arithmetic mod a prime for clarity (real code uses a proper elliptic-curve group):

// Toy multiplicative group (Z/p)* with generator g. Exponents reduce mod the
// group order n = p - 1, so that g^(r + c·x) = g^r · g^(c·x) (mod p) holds exactly.
// Production code uses a prime-order elliptic-curve group, not this.
const p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF61n; // a 128-bit prime
const n = p - 1n;                              // order of (Z/p)*
const g = 3n;                                  // a generator

const modpow = (b, e, m) => {
  let r = 1n; b %= m;
  while (e > 0n) { if (e & 1n) r = (r * b) % m; b = (b * b) % m; e >>= 1n; }
  return r;
};

// Fiat–Shamir challenge: hash the transcript into an exponent mod n.
async function challenge(...points) {
  const data = new TextEncoder().encode(points.map(String).join('|'));
  const digest = await crypto.subtle.digest('SHA-256', data);
  let h = 0n;
  for (const byte of new Uint8Array(digest)) h = (h << 8n) | BigInt(byte);
  return h % n;
}

// Prover: knows secret x, public statement P = g^x.
async function prove(x) {
  const P = modpow(g, x, p);
  const r = (BigInt(Date.now()) * 0x9E3779B1n + 0x1234567n) % n; // nonce (use a CSPRNG!)
  const R = modpow(g, r, p);             // commitment
  const c = await challenge(P, R);       // non-interactive challenge
  const s = (r + c * x) % n;             // response
  return { P, R, s };                    // the "proof" — x never appears
}

// Verifier: checks g^s == R · P^c (mod p), learning nothing about x.
async function verify({ P, R, s }) {
  const c = await challenge(P, R);
  const lhs = modpow(g, s, p);
  const rhs = (R * modpow(P, c, p)) % p;
  return lhs === rhs;
}

const proof = await prove(123456789n);
console.log(await verify(proof)); // true — and the proof reveals nothing about 123456789

The structure mirrors a SNARK in miniature: a commitment (R), a challenge derived by hashing (Fiat–Shamir), and a response (s) that only someone knowing x could compute, yet which discloses nothing about it. A real zk-SNARK swaps "discrete log of one number" for "a satisfying assignment to an entire circuit," and swaps modular exponentiation for polynomial commitments and pairings.

Python: building and proving a real circuit

In practice you don't write the cryptography — you write the circuit in a DSL like Circom or use a library like py_ecc/galois, and the toolchain handles R1CS → QAP → proof. Here's the same Schnorr proof in Python to mirror the JS, followed by the shape of a real Circom workflow:

import hashlib, secrets

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF61  # a 128-bit prime
n = p - 1                            # order of (Z/p)*; exponents reduce mod n
g = 3                                # a generator

def challenge(*pts):
    data = "|".join(str(x) for x in pts).encode()
    return int.from_bytes(hashlib.sha256(data).digest(), "big") % n

def prove(x):
    P = pow(g, x, p)
    r = secrets.randbelow(n)        # nonce from a CSPRNG — never reuse!
    R = pow(g, r, p)                # commitment
    c = challenge(P, R)             # Fiat-Shamir challenge
    s = (r + c * x) % n             # response
    return {"P": P, "R": R, "s": s}

def verify(proof):
    P, R, s = proof["P"], proof["R"], proof["s"]
    c = challenge(P, R)
    return pow(g, s, p) == (R * pow(P, c, p)) % p

pf = prove(123456789)
assert verify(pf)                   # passes; x is never transmitted

And the real-world Circom + snarkjs Groth16 pipeline — what production teams actually run — looks like this (shell pseudocode):

# 1. Write the circuit (multiplier.circom): proves "I know a, b with a*b == c"
#    template Multiplier() { signal input a; signal input b; signal output c; c <== a*b; }

circom multiplier.circom --r1cs --wasm           # compile to R1CS + witness generator
snarkjs groth16 setup multiplier.r1cs pot.ptau key.zkey   # circuit-specific trusted setup
snarkjs zkey export verificationkey key.zkey vkey.json

# Prover side: supply private inputs, generate witness + proof
node multiplier_js/generate_witness.js multiplier.wasm input.json witness.wtns
snarkjs groth16 prove key.zkey witness.wtns proof.json public.json

# Verifier side: ~200-byte proof.json, checked in milliseconds against vkey.json
snarkjs groth16 verify vkey.json public.json proof.json   # -> "OK"

Variants worth knowing

Groth16 (2016). Jens Groth's scheme is the smallest, fastest-verifying SNARK in production: 3 group elements, 3 pairings. The catch is a per-circuit trusted setup — change the circuit, rerun the ceremony. Used by Zcash Sapling and many early rollups.

PLONK (2019). Permutations over Lagrange-bases for Oecumenical Non-interactive arguments of Knowledge. Introduces a universal, updatable trusted setup: one ceremony serves any circuit up to a size bound, and anyone can add entropy later. Slightly larger proofs than Groth16 but vastly more practical to deploy. Basis for many zkEVMs.

Marlin, Sonic, Halo/Halo2. Other universal-setup SNARKs. Halo2 removes the trusted setup by using a transparent inner-product-argument polynomial commitment (no toxic waste), and famously makes recursive proof composition — a proof that verifies another proof — practical via an accumulation scheme that avoids re-verifying in-circuit at every step.

zk-STARKs (2018). Not pairing-based at all: they use Merkle commitments and the FRI protocol over hashes. No trusted setup, plausibly post-quantum, but proofs are tens to hundreds of kilobytes. Technically a different family, but they prove the same kind of statement.

KZG vs IPA commitments. The polynomial-commitment scheme underneath is itself a choice. KZG (Kate–Zaverucha–Goldberg) gives constant-size openings but needs a trusted setup; inner-product-argument (IPA / Bulletproofs-style) commitments are transparent but give logarithmic-size openings. This single choice cascades into the whole system's setup and proof-size profile.

Common bugs and edge cases

• Under-constrained circuits. The most dangerous SNARK bug: if a signal isn't fully constrained, a malicious prover can choose a witness that satisfies the equations but doesn't correspond to the intended computation — producing a valid proof of a false statement. Auditing circuits for completeness is harder than auditing ordinary code.
• Leaking the toxic waste. If anyone retains the trusted-setup secrets, they can forge proofs forever. This is why setups use multi-party "powers of tau" ceremonies — secure as long as a single participant deletes their share.
• Nonce reuse in the underlying signatures/proofs. As in ECDSA, reusing the random nonce r across two Σ-protocol proofs lets an attacker solve for the secret. Always draw nonces from a CSPRNG; never from Math.random() as the toy code does for readability.
• Forgetting to hash all public inputs into the Fiat–Shamir challenge. If any public value is left out of the transcript hash, the proof can be malleable or replayable across contexts. The challenge must bind the entire statement.
• Field-overflow / aliasing. Comparisons and bit-decompositions in a prime field need explicit range constraints; without them, values can "wrap around" the field modulus and pass checks they shouldn't.
• Assuming zero-knowledge implies privacy of metadata. The proof hides w, but timing, transaction graphs, and which circuit was used can still leak information at the application layer.