10a-arithmetic-circuits.ipynb

Kernel: SageMath 10.5

Notebook 10a: Arithmetic Circuits

Module 10. SNARKs and STARKs

---

Motivating Question. You want to prove that you know a secret input $x$ such that $f(x) = y$, without revealing $x$. Before we can build such a proof system, we need a way to represent any computation as a structured mathematical object. Arithmetic circuits are that object, they turn programs into addition and multiplication gates over a finite field. How does $x^3 + x + 5$ become a circuit?

---

Prerequisites. You should be comfortable with:

• Finite fields $\mathbb{F}_p$ and arithmetic in them (Module 01–02)

• Polynomials over finite fields (Module 02)

Learning objectives. By the end of this notebook you will be able to:

1. Represent a computation as a directed acyclic graph (DAG) of addition and multiplication gates.

2. Flatten an algebraic expression into a sequence of elementary gates.

3. Evaluate a circuit by propagating wire values.

4. Understand why arithmetic circuits are the foundation of SNARKs and STARKs.

1. What Is an Arithmetic Circuit?

Bridge from Module 02. In Module 02, we did arithmetic in polynomial rings over finite fields. An arithmetic circuit formalizes exactly this: each gate performs one field operation (add or multiply), and wires carry field elements. And in Module 09 (Fiat-Shamir), we saw how interactive proofs become non-interactive, SNARKs apply the same transform to circuit-based proofs, turning them into a single non-interactive argument.

An arithmetic circuit over a field $\mathbb{F}$ is a directed acyclic graph (DAG) where:

• Input wires carry values from $\mathbb{F}$ (public inputs, private inputs, constants).

• Gates perform either addition ($+$) or multiplication ($\times$) on two input wires.

• Output wires carry the gate's result to subsequent gates or the final output.

Every polynomial computation, and indeed every computation that can be expressed over a finite field, can be written as an arithmetic circuit.

# Let's work over a small prime field for clarity
p = 97  # small prime
F = GF(p)
print(f"Working over F_{p} = {{0, 1, 2, ..., {p-1}}}")
print(f"All arithmetic is mod {p}")
print(f"\nExample: 50 + 60 = {F(50) + F(60)} (not 110)")
print(f"Example: 10 * 10 = {F(10) * F(10)} (not 100)")

2. A Concrete Circuit: $f(x) = x^3 + x + 5$

Let's trace how the computation $f(x) = x^3 + x + 5$ becomes a circuit.

Step 1: Identify the operations.

• $x \times x = x^2$ (multiplication gate)

• $x^2 \times x = x^3$ (multiplication gate)

• $x^3 + x$ (addition gate)

• $(x^3 + x) + 5$ (addition gate)

Step 2: Draw the circuit.

    x ──┬──────────────────┐
        │                  │
        ├──┐               │
        │  │               │
       [× ]  ← gate 1     │
        │                  │
       w1 = x²            │
        │                  │
        ├──── x ──┐       │
        │         │       │
       [× ]  ← gate 2    │
        │                 │
       w2 = x³           │
        │                 │
        ├──── x ──────────┘
        │         │
       [+ ]  ← gate 3
        │
       w3 = x³ + x
        │
        ├──── 5
        │     │
       [+ ]  ← gate 4
        │
       w4 = x³ + x + 5  (OUTPUT)

Four gates, two multiplications, two additions. This is the flattened form of $f(x)$.

# Represent the circuit as a list of gates
# Each gate: (operation, left_input, right_input, output_wire)
# Wire names: 'x' for input, 'one' for constant 1, 'w1','w2',... for intermediates

circuit = [
    ('mul', 'x',  'x',    'w1'),  # w1 = x * x = x²
    ('mul', 'w1', 'x',    'w2'),  # w2 = w1 * x = x³
    ('add', 'w2', 'x',    'w3'),  # w3 = w2 + x = x³ + x
    ('add', 'w3', 'five', 'w4'),  # w4 = w3 + 5 = x³ + x + 5
]

print("Circuit for f(x) = x³ + x + 5:")
for i, (op, l, r, o) in enumerate(circuit):
    symbol = '×' if op == 'mul' else '+'

3. Evaluating the Circuit

Given an input $x$, we propagate values through the circuit by evaluating each gate in order.

def evaluate_circuit(circuit, inputs, F):
    """
    Evaluate an arithmetic circuit over field F.
    inputs: dict mapping wire names to field values.
    Returns: dict of all wire values.
    """
    wires = dict(inputs)  # copy inputs
    
    for op, left, right, out in circuit:
        l_val = F(wires[left])
        r_val = F(wires[right])
        if op == 'mul':
            wires[out] = l_val * r_val
        elif op == 'add':
            wires[out] = l_val + r_val
        else:
            raise ValueError(f"Unknown operation: {op}")
    
    return wires


