From Computation to Polynomials

In Module 1, we assembled our mathematical toolkit. Now it's time to ask a deeper question:

How can we encode an entire computation — every step, every intermediate value — into a single polynomial divisibility check?

We will follow a natural progression:

1. Arithmetic Circuits — represent any computation as a graph of wires and gates.
2. R1CS — translate that graph into algebraic constraints.
3. Schwartz–Zippel Lemma — learn why checking one random point is enough.
4. QAP — lift R1CS into polynomials, so satisfying constraints becomes divisibility.
5. Knowledge of Exponent & Encrypted Arithmetic — hide all values so the verifier checks everything without seeing anything.

Running example. Throughout this module we use the computation $y = x^3 + x^2$. Simple enough to follow by hand, rich enough to illustrate every idea.

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.

1. Arithmetic Circuits

When we write $y = x^3 + x^2$, we think of it as a single formula. But a proof system executes it one operation at a time:

Every value is a wire ($C_i$). The operations are gates. Both the prover (Philip) and the verifier (Veronica) know the circuit structure. But only Philip knows the wire values. Veronica only knows input $C_1 = x$ and output $C_5 = y$.

The challenge: how can Philip prove he computed all intermediate values correctly, without Veronica re-doing the computation?

The Rust snippet below makes that circuit explicit. It hardcodes the gates for $y = x^3 + x^2$, evaluates them one by one, and records every intermediate wire value in the witness.

Key Observations

• Any computation can be broken into multiplication and addition gates.
• The number of multiplication gates determines the cost of the proof. Our circuit has 3 multiplication gates and 1 addition gate.
• The full list of wire values $(C_1, C_2, C_3, C_4, C_5)$ is called the witness.

2. Rank-1 Constraint Systems (R1CS)

To do algebra with a circuit, we turn it into equations. Every multiplication gate gives:

For our circuit:

The addition gate has not disappeared. It is a purely linear relation, so we can write it as:

In the compact matrix view below, we keep the three multiplicative rows explicit and then check this final linear relation separately. That is also the reason additions will look cheaper later on: they do not contribute a new multiplication constraint.

Matrix Representation

Collect all wire values into a witness vector:

The leading $1$ is there so constraints can include constant terms. Without it, rows could only describe linear combinations of witness wires. With it, a row can also encode expressions like $C_3 + C_4 - C_5$ or, more generally, things such as $x + 5$ by putting the constant in the first column. Even in our example, the linear relation $(C_3 + C_4) \cdot 1 - C_5 = 0$ uses this idea.

With columns ordered as $(1,\; C_1,\; C_2,\; C_3,\; C_4,\; C_5)$, the three multiplicative gates give the concrete matrices:

Each row corresponds to one multiplication gate, and each column corresponds to one witness entry. The addition gate still sits outside these three rows as the separate linear check $C_3 + C_4 = C_5$.

Each multiplicative constraint becomes a row in $\mathbf{L}, \mathbf{R}, \mathbf{O}$. The R1CS is satisfied when, element-wise:

The R1CS is a clean algebraic representation. But checking it directly means one check per gate — millions of gates means millions of checks. We need something more succinct.

3. The Schwartz–Zippel Lemma

Two different polynomials of degree $n$ can agree on at most $n$ points. If we pick a random point $s$ from a field with $p \approx 2^{256}$ elements:

For $n = 10^6$ and $p = 2^{256}$, this probability is astronomically small.

Schwartz–Zippel Lemma. You can check polynomial equality everywhere by checking at just one random point.

4. Quadratic Arithmetic Programs (QAP)

A Quadratic Arithmetic Program is the polynomial form of our R1CS. Instead of checking each gate one by one, we encode the whole system into a few polynomials and reduce correctness to a single divisibility check.

This is the key compression step: many local circuit constraints become one global algebraic statement that we can later test at a secret random point.

The plan is:

