Easier to read with cream paper, a tint, more contrast or larger text? Choose your colours and text, once, for every page.

Free lesson

Circuits, constraints and where SNARKs fit

After this lesson: I can write a statement about a secret as constraints and check a witness against them.

70 min lesson2 commandsZero-knowledge proofs lab: commitments, Schnorr, Fiat-Shamir and Merkle proofs in Python

Proving your age without showing your birthday

An arithmetic circuit writes a statement about a secret as small sums and products that must all hold. A SNARK is a short proof that you know values making every one of them hold.

This is how a system can check that you are over 18, or on a list, without seeing the private data.

By the end of this lesson

Note

I can write a statement about a secret as constraints and check a witness against them.

Key words

WordWhat it meansExample
Fieldwhole numbers mod a prime, with adding and multiplyingmod 97
Gateone sum or product with its output
Witnessa value for every wire, including the secret
Constraintan equation the witness must satisfy
SNARKa short proof that a witness exists, quick to check

The cells students fill in are left blank in this preview.

A statement becomes a list of gates

Take the statement "I know x with x times x plus 2 times x equal to 48". Break it into steps that each do one thing: x2 = x times x, two_x = x plus x, out = x2 plus two_x. Each step is a gate.

The prover fills in every wire, which is the witness. The public part is out = 48. Every value lives in a field, here mod 97.

Check a witness against the gates

Command
docker exec jupyter python3 steps/constraints.py

Shown here, not run. Press Start lab to type it into your own lab’s terminal.

Read what the lab printed

For x = 6 the witness is x2 = 36, two_x = 12 and out = 48, and the first bad gate is -1, meaning none. Every gate holds.

A prover with x = 5 who claims out is 48 fails at gate 2, the last addition, because 25 plus 10 is 35. A false witness cannot satisfy every gate.

Try it: gates for a cube

Code: python
F = 97  # every sum and product is taken mod 97

# Statement: "I know x with x * x * x + 2 * x = 33", and 33 is public.
gates = [
    ["mul", "x", "x", "x2"],
    ["mul", "x2", "x", "x3"],
    ["add", "x", "x", "two_x"],
    ["add", "x3", "two_x", "out"],
]

x = 3
w = {"x": x, "x2": x * x % F, "x3": x * x * x % F, "two_x": 2 * x % F, "out": 33}

for gate in gates:
    a = w[gate[1]]
    b = w[gate[2]]
    if gate[0] == "mul":
        value = a * b % F
    else:
        value = (a + b) % F
    print(gate[0], gate[1], gate[2], "->", gate[3], "holds:", value == w[gate[3]])
# Change x = 3 to x = 4 (out stays 33) and run again. Which gate fails?

A range check is made of bits

To prove a secret x is between 0 and 15 without showing it, the prover gives four bits. Two kinds of constraint check them. Each bit b must satisfy b times b equals b, which only 0 and 1 do. And the bits, weighted 1, 2, 4 and 8, must add up to x.

The lab checked 11 as 1, 1, 0, 1: true. A bit of 2 broke the first rule: false.

Worked example: gates as constraints

GateConstraint, left times right equals outputWith x = 6
x2 = x times xx times x = x26 times 6 = 36
two_x = x plus x(x + x) times 1 = two_x12 times 1 = 12
out = x2 plus two_x(x2 + two_x) times 1 = out48 times 1 = 48

The cells students fill in are left blank in this preview.

Where a SNARK comes in

So far the verifier checked the witness by seeing it, which shows the secret. A SNARK lets the prover convince the verifier that such a witness exists. The proof is a few hundred bytes and fast to check, whatever the size of the circuit.

Languages such as Noir and Circom turn a statement into constraints like these. This lab does not run them: it has no prover, so the circuit stays in Python.

List the functions in circuit.py

Command
docker exec jupyter grep -n def circuit.py

Shown here, not run. Press Start lab to type it into your own lab’s terminal.

A common mistake

Warning

Many people think a SNARK proves that the statement is sensible. It only proves that the constraints hold. If a constraint is missing, such as the bit rule, a prover can satisfy the rest with values the author never meant.

About this lab and its source: Zero-knowledge proofs lab: commitments, Schnorr, Fiat-Shamir and Merkle proofs in Python

Teaching a class? Set this module for your students with a teacher guide, marked assignments and a lab for every student.