Note

ZK Proving Systems

Categorization and mental model of various ZK concepts.

By Roman Akhtariev•

Layer 1: Overarching Categories

  • SNARK (Succinct Non-interactive Argument of Knowledge) — A class of proof systems where proofs are small and fast to verify. Not a specific system. Groth16, PLONK, Halo2 are all SNARKs. The "succinct" part means proof size is sublinear (usually constant or logarithmic) in the computation size.

  • STARK (Scalable Transparent Argument of Knowledge) — Another class of proof systems. "Transparent" means no trusted setup. "Scalable" means prover time is quasi-linear. Uses hash-based commitments (no elliptic curves), so proofs are larger but post-quantum secure. FRI is the core verification technique.

These two categories aren't mutually exclusive in every property, but they represent different design philosophies: SNARKs optimize for proof compactness, STARKs optimize for transparency and prover scalability.

Layer 2: Arithmetization (How You Express Computation as Math)

Before you can prove anything, you need to turn a computation into polynomial equations. This is arithmetization — the most important conceptual layer to understand.

  • R1CS (Rank-1 Constraint System) — The older, simpler arithmetization. Every constraint has the form (a · witness) × (b · witness) = (c · witness). Each constraint captures exactly one multiplication. This means even simple operations like x⁵ require multiple constraints (intermediate variables for each multiply). R1CS is used by Groth16 and the Circom ecosystem.

  • PLONKish — The newer, more flexible arithmetization used by PLONK, Halo2, UltraPlonk, and UltraHonk. Instead of "one multiplication per constraint," you have a table of cells organized in columns (called "advice," "fixed," "selector" columns). You define custom gates — arbitrary polynomial relations across cells — and lookup tables for efficient range checks, bitwise ops, etc. This is dramatically more expressive: you can encode x⁵ in a single custom gate, or do a SHA-256 round with a lookup instead of thousands of R1CS constraints.

This is the single biggest architectural divide. When someone says a system is "PLONKish," they mean it uses this table-based arithmetization.

Layer 3: Proving Systems (The Cryptographic Backend)

These take an arithmetized circuit and produce/verify proofs.

  • Groth16 — The gold standard preprocessing SNARK. Uses R1CS. Requires a circuit-specific trusted setup (new ceremony per circuit). Produces the smallest proofs in practice (~128 bytes, 3 pairings to verify). Verification is constant time. The tradeoff is the per-circuit setup and R1CS inflexibility.

  • PLONK — A universal SNARK. Uses PLONKish arithmetization. Has a universal SRS (one trusted setup works for any circuit up to a size bound). Verification is fast but not quite Groth16-level (logarithmic polynomial commitment checks). The key innovation was the permutation argument for wiring constraints between gates.

Permutation argument. In PLONKish arithmetization, each gate is a row in a table with its own local constraint (e.g., a * b = c). But the output of gate 3 might feed into the input of gate 7 — you need a way to say "these two cells must hold the same value." These are copy constraints (or wiring constraints).

PLONK handles this by defining a permutation σ over all cells: cells that must share a value are placed in the same cycle of the permutation. The prover then constructs a grand product accumulator polynomial Z(X) that telescopes to 1 if and only if the witness values respect the permutation. Concretely, Z uses random challenges β, γ and checks that f(ωⁱ) + β·ωⁱ + γ and f(ωⁱ) + β·σ(ωⁱ) + γ produce a balanced product across all rows. If any wire is mismatched, the product doesn't close and the verifier catches it.

This cleanly separates gate constraints (local polynomial relations per row) from wiring constraints (the global permutation), which is what makes PLONKish so extensible — you can swap out custom gates without rethinking wiring.

  • UltraPlonk — Aztec's extension of PLONK that adds custom gates and lookup tables (specifically Plookup). This is where the PLONKish arithmetization really became powerful. Still uses KZG polynomial commitments (so still needs a trusted setup, but universal).

  • UltraHonk — Aztec's newer proving backend, evolving beyond UltraPlonk. Adds features like Goblin Plonk (delegating expensive operations like elliptic curve ops to specialized sub-proofs) and is designed for recursive proof composition. It's part of Aztec's Barretenberg library.

  • Halo2 — Developed by Zcash/ECC. Uses PLONKish arithmetization but with IPA (Inner Product Argument) polynomial commitments instead of KZG. This means no trusted setup. Verification is slower than KZG-based systems (logarithmic group operations for IPA opening), but the "Halo" technique enables recursive proof composition by deferring expensive checks. Halo2 can also be configured with KZG commitments if you're willing to accept a trusted setup for faster verification (PSE's fork does this).

Layer 4: Frontends / Frameworks (How You Write Circuits)

  • Circom — A domain-specific language (DSL) for writing circuits. Compiles to R1CS. You write .circom files, compile to a constraint system, then use a separate backend (usually Groth16 via snarkjs, or PLONK) to generate proofs. Circom is a frontend only — it doesn't do any proving itself.

  • Arkworks — A Rust library ecosystem for building ZK applications. It provides building blocks: finite field arithmetic, elliptic curves, R1CS constraint generation, and implementations of multiple proving systems (Groth16, Marlin, etc.). It's a toolkit, not a single system. You'd use Arkworks if you want low-level control and are working with R1CS-based systems in Rust.

  • Halo2 (as framework) — Halo2 is confusingly both a proving system and a circuit development framework. The Halo2 API is how you define PLONKish circuits in Rust — you configure columns, define custom gates, assign witness values into a table. Then the Halo2 backend proves it.

Layer 5: Verification Speed Categories

Now your original distinction maps cleanly:

  • Preprocessing-based fast verification — Groth16, PLONK, UltraPlonk, UltraHonk. A setup phase produces compact verifying keys. Verification is constant (Groth16) or logarithmic (PLONK-family). The verifier key "bakes in" the circuit structure.

  • Structure-based fast verification — STARKs, and sumcheck-based systems (Spartan, Lasso/Jolt). No preprocessing. Instead, algebraic structure of the computation (low-degree polynomials over structured domains, multilinear extensions) lets the verifier do sublinear work. FRI and sumcheck are the core techniques.

Halo2 with IPA sits in between — PLONKish preprocessing gives it structure, but IPA avoids trusted setup at the cost of slower verification than KZG-based PLONK.