> ## 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 > 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: ```rust theme={null} // Prover side struct ProverOpeningAccumulator { opening_claims: Vec<(PolynomialId, Point, Value)>, // ... commitment scheme state } // Verifier side struct VerifierOpeningAccumulator { opening_claims: Vec<(CommitmentId, Point, Value)>, zk_mode: bool, // ... commitment scheme state } ``` ### Usage Pattern **During sumcheck stages:** ```rust theme={null} // 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:** ```rust theme={null} // 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`: ```rust theme={null} // 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ₙ`: ```rust theme={null} // 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 ```rust theme={null} // 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 { tier1_proofs: Vec>, tier2_aggregation: AggregationProof, } ``` ### Batching Flow 1. **Accumulation Phase** (during sumcheck stages): ```rust theme={null} // Each polynomial opening is accumulated accumulator.append_claim(poly_id, point, value); ``` 2. **Batching Phase** (after all sumchecks): ```rust theme={null} // 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**: ```rust theme={null} // 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 ```rust theme={null} // Cleartext evaluation revealed opening_accumulator.append_claim(poly_id, point, value); transcript.append_scalar(b"opening_value", &value); ``` ### ZK Mode ```rust theme={null} // 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 ```rust theme={null} pub struct OpeningClaim { pub polynomial_id: usize, pub opening_point: Vec, pub opening_value: F, } ``` ### Accumulator Methods ```rust theme={null} impl ProverOpeningAccumulator { // 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: ```rust theme={null} // 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](/architecture/optimizations/batched-sumcheck): Batch sumcheck protocols * [CompactPolynomial](/architecture/optimizations/small-value): Efficient polynomial storage * [Torus Compression](/architecture/optimizations/compression): Compress opening proof size ## References * [Dory: Efficient, Transparent Polynomial Commitments](https://eprint.iacr.org/2020/1274) — Dory commitment scheme * ProverOpeningAccumulator implementation: `jolt-core/src/poly/opening_proof.rs` * Batched opening verification: `jolt-core/src/poly/commitment/dory/`