10b-r1cs-constraints.ipynb

Kernel: SageMath 10.5

Notebook 10b: R1CS Constraints

Module 10. SNARKs and STARKs

---

Motivating Question. We can represent computations as arithmetic circuits with addition and multiplication gates (Notebook 10a). But proof systems need a more structured format, one where every constraint has the same shape. Rank-1 Constraint Systems (R1CS) rewrite each multiplication gate as a matrix equation: $(A_i \cdot s) \times (B_i \cdot s) = (C_i \cdot s)$. How do we transform a circuit into matrices, and what is the "witness" vector $s$?

---

Prerequisites. You should be comfortable with:

• Arithmetic circuits and flattening (Notebook 10a)

• Matrix-vector operations over finite fields (Module 02)

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

1. Transform an arithmetic circuit into R1CS matrices $A$, $B$, $C$.

2. Construct the witness vector $s$ from a circuit evaluation.

3. Verify that a witness satisfies all R1CS constraints.

4. Understand why R1CS is the standard intermediate representation for SNARKs.

1. From Circuits to Constraints

Bridge from Notebook 10a. In the previous notebook, we represented $f(x) = x^3 + x + 5$ as a sequence of gates. Now we'll convert each multiplication gate into a rank-1 constraint. Addition gates get absorbed into the constraint structure, they're free!

A Rank-1 Constraint System over a field $\mathbb{F}$ consists of:

• A witness vector $s \in \mathbb{F}^n$ containing all wire values (including a leading $1$).

• Three matrices $A, B, C \in \mathbb{F}^{m \times n}$, one row per constraint.

• The constraint: for each row $i$, $(A_i \cdot s) \times (B_i \cdot s) = (C_i \cdot s)$.

Each multiplication gate becomes one row. Addition gates are incorporated by adjusting matrix entries.

# Working field
p = 97
F = GF(p)
print(f"Working over F_{p}")

2. The Witness Vector

For our running example $f(x) = x^3 + x + 5$, the flattened circuit is:

Gate	Operation	Constraint
1	$w_1 = x \times x$	multiplication
2	$w_2 = w_1 \times x$	multiplication
3	$w_3 = w_2 + x$	addition (free!)
4	$w_4 = w_3 + 5$	addition (free!)

The witness vector contains all values: $$s = (1, x, w_1, w_2, w_3, w_4)$$

The leading $1$ is a convention that lets us include constants in constraints.

# Build the witness for x = 3
x = F(3)
w1 = x * x       # x²  = 9
w2 = w1 * x      # x³  = 27
w3 = w2 + x      # x³ + x = 30
w4 = w3 + F(5)   # x³ + x + 5 = 35

# Witness vector: s = [1, x, w1, w2, w3, w4]
s = vector(F, [1, x, w1, w2, w3, w4])

wire_names = ['one', 'x', 'w1', 'w2', 'w3', 'w4']
print("Witness vector s:")
for name, val in zip(wire_names, s):
    print(f"  s[{name}] = {val}")
print(f"\nOutput: f({x}) = {w4}")

3. Building the R1CS Matrices

Each multiplication gate becomes a constraint $(A_i \cdot s) \times (B_i \cdot s) = (C_i \cdot s)$.

Gate 1: $w_1 = x \times x$

• Left input: $x$ → $A_1 \cdot s = x$, so $A_1 = [0, 1, 0, 0, 0, 0]$

• Right input: $x$ → $B_1 \cdot s = x$, so $B_1 = [0, 1, 0, 0, 0, 0]$

• Output: $w_1$ → $C_1 \cdot s = w_1$, so $C_1 = [0, 0, 1, 0, 0, 0]$

Gate 2: $w_2 = w_1 \times x$

• Left: $w_1$ → $A_2 = [0, 0, 1, 0, 0, 0]$

• Right: $x$ → $B_2 = [0, 1, 0, 0, 0, 0]$

• Output: $w_2$ → $C_2 = [0, 0, 0, 1, 0, 0]$

What about the addition gates? Gate 3 says $w_3 = w_2 + x$. We don't create a separate constraint, instead, wherever $w_3$ appears later, we substitute $w_2 + x$. Gate 4 says $w_4 = w_3 + 5 = w_2 + x + 5$. We add an output constraint: $w_4 = w_2 + x + 5$, which can be written as the multiplication $1 \times (w_2 + x + 5) = w_4$.