# Evaluate f(3) = 27 + 3 + 5 = 35
x_val = F(3)
inputs = {'x': x_val, 'five': F(5)}
wires = evaluate_circuit(circuit, inputs, F)

print(f"Input: x = {x_val}")
print(f"\nWire values:")
for name, val in wires.items():
    print(f"  {name} = {val}")
print(f"\nOutput: f({x_val}) = {wires['w4']}")
print(f"Check:  {x_val}³ + {x_val} + 5 = {x_val^3 + x_val + 5}")

# Try several inputs to see the circuit in action
for x in range(10):
    wires = evaluate_circuit(circuit, {'x': F(x), 'five': F(5)}, F)

Checkpoint 1. Every wire in the circuit carries a field element. The complete set of wire values, input wires, intermediate wires, and output wires, is called the witness (or trace). This witness is what a prover will later claim to know, and what a verifier will check.

4. Flattening: From Expressions to Circuits

Any algebraic expression can be flattened into a circuit where each gate has exactly one operation. The key rule: each gate output gets its own wire name.

Let's flatten a more complex expression: $g(x, y) = x^2 y + 3xy + 2$.

# Flatten g(x, y) = x²y + 3xy + 2
#
# Step by step:
#   w1 = x * x       (x²)
#   w2 = w1 * y      (x²y)
#   w3 = x * y       (xy)
#   w4 = 3 * w3      (3xy)   . Note: multiplication by constant
#   w5 = w2 + w4     (x²y + 3xy)
#   w6 = w5 + 2      (x²y + 3xy + 2)

circuit_g = [
    ('mul', 'x',     'x',     'w1'),  # w1 = x²
    ('mul', 'w1',    'y',     'w2'),  # w2 = x²y
    ('mul', 'x',     'y',     'w3'),  # w3 = xy
    ('mul', 'three', 'w3',    'w4'),  # w4 = 3xy
    ('add', 'w2',    'w4',    'w5'),  # w5 = x²y + 3xy
    ('add', 'w5',    'two',   'w6'),  # w6 = x²y + 3xy + 2
]

# Evaluate g(4, 5) = 16*5 + 3*4*5 + 2 = 80 + 60 + 2 = 142 mod 97 = 45
inputs_g = {'x': F(4), 'y': F(5), 'three': F(3), 'two': F(2)}
wires_g = evaluate_circuit(circuit_g, inputs_g, F)

print("Circuit for g(x, y) = x²y + 3xy + 2:")
print(f"\nInputs: x = {inputs_g['x']}, y = {inputs_g['y']}")
for name in ['w1', 'w2', 'w3', 'w4', 'w5', 'w6']:
    print(f"  {name} = {wires_g[name]}")
print(f"\nDirect computation: {F(4)^2 * F(5) + 3*F(4)*F(5) + 2}")
print(f"Circuit output:     {wires_g['w6']}")
print(f"Match? {wires_g['w6'] == F(4)^2 * F(5) + 3*F(4)*F(5) + 2}")

5. Circuit Size and Depth

Two key metrics for an arithmetic circuit:

Metric	Definition	Why It Matters
Size	Total number of gates	Determines proof generation time
Depth	Longest path from input to output	Affects parallelizability
Multiplicative size	Number of multiplication gates only	Key for R1CS/QAP (next notebooks)

Addition gates are "free" in many proof systems (they can be absorbed into the constraint structure). Multiplication gates are the expensive ones.

def circuit_stats(circuit):
    """Compute size and multiplicative size of a circuit."""
    total = len(circuit)
    muls = sum(1 for op, _, _, _ in circuit if op == 'mul')
    adds = sum(1 for op, _, _, _ in circuit if op == 'add')
    return total, muls, adds

print("Circuit for f(x) = x³ + x + 5:")
total, muls, adds = circuit_stats(circuit)
print(f"  Total gates: {total}, Multiplications: {muls}, Additions: {adds}")

print("\nCircuit for g(x,y) = x²y + 3xy + 2:")
total_g, muls_g, adds_g = circuit_stats(circuit_g)
print(f"  Total gates: {total_g}, Multiplications: {muls_g}, Additions: {adds_g}")

print(f"\nIn R1CS (next notebook), each multiplication gate becomes one constraint.")
print(f"So f(x) needs {muls} constraints, and g(x,y) needs {muls_g} constraints.")

Checkpoint 2. The number of multiplication gates in a circuit directly determines the number of constraints in the R1CS representation, and hence the size of the SNARK proof's trusted setup and proving time. Minimizing multiplication gates is a key optimization in zero-knowledge circuit design.

6. Constants and Public vs. Private Inputs

In a zero-knowledge setting, wires are classified as:

