From SARK to zk-SNARK: Groth16 End-to-End

In Module 2 we saw that satisfying an R1CS reduces to a single polynomial identity $L(x) \cdot R(x) - O(x) = G(x) \cdot H(x)$, and that pairings let us check such an identity on encrypted values.

That gave us a SARK: a succinct, non-interactive, sound argument of knowledge — but not yet zero-knowledge, and not really efficient. In this module we close all three gaps and build a full, working Groth16 prover and verifier in Rust.

Mental model. Groth16 has three phases. First, setup builds an encrypted lookup table for one fixed circuit. Then the prover combines that table with a private witness to form a proof. Finally, the verifier checks one pairing equation using only public data. The rest of this module just makes those three sentences precise.

All Rust snippets in this module come from the companion repository github.com/bsaepfl/zksnarks-101-labs. Clone it locally if you want to run, tweak, or extend the code yourself — every cell on this page is pre-executed with the output shown directly below it.

We'll follow three steps:

1. Trusted setup — sample one secret evaluation point and a few extra random setup scalars (called blinders), publish encrypted evaluations (the Structured Reference String), then throw the secrets away.
2. Zero-knowledge blinding — randomize every proof with fresh per-proof values $r, s$ so two proofs of the same witness look completely different.
3. Groth16 verification — one pairing equation checks correctness, knowledge-soundness, and zero-knowledge all at once.

Running example. We keep the circuit $y = x^3 + x^2$ from Module 2, so you can trace every cell against wire values $x = 3$, $y = 36$ that you already know by heart.

1. Trusted Setup & the Structured Reference String

Goal of this section: turn the public QAP data of the circuit into reusable encrypted material. After setup, the prover will no longer manipulate plain values like $L_i(\tau)$ or $R_i(\tau)$ directly; it will only combine their encoded versions from the SRS.

The verifier cannot see the secret witness, but she needs a way to evaluate the QAP polynomials at a secret point $\tau$. The trick: let a trusted setup party sample $\tau$ together with blinding scalars $\alpha$, $\beta$, $\gamma$, $\delta$, publish encrypted evaluations, and then destroy the secrets. Anything published lives on an elliptic curve, so no one can recover the underlying scalars.

This $\tau$ is the same kind of hidden evaluation point that we called $s$ in Module 2. We rename it here only to avoid a clash with the later Groth16 blinding scalar $s$ used in the proof itself.

These setup secrets appear all at once, so it helps to separate their roles before looking at the SRS itself. None of them belong to the prover's witness or the verifier's public input: they exist only during setup and are discarded afterwards.

A blinder is just an extra random secret scalar added for cryptographic reasons, not because the original circuit needs it. The computation $y = x^3 + x^2$ does not involve $\alpha, \beta, \gamma, \delta$ at all. These values are introduced by the setup to hide structure, separate public from private terms, and prevent the prover from mixing pieces of the proof in invalid ways.

What the SRS contains

The SRS is much easier to read as a few families of published curve points rather than as one giant formula. For our QAP, the setup publishes:

Before reading the table, here is the notation. Writing $[u]_1$ means “encode the scalar $u$ as a point in the first curve group $G_1$,” and $[u]_2$ means the same in $G_2$. Concretely:

So $[L_i(\tau)]_1$ is not the plain scalar $L_i(\tau)$; it is that value hidden inside a group element. The index $i$ ranges over wires of the circuit, and braces such as $\{[L_i(\tau)]_1\}$ mean “the whole family of such encodings for every wire.”

The only new composite term here is $K_i(\tau) = \beta L_i(\tau) + \alpha R_i(\tau) + O_i(\tau)$. It packages together the three selector families into the combination Groth16 needs later in the proof.

Mental picture. The SRS is an encrypted lookup table for this circuit. It lets the prover recover exactly the encoded quantities needed at the hidden point $\tau$, without ever learning $\tau$ itself.

The verification key is a small subset: $([\alpha]_1, [\beta]_2, [\gamma]_2, [\delta]_2, \{[K_i(\tau)/\gamma]_1\})$. The proving key contains everything else.

Why the division by $\gamma$ and $\delta$? These extra blinders lock the prover into combining proving-key terms in exactly the right way. Multiplying two encrypted factors in the pairing equation reintroduces the scalars, which only cancel if the prover used the advertised decomposition — otherwise verification fails.

2. Wire Layout and the QAP Recap