Gate 3 (output): $1 \times (w_2 + x + 5) = w_4$

• Left: $1$ → $A_3 = [1, 0, 0, 0, 0, 0]$

• Right: $w_2 + x + 5$ → $B_3 = [5, 1, 0, 1, 0, 0]$ (the 5 is in the one position)

• Output: $w_4$ → $C_3 = [0, 0, 0, 0, 0, 1]$

# Wire indices: one=0, x=1, w1=2, w2=3, w3=4, w4=5
#                0  1  2  3  4  5

# Constraint 1: x * x = w1
A1 = vector(F, [0, 1, 0, 0, 0, 0])
B1 = vector(F, [0, 1, 0, 0, 0, 0])
C1 = vector(F, [0, 0, 1, 0, 0, 0])

# Constraint 2: w1 * x = w2
A2 = vector(F, [0, 0, 1, 0, 0, 0])
B2 = vector(F, [0, 1, 0, 0, 0, 0])
C2 = vector(F, [0, 0, 0, 1, 0, 0])

# Constraint 3: 1 * (w2 + x + 5) = w4
A3 = vector(F, [1, 0, 0, 0, 0, 0])
B3 = vector(F, [5, 1, 0, 1, 0, 0])  # 5·one + x + w2
C3 = vector(F, [0, 0, 0, 0, 0, 1])

# Assemble into matrices
A = matrix(F, [A1, A2, A3])
B = matrix(F, [B1, B2, B3])
C = matrix(F, [C1, C2, C3])

print("R1CS matrices for f(x) = x³ + x + 5:")
print(f"\nWire order: {wire_names}")
print(f"\nA = {A}")
print(f"B = {B}")
print(f"C = {C}")
print(f"\nConstraints: {A.nrows()} (one per multiplication gate + output)")

4. Checking the Witness

A witness $s$ satisfies R1CS if and only if for every row $i$: $$(A_i \cdot s) \times (B_i \cdot s) = C_i \cdot s$$

def check_r1cs(A, B, C, s):
    """Check if witness s satisfies R1CS constraints A, B, C."""
    m = A.nrows()
    all_ok = True
    for i in range(m):
        lhs = (A[i] * s) * (B[i] * s)  # (A_i · s) × (B_i · s)
        rhs = C[i] * s                   # C_i · s
        ok = (lhs == rhs)
        print(f"  Constraint {i+1}: ({A[i]*s}) × ({B[i]*s}) = {lhs}, C·s = {rhs}  {'✓' if ok else '✗'}")
        all_ok = all_ok and ok
    return all_ok


print(f"Witness: s = {list(s)}")
print(f"Wire names: {wire_names}")
print()
valid = check_r1cs(A, B, C, s)
print(f"\nAll constraints satisfied? {valid}")

# What happens with a WRONG witness?
print("=== Wrong witness (w1 tampered) ===")
s_bad = vector(F, [1, 3, 10, 27, 30, 35])  # w1 should be 9, not 10
valid_bad = check_r1cs(A, B, C, s_bad)
print(f"Satisfied? {valid_bad}")

print("\n=== Wrong witness (output tampered) ===")
s_bad2 = vector(F, [1, 3, 9, 27, 30, 42])  # w4 should be 35, not 42
valid_bad2 = check_r1cs(A, B, C, s_bad2)
print(f"Satisfied? {valid_bad2}")

Checkpoint 1. R1CS is a completeness and soundness check:

• Completeness: If the prover honestly evaluates the circuit, the witness satisfies all constraints.

• Soundness: If any wire value is wrong, at least one constraint will fail.

The matrices $A$, $B$, $C$ are public. Only the witness $s$ is (partially) secret.

5. Why Only Multiplication Gates?

Addition gates don't become separate constraints because addition is linear. If $w_3 = w_2 + x$, we can always substitute $w_2 + x$ wherever $w_3$ appears in the A, B, or C vectors.

Multiplication is the only non-linear operation, so it's the only one that needs its own constraint.

Operation	R1CS Cost	Why
$a \times b = c$	1 constraint	Non-linear, needs explicit check
$a + b = c$	0 constraints	Linear, absorbed into adjacent constraints
$k \cdot a = c$ (constant mul)	0 constraints	Linear, absorbed as coefficient

This is why circuit designers count multiplication gates as the true measure of circuit complexity.

6. A Second Example: $g(x) = x^2 + x + 1$

