Abstract

Polynomial commitment schemes (PCS) are the core primitive that allows a prover to commit to a polynomial, then later convince a verifier that a specific evaluation is correct without revealing the full polynomial. KZG commitments, introduced by Kate, Zaverucha, and Goldberg in 2010, have dominated ZK proof systems for years because of their constant-size proofs and fast verification. However, KZG requires a structured reference string generated from a trusted setup, and the commitment size is linear in the polynomial degree. A new generation of alternatives - IPA-based schemes, FRI, and Brakedown - remove or relax these requirements at the cost of different tradeoffs, and selecting among them is now one of the central protocol-design decisions in the ZK rollup space.

KZG and Its Limitations

A KZG commitment to a polynomial f(x) of degree d requires committing over a group with a structured reference string that encodes powers of a secret tau: [tau^0]G, [tau^1]G, …, [tau^d]G. This string must be generated in a multi-party computation (MPC) ceremony where at least one participant is honest - Ethereum’s KZG ceremony, completed in 2023 with over 140,000 contributors, is the largest such ceremony to date. The commitment is a single group element and the opening proof is also a single group element, making verification extremely cheap. The limitation is that the degree bound is fixed at setup time, and the trusted setup cannot be reused across different degree bounds or different elliptic curves without a new ceremony.

IPA and Bulletproofs-Style Commitments

Inner Product Argument (IPA) schemes, as used in Halo2 and the Plonky2-based prover from Polygon, replace the trusted setup with a random group generator, eliminating the ceremony requirement entirely. The commitment is still a single group element (a Pedersen vector commitment), but the opening proof is logarithmic in the polynomial degree rather than constant - O(log d) group elements instead of O(1). For polynomials of degree 2^20 (one million), this means a few hundred kilobytes of proof rather than a few dozen bytes for KZG. The verification time is correspondingly higher, though it remains practical for on-chain use when batched across many proofs with aggregation techniques.

FRI and Transparent Setups for STARKs

Fast Reed-Solomon IOP of Proximity (FRI) is a hash-based polynomial commitment scheme used in STARK proof systems from StarkWare and Polygon Miden. Because it relies only on hash functions and no elliptic curve groups, it requires no trusted setup and is conjectured to be quantum-resistant. The proof size is polylogarithmic in the polynomial degree and the concrete sizes are significantly larger than KZG - typically 40-200 KB for a single proof - but recursive composition and proof aggregation (e.g., wrapping a STARK in a SNARK for on-chain verification) can amortize this overhead across many transactions. The winterfell Rust library from StarkWare provides a production implementation of FRI-based proof generation.

Brakedown and Linear-Time Commitments

Brakedown, from Golovnev et al., achieves linear-time prover complexity by using a linear error-correcting code rather than FFT-based polynomial encoding. This makes it attractive for very large circuits where the prover’s time is the bottleneck, but the proof sizes are larger than both KZG and FRI for typical constraint system sizes. The Spartan proof system from Microsoft Research builds on similar ideas using sparse polynomial commitments and does not require a trusted setup. As of late 2025, Brakedown-based schemes remain mostly in the research-to-production pipeline rather than deployed in high-throughput rollups, but several teams are evaluating them for prover-side performance improvements where bandwidth costs are secondary.

Choosing a Scheme

The decision tree for selecting a PCS in a new ZK system roughly follows: if on-chain verifier cost is paramount and a trusted setup is acceptable, KZG with Groth16 or PLONK is still the most gas-efficient path. If quantum resistance or no trusted setup is required and proof size can be amortized, FRI-based STARKs are the mature choice. If prover time at large circuit sizes is the bottleneck, Brakedown and Spartan-style schemes are worth evaluating. IPA sits between KZG and FRI - no trusted setup, moderate proof sizes - and is the default in the Halo2 ecosystem used by the Ethereum Privacy and Scaling Explorations (PSE) group.