10e-fri-protocol.ipynb

Kernel: SageMath 10.5

Notebook 10e: The FRI Protocol

Module 10: SNARKs and STARKs

---

Motivating Question. Groth16 gives us tiny proofs, but requires a trusted setup, if the toxic waste leaks, anyone can forge. Can we build a proof system where there's nothing to trust? The FRI protocol (Fast Reed-Solomon Interactive Oracle Proof of Proximity) is the engine behind STARKs. It lets a prover convince a verifier that a function is "close to" a low-degree polynomial, using only hashing, no elliptic curves, no pairings, no toxic waste.

---

Prerequisites. You should be comfortable with:

• Polynomial evaluation and interpolation (Module 02)

• The QAP divisibility check: polynomials encode computation (Notebook 10c)

• Groth16's trusted-setup trade-off (Notebook 10d)

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

1. Understand Reed-Solomon codes and why "low degree" means "valid codeword."

2. Decompose a polynomial into even and odd parts.

3. Perform FRI folding rounds that halve the polynomial degree.

4. Walk through a complete mini-FRI protocol with Merkle commitments.

5. See why FRI eliminates the need for a trusted setup.

1. Reed-Solomon Codes: Polynomials as Error-Correcting Codes

Bridge from Notebook 10d. Groth16 encodes polynomial evaluations as curve points and uses pairings to check the QAP equation. FRI takes a completely different approach: encode polynomial evaluations as a vector of field elements and use algebraic structure to prove it came from a low-degree polynomial.

A Reed-Solomon code is simple: evaluate a polynomial of degree $< d$ on a domain $D$ of size $n > d$. The resulting vector of evaluations is a codeword.

$$\text{RS}[d, D] = \{(f(\omega^0), f(\omega^1), \ldots, f(\omega^{n-1})) : \deg(f) < d\}$$

The rate $\rho = d / n$ controls redundancy. If $\rho = 1/4$ (blowup factor 4), the codeword is 4x longer than necessary, providing strong error detection.

# Setup: we'll use F_257, a Fermat prime where |F*| = 256 = 2^8
# This gives us perfect power-of-2 domains for FRI!

p = 257
F = GF(p)
R.<X> = PolynomialRing(F)

# Find a generator of F_257* (multiplicative group of order 256 = 2^8)
g = F.multiplicative_generator()
print(f"Field: F_{p}")
print(f"Multiplicative group order: {p-1} = 2^8")
print(f"Generator: g = {g}")
print(f"g^256 = {g^256}")  # should be 1

# Reed-Solomon encoding: evaluate a degree-3 polynomial on a domain of size 16
# Rate rho = 4/16 = 1/4 (blowup factor 4)

max_degree = 4  # polynomials of degree < 4
domain_size = 16  # |D| = 16

