Batched Opening Proofs

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.

​

Overview

​

Role in the Proving System

1. Stage 8: Batched opening proofs
2. Input: Opening claims accumulated across Stages 1-7
3. Method: Batch all claims via random linear combination, prove via Dory
4. Output: Single batched proof covering all polynomial evaluations
5. Benefit: ~10x smaller proof size vs. individual opening proofs

​

Opening Accumulator Pattern

​

Prover Accumulator

pub struct ProverOpeningAccumulator<F: JoltField> {
    openings: HashMap<OpeningId, (OpeningPoint, F)>,  // id → (point, eval)
    // ... cached data for batching ...
}

// During sumcheck stages:
accumulator.append_committed(poly_id, point, eval);
accumulator.append_virtual(poly_id, point, eval);
accumulator.append_advice(kind, point, eval);

// After all stages:
let proof = accumulator.prove_openings(pcs_setup);

​

Verifier Accumulator

pub struct VerifierOpeningAccumulator<F: JoltField> {
    openings: HashMap<OpeningId, (OpeningPoint, F::Challenge)>,
    commitments: HashMap<OpeningId, Commitment>,
}

// During sumcheck stages:
accumulator.append_commitment(poly_id, point, commitment);

// Verification:
let result = accumulator.verify_openings(proof, pcs_setup);

​

Opening ID Structure

pub enum OpeningId {
    Committed(CommittedPolynomial, SumcheckId),
    Virtual(VirtualPolynomial, SumcheckId),
    TrustedAdvice(SumcheckId),
    UntrustedAdvice(SumcheckId),
}

• Polynomial: Which committed/virtual polynomial (e.g., RamInc, InstructionRa[3])
• Sumcheck ID: Which sumcheck stage produced the opening (e.g., RamReadWriteChecking)

​

Committed vs. Virtual Polynomials

​

Committed Polynomials

• RdInc: Increment polynomial for register destination
• RamInc: Increment polynomial for RAM addresses
• InstructionRa[d]: Read-after polynomial for instruction lookups (d dimensions)
• BytecodeRa[d]: Read-after polynomial for bytecode lookups
• RamRa[d]: Read-after polynomial for RAM accesses
• TrustedAdvice: Prover-supplied trusted witness data
• UntrustedAdvice: Prover-supplied untrusted witness data

​

Virtual Polynomials

• InstructionFlags: One-hot encoding of instruction type (derived from trace)
• RegisterValues: Register contents (derived from trace + register checking)
• RamAddress, RamValue: Memory access address/value (derived from trace + RAM checking)
• PC: Program counter (derived from bytecode checking)

​

Batching Strategy

​

Batching Protocol

1. Prover commits to all polynomials (one-time, at start)
2. Sumcheck stages produce opening claims:
   poly_1(r_1) = v_1
   poly_2(r_2) = v_2
   ...
   poly_n(r_n) = v_n
   
3. Verifier samples random batching challenge α
4. Prover constructs batched polynomial:
   P_batch = poly_1 + α·poly_2 + α²·poly_3 + ... + α^(n-1)·poly_n
   
5. Prover proves opening:
   P_batch(r_batch) = v_1 + α·v_2 + α²·v_3 + ... + α^(n-1)·v_n
   
   where r_batch is a combined challenge point.

​

Soundness

P_batch(r_batch) ≠ v_batch

​

Opening Points

pub struct OpeningPoint<const ORDER: BindingOrder, F: JoltField> {
    pub r: Vec<F::Challenge>,  // Evaluation point
}

​

Binding Order

• Challenges consumed from MSB to LSB
• Used for cycle-indexed polynomials (outer sumcheck)

• Challenges consumed from LSB to MSB
• Used for address-indexed polynomials (RAM/register checking)

​

Dory Commitment Scheme

​

Key Properties

• Transparent setup: No trusted setup required
• Logarithmic proof size: O(log n) group elements for n-coefficient polynomial
• Efficient batching: Supports batching via random linear combination
• KZG-like structure: Based on inner-product arguments over elliptic curves

​

Commitment Process

pub trait CommitmentScheme {
    fn commit(poly: &DensePolynomial<F>) -> Commitment;
    fn prove_opening(
        poly: &DensePolynomial<F>,
        point: &[F::Challenge],
        eval: F,
    ) -> OpeningProof;
    fn verify_opening(
        commitment: &Commitment,
        point: &[F::Challenge],
        eval: F,
        proof: &OpeningProof,
    ) -> bool;
}

​

Batched Dory Opening

