01 · Statement

The argument in one sentence

A polynomial commitment opening is meaningful only relative to a commitment that was fixed before the opening proof was produced.

If the prover supplies the commitment inside the proof and the verifier has no independently trusted copy, verification establishes only that the value and witnesses are consistent with that prover-chosen commitment. It does not establish that this is the value of the polynomial committed to earlier.

The pairing equation cannot recover missing protocol context. The API has to preserve it.

02 · Implementation

What I implemented

The repository builds the relevant pieces from first principles: multilinear polynomials represented by evaluations on the Boolean hypercube, partial evaluation and interpolation, a structured reference string evaluated at a secret point, commitment computation, quotient-witness generation, and pairing-based verification using Arkworks and BLS12-381.

The code is intentionally educational. It keeps the algebra visible instead of hiding it behind an optimized polynomial-commitment interface.

One naming detail matters: the Rust field is called coefficients, but the vector behaves as an evaluation table. For an n-variable multilinear polynomial, it stores values f(b) for Boolean vectors b. These are not monomial-basis coefficients.

  • Boolean-hypercube evaluation tables
  • Multilinear extension and partial evaluation
  • Lagrange-basis commitment over BLS12-381
  • Quotient-witness construction and pairing verification

03 · Polynomial representation

From a Boolean evaluation table to any field point

A multilinear polynomial is determined by its values on the Boolean hypercube. Its multilinear extension evaluates that table at an arbitrary field point by weighting every Boolean evaluation with the matching equality-basis polynomial.

The implementation evaluates one variable at a time. When two table entries differ only in the variable being fixed, partial evaluation is ordinary linear interpolation. Repeating that fold over every coordinate reduces the full table to one value.

This representation is useful for studying sumcheck and GKR because both protocols repeatedly fix variables of multilinear extensions.

f~(x)=∑b∈{0,1}nf(b) χb(x),χb(x)=∏j=1n(bjxj+(1−bj)(1−xj))\widetilde{f}(x)=\sum_{b\in\{0,1\}^{n}}f(b)\,\chi_b(x),\qquad \chi_b(x)=\prod_{j=1}^{n}\left(b_jx_j+(1-b_j)(1-x_j)\right)
The multilinear extension written in the equality basis over the Boolean hypercube.
Partial evaluation is linear interpolationrust
fn interpolate<F: Field>(y0: F, y1: F, r: F) -> F {
    y0 + r * (y1 - y0)
}

04 · Commitment

Committing in the multilinear Lagrange basis

Classic KZG is often introduced for a univariate polynomial in the monomial basis. This prototype commits to a multilinear evaluation table in the Lagrange basis over the Boolean hypercube.

For a secret setup point tau, the setup contains group elements for each basis evaluation chi_b(tau). The commitment is the group-valued inner product of those basis elements and the evaluation table.

The implementation makes group and field operations explicit. It also exposed a real dimension hazard: one path indexes a slice while another uses zip, which silently stops at the shorter iterator. The mathematics assumes matching dimensions, so the public API must enforce them before doing algebra.

C=∑b∈{0,1}nf(b)[χb(τ)]1=[f~(τ)]1\begin{aligned}C&=\sum_{b\in\{0,1\}^{n}}f(b)\left[\chi_b(\tau)\right]_1\\&=\left[\widetilde{f}(\tau)\right]_1\end{aligned}
The commitment is the multilinear evaluation at the hidden setup point, encoded in G1.
Commitment as a group-valued inner productrust
fn commit(g1_basis: &[P::G1], evaluations: &[F]) -> P::G1 {
    let mut commitment = P::G1::zero();

    for (i, basis) in g1_basis.iter().enumerate() {
        let scalar = evaluations[i].into_bigint();
        commitment += basis.mul_bigint(scalar);
    }

    commitment
}

05 · Opening proof

The quotient identity behind verification

Suppose the prover claims v = f(r). For multilinear polynomials, the difference from the claimed value decomposes across coordinates. Each quotient polynomial records the slope along one variable after the earlier variables have been fixed.

The prototype constructs a quotient from paired entries in the current evaluation table, partially evaluates at the matching coordinate, and repeats. At the end, the remainder should be zero.

The proof contains the claimed value and commitments to the quotient polynomials. Arkworks represents its target-group wrapper with additive operators, so the implementation accumulates pairing outputs with addition even though conventional notation writes a product.

