Polynomial commitments

Why do we need polynomial commitments?

Suppose someone gives you a polynomial:

They claim that f has some important property. Later, they want to convince you that:

The naive approach is to send you the entire polynomial. But if the polynomial has millions of coefficients, that is expensive.

A polynomial commitment scheme lets the prover first create a short cryptographic commitment to the polynomial. Later, the prover can open that commitment at a point and convince the verifier of the value without sending the entire polynomial.

What is a commitment scheme?

Before talking about polynomials, understand ordinary commitments.

A commitment scheme has two conceptual phases:

1. Commit: choose a value m and produce a commitment C.
2. Open: later reveal information that allows the verifier to check that C really committed to m.

A useful commitment needs two central security properties.

These properties are logically different. Some commitment schemes are perfectly binding but not hiding; others add randomness to obtain hiding.

Now replace a message with a polynomial

For a polynomial commitment, the committed object is not just one number.

The commitment algorithm produces a compact value:

Later, the prover can claim:

and provide an opening proof π:

The verifier does not need to receive every coefficient of f.

The basic polynomial-commitment API

A typical scheme can be described with four algorithms:

Some schemes also have separate algorithms for setup, batch opening, multi-point opening, aggregation, or degree-bound enforcement.

What security properties should it have?

Binding

A malicious prover should not be able to produce valid openings claiming two different values for the same point:

If both openings verify against the same commitment, the scheme's binding property has failed.

Hiding

Hiding means the commitment does not unnecessarily reveal the polynomial itself.

Whether a particular polynomial commitment is hiding depends on the construction. For example, the simplest textbook KZG commitment is binding under its assumptions but is not automatically hiding; blinding techniques can be added when hiding is required.

Succinctness

The commitment and opening proof should be much smaller than the polynomial representation.

Efficient verification

The verifier should be able to check an opening substantially faster than reconstructing and evaluating a huge polynomial from scratch.

KZG: the first major construction

KZG stands for Kate–Zaverucha–Goldberg polynomial commitments.

The key idea is surprisingly compact:

Let:

The trusted setup publishes group elements representing:

The secret τ itself is never revealed.

The commitment is:

Why is the KZG setup called a trusted setup?

The setup generates a secret scalar:

and publishes:

The dangerous piece is τ. If someone learns it, they may be able to violate the security assumptions behind the commitment.

This is why practical systems use multi-party ceremonies or other mechanisms intended to ensure that no single participant knows the final toxic waste.

How can KZG prove f(z) = y?

Suppose the prover wants to prove:

Define the polynomial:

Why is this a polynomial?

Because if f(z)=y, then:

so x−z divides f(x)−y.

Equivalently:

The prover computes a commitment to q. That commitment is the KZG opening proof:

Where do pairings enter?

The commitment equation conceptually contains:

The opening proof contains:

Since:

evaluate at the hidden point τ:

The verifier wants to check this relation without learning τ.

A bilinear pairing lets the verifier move scalar multiplication relationships into a pairing equation. In one common notation, with groups G₁, G₂, and target group G_T:

Equivalent formulations rearrange this equation depending on how the setup elements are represented.

KZG opening example from first principles

Take:

Suppose we open at:

The claimed value is:

Now compute:

Therefore:

The prover commits to q and sends the resulting group element as the opening proof.

The verifier does not need to receive the original coefficients of f.

Why does the degree bound matter?

Suppose a commitment scheme is intended for polynomials of degree at most d.

The setup provides enough powers to represent:

If the prover could freely use a polynomial of a much larger degree, the public parameters would no longer provide the intended representation.

Therefore polynomial commitment schemes often have a degree-bound requirement:

Degree bounds become particularly important when commitments are used inside larger proof systems.

Opening multiple points

A prover may need to prove:

Sending an independent proof for every point can be wasteful.

Polynomial commitment schemes can therefore provide batch opening techniques that combine several claims into a smaller proof or fewer verification operations.

The exact construction depends on the scheme and security model, but the motivation is always the same: exploit algebraic structure instead of paying independently for every opening.

KZG in Rust: the core algebra

The following educational implementation demonstrates the central KZG idea over a small prime field. It is intentionally not an elliptic-curve implementation; instead, it models the exponent/scalar algebra so the polynomial quotient relationship is visible.

// Educational model of the algebra behind KZG.
// This demonstrates:
//   C = f(tau)
//   q(x) = (f(x) - f(z)) / (x - z)
//   f(tau) - f(z) = q(tau) * (tau - z)
//
// A real KZG implementation encodes these scalars
// into elliptic-curve group elements and verifies the
// relation with a bilinear pairing.

