zk-STARK: Transparency Without Trusted Setup

To trust a Groth16 SNARK, 140,000 people held a ceremony and swore to destroy their secrets. If even one lied - the whole system is at risk. What if you could build a zero-knowledge proof that requires trusting no one? Where the only assumption is that SHA-256 works as intended? That is exactly what STARK does: instead of elliptic curves and secret ceremonies - a computation table, polynomials, and a hash function. The proof is 1000x larger, but in return you get something no SNARK can offer: complete transparency and resistance to a quantum computer that will one day obliterate all elliptic-curve-based cryptography.

• **StarkNet** - an L2 on Ethereum where Cairo programs compile into a STARK proof aggregating thousands of transactions without a trusted setup. Processes up to 500 TPS at a cost of ~$0.01 per transaction
• **dYdX v4** - the largest decentralized derivatives exchange, using StarkWare STARK proofs for order settlement. Has processed more than $1 trillion in cumulative trading volume
• **Polygon Miden** - a ZK-rollup built entirely on STARK with client-side proving: proofs are generated on the user's device, providing privacy without trusting the sequencer

Предварительные знания

• zk-SNARK: From Theory to Practice

AIR: Computation as an Algebraic Table

In the zk-SNARK lesson we turned a program into **R1CS** - a system of constraints of the form `a * b = c`. STARK uses a different format: **AIR** - Algebraic Intermediate Representation. Instead of a system of multiplications, we record the computation as a **table** (execution trace) and then formulate **polynomial constraints** on the transitions between rows. This gives STARK a key advantage: constraints describe not individual operations, but a **pattern** that repeats at every step of the computation.

An execution trace is a matrix where each row represents the state of the computation at a particular step, and the columns are registers (variables). Proving correctness requires two types of constraints: **transition constraints** (the relationship between adjacent rows) and **boundary constraints** (values in the first/last row).

The key difference between AIR and R1CS: in R1CS each constraint is unique (different coefficients in matrices A, B, C), while in AIR **the same polynomial** describes the constraint for **all rows**. This means the size of the AIR description does not depend on the length of the computation - only on its **width** (number of registers) and the **degree** of the transition. A computation of one million steps is described by the same constraint as one of ten steps.

**AIR vs R1CS - comparing approaches.** R1CS (SNARK): each operation is a separate constraint; description size grows linearly with the number of operations. An ETH transfer requires ~5,000 constraints. AIR (STARK): one transition constraint describes the pattern for all rows; description size is fixed. The same ETH transfer requires 2-3 transition constraints applied to **one million trace rows**. The cost of this compactness: the prover must interpolate the entire trace into polynomials, which requires FFT in O(n log n). But this is transparent to the verifier - they only work with the composition polynomial.

FRI: Polynomial Testing Without Trusted Setup

After AIR, we reduced the correctness of the computation to the question: "is the composition polynomial genuinely a low-degree polynomial?" In SNARK, this check was done by pairing on elliptic curves - but that required a trusted setup. **FRI** (Fast Reed-Solomon Interactive Oracle Proof) solves the same problem using only **hash functions and Merkle trees**. It is a "proximity testing" protocol: it checks that a function, given as a set of values, is **close** to a polynomial of degree at most d.

The intuition behind FRI: if you have a degree-d polynomial given by values at 2d points, you can "fold" it in half - split into even and odd parts - and obtain a degree-d/2 polynomial at d points. Repeating this process log(d) times, you reach a constant. If at some step the "folding" fails, it means the original function was not a polynomial of the required degree.

Why does FRI provide **transparency**? The only "secret" elements are the random challenges α₁, α₂, ... But the verifier generates them **after** receiving the Merkle root, so the prover cannot adapt. To convert from an interactive to a non-interactive protocol, the **Fiat-Shamir transform** is applied: challenges are computed as the hash of the previous commitments. No secret parameters, no ceremony - only a hash function.

**FRI proof size** depends on the number of query points and the folding depth. For a 128-bit security level, ~30 query points are needed, each requiring a Merkle path at every level. Total: proof ≈ 30 × log(d) × (hash size) ≈ **40-200 KB** - 200-1000x larger than Groth16 (128 bytes). But this "price" for size buys full transparency and quantum resistance.

Transparency: Only Hashes, Nothing More

Now we can precisely define what makes STARK **transparent**: the entire system is built on two primitives - a **collision-resistant hash function** (SHA-256, Blake3, Poseidon) and **FRI** for polynomial proximity testing. No elliptic curves, no pairings, no toxic waste. Anyone can verify a proof given only public code and a hash function. This is a fundamental difference from SNARK, where security relies on the algebraic structure of elliptic curve groups.

In cryptography we distinguish three types of setup: **per-circuit** (Groth16 - a new ceremony for each circuit), **universal/updatable** (PLONK, Marlin - one ceremony for all circuits, participants can be added later) and **transparent** (STARK, Bulletproofs - no setup required at all). Transparent is the strongest guarantee: trust assumptions are reduced to the standard cryptographic model (random oracle for hash functions).

**Cairo** is a programming language developed by StarkWare specifically for STARK. A Cairo program compiles into an execution trace compatible with AIR. It is like Solidity for the EVM, but optimized for generating zk-proofs. StarkNet is an L2 solution on Ethereum where all transactions are executed in Cairo VM, and only a STARK proof - compressing thousands of transactions into a single commitment - is sent to L1.