Now that setup has published the encrypted queries, what does the prover actually plug into them? Only two things matter: which wires are public versus private, and the quotient polynomial $H(x)$ witnessing that the QAP identity really holds.

Groth16 separates public wires (the verifier sees them) from private wires (the prover keeps them secret). For $y = x^3 + x^2$ the natural split is:

We encode three gates: $x \cdot x = x^2$, $x^2 \cdot x = x^3$, and the consistency constraint $(x^3 + x^2 - y) \cdot 1 = 0$. The target polynomial vanishing on all three gates is $G(x) = (x-1)(x-2)(x-3)$.

The QAP identity $W(x) = L(x)R(x) - O(x) = G(x) \cdot H(x)$ must hold exactly. Here is how the prover computes $H(x)$:

The $BigInt$coefficients look opaque because arkworks shows each field element as a 4×64-bit Montgomery representation — that's just how $Fr$ prints at the 256-bit level. What matters is that the division succeeded with zero remainder, so the identity $W(x) = G(x) \cdot H(x)$ holds.

3. Proving: Unblinded Core + Fresh Blinding

Goal of this section: build a proof from the witness without revealing the witness. Groth16 does this in two layers: first compute a deterministic core from the proving key and the witness, then add fresh randomness so the final proof is unlinkable and zero-knowledge.

A Groth16 proof is just three group elements:

The prover first builds an unblinded core that captures the witness:

Then — and this is the zero-knowledge step — it samples fresh $r, s \in F_r$ for each proof and blinds:

The $-rs \cdot [\delta]_1$ term is the clever piece: when the verifier computes $e(A, B)$, expanding the definitions produces an $rs \cdot \delta^2$ cross-term that must be canceled by $C$. This makes the proof perfectly re-randomizable: two honest proofs of the same witness look statistically independent, yet both verify.

4. Verification: One Pairing Equation

Goal of this section: show that the verifier only has to rebuild the public part of the computation. Everything else is carried by the proof elements $A, B, C$.

The verifier never sees the witness. She only receives $\pi = (A, B, C)$ and the public output $y$, assembles the public-wire term $vk_x = [\text{IC}_0 + y \cdot \text{IC}_1]_1$, and checks a single pairing equation:

That one equation simultaneously enforces three properties:

• Correctness of the QAP identity $L(\tau)R(\tau) - O(\tau) = G(\tau) H(\tau)$.
• Knowledge soundness: the prover had to use the advertised $\alpha, \beta$ terms — without them, no linear combination of SRS elements can produce a valid $(A, B, C)$ (this is the Knowledge-of-Exponent argument from Module 2).
• Public-input binding: wires in $vk_x$ are divided by $\gamma$, wires in $C$ by $\delta$, so the prover cannot swap one pool for the other.

5. Tampering: What Breaks and Why

To make the security guarantees tangible, let's try two kinds of cheating. First, lie about the public output: submit an honest proof for $y = 36$ but claim it proves $y + 1 = 37$. Second, tamper with $C$: replace it with $[1]_1$. Both should fail:

The first failure is due to $vk_x$: changing $y$ changes the $\gamma$-side of the equation but not the $\delta$-side, so the balance breaks. The second failure is due to knowledge-soundness: a random point $[1]_1$can't be re-derived from the advertised proving-key terms, so the pairing equation refuses it.

6. Bonus: KZG-Style Polynomial Commitments

Groth16 uses a one-shot QAP evaluation in the exponent. The more general technique — used by Plonk, Halo2, and many modern SNARKs — is a polynomial commitment scheme. KZG is the canonical example. Given an SRS $\{[\tau^k]_1\}$, committing to a polynomial $f$ is a single group element:

To prove $f(z) = y$, the prover sends the quotient commitment $\pi = [q(\tau)]_1$ where $q(x) = (f(x) - y) / (x - z)$. The verifier checks:

By bilinearity this reduces to $f(\tau) - y = q(\tau) \cdot (\tau - z)$, which is exactly the Euclidean division identity. A false claim $y' \neq f(z)$ has no quotient by $(x - z)$, so it cannot pass.

Summary

You now have a complete zkSNARK — a succinct, non-interactive, and zero-knowledge argument of knowledge — built from the ground up on BLS12-381. The companion repository contains every file you need to experiment further:

• swap the circuit $y = x^3 + x^2$ for your own (e.g. a Merkle membership proof);
• replace the $test_rng()$ with a real CSPRNG;
• compare performance against ark-groth16's production implementation.