Let's build R1CS for a simpler function to reinforce the process.

# g(x) = x² + x + 1
# Flattening:
#   w1 = x * x       (multiplication)
#   out = w1 + x + 1  (addition, absorbed)

# Witness: s = [one, x, w1, out]
# Only 1 multiplication constraint + 1 output constraint

# Constraint 1: x * x = w1
#   A = [0, 1, 0, 0], B = [0, 1, 0, 0], C = [0, 0, 1, 0]

# Constraint 2: 1 * (w1 + x + 1) = out
#   A = [1, 0, 0, 0], B = [1, 1, 1, 0], C = [0, 0, 0, 1]

A_g = matrix(F, [
    [0, 1, 0, 0],
    [1, 0, 0, 0],
])
B_g = matrix(F, [
    [0, 1, 0, 0],
    [1, 1, 1, 0],  # 1 + x + w1
])
C_g = matrix(F, [
    [0, 0, 1, 0],
    [0, 0, 0, 1],
])

# Test with x = 7: g(7) = 49 + 7 + 1 = 57
x_g = F(7)
s_g = vector(F, [1, x_g, x_g^2, x_g^2 + x_g + 1])

print(f"g(x) = x² + x + 1")
print(f"x = {x_g}, g(x) = {x_g^2 + x_g + 1}")
print(f"Witness: s = {list(s_g)}")
print()
valid_g = check_r1cs(A_g, B_g, C_g, s_g)
print(f"\nSatisfied? {valid_g}")
print(f"Only {A_g.nrows()} constraints for a degree-2 polynomial!")

7. Building R1CS Programmatically

Let's write a function that converts a flat circuit into R1CS matrices.

def circuit_to_r1cs(circuit, wire_names, F):
    """
    Convert a flat circuit to R1CS matrices.
    Only multiplication gates become constraints.
    wire_names: list of wire names (first must be 'one').
    Returns: (A, B, C) matrices.
    """
    n = len(wire_names)
    wire_idx = {name: i for i, name in enumerate(wire_names)}
    
    A_rows, B_rows, C_rows = [], [], []
    
    for op, left, right, out in circuit:
        if op == 'mul':
            a = vector(F, n)
            b = vector(F, n)
            c = vector(F, n)
            a[wire_idx[left]] = F(1)
            b[wire_idx[right]] = F(1)
            c[wire_idx[out]] = F(1)
            A_rows.append(a)
            B_rows.append(b)
            C_rows.append(c)
        # Addition gates: skip (absorbed into structure)
    
    return matrix(F, A_rows), matrix(F, B_rows), matrix(F, C_rows)


# Test: rebuild R1CS for x^3 + x + 5
circuit_f = [
    ('mul', 'x',  'x',  'w1'),
    ('mul', 'w1', 'x',  'w2'),
    ('add', 'w2', 'x',  'w3'),   # skipped
    ('add', 'w3', 'five', 'w4'), # skipped
]
wires_f = ['one', 'x', 'five', 'w1', 'w2', 'w3', 'w4']

A_auto, B_auto, C_auto = circuit_to_r1cs(circuit_f, wires_f, F)
print(f"Auto-generated R1CS (multiplication gates only):")
print(f"A = {A_auto}")
print(f"B = {B_auto}")
print(f"C = {C_auto}")
print(f"\n{A_auto.nrows()} constraints for 2 multiplication gates")
print(f"(Addition gates absorbed, they don't need constraints)")

# Verify the auto-generated R1CS
x_val = F(3)
s_auto = vector(F, [1, x_val, 5, x_val^2, x_val^3, x_val^3 + x_val, x_val^3 + x_val + 5])

print(f"Witness: {list(s_auto)}")
print(f"Wires:   {wires_f}")
print()
valid_auto = check_r1cs(A_auto, B_auto, C_auto, s_auto)
print(f"\nSatisfied? {valid_auto}")

Checkpoint 2. The auto-generated R1CS only captures the multiplication gates. In a full SNARK system, the output equality constraint ($f(x) = y$) is enforced separately by the verifier comparing public inputs. The R1CS ensures internal consistency of the computation.

8. Hadamard Product View

We can express all constraints at once using the Hadamard product (element-wise multiplication):

$$A \cdot s \circ B \cdot s = C \cdot s$$

where $\circ$ denotes element-wise multiplication of vectors.

