+TITLE: Zero Knowledge Proofs

Table of Contents

file	Description
Pre-Course	Course Prep
Lecture 1	Notes: lecture 1
Homework 1	Homework 1
Lecture 2	Notes: lecture 2
Homework 2	Homework 2 (group theory, binary operators)
Lecture 3	Notes: lecture 3
Homework 3	Homework 3 (EC point addition)
Lecture 4	Notes from lecture 4
Homework 4	Homework 4 (ECDSA)
Lecture 5	Notes: lecture 5
Homework 5	Homework 4 (EC calculations in Solidity)
Lecture 6	Notes: lecture 6
Homework 6	Homework 6 (Pairings in Solidity)
Lecture 7	Notes: lecture 7
Homework 7	Hw 7 (Arithmetic Circuits)
Lecture 8	Notes: lecture 8
Homework 8	Homework 8 (R1CS)
Lecture 9	Lecture 9 (QAP)
Homework 9	HW9 (Lagrange interpolation, Schwartz-Zippel Lemma)
Lecture 10	Notes: lecture 10
Homework 10	HW10 (R1CS to QAP)
Lecture 11	Notes: lecture 10
Homework 11	HW11: Proving the QAP using EC points
Lecture 12	Pinocchio and trusted setup
Homework 12	Homework 12
Homework 13	Homework 13

Building a SNARK from Scratch

The construction proceeds in 5 stages, each building on the last.

Stage 1: Arithmetic Circuits (lecture 7, homework 7)

The starting point is encoding a computational statement as an arithmetic circuit – a DAG of addition and multiplication gates over a finite field. The homework problems demonstrate this for graph coloring, subset sum, covering set, max, and power-of-two checks. The key insight: any computation can be “flattened” into constraints of the form $a ⋅ b = c$, where addition is folded into linear combinations for free.

Stage 2: R1CS – Rank-1 Constraint System (lecture 8, homework 8)

Each multiplication gate becomes one row of three matrices $L, R, O$ (of size $n × m$, where $n$ = number of constraints, $m$ = witness length). The witness vector $w = [1, \text{public inputs}\ldots, \text{private inputs}\ldots, \text{intermediates}\ldots]$ satisfies:

$L\mathbf{w} o R\mathbf{w} = O\mathbf{w}$

where $o$ is the Hadamard (element-wise) product. The homework 8 demonstrates this for graph 3-coloring, and lecture 10 works through $x ⋅ y ⋅ z = 10$ by hand. The single-multiplication-per-row restriction is fundamental – it maps directly onto bilinear pairings later (homework 8, problem 4).

Stage 3: QAP – Quadratic Arithmetic Program (lectures 9-10, homeworks 9-10)

The R1CS matrices are converted to polynomials via Lagrange interpolation. Each column of $L, R, O$ becomes a polynomial $u_i(x)$, $v_i(x)$, $w_i(x)$ interpolated over points $x = 0, 1, \ldots, n-1$. Combining with the witness:

$l(x) = ∑_i a_i ⋅ u_i(x), \quad r(x) = ∑_i a_i ⋅ v_i(x), \quad o(x) = ∑_i a_i ⋅ w_i(x)$

The R1CS identity $L\mathbf{w} o R\mathbf{w} = O\mathbf{w}$ holding at every row translates to $l(x) ⋅ r(x) = o(x)$ at each interpolation point. Therefore $l(x) ⋅ r(x) - o(x)$ is divisible by the target polynomial $T(x) = (x-0)(x-1)\cdots(x-(n-1))$, giving:

$l(x) ⋅ r(x) - o(x) = h(x) ⋅ T(x)$

The prover computes $h(x) = \frac{l(x) ⋅ r(x) - o(x)}{T(x)}$. Succinctness comes from the Schwartz-Zippel Lemma: instead of checking this identity at every point, the verifier picks a random $τ$ and checks $l(τ) ⋅ r(τ) = o(τ) + h(τ) ⋅ T(τ)$. A false proof passes with negligible probability $\frac{°}{|\mathbb{F}|}$.