# Domain = multiplicative subgroup of order 16
omega = g^(256 // domain_size)  # primitive 16th root of unity
D = [omega^i for i in range(domain_size)]

print(f"Primitive 16th root of unity: ω = {omega}")
print(f"ω^16 = {omega^16}")  # should be 1
print(f"Domain D = {{ω^i : i = 0..15}} = {[ZZ(d) for d in D]}")
print(f"Rate: ρ = {max_degree}/{domain_size} = 1/4")

# Encode a polynomial as a Reed-Solomon codeword
f = R(3 + 5*X + 2*X^2 + X^3)  # degree 3 < 4
print(f"Polynomial: f(x) = {f}")
print(f"Degree: {f.degree()} (< {max_degree} ✓)")

# Codeword = evaluations on domain
codeword = [f(d) for d in D]
print(f"\nCodeword (evaluations of f on D):")
print(f"  {[ZZ(c) for c in codeword]}")
print(f"  Length: {len(codeword)} (domain size)")
print(f"\nKey insight: this codeword UNIQUELY determines f")
print(f"because {domain_size} points determine a polynomial of degree < {max_degree}.")
print(f"The extra {domain_size - max_degree} evaluations are redundant, they're the 'error correction.'")

Checkpoint 1. A Reed-Solomon codeword is just a polynomial evaluated on a structured domain. The key property: if you change any evaluation in a valid codeword, the result is no longer a valid codeword (it doesn't come from a degree-$< d$ polynomial). FRI exploits this: proving a function is low-degree is equivalent to proving it's a valid RS codeword.

# Corrupted codeword: change one evaluation
corrupted = list(codeword)
corrupted[3] = F(99)  # tamper with one position

# Try to interpolate back, the result won't have degree < 4
f_corrupted = R.lagrange_polynomial(list(zip(D, corrupted)))
print(f"Original polynomial:     deg = {f.degree()}")
print(f"Corrupted interpolation: deg = {f_corrupted.degree()}")
print(f"\nCorrupting even ONE evaluation pushes the degree above {max_degree - 1}.")
print(f"This is the foundation of FRI: low degree ↔ valid codeword.")

2. Even-Odd Decomposition

The core trick of FRI is splitting a polynomial into its even and odd parts:

$$f(x) = f_{\text{even}}(x^2) + x \cdot f_{\text{odd}}(x^2)$$

For example, $f(x) = 3 + 5x + 2x^2 + x^3$ becomes:

• Even part: $f_e(y) = 3 + 2y$ (coefficients of $x^0, x^2$)

• Odd part: $f_o(y) = 5 + y$ (coefficients of $x^1, x^3$)

• Check: $f_e(x^2) + x \cdot f_o(x^2) = (3 + 2x^2) + x(5 + x^2) = 3 + 5x + 2x^2 + x^3$ ✓

The key observation: $f_e$ and $f_o$ each have degree $\leq \lfloor \deg(f)/2 \rfloor$, half the degree.

def even_odd_split(poly):
    """Split f(x) into f_even(y), f_odd(y) where f(x) = f_even(x²) + x·f_odd(x²)"""
    coeffs = poly.padded_list(poly.degree() + 1) if poly.degree() >= 0 else [F(0)]
    # Pad to even length
    if len(coeffs) % 2 == 1:
        coeffs.append(F(0))
    even_coeffs = coeffs[0::2]  # a_0, a_2, a_4, ...
    odd_coeffs = coeffs[1::2]   # a_1, a_3, a_5, ...
    return R(even_coeffs), R(odd_coeffs)

f_even, f_odd = even_odd_split(f)
print(f"f(x) = {f}")
print(f"f_even(y) = {f_even}")
print(f"f_odd(y)  = {f_odd}")
print(f"\nDegree reduction: {f.degree()} → max({f_even.degree()}, {f_odd.degree()}) = {max(f_even.degree(), f_odd.degree())}")

# Verify: f(x) = f_even(x²) + x * f_odd(x²)
reconstruction = f_even(X^2) + X * f_odd(X^2)
print(f"\nReconstruction: f_even(x²) + x·f_odd(x²) = {reconstruction}")
print(f"Matches f(x)? {reconstruction == f}")

3. One Round of FRI Folding

The verifier sends a random challenge $\alpha \in \mathbb{F}$. The prover computes the folded polynomial:

$$f'(y) = f_{\text{even}}(y) + \alpha \cdot f_{\text{odd}}(y)$$

This is a random linear combination of $f_e$ and $f_o$, so:

• $\deg(f') \leq \lfloor \deg(f)/2 \rfloor$, the degree halves!

• The domain also shrinks: $D \to D' = \{d^2 : d \in D\}$

Why does the domain shrink? Because $\omega^i$ and $\omega^{i+n/2}$ square to the same value (they're negatives of each other: $(\omega^{n/2} = -1)$). So squaring maps $n$ points to $n/2$ points.

def fri_fold(poly, alpha, domain):
    """
    One round of FRI folding.
    Returns (folded_poly, new_domain, folded_evals).
    """
    f_even, f_odd = even_odd_split(poly)
    folded = f_even + alpha * f_odd  # degree halves!
    
    # New domain: square each element, take unique values
    new_domain = sorted(set(d^2 for d in domain), key=lambda x: ZZ(x))
    
    # Folded evaluations
    folded_evals = [folded(d) for d in new_domain]
    
    return folded, new_domain, folded_evals

# Verifier sends random challenge
alpha_1 = F(7)  # (in practice, derived via Fiat-Shamir)

f1, D1, evals1 = fri_fold(f, alpha_1, D)

print(f"=== FRI Round 1 ===")
print(f"Original:  f(x) = {f}, degree {f.degree()}, domain size {len(D)}")
print(f"Challenge: α₁ = {alpha_1}")
print(f"Folded:    f₁(y) = {f1}, degree {f1.degree()}, domain size {len(D1)}")
print(f"\nDegree went from {f.degree()} to {f1.degree()}, halved!")
print(f"Domain went from {len(D)} to {len(D1)}, also halved!")

# Key property: the verifier can CHECK consistency without the polynomial!
# For any point d in D, the prover's claim about f₁(d²) should match:
#   f₁(d²) = f_even(d²) + α₁ · f_odd(d²)
#          = [f(d) + f(-d)] / 2 + α₁ · [f(d) - f(-d)] / (2d)

# The verifier can check this using just f(d) and f(-d)!
print("Consistency check: verifier queries f(d) and f(-d)")

half = len(D) // 2
for i in range(min(8, half)):  # show first 8
    d = D[i]
    neg_d = D[i + half]  # ω^(i+n/2) = -ω^i
    
    # Verifier computes expected f₁(d²) from f(d) and f(-d)
    f_d = f(d)
    f_neg_d = f(neg_d)
    inv2 = F(2)^(-1)
    expected = inv2 * (f_d + f_neg_d) + alpha_1 * inv2 * (f_d - f_neg_d) * d^(-1) if d != 0 else None
    actual = f1(d^2)
    

Checkpoint 2. The verifier doesn't need the polynomial itself, just two evaluations $f(d)$ and $f(-d)$ to check one folding step. This is what makes FRI an interactive oracle proof: the prover commits to evaluations (via Merkle trees), and the verifier spot-checks consistency.

4. Full FRI: Fold Until Constant

Repeat the folding until we reach a constant polynomial (degree 0). For our degree-3 polynomial:

Round	Degree	Domain size	Challenge
0	3	16	,
1	1	8	$\alpha_1$
2	0	4	$\alpha_2$

After round 2, the polynomial is constant, the prover just sends this value.

# Full FRI protocol
def fri_commit(poly, domain, challenges):
    """
    Run the full FRI commit phase.
    Returns list of (polynomial, domain, evaluations) for each round.
    """
    rounds = []
    current_poly = poly
    current_domain = domain
    current_evals = [current_poly(d) for d in current_domain]
    rounds.append((current_poly, list(current_domain), current_evals))
    
    for alpha in challenges:
        current_poly, current_domain, current_evals = fri_fold(current_poly, alpha, current_domain)
        rounds.append((current_poly, list(current_domain), current_evals))
    
    return rounds

# Two challenges to fold degree 3 → 1 → 0
challenges = [F(7), F(11)]
rounds = fri_commit(f, D, challenges)

print(f"=== Full FRI Commit Phase ===")
print(f"Original polynomial: f(x) = {f}\n")

for i, (poly, dom, evals) in enumerate(rounds):
    print(f"Round {i}: f_{i}(x) = {poly}")
    print(f"  Degree: {poly.degree()}, Domain size: {len(dom)}")
    print(f"  Evaluations: {[ZZ(e) for e in evals[:8]]}{'...' if len(evals) > 8 else ''}")
    if i < len(challenges):
        print(f"  → Fold with α_{i+1} = {challenges[i]}")
    print()

final_value = rounds[-1][2][0]
print(f"Final constant value: {ZZ(final_value)}")
print(f"Prover sends this single value to verifier.")

Misconception alert. "FRI proves that $f$ is a low-degree polynomial." Not exactly, FRI proves that $f$ is close to a low-degree polynomial (a proximity test). In STARK usage this distinction doesn't matter because exact equality is enforced by the constraint system, but the formal guarantee is proximity.

5. Merkle Commitments: The Oracle Model

In each round, the prover commits to evaluations using a Merkle tree. This turns the interactive protocol into a non-interactive one (via Fiat-Shamir):

1. Hash all evaluations into a Merkle tree, send the root

2. Derive challenge $\alpha$ from the root (Fiat-Shamir)

3. When verifier queries positions, prover provides values + Merkle proofs

       Root(f₀)
      /        \
   H(0..7)   H(8..15)      ← Round 0 evaluations (16 leaves)
      ↓ α₁ = Hash(Root)
       Root(f₁)
      /        \
   H(0..3)   H(4..7)       ← Round 1 evaluations (8 leaves)
      ↓ α₂ = Hash(Root)
       Root(f₂)
     [constant]             ← Round 2: single value (4 copies)

The verifier only checks $O(\log n)$ positions, this gives logarithmic verification time.

import hashlib

def merkle_root(values):
    """Compute a simple Merkle root of field element evaluations."""
    leaves = [hashlib.sha256(str(ZZ(v)).encode()).digest() for v in values]
    while len(leaves) > 1:
        if len(leaves) % 2 == 1:
            leaves.append(leaves[-1])  # duplicate last if odd
        leaves = [
            hashlib.sha256(leaves[i] + leaves[i+1]).digest()
            for i in range(0, len(leaves), 2)
        ]
    return leaves[0].hex()[:16]  # truncate for readability

# Simulate FRI with Merkle commitments
print("=== FRI with Merkle Commitments ===")
for i, (poly, dom, evals) in enumerate(rounds):
    root = merkle_root(evals)
    print(f"Round {i}: Merkle root = {root}...")
    print(f"  {len(evals)} evaluations committed")
    if i < len(challenges):
        # In practice: α = Hash(root)
        print(f"  Challenge α_{i+1} = {challenges[i]} (would be Hash(root) via Fiat-Shamir)")
    else:
        print(f"  Final constant: {ZZ(evals[0])}")
    print()

print("Proof data: Merkle roots + queried positions + Merkle proofs")
print(f"Proof size: O(log²(n)), logarithmic in the domain size!")

6. FRI Verification: Spot-Check Consistency

The verifier picks random query positions and checks that each folding step is consistent. For each query index $i$:

1. Look up $f_0(\omega^i)$ and $f_0(\omega^{i+n/2})$, these are "paired" positions (negatives of each other)

2. Compute the expected $f_1((\omega^i)^2)$ from the folding formula

3. Compare with the committed value of $f_1$ at that position

4. Repeat for each folding round

def fri_verify_query(rounds, challenges, query_idx):
    """
    Verify one FRI query at the given index.
    Returns True if all folding steps are consistent.
    """
    idx = query_idx
    for r in range(len(challenges)):
        poly_r, dom_r, evals_r = rounds[r]
        poly_next, dom_next, evals_next = rounds[r + 1]
        alpha = challenges[r]
        
        n = len(dom_r)
        half = n // 2
        
        # Paired indices: i and i + n/2
        i_pos = idx % half
        i_neg = i_pos + half
        
        d = dom_r[i_pos]
        neg_d = dom_r[i_neg]
        
        f_d = evals_r[i_pos]
        f_neg_d = evals_r[i_neg]
        
        # Compute expected folded value
        inv2 = F(2)^(-1)
        f_even_at_d2 = inv2 * (f_d + f_neg_d)
        f_odd_at_d2 = inv2 * (f_d - f_neg_d) * d^(-1)
        expected = f_even_at_d2 + alpha * f_odd_at_d2
        
        # Look up committed value
        actual = evals_next[i_pos % len(dom_next)]
        
        if expected != actual:
            return False, r
        
        idx = i_pos  # next round's index
    
    return True, -1

# Verify multiple random queries
print("=== FRI Verification ===")
random.seed(42)

n_queries = 5
for _ in range(n_queries):
    qi = randint(0, len(D) // 2 - 1)
    ok, fail_round = fri_verify_query(rounds, challenges, qi)
    status = "✓ PASS" if ok else f"✗ FAIL at round {fail_round}"
    print(f"  Query index {qi}: {status}")

print(f"\nAll {n_queries} queries passed, verifier accepts!")
print(f"Each query checks O(log n) = O({len(challenges)}) folding steps.")

Checkpoint 3. Each query costs the verifier $O(\log n)$ work (one check per folding round). With $\lambda$ queries, the soundness error is $(1 - \delta)^\lambda$ where $\delta$ depends on the rate. For $\rho = 1/4$ and 80 queries, the probability of a cheating prover fooling the verifier is negligible ($< 2^{-80}$).

7. Catching a Cheater

What happens if the prover tries to commit to a high-degree function (not a valid RS codeword)?

# Cheating prover: commit to a degree-7 polynomial but claim it's degree < 4
f_cheat = R(1 + 2*X + 3*X^2 + 4*X^3 + 5*X^4 + 6*X^5 + 7*X^6 + X^7)
print(f"Cheater's polynomial: f(x) = {f_cheat}")
print(f"Actual degree: {f_cheat.degree()} (> 3, cheating!)")

# Run honest FRI on the cheating polynomial
cheat_rounds = fri_commit(f_cheat, D, challenges)

print(f"\n=== Cheater's FRI Rounds ===")
for i, (poly, dom, evals) in enumerate(cheat_rounds):
    print(f"Round {i}: degree {poly.degree()}, domain size {len(dom)}")

# The final polynomial should be constant (degree 0) for honest prover
# For cheater, it won't be!
final_poly = cheat_rounds[-1][0]
print(f"\nFinal polynomial: {final_poly}")
print(f"Final degree: {final_poly.degree()}")
print(f"Is constant? {final_poly.degree() == 0}")
print(f"\nThe cheater is caught! After folding, the result isn't constant.")
print(f"In the real protocol, the cheater would have to lie in the Merkle commitments,")
print(f"which the spot-check queries would catch with overwhelming probability.")

# More subtle cheating: tamper with one evaluation
# Compute honest evaluations but change one value
honest_evals = [f(d) for d in D]
tampered_evals = list(honest_evals)
tampered_evals[5] = F(42)  # change one evaluation

print("=== Tampered Evaluation Detection ===")
print(f"Changed evaluation at index 5: {ZZ(honest_evals[5])} → 42")

# Fold manually with tampered values
alpha = challenges[0]
half = len(D) // 2

# Check the pair involving index 5
i_pos = 5  # in first half
i_neg = 5 + half  # paired index
d = D[i_pos]

# Honest folded value
inv2 = F(2)^(-1)
honest_fold = inv2 * (honest_evals[i_pos] + honest_evals[i_neg]) + \
              alpha * inv2 * (honest_evals[i_pos] - honest_evals[i_neg]) * d^(-1)

# Tampered folded value
tampered_fold = inv2 * (tampered_evals[i_pos] + tampered_evals[i_neg]) + \
                alpha * inv2 * (tampered_evals[i_pos] - tampered_evals[i_neg]) * d^(-1)

print(f"\nHonest f₁(d²):   {ZZ(honest_fold)}")
print(f"Tampered f₁(d²):  {ZZ(tampered_fold)}")
print(f"Mismatch? {honest_fold != tampered_fold}")
print(f"\nIf the verifier queries index 5, the inconsistency is detected!")
print(f"With enough queries, tampering is caught with overwhelming probability.")

8. Putting It All Together: A Complete Mini-FRI

Let's run a complete FRI protocol end-to-end with all the steps labeled.

def fri_protocol(poly, domain, n_queries=4, seed=12345):
    """
    Run a complete FRI protocol.
    Returns (accept/reject, transcript).
    """
    transcript = []
    rng = random.Random(seed)
    
    # Determine number of rounds needed
    target_degree = 0
    current_degree = (len(domain) // 4) - 1  # expected max degree (rate 1/4)
    n_rounds = 0
    d = current_degree
    while d > target_degree:
        d = d // 2
        n_rounds += 1
    
    # COMMIT PHASE
    transcript.append(f"=== COMMIT PHASE ({n_rounds} rounds) ===")
    
    all_rounds = []
    current_poly = poly
    current_dom = list(domain)
    current_evals = [current_poly(d) for d in current_dom]
    
    root = merkle_root(current_evals)
    all_rounds.append((current_poly, current_dom, current_evals))
    transcript.append(f"  Round 0: commit {len(current_evals)} evals, root={root}...")
    
    fold_challenges = []
    for r in range(n_rounds):
        # Verifier challenge (Fiat-Shamir: hash the root)
        alpha = F(rng.randint(1, p-1))
        fold_challenges.append(alpha)
        
        current_poly, current_dom, current_evals = fri_fold(current_poly, alpha, current_dom)
        root = merkle_root(current_evals)
        all_rounds.append((current_poly, current_dom, current_evals))
        transcript.append(f"  Round {r+1}: α={ZZ(alpha)}, commit {len(current_evals)} evals, root={root}...")
    
    # Final value
    final_val = current_evals[0]
    transcript.append(f"  Final constant: {ZZ(final_val)}")
    
    # Check all final evaluations are the same (constant poly)
    is_constant = all(e == final_val for e in current_evals)
    transcript.append(f"  All final evals equal? {is_constant}")
    
    if not is_constant:
        transcript.append("  REJECT: final layer not constant!")
        return False, transcript
    
    # QUERY PHASE
    transcript.append(f"\n=== QUERY PHASE ({n_queries} queries) ===")
    
    for q in range(n_queries):
        qi = rng.randint(0, len(domain) // 2 - 1)
        ok, fail_round = fri_verify_query(all_rounds, fold_challenges, qi)
        status = "PASS" if ok else f"FAIL round {fail_round}"
        transcript.append(f"  Query {q}: index={qi} → {status}")
        if not ok:
            transcript.append("  REJECT: inconsistent folding!")
            return False, transcript
    
    transcript.append("\n=== ACCEPT ===")
    return True, transcript

# Run on honest polynomial
print("--- Honest Prover ---")
accept, log = fri_protocol(f, D)
for line in log:
    print(line)

# Run on cheating polynomial
print("--- Cheating Prover (degree 7 claiming degree < 4) ---")
accept_cheat, log_cheat = fri_protocol(f_cheat, D)
for line in log_cheat:
    print(line)

9. Why FRI Matters for STARKs

FRI is the polynomial commitment scheme used in STARKs. Here's how it fits into the bigger picture:

Step	SNARK (Groth16)	STARK
Computation → constraints	Arithmetic circuit → R1CS	Arithmetic circuit → AIR (Algebraic Intermediate Representation)
Constraints → polynomial	R1CS → QAP	AIR → composition polynomial
Polynomial commitment	Trusted setup (CRS + pairings)	FRI (hash-based, no setup)
Verification	3 pairings	Merkle proofs + hash checks

Key Properties of FRI

Property	Value
Trust assumption	None (transparent)
Cryptographic assumption	Collision-resistant hash function only
Quantum resistance	Yes (no discrete log or pairing)
Proof size	$O(\log^2 n)$
Verification time	$O(\log^2 n)$
Prover time	$O(n \log n)$

Crypto foreshadowing. The next notebook compares SNARKs and STARKs head-to-head. The key trade-off: Groth16 has constant-size proofs (192 bytes) but needs a trusted setup. STARKs (via FRI) have larger proofs ($\sim$50-200 KB) but are transparent and quantum-resistant.

10. Exercises

Exercise 1 (Worked): Manual Folding

Problem. Take $g(x) = 1 + 3x + 5x^2 + 7x^3$. Split it into even/odd parts and fold with $\alpha = 2$.

Solution:

# Exercise 1: Worked solution
g = R(1 + 3*X + 5*X^2 + 7*X^3)
print(f"g(x) = {g}")

# Step 1: Even-odd split
g_even, g_odd = even_odd_split(g)
print(f"\nStep 1: Split into even/odd parts")
print(f"  g_even(y) = {g_even}  (coefficients of x⁰, x²)")
print(f"  g_odd(y)  = {g_odd}  (coefficients of x¹, x³)")

# Step 2: Verify decomposition
check = g_even(X^2) + X * g_odd(X^2)
print(f"\nStep 2: Verify g(x) = g_even(x²) + x·g_odd(x²)")
print(f"  Reconstruction = {check}")
print(f"  Matches? {check == g}")

# Step 3: Fold with α = 2
alpha_ex = F(2)
g_folded = g_even + alpha_ex * g_odd
print(f"\nStep 3: Fold with α = {alpha_ex}")
print(f"  g₁(y) = g_even(y) + {alpha_ex}·g_odd(y) = {g_folded}")
print(f"  Degree: {g.degree()} → {g_folded.degree()} (halved!)")

Exercise 2 (Guided): FRI with Different Rate

Problem. Run FRI on $f(x) = 2 + x + 4x^2 + 3x^3$ using a domain of size 32 (rate $\rho = 4/32 = 1/8$). Compare the number of rounds with the rate-$1/4$ case.

Fill in the TODOs:

# Exercise 2: fill in the TODOs

# TODO 1: Create domain of size 32
# omega_32 = g^(256 // 32)  # primitive 32nd root of unity
# D_32 = [omega_32^i for i in range(32)]

# TODO 2: Define the polynomial
# f_ex2 = R(2 + X + 4*X^2 + 3*X^3)

# TODO 3: Run FRI with enough challenges to fold to constant
# How many rounds needed? degree 3 → 1 → 0 = 2 rounds
# challenges_ex2 = [F(13), F(17)]
# rounds_ex2 = fri_commit(f_ex2, D_32, challenges_ex2)

# TODO 4: Print results and compare
# for i, (poly, dom, evals) in enumerate(rounds_ex2):
#     print(f"Round {i}: degree {poly.degree()}, domain size {len(dom)}")
#
# print(f"\nRate 1/4: domain 16, same number of folding rounds")
# print(f"Rate 1/8: domain 32, same number of folding rounds")
# print(f"Observation: more redundancy → better soundness per query")

Exercise 3 (Independent): Degree-7 FRI

Problem.

1. Create a random polynomial of degree 7 over $\mathbb{F}_{257}$.

2. Choose an appropriate domain size (what should the blowup factor be?).

3. Run the full FRI protocol and verify it accepts.

4. How many folding rounds are needed? How many Merkle commitments does the prover send?

# Exercise 3: write your solution here

Summary

Concept	Key Fact
Reed-Solomon code	Evaluations of degree-$<d$ polynomial on domain $D$; low degree ↔ valid codeword
Even-odd split	$f(x) = f_e(x^2) + x \cdot f_o(x^2)$; each half has half the degree
FRI folding	$f'(y) = f_e(y) + \alpha \cdot f_o(y)$; random $\alpha$ from verifier
Domain halving	$D \to D^2 = \{d^2 : d \in D\}$; squaring maps $\pm d$ to same point
Merkle commitment	Hash evaluations into tree; prover can't change values after commit
Verification	Spot-check $O(\lambda)$ queries, each checking $O(\log n)$ folding steps
Transparency	No trusted setup, only hash functions needed

FRI is the heart of STARKs: it replaces the pairing-based polynomial commitment of SNARKs with a purely hash-based one. The trade-off is larger proofs ($O(\log^2 n)$ vs constant), but with no trusted setup and post-quantum security.

---

Next: 10f: STARKs vs SNARKs