# Full R1CS for f(x) = x³ + x + 5 (hand-crafted with output constraint)
#
# Wires: [one, x, w1, w2, w4]
# (We skip w3 since it's just w2 + x, absorbed)

wires_compact = ['one', 'x', 'w1', 'w2', 'w4']
n = len(wires_compact)

# Constraint 1: x * x = w1
# Constraint 2: w1 * x = w2
# Constraint 3: 1 * (w2 + x + 5) = w4

A_full = matrix(F, [
    [0, 1, 0, 0, 0],  # x
    [0, 0, 1, 0, 0],  # w1
    [1, 0, 0, 0, 0],  # 1
])
B_full = matrix(F, [
    [0, 1, 0, 0, 0],  # x
    [0, 1, 0, 0, 0],  # x
    [5, 1, 0, 1, 0],  # 5 + x + w2
])
C_full = matrix(F, [
    [0, 0, 1, 0, 0],  # w1
    [0, 0, 0, 1, 0],  # w2
    [0, 0, 0, 0, 1],  # w4
])

x_val = F(3)
s_full = vector(F, [1, x_val, x_val^2, x_val^3, x_val^3 + x_val + 5])

# Hadamard check
As = A_full * s_full
Bs = B_full * s_full
Cs = C_full * s_full

# Element-wise product
hadamard = vector(F, [As[i] * Bs[i] for i in range(len(As))])

print(f"A·s = {As}")
print(f"B·s = {Bs}")
print(f"C·s = {Cs}")
print(f"\nA·s ∘ B·s = {hadamard}")
print(f"C·s       = {Cs}")
print(f"Equal?      {hadamard == Cs}")

9. R1CS Size and Sparsity

R1CS matrices are typically very sparse, each row has only a few non-zero entries. This sparsity is exploited for efficiency.

# Analyze sparsity
def r1cs_stats(A, B, C, wire_names):
    m, n = A.nrows(), A.ncols()
    nonzero_A = sum(1 for i in range(m) for j in range(n) if A[i,j] != 0)
    nonzero_B = sum(1 for i in range(m) for j in range(n) if B[i,j] != 0)
    nonzero_C = sum(1 for i in range(m) for j in range(n) if C[i,j] != 0)
    total_entries = 3 * m * n
    total_nonzero = nonzero_A + nonzero_B + nonzero_C
    
    print(f"R1CS dimensions: {m} constraints × {n} wires")
    print(f"Wires: {wire_names}")
    print(f"Non-zero entries: A={nonzero_A}, B={nonzero_B}, C={nonzero_C}")
    print(f"Sparsity: {total_nonzero}/{total_entries} entries non-zero ({100*total_nonzero/total_entries:.1f}%)")

r1cs_stats(A_full, B_full, C_full, wires_compact)
print(f"\nEach constraint row has at most 2-3 non-zero entries.")
print(f"Real SNARK circuits have millions of constraints but similar sparsity.")

Misconception alert. "R1CS constraints are hard to write." For simple circuits, yes, it's tedious. In practice, nobody writes R1CS by hand. Tools like Circom (a domain-specific language) compile high-level circuits to R1CS automatically. We do it by hand here to understand what those tools generate.

10. R1CS for a Multi-Variable Function

Let's build R1CS for $h(a, b) = a \cdot b \cdot (a + b)$.

Flattening:

• $w_1 = a \times b$ (multiplication)

• $w_2 = a + b$ (addition, free)

• $w_3 = w_1 \times w_2$ (multiplication)

# h(a, b) = a * b * (a + b)
# Wires: [one, a, b, w1=a*b, w3=w1*(a+b)]

wires_h = ['one', 'a', 'b', 'w1', 'w3']

# Constraint 1: a * b = w1
# Constraint 2: w1 * (a + b) = w3

A_h = matrix(F, [
    [0, 1, 0, 0, 0],  # a
    [0, 0, 0, 1, 0],  # w1
])
B_h = matrix(F, [
    [0, 0, 1, 0, 0],  # b
    [0, 1, 1, 0, 0],  # a + b  (absorbed addition!)
])
C_h = matrix(F, [
    [0, 0, 0, 1, 0],  # w1
    [0, 0, 0, 0, 1],  # w3
])

# Test: h(4, 5) = 4 * 5 * (4 + 5) = 20 * 9 = 180 mod 97 = 83
a_val, b_val = F(4), F(5)
w1_val = a_val * b_val
w3_val = w1_val * (a_val + b_val)
s_h = vector(F, [1, a_val, b_val, w1_val, w3_val])

