Polynomial Commitments — The Big Idea

The problem that polynomial commitments solve

A ZK proof needs to convince a verifier that a prover knows some secret values satisfying a set of constraints, without revealing those values. But the prover and verifier do not talk in real time for every constraint check. The prover needs to commit to the values upfront and then prove properties about them later.

The tool that makes this work is a polynomial commitment scheme. It lets the prover compress an entire set of values into a single short commitment, and then prove that any specific value in that set is correct, without revealing the rest.

Polynomials as containers for data

A polynomial is a mathematical expression built from powers of a variable. A degree-3 polynomial over a field looks like this:

`` f(x) = a₀ + a₁x + a₂x² + a₃x³ ``

The coefficients a₀, a₁, a₂, a₃ are field elements. They encode the data you want to commit to.

This is the key insight: you can encode an entire vector of values into the coefficients of a polynomial. If you have 1000 constraint values, you can represent all of them as a single degree-999 polynomial. That polynomial then becomes the object you commit to.

What a commitment scheme requires

A commitment scheme must satisfy two properties:

Hiding means the commitment reveals nothing about the underlying data. Looking at the commitment, you learn nothing about the polynomial's coefficients.

Binding means once you commit, you cannot produce a different polynomial that opens to the same commitment. You are locked in. You cannot cheat by claiming the polynomial evaluates to a different value after the fact.

A polynomial commitment scheme extends this with one more capability: the prover can prove that the polynomial evaluates to a specific value at a specific point, without revealing the polynomial itself.

Concretely: the prover commits to f(x) and later proves that f(7) = 42, without revealing any coefficient of f.

The KZG commitment scheme

The most widely used polynomial commitment scheme in production ZK systems is KZG, named after Kate, Zaverucha, and Goldberg who introduced it.

KZG works over elliptic curves using a bilinear pairing. Here is the structure at a high level.

Setup — a trusted setup ceremony generates a structured reference string containing elliptic curve points of the form:

`` [g, g^τ, g^τ², g^τ³, ..., g^τᵈ] ``

Where g is a generator of the elliptic curve group, τ is a secret value (the trapdoor) that is discarded after the ceremony, and d is the maximum degree of polynomial the scheme supports. Nobody knows τ after setup. If they did, they could forge proofs.

Commit — given a polynomial f(x) = Σ cᵢxⁱ, the commitment is a single elliptic curve point:

`` com_f = g^f(τ) = Π (g^τⁱ)^cᵢ ``

The prover computes this using the structured reference string without knowing τ directly. The result is a single group element, regardless of the degree of f.

Open — to prove that f(a) = y for some point a, the prover computes a quotient polynomial:

`` q(x) = (f(x) - y) / (x - a) ``

If f(a) = y, then (x - a) divides (f(x) - y) exactly, and q(x) is a valid polynomial. The prover computes a commitment to q(x) and sends it as the proof π.

Verify — the verifier checks:

`` e(com_f / g^y, g) == e(π, g^τ / g^a) ``

Where e is a bilinear pairing. This check confirms that the quotient relationship holds at τ, which proves f(a) = y without the verifier learning any other information about f.

💡

The proof for any evaluation is always a single elliptic curve point, regardless of the degree of the polynomial. This is what makes KZG succinct. Proof size is O(1). Verification time is O(1). These properties are what make SNARKs practical for blockchain applications.

The trusted setup requirement

KZG requires a trusted setup to generate the structured reference string. If the secret τ is ever recovered, a malicious prover can create false proofs. This is the "toxic waste" problem.

In practice this is addressed through multi-party computation ceremonies where many participants each contribute randomness. The structured reference string is secure as long as at least one participant was honest and destroyed their contribution. Ethereum's KZG ceremony in 2023 had over 140,000 participants.

Transparent alternatives

Some proof systems avoid trusted setups entirely by using different commitment schemes.

FRI (Fast Reed-Solomon Interactive Oracle Proof) is the commitment scheme underlying STARKs. Instead of elliptic curves, it uses hash functions and Reed-Solomon codes. No trusted setup is required. The tradeoff is larger proof sizes: while KZG proofs are a constant few hundred bytes, FRI-based proofs can be tens to hundreds of kilobytes.

IPA (Inner Product Argument), used in schemes like Halo2 and Bulletproofs, is also transparent. It uses no trusted setup and relies only on the discrete logarithm assumption. Proof size and verification time scale logarithmically with circuit size rather than being constant.

| Scheme | Trusted Setup | Proof Size | Verification | |--------|--------------|------------|--------------| | KZG | Yes | O(1) | O(1) | | FRI | No | O(log² n) | O(log² n) | | IPA | No | O(log n) | O(n) |

How this connects to ZK circuits

When you write a Circom circuit and compile it to R1CS, the proving system needs to convince a verifier that all constraints are satisfied. The prover encodes the witness values as a polynomial, commits to it using a polynomial commitment scheme, and then uses the evaluation proof mechanism to prove that specific witness values satisfy the constraint equations.

In Groth16, the commitment scheme underlying the proof is pairing-based and closely related to KZG. In PLONK and its variants, KZG commitments are used explicitly to commit to the trace polynomials that encode the computation. In STARKs, FRI commitments play the equivalent role.

This is why the choice of polynomial commitment scheme determines so much about a proof system: proof size, verification cost, whether a trusted setup is required, and whether the scheme is post-quantum secure.

💡

FRI-based systems using hash functions are considered post-quantum secure because their hardness does not depend on problems like discrete logarithm that quantum computers can solve efficiently. Pairing-based systems like KZG are not post-quantum secure under current analysis. This distinction will matter more as quantum hardware matures.

What you need to remember

A polynomial commitment scheme lets a prover commit to a polynomial and later prove evaluations of it without revealing the polynomial. KZG is the most efficient scheme but requires a trusted setup. FRI and IPA are transparent alternatives with different size tradeoffs.

Every major ZK proof system you will encounter uses one of these schemes under the hood. Understanding this layer explains why proof sizes differ between systems, why some require ceremonies and others do not, and why verifying a STARK on Ethereum is expensive while verifying a SNARK is cheap.