Crypto Gloss

Zero-Knowledge Proofs Advanced

Zero-knowledge proofs are the mathematical primitive that enables ZK rollups, zkEVMs, and privacy applications to prove computational correctness without revealing inputs. But “ZK proof” covers a diverse family of proof systems with dramatically different tradeoffs — a Groth16 proof is 192 bytes and verifies in milliseconds but requires a per-circuit trusted setup; a STARK proof is several hundred kilobytes and slower to verify but requires no trusted setup and is post-quantum secure. The choice of proof system is one of the most consequential engineering decisions for any ZK application. This entry covers the full production-deployed proof system landscape for practitioners who need to understand what “we use STARKs” or “our proving system is Boojum” actually means technically.

Note: For a general introduction to ZK proofs, see the [zk-proof] entry. This entry covers advanced technical distinctions.

The Fundamental ZK Proof Structure

Any ZK proof system proves the following statement:

> “I know a secret witness w such that when I apply program f to public input x and w, I get output y.”

The prover (who knows w) generates a proof. The verifier (who doesn’t know w) checks the proof against (f, x, y) without learning w.

Three universal properties:

  • Completeness: If the statement is true, an honest prover can always generate an accepted proof
  • Soundness: If the statement is false, no cheating prover can generate an accepted proof (with overwhelming probability)
  • Zero-knowledge: The proof reveals nothing beyond the truth of the statement

For blockchain rollups, the “program” f is a batch of transactions, the “public input” x is the pre-state root, and the “output” y is the post-state root. The “witness” w is all the transaction data and execution trace.

Proof System Categories

The following sections cover this in detail.

SNARKs — Succinct Non-interactive Arguments of Knowledge

Key properties:

  • Very small proofs (100–300 bytes typically)
  • Fast verification (milliseconds)
  • Typically require trusted setup (structured reference string)
  • Efficient for general-purpose circuits

Trusted setup: The most controversial aspect of many SNARK constructions. To set up the proof system, a “toxic waste” secret must be generated and then destroyed. If it isn’t destroyed, an adversary who knows it can forge fake proofs (prove false statements).

Multi-party computation (MPC) ceremonies address this: hundreds of participants each contribute randomness; the toxic waste exists only if EVERY participant was corrupt. Groth16 ceremony examples: Zcash’s “Powers of Tau” ceremony had 90+ participants; Hermez (now Polygon zkEVM) ceremony had 600+ participants.

Groth16

The most commonly deployed SNARK for fixed smart contracts (pre-2022):

  • Proof size: 192 bytes — smallest of major proof systems
  • Verification: O(1) — extremely fast on-chain
  • Constraint: Requires a per-circuit trusted setup — each new circuit (each smart contract) needs its own ceremony
  • Prover time: Moderate; scales with circuit complexity
  • Used by: Zcash (original shielded transactions), Tornado Cash (mixing), Hermez V1, many Circom-compiled circuits

The problem with Groth16 for zkEVMs: Every time you change the EVM circuit (upgrade), you need a new trusted setup ceremony. This makes protocol upgrades difficult. Ethereum zkEVMs that need to be upgraded frequently prefer proving systems without per-circuit setup requirements.

PLONK (and Variants)

PLONK (Permutations over Lagrange-bases for Oecumenical Non-interactive arguments of Knowledge) was published in 2019 and became the dominant SNARKs construction post-2020:

Key innovation: Universal and updatable trusted setup — one ceremony works for all circuits of up to a certain size (the “universal SRS”). No per-circuit ceremonies needed.

PLONK variants:

  • TurboPlonk: Adds custom gates for efficiency (Aztec Network)
  • UltraPlonk: Further custom gate optimizations (Aztec)
  • PlonKish arithmetization: General term for PLONK-style circuit encoding
  • PLONK + KZG commitments: The standard combination (used by Polygon zkEVM, Aztec)
  • PLONK + FRI: Replace KZG polynomial commitments with FRI → no trusted setup → get STARKish properties (used by Boojum/zkSync)

Production deployments: Polygon zkEVM, Aztec Network, Scroll, Taiko (all use PLONK-based proving)

STARKs — Scalable Transparent Arguments of Knowledge

Eli Ben-Sasson’s construction (StarkWare) with fundamentally different properties:

Key properties:

  • No trusted setup (transparent) — all setup parameters are public
  • Post-quantum secure — security relies only on hash functions (SHA-256, Keccak), not elliptic curve discrete logarithm
  • Large proofs: Hundreds of kilobytes to low megabytes
  • Fast proving relative to proof size; parallelizable
  • Slower on-chain verification (larger L1 gas cost)

FRI (Fast Reed-Solomon IOP of Proximity): The polynomial commitment scheme at the heart of STARKs. Unlike KZG commitments (used in SNARKs), FRI doesn’t require elliptic curve cryptography → post-quantum security.

Production deployments: StarkWare’s StarkEx (dYdX V3, Immutable, Sorare) and Starknet both use STARKs. Polygon’s Miden (in development) uses STARKs.

The STARK tradeoff: More expensive to verify on-chain ($400K+ gas for full STARK vs. $200K for Groth16) but no trusted setup ceremony risk and better quantum resistance. For very high-throughput applications or applications requiring maximum decentralization of the prover, acceptable.

Plonky2 and Plonky3

Plonky2 (Polygon/0xPolygon Labs, 2022): Combines PLONK arithmetization with FRI polynomial commitments. Result: PLONK-like flexibility (custom gates, universal setup) with STARK-like proof generation speed. No trusted setup. Proof size: ~45KB.

Plonky3 (2023): Next generation; modular design allowing different hash functions and fields. Used as a component in Polygon zkEVM’s Type 1 prover and other production systems.