**Proof size is not a death sentence.** 100 KB seems enormous next to Groth16's 128 bytes, but in the context of L2 rollups, a proof is published once for thousands of transactions. For a batch of 10,000 transactions, the proof cost is ~10 bytes per transaction. StarkWare processes hundreds of thousands of transactions per day on dYdX (derivatives) and StarkNet (general-purpose L2), and the proof size is offset by the scale. Moreover, recursive STARKs allow "compressing" several proofs into one, further reducing amortized cost.

Quantum Resistance: Why STARKs Will Survive the Quantum Computer

STARK's quantum resistance is not a marketing claim - it is a direct consequence of its architecture. All of STARK's security relies on the **collision resistance of hash functions**. Shor's algorithm, which breaks RSA, ECC, and pairings on a quantum computer in polynomial time, is **useless** against hash functions - it only works on problems with algebraic structure (factorization, discrete logarithm). Grover's algorithm speeds up collision search, but only **quadratically**: for SHA-256 security drops from 2¹²⁸ to 2⁶⁴ - sufficient to fix by increasing the hash length to 384 or 512 bits.

Realistic timeline for the quantum threat: cryptographically significant quantum computers (capable of running Shor's algorithm for 256-bit curves) are expected between 2030 and 2040. But preparation must start **now**: data encrypted today can be recorded and decrypted later (the "harvest now, decrypt later" attack). NIST standardized post-quantum algorithms in 2024: **ML-KEM** (Kyber) for encryption and **ML-DSA** (Dilithium) for signatures - both based on lattice problems.

Lattice-based ZKP is a promising direction that may combine **compact proofs** (like SNARK) with **quantum resistance** (like STARK). The Module-LWE (Learning With Errors) problem underlying Kyber and Dilithium is considered quantum-resistant and allows building polynomial commitment schemes. But these systems remain in the research stage - for production-ready ZKP in 2025, STARK is the only quantum-resistant option with proven security.

**A practical view of quantum migration.** StarkWare (StarkNet, dYdX) and Polygon Miden already run on STARK - no migration needed. zkSync and Scroll use PLONK + KZG and plan to transition to FRI-based commitments. Zcash is researching Halo 2 (recursive PLONK without trusted setup), but with ECC-based commitments - the quantum vulnerability remains. Full migration of the ZKP ecosystem to post-quantum primitives will take 5-10 years, and STARK-based systems have a strategic advantage in this race: they only need to increase the hash length.

Key Ideas

• **AIR** (Algebraic Intermediate Representation) - computation is recorded as an execution trace (matrix), and transition constraints describe the transition pattern between rows. Unlike R1CS, a single constraint covers all steps - description size does not depend on computation length
• **FRI** (Fast Reed-Solomon IOP) - a proximity testing protocol that checks whether a function is a low-degree polynomial. Works by iteratively "folding" the polynomial in half with Merkle commitments at each level. Fiat-Shamir turns the interactive protocol into a non-interactive proof
• **Transparency** - STARK requires no trusted setup, relying only on collision-resistant hash functions. Proof size is larger (~100 KB vs 128 bytes for Groth16), but for batch verification in rollups the amortized cost is comparable. Cairo is the language for writing STARK-compatible programs (StarkNet)
• **Quantum resistance** - Shor's algorithm breaks ECC-based SNARKs but is useless against hash functions. Remember the 140,000-person ceremony from the start of the lesson? STARK makes it unnecessary - and will also survive the quantum computer that will nullify the security of all ECC-based systems

Related Topics

zk-STARK connects hash-based cryptography with practical blockchain scaling and post-quantum security:

• zk-SNARK: From Theory to Practice — SNARK uses R1CS + QAP + pairings, STARK replaces them with AIR + FRI + hashes. Understanding both approaches allows making an informed trade-off between proof size and trust assumptions
• PLONK: Universal SNARK — PLONK is a hybrid: universal setup (one ceremony for all circuits) with the option of replacing KZG with FRI to achieve transparency without losing universality
• zkEVM: EVM-Equivalent Proofs — zkEVM uses ZKP (STARK or SNARK) to prove the correctness of EVM transaction execution. The choice of proof system determines the trade-offs of an L2 solution
• ZK-Rollups: Scaling Through Proofs — ZK-Rollups are the primary application of STARK: thousands of transactions are compressed into one proof, and transparency eliminates the need to trust the rollup operator

Вопросы для размышления

• A STARK proof is 1000x larger than a SNARK, but the STARK prover runs faster (no costly EC operations). For an L2 rollup processing 10,000 TPS, what matters more: prover speed (finality latency) or proof size (on-chain publication cost)?
• If a quantum computer arrives in 2035, and migrating a ZKP system from ECC to hash-based primitives takes 3 years, when should the transition begin? Consider the "harvest now, decrypt later" attack for data published on-chain.
• Cairo (StarkWare) is a domain-specific language for STARK. An alternative approach - zkEVM - proves execution of ordinary EVM code. What are the advantages and limitations of each approach from the perspective of developers and users?

Связанные уроки

• crypto-44-zk-snarks