10c-qap-construction.ipynb

Kernel: SageMath 10.5

Notebook 10c: QAP Construction

Module 10. SNARKs and STARKs

---

Motivating Question. R1CS gives us $m$ separate constraints to check: $(A_i \cdot s)(B_i \cdot s) = C_i \cdot s$ for each row $i$. Can we compress all $m$ checks into a single polynomial equation? Yes, by interpolating the R1CS columns into polynomials and using the fact that a polynomial that vanishes at $m$ points must be divisible by a known "vanishing polynomial." This is the Quadratic Arithmetic Program (QAP).

---

Prerequisites. You should be comfortable with:

• R1CS: matrices $A$, $B$, $C$ and witness vector $s$ (Notebook 10b)

• Polynomial interpolation (Lagrange) over finite fields (Module 02)

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

1. Interpolate R1CS columns into polynomials using Lagrange interpolation.

2. Construct the vanishing polynomial $Z(x)$.

3. Verify the QAP equation: $A(x) \cdot B(x) - C(x) = H(x) \cdot Z(x)$.

4. Understand why this polynomial identity enables succinct proofs.

1. Recap: Our R1CS

Bridge from Notebook 10b. We built R1CS for $f(x) = x^3 + x + 5$ with 3 constraints over 5 wires. Now we'll transform those matrices into polynomials, the key step toward Groth16.

# Setup
p = 97
F = GF(p)
R.<X> = PolynomialRing(F)  # polynomial ring over F_97

# R1CS for f(x) = x³ + x + 5
# Wires: [one, x, w1=x², w2=x³, out=x³+x+5]
wire_names = ['one', 'x', 'w1', 'w2', 'out']
n = len(wire_names)  # 5 wires

# 3 constraints:
# C1: x * x = w1
# C2: w1 * x = w2
# C3: 1 * (w2 + x + 5) = out

A_mat = matrix(F, [
    [0, 1, 0, 0, 0],  # x
    [0, 0, 1, 0, 0],  # w1
    [1, 0, 0, 0, 0],  # 1
])
B_mat = matrix(F, [
    [0, 1, 0, 0, 0],  # x
    [0, 1, 0, 0, 0],  # x
    [5, 1, 0, 1, 0],  # 5 + x + w2
])
C_mat = matrix(F, [
    [0, 0, 1, 0, 0],  # w1
    [0, 0, 0, 1, 0],  # w2
    [0, 0, 0, 0, 1],  # out
])

m = A_mat.nrows()  # 3 constraints

# Witness for x = 3: f(3) = 35
x_val = F(3)
s = vector(F, [1, x_val, x_val^2, x_val^3, x_val^3 + x_val + 5])

print(f"R1CS: {m} constraints × {n} wires")
print(f"Witness: {list(s)}")
print(f"Wires:   {wire_names}")

2. The Key Idea: Interpolation

We have $m = 3$ constraints. Assign each constraint an evaluation point:

• Constraint 1 → point $r_1 = 1$

• Constraint 2 → point $r_2 = 2$

• Constraint 3 → point $r_3 = 3$

For each column $j$ of matrix $A$, we interpolate a polynomial $A_j(x)$ such that: $$A_j(r_i) = A[i, j]$$

This means the polynomial "encodes" the entire column, evaluating it at point $r_i$ gives back the matrix entry for constraint $i$.

# Evaluation points for constraints
eval_points = [F(i+1) for i in range(m)]  # [1, 2, 3]
print(f"Evaluation points: {eval_points}")

# Lagrange interpolation: given points (x_i, y_i), find polynomial P such that P(x_i) = y_i
def lagrange_interpolate(points, values, R):
    """Lagrange interpolation over polynomial ring R."""
    x = R.gen()
    n = len(points)
    result = R(0)
    for i in range(n):
        # Lagrange basis polynomial L_i(x)
        L_i = R(1)
        for j in range(n):
            if i != j:
                L_i *= (x - points[j]) / (points[i] - points[j])
        result += values[i] * L_i
    return result

