starks-starknet.ipynb

Kernel: SageMath 10.0

Connect: STARKs in StarkNet

Module 10 | Real-World Connections

StarkNet processes transactions off-chain and posts STARK proofs to Ethereum for verification.

Introduction

StarkNet is a ZK rollup on Ethereum: it executes transactions off-chain, generates a STARK proof that all transactions were executed correctly, and posts only the proof to Ethereum. This achieves:

Property	Ethereum L1	StarkNet L2
Execution	On-chain (every node)	Off-chain (prover only)
Verification	Re-execute	Verify STARK proof
Throughput	~15 TPS	~100-1000+ TPS
Cost per tx	$1-50	$0.01-0.10
Trust model	Consensus	Math (no trusted setup)

The STARK proof system uses the FRI protocol (Notebook 10e) as its polynomial commitment scheme, achieving transparency (no trusted setup) and quantum resistance.

STARKs vs SNARKs in Practice

Feature	Groth16 (SNARK)	STARK
Trusted setup	Yes (circuit-specific ceremony)	No (transparent)
Proof size	192 bytes	~50-200 KB
Verification time	~5 ms (3 pairings)	~10-50 ms (hash checks)
Prover time	$O(n \log n)$	$O(n \log^2 n)$
Crypto assumption	Pairings, DLP	Hash functions only
Quantum resistance	No	Yes
Proof aggregation	Hard	Natural (recursive STARKs)

StarkNet chose STARKs because:

1. No trusted setup needed (critical for decentralization)

2. Quantum resistance (future-proofing)

3. Fast prover for large computations

4. Natural recursion for batching proofs

# === The STARK pipeline: execution trace -> AIR -> FRI ===

p = 257  # same field as Notebook 10e (Fermat prime, 2^8 + 1)
F = GF(p)
R.<X> = PolynomialRing(F)

# Step 1: Execution Trace
# In StarkNet, the execution trace records every step of a Cairo program.
# We'll use a simple example: compute Fibonacci numbers mod p.

# Fibonacci: a_{i+2} = a_{i+1} + a_i
# Execution trace: [(a_0, a_1), (a_1, a_2), (a_2, a_3), ...]

n_steps = 8  # must be power of 2 for FRI
trace_col0 = [F(0)] * n_steps  # first column: a_i
trace_col1 = [F(0)] * n_steps  # second column: a_{i+1}

# Initial values
trace_col0[0] = F(1)
trace_col1[0] = F(1)

# Fill the trace
for i in range(1, n_steps):
    trace_col0[i] = trace_col1[i-1]
    trace_col1[i] = trace_col0[i-1] + trace_col1[i-1]

print("=== Execution Trace (Fibonacci mod 257) ===")
for i in range(n_steps):

print(f"\nThe prover claims: starting from (1,1), after {n_steps} Fibonacci steps,")
print(f"the final value is a_{n_steps} = {ZZ(trace_col1[-1])}.")
print(f"This is the execution trace that StarkNet would generate.")

# Step 2: Encode trace as polynomials
# Interpolate each column over a domain of size n_steps

