zk-STARK

What Is a zk-STARK?

A zk-STARK (Zero-Knowledge Scalable Transparent Argument of Knowledge) is a cryptographic proof system that lets one party (the prover) convince another party (the verifier) that a computation was performed correctly, without revealing any of the underlying data. The name encodes its defining properties: "scalable" refers to quasi-linear prover time and polylogarithmic verification time, and "transparent" means all parameters are derived from public randomness with no secret setup phase.

STARKs were introduced in a 2018 paper by Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Ben-Sasson went on to co-found StarkWare Industries, the company behind StarkNet, one of the largest rollup networks. The research emerged from decades of work on probabilistically checkable proofs (PCPs) and interactive oracle proofs (IOPs), aiming to build a practical proof system that avoids the trust assumptions inherent in earlier constructions like Groth16.

The core motivation is straightforward: if a proof system requires a trusted setup, someone must generate secret parameters and then destroy them. If those secrets are ever compromised, an attacker can forge proofs for false statements. STARKs sidestep this entirely by deriving all randomness from hash functions, which are publicly computable and verifiable.

How It Works

The STARK proving pipeline transforms an arbitrary computation into a mathematical object that can be efficiently verified. The process has several stages: arithmetization, polynomial commitment via FRI, and non-interactive proof generation using the Fiat-Shamir heuristic.

Arithmetization and Execution Traces

The first step converts a computation into an algebraic form called an Algebraic Intermediate Representation (AIR). The computation is executed step by step, producing an execution trace: a matrix where each row represents one step and each column tracks a register value across all steps.

Each column of the trace is then interpreted as evaluations of a polynomial over a structured domain (typically roots of unity in a finite field). Constraints on the computation are expressed as polynomial relations over these trace polynomials:

• Transition constraints enforce rules between consecutive rows (for example, "the next Fibonacci number equals the sum of the previous two")
• Boundary constraints enforce specific values at specific positions (for example, "the first value is 1")

When all constraints are satisfied, the constraint polynomials divided by a vanishing polynomial yield a low-degree quotient. If any constraint is violated, the quotient is not low-degree, and the verifier will detect the discrepancy with high probability.

FRI Commitment Scheme

FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity) is the polynomial commitment scheme at the heart of STARKs. It allows the verifier to check that a committed function is close to a polynomial of bounded degree, without reading the entire function. FRI works through successive commit-and-fold rounds:

1. The prover commits to the polynomial evaluations using a Merkle tree
2. The verifier sends a random challenge
3. The prover folds the polynomial using the challenge, halving the degree and domain size
4. Steps 2 and 3 repeat for approximately log2(d) rounds, where d is the polynomial degree
5. The final constant polynomial is checked directly

Because FRI uses only Merkle trees and hash functions for commitment (no elliptic curve pairings), the entire scheme inherits the post-quantum security properties of the underlying hash function. The prover complexity is strictly linear in the domain size, and the verifier complexity is strictly logarithmic.

Putting It Together

The full STARK proof pipeline:

1. Arithmetize: computation → execution trace matrix
2. Interpolate: trace columns → trace polynomials over roots of unity
3. Constrain: define AIR (transition + boundary constraints)
4. Compose: build composition polynomial = constraints / vanishing poly
5. Commit: Merkle-commit all polynomials (FRI)
6. Prove low-degree: FRI commit-and-fold rounds
7. Fiat-Shamir: replace verifier randomness with hash-derived challenges

The Fiat-Shamir transformation converts the interactive protocol into a non-interactive proof by hashing the transcript to generate the verifier's challenges. This means the final STARK proof is a single static object that anyone can verify independently.

STARKs vs. SNARKs

STARKs and SNARKs solve the same fundamental problem (proving computation integrity with zero knowledge) but make different engineering tradeoffs. A December 2025 academic benchmark on consumer hardware illustrates the differences:

The proof size difference is the most visible tradeoff. A Groth16 SNARK proof is a constant 384 bytes regardless of computation size. A STARK proof grows polylogarithmically with computation size, typically landing in the 45-200 KB range. This matters enormously for on-chain verification, where every byte costs gas or block space.

Many production systems address this through STARK-to-SNARK wrapping: proving the bulk of the computation with STARKs (for speed and transparency), then generating a small SNARK proof that the STARK proof is valid (for cheap on-chain verification). This hybrid approach captures the best of both worlds.

Use Cases

Layer 2 Scaling