# Interpolate column 1 of A (the 'x' column: [1, 0, 0])
col_vals = [A_mat[i, 1] for i in range(m)]  # [1, 0, 0]
poly_test = lagrange_interpolate(eval_points, col_vals, R)
print(f"\nA column 'x': values = {col_vals}")
print(f"Interpolated polynomial: A_x(X) = {poly_test}")
print(f"Check: A_x(1) = {poly_test(1)}, A_x(2) = {poly_test(2)}, A_x(3) = {poly_test(3)}")

3. Interpolating All Columns

We interpolate every column of $A$, $B$, and $C$ into polynomials.

def matrix_to_polys(M, eval_points, R):
    """Interpolate each column of matrix M into a polynomial."""
    m, n = M.nrows(), M.ncols()
    polys = []
    for j in range(n):
        col_vals = [M[i, j] for i in range(m)]
        poly_j = lagrange_interpolate(eval_points, col_vals, R)
        polys.append(poly_j)
    return polys

# Interpolate all three matrices
A_polys = matrix_to_polys(A_mat, eval_points, R)
B_polys = matrix_to_polys(B_mat, eval_points, R)
C_polys = matrix_to_polys(C_mat, eval_points, R)

print("QAP polynomials (one per wire):")
for j, name in enumerate(wire_names):
    print(f"\n  Wire '{name}' (column {j}):")
    print(f"    A_{name}(X) = {A_polys[j]}")
    print(f"    B_{name}(X) = {B_polys[j]}")
    print(f"    C_{name}(X) = {C_polys[j]}")

# Verify: evaluating polynomials at eval points recovers the matrices
print("Verification: polynomials reproduce matrix entries")
for i, pt in enumerate(eval_points):
    for j, name in enumerate(wire_names):
        mat_val = A_mat[i, j]
        poly_val = A_polys[j](pt)
        if mat_val != 0 or poly_val != 0:

Checkpoint 1. We now have $3 \times 5 = 15$ polynomials (3 matrices × 5 wires). Each polynomial has degree at most $m - 1 = 2$ (interpolated through $m = 3$ points). Evaluating all polynomials at point $r_i$ reconstructs the $i$-th row of each matrix.

4. Combining with the Witness

The R1CS check at constraint $i$ is: $(A_i \cdot s)(B_i \cdot s) = C_i \cdot s$.

Define the combined polynomials: $$A(x) = \sum_j s_j \cdot A_j(x), \quad B(x) = \sum_j s_j \cdot B_j(x), \quad C(x) = \sum_j s_j \cdot C_j(x)$$

Then $A(r_i) = A_i \cdot s$, and similarly for $B$ and $C$. So:

$$A(r_i) \cdot B(r_i) = C(r_i) \quad \text{for all } i$$

This means $A(x) \cdot B(x) - C(x)$ vanishes at all evaluation points!

# Combine polynomials with witness
A_combined = sum(s[j] * A_polys[j] for j in range(n))
B_combined = sum(s[j] * B_polys[j] for j in range(n))
C_combined = sum(s[j] * C_polys[j] for j in range(n))

print(f"A(X) = Σ s_j · A_j(X) = {A_combined}")
print(f"B(X) = Σ s_j · B_j(X) = {B_combined}")
print(f"C(X) = Σ s_j · C_j(X) = {C_combined}")

# Check: A(r_i) * B(r_i) should equal C(r_i)
print(f"\nConstraint checks:")
for i, pt in enumerate(eval_points):
    a_val = A_combined(pt)
    b_val = B_combined(pt)
    c_val = C_combined(pt)
    print(f"  r={pt}: A({pt})·B({pt}) = {a_val}·{b_val} = {a_val*b_val}, C({pt}) = {c_val}, equal? {a_val*b_val == c_val}")

5. The Vanishing Polynomial

Since $A(x) \cdot B(x) - C(x)$ vanishes at $r_1, r_2, \ldots, r_m$, it must be divisible by the vanishing polynomial:

$$Z(x) = (x - r_1)(x - r_2) \cdots (x - r_m)$$

So there exists a polynomial $H(x)$ such that:

$$\boxed{A(x) \cdot B(x) - C(x) = H(x) \cdot Z(x)}$$

This is the QAP equation, the heart of SNARKs.

