A. StarkNet
Cairo VM execution is compiled to AIR, proven with STARKs, recursively aggregated, and settled on Ethereum.
STARK Tower
zk-STARK · AIR + FRI · Post-Quantum
Run a real (if small) STARK in your browser — build a trace polynomial and AIR constraints, commit with a SHA-256 Merkle tree, and watch a FRI low-degree test decide whether the proof is accepted or the cheat is caught.
This demo runs a real (if small) STARK in your browser over the STARK-101 field p = 3·2³⁰ + 1: a trace polynomial, a constraint quotient, a SHA-256 Merkle commitment, and a genuine FRI low-degree test. The one idea everything builds toward — a tampered trace is caught by the proof system itself, not by recomputing Fibonacci — is demonstrated live in Exhibit 05.
EXHIBIT 01Orientation
STARKs vs SNARKs: Key Differences
Both prove a statement was computed correctly while revealing little about how. They differ in what they trust and what they cost.
Side-by-side
| Property | STARK | SNARK (Groth16 / PLONK) |
|---|---|---|
| Trusted setup | None — transparent, public randomness from transcript hashing | Required (per-circuit or universal ceremony) |
| Cryptographic assumption | Collision-resistant hash + FRI soundness | Pairings / discrete log (elliptic curves) |
| Post-quantum | Conjectured secure | Broken by Shor's algorithm |
| Proof size | Large (~45–200 KB) | Tiny (Groth16 ~128 bytes) |
| Prover scaling | Quasi-linear in computation size | Quasi-linear, larger constants |
| Core stack | AIR constraints + FRI + hash commitments | R1CS/Plonkish + polynomial commitments + pairings |
Why this matters: StarkNet, StarkEx, Polygon Miden, and Risc Zero all chose STARK architecture because transparency (no toxic waste) and post-quantum posture outweigh proof size for their use cases.
EXHIBIT 02AIR + Fibonacci
Step 1 — Arithmetic Intermediate Representation (AIR)
AIR expresses a computation as a trace (a table of field elements) plus constraints that every honest trace must satisfy. We use single-column Fibonacci: t[0] = t[1] = 1 and t[i+2] = t[i+1] + t[i].
The prover interpolates the trace into a polynomial f of degree below the trace length. "The trace is valid" becomes "f is genuinely low degree" — the claim FRI will later test.
Build & check the AIR
Ready.
What the verifier never sees
- The full execution trace
- Almost all intermediate values
- The prover's polynomials in full
It will only ever open a handful of committed points and run a low-degree test.
Trace table
Constraint residuals
Why this matters: AIR is the compilation target for StarkNet Cairo, Miden VM, and Risc Zero zkVM execution traces. Try Tamper a row and watch a residual become nonzero — that single broken constraint is what the rest of the protocol amplifies into a rejection.
EXHIBIT 02·5The missing middle step
From “constraint broken” to “degree too high”
Here is the step every STARK explainer skips. Exhibit 02 showed a broken constraint as a nonzero residual. But FRI does not test residuals — it tests degree. This panel is the converter between the two.
The transition rule t[i+2] = t[i+1] + t[i] becomes a polynomial C(x)The constraint polynomial: C(x) = f(w²x) − f(wx) − f(x). It is zero at every trace step where the rule holds. that must be zero at every step. So C should be divisible by the vanishing polynomialZ(x) is zero at exactly the trace steps the rule covers. If C is zero there too, Z divides C with no remainder. Z(x) that is zero at exactly those steps. The prover commits to the quotientQ(x) = C(x) / Z(x). It is a genuine low-degree polynomial only when the division is clean — i.e. only when every constraint held. Q(x) = C(x) / Z(x). Watch what the division does:
Divide the same trace
Ready.
The one number that decides everything
C(x) ÷ Z(x), step by step
Why this matters: … A clean division keeps
Q low degree; a nonzero remainder forces Q’s degree up to nearly the domain size. That degree explosion is exactly the signal the next exhibit’s FRI test rejects — so a broken constraint and a failed low-degree test are the same event, seen twice.EXHIBIT 03FRI Low-Degree Test
Step 2 — FRI: The Heart of STARKs
FRI proves a committed polynomial is close to low degree using only hashes and verifier challenges — no trusted setup. Each round halves the degree and the domain. After enough rounds, an honest polynomial becomes a single constant. That final constant is the whole verdict.
FRI controls
Ready.
Proof size estimate
Roughly: queries × folds × 2 openings × path length × 32-byte hashes.
Folding rounds
Folding, visualized
- The top row is the full evaluation domain — one dot per point where the polynomial was committed.
- Each fold pairs a point with its negative (
xand−x, the two parents of one child) and combines them throughx²into a single point one row down. - That halves both the domain and the degree. After enough folds only the bottom row is left: one dot. If it is a single constant (green), FRI accepts; if the dots differ (red), it rejects.
Why this matters: FRI is transparent low-degree testing from hashes alone. Tick the cheat box: the final layer stops being constant, so FRI rejects — and it did so without ever looking at a trace.
EXHIBIT 04Proof Size Tradeoff
The Cost: Proof Size
Representative benchmarks
Log-scale proof size (bytes)
Measured here: …
Security ↔ size ↔ speed: the tradeoff triangle
Soundness comes from two knobs: the blowup (code rate) and the number of FRI queries. More of either buys security bits — and costs proof size and verifier time. Move the sliders.
96≈ security bits
—a liar slips through
—≈ FRI query bytes
Recursive STARK aggregation compresses many proofs into one L1-submitted proof — central to StarkNet and other rollups. Fiat-Shamir turns verifier randomness into transcript-derived hash challenges, making everything non-interactive in the random-oracle model.
The practical question is never "is 100 KB big?" but "does trust minimization plus post-quantum posture justify the bytes?" Off-chain, it almost always does; under tight on-chain gas, often not.
EXHIBIT 05End-to-End STARK
Step 3 — Prove and Verify in the Browser
Watch for this: after Corrupt trace → Verify proof, the failing check is "FRI low-degree test", not a trace recomputation. That is the entire point of a STARK: the cheat is caught algebraically, succinctly, blind to the witness.
Protocol run
No proof generated yet.
Prover transcript
Verifier report
Succinctness — what the verifier actually examined
Generate a proof to see how few committed values the verifier inspects.
Inspect one query
EXHIBIT 05·ZKZero-Knowledge
The "zk" in zk-STARK
The verifier opens a few evaluations of the trace polynomial. Without protection, those points leak information about the witness. The zero-knowledge fix masks the trace as f′(x) = f(x) + (xᴺ−1)·r(x) with fresh random r: on the trace domain f′ = f (so every constraint is untouched), but on the opened coset points the values are blinded by randomness independent of the witness.
Below we draw many masked openings of the same point with fresh randomness and compare them to a witness-free simulator that just emits uniform field elements. If masking works, the two distributions are indistinguishable and the true value never stands out.
Step 1 — watch one masked opening change
The verifier opens the trace polynomial at a fixed point. Click repeatedly: the secret value f(x) never changes, but the value the verifier actually receives is different every single time — fresh randomness blinds it.
Step 2 — the accumulated distribution vs. a witness-free simulator
Now draw many masked openings of that same point and pile them into a histogram. Overlay a simulator that knows no secret at all and just emits uniform noise. If masking works, the two shapes are indistinguishable.
Because the masked value looks like uniform noise no matter what the secret was, the secret cannot be read off it. That “the two distributions match” is the hiding property.
Honesty note: this measures the necessary condition — revealed values distributed independently of the witness. It is strong evidence, not a formal zero-knowledge proof, which additionally argues a simulator can reproduce entire transcripts. Try the Zero-knowledge mode checkbox above: the proof still verifies, but its trace commitment changes on every run.
What a production STARK still adds on top of this demo
Already implemented here: per-constraint degree adjustment (αᵢ + βᵢ·x^(D−dᵢ), so a cheater cannot hide a high-degree term in a low-degree slot) and optional zero-knowledge masking of the trace polynomial (demonstrated just above).
Real security parameters. Production systems target ~100-bit soundness: a larger blowup and dozens of queries (see Exhibit 04's calculator), plus longer traces (2¹⁰–2²⁴ rows) interpolated with NTTs instead of the O(n²) Lagrange interpolation used here for clarity.
A full zero-knowledge proof. We verify the masking empirically (openings independent of the witness). A production claim also exhibits a simulator that reproduces entire transcripts — commitments, paths, and FRI layers — without the witness, and masks the composition and FRI layers too.
DEEP / out-of-domain sampling. Stronger soundness samples the composition at a random point outside the evaluation domain, tightening the proximity gap. The core idea — commit, then prove low degree — is identical.
Why this matters: even at toy size, a few random queries plus one low-degree test catch an inconsistent trace with high probability — and the verifier's work is independent of how long the computation was.
EXHIBIT 06Production Deployments
STARKs in Production
B. StarkEx
Application-specific scaling for exchanges and games, including dYdX v3, ImmutableX, and Sorare deployments.
C. Risc Zero
A RISC-V zkVM proving general computation with STARK internals, commonly SNARK-wrapped for compact on-chain verification.
D. Polygon Miden
A STARK-based VM with AIR constraints and a recursion pipeline for compressed proofs.
Cross-demo links
Why this matters: STARKs are deployed infrastructure for scalability and integrity proofs, not just research prototypes.