“Scalable, transparent, and post-quantum secure computational integrity” is the 2018 IACR Cryptology ePrint paper by Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev that introduced STARKs — Scalable Transparent ARguments of Knowledge. This is the cryptographic foundation for StarkWare’s products: StarkEx (a validity-proof-based app-specific engine) and Starknet (a general-purpose ZK-Rollup for Ethereum).

Ben-Sasson co-founded both the Zcash project (which pioneered zk-SNARKs) and StarkWare Industries. STARKs are his team’s answer to a key limitation of SNARKs: the requirement for a trusted setup ceremony.

> PDF hosting: The STARK paper is at eprint.iacr.org/2018/046. StarkWare’s production documentation is at docs.starknet.io.

---

Publication and Context

The STARK paper was published at IACR ePrint in 2018 and presented at CRYPTO 2019. At the time, zk-SNARKs (used by Zcash and later Tornado Cash) were the dominant zero-knowledge proof system, but they required a trusted setup ceremony: a multi-party computation that generates CRS (Common Reference String) parameters. If the ceremony were compromised, an attacker could forge proofs.

STARKs eliminate this by using only a hash function as their cryptographic assumption — no structured mathematical objects (pairings, elliptic curves) that require setup. This makes STARKs:

• Transparent: Public coin; no trusted setup; verifiable by anyone
• Post-quantum secure: Assuming hash function security (SHA-3, Poseidon), STARKs remain secure against quantum computers
• Scalable: Proof verification time is polylogarithmic in the computation size (vs. linear for naive replay)

---

How STARKs Work

The high-level idea:

1. The prover wants to convince the verifier that they honestly computed F(x) = y, where F is a complex computation

1. The prover encodes the computation trace (every intermediate step) as a polynomial over a finite field

1. The prover uses FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity) — a hash-based protocol to prove that the trace polynomial is low-degree (i.e., that it corresponds to a valid computation trace)

1. The verifier checks the FRI proof by querying random points and verifying consistency hashes — no cryptographic pairings needed

FRI (Fast RS IOPP):

FRI is the core of STARK efficiency. It reduces the problem of checking a polynomial evaluation to a sequence of hash-based folding operations. The key properties:

• Prover time: O(N log N) where N is the trace length
• Verifier time: O(log²N) — polylogarithmic
• Proof size: O(log²N) field elements

Compared to SNARKs (O(1) proof size, O(N) prover time), STARKs have larger proofs but faster proving and no trusted setup — a different point in the tradeoff space.

---

The STARK Lifecycle in Production (StarkWare)

StarkWare built a production stack on top of the STARK paper:

Cairo Language: A custom programming language designed to be efficiently provable via STARKs. Cairo compiles to low-level instructions that the STARK prover can efficiently process.

StarkEx: A validity-proof-based scalability engine. Applications (dYdX v3, Immutable X, Sorare) submit transactions off-chain; StarkEx batches them and submits a STARK proof to Ethereum verifying the batch. Production since 2020.

Starknet: A general-purpose ZK-Rollup that supports arbitrary Cairo smart contracts. Users interact with Starknet; STARK proofs are periodically submitted to Ethereum. Full STARK proof verification happens on Ethereum via the solidity Verifier contract.

Starknet Architecture:

Layer	Component
User layer	Starknet contracts written in Cairo
Sequencer	Orders transactions, produces blocks
Prover	Generates STARK validity proof of the batch
L1 contract	Verifies STARK proof and updates L1 state root

---

Proof Sizes and Ethereum Verification Costs

One challenge with STARKs on Ethereum: STARK proofs are larger than SNARK proofs (~100–500KB vs. ~1KB for Groth16). Verifying a STARK on Ethereum costs more gas than verifying a SNARK.

StarkWare addresses this via recursion: proofs of proofs. A recursive STARK can prove that many STARK proofs are valid, aggregating thousands of transactions into one small proof submitted to Ethereum. This is called “proof recursion” or “proof aggregation” and dramatically reduces per-transaction L1 costs.

---

STARK vs. SNARK Comparison

Property	STARKs	SNARKs (Groth16)
Trusted setup	Not required	Required
Post-quantum	Yes (hash-based)	No (pairing-based)
Proof size	O(log²N) — larger	O(1) — very small
Verification cost	Higher	Lower
Prover time	Faster for large N	Slower for large N
Cryptographic assumption	Collision-resistant hashes	Elliptic curve pairings

---

Reality Check

Starknet launched progressively from 2021 and achieved full decentralization milestones in 2023–2024, with the STRK token airdrop in February 2024. Starknet’s throughput has improved significantly, but Cairo’s learning curve (being non-Solidity) remains an adoption barrier. dYdX v3 (one of the largest StarkEx users) migrated to a Cosmos-based v4 chain in 2023 — reducing StarkEx’s TVL. Starknet’s EVM compatibility is limited; Solidity code does not run natively (unlike Optimism/Arbitrum).

---

Legacy

The STARK paper is one of the most important cryptographic papers in blockchain history. STARKs enabled provable scalability without trust assumptions — a breakthrough from SNARKs’ trusted setup requirement. The FRI protocol is reused in many contexts: Polygon’s zkEVM uses STARKs for some components; many other ZK systems borrow ideas from the STARK literature.

---

Related Terms

• Zero-Knowledge Proof
• ZK-Rollup
• zkSync Whitepaper
• Groth16 Whitepaper
• PLONK Whitepaper

---

Research

• Ben-Sasson, E., Bentov, I., Horesh, Y., & Riabzev, M. (2018). Scalable, transparent, and post-quantum secure computational integrity. IACR ePrint 2018/046.

— The primary STARK paper. Section 3 introduces FRI; Section 4 constructs the STARK from FRI.

• Ben-Sasson, E., et al. (2020). DEEP-FRI: Sampling Outside the Box Improves Soundness. ITCS 2020.

— Improves FRI’s soundness guarantees; used in production StarkWare provers.

• Goldwasser, S., Micali, S., & Rackoff, C. (1989). The Knowledge Complexity of Interactive Proof Systems. SIAM Journal on Computing.

— The foundational zero-knowledge paper on which all ZKP systems (SNARKs, STARKs) are built.