Skip to main content

Documentation Index

Fetch the complete documentation index at: https://mintlify.com/a16z/jolt/llms.txt

Use this file to discover all available pages before exploring further.

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

MetricIndividual OpeningsBatched Openings
Prover timeO(N · M)O(M) + O(N)
Proof sizeN × proof_size1 × proof_size + O(N)
Verifier timeO(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);

​
References

Build docs developers (and LLMs) love

Get started for freeTalk to us