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

Part 1 took a program and reduced it to a single polynomial check: for any random $\tau$, a valid witness satisfies $T(\tau) = H(\tau) \cdot Z(\tau)$, where $T(t) = L(t) \cdot R(t) - O(t)$. 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.

Binding the Commitments to the QAP Polynomials

Let's start with three commitments: one per aggregate polynomial $L$, $R$, and $O$. Take $\pi_A$, the commitment to $L(\tau)$, which per Part 1 should be computed 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. Recall that both prover and verifier know the $L_i$. 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$'s, which is the property we need to bind $\pi_A$ to the $L_i$: for each variable $i$, the setup 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)$$

Both sides reduce to $e(\pi_A, G_2)^{\alpha_A}$ by bilinearity, so 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$; $\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 $\pi_A' = \alpha_A \cdot \pi_A,\ \pi_B' = \alpha_B \cdot \pi_B,\ \pi_C' = \alpha_C \cdot \pi_C$.

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

That freedom lets the prover pass divisibility at $\tau$ without a genuine witness. 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 bundled point scaled by a secret $\beta$:

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

β keeps the bundle tied: the prover can't split it into $L_i, R_i, O_i$ pieces to apply different weights. Picking a single weight $r_i$ per variable, they form:

$$\pi_K = \beta \sum_i r_i \cdot \big(L_i(\tau) + R_i(\tau) + O_i(\tau)\big) \cdot G_1 \tag{2}$$

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

$$e(\pi_K, G_2) = e(\pi_A + \pi_C,\ \beta \cdot G_2) \cdot e(\beta \cdot G_1,\ \pi_B)$$

$\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:

$$r_i \cdot \big(L_i(\tau) + R_i(\tau) + O_i(\tau)\big) = s_i \cdot L_i(\tau) + s_i' \cdot R_i(\tau) + s_i'' \cdot O_i(\tau), \quad \forall i$$

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$.

$\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 $H(t) = (L(t) \cdot R(t) - O(t)) / Z(t)$ exists as a polynomial 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$:

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

With $Z(\tau) \cdot G_2$ also in the CRS, the verifier runs:

$$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$, now lifted into curve space. 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

Eight commitments and five pairing checks:

What we have is a working SNARK, modulo a CRS-level patch that closes a remaining soundness gap (ρ, covered in the appendix), and a second scalar γ included in the CRS for soundness-proof reasons.⁴ 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 still leak information about the witness. The final section adds blinding to close that gap.

Pinning the Public Variables

The 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.

Split the witness vector:

$$\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 the claimed output. The private half holds the prover's inputs and every intermediate value. From here on, $\pi_A$ sums only over private indices; $\pi_B$ and $\pi_C$ stay as defined, since the verifier needs only one handle on the public values:⁵

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

The missing public half falls to the verifier. The CRS exposes $L_i(\tau) \cdot G_1$ for each public index, and the verifier 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:

$$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)$$

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}$.⁶

Blinding the Commitments

Everything above is sound: any proof the verifier accepts means a valid witness exists for the claim. Soundness alone doesn't imply privacy of the witness. $\pi_A, \pi_B, \pi_C$ are deterministic functions of the witness, and thus an attacker with a candidate witness can confirm or rule it out by recomputing $\pi_A$. 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. Using $L \cdot R - O = H \cdot Z$, the blinded expression factors:

$$\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 too: the CRS grows with matching shifted elements ($\alpha_A Z(\tau) G_1$, $\beta Z(\tau) G_1$, etc.), so the companion proof elements ($\pi_A', \pi_B', \pi_C', \pi_K$) absorb corresponding shifts.

For any fixed witness, $\pi_A, \pi_B, \pi_C$ are uniformly distributed in their groups (δ is uniform, $Z(\tau) \neq 0$). Random points carry no information about the witness that produced them.

What's Next

Together with ρ 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 taken the same pattern far: a private-payment circuit runs about 100,000 constraints and fits in a proof a few hundred bytes long; a zkEVM rollup aggregates tens of millions of constraints and lands around the same size after wrapping.⁸

Part 3 picks up two threads. First, how modern protocols (Groth16, PLONK, STARKs) reshape this pattern to shrink proofs, replace per-circuit setup with a universal one, or drop pairings entirely. Second, what production ZK systems prove in practice: Zcash's shielded transfers, zkEVM rollups, and newer applications.

Appendix

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