zk-SNARKs: succinct proofs and the trusted setup

The wall the last guide left us at

In the previous guide we flattened a computation into an arithmetic circuit and then into an R1CS: a flat list of multiplication constraints that a secret witness must satisfy. Our running toy was prove you know two factors of 15 without revealing them — a single constraint, `p * q = 15`, where the witness is the pair `(p, q)`.

The honest-but-naive proof is simply *"here is my witness, check it yourself."* It fails on two counts at once. It reveals the secret, so there is no zero knowledge left; and the verifier must re-run every single constraint, so there is no saving — for a circuit with a billion gates the verifier does a billion multiplications. A zk-SNARK is the exact opposite extreme.

Unpacking the acronym, word by word

1. Succinct — the proof is tiny and verification is fast, sublinear in (typically independent of) the size of the computation. A Groth16 proof is three group elements whether the circuit had a thousand constraints or a billion.
2. Non-interactive — the prover sends ONE message; no back-and-forth challenge rounds. Anyone, anytime, can verify that same single proof — which is exactly what you need to post it on a blockchain.
3. ARgument — it is computationally sound, not unconditionally sound. A "proof" stops even an all-powerful cheater; an "argument" only stops a cheater bounded by real computing power, because soundness rests on a hardness assumption such as the discrete-log problem.
4. of Knowledge — the prover does not merely show a statement is true, it proves it actually possesses a witness. This is formalized by an extractor: a hypothetical machine that could pull the witness back out of any prover who convinces the verifier.

Two of these we already have tools for. We make the proof non-interactive with the Fiat–Shamir heuristic from guide 1: replace the verifier's coin-flip challenge with a hash of the transcript so far, so the prover can generate the challenge itself without being able to cheat. The genuinely new machinery — succinctness — comes from a beautiful detour through polynomials.

From a heap of constraints to one polynomial

Here is the leap that makes SNARKs succinct: *stop checking constraints one by one, and check them all at once as a single polynomial identity.* The re-encoding of an R1CS that lets you do this is the Quadratic Arithmetic Program (QAP).

The construction: pick `m` distinct points `r_1 … r_m`, one for each constraint, and interpolate per-variable polynomials so that *evaluating at `r_i` reproduces constraint `i`*. Bundle them with the witness into `A(x)`, `B(x)`, `C(x)`. Now the whole claim *"my witness satisfies all m constraints"* becomes the single statement: `A(x)·B(x) − C(x)` is zero at every `r_i`, and therefore is divisible by the vanishing polynomial `Z(x) = Π(x − r_i)`. That is, there exists a quotient `H(x)` with `A·B − C = H·Z`.

# R1CS: for each constraint i,   (A_i . z) * (B_i . z) = (C_i . z)
#   z is the witness vector (the secret inputs plus the constant 1).
#
# Step 1: pick m distinct points r_1 .. r_m, one per constraint.
# Step 2: for each variable j, interpolate column polynomials
#         A_j, B_j, C_j  so that  A_j(r_i) = A[i][j],  etc.

A(x) = sum_j  z_j * A_j(x)
B(x) = sum_j  z_j * B_j(x)
C(x) = sum_j  z_j * C_j(x)
Z(x) = (x - r_1)(x - r_2) ... (x - r_m)        # the "vanishing" polynomial

# z is a valid witness  <=>  A(x)*B(x) - C(x) vanishes at every r_i
#                       <=>  it is divisible by Z(x):
#
#         A(x) * B(x) - C(x)  =  H(x) * Z(x)
#
# The prover commits to A, B, C, H. The verifier picks ONE random s and checks
#
#         A(s) * B(s) - C(s)  ==  H(s) * Z(s)
#
# Schwartz-Zippel: if the identity is false, this passes with prob <= deg/|F|.

Why does checking at one random point suffice? The Schwartz–Zippel lemma: two distinct polynomials of degree `d` agree on at most `d` points. So if the verifier picks a random `s` and finds `A(s)B(s) − C(s) = H(s)Z(s)`, a cheating prover — whose polynomials do not really satisfy the identity — got lucky with probability at most `d/|F|`. Over a field of about `2^254` elements that is astronomically small. Millions of constraints collapse into evaluating a handful of polynomials at a single random point.

Polynomial commitments: the KZG magic trick

There is a catch in the spot-check. The verifier cannot simply see the prover's polynomials: they encode the secret witness, and they are enormous. So the prover must do two things. First, lock in the polynomials before learning `s`, so it cannot quietly change them afterward. Second, reveal only their value at `s`, together with a proof that the value is honest. The primitive that does both is a polynomial commitment — a commitment scheme specialized to polynomials.

The workhorse is KZG (Kate–Zaverucha–Goldberg, 2010). Using a structured reference string `{[τ⁰], [τ¹], …, [τ^d]}` of elliptic-curve points for a secret scalar `τ`, the commitment to a polynomial `p` is the single point `C = [p(τ)]`. The opening proof that `p(a) = v` is also a single point: `π = [q(τ)]`, where `q(x) = (p(x) − v)/(x − a)` — an exact division, because `a` is a root of `p(x) − v`. The verifier then checks one bilinear-pairing equation.