1. Assign gate $k$ the value $k = 1, 2, 3$
2. Encode each column of the R1CS matrices as a polynomial via Lagrange interpolation
3. Combine with wire values into $L(x), R(x), O(x)$
4. Show that $W(x) = L(x) \cdot R(x) - O(x)$ is divisible by $G(x) = (x-1)(x-2)(x-3)$ if and only if all R1CS constraints are satisfied.

Step 1 — Gate Roots

Here the $x$ in $G(x)$ is a formal polynomial variable, not the circuit input $x$ from $y = x^3 + x^2$. We use the points $x = 1, 2, 3$ to label the three multiplication gates, so evaluating a polynomial at one of these values means “look at that gate”.

Step 2 — Sub-Polynomials

For each wire $C_i$, define sub-polynomials by their values at each gate index:

The index $i$ tells us which witness wire we are talking about. The argument $x$ tells us which gate position we are querying. Concretely:

$L_i(k)$ is the coefficient of wire $C_i$ on the left input of gate $k$, $R_i(k)$ is its coefficient on the right input, and $O_i(k)$ is its coefficient on the output.

For example, $L_1$ has values $(1, 0, 1)$ because wire $C_1$ appears on the left side of gates 1 and 3, but not gate 2. Likewise,$O_3$ has values $(0, 1, 0)$ because wire $C_3$ is the output of gate 2 only.

This is exactly the link with the R1CS matrices: each sub-polynomial is obtained from one column of $\mathbf{L}, \mathbf{R}, \mathbf{O}$. For instance, the $C_1$ column of $\mathbf{L}$ is $(1, 0, 1)$, so interpolating those three gate values gives $L_1(x)$. The $C_3$ column of $\mathbf{O}$ is $(0, 1, 0)$, so it becomes $O_3(x)$.

So the QAP is not inventing new information: it is just turning each relevant matrix column into a polynomial that can be evaluated at gate positions. Columns that are all zero correspond to the zero polynomial and are usually omitted from the notation.

Steps 3 & 4 — Build and Check

These are the combined polynomials for one specific witness. When we plug in a gate index $k$, they recover the three linear forms of that gate:

If all constraints are satisfied, then $W(k) = L(k) \cdot R(k) - O(k) = 0$ for every gate $k$, so $G(x)$ divides $W(x)$:

Why does vanishing at the same points imply divisibility? By the factor theorem, if $W(1) = 0$ then $(x-1)$ is a factor of $W(x)$. The same holds for $x = 2$ and $x = 3$. Since these are distinct roots, all three linear factors multiply together, so:

That is exactly why the target polynomial $G(x) = (x-1)(x-2)(x-3)$ is chosen this way: it collects the gate roots into a single polynomial. If $G(x)$ divides $W(x)$, then $W(x)$ automatically vanishes at every gate position.

Now we can separate what is public from what is private. The circuit structure, the gate indices, the target polynomial $G(x)$, and the sub-polynomials $L_i(x), R_i(x), O_i(x)$ are fixed entirely by the circuit, so they are public and known by everyone.

By contrast, the combined polynomials $L(x), R(x), O(x), W(x), H(x)$ depend on the actual witness values used by the prover. In our example, the circuit and the public input/output $x$ and $y$ are known, while intermediate values like $C_2, C_3, C_4$ remain private.

This is the core of the QAP: satisfying all constraints ⇔ $W(x)$ is divisible by $G(x)$.

The following code builds the full QAP for $y = x^3 + x^2$ with $x = 3$ using arkworks:

Addition Gates Come for Free

Notice we only assigned gate indices to multiplication gates. The addition gate ($C_5 = C_3 + C_4$) never appeared explicitly. Addition constraints are folded into the sub-polynomials of adjacent multiplication gates — they don't increase the degree of the QAP.

This is why proof cost scales with the number of multiplication gates, not total operations.

Try it yourself — build your own circuit

Now that the QAP construction is on the table, you can play with the circuit directly. Pick an input $x$, add gates, and watch the witness and the resulting $L(\tau), R(\tau), O(\tau), W(\tau)$ polynomials update in real time.