Type	Who knows it	Example
Public input (instance)	Everyone	The claimed output $y$
Private input (witness)	Prover only	The secret $x$ such that $f(x) = y$
Constant	Hardcoded	The 5 in $f(x) = x^3 + x + 5$
Intermediate	Prover computes	Wire values $w_1, w_2, \ldots$

The prover's goal: convince the verifier that there exists a private input making the circuit output equal the public input, without revealing the private input.

# Scenario: "I know x such that x³ + x + 5 = 35 (mod 97)"
#
# Public:  output = 35
# Private: x = 3  (the secret)
# The prover knows x=3; the verifier knows only the output 35.

public_output = F(35)
secret_x = F(3)

# Prover evaluates the circuit (knows everything)
prover_wires = evaluate_circuit(circuit, {'x': secret_x, 'five': F(5)}, F)

print("=== Prover's View ===")
print(f"Secret input: x = {secret_x}")
for name, val in prover_wires.items():
    print(f"  {name} = {val}")

print(f"\n=== Verifier's View ===")
print(f"Public output: f(x) = {public_output}")
print(f"Claim: 'I know x such that f(x) = {public_output}'")
print(f"Verifier does NOT know x, w1, w2, w3.")
print(f"\nGoal: convince verifier this claim is true without revealing x.")

7. More Complex Circuits

Let's build a circuit for a more interesting computation: checking that a Sudoku cell constraint holds.

Example: Prove that $a \neq b$ over $\mathbb{F}_p$. One way: prove that there exists $w$ such that $(a - b) \cdot w = 1$. (If $a = b$ then $a - b = 0$ and no such $w$ exists.)

# Circuit for "a ≠ b": prove existence of w such that (a - b) * w = 1
circuit_neq = [
    ('add', 'a',    'neg_b', 'diff'),  # diff = a + (-b) = a - b
    ('mul', 'diff', 'w',     'out'),   # out = diff * w = (a-b)*w
    # Constraint: out must equal 1
]

# Case 1: a=7, b=3 → a-b=4, w=4^(-1) mod 97
a, b = F(7), F(3)
diff = a - b
w = diff^(-1)  # multiplicative inverse exists because a ≠ b

wires_neq = evaluate_circuit(circuit_neq, {'a': a, 'neg_b': -b, 'w': w}, F)
print(f"Proving {a} ≠ {b}:")
print(f"  a - b = {diff}")
print(f"  w = (a-b)⁻¹ = {w}")
print(f"  (a-b) * w = {wires_neq['out']} (should be 1)")

# Case 2: a=5, b=5 → a-b=0, no w exists
print(f"\nTrying to prove {F(5)} ≠ {F(5)}:")
print(f"  a - b = {F(5) - F(5)} = 0")
print(f"  0 has no multiplicative inverse → no valid witness exists!")
print(f"  The prover CANNOT make a false claim.")

8. Boolean Circuits vs. Arithmetic Circuits

You might be familiar with Boolean circuits (AND, OR, NOT gates). Arithmetic circuits are their field-element generalization.

Boolean Circuits	Arithmetic Circuits
Wires carry bits (0 or 1)	Wires carry field elements
AND, OR, NOT gates	ADD ($+$), MUL ($\times$) gates
Used in traditional CS complexity	Used in SNARKs/STARKs

We can enforce Boolean constraints in an arithmetic circuit: to ensure wire $b$ is Boolean, add the constraint $b \times (1 - b) = 0$. This forces $b \in \{0, 1\}$.

# Boolean constraint: b * (1 - b) = 0
print("Boolean constraint: b × (1 - b) = 0")
for b_val in range(5):
    b = F(b_val)
    result = b * (1 - b)
    is_bool = (result == 0)

print(f"\nOnly b=0 and b=1 satisfy the constraint!")
print(f"This is how arithmetic circuits enforce bit values.")

Misconception alert. "Arithmetic circuits can only handle numbers." Wrong! By enforcing Boolean constraints on wires, you can embed any Boolean computation inside an arithmetic circuit. SHA-256, AES, comparisons, if-else, all can be expressed as arithmetic circuits, though the circuit size may be large.

9. Circuit for a Hash Preimage Proof

A classic ZK application: "I know a preimage $x$ such that $\text{hash}(x) = h$."

Real hash functions have massive circuits (SHA-256 ≈ 25,000 gates). Let's use a toy "hash" to illustrate the concept: $\text{hash}(x) = x^5 + 3x + 7 \bmod p$.

# Toy hash: hash(x) = x^5 + 3x + 7 mod p
circuit_hash = [
    ('mul', 'x',  'x',     'w1'),   # w1 = x²
    ('mul', 'w1', 'w1',    'w2'),   # w2 = x⁴
    ('mul', 'w2', 'x',     'w3'),   # w3 = x⁵
    ('mul', 'three', 'x',  'w4'),   # w4 = 3x
    ('add', 'w3', 'w4',    'w5'),   # w5 = x⁵ + 3x
    ('add', 'w5', 'seven', 'w6'),   # w6 = x⁵ + 3x + 7
]