const P: u64 = 97;

fn add(a: u64, b: u64) -> u64 {
    (a + b) % P
}

fn sub(a: u64, b: u64) -> u64 {
    (a + P - b) % P
}

fn mul(a: u64, b: u64) -> u64 {
    (a * b) % P
}

fn pow(mut base: u64, mut exp: u64) -> u64 {
    let mut result = 1;

    while exp > 0 {
        if exp & 1 == 1 {
            result = mul(result, base);
        }

        base = mul(base, base);
        exp >>= 1;
    }

    result
}

fn inv(a: u64) -> u64 {
    assert!(a != 0);
    pow(a, P - 2)
}

fn eval(coeffs: &[u64], x: u64) -> u64 {
    let mut result = 0;

    // Horner's method.
    for &c in coeffs.iter().rev() {
        result = add(mul(result, x), c);
    }

    result
}

// Synthetic division by (x - z).
// Returns quotient q where:
// f(x) - f(z) = q(x) * (x - z).
fn opening_quotient(coeffs: &[u64], z: u64) -> Vec<u64> {
    assert!(coeffs.len() >= 2);

    let n = coeffs.len() - 1;
    let mut q = vec![0; n];

    q[n - 1] = coeffs[n];

    for i in (1..n).rev() {
        q[i - 1] = add(
            coeffs[i],
            mul(z, q[i]),
        );
    }

    q
}

fn main() {
    // f(x) = 3 + 2x + x^2.
    let f = vec![3, 2, 1];

    // Secret setup scalar in this educational model.
    let tau = 11;

    // Opening point.
    let z = 4;

    // Claimed evaluation y = f(z).
    let y = eval(&f, z);

    // Commitment is modeled as f(tau).
    let commitment = eval(&f, tau);

    // Opening quotient.
    let q = opening_quotient(&f, z);

    // Proof is modeled as q(tau).
    let proof = eval(&q, tau);

    // The fundamental KZG equation:
    // f(tau) - f(z) = q(tau) * (tau - z).
    let lhs = sub(commitment, y);

    let rhs = mul(
        proof,
        sub(tau, z),
    );

    assert_eq!(lhs, rhs);

    println!("commitment = {commitment}");
    println!("evaluation  = {y}");
    println!("quotient    = {:?}", q);
    println!("proof model = {proof}");
    println!("opening verified");
}

This code is useful because it isolates the algebraic heart of KZG. In a real implementation:

What a real Rust implementation looks like

For actual KZG over BLS12-381, a Rust implementation uses finite-field and elliptic-curve types rather than plain integers.

The conceptual structure is:

And the opening proof is another multi-scalar multiplication using the quotient polynomial.

A production implementation should use a mature pairing library, constant-time field/group operations where appropriate, compressed serialization, subgroup checks, and carefully audited parameter handling.

FRI is a different kind of polynomial commitment

KZG is not the only way to commit to a polynomial.

FRI-based systems use a very different idea. Instead of hiding the polynomial inside an elliptic-curve group element, they work with evaluations over a finite domain and commit to those evaluations using hash-based structures such as Merkle trees.

FRI is more precisely a low-degree testing protocol; in a STARK, Merkle commitments to evaluation vectors and FRI are combined to obtain a proof system for low-degree claims.

Why Merkle trees appear with FRI

Suppose the prover has evaluations:

Hash each value and build a Merkle tree:

The root becomes a compact commitment to the entire evaluation vector.

Later, the prover can reveal selected evaluations together with Merkle authentication paths. The verifier checks that the revealed values really belong to the committed vector.

FRI then supplies the algebraic part: evidence that the committed evaluations are consistent with a low-degree polynomial.

KZG vs FRI: what is actually different?

How polynomial commitments fit into a ZK proof

A proving system often needs to convince a verifier about many polynomial relationships.

A simplified algebraic proof pipeline looks like:

For KZG-based SNARKs, polynomial commitments are used to make polynomial claims succinctly verifiable.

For STARKs, evaluation-domain commitments and FRI allow the verifier to check that committed data behaves like evaluations of low-degree polynomials.

So the commitment layer sits between “here are my algebraic objects” and “here is a small proof about those objects.”

Common mistakes

The whole idea in one map

If FFT answers “how do we efficiently move between polynomial representations?”, polynomial commitments answer “how do we cryptographically bind to a polynomial and later prove statements about it without sending the whole polynomial?”