Skip to main content
Polynomial commitment schemes (PCS) are a core cryptographic primitive in proof systems, including zkVMs. They allow a prover to commit to a polynomial and later prove evaluations of that polynomial at points chosen by the verifier, without revealing the entire polynomial.

​
Overview

At a high level, polynomial commitment schemes allow a prover to:
  1. Commit to a polynomial
  2. Later open that commitment (evaluate the underlying polynomial) at a point chosen by the verifier
  3. Ensure the binding property: the prover cannot change the polynomial after committing
This mechanism is powerful because it allows succinct verification of polynomial relationships without the prover needing to reveal the entire polynomial. The verifier only learns the evaluation at chosen points.

​
Components

A PCS comprises three main algorithms (plus optional preprocessing):
  • Commit: C:=Commit(P)C := \mathsf{Commit}(P) - Create a commitment to polynomial PP
  • Prove: π:=Prove(P,r)\pi := \mathsf{Prove}(P, r) - Generate an opening proof for P(r)P(r)
  • Verify: Verify(C,r,x,π)\mathsf{Verify}(C, r, x, \pi) - Verify that P(r)=xP(r) = x given commitment CC

​
Preprocessing

Depending on the PCS, there may be a preprocessing step that generates public parameters:
  • Trusted setup: Requires a trusted party to generate parameters (e.g., KZG)
  • Transparent setup: Parameters can be generated publicly without trust assumptions (e.g., Dory, FRI)
Jolt uses Dory, which has a transparent setup.

​
Usage Pattern

In the context of a larger proof system like Jolt, polynomial commitment schemes are typically used as follows:

​
Step 0: Preprocessing

Generate public parameters if needed. This data may be required for commit, prove, or verify operations.

​
Step 1: Commitment

Prover commits to polynomial PP, and the commitment C:=Commit(P)C := \mathsf{Commit}(P) is sent to the verifier.

​
Step 2: Challenge

In some subsequent part of the proof system, the prover and verifier arrive at a claimed evaluation x:=P(r)x := P(r) for a random point r∈Fnr \in \mathbb{F}^n. For example, this claimed evaluation might be an output claim from a sumcheck protocol.

​
Step 3: Opening Proof

The prover provides an opening proof and sends π:=Prove(P,r)\pi := \mathsf{Prove}(P, r) to the verifier.

​
Step 4: Verification

The verifier verifies the opening proof via Verify(C,r,x,π)\mathsf{Verify}(C, r, x, \pi). If verification succeeds, the verifier is convinced that P(r)=xP(r) = x as claimed.

​
Role in Jolt

In Jolt, the prover commits to several witness polynomials derived from the execution trace being proven. These polynomial commitments tie together the various algebraic claims generated during proving.

​
Committed Witness Polynomials

Jolt commits to the following witness polynomials:
  • RdInc: Increment counters for destination registers
  • RamInc: Increment counters for RAM addresses
  • InstructionRa/Rad: Read address polynomials for instruction lookups
  • BytecodeRa/Rad: Read address polynomials for bytecode
  • RamRa/Rad: Read address polynomials for RAM
  • TrustedAdvice: Prover-supplied auxiliary witness data (verified)
  • UntrustedAdvice: Prover-supplied auxiliary witness data (constrained)

​
Dory PCS

Jolt currently uses Dory as its polynomial commitment scheme. Dory provides:
  • Transparent setup: No trusted party required
  • Efficient one-hot commitments: Optimized for sparse polynomials
  • Batch openings: Amortizes cost across multiple opening proofs
  • Pay-per-bit commitments: Commitment size proportional to coefficient size, not field size
The pay-per-bit property is particularly important for Jolt: witness polynomials with small coefficients (like one-hot encodings or small counters) have proportionally small commitments.

​
Opening Proof Pipeline

Jolt’s opening proof pipeline (step 6 in the prover pipeline):
  1. During sumcheck stages, polynomial openings accumulate in ProverOpeningAccumulator
  2. Batched Dory opening proofs are generated via the accumulator
  3. In ZK mode, openings use committed evaluations (y_com) rather than revealing values directly

​
Key Properties

​
Binding

Once committed, the prover cannot change the polynomial. Any attempt to open at a different polynomial will fail verification except with negligible probability.

​
Hiding (Optional)

Some PCS schemes provide hiding: the commitment reveals no information about the polynomial. Dory in Jolt can be used in ZK mode with Pedersen blinding.

​
Succinctness

Commitment size and verification time should be much smaller than the polynomial size. For Dory, commitments are logarithmic in the polynomial size.

​
Batching

Modern PCS schemes support batching: opening multiple polynomials at multiple points with a single proof. This amortizes the proof cost. Jolt extensively uses batch openings. All polynomial openings from the sumcheck stages are batched into a single opening proof, reducing verification cost.

​
Implementation in Jolt

Polynomial commitment code lives in jolt-core/src/poly/commitment/:
  • dory/: Dory PCS implementation
    • commitment_scheme.rs: Main commit/prove/verify logic
    • streaming.rs: Streaming commitment for large polynomials
  • pedersen.rs: Pedersen commitments for small vectors (used in BlindFold)
  • hyperkzg.rs: HyperKZG implementation (alternative PCS)
The commitment scheme is generic over the CommitmentScheme trait, allowing different PCS backends.

​
Further Reading

For a more formal and detailed introduction to polynomial commitment schemes, see:

Build docs developers (and LLMs) love

Get started for freeTalk to us