# "Hash" a secret value
secret = F(42)
hash_inputs = {'x': secret, 'three': F(3), 'seven': F(7)}
hash_wires = evaluate_circuit(circuit_hash, hash_inputs, F)
h = hash_wires['w6']

print(f"Secret preimage: x = {secret}")
print(f"Hash output:     h = hash({secret}) = {h}")
print(f"\nZK claim: 'I know x such that hash(x) = {h}'")
print(f"Verifier sees:   h = {h}")
print(f"Verifier doesn't see: x = {secret}")

total_h, muls_h, adds_h = circuit_stats(circuit_hash)
print(f"\nCircuit size: {total_h} gates ({muls_h} muls, {adds_h} adds)")
print(f"R1CS constraints needed: {muls_h}")

Crypto foreshadowing. In real ZK systems:

• Zcash uses a circuit for the Pedersen hash and EdDSA signature verification (~100K gates)

• zkEVM projects encode the entire Ethereum Virtual Machine as an arithmetic circuit (~millions of gates)

• The circuit is compiled once; then any execution can be proven

10. Exercises

Exercise 1 (Worked): Flatten and Evaluate

Problem. Flatten $h(x) = (x + 1)^2 + x$ into an arithmetic circuit. Evaluate it at $x = 10$ over $\mathbb{F}_{97}$.

Solution:

# Exercise 1: Worked solution
# h(x) = (x + 1)^2 + x
#   w1 = x + 1
#   w2 = w1 * w1    (= (x+1)²)
#   w3 = w2 + x     (= (x+1)² + x)

circuit_h = [
    ('add', 'x',  'one', 'w1'),  # w1 = x + 1
    ('mul', 'w1', 'w1',  'w2'),  # w2 = (x+1)²
    ('add', 'w2', 'x',   'w3'),  # w3 = (x+1)² + x
]

wires_h = evaluate_circuit(circuit_h, {'x': F(10), 'one': F(1)}, F)
print(f"h(10) via circuit: {wires_h['w3']}")
print(f"h(10) directly:    {(F(10)+1)^2 + F(10)}")
print(f"Match? {wires_h['w3'] == (F(10)+1)^2 + F(10)}")

total_h, muls_h, adds_h = circuit_stats(circuit_h)
print(f"\nGates: {total_h} total, {muls_h} multiplication(s)")

Exercise 2 (Guided): Multi-Variable Circuit

Problem. Flatten $f(a, b, c) = a \cdot b + b \cdot c + a$ into a circuit. Evaluate at $a=2, b=3, c=5$ over $\mathbb{F}_{97}$.

Fill in the TODOs:

# Exercise 2: fill in the TODOs

# TODO 1: Define the flattened circuit
# circuit_f = [
#     ('mul', 'a', 'b', 'w1'),   # w1 = a*b
#     ('mul', ???, ???, 'w2'),    # w2 = b*c
#     ('add', ???, ???, 'w3'),    # w3 = a*b + b*c
#     ('add', ???, ???, 'w4'),    # w4 = a*b + b*c + a
# ]

# TODO 2: Evaluate at a=2, b=3, c=5
# inputs_f = {'a': F(2), 'b': F(3), 'c': F(5)}
# wires_f = evaluate_circuit(circuit_f, inputs_f, F)
# print(f"f(2,3,5) = {wires_f['w4']}")

# TODO 3: Verify with direct computation
# print(f"Direct: {F(2)*F(3) + F(3)*F(5) + F(2)}")

Exercise 3 (Independent): Inequality Circuit

Problem.

1. Build a circuit that proves $x^2 = y$ (i.e., $x$ is a square root of $y$).

2. Identify which wires are public (verifier sees $y$) and private (prover knows $x$).

3. Test with $y = 16 \bmod 97$. Find both square roots and show the circuit accepts both.

4. Try $y = 3 \bmod 97$, does a square root exist? (Hint: check if $3$ is a quadratic residue mod $97$.)

# Exercise 3: write your solution here

Summary

Concept	Key Fact
Arithmetic circuit	DAG of $+$ and $\times$ gates over a field $\mathbb{F}_p$
Flattening	Any algebraic expression → sequence of elementary gates
Wire values	Complete evaluation trace = the witness
Circuit size	Number of gates; multiplicative gates matter most
Public vs. private	Verifier sees public inputs/outputs; prover knows all wire values
Boolean in arithmetic	Enforce $b(1-b) = 0$ to constrain a wire to $\{0, 1\}$

Arithmetic circuits are the universal language of zero-knowledge proof systems. In the next notebook, we'll transform these circuits into a mathematical constraint system called R1CS, the first step toward building a SNARK.

---

Next: 10b: R1CS Constraints