# Linear-Time Accumulation Schemes: WARP

## Why linear accumulation matters

Distributed systems often need to prove that many individual checks are all correct without re-examining every witness, that is the case for the application we target: post-quantum signature aggregation for the beam chain. Proof-carrying data (PCD) solves this, but until now its key sub-component—an **accumulation scheme**—forced the prover to do more than linear work.


The WARP protocol changes that: its prover runs in time proportional to the size of the data it really touches, while the verifier touches only a logarithmic fraction. A faster accumulation scheme speeds up every application that stacks many proofs together.

### How Incremental Verifiable Computation (IVC) connects

To understand why linear accumulation matters, it helps to first look at incremental verifiable computation (IVC), introduced by Val08.

An IVC protocol consists of two players:
* the prover $\mathbb{P}$, who incrementally computes and updates a result, and
* the verifier $\mathbb{V}$, who checks the final result efficiently.

At each step $t$, the prover:
* takes in the previous state $st_{t-1}$ and produces the next state $st_t$,
* generates a short proof $\sigma_t$ showing that $st_t$ was correctly derived.

This chain of proofs, called the **IVC proof**, ensures that the verifier only needs to check the final step $(st_t, \sigma_t)$ instead of re-executing the entire computation history. That’s crucial for scalability.


### Reductions: the modern approach

At the heart of modern proof systems lies the idea of **reductions** between relations.

We start with a relation $R$, where a prover $\mathbb{P}$ knows a witness $w$ proving that an instance $x$ satisfies $R$ (i.e., $(x, w) \in R$). Through interaction, the prover and verifier $\mathbb{V}$ produce:
* a new instance $x'$ and witness $w'$,
* and a proof $\pi$ showing that $(x', w')$ satisfies some simpler or reduced relation $R'$.

A good reduction ensures two key properties:
* **Completeness**: if the original pair was valid (in $R$), the reduced pair remains valid (in $R'$).
* **Soundness**: if $x$ didn’t come from the language $L(R)$ (i.e., no valid $w$ exists), then with high probability $x'$ also won’t belong to $L(R')$.

Formally, the language $L(R)$ is defined as:
$$
L(R) := \{x \mid \exists w \text{ such that } (x, w) \in R \}.
$$

These reductions let us break complex proof goals into simpler building blocks, chaining them together while tightly controlling error.

In WARP, reductions are implemented as **interactive oracle reductions (IORs)**, where the prover and verifier progressively transform hard-to-check relations into easier proximity or codeword claims, all while preserving soundness and efficiency.


## What an accumulation scheme does

An accumulation scheme is a method for compactly bundling many statements (claims) together. Specifically, the accumulator is split into two parts:
* $\text{acc} = (\text{acc}.\mathbb{x}, \text{acc}.\mathbb{w})$
* $\text{acc}.\mathbb{x}$: the instance part — short, public, and readable by the verifier.
* $\text{acc}.\mathbb{w}$: the witness part — long, private, and known only to the prover and the decider.

### How it works

Imagine you have a long list of instance–witness pairs $(x_i, w_i)$. Rather than store or verify all of them separately, we maintain a compact accumulator $\text{acc}$.

For each new pair:
* The prover runs $P_{\text{ACC}}$ to:
* Update the accumulator: $\text{acc} \to \text{acc}'$.
* Produce a short proof $\text{pf}$ explaining the update.

### What the verifier does