f~(X)−v=∑i=1n(Xi−ri)Qi(X)e ⁣(C−v[G1],[G2])=∏i=1ne ⁣([Qi(τ)]1,[τi−ri]2)\begin{aligned}\widetilde{f}(X)-v&=\sum_{i=1}^{n}(X_i-r_i)Q_i(X)\\e\!\left(C-v[G_1],[G_2]\right)&=\prod_{i=1}^{n}e\!\left([Q_i(\tau)]_1,[\tau_i-r_i]_2\right)\end{aligned}
The quotient decomposition and its corresponding multilinear KZG pairing check.
Pairing verification in Arkworksrust
let claimed_value = g1.mul_bigint(value.into_bigint());
let lhs = P::pairing(commitment - claimed_value, g2);

let mut rhs = PairingOutput::<P>::ZERO;

for (i, tau_i) in g2_taus.iter().enumerate() {
    let r_i = g2.mul_bigint(point[i].into_bigint());
    let tau_minus_r = *tau_i - r_i;
    let quotient = quotient_commitments[i];

    rhs += P::pairing(quotient, tau_minus_r);
}

lhs == rhs

06 · Trust boundary

The API mistake: the proof carried its own commitment

My first proof type carried the commitment alongside the claimed value and quotient commitments. The verifier read that commitment from the proof and checked the equation against it.

The equation can be perfectly valid while the statement is still wrong for the application. The prover selected the polynomial, the commitment, the claimed value, and the witnesses. A server could replace an earlier database commitment with a new polynomial that gives a convenient value at the requested point and return a valid opening for the replacement.

No pairing check detects this because the new tuple may be internally correct. The issue is not broken elliptic-curve arithmetic. It is a broken statement boundary.

The prover-controlled referencerust
pub struct KzgProof<G1, F> {
    pub commitment: G1, // Prover-controlled reference
    pub value: F,
    pub quotient_commitments: Vec<G1>,
}

07 · API design

A better interface

The opening proof should not have authority over the identity of the committed object. The verifier must receive the expected commitment from trusted application state, a transcript, a signed object, a consensus layer, or another source fixed before the opening was generated.

The type boundary now says what prose otherwise has to explain: the proof supplies an opening, the caller supplies the commitment it expects, and malformed input is distinct from a well-formed but invalid proof.

For transcript-based protocols, I would absorb the commitment, point, claimed value, and protocol or domain identifier before deriving Fiat-Shamir challenges. Application state should also bind the commitment to the relevant record ID, chain, version, and context.

Expected commitment supplied independentlyrust
pub struct OpeningProof<G1, F> {
    pub value: F,
    pub quotient_commitments: Vec<G1>,
}

pub fn verify_opening<P: Pairing>(
    vk: &VerifierKey<P>,
    expected_commitment: P::G1,
    point: &[P::ScalarField],
    proof: &OpeningProof<P::G1, P::ScalarField>,
) -> Result<bool, VerificationError> {
    validate_dimensions(vk, point, proof)?;
    verify_pairing(vk, expected_commitment, point, proof)
}

08 · Limits

What would need to change before production

The commitment boundary was the most instructive problem, but it was not the only production gap. Prover and verifier state should be separated so verification never requires the witness polynomial or the complete setup.

The locally known tau values are useful for deterministic tests and inappropriate as a trusted setup. A production system needs a secure ceremony, a correctly inherited setup, or a transparent commitment scheme with different assumptions.

Canonical serialization, subgroup checks, versioning, domain separation, explicit transcript ordering, structured verification errors, negative tests, property tests, fuzzing, and benchmarks are protocol requirements rather than finishing touches.

Finally, a polynomial commitment and evaluation proof are not automatically zero knowledge. Hiding requires additional randomization and a security argument for the complete protocol.

  • Separate ProverKey, VerifierKey, commitment, and opening-proof types
  • Reject malformed dimensions and non-canonical encodings before algebra
  • Treat setup generation and transcript rules as security protocols
  • Test mutated commitments, points, values, witnesses, lengths, and encodings
  • State explicitly whether the complete construction provides hiding

09 · Reflection

The lesson extends beyond KZG

The same mistake appears when a Merkle proof is checked against a root supplied by the prover, a signature is verified against a caller-selected public key with no identity binding, or a SNARK is accepted against public inputs that are not tied to the intended state.

Cryptographic verification proves a precise relation over its inputs. It does not decide whether those inputs are the ones the application meant to trust. That responsibility lives at the boundary between cryptographic code and protocol code.

Implementing the scheme made the quotient identity and pairing equation concrete. The more valuable lesson came after the equation worked: start with protocol roles and trusted inputs, make the Rust types encode them, and optimize only after the statement boundary is sound.