# --- Trusted setup: run ONCE, then the secret tau MUST be destroyed ---
SRS_G1 = [ G1 * tau^i  for i in 0 .. d ]   # d+1 elliptic-curve points
SRS_G2 = [ G2, G2 * tau ]                  # two points for the pairing check

# --- Commit to p(x) = p_0 + p_1 x + ... + p_d x^d ---
def commit(p):
    # = G1 * p(tau), but computable WITHOUT knowing tau, straight from the SRS
    return sum(p[i] * SRS_G1[i] for i in range(len(p)))   # one G1 point

# --- Prove that p(a) = v ---
def open(p, a):
    v = eval(p, a)
    q = poly_div(p - v, x - a)     # exact division: a is a root of p(x) - v
    return v, commit(q)            # the value plus ONE G1 proof point pi

# --- Verify the opening with a single bilinear pairing equation ---
def verify(C, a, v, pi):
    #  e( C - v*G1 , G2 )  ==  e( pi , SRS_G2[1] - a*G2 )
    #  holds because   p(tau) - v  ==  q(tau) * (tau - a)
    return pairing(C - v*G1, G2) == pairing(pi, SRS_G2[1] - a*G2)

Sit with how astonishing this is: a polynomial of any degree is pinned down by one ~48-byte point, and any one of its evaluations is proved by one more. Binding — the fact that you cannot open the same commitment two different ways — rests on a discrete-log-style hardness assumption. This constant-size commit-and-open is precisely what lets the entire proof stay constant-size, no matter how vast the computation behind it.

The trusted setup, and the toxic waste

Look hard at that reference string again: the points are *powers of a secret scalar `τ`*. Somebody had to choose `τ` to build them. And here is the danger — if anyone still knows `τ`, they can forge. Knowing `τ` lets them construct a valid-looking opening `π` for a value `v` that is simply wrong, because the secret hands them a shortcut through the algebra. They could prove a false statement. That leftover secret is the trusted setup's toxic waste, and it must be destroyed the instant the string is built.

Forging this way breaks soundness — it lets you mint counterfeit proofs, for instance conjuring shielded coins out of nothing — though notably it does not break zero-knowledge. Still catastrophic. The fix is never to let one person hold `τ`. A powers-of-tau ceremony is a multi-party computation: each participant folds in their own fresh secret randomness, passes the string along, and deletes their share. The final `τ` is the product of everyone's contributions, and the setup is secure as long as at least one participant was honest and threw their piece away. This is the famous 1-of-N trust assumption.

1. Zcash ran multi-party ceremonies for its shielded SNARK parameters — 6 participants in the original 2016 launch, and a far larger powers-of-tau for the 2018 Sapling upgrade. Each guarded against any single party retaining the toxic waste.
2. Ethereum's KZG Summoning Ceremony, run for the EIP-4844 (proto-danksharding) upgrade, drew over 140,000 contributions — the largest trusted setup ever performed. Among 140,000 people, the bet that at least one honestly deleted their share is overwhelmingly safe.
3. Per-circuit vs universal is the crucial distinction. Some systems need a brand-new ceremony for every circuit; others run one ceremony that serves all circuits up to a size bound. That single choice drives the comparison in the next section.

Groth16, PLONK, and the honest trade-offs

Two systems you will meet constantly. Groth16 (Jens Groth, 2016) is the size champion: a proof of just three group elements — a couple of hundred bytes — verified with a handful of pairings, cheap enough to run inside an Ethereum contract via the `alt_bn128` precompile. Its price tag: a fresh, circuit-specific trusted setup. Change one gate in your circuit and you must run a whole new ceremony.

PLONK (2019) trades a little proof size for a universal, updatable setup: one powers-of-tau string serves every circuit up to a size bound, and it is built directly on KZG. PLONK-style arithmetization also unlocks custom gates and lookup arguments, which is why most modern zkEVMs and general-purpose proving stacks descend from it rather than from Groth16.

// A Groth16 verifier on Ethereum (shape generated by snarkjs), trimmed.
// The whole proof is THREE group elements: a (G1), b (G2), c (G1).
function verifyProof(
    uint[2]    calldata a,        // proof element A  in G1
    uint[2][2] calldata b,        // proof element B  in G2
    uint[2]    calldata c,        // proof element C  in G1
    uint[]     calldata input     // the public inputs
) public view returns (bool) {
    // Rebuild vk_x from the public inputs and the embedded verification key:
    //     vk_x = IC[0] + sum_i input[i] * IC[i+1]
    // Then ONE pairing-product check (4 pairings via the alt_bn128 precompile):
    //     e(-A, B) * e(alpha, beta) * e(vk_x, gamma) * e(C, delta) == 1
    // Constant gas, whether the circuit had 1e3 or 1e9 constraints.
    return pairingCheck(a, b, c, vk_x);
}

Now the honest limits. (1) Not post-quantum: KZG and Groth16 rest on elliptic-curve and pairing assumptions that a large quantum computer would break — contrast the next guide's zk-STARKs, which lean only on hash functions. (2) The trusted setup is real: mitigated by ceremonies, never eliminated. (3) Proving is heavy: the prover runs giant FFTs and multi-scalar multiplications, often hundreds to thousands of times the cost of merely running the computation. Succinctness is paid for entirely on the prover's side — and that asymmetry is exactly what makes SNARKs perfect for blockchains: prove once, expensively, off-chain; verify cheaply, forever, on-chain.