> ## 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 Opening Proofs

> Learn how Jolt efficiently verifies polynomial evaluations via batched commitments

## Overview

**Opening proofs** verify that polynomial evaluations claimed during sumchecks are correct with respect to committed polynomials. Jolt uses **batched opening proofs** to aggregate hundreds of evaluation checks into a single proof, dramatically reducing proof size and verification time.

## Role in the Proving System

Opening proofs are the final stage of proving:

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

Jolt uses **accumulators** to collect opening claims during proving:

### Prover Accumulator

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

**Usage pattern**:

```rust theme={null}
// 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

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

**Usage pattern**:

```rust theme={null}
// During sumcheck stages:
accumulator.append_commitment(poly_id, point, commitment);

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

## Opening ID Structure

```rust theme={null}
pub enum OpeningId {
    Committed(CommittedPolynomial, SumcheckId),
    Virtual(VirtualPolynomial, SumcheckId),
    TrustedAdvice(SumcheckId),
    UntrustedAdvice(SumcheckId),
}
```

**Components**:

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

**Purpose**: Uniquely identify each opening claim for batching.

## Committed vs. Virtual Polynomials

### Committed Polynomials

**Definition**: Polynomials explicitly committed by prover.

**Examples**:

* `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

**Commitment**: Using Dory polynomial commitment scheme.

### Virtual Polynomials

**Definition**: Polynomials **derived** from committed polynomials (not directly committed).

**Examples**:

* `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)

**Opening**: Computed from committed openings (no separate commitment needed).

## Batching Strategy

Jolt batches all openings via **random linear combination**:

### 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

With overwhelming probability, if any individual opening is incorrect:

```
P_batch(r_batch) ≠ v_batch
```

due to random `α` preventing cancellation of errors.

## Opening Points

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

### Binding Order

**Big-endian** (`BIG_ENDIAN`):

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

**Little-endian** (`LITTLE_ENDIAN`):

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

**Why it matters**: Sumcheck binding order must match polynomial structure for correct evaluation.

## Dory Commitment Scheme

Jolt uses **Dory** polynomial commitment:

### 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

```rust theme={null}
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

Dory's batching is **native** (not via random linear combination):

```rust theme={null}
proof = Dory::batch_prove(
    polys: &[DensePolynomial<F>],
    points: &[Vec<F::Challenge>],
    evals: &[F],
)
```

This is even more efficient than generic batching (exploits Dory's structure).

## ZK Mode: Evaluation Commitments

In ZK mode, evaluations are **committed** (not revealed):

### Standard Mode

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

### ZK Mode

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

**Dory ZK opening**:

```rust theme={null}
Dory::prove_opening_zk(
    poly: &DensePolynomial<F>,
    point: &[F::Challenge],
    eval: F,  // Not revealed
) -> (y_com: Commitment, proof: OpeningProof)
```

**Verifier** checks `y_com` matches evaluation without learning `eval`.

## Stage 8: Opening Proof Generation

### Prover Side

```rust theme={null}
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

```rust theme={null}
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

**Stage 8 (Opening proofs)**:

* O(num\_openings · poly\_size · log(poly\_size)) field operations
* \~10-15% of total proving time
* Parallelized across polynomial groups

**Batching benefit**:

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

### Proof Size

**Per opening** (unbatched):

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

**Batched**:

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

### Verifier Time

**Stage 8 verification**:

* O(num\_openings · log(poly\_size)) field operations
* \~5-10ms for typical proofs
* Batching reduces constant factors

### Memory Usage

**Accumulator storage**:

* \~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](/architecture/spartan): How sumchecks produce opening claims
* [RAM Checking](/architecture/ram): Major source of opening claims
* [Instruction Execution](/architecture/instruction-execution): Lookup table opening claims