Batched Polynomial Openings

Amortizing opening proof costs across multiple polynomials with Dory commitment scheme

Batched polynomial openings allow the prover to create a single proof that demonstrates the correct evaluation of multiple committed polynomials at potentially different points. This optimization is critical for Jolt’s efficiency, as each proof stage requires opening dozens of polynomials.

Overview

Instead of creating N separate opening proofs for N polynomials:

1. Prover commits to all polynomial evaluations
2. Verifier samples a random batching challenge
3. Prover creates a single opening proof for the random linear combination
4. Verifier checks one combined opening instead of N individual proofs

Opening Accumulator Pattern

Jolt uses an accumulator pattern to collect opening claims throughout the proof:

// Prover side
struct ProverOpeningAccumulator<F: JoltField> {
    opening_claims: Vec<(PolynomialId, Point, Value)>,
    // ... commitment scheme state
}

// Verifier side  
struct VerifierOpeningAccumulator<F: JoltField> {
    opening_claims: Vec<(CommitmentId, Point, Value)>,
    zk_mode: bool,
    // ... commitment scheme state
}

Usage Pattern

During sumcheck stages:

// Prover caches openings after each sumcheck
sumcheck.cache_openings(opening_accumulator, &r_sumcheck);

// Internally calls:
opening_accumulator.append_claim(
    polynomial_id,
    opening_point,
    polynomial.evaluate(&opening_point),
);

After all sumchecks:

// Flush accumulated claims to transcript
opening_accumulator.flush_to_transcript(transcript);

// Create batched opening proof
let opening_proof = opening_accumulator.finalize(transcript);

Batching Strategies

Same-Point Batching

When multiple polynomials are opened at the same point r:

// Individual claims: P₁(r), P₂(r), ..., Pₙ(r)
// Batched claim: Q(r) where Q = Σᵢ βᵢ · Pᵢ

let batching_challenge = transcript.challenge_scalar();
let coeffs = powers_of(batching_challenge, num_polys);
let combined_poly = polynomials.iter()
    .zip(coeffs.iter())
    .map(|(poly, coeff)| poly * coeff)
    .sum();

Benefit: Single KZG/Dory opening proof instead of N proofs.

Different-Point Batching

When polynomials are opened at different points r₁, ..., rₙ:

// Use shift-and-combine technique:
// 1. Define shifted polynomial: P'ᵢ(x) = Pᵢ(x) - Pᵢ(rᵢ)
// 2. Compute quotient: Qᵢ(x) = P'ᵢ(x) / eq(x, rᵢ)
// 3. Batch the quotients

let quotients: Vec<_> = polynomials.iter().zip(points.iter())
    .map(|(poly, point)| {
        let shifted = poly.clone() - poly.evaluate(point);
        shifted.divide_by_eq_poly(point)
    })
    .collect();

// Now batch quotients (they can be opened at any common point)

Jolt’s implementation handles this transparently in the Dory opening proof.

Dory Batched Openings

Dory (Jolt’s default commitment scheme) supports efficient batching:

Tier-Based Structure

// Dory commitments are structured in tiers:
// - Tier 1: Polynomial chunks of size 2^chunk_size
// - Tier 2: Aggregation of tier-1 commitments

// Opening proof batches across both tiers:
struct DoryOpeningProof<C: JoltCurve> {
    tier1_proofs: Vec<TierProof<C>>,
    tier2_aggregation: AggregationProof<C>,
}

Batching Flow

1. Accumulation Phase (during sumcheck stages):

   // Each polynomial opening is accumulated
   accumulator.append_claim(poly_id, point, value);
   

2. Batching Phase (after all sumchecks):

   // Sample batching coefficients
   let coeffs = transcript.challenge_vector(num_claims);
   
   // Compute batched evaluation
   let batched_value = claims.iter().zip(coeffs.iter())
       .map(|(claim, coeff)| claim.value * coeff)
       .sum();
   

