The Math of zk-SNARKs

A Visual Journey from Computation to Cryptographic Proof

The High-Level Pipeline

To prove you ran a computation correctly without revealing the inputs (zk), we transform a computer program into a mathematical object that can be probabilistically checked.

Step 1 Code

→

Step 2 Arithmetic Circuit

→

Step 3 R1CS

→

Step 4 QAP

→

Step 5 Elliptic Curve Proof

1. Arithmetic Circuits

Computers use boolean logic (AND, XOR). SNARKs work over Fields (numbers modulo a prime \(p\)). We must flatten code into steps that only use Addition (+) and Multiplication (*).

Example: \(y = x^3 + x + 5\)

Suppose we want to prove we know an \(x\) such that \(x^3 + x + 5 = 35\). (Witness \(x=3\)).

We break this down into elementary operations (gates):

\begin{align} sym_1 &= x \times x \\ y &= sym_1 \times x \\ out &= y + x + 5 \end{align}

This is a circuit! To represent this mathematically, we move to R1CS.

2. Rank-1 Constraint System (R1CS)

R1CS is a system of equations where each equation looks like:

(A \cdot \mathbf{s}) \times (B \cdot \mathbf{s}) = (C \cdot \mathbf{s})

Here \(\mathbf{s}\) is our Solution Vector comprising all variables: \([1, out, x, sym_1, y]\).
Note: The 1 is necessary for constant additions.

Interactive Visualization

Let's map our witness \(x=3\) to the vector \(\mathbf{s}\).

\(x = 3\)
\(sym_1 = x \cdot x = 9\)
\(y = sym_1 \cdot x = 27\)
\(out = 35\)

Vector s: [1, 35, 3, 9, 27]

3. Quadratic Arithmetic Programs (QAP)

Checking thousands of constraints (R1CS) is slow. We want to check Polynomials instead.

Using Lagrange Interpolation, we convert the matrices \(A, B, C\) into polynomials \(A(z), B(z), C(z)\).

The Master Equation

A(z) \cdot B(z) - C(z) = H(z) \cdot Z(z)

where \(Z(z)\) is the "Vanishing Polynomial" \((z-1)(z-2)...(z-n)\), which is zero at every logic gate step. If the equation divides cleanly by \(Z(z)\), it means all constraints are satisfied simultaneously.

4. The Moon Math (Cryptographic Check)

The verifier picks a secret random point \(\tau\) (tau). The prover must evaluate the polynomials at \(\tau\). To prevent the prover from cheating or learning \(\tau\), we compute everything inside Elliptic Curve points.

Homomorphic Hiding & Pairings

We use a generator \(G\) on an Elliptic Curve. We encrypt values as \(G^x\).

The Prover computes \(G^{A(\tau)}, G^{B(\tau)}, G^{C(\tau)}\) and sends them to the Verifier.

The Verifier checks the QAP equation using a Bilinear Pairing \(e(g, g)\):

e(G^A, G^B) / e(G^C, G) \stackrel{?}{=} e(G^H, G^Z)

Because \(e(G^a, G^b) = e(G, G)^{ab}\), this checks multiplication in the exponent!