Zero-Knowledge: Constructing a SNARK Proof (Part 2/3)

Equation (3) from Part 1 reduced a program to a single polynomial check: for any random $\tau$, a valid witness satisfies

$$L(\tau) \cdot R(\tau) - O(\tau) = H(\tau) \cdot Z(\tau)$$

That is a clean algebraic statement, but it is not yet a proof. Two gaps remain. The prover must evaluate at a $\tau$ they do not know, and the evaluation must come from the QAP's actual polynomials, not arbitrary ones cooked up to pass the check.

This post closes both gaps, and a few more we'll uncover along the way. By the end, we'll have a full SNARK: eight curve points, five pairing checks, and a proof that reveals nothing about the witness.

Moving Evaluation into Curve Space

The first gap closes by hiding $\tau$ inside curve points. A trusted setup ceremony picks a random scalar $\tau$ and publishes its powers in two prime-order elliptic-curve groups:

$$G_1,\ \tau G_1,\ \tau^2 G_1,\ \ldots,\ \tau^d G_1$$

in $\mathbb{G}_1$, plus the parallel powers $G_2, \tau G_2, \ldots, \tau^d G_2$ in $\mathbb{G}_2$, then destroys the scalar itself. A group of participants each contributes randomness to $\tau$, and as long as one of them destroys their share honestly, nobody can reconstruct it. The destroyed randomness is called toxic waste. What survives is the list of points above: the Common Reference String (CRS), following the same pattern as the trusted setup from the Verkle post.

Anyone who holds the coefficients of a polynomial $P$ can now compute $P(\tau) \cdot G_1$ without learning $\tau$: multiply each published $\tau^k G_1$ by the coefficient $p_k$ and sum. The result is a commitment to the polynomial's value at the hidden point, and it is the core tool that lets the prover hand the verifier witness-dependent values without revealing the witness.

That CRS will keep growing through the rest of this post as new checks call for new fixed points. Every addition follows the same recipe: an expression in the secret scalars, evaluated during the ceremony and published only as a curve point.

Binding the Commitments to the QAP Polynomials

Let's start with three commitments: one per aggregate polynomial $L$, $R$, and $O$. Denote $\pi_A$, the commitment to $L(\tau)$, which per Part 1 is defined as the witness-weighted sum of per-variable polynomials $L_i$:¹

$$\pi_A = L(\tau) \cdot G_1 = \sum_i s_i \cdot L_i(\tau) \cdot G_1$$

where $s_i$ are the witness values. The Knowledge of Exponent (KoE) assumption is what forces the prover to publish a $\pi_A$ computed using the equation above:

Given a pair $(P, \alpha P)$, a curve point and itself shifted by an unknown scalar $\alpha$, KoE says the only way to produce another pair with the same shift is to scale the original pair by a second known scalar $c$, as $(cP, c \cdot \alpha P) = (cP, \alpha \cdot cP)$.² KoE extends naturally to linear combinations: publish $(P_1, \alpha P_1), \ldots, (P_n, \alpha P_n)$ and the prover can return another $\alpha$-shifted pair $(C, \alpha C)$ if and only if $C = \sum_j c_j P_j$ for coefficients $c_j$ the prover knows.

So the prover must build from the published $P_j$ values, which is the property we need to bind $\pi_A$ to the $L_i$. Since both prover and verifier know the $L_i$ polynomials, the setup can hardcode them into the CRS: for each variable $i$, it publishes the pair $\big(L_i(\tau) \cdot G_1,\ \alpha_A \cdot L_i(\tau) \cdot G_1\big)$ with a secret scalar $\alpha_A$. The prover combines these pairs with witness weights $s_i$, using the plain halves to form $\pi_A$ and the $\alpha_A$-shifted halves to form $\pi_A'$.

