zk-STARKs

Imagine you finish a billion-step computation and a stranger asks: "Did you really run that correctly?" You could hand over all the inputs and let them rerun it — but that takes another billion steps and exposes every secret input. What if you could hand them a short proof instead, something they could check in seconds, that reveals absolutely nothing beyond the single fact: yes, the computation was done correctly?

That is the promise of a zero-knowledge proof. And zk-STARKs — Scalable Transparent ARguments of Knowledge — are a family of such proofs invented by Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev and published in 2018. They have three remarkable properties that set them apart:

1. Scalable — the proof is tiny (logarithmic in the computation size) and verification is fast even when the underlying computation has trillions of steps.
2. Transparent — no trusted setup is required. Earlier systems like zk-SNARKs need a one-time ceremony where participants generate "toxic waste" that must be destroyed; if anyone keeps a copy, they can forge proofs. STARKs skip this entirely, using only public randomness.
3. Post-quantum secure — STARKs rely on hash functions (collision resistance) rather than on discrete logarithms or elliptic curves. The latter are broken by Shor's algorithm; hash functions are not.

The cost? STARK proofs are larger than SNARK proofs — roughly kilobytes versus hundreds of bytes. But as blockchains push toward millions of transactions and quantum computers loom on the horizon, that trade-off is increasingly worth making.

The key insight of STARKs is that any computation trace can be encoded as a low-degree polynomial. The prover commits to this polynomial by evaluating it at many random points; the verifier spot-checks a few of those evaluations and runs a low-degree test (FRI). If the polynomial passes, the verifier is convinced the computation was honest — without seeing the inputs.

<p class="hint">{{hint}}</p>
<div class="controls">
  <button id="btn-honest" type="button">{{btn_honest}}</button>
  <button id="btn-cheat" type="button" class="ghost">{{btn_cheat}}</button>
  <button id="btn-verify" type="button" class="ghost">{{btn_verify}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<canvas id="chart" width="560" height="240"></canvas>
<div id="status" class="status"></div>
<div id="details" class="details"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; background: #fff; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .75rem; line-height: 1.45; }
.controls { display: flex; gap: .45rem; flex-wrap: wrap; margin-bottom: .65rem; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: default; }
canvas { display: block; width: 100%; max-width: 560px; height: auto;
         border: 1px solid #dce3ea; border-radius: 8px; background: #f8fafc; }
.status { font-size: .97rem; font-weight: 600; min-height: 1.5em;
          margin: .55rem 0 .3rem; }
.status.ok  { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #1d3557; }
.details { font-size: .82rem; color: #555; line-height: 1.5; }

// Code not found

Click Honest prover to encode a correct computation as a degree-3 polynomial and sample it at four points. Click Cheating prover to see what happens when someone tampers with one output: the recovered polynomial shifts, and a spot-check at a fresh point catches the lie. The Verify button runs this spot-check — exactly what FRI does in a real STARK.

How hard is it to build — and break — a zk-STARK?

• Security assumption: collision-resistant hash functions. No one has found an efficient algorithm to break SHA-256 or similar; this assumption is believed to hold even against quantum adversaries. By contrast, zk-SNARKs typically rely on the hardness of the discrete logarithm, which Shor's algorithm can solve in polynomial time on a quantum computer.
• Proof size: $O(\log ^{2} n)$, where n is the number of steps in the computation. A SNARK proof is only $O(1)$ — a fixed constant size — but requires a trusted setup. The logarithmic overhead of STARKs is acceptable at the scales where they are deployed.
• Verification time: $O(\log ^{2} n)$ — fast. The verifier does not re-execute the computation; it only checks a handful of polynomial evaluations.
• Prover time: $O(n \log n)$ — significantly more work than just running the computation. This is where most STARK engineering effort goes: FFTs over large finite fields, Merkle trees, and Reed-Solomon encodings.
• The trusted setup problem: zk-SNARKs were introduced around 2012 by Groth, Sahai, and others. Their "common reference string" must be generated in a secure multi-party computation; if any one party is corrupt, all proofs from that system can be forged. STARKs eliminate this entirely — their only "setup" is agreeing on a public hash function.
• Status: zk-STARKs are a solved, deployed technology (not open or conjectured). The security proof reduces STARK soundness to the collision resistance of the underlying hash. The FRI (Fast Reed-Solomon Interactive Oracle Proof) protocol at their core was analyzed rigorously by Ben-Sasson et al. in 2018.

The bottom line: STARKs trade a somewhat larger proof for the elimination of all trusted parties and resistance to quantum attacks — a bargain that gets better as quantum hardware matures.

zk-STARKs started as a theoretical breakthrough and have become production infrastructure in under a decade:

• Blockchain scaling (zkRollups): StarkWare's StarkNet and StarkEx use STARKs to bundle thousands of Ethereum transactions into a single on-chain proof. Dydx processed over $1 trillion in derivatives volume on STARK-backed infrastructure. The proof verifies that all those trades followed the rules — without posting each one to the chain.
• Verifiable AI inference: proving that a specific neural network model produced a specific output, without revealing the model weights or the input. Companies are beginning to use STARKs here because the computation trace of a transformer forward pass can be arithmetized and proven.
• Transparent voting: a zk-STARK can prove that a tally was computed correctly over encrypted ballots without a trusted tallying authority and without revealing individual votes.
• Post-quantum identity: as quantum computers approach, credential systems based on elliptic-curve signatures face replacement. STARK-based schemes (such as those using lattice-based or hash-based signatures inside a STARK) remain secure.
• The broader zero-knowledge ecosystem: STARKs sit alongside zk-SNARKs and other proof systems. Each trades different parameters — proof size, setup assumptions, quantum resistance — and the field is evolving rapidly toward recursive proofs (a STARK that verifies another STARK) for constant-time verification of unlimited computation.

The unifying theme is verifiable trust without a trusted party — one of the most powerful ideas in modern cryptography.

zk-STARKs answer a question that would have seemed impossible a generation ago: how do you convince a stranger that a trillion-step computation was done honestly, in seconds, with no secrets and no trusted intermediary? The answer is a short list of polynomial evaluations and a hash-function-based consistency check.

The deeper lesson is about the geometry of trust. Classical cryptography lets two parties share a secret. Zero-knowledge proofs let one party convince another of a fact without sharing anything else. STARKs do this at scale, transparently, and in a world where quantum computers are becoming real.

The next time you hear that a blockchain processed a million transactions in a single proof, or that an AI company can prove its model gave a particular answer without revealing the model — that is a STARK (or something very like it) at work. The mathematics of polynomials and hash functions is quietly underpinning a new kind of verifiable trust that requires no leap of faith at all.