From a ceremony in the dark to a proof in the sunlight
In the last guide you saw how a zk-SNARK gets its magic: it folds a constraint system into polynomials and commits to them with a KZG commitment. But that commitment has a price — it needs a structured reference string baked in a trusted setup. Recall the powers-of-tau ceremony: dozens of people each mix in a secret, and as long as one of them honestly destroyed their fragment, the system is safe. The leftover secret is called toxic waste, and if an attacker ever reconstructs it, they can forge proofs of false statements that verify perfectly. You can never prove the waste was destroyed — you can only trust that it was.
A zk-STARK is the answer to a simple, stubborn question: *what if we needed no ceremony at all?* The acronym stands for Scalable Transparent ARgument of Knowledge. Transparent is the headline: there is no secret setup, no toxic waste, only public randomness anyone can re-derive. Scalable means the prover runs in near-linear time and the verifier in time that grows only polylogarithmically with the size of the computation. The construction, introduced by Eli Ben-Sasson and co-authors in 2018, leans on exactly one cryptographic ingredient you already trust: a collision-resistant hash function.
A computation is a table: the execution trace and AIR
SNARKs flatten a program into an arithmetic circuit and then R1CS. STARKs take a different, very physical view: write the computation down as a table of numbers over a finite field, where each row is one step of the machine and each column is a register. This table is the execution trace. The same secret inputs that formed your R1CS witness now live inside the trace.
What replaces R1CS is an AIR — Algebraic Intermediate Representation. Instead of one equation per gate, AIR gives you two kinds of rule: transition constraints that every adjacent pair of rows must satisfy (how one step follows from the last), and boundary constraints that pin down specific cells (the inputs and the claimed output). Take a tiny Fibonacci computation. Its trace is a single column, and the rule relating three consecutive rows is the whole program:
row | a AIR for Fibonacci over a finite field F_p
----+----- ------------------------------------------
0 | 1 boundary: a[0] = 1 , a[1] = 1
1 | 1 transition: a[i+2] - a[i+1] - a[i] = 0 (for all i)
2 | 2 boundary: a[7] = 21 (the claimed result)
3 | 3
4 | 5 # 1) interpolate the column into a polynomial f(x)
5 | 8 # over a domain D = {g^0, g^1, ..., g^7}, g a root of unity
6 | 13 # 2) the transition rule becomes ONE polynomial identity:
7 | 21 # C(x) = f(g^2 . x) - f(g . x) - f(x)
# C(x) must be ZERO on every trace point => divisible by
# the vanishing polynomial Z(x) = x^8 - 1
# 3) prover computes the quotient q(x) = C(x) / Z(x)
# if q(x) is a genuine low-degree polynomial, the trace was validThis is the pivot the rest of the protocol turns on. "Did the computation run correctly?" has become "Is this quotient polynomial actually low-degree?" The prover extends each trace polynomial over a domain much larger than the trace — a Reed–Solomon low-degree extension, typically 4× to 16× the trace length (the blow-up factor). On that big domain, a real degree-`d` polynomial and a forged high-degree imposter disagree almost everywhere, so a handful of random spot-checks can tell them apart. All STARK soundness ultimately reduces to a single sub-problem: proving a function is close to a low-degree polynomial.
Commit with hashes, not pairings
Here is where STARKs part ways with SNARKs at the deepest level. A SNARK commits to a polynomial with a polynomial commitment like KZG — one elliptic-curve group element, opened in constant size, but resting on pairing-based algebra and that toxic-waste setup. A STARK refuses all of it. To commit to a polynomial, the prover simply evaluates it on the whole big domain and Merkle-hashes the list of evaluations.
The Merkle root is the commitment. To "open" the polynomial at a point the verifier picks, the prover reveals that evaluation plus the `log(n)` sibling hashes of its Merkle path; the verifier rehashes up to the root to confirm the value was fixed in advance and never altered. The binding property comes entirely from collision resistance — if the prover could find two different evaluation lists hashing to the same root, they could cheat, but finding a hash collision is exactly what we believe is infeasible.
FRI: how to prove a polynomial is low-degree
Everything now hinges on one test: given a Merkle-committed list of evaluations, convince the verifier they really come from a low-degree polynomial — without sending the whole polynomial. The engine that does this is FRI: the Fast Reed–Solomon Interactive Oracle Proof of Proximity. Its idea is recursion by folding: cut the degree in half, round after round, until what remains is so small the prover can just send it outright.
Split any polynomial into its even-power and odd-power halves, `f(x) = f_even(x²) + x·f_odd(x²)`. Each half has half the degree. The verifier sends a random challenge `β`, and the prover commits to the folded polynomial `f'(y) = f_even(y) + β·f_odd(y)`, defined on a domain half the size. The beautiful part: you can recover the two halves from evaluations at `x` and `−x`, so the verifier can later check the fold was done honestly with cheap arithmetic.
FRI, in two phases
===================
COMMIT phase (log(d) rounds, halving the degree each time)
layer 0: f0 = the polynomial we want to prove is low-degree
repeat until the polynomial is a constant:
verifier (Fiat-Shamir) sends random beta_k
f_{k+1}(y) = f_even(y) + beta_k * f_odd(y) # degree halved
prover Merkle-commits f_{k+1} over the half-size domain
finally: prover sends the tiny final polynomial in the clear
QUERY phase (repeat ~tens of times for soundness)
verifier picks a random point x in the layer-0 domain
for each layer k, prover opens (Merkle paths) the values at x and -x
verifier checks the FOLDING relation links the two layers:
f_{k+1}(x^2) ?= f_even(x^2) + beta_k * f_odd(x^2)
where f_even = (f_k(x)+f_k(-x))/2 , f_odd = (f_k(x)-f_k(-x))/(2x)
ACCEPT only if every layer is consistent AND the final value matchesWhy is this sound? If the prover started from a function that was far from any low-degree polynomial, that distance survives the folding — the folded function is still far from low-degree, round after round. So at least one layer is inconsistent at a large fraction of points, and each random query in the query phase catches the lie with constant probability. Run, say, 30–80 queries (the exact number is tuned to the blow-up factor) and the cheating probability drops below `2⁻¹⁰⁰`. Honesty costs the prover almost nothing; a forged proof is caught with overwhelming probability. That is the whole bargain, paid for entirely in hashes.
Non-interactive, and why a quantum computer can't help
FRI as described is interactive — the verifier keeps sending fresh random `β`s and query points. To put a STARK on a blockchain we need it non-interactive: one self-contained proof, no live verifier. The fix is the same one from the intuition guide — the Fiat–Shamir heuristic. Wherever the verifier would have flipped a coin, the prover instead derives that randomness by hashing the transcript so far. Because the challenges are pinned to everything already committed, the prover can't grind them to their advantage — under the random-oracle model, the hash behaves like an honest, unpredictable coin.
Now the post-quantum claim, stated honestly. A pairing-based SNARK like Groth16 or a KZG-based PLONK rests its soundness on the hardness of the discrete logarithm in an elliptic-curve group. Shor's algorithm solves discrete log and factoring in polynomial time on a large quantum computer — so a cryptographically-relevant quantum machine would break those SNARKs' setups outright, letting an attacker forge proofs. A STARK has no discrete-log assumption to break. Its only assumption is that the hash function is collision-resistant and behaves like a random oracle.
Against hashes, the best a quantum computer offers is Grover's algorithm, a mere quadratic speedup for unstructured search — it finds a preimage in about `2^(n/2)` work instead of `2^n`. The defense is trivial: double the output. A 256-bit hash keeps roughly 128 bits of security even against Grover, the same logic that makes hash-based signatures a flagship post-quantum primitive. So STARKs are plausibly post-quantum: not because anyone proved quantum computers are powerless, but because they were built on the one assumption quantum computers barely dent.
SNARK vs STARK: an honest scorecard
There is no free lunch, and STARKs pay for transparency in bytes. A Groth16 proof is about 200 bytes and verifies with three pairings in constant time — unbeatable on-chain. A STARK proof carries thousands of hash openings: realistically tens to a few hundred kilobytes. Verifier work is polylogarithmic in the computation, which is excellent, but it means tens of thousands of hash operations — cheap on a laptop, but pricey as raw Ethereum gas. Here is the trade laid bare:
zk-SNARK (Groth16 / KZG-PLONK) zk-STARK (FRI)
----------------- ------------------------------ --------------------
Trusted setup YES - per-circuit or universal NO - fully transparent
ceremony; toxic waste risk (public randomness)
Proof size ~200 B (Groth16) ~tens-hundreds of KB
~0.5 KB (PLONK)
Verify cost constant, ~3 pairings (cheap polylog, many hashes
on-chain) (heavier on-chain)
Prover speed slower, heavy FFT + MSM faster, hashing-bound,
scales near-linearly
Crypto assumption elliptic-curve / pairing collision-resistant
discrete-log hash + random oracle
Quantum threat BROKEN by Shor (discrete log) only Grover (quadratic)
=> plausibly post-quantumThe industry's favorite move erases the dilemma: prove with a STARK, then wrap the STARK proof inside a small SNARK. You get the STARK's transparent, fast, scalable prover for the heavy computation, then a final Groth16 proof attests "I verified that STARK correctly," shrinking the on-chain footprint back to ~200 bytes. This is proof recursion in action, and it's exactly how systems like Polygon zkEVM and RISC Zero post a tiny proof to Ethereum while keeping a transparent backbone. The wrapper reintroduces a trusted setup only for the final thin layer.
STARKs in the wild, and the road ahead
STARKs are not a whiteboard idea — they settle real value today. StarkWare's StarkEx has proven hundreds of billions of dollars of trades for dYdX, Sorare, and Immutable; StarkNet is a general-purpose zk-rollup whose contracts are written in Cairo, a language designed so its execution trace is STARK-provable by construction. Polygon Miden, RISC Zero (proving correct execution of a RISC-V program), and Plonky2/Plonky3 (a FRI-based system that fuses PLONK-style arithmetization with STARK commitments) all build on the same hash-only foundation.
Every one of these emits a validity proof: unlike an optimistic rollup that assumes batches are honest and waits a week for a challenge, a STARK rollup proves its batch correct before it settles, so funds can exit as soon as the proof verifies. The frontier now is making the prover ever cheaper — Circle STARKs over the tiny Mersenne-31 field, hardware acceleration, and deep recursion — and pushing toward a full zkEVM that proves real Ethereum execution opcode for opcode.