5. Knowledge of Exponent & Encrypted Arithmetic

Up to now, our QAP check has been completely in the clear. Philip and Veronica can both talk about $L(s), R(s), O(s), H(s)$as ordinary field elements. But a real proof system cannot simply reveal all of these values, because they are built from the prover's private witness.

The next step is therefore cryptographic: keep the same algebraic check, but hide the values inside group elements so Veronica can verify correctness without learning the witness. This is where knowledge of exponent and pairings enter the picture.

We have the divisibility check $W(s) = G(s) \cdot H(s)$ at a secret point $s$. But if Veronica sends $s$ to Philip, he could cheat — just pick any $h$, set $w = G(s) \cdot h$, and it passes.

Doing Math in the Exponent

Raising $g$ to a power is one-way (discrete log). We can encrypt a value $x$ as $g^x$. The exponent rules give us:

• Encrypted addition: $g^x \cdot g^y = g^{x+y}$
• Multiply encrypted by scalar: $(g^x)^y = g^{xy}$
• Cannot multiply two encrypted values with exponent rules alone.

Evaluating a Polynomial in the Exponent

Veronica precomputes $g^1, g^s, g^{s^2}, \ldots, g^{s^N}$ and sends them to Philip. He computes:

Philip evaluates $H$ at the secret point $s$ entirely in the exponent, without ever knowing $s$.

The Knowledge-of-Exponent Assumption

Here Veronica is the verifier and Philip is the prover. Veronica samples a secret $\alpha$ that only she knows. For each public circuit term, she gives Philip two encrypted versions: the plain one $g^{L_i(s)}$ and the $\alpha$-tagged one $g^{\alpha L_i(s)}$.

Philip then combines these public encodings using his private witness coefficients, producing both $g^{L(s)}$ and $g^{\alpha L(s)}$. The key point is that Philip never learns $\alpha$ itself: he only sees encodings that already contain it in the exponent.

The knowledge-of-exponent assumption says, informally, that if the prover can output a pair with the correct hidden $\alpha$-relation, then he must have actually built it from Veronica's provided pieces rather than forged it from scratch. In other words, Philip cannot fake the $g^{\alpha L(s)}$ part unless he uses the same witness combination as in $g^{L(s)}$.

Intuition: Veronica's secret $\alpha$ acts like a hidden watermark chosen by the verifier. If the prover combines the public encodings honestly, the watermark is preserved in the second term. If he tries to cheat, he does not know $\alpha$, so he cannot reproduce that same hidden relation.

Encrypted Multiplication via Pairings

Pairings solve the final piece: multiplying two encrypted values.

Recall the plain QAP identity we want to verify at the secret point $s$:

If these values were public, Veronica could check that equation directly. But they are hidden inside group elements such as $g^{L(s)}$ and $g^{R(s)}$. Pairings let her recover the product in the exponent, while ordinary group multiplication lets her add exponents on the right-hand side.

So the verifier checks the encrypted version of the same identity:

The left-hand side encodes $L(s)R(s)$. The right-hand side encodes $O(s)$ and $G(s)H(s)$, whose exponents add together. So this pairing equation is exactly the hidden form of $L(s)R(s) = O(s) + G(s)H(s)$.

Veronica checks this using only encrypted values — she never sees $L(s), R(s), O(s)$, or $H(s)$ in the clear.

6. Exercise: Build a QAP from Scratch

Now it's your turn. Build a QAP for the simplest possible circuit — a single multiplication $z = a \cdot b$ with $a = 4, b = 5, z = 20$. Only one multiplication gate means the target polynomial is just $G(x) = (x - 1)$, and each sub-polynomial is a constant. The reference solution below checks divisibility and then verifies $W(s) = G(s) \cdot H(s)$ at a random Schwartz–Zippel point $s$:

With the QAP and pairing-based checks in place, we are ready to turn this into a full zkSNARK. In the next module we add trusted setup, zero-knowledge blinding, and the full Groth16 verification equation on BLS12-381.