recursive-snarks-mina.ipynb

Kernel: SageMath 10.0

Connect: Recursive SNARKs in Mina

Module 10 | Real-World Connections

Mina maintains a constant-size (~22 KB) blockchain by recursively composing SNARK proofs.

Introduction

Most blockchains grow without bound. To verify Bitcoin, you download ~500 GB. For Ethereum, ~1 TB. The more transactions, the larger the chain.

Mina takes a radically different approach: the entire blockchain state is always represented by a single SNARK proof of approximately 22 KB.

Blockchain	Full verification data	Growth rate
Bitcoin	~500 GB	~60 GB/year
Ethereum	~1 TB	~200 GB/year
Mina	~22 KB	Constant

The key idea: recursive proof composition. Each new block includes a SNARK that proves "the previous proof was valid AND this new block is valid." The chain of proofs collapses into a single proof.

Recursive Composition: The Core Idea

A recursive SNARK proves a statement of the form:

$$\pi_{n} \text{ proves: } \begin{cases} \text{The proof } \pi_{n-1} \text{ is valid} \\ \text{Block } n \text{ is a valid transition from state } S_{n-1} \text{ to } S_n \end{cases}$$

This means:

• $\pi_1$ proves: "Block 1 is valid"

• $\pi_2$ proves: "$\pi_1$ is valid AND block 2 is valid"

• $\pi_3$ proves: "$\pi_2$ is valid AND block 3 is valid"

• $\pi_n$ proves: "The ENTIRE chain from block 1 to block $n$ is valid"

Each $\pi_i$ has the same size regardless of $i$. After a million blocks, the proof is still 22 KB.

# === Simulate recursive proof composition ===

p = 101
F = GF(p)

# We model a simple blockchain:
# - State = running sum of transaction values (mod p)
# - Each block adds a transaction value
# - Validity: the state transition is correctly computed

# Simulated Groth16-style proof: (a, b, c) satisfying a*b = alpha*beta + pub + c*delta
set_random_seed(55)
alpha = F.random_element()
while alpha == 0: alpha = F.random_element()
beta = F.random_element()
while beta == 0: beta = F.random_element()
delta = F.random_element()
while delta == 0: delta = F.random_element()

alpha_beta = alpha * beta

def make_proof(public_input):
    """Create a simulated Groth16 proof for a given public input."""
    # Prover has the witness; we just simulate the proof structure
    a = alpha + F.random_element()
    b = beta + F.random_element()
    c = (a * b - alpha_beta - public_input) * delta^(-1)
    return (a, b, c)

def verify_proof(proof, public_input):
    """Verify a simulated Groth16 proof."""
    a, b, c = proof
    return a * b == alpha_beta + public_input + c * delta

# Genesis state
state = F(0)
transactions = [F(7), F(13), F(25), F(4), F(52)]

print("=== Recursive Blockchain (Mina-style) ===")
print(f"Genesis state: S_0 = {state}")
print()

proofs = []
states = [state]

for i, tx in enumerate(transactions):
    new_state = state + tx
    
    # The public input encodes: (old_state, new_state, tx_value)
    # Simplified: public_input = hash of the state transition
    pub = state + new_state + tx  # simplified "hash"
    
    # Create proof for this block
    proof = make_proof(pub)
    valid = verify_proof(proof, pub)
    
    proofs.append(proof)
    states.append(new_state)
    
    print(f"Block {i+1}: tx = +{ZZ(tx)}, state {ZZ(state)} -> {ZZ(new_state)}")
    print(f"  Proof: a={proof[0]}, b={proof[1]}, c={proof[2]}")
    print(f"  Valid? {valid}")
    print(f"  Proof size: 3 field elements (constant!)")
    print()
    
    state = new_state

print(f"Final state after {len(transactions)} blocks: S_{len(transactions)} = {ZZ(state)}")
print(f"A new node only needs the LAST proof to verify the entire chain.")

# === The recursive circuit: what does each proof actually prove? ===