3. Opening Proof Generation:

   // Create single proof for batched polynomial
   let proof = dory_scheme.prove_batched_opening(
       polynomials,
       points,
       batched_value,
       batching_coeffs,
   );
   

Zero-Knowledge Mode

In ZK mode, opening proofs must not reveal polynomial evaluations:

Standard Mode

// Cleartext evaluation revealed
opening_accumulator.append_claim(poly_id, point, value);
transcript.append_scalar(b"opening_value", &value);

ZK Mode

// Evaluation is committed, not revealed
let value_commitment = pedersen_gens.commit(&[value], &blinding);
transcript.append_commitment(b"opening_commitment", &value_commitment);

// Dory creates "ZK evaluation commitment" (y_com)
let zk_opening_proof = dory_scheme.prove_opening_zk(
    polynomial,
    point,
    value_commitment,  // Committed value, not cleartext
);

BlindFold later proves that these committed evaluations are correct.

Performance Impact

Cost Comparison

Metric	Individual Openings	Batched Openings
Prover time	O(N · M)	O(M) + O(N)
Proof size	N × proof_size	1 × proof_size + O(N)
Verifier time	O(N · V)	O(V) + O(N)

Where:

• N = number of polynomials
• M = polynomial size (commitment time)
• V = opening verification cost

Concrete Example: Jolt Stage 8

Stage 8 performs a single batched Dory opening for all polynomials accumulated across stages 1-7:

• Polynomials opened: 50-100+ (depends on program)
• Batched into: 1 Dory opening proof
• Prover speedup: ~10-20x vs. individual openings
• Proof size reduction: ~30-50x

Transcript Optimization

Critical change in Jolt’s BlindFold branch:

On this branch, ProverOpeningAccumulator::append_* and VerifierOpeningAccumulator::append_* do NOT append claims to the Fiat-Shamir transcript (the transcript parameter was removed). Both sides are consistent. On main, these methods DO append opening_claim scalars.

This eliminates redundant transcript operations during accumulation.

Implementation Details

Opening Claim Structure

pub struct OpeningClaim<F: JoltField> {
    pub polynomial_id: usize,
    pub opening_point: Vec<F::Challenge>,
    pub opening_value: F,
}

Accumulator Methods

impl<F: JoltField> ProverOpeningAccumulator<F> {
    // Add a polynomial opening claim
    pub fn append_claim(
        &mut self,
        poly_id: usize,
        point: &[F::Challenge],
        value: F,
    );
    
    // Flush all claims to transcript (generates batching coeffs)
    pub fn flush_to_transcript(&mut self, transcript: &mut impl Transcript);
    
    // Create batched opening proof
    pub fn finalize(&self, transcript: &mut impl Transcript) -> OpeningProof;
}

Usage in Jolt Proof Stages

Each sumcheck stage accumulates openings:

// Stage 1: Spartan outer sumcheck
let (proof1, r1, _) = BatchedSumcheck::prove(stage1_instances, accumulator, transcript);
stage1_instances.iter().for_each(|instance| {
    instance.cache_openings(accumulator, &r1);
});

// Stage 2: Instruction lookups
let (proof2, r2, _) = BatchedSumcheck::prove(stage2_instances, accumulator, transcript);
stage2_instances.iter().for_each(|instance| {
    instance.cache_openings(accumulator, &r2);
});

// ... stages 3-7 ...

// Stage 8: Single batched opening for ALL accumulated claims
let opening_proof = accumulator.finalize(transcript);

Related Optimizations

• Batched Sumcheck: Batch sumcheck protocols
• CompactPolynomial: Efficient polynomial storage
• Torus Compression: Compress opening proof size

References

• Dory: Efficient, Transparent Polynomial Commitments — Dory commitment scheme
• ProverOpeningAccumulator implementation: jolt-core/src/poly/opening_proof.rs
• Batched opening verification: jolt-core/src/poly/commitment/dory/