The verifier $V_{\text{ACC}}$:
* Only sees the public instance part $\text{acc}.\mathbb{x}$ (not the witness part).
* Checks whether the transition:
$$
(\text{acc}.\mathbb{x}, x, \text{acc}'.\mathbb{x}, \text{pf})
$$
is valid — meaning, does the proof $\text{pf}$ justify going from the old accumulator state to the new one for this instance?

Importantly the verifier only operates on the instance view; it never touches $\text{acc}.\mathbb{w}$.

### What the decider does

The decider $D_{\text{ACC}}$:

* Eventually opens and inspects the **full accumulator** $(\text{acc}.\mathbb{x}, \text{acc}.\mathbb{w})$.
* Outputs a single bit: ✅ accept or ❌ reject.

This final decision ensures that all accumulated claims are valid — not just the most recent transition.

### Core security guarantee

The key property is called knowledge soundness:
* Anyone who convinces the verifier of a valid update must already know valid witnesses for every instance stored in the accumulator.
* This holds even if the verifier only ever sees the short, public part.

### Why the split matters

This two-part design is essential for efficiency:
* The verifier stays lightweight by only handling the short instance part.
* The prover and decider manage the heavy witness part, offloading the expensive operations.

This is the foundation that WARP builds on.


## Polynomial equation satisfiability (PESAT)

At the heart of WARP lies the problem of **polynomial equation satisfiability** (PESAT). This asks: given a system of $M$ polynomial equations ${\hat{p}_i(x, w) = 0}$ over a field $\mathbb{F}$, can we find an assignment of variables that satisfies them all?

Formally, the PESAT relation is:

$$
R_{\text{PESAT}} = \left\{ (x, w) \,\middle|\, x \in \mathbb{F}^{N - k},\, w \in \mathbb{F}^k,\, \forall i \in [M]: \hat{p}_i(x, w) = 0 \right\},
$$

where:
* $x$ holds the public (instance) variables,
* $w$ holds the private (witness) variables,
* each $\hat{p}_i$ is a polynomial over all $N$ variables.

This general framework underlies well-known models like R1CS, CCS, and GR1CS. For example, in R1CS, the polynomial constraints are bilinear:

$$
\mathbf{A}[x, w] \cdot \mathbf{B}[x, w] = \mathbf{C}[x, w],
$$

where $\mathbf{A}, \mathbf{B}, \mathbf{C}$ are matrices over $\mathbb{F}$.

PESAT captures these structured relations, wrapping them into a unified polynomial system. Solving PESAT means finding a witness $w$ such that all polynomial checks pass.


## WARP in one sentence

WARP is the first accumulation scheme whose prover runs in linear time and whose verifier runs in logarithmic time, while staying hash-based and plausibly post-quantum.

\begin{equation}
\text{Prover time} = O\bigl(\ell\cdot|p|+\lambda\log k\bigr),\quad
\text{Verifier time} = O\bigl(\ell\cdot(\log N+\log M+\lambda)\bigr)
\end{equation}

- $|p|$ is the size of the polynomial system,
- $\ell$ is the number of items being accumulated at once,
- $k$ is the witness length,
- $N$ and $M$ are, respectively, the variable and constraint counts in the system,
- $\lambda$ is the security parameter.

The protocol retains soundness error at most $2^{-\lambda}$ provided the field size is large enough.


## How WARP reaches linear time

Earlier accumulation schemes fell into two broad categories:
1. **Group-based** (e.g., Pedersen or KZG commitments): the verifier is tiny, but the prover pays a super-linear cost due to heavy multiscalar multiplications.
2. **Lattice-based**: potentially post-quantum, but the need to tightly control noise growth introduces extra overhead.

A recent third direction uses hash commitments and Reed–Solomon codes, achieving quasi-linear time. WARP improves on this by switching to *any* linear code with fast encoding—such as expander codes or repeat–accumulate–accumulate codes—and crucially, achieves true linear prover time.

A key ingredient here is that WARP moves away from univariate representations (as used in BMNW24) to multivariate ones, which avoids the need for costly quotienting steps during the sumcheck. Combined with the switch from Reed–Solomon to general linear codes, this lets WARP fully unlock the efficiency of linear-time encodable codes.

The key technical innovation is a new **interactive oracle reduction of proximity (IOR)**. This connects three layers:
* an IOR,
* compiled into an accumulation scheme,
* which powers the final PCD system.

WARP’s IORs are designed to work with any linear code over any field, inheriting the code’s efficiency. With a linear-time encodable code, the prover runs in linear time. The verifier, on the other hand, performs only $O(\log n)$ random queries, staying lightweight.

Bonus features come built-in:
* **Straightline extraction**: works for any linear code, even without efficient decoding.
* **Out-of-domain sampling**: generalizes to any linear code, forcing the prover to commit to a single codeword.

This careful layering is what lets WARP break past the quasi-linear barrier and deliver the first hash-based, plausibly post-quantum accumulation scheme with both linear prover time and logarithmic verifier time.


## Key ideas in more detail

### Out-of-domain sampling for every code

Each codeword $u \in C$ can be extended beyond its $n$ positions to all of $F^{\log n}$ using its multilinear polynomial $\hat{u}$, which matches $u$ on the Boolean hypercube ${0,1}^{\log n} \cong [n]$.

In simple terms: the linear code $C : \mathbb{F}^k \to \mathbb{F}^n$ maps messages to codewords. We work with a function $f : [n] \to \mathbb{F}$, which might or might not match some codeword $u \in C$. The out-of-domain sampling test checks whether a close codeword exists by using random linear constraints derived from the multilinear extension — allowing the verifier to meaningfully query the prover even outside the original code positions.

Specifically, the verifier picks a random point $\tau \in F^{\log n} \setminus {0,1}^{\log n}$ and asks for $\sigma = \hat{u}(\tau)$. Since $\hat{u} - \hat{v}$ is a nonzero polynomial of degree $\log n$, two distinct codewords $u, v$ will match at a random $\tau$ with probability at most $\log n / |F|$.

By applying a union bound over the small list of codewords within distance $\delta n$, this collision probability becomes negligible — effectively forcing the prover to lock in one specific codeword before further checks proceed.

### Twin constraints

The prover’s codeword $u \in C$ needs to satisfy two different types of checks at the same time — that’s why we call them “twin” constraints.

1. **Point evaluation check**
The verifier picks a random point $\alpha \in F^{\log n}$ and asks: does the multilinear extension $\hat{u}$ evaluate to a target value $\mu$ at that point? In other words:
$$
\hat{u}(\alpha) = \mu.
$$
2. **Bundled PESAT check**
The original relation (defining what makes $u$ valid) comes from $M$ polynomial conditions on the message $Z = C^{-1}(u)$. Instead of checking each one separately, we bundle them into a **single combined polynomial**:
$$
P_b(Y, Z) = \sum_{i=0}^{M-1} \mathrm{eq}(Y, i) \, p_i(Z),
$$
where $Y$ is the selector and $p_i(Z)$ are the individual conditions.
The verifier picks another random point $\beta$ and checks:
$$
P_b(\beta, Z) = \eta.
$$

Here’s the key idea: both the point evaluation and the bundled polynomial check are packed into a single constrained code:
$$
C[(\alpha, \mu), (P_b, \beta, \eta)].
$$

This means any later step — like reducing or batching — only needs to preserve the code’s distance properties, and it will automatically preserve **both** constraints together. That’s why they’re called “twin”: they’re locked together inside the same code framework.

### Codeword batching without quotienting

Given two functions $f_0,f_1$ and random scalars $\gamma_0,\gamma_1$, the prover sends their linear combination $g=\gamma_0f_0+\gamma_1f_1$. A carefully chosen set of in-domain points ensures that if either input was far from the code, $g$ will also be far with high probability. Because the verifier touches only $O(\lambda)$ field locations, the prover’s extra cost is $O(\lambda\log n)$, which keeps the whole step linear.

### Round-by-round extraction via erasures

In the state-restoration game, the extractor eventually gets two key pieces:
* the prover’s oracle $f$, and
* a valid codeword $u \in C$ that the protocol ensures is part of the final accumulator.

The extractor identifies the agreement set:
$$
S = \{ i \mid f_i = u_i \},
$$

which covers at least $(1 - \delta) n$ positions. It then treats the remaining positions as erasures and uses the code’s generator matrix to solve for the missing entries.

Crucially, erasure correction only requires solving a small linear system — costing just $O(n)$ field operations — and works efficiently for any linear code. This neatly avoids needing a full (and often much more expensive) list decoder.

## Preliminaries and notations

This section fixes language, notation, and a few basic facts that WARP will use later.

### Relations and distance from a relation

A *relation* $R$ is a set of quadruples $(\mathbb{i},\mathbb{x},\mathbb{y},\mathbb{w})$.
- $\mathbb{i}$: an index describing the problem,
- $\mathbb{x}$: the public instance,
- $\mathbb{y}$: a large oracle string,
- $\mathbb{w}$: a witness.

The language of valid statements is
\begin{equation}
L(R)=\{(\mathbb{i},\mathbb{x},\mathbb{y})\mid\exists \mathbb{w}:(\mathbb{i},\mathbb{x},\mathbb{y}, \mathbb{w})\in R\}.
\end{equation}

For parallel work we lift $R$ to a multi-instance relation
\begin{equation}
R^{\ell}=\bigl\{(\mathbb{i},(\mathbb{x}_1,\dots,\mathbb{x}_\ell),(\mathbb{y}_1,\dots,\mathbb{y}_\ell),(\mathbb{w}_1,\dots,\mathbb{w}_\ell))\mid
\forall i\in[\ell]:(\mathbb{i},\mathbb{x}_j,\mathbb{y}_j,\mathbb{w}_j)\in R\bigr\}.
\end{equation}

We measure how far a statement sits from $R$ using an *oracle view* $\pi_R(\mathbb{i},\mathbb{x},\mathbb{y})$ (usually we just take $\mathbb{y}$ itself). The distance is
\begin{equation}
\Delta_R(\mathbb{i},\mathbb{x},\mathbb{y})=\Delta\bigl(\pi_R(\mathbb{i},\mathbb{x},\mathbb{y}),\Pi_R(\mathbb{i},\mathbb{x})\bigr),
\end{equation}

where $\Pi_R(\mathbb{i},\mathbb{x})$ collects all honest oracles for $(\mathbb{i},\mathbb{x})$.

### Interactive oracle reductions (IORs)

An interactive oracle reduction (IOR) reduces the task of proving that an instance $\mathbb{x}$ belongs to a relation $\mathbb{R}$ to the task of proving that a new instance $\mathbb{x}'$ belongs to a (simpler) relation $\mathbb{R}'$, through an interactive protocol between the prover $\mathbb{P}$ and verifier $\mathbb{V}$.

In an IOR:
* The prover holds inputs $(\mathbb{x}, \mathbb{y}, \mathbb{w})$ satisfying $\mathbb{R}$.
* The verifier and prover interact over several rounds, exchanging oracle messages $\Pi_1, \Pi_2, \dots$.
* The verifier only reads small, random parts of these oracles, treating them like black boxes.
* At the end, the verifier outputs a new (simpler) statement $(\mathbb{x}', \mathbb{y}')$, and the prover outputs a new witness $\mathbb{w}'$, together forming $(\mathbb{x}', \mathbb{y}', \mathbb{w}')$ for the simpler relation $\mathbb{R}'$.