print("=== Inside the Recursive Circuit ===")
print()
print("Each block's SNARK circuit proves TWO things:")
print()
print("1. TRANSITION VALIDITY (the easy part):")
print("   'new_state = old_state + tx_value'")
print("   This is a simple addition constraint.")
print(f"   Example: {ZZ(states[-2])} + {ZZ(transactions[-1])} = {ZZ(states[-1])}")
print()
print("2. PREVIOUS PROOF VALIDITY (the hard part):")
print("   'The SNARK proof pi_{n-1} verifies correctly'")
print("   This means the circuit contains a SNARK VERIFIER.")
print("   The verifier computation is itself encoded as R1CS constraints.")
print()
print("The recursive step is what makes this work:")
print("  pi_n proves: verify(pi_{n-1}) = true AND transition(S_{n-1}, S_n) = true")
print()
print("This is conceptually simple but practically challenging because")
print("the SNARK verifier itself requires many constraints (~hundreds of thousands).")
print("Mina uses the Pasta curves (Pallas + Vesta) specifically designed for this.")

# === Simulate the recursive proof verification chain ===

print("=== Verification: Traditional vs Recursive ===")
print()

n_blocks = len(transactions)

# Traditional verification: check every block
print("Traditional (Bitcoin-style): verify ALL blocks")
total_checks = 0
s = F(0)
for i, tx in enumerate(transactions):
    s_new = s + tx
    check = (s_new == s + tx)  # verify transition
    total_checks += 1
    s = s_new
print(f"  Checks performed: {total_checks}")
print(f"  Data downloaded: all {n_blocks} blocks")
print(f"  Work scales with: O(n) where n = number of blocks")
print()

# Recursive verification: check ONE proof
print("Recursive (Mina-style): verify LAST proof only")
last_proof = proofs[-1]
last_pub = states[-2] + states[-1] + transactions[-1]
valid = verify_proof(last_proof, last_pub)
print(f"  Checks performed: 1 (the recursive proof)")
print(f"  Data downloaded: ~22 KB (one proof + state commitment)")
print(f"  Work scales with: O(1). CONSTANT regardless of chain length!")
print(f"  Proof valid? {valid}")
print()
print("If the last proof is valid, the entire chain history is valid.")
print("This is the power of recursive proof composition.")

The Pickles Proof System

Mina uses Pickles, a recursive proof system built on:

• Kimchi: a Plonk-based proof system (more flexible than Groth16's R1CS)

• IPA (Inner Product Arguments): a polynomial commitment scheme

• Pasta curves (Pallas and Vesta): a cycle of elliptic curves designed for recursion

Why a Curve Cycle?

The key challenge in recursive SNARKs: to verify a proof over curve $E_1$, you need to do field arithmetic in $E_1$'s scalar field. But if you're building a circuit over $E_1$, the native field is $E_1$'s base field.

Solution: use two curves where each curve's base field equals the other's scalar field:

	Pallas	Vesta
Base field	$\mathbb{F}_p$	$\mathbb{F}_q$
Scalar field	$\mathbb{F}_q$	$\mathbb{F}_p$

Block $n$ (even): prove on Pallas, verify previous Vesta proof natively. Block $n+1$ (odd): prove on Vesta, verify previous Pallas proof natively.

# === Demonstrate the curve cycle idea ===

# We use a toy example: two small "paired" primes
# In reality, Pallas and Vesta are designed so that:
#   |E_pallas(F_p)| = q  and  |E_vesta(F_q)| = p

# Toy cycle: two primes where each is the group order of an
# elliptic curve over the other
p_pallas = 101
q_vesta = 97  # these are "paired" in our toy example

F_pallas = GF(p_pallas)
F_vesta = GF(q_vesta)

print("=== Toy Curve Cycle (Pallas/Vesta analogy) ===")
print(f"Pallas-like: arithmetic in F_{p_pallas}, scalar field F_{q_vesta}")
print(f"Vesta-like:  arithmetic in F_{q_vesta}, scalar field F_{p_pallas}")
print()
print("Recursive proof chain:")
print(f"  Block 1: prove on 'Pallas' (native field F_{p_pallas})")
print(f"    Circuit verifies: block 1 transition")
print(f"  Block 2: prove on 'Vesta' (native field F_{q_vesta})")
print(f"    Circuit verifies: block 2 transition + verify Pallas proof")
print(f"    (Pallas scalar field = F_{q_vesta} = Vesta native field!)")
print(f"  Block 3: prove on 'Pallas' (native field F_{p_pallas})")
print(f"    Circuit verifies: block 3 transition + verify Vesta proof")
print(f"    (Vesta scalar field = F_{p_pallas} = Pallas native field!)")
print()
print("The curve cycle eliminates the field mismatch problem.")
print("Each curve can natively verify proofs from the other curve.")

# === Incrementally Verifiable Computation (IVC) ===

print("=== Incrementally Verifiable Computation ===")
print()
print("Mina's recursive SNARKs implement IVC:")
print("  Given: a computation f applied n times")
print("    f(f(f(...f(x_0)...))) = x_n")
print("  Prove: x_n is the correct result, with a proof of size O(1)")
print()

# Demonstrate with iterated squaring
# f(x) = x^2 mod p, applied repeatedly
x = F_pallas(3)
n_iterations = 10

print(f"Example: f(x) = x^2 mod {p_pallas}, starting from x_0 = {x}")

for i in range(n_iterations):
    x_new = x^2
    proof_scope = f"steps 0..{i+1} (O(1) size)"
    x = x_new

print(f"\nFinal result: x_{n_iterations} = {ZZ(x)}")
print(f"Proof size: constant (~22 KB), regardless of {n_iterations} steps")
print(f"Verification cost: constant (one proof check)")
print(f"\nWithout IVC: verifier would need to re-execute all {n_iterations} steps.")
print(f"With IVC: verifier checks ONE proof, done.")

Comparison: Blockchain Verification Models

Model	Data needed	Verification work	Trust assumption
Full node (Bitcoin)	Entire chain (~500 GB)	Replay all txs	None (verify everything)
SPV (light client)	Block headers (~50 MB)	Check Merkle proofs	Trust miners (majority honest)
Mina (recursive SNARK)	One proof (~22 KB)	One verification	Math (proof system soundness)

# === Size comparison over time ===

print("=== Blockchain Size Over Time ===")
print()

# Approximate chain sizes (GB)
years = [2015, 2017, 2019, 2021, 2023, 2025]
bitcoin_gb = [50, 150, 250, 370, 500, 580]
ethereum_gb = [1, 50, 200, 500, 900, 1200]
mina_kb = 22  # always

for i, year in enumerate(years):
    btc = f"{bitcoin_gb[i]} GB"
    eth = f"{ethereum_gb[i]} GB"
    mina = f"{mina_kb} KB"

print()
print(f"Bitcoin grows ~60 GB/year. Ethereum grows ~200 GB/year.")
print(f"Mina stays at {mina_kb} KB. Forever.")
print()
print(f"This means a Mina full node can run on a smartphone.")
print(f"True decentralization: anyone can verify the chain.")

Concept Map: Module 10 Concepts in Mina

Module 10 Concept	Mina Application
SNARK proof	Each block produces a proof of the entire chain's validity
Proof composition	$\pi_n$ proves: verify($\pi_{n-1}$) AND block $n$ is valid
SNARK verification circuit	The verifier is itself encoded as constraints inside the recursive circuit
Polynomial commitments (IPA)	Pickles uses Inner Product Arguments instead of pairings
Curve cycle (Pasta)	Pallas + Vesta enable native cross-curve verification
Constant-size proofs	~22 KB regardless of chain length

# === Trade-offs of Mina's approach ===

print("=== Trade-offs ===")
print()
print("Advantage Challenge")
tradeoffs = [
    ("Constant-size chain (~22 KB)",
     "Proving is computationally expensive"),
    ("Any device can be a full verifier",
     "Block production requires powerful hardware"),
    ("No growing storage requirements",
     "Historical data must be stored elsewhere"),
    ("Mathematically guaranteed validity",
     "Proof system complexity (Pickles/Kimchi)"),
    ("No trusted setup (IPA-based)",
     "Larger proofs than Groth16 (22 KB vs 192 B)"),
]

for adv, challenge in tradeoffs:
    print(f"{adv} {challenge}")

print()
print("Key insight: Mina trades prover work for verifier convenience.")
print("The prover does heavy computation so that the verifier barely needs to.")
print("This is the SNARK philosophy: compress computation into tiny proofs.")

Summary

Concept	Key idea
Recursive composition	Each block's SNARK proves the validity of the entire chain history
Constant-size blockchain	Always ~22 KB, regardless of the number of blocks
Pickles proof system	Plonk-based SNARKs with IPA commitments, no trusted setup required
Pasta curves	A cycle of curves (Pallas + Vesta) enabling efficient cross-curve recursion
Incrementally verifiable computation	Verify the whole chain with one proof check in constant time

The recursive SNARK paradigm is one of the most powerful ideas in modern cryptography: it transforms a linearly growing verification problem into a constant-time one.

---

Back to Module 10: SNARKs and STARKs