# Vanishing polynomial
Z = prod(X - pt for pt in eval_points)
print(f"Vanishing polynomial: Z(X) = {Z}")
print(f"Degree: {Z.degree()}")
print(f"Roots: Z(1) = {Z(1)}, Z(2) = {Z(2)}, Z(3) = {Z(3)}")

# Compute A*B - C
P = A_combined * B_combined - C_combined
print(f"\nP(X) = A(X)·B(X) - C(X) = {P}")
print(f"Degree of P: {P.degree()}")

# P should vanish at eval points
print(f"\nP vanishes at eval points:")
for pt in eval_points:
    print(f"  P({pt}) = {P(pt)}")

# Compute H(X) = P(X) / Z(X)
H, remainder = P.quo_rem(Z)

print(f"H(X) = P(X) / Z(X) = {H}")
print(f"Remainder: {remainder}")
print(f"\nDivision is exact (remainder = 0)? {remainder == 0}")

# Verify: H(X) * Z(X) = A(X)*B(X) - C(X)
print(f"\nVerification: H·Z = {H * Z}")
print(f"              P   = {P}")
print(f"Equal? {H * Z == P}")

Checkpoint 2. The QAP equation $A(x) \cdot B(x) - C(x) = H(x) \cdot Z(x)$ is a polynomial identity. It holds for all $x \in \mathbb{F}$ (not just the evaluation points). The prover constructs $H(x)$ by polynomial division. If the witness is invalid, the division will have a non-zero remainder, and the prover cannot forge $H$.

6. Why QAP Enables Succinct Proofs

The QAP equation can be checked at a single random point $\tau$ (chosen by the verifier or embedded in the trusted setup):

$$A(\tau) \cdot B(\tau) - C(\tau) \stackrel{?}{=} H(\tau) \cdot Z(\tau)$$

By the Schwartz-Zippel lemma: if two polynomials of degree $d$ agree at a random point, they are the same polynomial with probability $\geq 1 - d/|\mathbb{F}|$. For a 256-bit field, this probability is negligibly close to 1.

One check replaces $m$ constraint checks!

# Schwartz-Zippel demo: check at a random point
tau = F.random_element()
while tau in eval_points:  # avoid evaluation points (trivial zeros)
    tau = F.random_element()

lhs = A_combined(tau) * B_combined(tau) - C_combined(tau)
rhs = H(tau) * Z(tau)

print(f"Random challenge: τ = {tau}")
print(f"\nA(τ)·B(τ) - C(τ) = {lhs}")
print(f"H(τ)·Z(τ)         = {rhs}")
print(f"Equal? {lhs == rhs}")
print(f"\nOne evaluation check replaces {m} constraint checks!")
print(f"Soundness error: ≤ {P.degree()}/{p} ≈ {float(P.degree())/p:.6f}")

7. What Happens with a Bad Witness?

If the prover uses an incorrect witness, the polynomial $P(x) = A(x) \cdot B(x) - C(x)$ won't vanish at all evaluation points, so it won't be divisible by $Z(x)$.

# Bad witness: claim x=3 but use wrong w1 = 10 instead of 9
s_bad = vector(F, [1, 3, 10, 27, 35])  # w1 should be 9

A_bad = sum(s_bad[j] * A_polys[j] for j in range(n))
B_bad = sum(s_bad[j] * B_polys[j] for j in range(n))
C_bad = sum(s_bad[j] * C_polys[j] for j in range(n))

P_bad = A_bad * B_bad - C_bad

print("=== Bad witness: w1 = 10 (should be 9) ===")
print(f"P_bad(X) = {P_bad}")
print(f"\nP_bad at eval points:")
for pt in eval_points:
    print(f"  P_bad({pt}) = {P_bad(pt)}")

H_bad, rem_bad = P_bad.quo_rem(Z)
print(f"\nDivision by Z(X):")
print(f"  H_bad = {H_bad}")
print(f"  Remainder = {rem_bad}")
print(f"  Remainder is zero? {rem_bad == 0}")
print(f"\nThe prover CANNOT construct a valid H(X) with a bad witness!")

8. Degree Analysis

Understanding the polynomial degrees is important for the proof system.