print(f"h(a, b) = a·b·(a+b)")
print(f"h({a_val}, {b_val}) = {w3_val}")
print(f"Witness: {list(s_h)}")
print()
valid_h = check_r1cs(A_h, B_h, C_h, s_h)
print(f"\nSatisfied? {valid_h}")
print(f"\nNote: (a+b) was absorbed into B's second row, no extra constraint!")

Checkpoint 3. The key insight of R1CS: every computation reduces to checking that three matrices, multiplied by the witness vector and then Hadamard-multiplied, produce zero. This uniform structure is exactly what the QAP polynomial transformation (next notebook) needs to convert discrete constraint checking into a single polynomial divisibility check.

11. Exercises

Exercise 1 (Worked): R1CS for $x^2 + 3$

Problem. Write R1CS matrices for $f(x) = x^2 + 3$. Construct the witness for $x = 5$ and verify.

Solution:

# Exercise 1: Worked solution
# f(x) = x² + 3
# Flattening: w1 = x*x, out = w1 + 3
# Wires: [one, x, w1, out]

# Constraint 1: x * x = w1
# Constraint 2: 1 * (w1 + 3) = out

A_ex1 = matrix(F, [
    [0, 1, 0, 0],
    [1, 0, 0, 0],
])
B_ex1 = matrix(F, [
    [0, 1, 0, 0],
    [3, 0, 1, 0],  # 3 + w1
])
C_ex1 = matrix(F, [
    [0, 0, 1, 0],
    [0, 0, 0, 1],
])

x_ex1 = F(5)
s_ex1 = vector(F, [1, x_ex1, x_ex1^2, x_ex1^2 + 3])
print(f"f({x_ex1}) = {x_ex1^2 + 3}")
print(f"Witness: {list(s_ex1)}")
print()
check_r1cs(A_ex1, B_ex1, C_ex1, s_ex1)

Exercise 2 (Guided): R1CS for $f(x, y) = x \cdot y + y^2$

Problem. Write R1CS for $f(x, y) = xy + y^2$. Test with $x = 3, y = 4$.

Fill in the TODOs:

# Exercise 2: fill in the TODOs

# Flattening:
#   w1 = x * y       (mul)
#   w2 = y * y       (mul)
#   out = w1 + w2    (add, free)
# Wires: [one, x, y, w1, w2, out]

# TODO 1: Write the A, B, C matrices
# A_ex2 = matrix(F, [
#     [0, 1, 0, 0, 0, 0],  # Constraint 1: left = x
#     [0, 0, ???, 0, 0, 0],  # Constraint 2: left = y
#     [1, 0, 0, 0, 0, 0],  # Constraint 3: left = 1
# ])
# B_ex2 = matrix(F, [
#     ???  # fill in
# ])
# C_ex2 = matrix(F, [
#     ???  # fill in
# ])

# TODO 2: Build witness for x=3, y=4
# s_ex2 = vector(F, [1, 3, 4, ???, ???, ???])

# TODO 3: Verify
# check_r1cs(A_ex2, B_ex2, C_ex2, s_ex2)

Exercise 3 (Independent): Boolean R1CS

Problem.

1. Write R1CS for the computation: "Given Boolean inputs $a, b \in \{0, 1\}$, compute $\text{AND}(a, b) = a \cdot b$."

2. Add Boolean constraints: $a(1-a) = 0$ and $b(1-b) = 0$.

3. Build the full R1CS (3 constraints total) and test with all 4 input combinations.

4. Show that a non-Boolean witness (e.g., $a = 2$) fails the Boolean constraint.

# Exercise 3: write your solution here

Summary

Concept	Key Fact
R1CS	Rank-1 Constraint System: $(A_i \cdot s)(B_i \cdot s) = C_i \cdot s$
Witness	Vector $s$ containing all wire values (including leading 1)
Multiplication gates	Each becomes one R1CS constraint
Addition gates	Free, absorbed into matrix entries
Hadamard form	$As \circ Bs = Cs$, all constraints at once
Sparsity	R1CS matrices have very few non-zero entries per row

R1CS transforms a circuit into a uniform algebraic structure. In the next notebook, we'll use polynomial interpolation to convert these discrete constraints into a single polynomial equation, the Quadratic Arithmetic Program (QAP).

---

Next: 10c: QAP Construction