With these $\alpha$-shifted pairs and $\alpha_A \cdot G_2$ also in the CRS, the verifier can run a pairing check confirming $(\pi_A, \pi_A')$ has the right shift:

$$e(\pi_A',\ G_2) = e(\pi_A,\ \alpha_A \cdot G_2)$$

A pairing $e(P, Q)$ takes two curve points and produces an element of a multiplicative target group $\mathbb{G}_T$. Bilinearity gives $e(aP, bQ) = e(P, Q)^{ab}$, so both sides above reduce to $e(\pi_A, G_2)^{\alpha_A}$, and the check passes iff $\pi_A' = \alpha_A \cdot \pi_A$.³

The same construction with fresh scalars $\alpha_B$ and $\alpha_C$ gives $(\pi_B, \pi_B')$ and $(\pi_C, \pi_C')$. $\pi_B$ is built in $G_2$ rather than $G_1$ so it can later pair with $\pi_A$, while $\pi_C$ stays in $G_1$.

In summary:

$$\begin{aligned} \pi_A &= \sum_i s_i \cdot L_i(\tau) \cdot G_1 \\ \pi_B &= \sum_i s_i' \cdot R_i(\tau) \cdot G_2 \\ \pi_C &= \sum_i s_i'' \cdot O_i(\tau) \cdot G_1 \end{aligned} \tag{1}$$

with α-shifted companions:

$$\begin{aligned} \pi_A' &= \alpha_A \cdot \pi_A \\ \pi_B' &= \alpha_B \cdot \pi_B \\ \pi_C' &= \alpha_C \cdot \pi_C \end{aligned} \tag{2}$$

Nothing yet forces $s_i = s_i' = s_i''$; we could have three candidate witnesses passed in parallel.

Binding the Commitments to a Single Witness

A prover who passes every check without holding a single coherent witness hasn't proved anything. The fix is a fourth commitment $\pi_K$ the verifier uses to check whether the three witness sets agree.

For each variable $i$, the CRS publishes a single point that bundles all three sides under a secret $\beta$:

$$\beta \big(L_i(\tau) + R_i(\tau) + O_i(\tau)\big) \cdot G_1$$

The prover scales each bundle with a single weight $r_i$ per variable to form:

$$\begin{aligned} \pi_K = \beta \cdot G_1 \cdot \sum_i r_i \cdot \big({}&L_i(\tau) + R_i(\tau) \\ &{}+ O_i(\tau)\big) \tag{3} \end{aligned}$$

With $\beta \cdot G_1$ and $\beta \cdot G_2$ also added to the CRS, the verifier runs a pairing check:

$$\begin{aligned} e(\pi_K, G_2) &= e(\pi_A + \pi_C,\ \beta \cdot G_2) \\ &\quad \cdot e(\beta \cdot G_1,\ \pi_B) \end{aligned}$$

$\pi_B$ pairs separately since it lives in $G_2$ while $\pi_A, \pi_C$ stay in $G_1$. By bilinearity, both sides reduce to the same power of $e(G_1, G_2)$. Matching exponents, canceling β, and equating per term in the sum:

$$\begin{aligned} &r_i \cdot \big(L_i(\tau) + R_i(\tau) + O_i(\tau)\big) \\ &\quad = s_i \cdot L_i(\tau) + s_i' \cdot R_i(\tau) \\ &\quad\quad {} + s_i'' \cdot O_i(\tau), \quad \forall i \end{aligned}$$

Assuming the per-variable polynomials $L_i, R_i, O_i$ are linearly independent, the check pushes $r_i$ to match each of $s_i, s_i', s_i''$ for every $i$, forcing the first three commitments to collapse onto a single witness.

$\alpha$ binds each proof element to the QAP polynomials; β binds the three elements to the same witness. We now have a consistent prover. One gap remains: their witness must satisfy the gate constraints.

Binding the Commitments to a Satisfying Witness

Part 1 showed that the quotient polynomial $H(t) = (L(t) \cdot R(t) - O(t)) / Z(t)$ divides with no remainder iff every gate is satisfied, where $Z$ is the target polynomial vanishing at all gate roots. The prover commits $H(\tau)$ using the CRS powers of $\tau$ from the first section:

$$\pi_H = H(\tau) \cdot G_1 = \sum_j h_j \cdot (\tau^j \cdot G_1) \tag{4}$$

Once $Z(\tau) \cdot G_2$ joins the CRS, the verifier can run:

$$e(\pi_A,\ \pi_B) = e(\pi_H,\ Z(\tau) \cdot G_2) \cdot e(\pi_C,\ G_2)$$

Both sides reduce to powers of $e(G_1, G_2)$; by bilinearity, matching exponents gives:

$$L(\tau) \cdot R(\tau) = H(\tau) \cdot Z(\tau) + O(\tau)$$

That is the QAP identity $L \cdot R - O = H \cdot Z$ evaluated at $\tau$. By Schwartz-Zippel, if the identity holds at a hidden random $\tau$, it holds as polynomials with overwhelming probability.

A Working Core, Two Gaps Left

Equations (1) through (4) supply the eight commitments shown on the left, wired to the five pairing checks on the right:

What we have is a working SNARK, modulo a CRS-level patch that closes a remaining soundness gap (ρ, covered in the appendix). Two gaps remain on the main path:

• Public inputs. Nothing yet pins the claimed output to what the verifier expects. The next section adds a public/private split.
• Zero knowledge. The commitments could leak information about the witness. The final section adds blinding to close that gap.

Pinning the Public Variables

A typical SNARK claim reads "this program, run on my private inputs, produces this public output." The verifier has the output. They want a proof the run was honest. The five pairing checks, though, accept any consistent witness: the prover can pick whatever output they like and still pass.

Fix it by splitting the witness vector so the verifier owns the public half:

$$\mathbf{s} = [\underbrace{s_0, s_1, \ldots, s_\ell}_{\text{public}} \mid \underbrace{s_{\ell+1}, \ldots, s_n}_{\text{private}}]$$

The public half holds the constant 1 and whatever values the verifier needs visible, usually the claimed output. The private half holds everything else.

From here on, $\pi_A$ sums only over private indices; $\pi_B$ and $\pi_C$ stay as defined, since one anchor on the public side is enough:⁴

$$\pi_A = \sum_{i \text{ private}} s_i \cdot L_i(\tau) \cdot G_1$$

The missing public half falls to the verifier, and the CRS already has the $L_i(\tau) \cdot G_1$ they need (from the KoE setup). The verifier picks the public-index ones and combines them with the claimed values on their side:

$$L_\text{pub}(\tau) \cdot G_1 = \sum_{i \text{ public}} s_i \cdot L_i(\tau) \cdot G_1$$

Wherever the verification equations used the full $L(\tau) \cdot G_1$, they now use $L_\text{pub}(\tau) \cdot G_1 + \pi_A$: the verifier's half plus the prover's, reassembled on the curve.

The divisibility check becomes:

$$\begin{aligned} e\big(L_\text{pub}(\tau) \cdot G_1 + \pi_A,\ \pi_B\big) ={}& e(\pi_H,\ Z(\tau) \cdot G_2) \\ &\cdot e(\pi_C,\ G_2) \end{aligned}$$

Same argument as before forces the QAP identity, now on $L = L_\text{pub} + L_\text{priv}$: it holds iff $\pi_A, \pi_B, \pi_C, \pi_H$ were computed from a witness matching the verifier's $L_\text{pub}$. The verifier now binds the proof to the output they specify: a proof passes only when it's computed against that exact value.

Blinding the Commitments

Everything above is sound: any proof the verifier accepts means a valid witness exists for the claim. But soundness doesn't imply privacy. $\pi_A, \pi_B, \pi_C$ are deterministic functions of the witness, so anyone with a candidate witness in mind can recompute $\pi_A$ from the public CRS and check it against the published proof: a match confirms the guess, a mismatch rules it out. Zero-knowledge demands the proof reveal nothing about the witness.

The fix: randomize each commitment with a shift the verification equations absorb. The prover picks fresh $\delta_L, \delta_R, \delta_O$ per proof:⁵

$$\begin{aligned} \pi_A &= L(\tau) \cdot G_1 + \delta_L \cdot Z(\tau) \cdot G_1 \\ \pi_B &= R(\tau) \cdot G_2 + \delta_R \cdot Z(\tau) \cdot G_2 \\ \pi_C &= O(\tau) \cdot G_1 + \delta_O \cdot Z(\tau) \cdot G_1 \end{aligned}$$

The divisibility check already uses $Z(\tau) \cdot G_2$. Adding $Z(\tau) \cdot G_1$ to the CRS lets the prover form each shift on the curve.

Divisibility survives. Expand the products and substitute $L \cdot R = H \cdot Z + O$ for the bare $LR$ term. The $O$ cancels with $-O$, leaving everything multiplied by $Z$:

$$\begin{aligned} &\underbrace{(L + \delta_L Z)}_{L_{\text{new}}}\underbrace{(R + \delta_R Z)}_{R_{\text{new}}} - \underbrace{(O + \delta_O Z)}_{O_{\text{new}}} \\ &\quad = Z \cdot \underbrace{(H + \delta_L R + \delta_R L - \delta_O + \delta_L \delta_R Z)}_{H_{\text{new}}} \end{aligned}$$

The prover now computes $\pi_H = H_{\text{new}}(\tau) \cdot G_1$. The α- and β-checks balance by the same trick: the CRS adds matching shifts ($\alpha_A Z(\tau) G_1$, $\beta Z(\tau) G_1$, etc.) and the companion elements pick them up.

For any fixed witness, $\pi_A, \pi_B, \pi_C$ are uniformly distributed in their groups (δ is uniform, $Z(\tau) \neq 0$). The attacker who tried recomputing $\pi_A$ from a candidate witness now sees only noise: eight curve points, five pairing checks, and zero bits about the witness.

What's Next

Fold in the ρ patch and γ gating from the appendix, and the scheme we just derived is Pinocchio/BCTV14 (2013–2014), the construction Zcash shipped with its original shielded pool in 2016. Modern refinements have pushed the pattern much further: a private-payment circuit runs ~100k constraints and fits in a proof a few hundred bytes long; a zkEVM rollup, an L2 chain that batches Ethereum execution into a single proof, aggregates tens of millions of constraints and lands around the same size after wrapping.⁶

Part 3 will pick up two threads. First, the three protocols that shaped modern ZK proof systems: Groth16 shrinks the SNARK proof to 3 commitments and 1 pairing check, PLONK swaps per-circuit setup for a universal one that unlocks zkVMs, and STARKs leave the SNARK family entirely, replacing pairings with hash-based commitments to drop the trusted setup and gain post-quantum security. Second, what production ZK systems prove in practice: Zcash's shielded transfers, general-purpose zkVMs that turn arbitrary programs into proofs, verifiable ML inference, and ZK identity systems.

Appendix

Two appendices: ρ (linear dependence among the $L_i, R_i, O_i$) and a reference card in literature notation.