Polynomial Commitment

Once a prover commits to a polynomial f, they cannot later change their mind and claim the commitment was to a different polynomial f'.

• Computational Binding: Changing the polynomial requires solving a hard mathematical problem (e.g., discrete log).
• Perfect Binding: The commitment mathematically determines the polynomial uniquely.
• This property ensures the prover is locked into a single statement, preventing them from forging proofs for false evaluations.

The commitment string C reveals zero information about the committed polynomial f(x).

• A verifier cannot deduce the degree or coefficients of the polynomial from the commitment alone.
• Perfect Hiding: The commitment is statistically independent of the polynomial.
• Computational Hiding: Distinguishing commitments is as hard as breaking a cryptographic assumption.
• This is crucial for zero-knowledge applications where the witness (the polynomial) must remain private.

The commitment and the evaluation proof must be sub-linear in the degree d of the polynomial.

• Constant-Size Commitment: The commitment string is a single group element (e.g., 32 bytes) regardless of whether the polynomial has 10 or 1,000,000 coefficients.
• Logarithmic Proof Size: The proof that f(a) = b is typically O(log d) in size.
• This property is what makes zkSNARKs practical, allowing a verifier to check massive computations with minimal data.

Commitments support algebraic operations directly on the commitments themselves, without knowing the underlying polynomials.

• Additive Homomorphism: Commit(f) + Commit(g) = Commit(f + g)
• Scalar Multiplication: c * Commit(f) = Commit(c * f)
• This enables batching of multiple evaluation proofs into a single proof.
• Provers can combine commitments to different polynomials to prove complex relationships between them efficiently.

The core interactive protocol where a prover convinces a verifier that f(a) = b without revealing f.

• The prover computes a witness polynomial w(x) = (f(x) - b) / (x - a).
• The prover then commits to w(x) and the verifier checks the relationship at a random challenge point.
• If f(a) truly equals b, then (x - a) divides (f(x) - b) evenly, leaving a valid polynomial w(x).
• This leverages the polynomial remainder theorem for soundness.

Different polynomial commitment schemes have varying trust assumptions for their initialization.

• Trusted Setup (e.g., KZG): Requires a multi-party computation ceremony to generate a Common Reference String (CRS). If the toxic waste is not destroyed, proofs can be forged.
• Transparent Setup (e.g., FRI, IPA): Uses nothing but a standard hash function. No toxic waste exists, offering stronger security guarantees.
• Universal Setup (e.g., Plonk-KZG): A single CRS can be reused for any circuit up to a fixed size limit, simplifying deployment.

A prover commits to the polynomial representing a machine learning model's computation. They can then generate a constant-size proof that the output for a given input is correct, without revealing the model's weights. This enables a lightweight client to verify that a cloud-based model executed faithfully.

• Mechanism: The model's forward pass is arithmetized into a polynomial, and a commitment is published.
• Benefit: Proof size and verification time are independent of model size, enabling scalable verification.

Polynomial commitments are used to prove the integrity of a training run. The entire iterative optimization process is encoded as a sequence of polynomial constraints. A final, succinct proof attests that the model weights are the result of a correct training algorithm applied to a specific dataset.

• Key Technique: Recursive proof composition combines proofs from each training step into one.
• Use Case: Auditing a model's provenance without re-running the entire compute-intensive training job.

Combined with zero-knowledge arguments, polynomial commitments allow a prover to demonstrate knowledge of a model's prediction without disclosing the model itself. The verifier learns only that the output is correct for a given input.

• Property: The commitment hides the polynomial (the model) while binding the prover to it.
• Application: A proprietary fraud detection model can be queried by a third party, who receives the result and a cryptographic proof of its correctness, without ever seeing the model's logic.

The KZG (Kate-Zaverucha-Goldberg) scheme is a popular polynomial commitment used in zkML for its constant-size proofs and efficient verification. It relies on elliptic curve pairings.

• Opening Proof: A single group element proves the evaluation of a committed polynomial at any point.
• Advantage: Enables batch opening of multiple evaluation points into a single constant-size proof, crucial for verifying many constraints in a neural network layer simultaneously.

The FRI (Fast Reed-Solomon IOP of Proximity) protocol provides a polynomial commitment scheme based on error-correcting codes and hash functions, avoiding a trusted setup. This is the foundation of zkSTARKs.

• Security: Relies on collision-resistant hash functions, offering post-quantum security.
• Trade-off: Proofs are larger than KZG (logarithmic in degree) but the setup is completely transparent, eliminating toxic waste concerns for high-stakes ML integrity proofs.

Polynomial commitments are the engine behind lookup arguments, which prove that all elements of a computed vector belong to a predefined table. This is critical for efficiently handling non-arithmetic operations in zkML.

• Example: Proving that the output of a ReLU activation function is correct without bit-decomposing the operation into thousands of arithmetic gates.
• Mechanism: A polynomial commitment is used to prove the multi-set equality between a query vector and a subset of a table vector, dramatically reducing circuit complexity.

A critical security distinction in polynomial commitment schemes that determines whether the commitment leaks information about the committed polynomial.

• Binding: Guarantees the prover cannot find two different polynomials that produce the same commitment. This is essential for computational integrity.
• Hiding: Guarantees the commitment reveals zero information about the polynomial. This is essential for zero-knowledge applications.
• KZG Hiding: Achieved by adding a random blinding polynomial of the same degree, using additional SRS elements to mask the original commitment.
• Trade-off: Hiding commitments often require larger proof sizes or additional verification work. Many zkSNARKs use only binding commitments for efficiency, relying on other techniques for zero-knowledge.