The guarantees are:
* **Completeness**: if $(\mathbb{x}, \mathbb{y}, \mathbb{w}) \in \mathbb{R}$, then the reduced output satisfies $(\mathbb{x}', \mathbb{y}', \mathbb{w}') \in \mathbb{R}'$.
* **Soundness (distance preservation)**: if the oracle $\mathbb{y}$ is $\delta$-far from any valid solution in $\mathbb{L}_{\mathbb{x}}(\mathbb{R})$, then with high probability, the reduced oracle $\mathbb{y}'$ remains $\delta$-far from $\mathbb{L}_{\mathbb{x}'}(\mathbb{R}')$.

Here, $\mathbb{L}_{\mathbb{x}}(\mathbb{R})$ denotes the set of oracle views $\mathbb{y}$ for which there exists a witness $\mathbb{w}$ such that $(\mathbb{x}, \mathbb{y}, \mathbb{w}) \in \mathbb{R}$.

We track the efficiency of an IOR using:
* $k$: number of rounds,
* $l$: proof length,
* $q_{\mathbb{y}}, q_{\pi}$: number of oracle queries,
* $r$: verifier randomness,
* $pt, vt$: algebraic time (field operations) for the prover and verifier.

In WARP, carefully designed IORs allow compressing complex proof problems into compact proximity checks — crucially, this works without the prover ever fully revealing the oracles, keeping prover costs linear and verifier queries minimal.


### Constrained codes

In WARP, a central object is the concept of a **constrained code**, which refines a linear code $C \subseteq \mathbb{F}^n$ by adding extra algebraic conditions.

Formally, given:
* a linear code $C$ over $\mathbb{F}$,
* and an algebraic constraint $\Phi : \mathbb{F}^n \to {0, 1}$ (typically low-degree),

we define the constrained code:
\begin{equation}
C_\Phi := { u \in C \mid \Phi(u) = 1 }.
\end{equation}

This selects only those codewords that satisfy the constraint $\Phi$.

For example, when handling PESAT (Polynomial Equation SATisfiability) instances, we start with polynomials $\hat{p}_i(x, w)$, where $x \in \mathbb{F}^{N - k}$ (instance) and $w \in \mathbb{F}^k$ (witness), and bundle all $M$ equations into a single bundled polynomial:
\begin{equation}
\mathbb{P}_b(\tau, (x, w)) := \sum_{i} \text{eq}(\tau, i) \cdot \hat{p}_i(x, w),
\end{equation}
where $\tau$ is a random point in $\mathbb{F}^{\log M}$.

This lets us enforce all constraints via a single condition $\Phi(u) = [ \mathbb{P}_b(\tau, C^{-1}(u)) = 0 ]$, where $C^{-1}(u)$ decodes the message from the codeword $u$.

In practice, the prover $\mathbb{P}$ sends a codeword $f$ combining:
* prior codewords $f_1, f_2 \in C_{\Phi_1}, C_{\Phi_2}$,
* random coefficients,
* and produces a mixed word $f \in C_\Phi$.

The verifier $\mathbb{V}$ checks this new combined word against the new constraint $\Phi$.

This constrained accumulation allows WARP to:
* work over any linear code (not just Reed–Solomon),
* handle arbitrary algebraic constraints $\Phi$,
* and propagate proof obligations in a compact, composable way.

Importantly, the verifier only needs to query small random parts, while the prover only performs fast, linear-time algebraic operations.


### Zero-evaders and codes

A *zero-evader* is a short function $ZE$ such that inner products $\langle ZE(\rho),v\rangle$ almost never vanish unless $v=0$. Lemma 3.4 builds one from the generator matrix of any linear code; the failure chance is only $\log n/|F|$.

We use linear codes $C:F^{k}\to F^{n}$, always with $n$ a power of two.
Important parameters:

* minimum relative distance $\delta(C)$,
* encoding cost $\mathrm{enc}_C$,
* erasure-correction cost $\mathrm{ecor}_C$ (always $O(n^3)$ by a textbook algorithm, and often better).

Erasure correction will be vital: given a word that agrees with some codeword on at least $(1-\delta(C))n$ positions, we can recover the exact codeword by solving a linear system.

For list decoding we write
\begin{equation}
\Lambda(C,f,\delta)=\{u\in C\mid\Delta(f,u)\le\delta\},
\end{equation}

and denote the worst-case list size by $|\Lambda(C,\delta)|$.

Interleaving $m$ codewords entrywise gives a new code $C^m$ whose list size grows only combinatorially; Lemma 3.12 states the exact bound.

### Out-of-Domain sampling in general codes


#### What is the purpose?

To summarize, Out-of-domain (OOD) sampling is a technique that allows the verifier to “probe” properties of a codeword even when it’s outside the code’s natural domain — effectively forcing the prover to commit to a unique valid codeword.

This works using a special short vector called a zero-evader:
* The zero-evader $ZE: D \to \mathbb{F}^k$ outputs a random vector $z$.
* With high probability, this random $z$ will not be orthogonal to any nonzero message.

In other words, unless the prover gives a consistent codeword, the random probes will detect mismatches with overwhelming probability.

#### How does the verifier use it?

1. The verifier draws a random seed $\rho$.
2. Computes:
$$
z = ZE(\rho)
$$
3. Asks the prover to provide the single inner product:
$$
\langle z, C^{-1}(u) \rangle
$$
where $C^{-1}(u)$ is the preimage (or decoding) of $u$ under the code $C$.

#### Why does it work?

Because each random probe $z$ interacts differently with each possible codeword, if the prover tries to cheat (by “pretending” to be close to two different codewords), the mismatch will almost certainly be detected.

Formally (from Lemma 3.13):

* If you run $s$ independent OOD probes, the probability that two distinct codewords inside the same $\delta$-ball agree on all probes is bounded by:
$$
\frac{|\Lambda(C, \delta)|^2}{2} \cdot \varepsilon_{\text{zero}}^s
$$
* By setting:
$$
s \geq \frac{\lambda}{\log(1 / \varepsilon_{\text{zero}})}
$$
you ensure that the collision probability drops below $2^{-\lambda}$, forcing the prover to effectively commit to a unique codeword.

#### Insights from the image

The image highlights two important differences in OOD sampling approaches:

- **For general codes** (green box):
* We construct $z$ using the multilinear extension of the code’s generator matrix $\hat{G}(\tau, b)$, which makes the sampling batch-friendly.
* The verifier checks:
$$
\langle z, C^{-1}(u) \rangle = \hat{u}(\tau)
$$
This allows the protocol to scale efficiently even in batched settings.

- **For Reed–Solomon (RS) codes** (yellow box):
* Traditional sampling takes $\tau \in \mathbb{F}$ and builds $z = (1, \tau, \tau^2, \ldots)$.
* This is not batch-friendly, making it harder to scale when verifying many statements at once.

#### Why is batch-friendliness important?

Batch-friendly OOD sampling allows the verifier to efficiently run checks on many codewords simultaneously, reducing both time and communication costs.

By contrast, older approaches (like those used in RS codes) force the verifier to perform independent, costly checks for each codeword, which does not scale well.

### Mutual correlated agreement

Take $\ell$ words $f_1,\dots,f_\ell:[n]\to F$ and draw random coefficients $\gamma=(\gamma_1,\dots,\gamma_\ell)$ from a *proximity generator* PG. The mixed word is
\begin{equation}
g=\sum_{j=1}^{\ell}\gamma_j\,f_j.
\end{equation}

For a *mutual correlated* generator two things happen with high probability (outside an error $\mathrm{err}_{\text{PG}}$).

1. **Shared agreement set.**

There is a large set $S\subseteq[n]$ (at least $(1-\delta_{\text{PG}})n$ points) such that $f_j(S)=u_j(S)$ for some codewords $u_j\in C$ *and simultaneously* $g(S)=u_{\text{mix}}(S)$ where $u_{\text{mix}}=\sum_j\gamma_j u_j$. So the places where each $f_j$ agrees with its nearest codeword are exactly the places where the mix agrees with the mixed codeword.

2. **No hidden agreement.**
If a position is outside $S$ for one of the $f_j$, it is also outside for $g$; the generator does not create new accidental matches.

This synchrony lets the extractor recover the mixed codeword first, mark $[n]\setminus S$ as erasures, and then fill in each $u_j$ separately—all in linear time. The guarantee holds for every linear code, and the radius–error trade-off is especially good for Reed–Solomon and modern linear-time encodable expander codes.

## Round-by-round knowledge soundness (RBR-KS)

An IOR must stay secure even if the verifier’s random coins are later reconstructed from a hash (Fiat–Shamir). To formalise this we give each *partial* transcript its own “knowledge state’’ bit that says whether a witness can already be extracted.

* **Knowledge state function.**
A function
$$
\text{KState}_{\delta}\bigl(i,x,y,\text{tr},w\bigr)\in\{0,1\}
$$

depends on the current transcript tr, a candidate witness $w$, and a proximity bound $\delta$.
It must satisfy three easy syntactic rules (empty transcript, prover moves never help, full transcript) that exactly mirror the usual RBR definition, except that the witness $w$ travels along as extra input.

* **Extractor for each verifier move.**
At the start of round \$i\$ the verifier chooses its random message $\rho_i$.
A deterministic extractor

$$
E^{\text{rbr}}_i(i,x,y,\text{tr}\parallel\rho_i,w)
$$

runs in a prescribed time budget and outputs the witness that *ought* to make KState flip to 1. The RBR-KS error $\varepsilon_i$ is the probability (over $\rho_i$) that the state flips despite the extractor failing.

This weaker—but handier—form of RBR-KS is enough: Appendix A shows that
$$
\text{RBR-KS}\;+\;\text{Fiat–Shamir}\;\Longrightarrow\;\text{straightline state-restoration KS}.
$$

## WARP: the accumulation scheme

WARP turns any linear code $C:F^{k}\to F^{n}$ with erasure correction into an unbounded accumulation scheme for the PESAT relation. The construction glues together the three IORs we met earlier (Sections 6–8) and wraps them with:

* a Merkle tree commitment MT (for long oracles) and
* a sponge-style Fiat–Shamir PRF FS (for non-interactive randomness).

## Protocol overview

This protocol is designed to efficiently verify whether two functions, $f_1$ and $f_2$, belong to their respective structured code families. Instead of checking each one fully and separately, it cleverly combines the checks in two streamlined phases.


### Phase 1: Batch phase

The batch phase sets up the foundation: we want to check whether two functions, $f_1$ and $f_2$, each belong to their respective structured code families.


#### Purpose

We aim to check:
* Does $f_1$ belong to the code family $\mathcal{C}_{\Phi_1}$?
* Does $f_2$ belong to the code family $\mathcal{C}_{\Phi_2}$?

This is written as:
$$
f_1 \in \mathcal{C}_{\Phi_1} \quad \text{and} \quad f_2 \in \mathcal{C}_{\Phi_2}
$$

#### How does it work?

* The prover $P_{\text{batch}}$ provides proofs or evidence supporting these membership claims.
* The verifier $V_{\text{batch}}$ uses a batch verification method that dramatically reduces the number of necessary queries: it only needs around $\lambda$ random queries (where $\lambda$ is the security parameter).

This is where the key idea from the image comes in:

> **Use mutual correlated agreement to perform “folding” reductions over the oracles.**

Rather than separately checking both oracles ($f_1$, $f_2$) in full, the verifier leverages their structure to compress the verification effort.

#### Visual breakdown (see image)

* The two functions $f_1, f_2$ are provided as oracles (black-box functions).
* The verifier $V_{\text{batch}}$, armed with knowledge of $\Phi_1, \Phi_2$, performs a folding reduction — a standard approach often paired with sumcheck techniques — to simplify the checking task.
* The result is a smaller, aggregated proof object $\hat{h}$ (highlighted in the image).

#### Why is this efficient?

Normally, proving each statement individually would require many rounds of querying and interaction. Instead, by batching and using folding reductions, we:
- Reduce the number of queries,
- Save on communication,
- Maintain strong soundness guarantees, thanks to the proximity gap for the code family $\mathcal{C}$.

#### What happens at the end?

Once the verifier is satisfied with the batch check, it sends back:
* A random scalar $\gamma$, drawn freshly for the next phase.

This scalar is crucial because it enables the switch phase, where the verifier will check a single combined function:
$$
f_1 + \gamma \cdot f_2 \in \mathcal{C}_{\Phi'}
$$

This prepares the system to collapse two separate checks into one — making the overall protocol even more efficient.

### Phase 2: Switch phase


#### Purpose

At this stage, instead of verifying $f_1$ and $f_2$ separately, we combine them into a single function:
$$
f = f_1 + \gamma \cdot f_2
$$

where $\gamma$ is the random scalar the verifier provided at the end of the batch phase.

The goal now is:

* To check whether this new combined function $f$ belongs to the code family $\mathcal{C}_{\Phi'}$.

#### What’s the key idea?
As shown in the image, the verifier uses an arithmetization trick:

* Treat the function $f$ (originally defined over indices $[n]$) as its multilinear extension:
$$
\hat{f}: \mathbb{F}^{\log n} \to \mathbb{F}
$$

This means we interpret the index $i$ in binary ($\text{bin}(i)$) and evaluate $\hat{f}$ at that point:
$$
f[i] = \hat{f}(\text{bin}(i))
$$

This lets the verifier work algebraically over the function, making the verification compatible with powerful algebraic techniques.

#### Who does what?

* The prover $P_{\text{switch}}$ provides the combined oracle $f$ (think of it as handing over a new black box the verifier can query).
* The verifier $V_{\text{switch}}$ performs the following:
1. Selects random indices $i$ from the domain $[n]$.
2. Computes:
$$
\alpha = f_1[i] + \gamma \cdot f_2[i]
$$
3. Checks if:
$$
f[i] = \alpha
$$
4. Verifies that $f$ as a whole satisfies the code properties under $\mathcal{C}_{\Phi'}$.

This process is repeated $O(\lambda)$ times (where $\lambda$ is the security parameter) to amplify soundness, making sure a cheating prover is caught with high probability.

#### Why is this smart and efficient?

- Instead of running two separate code checks, we collapse the verification into a single combined check.
- The use of random sampling plus algebraic folding keeps communication and query complexity low.
- The verifier focuses only on batch-friendly, in-domain constraints that scale efficiently.

At the end, the verifier essentially checks:
* Does $f$ belong to $\mathcal{C}_{\Phi'}$?
* Are the pointwise values of $f$ consistent with the folded combination $f_1 + \gamma f_2$?

This sets up the final confirmation phase where only the combined result matters, reducing complexity across the entire protocol.

### Summary of benefits for the protocol overall

- **Batch phase** → Only needs a few queries (proportional to $\lambda$).
- **Switch phase** → Only one combined oracle is transmitted.
- **Overall** → Saves time and reduces communication by collapsing two proofs into one.

## Bonus: Straightline extraction for every linear code


### The big goal

We want to design extractors that can pull out a witness (the prover’s hidden information) directly and efficiently from a proof transcript — without needing to rewind the prover or rerun the protocol.

This is called:
* **Straightline extraction** — the extractor runs forward, using only the messages and random oracle traces, without black-box access to the prover or repeated interactions.

### What’s the challenge?

In many prior systems, straightline extraction depends on:
* The underlying error-correcting code $C$ having an efficient error-tolerant decoder.

For example:
* Reed–Solomon codes work well because they can be error-decoded efficiently.
* But many other practically interesting linear codes don’t have known efficient error-tolerant decoders.

Without such decoders, previous work fell back on:
* **Rewinding extractors**, which are slower, less robust, and introduce worse error guarantees.

### What’s the contribution here?

This work introduces a new notion of straightline extraction — one that directly targets the state-restoration game and still implies straightline state-restoration knowledge soundness (ks).

This is notable because:
* Prior work could only establish this soundness through the stronger and more restrictive notion of round-by-round knowledge soundness.
* By contrast, the new approach allows proving straightline extraction even without relying on round-by-round guarantees.

Crucially, it works for any linear code, even if it lacks an efficient error-tolerant decoder. How?
* By using erasure correction (which is always efficient for linear codes) and
* Exploiting the protocol’s internal structure, particularly a property called mutual correlated agreement.

### How does the extractor work?

The extractor operates inside the formal security setting of the state-restoration game:
* The adversary (cheating prover) interacts with a random oracle and tries to convince the verifier.
* The extractor receives:
* The prover’s messages,
* The verifier’s random challenges,
* And importantly, a valid witness $w'$ for the reduced (folded) problem.

The clever insight is:

* Even if the prover’s oracles (like functions $f_i$) are slightly corrupted, the mutual correlated agreement ensures that the extractor can find enough agreement locations (good indices) where the corrupted function still matches a nearby codeword.

Then:

* By erasure correcting just on these agreed locations (ignoring the bad parts), the extractor efficiently recovers the clean codeword, and thus the original witness $w$.

This works because every linear code has an efficient erasure correction algorithm (solving a simple linear system), even when no efficient error decoder exists.

### Why is this faster?

Even for codes that do have error-tolerant decoders, erasure correction is often much faster:

* Error-tolerant decoders need to return all close codewords — which can take time proportional to the number of such codewords.
* Erasure correction, in contrast, just solves for the unique valid codeword given the surviving (good) positions, and typically runs in near-linear time.

This makes the overall accumulation scheme more efficient, practical, and broadly applicable.