Stage 4: Trusted Setup + Elliptic Curve Commitments (lecture 11, homework 11)

The verifier shouldn’t reveal $τ$ to the prover (that would let them cheat). Solution: powers of tau in the exponent of elliptic curve points.

A trusted party generates a Structured Reference String (SRS):

• $\text{SRS}_1 = [τ^0 G_1, τ^1 G_1, τ^2 G_1, \ldots]$ for $l, o$ commitments
• $\text{SRS}_2 = [τ^0 G_2, τ^1 G_2, \ldots]$ for $r$ commitment
• $\text{SRS}_3 = [T(τ)τ^0 G_1, T(τ)τ^1 G_1, \ldots]$ for $h ⋅ T$ commitment

Then $τ$ is destroyed (“toxic waste”). The prover commits to polynomials by computing linear combinations of SRS points (never learning $τ$):

$[l(τ)]G_1 = ∑_i c_i ⋅ \text{SRS}_1[i], \quad [r(τ)]G_2 = ∑_i c_i ⋅ \text{SRS}_2[i]$

Stage 5: Verification via Pairings (lecture 6, homework 6, homework 11)

The verifier checks the QAP identity in the exponent using bilinear pairings:

$e([l]G_1, [r]G_2) = e([o]G_1 + [hT]G_1, G_2)$

This works because $e(aG_1, bG_2) = g^ab$ where $g = e(G_1, G_2)$, so the pairing equation reduces to checking $g^{l ⋅ r} = g^{o + hT}$ without anyone knowing $τ$, $l$, $r$, $o$, or $h$ in the clear.

Adding Zero Knowledge

Everything above gives a SNARK (Succinct Non-interactive Argument of Knowledge) but it is not yet zero-knowledge. The verifier learns the EC point commitments $[l]G_1$, $[r]G_2$, $[o]G_1$ which, while they don’t directly reveal the witness, could leak information (e.g., the verifier could test whether a guessed witness produces those same points).

The Pinocchio protocol / Groth16 approach adds ZK in layers:

Alpha/Beta shifting (Knowledge of Exponent)

The trusted setup includes random $α$, $β$. The prover must provide “shifted” versions of their commitments (e.g., $[α ⋅ l]G_1$). The verifier checks consistency via pairings. This prevents the prover from constructing valid-looking proofs without actually knowing the polynomials – it enforces that the proof was derived from the SRS.

Gamma/Delta partitioning

The witness is split into public inputs and private inputs. Random $γ$ and $δ$ from the trusted setup are used to separate verification of public vs private parts. The public-input check uses $γ$, the private-witness check uses $δ$. The homework 6 already demonstrates this structure:

$a ⋅ b = α ⋅ β + (x_1 + x_2 + x_3) ⋅ γ + c ⋅ δ$

Random blinding ($r$ and $s$)

This is where actual zero-knowledge enters. The prover samples fresh random scalars $r$, $s$ for each proof and adds blinding terms to the commitments:

$A’ = [l(τ)]G_1 + r ⋅ [δ]G_1$

$B’ = [r(τ)]G_2 + s ⋅ [δ]G_2$

$C’ = [o(τ) + h(τ) ⋅ T(τ)]G_1 + s ⋅ A’ + r ⋅ B’ - rs ⋅ [δ]G_1$

The cross-terms cancel in the pairing check, so verification still works. But now each proof is randomized – even for the same witness, every proof looks different. This makes the proof a perfect zero-knowledge simulator: given only the public inputs, one could generate indistinguishable “fake” proofs (with knowledge of $δ$), proving that the real proof reveals nothing beyond the statement’s truth.

In short: the SNARK gives succinctness and soundness; $α / β$ enforce correct polynomial structure; $γ / δ$ separate public from private; and the random blinding $r, s$ make it truly zero-knowledge.