Polynomial	Degree	Explanation
$A_j(x)$, $B_j(x)$, $C_j(x)$	$\leq m - 1$	Interpolated through $m$ points
$A(x)$, $B(x)$, $C(x)$	$\leq m - 1$	Linear combinations of the above
$A(x) \cdot B(x)$	$\leq 2(m-1)$	Product of degree $m-1$ polynomials
$Z(x)$	$m$	Product of $m$ linear factors
$H(x)$	$\leq m - 2$	$\deg(A \cdot B) - \deg(Z) = 2(m-1) - m = m - 2$

print(f"Degree analysis (m = {m} constraints):")
print(f"  A(X) degree: {A_combined.degree()} (max: {m-1})")
print(f"  B(X) degree: {B_combined.degree()} (max: {m-1})")
print(f"  C(X) degree: {C_combined.degree()} (max: {m-1})")
print(f"  A·B  degree: {(A_combined * B_combined).degree()} (max: {2*(m-1)})")
print(f"  Z(X) degree: {Z.degree()} (exactly m)")
print(f"  H(X) degree: {H.degree()} (max: {m-2})")
print(f"  P(X) degree: {P.degree()} (max: {2*(m-1)})")

9. The Full QAP Pipeline

Let's wrap the entire construction into a clean function.

def r1cs_to_qap(A_mat, B_mat, C_mat, R):
    """
    Convert R1CS matrices to QAP polynomials.
    Returns: (A_polys, B_polys, C_polys, Z, eval_points)
    """
    F = R.base_ring()
    m, n = A_mat.nrows(), A_mat.ncols()
    eval_points = [F(i+1) for i in range(m)]
    
    A_polys = matrix_to_polys(A_mat, eval_points, R)
    B_polys = matrix_to_polys(B_mat, eval_points, R)
    C_polys = matrix_to_polys(C_mat, eval_points, R)
    
    X = R.gen()
    Z = prod(X - pt for pt in eval_points)
    
    return A_polys, B_polys, C_polys, Z, eval_points


def qap_prove(A_polys, B_polys, C_polys, Z, s):
    """
    Prover: combine polynomials with witness and compute H.
    Returns: (A_combined, B_combined, C_combined, H)
    """
    n = len(s)
    A_comb = sum(s[j] * A_polys[j] for j in range(n))
    B_comb = sum(s[j] * B_polys[j] for j in range(n))
    C_comb = sum(s[j] * C_polys[j] for j in range(n))
    
    P = A_comb * B_comb - C_comb
    H, rem = P.quo_rem(Z)
    
    if rem != 0:
        print("WARNING: Invalid witness, remainder is non-zero!")
    
    return A_comb, B_comb, C_comb, H


def qap_verify(A_comb, B_comb, C_comb, H, Z, tau):
    """
    Verifier: check the QAP equation at a random point.
    """
    lhs = A_comb(tau) * B_comb(tau) - C_comb(tau)
    rhs = H(tau) * Z(tau)
    return lhs == rhs


# Full pipeline demo
print("=== Full QAP Pipeline ===")
A_p, B_p, C_p, Z_qap, pts = r1cs_to_qap(A_mat, B_mat, C_mat, R)
A_c, B_c, C_c, H_qap = qap_prove(A_p, B_p, C_p, Z_qap, s)

tau = F(42)  # random challenge
valid = qap_verify(A_c, B_c, C_c, H_qap, Z_qap, tau)
print(f"Proof verified at τ={tau}? {valid}")

# Try with several random points
print(f"\nMultiple random checks:")
for _ in range(5):
    tau_i = F.random_element()
    v = qap_verify(A_c, B_c, C_c, H_qap, Z_qap, tau_i)
    print(f"  τ={tau_i}: {v}")

Checkpoint 3. The QAP pipeline:

1. Setup: Convert R1CS to QAP polynomials (done once per circuit).

2. Prove: Combine polynomials with witness, compute $H(x)$ via polynomial division.

3. Verify: Check $A(\tau) \cdot B(\tau) - C(\tau) = H(\tau) \cdot Z(\tau)$ at a random point.

In Groth16 (next notebook), the random $\tau$ is embedded in the trusted setup, and the evaluations are hidden inside elliptic curve points using pairings.

10. From QAP to SNARKs: The Gap

The QAP gives us a polynomial identity to check. But a few problems remain:

Problem	Solution (Groth16)
Verifier must know $\tau$	$\tau$ is generated and destroyed in trusted setup
Prover could evaluate at wrong point	Evaluations are committed via elliptic curve points
Witness $s$ is revealed	Polynomial evaluations are hidden in curve points
Need to check polynomial identity	Use pairing equation: $e([A]_1, [B]_2) = e([C]_1, [1]_2)$

Crypto foreshadowing. Groth16 uses the bilinear pairing from Module 07 to check the QAP equation "in the exponent", the verifier never sees $A(\tau)$, $B(\tau)$, etc., only elliptic curve points that encode them. This is how zero-knowledge is achieved.

11. Exercises

Exercise 1 (Worked): QAP for $g(x) = x^2 + x + 1$

Problem. Build the full QAP for $g(x) = x^2 + x + 1$ (from Notebook 10b). Verify the polynomial identity.

Solution:

# Exercise 1: Worked solution
# g(x) = x² + x + 1, R1CS from 10b:
A_ex = matrix(F, [[0, 1, 0, 0], [1, 0, 0, 0]])
B_ex = matrix(F, [[0, 1, 0, 0], [1, 1, 1, 0]])
C_ex = matrix(F, [[0, 0, 1, 0], [0, 0, 0, 1]])

# QAP
A_p_ex, B_p_ex, C_p_ex, Z_ex, pts_ex = r1cs_to_qap(A_ex, B_ex, C_ex, R)

# Witness for x = 7
x_ex = F(7)
s_ex = vector(F, [1, x_ex, x_ex^2, x_ex^2 + x_ex + 1])
print(f"g({x_ex}) = {x_ex^2 + x_ex + 1}")

# Prove
A_c_ex, B_c_ex, C_c_ex, H_ex = qap_prove(A_p_ex, B_p_ex, C_p_ex, Z_ex, s_ex)
print(f"H(X) = {H_ex}")

# Verify at random point
tau_ex = F(50)
valid_ex = qap_verify(A_c_ex, B_c_ex, C_c_ex, H_ex, Z_ex, tau_ex)
print(f"Verified at τ={tau_ex}? {valid_ex}")

Exercise 2 (Guided): Detect a Bad Witness

Problem. Using the QAP for $f(x) = x^3 + x + 5$, try to produce a proof for a wrong output: claim $f(3) = 40$ instead of $35$. Show that qap_prove gives a non-zero remainder.

Fill in the TODOs:

# Exercise 2: fill in the TODOs

# TODO 1: Construct a bad witness where out = 40 instead of 35
# s_forged = vector(F, [1, 3, 9, 27, ???])

# TODO 2: Run qap_prove and check the remainder
# A_c_f, B_c_f, C_c_f, H_f = qap_prove(A_p, B_p, C_p, Z_qap, s_forged)

# TODO 3: Try to verify, should it pass or fail?
# valid_f = qap_verify(A_c_f, B_c_f, C_c_f, H_f, Z_qap, F(42))
# print(f"Forged proof verified? {valid_f}")

Exercise 3 (Independent): QAP from Scratch

Problem.

1. Write R1CS for $f(x) = x^4$ (hint: two multiplication gates).

2. Convert to QAP polynomials.

3. Compute $H(x)$ for the witness with $x = 2$.

4. Verify the QAP equation at three different random points.

5. What degree is $H(x)$? Does it match the formula $m - 2$?

# Exercise 3: write your solution here

Summary

Concept	Key Fact
QAP	Polynomial encoding of R1CS constraints
Interpolation	Each R1CS column becomes a polynomial via Lagrange interpolation
Combined polynomials	$A(x) = \sum s_j A_j(x)$; evaluating at $r_i$ gives $A_i \cdot s$
Vanishing polynomial	$Z(x) = \prod (x - r_i)$, vanishes at all constraint points
QAP equation	$A(x) \cdot B(x) - C(x) = H(x) \cdot Z(x)$
Schwartz-Zippel	Check polynomial identity at one random point with overwhelming probability

The QAP is the mathematical core of pairing-based SNARKs. In the next notebook, we'll see how Groth16 evaluates this polynomial identity "in the exponent" using elliptic curve pairings, hiding the witness while allowing verification.

---

Next: 10d: Groth16 Overview