Why these matter: They represent the convergence of SNARK and STARK properties — getting both the efficiency of structured polynomial commitments and the transparency of hash-based systems.

Boojum: zkSync’s Proving System

zkSync’s Boojum (deployed mid-2023) is ZKsync Era’s production proving system:

  • Based on PLONK + FRI (similar to Plonky2 design approach)
  • No trusted setup (relies on hash functions)
  • GPU-accelerated proving (NVIDIA A100 GPU cluster)
  • Replaced Groth16 in production → enabled protocol upgrades without new ceremony
  • Open-source (MIT license)

Recursive Proofs

The scalability breakthrough: A recursive proof is a proof that verifies another proof. By proving “proof P is valid” inside a ZK circuit, you can compose proofs into trees:

  • Layer 1 proofs: Prove individual transactions
  • Layer 2 proofs: Prove that the Layer 1 proofs are valid
  • Final proof: One compact proof that all transactions are valid

Why this matters for scalability:

  • Proving a batch of 1,000 transactions takes N time
  • With recursion: Prove transactions in parallel, then aggregate proofs recursively → prover time scales as log(N) instead of N
  • Enables real-time proving for high-throughput applications

Production recursion:

  • Polygon zkEVM: Recursion to aggregate multiple execution proofs into one L1 verification
  • Starknet: Cairo VM proofs can be recursive
  • Mina Protocol: The extreme case — the entire blockchain state is replaced by a single recursive proof of ~10KB that proves the entire history

Folding Schemes: Nova and HyperNova

The next-generation alternative to recursion:

Traditional recursive proofs: Each recursion step requires proving inside a ZK circuit → expensive

Folding schemes (Nova, 2021, by Kothapalli, Setty & Tziallas): Accumulator-based approach that “folds” multiple instances of a computation together without paying the full proof cost at each step:

  • Nova: Takes two identical computation instances and “folds” them into one
  • Verifier cost per fold: ~2 group operations (extremely cheap vs. recursive SNARK)
  • Only the final accumulated instance needs to be proven with a full SNARK → amortize proof cost over many computation steps

HyperNova (2023): Extension of Nova to non-uniform computations (different circuits per step). Required for real-world applications like Ethereum’s EVM where each opcode is a different circuit.

Jolt (2024): Alternative folding-based zkVM design from a16z crypto; claims 5× faster proving than comparable zkVMs.

Applications: Long-running computations (running an entire Ethereum virtual machine, proving a whole day’s worth of transactions); iterative algorithms where the same computation repeats.

zkVMs: Proving General Computation

A zkVM is a zero-knowledge virtual machine — a proof system that can prove any computation expressed as a program in a target instruction set architecture (ISA):

RISC Zero

  • Proves any computation that compiles to RISC-V assembly
  • Rust is the primary developer language → compile Rust code → RISC Zero proves its execution
  • Produces a “receipt” (ZK proof) that a specific Rust program ran with specific inputs and outputs
  • Production use: Bonsai coprocessor (off-chain computation with on-chain proof verification)
  • Performance (2024): Proving ~2M RISC-V cycles/minute on A40 GPU

Succinct SP1

  • Also RISC-V based
  • Developed by Succinct Labs (former StarkWare researchers)
  • Prover written in Rust with PLONK-based proving
  • Competitive with RISC Zero in proving speed
  • More developer-friendly toolchain per industry feedback

Jolt (a16z)

  • Alternative RISC-V zkVM based on folding + Sumcheck protocol (no polynomial commitments)
  • Claims substantially faster proving times than transcript-based approaches
  • Research paper: “Jolt: SNARKs for Virtual Machines via Lookups”

Why zkVMs Matter for Ethereum

zkEVMs (ZK proofs of Ethereum’s specific VM) are specialized and expensive to build/maintain. zkVMs provide a more general path: compile any program (including an Ethereum EVM implementation) to the target ISA → prove it. This approach (Type 1 zkEVM using RISC Zero or SP1) may ultimately be more maintainable than hand-optimized zkEVM circuits.

Trusted Setup Ceremonies in Practice

For SNARK-based systems requiring trusted setup, understanding the ceremony mechanics matters:

Powers of Tau: Universal phase 1 ceremony (typically based on KZG polynomial commitments up to a certain degree). Once performed and verified, usable by any circuit. Ethereum’s KZG commitment ceremony (for EIP-4844 blob transactions) involved over 140,000 participants — making it the largest cryptographic ceremony in history.

Circuit-specific phase 2: For Groth16, an additional per-circuit ceremony is required. For PLONK universal CRS, phase 2 is not needed (circuit-specific).

Verification: Ceremony outputs are deterministically verifiable — anyone can check that the output was computed by the stated MPC protocol given the attested contributions.

Related Terms

Sources

Ben-Sasson, E., Bentov, I., Horesh, Y., & Riabzev, M. (2018). Scalable, Transparent, and Post-Quantum Secure Computational Integrity. IACR ePrint Archive 2018/046.

Gabizon, A., Williamson, Z.J., & Ciobotaru, O. (2019). PLONK: Permutations over Lagrange-bases for Oecumenical Non-interactive arguments of Knowledge. IACR ePrint Archive 2019/953.

Groth, J. (2016). On the Size of Pairing-Based Non-Interactive Arguments. IACR ePrint Archive 2016/260.

Kothapalli, A., Setty, S., & Tziallas, I. (2022). Nova: Recursive Zero-Knowledge Arguments from Folding Schemes. IACR ePrint Archive 2021/370.

Boneh, D., Drake, J., Fisch, B., & Gabizon, A. (2019). Halo Infinite: Proof-Carrying Data from Additive Polynomial Commitments. IACR ePrint Archive 2020/1536.