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
| Word | What it means | Example |
|---|---|---|
| Field | whole numbers mod a prime, with adding and multiplying | mod 97 |
| Gate | one sum or product with its output | |
| Witness | a value for every wire, including the secret | |
| Constraint | an equation the witness must satisfy | |
| SNARK | a 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
docker exec jupyter python3 steps/constraints.pyShown 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
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
| Gate | Constraint, left times right equals output | With x = 6 |
|---|---|---|
| x2 = x times x | x times x = x2 | 6 times 6 = 36 |
| two_x = x plus x | (x + x) times 1 = two_x | 12 times 1 = 12 |
| out = x2 plus two_x | (x2 + two_x) times 1 = out | 48 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
docker exec jupyter grep -n def circuit.pyShown 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.