zkSTARKs (Zero-Knowledge Scalable Transparent Arguments of Knowledge) are the primary alternative to zkSNARKs, invented by Eli Ben-Sasson and colleagues at Technion and StarkWare Industries and formally introduced in 2018. The critical distinctions from zkSNARKs are encoded in the acronym: Scalable (proving time scales quasi-linearly rather than linearly with computation) and Transparent (no trusted setup — the system is based solely on publicly verifiable randomness from a hash function). zkSTARKs rely only on collision-resistant hash functions (likely quantum-resistant) versus zkSNARKs which require pairing-based cryptography (vulnerable to quantum computers). The tradeoff: zkSTARK proofs are substantially larger (50-500KB) than zkSNARK proofs (200-500 bytes), making on-chain verification more expensive. StarkWare — the commercial entity built around zkSTARKs — has deployed StarkEx (custom application circuits: dYdX v3, Immutable X, Sorare) and StarkNet (general purpose L2 with Cairo smart contract language) in production, achieving the highest transaction throughput of any ZK-based L2.
STARK Properties Explained
Scalable: Proving time is O(n log n) vs. O(n) for most SNARKs — but the practical advantage is massive parallel proving via GPU. Verification is O(log² n) regardless of computation size.
Transparent: No trusted setup — the verifier sends random challenges derived from a public hash function (Fiat-Shamir transform applied to public transcript). No ceremony, no toxic waste risk.
Argument of Knowledge: Same as SNARKs — soundness holds computationally, with knowledge extraction.
Technical Architecture
Algebraic Intermediate Representation (AIR):
Computations are expressed as algebraic state transitions:
- Computation → Execution trace (table of values at each step)
- Trace correctness → Polynomial constraints (AIR)
- Polynomials → FRI commitment (Fast Reed-Solomon Interactive Oracle Proof)
- FRI proof → STARK proof
FRI Protocol:
FRI (Fast Reed-Solomon IOP) is STARK’s core: proves a function is close to a low-degree polynomial via repeated folding. Each fold halves the domain size; the proof is a path through a Merkle tree at each folding level → generates the large proof size (many Merkle paths).
STARK vs. SNARK Comparison
| Property | zkSTARK | zkSNARK (Groth16) | zkSNARK (PLONK) |
|---|---|---|---|
| Trusted setup | None | Circuit-specific | Universal |
| Proof size | 50-500KB | ~192 bytes | ~500 bytes |
| Verify gas (Ethereum) | ~5-10M | ~200K | ~300K |
| Quantum resistant | Yes | No | No |
| Scalability | Excellent | Good | Good |
| Hardware accel | GPU/FPGA | GPU/FPGA | GPU/FPGA |
StarkWare Products
StarkEx: Custom circuit product for specific applications:
- dYdX v3: perpetuals trading (~9,000 TPS capability)
- Immutable X: NFT minting/trading (gas-free for users)
- Sorare: fantasy sports NFT platform
StarkNet: General-purpose L2 with Turing-complete Cairo language:
- Cairo: STARK-native language (not EVM bytecode)
- Recursive STARKs: proofs of proofs — prove that many STARK proofs are valid → exponential scalability theoretically
Related Terms
Sources
- “Scalable, Transparent, and Post-Quantum Secure Computational Integrity” — Ben-Sasson et al. (2018). The original zkSTARK paper — introducing the construction, proving scalability, transparency, and quantum resistance, and benchmarking against SNARK alternatives.
- “Cairo: A Turing-Complete STARK-Friendly CPU Architecture” — Ben-Sasson et al. / StarkWare (2021). Introduction of Cairo — the programming language designed for STARK proving — establishing how arbitrary computation can be expressed in STARK-provable form for the StarkNet L2 platform.
- “Recursive STARKs: Exponential Scalability via Proof Aggregation” — StarkWare (2022). Technical description of recursive STARK proving — where STARK proofs verify other STARK proofs, enabling exponential compression of computation verification and infinite horizontal scalability.
- “StarkEx: Validium and ZK-Rollup Deployment Architecture” — StarkWare (2022). Technical documentation of StarkEx — StarkWare’s application-specific ZK scaling product deployed for dYdX v3, Immutable X, and Sorare — explaining the validium vs. rollup data availability choice.
- “Post-Quantum Cryptography and Blockchain: Which Proof Systems Survive?” — NIST Post-Quantum Cryptography Project / ZKProof Research (2023). Analysis of blockchain cryptographic systems’ quantum resistance — examining which hash-based proof systems (STARKs) survive Shor’s algorithm and which pairing-based systems (SNARKs) require post-quantum migration.