zk-STARK

A zk-STARK is a proof scheme built entirely from cryptographic hash functions rather than elliptic-curve pairings, which is what gives it its two defining properties: transparency and post-quantum resistance. The prover converts a computation into a polynomial representation, then uses a technique called FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity) to show, without revealing the underlying data, that the polynomial was constructed correctly. Anyone can verify the result using only public randomness, so there is no secret setup phase that a compromised party could exploit.

The concept was introduced in 2018 by Eli Ben-Sasson and collaborators, who went on to co-found StarkWare, the company behind Cairo, a programming language purpose-built for writing STARK-provable programs. StarkEx and StarkNet apply zk-STARKs to Ethereum scaling: batches of transactions are executed off-chain, then a single STARK proof attesting to their correctness is posted on-chain, cutting gas costs while inheriting Ethereum's security. This makes zk-STARKs a core building block of modern Zero-Knowledge Rollups.

Because verification time and proof size grow only quasilinearly with computation complexity, zk-STARKs handle large, repetitive workloads efficiently. The trade-off against zk-SNARKs is proof size: STARK proofs typically run tens to hundreds of kilobytes, versus a few hundred bytes for SNARKs, meaning higher on-chain storage and gas costs. Ongoing research into recursive proof composition and more compact hash-based commitments is steadily narrowing that gap.