g = F.multiplicative_generator()
omega = g^(256 // n_steps)  # primitive n_steps-th root of unity
trace_domain = [omega^i for i in range(n_steps)]

print(f"Trace domain: omega = {omega}, omega^{n_steps} = {omega^n_steps}")
print(f"Domain points: {[ZZ(d) for d in trace_domain]}")
print()

# Interpolate: find polynomial f such that f(omega^i) = trace[i]
points_col0 = list(zip(trace_domain, trace_col0))
points_col1 = list(zip(trace_domain, trace_col1))

f0 = R.lagrange_polynomial(points_col0)  # polynomial for column 0
f1 = R.lagrange_polynomial(points_col1)  # polynomial for column 1

print(f"Trace polynomial f0(x) = {f0}")
print(f"  degree: {f0.degree()} (< {n_steps})")
print(f"Trace polynomial f1(x) = {f1}")
print(f"  degree: {f1.degree()} (< {n_steps})")
print()

# Verify interpolation
print("Verification: f0(omega^i) should equal trace_col0[i]")
all_correct = all(f0(trace_domain[i]) == trace_col0[i] for i in range(n_steps))
print(f"  All correct? {all_correct}")

# Step 3: AIR Constraints (Algebraic Intermediate Representation)
#
# The Fibonacci recurrence imposes constraints on consecutive rows:
#   f0(omega * x) = f1(x)           (column 0 shifts by one step)
#   f1(omega * x) = f0(x) + f1(x)   (Fibonacci rule)
#
# These must hold for x in {omega^0, ..., omega^(n-2)} (all but the last row)

# Constraint 1: f0(omega * x) - f1(x) = 0
# Constraint 2: f1(omega * x) - f0(x) - f1(x) = 0

# Construct the constraint polynomials
# We evaluate f0(omega * x) by substituting omega*X into f0
f0_shifted = f0(omega * X)  # f0 evaluated at the next trace row
f1_shifted = f1(omega * X)  # f1 evaluated at the next trace row

constraint1 = f0_shifted - f1
constraint2 = f1_shifted - f0 - f1

print("=== AIR Constraints ===")
print(f"Constraint 1: f0(omega*x) - f1(x)")
print(f"  degree: {constraint1.degree()}")
print(f"Constraint 2: f1(omega*x) - f0(x) - f1(x)")
print(f"  degree: {constraint2.degree()}")
print()

# These constraints should vanish on {omega^0, ..., omega^(n-2)}
# That is, on all points EXCEPT the last step omega^(n-1)
print("Checking constraints on trace domain (except last row):")
for i in range(n_steps - 1):
    x_val = trace_domain[i]
    c1_val = constraint1(x_val)
    c2_val = constraint2(x_val)
    print(f"  x = omega^{i} = {ZZ(x_val)}: C1 = {ZZ(c1_val)}, C2 = {ZZ(c2_val)}")

print(f"\nBoth constraints are 0 on all valid trace rows.")

# Step 4: Vanishing polynomial and composition
#
# The constraints vanish on D' = {omega^0, ..., omega^(n-2)}
# The vanishing polynomial for D' is:
#   Z'(x) = (x^n - 1) / (x - omega^(n-1))

# Vanishing polynomial for the full domain
Z_full = X^n_steps - 1  # vanishes on all of {omega^0, ..., omega^(n-1)}

# Remove the last point
last_point = omega^(n_steps - 1)
Z_constraint = Z_full // (X - last_point)

print("=== Composition Polynomial ===")
print(f"Vanishing polynomial Z'(x) = (x^{n_steps} - 1) / (x - {ZZ(last_point)})")
print(f"  degree: {Z_constraint.degree()}")
print()

# The STARK prover computes the composition polynomial:
#   C(x) = constraint1(x) / Z'(x) + alpha * constraint2(x) / Z'(x)
# where alpha is a random challenge from the verifier

# If the constraints truly vanish on D', division is exact
h1, r1 = constraint1.quo_rem(Z_constraint)
h2, r2 = constraint2.quo_rem(Z_constraint)

print(f"Division check:")
print(f"  C1 / Z': quotient degree {h1.degree()}, remainder = {r1}")
print(f"  C2 / Z': quotient degree {h2.degree()}, remainder = {r2}")
print(f"  Exact division? C1: {r1 == 0}, C2: {r2 == 0}")
print()

# Random combination (Fiat-Shamir challenge)
alpha_comb = F(7)
composition = h1 + alpha_comb * h2
print(f"Composition polynomial: H(x) = h1(x) + {alpha_comb}*h2(x)")
print(f"  degree: {composition.degree()}")
print(f"\nThis composition polynomial is what FRI proves is low-degree.")
print(f"Low degree => constraints are satisfied => computation is correct.")

The FRI Protocol in Action

StarkNet's prover now runs FRI on the composition polynomial to prove it is low-degree. This is the connection to Notebook 10e:

1. Evaluate the composition polynomial on a larger domain (blowup factor 4-8)

2. Commit via Merkle tree

3. Fold repeatedly, halving the degree each round

4. Verify by spot-checking consistency of folding steps

The proof consists of Merkle roots and authentication paths.

# === Run FRI on the composition polynomial ===

import hashlib

# Evaluation domain: 4x blowup
eval_domain_size = 4 * n_steps  # 32 points
omega_eval = g^(256 // eval_domain_size)
eval_domain = [omega_eval^i for i in range(eval_domain_size)]

# Evaluate composition polynomial on the evaluation domain
comp_evals = [composition(d) for d in eval_domain]

print(f"=== FRI Setup ===")
print(f"Composition polynomial degree: {composition.degree()}")
print(f"Evaluation domain size: {eval_domain_size}")
print(f"Rate: {composition.degree() + 1}/{eval_domain_size} = 1/{eval_domain_size // (composition.degree() + 1)}")
print()

# Merkle commitment
def merkle_root(values):
    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])
        leaves = [hashlib.sha256(leaves[i] + leaves[i+1]).digest()
                  for i in range(0, len(leaves), 2)]
    return leaves[0].hex()[:16]

root = merkle_root(comp_evals)
print(f"Merkle commitment: {root}...")
print(f"This is the first thing the prover sends.")
print()

# FRI folding
def even_odd_split(poly):
    coeffs = poly.padded_list(poly.degree() + 1) if poly.degree() >= 0 else [F(0)]
    if len(coeffs) % 2 == 1:
        coeffs.append(F(0))
    return R(coeffs[0::2]), R(coeffs[1::2])

def fri_fold(poly, alpha, domain):
    f_even, f_odd = even_odd_split(poly)
    folded = f_even + alpha * f_odd
    new_domain = sorted(set(d^2 for d in domain), key=lambda x: ZZ(x))
    return folded, new_domain

# Fold until constant
current = composition
current_domain = eval_domain
round_num = 0
challenges = [F(13), F(29), F(41)]  # Fiat-Shamir challenges

print(f"=== FRI Folding ===")
print(f"Round {round_num}: degree {current.degree()}, domain size {len(current_domain)}")