The most significant application of STARKs today is in rollups. ZK-rollups execute transactions off-chain, then generate a STARK proof that all transitions were valid and post it to the base layer. The base layer verifier checks the proof in polylogarithmic time, regardless of how many transactions the rollup processed.

StarkNet, the largest STARK-based rollup, processes transactions using the Cairo virtual machine (whose name stands for "CPU AIR," reflecting the arithmetization scheme). In November 2025, StarkNet deployed the Stwo prover on mainnet, which uses Circle STARKs over the Mersenne prime field M31 and delivers roughly 100x efficiency improvements over its predecessor.

Bitcoin Scalability

STARK verification on Bitcoin is an active area of research with significant implications for Layer 2 scaling. In July 2024, StarkWare verified the first STARK proof on a Bitcoin test network (Signet) using OP_CAT-enabled covenants. The proof was split across chained transactions that together verified a computational claim.

If OP_CAT were activated on Bitcoin mainnet via soft fork, it would enable covenant-based STARK verification, potentially unlocking fully trustless, non-custodial bridges and ZK-based Layer 2s on Bitcoin. The BitVM/BitVMX approach takes a different path: executing STARK verification off-chain through a fraud-proof model, with successful STARK proof verification already demonstrated on Bitcoin mainnet using RISC Zero's prover wrapped in a Groth16 SNARK.

For a deeper exploration of how post-quantum cryptography affects Bitcoin, including the role of hash-based proof systems, see our research coverage.

Privacy-Preserving Computation

Beyond scaling, STARKs enable computations where the inputs must remain private. A financial institution could prove regulatory compliance (sufficient reserves, valid risk models) without revealing customer data or proprietary trading strategies. Identity systems can prove a user meets age or residency requirements without disclosing personal information.

Verifiable Computation

Any computation that is expensive to run but important to verify is a candidate for STARKs. Machine learning inference, scientific simulations, and database queries can all be proven correct, letting a weak verifier trust results from an untrusted but powerful prover.

Major Implementations

Several production systems use STARKs as their core proving technology:

• StarkNet: a Type-4 ZK-rollup on Ethereum using Cairo and the Stwo prover, live since 2021 with full permissionless operation since 2022
• RISC Zero: a STARK-based zkVM over the RISC-V instruction set, achieving 44-second Ethereum block proving with its R0VM 2 prover
• Polygon zkEVM: uses STARK provers internally for Ethereum-compatible ZK-rollup execution
• SP1 (Succinct): an FRI-based proving system targeting general-purpose zkVM workloads

The Cairo programming language, developed by StarkWare, deserves special mention. Cairo compiles high-level programs into an AIR that the STARK prover can process directly. Its name ("CPU AIR") reflects the tight coupling between the language and the proving architecture.

Risks and Considerations

Proof Size

STARK proofs are roughly 100-500x larger than SNARK proofs. For on-chain verification where block space is scarce and expensive, this is a significant cost. On Ethereum, posting a 100 KB STARK proof costs substantially more in gas than posting a 384-byte SNARK proof. The STARK-to-SNARK wrapping pattern mitigates this but adds complexity and reintroduces the trusted setup requirement for the final SNARK layer.

Implementation Complexity

Building a correct and efficient STARK prover is a major engineering challenge. The arithmetization step requires careful encoding of computations into AIR constraints, and bugs can create soundness vulnerabilities (where invalid proofs pass verification). The FRI parameters (expansion factor, number of queries, grinding bits) must be tuned to balance security level, proof size, and prover performance.

Prover Resource Requirements

While STARK verification is fast, proof generation is computationally intensive. Proving large computations requires significant memory and CPU time. The Stwo prover improved this dramatically (roughly 100x over its predecessor), but generating proofs for complex programs still requires dedicated hardware or distributed proving infrastructure.

Hash Function Dependence

STARKs trade one set of cryptographic assumptions for another. While they avoid elliptic curve assumptions vulnerable to quantum attacks, their security rests entirely on the collision-resistance of hash functions. A practical collision attack against SHA-256 or the chosen hash function would compromise all STARK proofs using it. Current hash functions are considered secure, but the security margin narrows from 2^n to 2^(n/2) under quantum attack via Grover's algorithm.

Maturity and Auditing

STARK-based systems are newer than their SNARK counterparts. While production deployments like StarkNet have processed millions of transactions, the ecosystem of auditing tools, formal verification frameworks, and battle-tested libraries is still maturing. The zero-knowledge proof space is evolving rapidly, with new optimizations and potential vulnerabilities discovered regularly.

This glossary entry is for informational purposes only and does not constitute financial or investment advice. Always do your own research before using any protocol or technology.