A zk-STARK (zero-knowledge scalable transparent argument of knowledge) is a kind of cryptographic proof that lets one party, the prover, convince another, the verifier, that a computation was carried out correctly, without the verifier repeating the computation and, if required, without revealing the private inputs. The construction was introduced in a 2018 paper by Eli Ben-Sasson, Iddo Bentov, Yinon Horesh and Michael Riabzev, and is a member of the wider family of zero-knowledge proofs.
STARKs are best known as an alternative to the zk-SNARK, the other main family of succinct proofs. They need no trusted setup ceremony, they rely only on cryptographic hash functions rather than elliptic-curve assumptions, and they scale efficiently to very large computations. Their main cost is larger proofs. On Ethereum they are used chiefly to build validity rollups that bundle many transactions into one proof.
What the name means
Each part of the acronym describes a property:
- Zero-knowledge. The proof can be made to reveal nothing beyond the truth of the statement. Many blockchain deployments use STARKs for compression rather than privacy, so the "zk" is often not exercised.
- Scalable. The prover's work grows only slightly faster than the size of the computation, roughly for a computation of size , while verification grows only with a power of . Checking a proof is therefore exponentially cheaper than redoing the work.
- Transparent. All randomness used by the system is public. There is no secret setup data that, if kept by someone, could be used to forge proofs.
- Argument of knowledge. Soundness holds against provers with realistic computing power, and the prover must actually know a valid execution, not merely claim one exists.
How a STARK proof works
The prover first runs the program and records its execution trace, a table showing the state of every register at every step. The rules of the program are then written as polynomial constraints over this table, a step known as arithmetisation. If the trace is valid, certain polynomials built from it have low degree; if any step is wrong, they do not.
The prover commits to these polynomials using Merkle trees of hashed values, and the verifier checks low degree through a protocol called FRI (Fast Reed–Solomon Interactive Oracle Proof of Proximity), which samples a small number of random positions. To make the proof non-interactive, the verifier's random challenges are derived from hashes of the prover's commitments, a standard technique known as the Fiat–Shamir heuristic. The final proof is a bundle of Merkle paths and values that anyone can check.
Comparison with zk-SNARKs
| Property | zk-STARK | Typical pairing-based zk-SNARK |
|---|---|---|
| Trusted setup | None | Usually required |
| Security assumption | Collision-resistant hash functions | Elliptic-curve and pairing assumptions |
| Quantum resistance | Believed to resist known quantum attacks | Vulnerable to a large quantum computer |
| Proof size | Tens to hundreds of kilobytes | A few hundred bytes |
| Prover speed on large computations | Fast | Often slower |
Because STARK proofs are larger, they cost more gas to verify on Ethereum than small SNARKs. A common compromise is recursion: many STARK proofs are aggregated and then wrapped in a single SNARK for cheap on-chain verification. The hash-based design is attractive in the context of post-quantum cryptography, since quantum computers would break the elliptic-curve assumptions behind most SNARKs but are not known to break well-chosen hash functions.
Uses in blockchains
StarkWare, a company co-founded by Ben-Sasson in 2018, built the first large deployments. Its StarkEx engine powered exchanges and NFT platforms, including earlier versions of dYdX and the Immutable network, and Starknet is a general-purpose layer 2 network whose programs are written in a language called Cairo. Other projects, including STARK-based virtual machines, use the technique to prove arbitrary programs.
In a validity rollup, transactions are executed off-chain, and a STARK proves that the resulting state change is correct. Ethereum verifies the proof instead of every transaction, which raises scalability and lowers fees while keeping security tied to the main chain. Unlike an optimistic rollup, there is no challenge period, so withdrawals can be final once the proof is accepted.
Limitations
STARKs remain technically demanding. Writing efficient constraints for complex programs is specialised work, proof generation needs substantial computing power, and errors in circuit design or verifier code can undermine security even if the underlying mathematics is sound. Larger proofs also mean higher data costs on chains where space is scarce.
Ref 1070001306