for alpha_fri in challenges:
    if current.degree() <= 0:
        break
    current, current_domain = fri_fold(current, alpha_fri, current_domain)
    round_num += 1
    print(f"Round {round_num}: degree {current.degree()}, domain size {len(current_domain)}, alpha = {alpha_fri}")

print(f"\nFinal constant: {ZZ(current.constant_coefficient())}")
print(f"Prover sends: {round_num} Merkle roots + final constant")

Recursive STARKs and SHARP

StarkNet uses SHARP (Shared Prover) to batch multiple transactions into one proof:

1. Collect 100-1000 transactions

2. Execute them all, producing a large execution trace

3. Generate ONE STARK proof for the entire batch

4. Post the proof to Ethereum L1

For even more efficiency, StarkNet uses recursive STARKs: prove that you verified a previous STARK proof, compressing multiple proofs into one.

Batch 1 (100 txs) --> STARK proof P1
Batch 2 (100 txs) --> STARK proof P2
Batch 3 (100 txs) --> STARK proof P3
                        |
                        v
Recursive proof: "P1, P2, P3 are all valid" --> STARK proof P_combined
                        |
                        v
                Post P_combined to Ethereum (one proof for 300 txs)

# === Cost analysis: STARK proof batching ===

print("=== StarkNet Proof Economics ===")
print()

# L1 Ethereum gas costs
gas_per_calldata_byte = 16  # EIP-4844 makes this cheaper with blobs
l1_gas_price_gwei = 30  # typical gas price
gwei_per_eth = 10^9

# STARK proof sizes
stark_proof_kb = 100  # ~100 KB typical
stark_proof_bytes = stark_proof_kb * 1024

# Cost per proof on L1
calldata_gas = stark_proof_bytes * gas_per_calldata_byte
verification_gas = 500000  # STARK verification on-chain
total_gas = calldata_gas + verification_gas

# Cost in ETH
cost_gwei = total_gas * l1_gas_price_gwei
cost_eth = cost_gwei / gwei_per_eth

print("Metric Value")print("STARK proof size ~100 KB")print(f"Calldata gas {f'{calldata_gas:,} gas':>15}")
print(f"Verification gas {f'{verification_gas:,} gas':>15}")
print(f"Total gas per proof {f'{total_gas:,} gas':>15}")
print()

# Amortize over transactions
for n_txs in [10, 100, 1000, 10000]:
    cost_per_tx = total_gas / n_txs
    print(f"  {n_txs} txs/batch: {cost_per_tx:>10,.0f} gas/tx")

print(f"\nWith 10,000 txs per batch, each tx costs ~{total_gas/10000:.0f} gas")
print(f"vs ~21,000 gas for a basic L1 Ethereum transfer.")
print(f"That is a ~{21000 / (total_gas / 10000):.0f}x cost reduction!")

Cairo: StarkNet's STARK-Native Language

StarkNet programs are written in Cairo, a language designed to produce execution traces that are efficient for STARK proving:

• Every Cairo program compiles to an algebraic execution trace

• The trace satisfies AIR constraints (Algebraic Intermediate Representation)

• The constraints are checked by FRI polynomial proximity testing

Cairo's computational model is based on a register machine where all operations are field arithmetic over a large prime field ($p \approx 2^{251}$ in production).

# === Concept Map: Module 10 -> StarkNet ===

print("=== Concept Map ===")
print()
concept_map = [
    ("Execution trace", "AIR constraints",
     "Cairo program produces trace; AIR encodes correctness rules"),
    ("Polynomial interpolation", "Trace polynomials",
     "Trace columns become polynomials over evaluation domain"),
    ("Vanishing polynomial", "Constraint satisfaction",
     "Constraints vanish on trace domain iff computation is correct"),
    ("FRI protocol", "Polynomial commitment",
     "Proves composition polynomial is low-degree (hash-based, transparent)"),
    ("Merkle trees", "Commitment scheme",
     "Prover commits to evaluations; verifier spot-checks"),
    ("Fiat-Shamir", "Non-interactive proofs",
     "Hash-based challenges make the protocol non-interactive"),
    ("Recursive STARKs", "Proof batching",
     "SHARP batches thousands of txs into one Ethereum proof"),
]

for concept, application, explanation in concept_map:
    print(f"  {concept} --> {application}")
    print(f"    {explanation}")
    print()

Summary

Concept	Key idea
Cairo programs	Produce algebraic execution traces that are natural inputs to the STARK pipeline
AIR constraints	Enforce computational correctness as polynomial identities over the trace
FRI protocol	Proves the composition polynomial is low-degree, confirming all constraints hold
Transparency	No trusted setup needed. All verifier randomness comes from Fiat-Shamir hashing
SHARP batching	Thousands of transactions compressed into a single proof posted to Ethereum
Recursive STARKs	Multiple proofs compressed into one, further reducing L1 costs

The trade-off vs Groth16: proofs are larger (~100 KB vs 192 bytes), but transparency and quantum resistance make STARKs attractive for large-scale rollups.

---

Back to Module 10: SNARKs and STARKs