proof = Dory::batch_prove(
    polys: &[DensePolynomial<F>],
    points: &[Vec<F::Challenge>],
    evals: &[F],
)

​

ZK Mode: Evaluation Commitments

​

Standard Mode

proof.openings = Claims<F> {
    poly_id → (point, eval),  // eval revealed in clear
    ...
}

​

ZK Mode

proof.openings = BlindFoldProof {  // evals hidden
    y_com: Commitment,  // Commitment to evaluation
    // ... BlindFold R1CS proof ...
}

Dory::prove_opening_zk(
    poly: &DensePolynomial<F>,
    point: &[F::Challenge],
    eval: F,  // Not revealed
) -> (y_com: Commitment, proof: OpeningProof)

​

Stage 8: Opening Proof Generation

​

Prover Side

pub fn prove_openings<PCS: CommitmentScheme>(
    accumulator: ProverOpeningAccumulator<F>,
    pcs_setup: &PCS::ProverSetup,
) -> BatchedOpeningProof<PCS> {
    // 1. Collect all openings
    let openings = accumulator.openings;
    
    // 2. Group by polynomial (multiple openings of same poly)
    let grouped = group_by_polynomial(openings);
    
    // 3. Batch prove all groups
    let proofs = grouped.par_iter().map(|(poly_id, openings)| {
        PCS::batch_prove(
            poly: get_polynomial(poly_id),
            points: openings.iter().map(|(pt, _)| pt),
            evals: openings.iter().map(|(_, eval)| eval),
            setup: pcs_setup,
        )
    }).collect();
    
    BatchedOpeningProof { proofs }
}

​

Verifier Side

pub fn verify_openings<PCS: CommitmentScheme>(
    accumulator: VerifierOpeningAccumulator<F>,
    proof: BatchedOpeningProof<PCS>,
    pcs_setup: &PCS::VerifierSetup,
) -> Result<(), Error> {
    // 1. Group openings by polynomial
    let grouped = group_by_polynomial(accumulator.openings);
    
    // 2. Verify each group's batched proof
    for ((poly_id, openings), group_proof) in grouped.zip(proof.proofs) {
        PCS::batch_verify(
            commitment: accumulator.commitments[poly_id],
            points: openings.iter().map(|(pt, _)| pt),
            evals: openings.iter().map(|(_, eval)| eval),
            proof: group_proof,
            setup: pcs_setup,
        )?;
    }
    Ok(())
}

​

Opening IDs by Stage

​

Stage 1 (Spartan Outer)

• VirtualPolynomial::* (Az, Bz, instruction flags)

​

Stage 2 (Product Virtual + RAM)

• CommittedPolynomial::RamRa[d] (d dimensions)
• CommittedPolynomial::RamInc

​

Stage 3 (Registers + Bytecode)

• CommittedPolynomial::RdInc
• CommittedPolynomial::BytecodeRa[d]

​

Stage 5 (Instruction Lookups)

• CommittedPolynomial::InstructionRa[d]

​

Stage 7 (Claim Reductions)

• All CommittedPolynomial::* at final reduction points
• TrustedAdvice / UntrustedAdvice (if present)

​

Stage 8 (Opening Proofs)

• Batches all above into single proof

​

Performance Characteristics

​

Prover Time

• O(num_openings · poly_size · log(poly_size)) field operations
• ~10-15% of total proving time
• Parallelized across polynomial groups

• Individual proofs: ~100ms per opening × 500 openings = 50s
• Batched proof: ~5s total (10x speedup)

​

Proof Size

• ~1KB per Dory opening proof
• Total: ~500KB for 500 openings

• ~50KB for all 500 openings (10x reduction)

​

Verifier Time

• O(num_openings · log(poly_size)) field operations
• ~5-10ms for typical proofs
• Batching reduces constant factors

​

Memory Usage

• ~1KB per opening (point + eval + metadata)
• ~500KB for 500 openings
• Cleared after Stage 8 (not included in final proof)

​

Key Files

• jolt-core/src/poly/opening_proof.rs: ProverOpeningAccumulator, VerifierOpeningAccumulator
• jolt-core/src/poly/commitment/dory/: Dory commitment scheme implementation
• jolt-core/src/zkvm/prover.rs: Stage 8 prover logic
• jolt-core/src/zkvm/verifier.rs: Stage 8 verifier logic

​

Next Steps

• Spartan: How sumchecks produce opening claims
• RAM Checking: Major source of opening claims
• Instruction Execution: Lookup table opening claims