# 𖦹 WARP 𖦹

WARP is an accumulation-scheme with a linear-time prover. This bound on the prover's running time is obtained from choosing a linear-time encoding linear code scheme (e.g. Brakedown's expander or Blaze's RAA codes) and careful bookeeping across 4 different Interactive Oracle Reduction (IOR) protocols. An IOR is a generalization of Interactive Oracle Proofs (IOP) where, instead of a single decision bit, the verifier outputs a new instance when accepting (or correspondingly rejecting). WARP is built out of four different IORs, which when reviewed independently and then combined, make the whole WARP construction relatively straightforward. I rewiew each of them here.

## (construction 5.10) IOR (1) from $\mathcal{R}_{\circ}(\mathbb{F})$ to $\mathcal{R}_{\mathcal{c}, 0}$

### Overview

The relation $\mathcal{R}_{\circ}(\mathbb{F})$ is all tuples $(\mathbb{i}, \mathbb{x}, \mathbb{w}) = ((\hat{\mathbf{p}}, M, N, k), x, w)$ such that $\hat{\mathbf{p}}(x, w) = 0$, where $\hat{\mathbf{p}}$ consists in $M$ polynomials in $N$ variables.

Set $z = (x, w)$. The zero-bundling of $\hat{\mathbf{p}}$ is:

$$
\hat{P}(\tau, z) = \Sigma_{i \in \log M} eq(\tau, i) \cdot \hat{p}_i(z)
$$

The $M$ constraints are reduced into a single polynomial. Using the well-known Ore–DeMillo–Lipton–Schwartz–Zippel lemma, the probability that a random point is a root of this polynomial is very small.

The multi-evaluation relation $\mathcal{R}_{\mathcal{c}, r}$ is all triples $(\mathbb{i}, \mathbb{x}, \mathbb{w}) = ((\hat{\mathbf{p}}, M, N, k), ((\mathbf{\alpha_i}, \mu_i)_{i \in [r]}, \mathbf{\beta}, \eta), f)$ such that $\forall i \in [r], \hat{f}(\mathbf{\alpha_i}) = \mu_i$ and $\hat{P}(\mathbf{\beta}, \mathcal{C}^{-1}(f)) = \eta$

WARP calls $f$ a "twin constrained" codeword since it is constrained with respect to its multilinear evaluations and its evaluation on $\hat{P}$. That is, $\mathcal{R}_{\mathcal{c}, 0}$ is the relation for which such codewords have no specified multilinear constraint.

Construction 5.10 reduces an instance-witness tuple satisfying a system of polynomial equations to a codeword verifying no evaluation claim but one evaluation claim over a zero-bundled version of this system of polynomial equations (aka a twin constraint).

Since all subsequent IORs are for $\mathcal{R}_{\mathcal{c}, 1}$, when runnning this IOR the prover can just provide his initial claim with any evaluation point, which doesn't need to be chosen at random. That is, the prover can just provide $0$ as an evaluation point, which will be the case in WARP's final construction.

From now on, set $R_{\mathcal{C}} := R_{\mathcal{C}, 1}$

## (construction 6.3) IOR (2) from $\mathcal{R}^{l}_{\mathcal{c}}$ to $\mathcal{R}_{\mathcal{c}, r, l}$

### Overview

The pseudo-batching accumulation relation $\mathcal{R}_{\mathcal{c}, r, l}$ is all triples $(\mathbb{i}, \mathbb{x}, \mathbb{w}) = ((\hat{\mathbf{p}}, M, N, k), (\mathbf{\gamma}, (\mathbf{\alpha_i}, \mu_i)_{i \in [r]}, \mathbf{\beta}, \eta), u)$ such that $u = \Sigma_{i \in [l]} = \gamma_i \cdot f_i$ where $f_i$ is a codeword from a tuple $(\mathbb{i}, \mathbb{x}, \mathbb{w}) \in \mathcal{R}_{\mathcal{c}}$.

This IOR computes the linear combination of $l$ single-evaluation, twin-constrained, codewords. This linear combination of $l$ codewords results into one with r multilinear evaluation points. We call this pseudo/twin-constraints batching.

Lemma 6.4 shows that prover can be implemented to perform $O(l \cdot (n + d \cdot (|\hat{\mathbf{p}}| + M)))$ field operations.

## (construction 7.2) IOR (3) from $\mathcal{R}_{\mathcal{c}, r, l}$ to $\mathcal{R}_{\mathcal{c}, r + s + t}$

### Overview

This IOR reduces the tuple $(\mathbb{i}, \mathbb{x}, \mathbb{w}) = ((\hat{\mathbf{p}}, M, N, k), (\mathbf{\gamma}, (\mathbf{\alpha_i}, \mu_i)_{i \in [r]}, \mathbf{\beta}, \eta), u) \in \mathcal{C}_{c, r, l}$ to $(\mathbb{i}, \mathbb{x}, \mathbb{w}) = ((\hat{\mathbf{p}}, M, N, k), ((\mathbf{\alpha_i}, \mu_i)_{i \in [r + s + t]}, \mathbf{\beta}, \eta), f)$. That is, it trades $\gamma$ and the linear combination of $l$ codewords for a single codeword equipped with $s + t$ multilinear evaluation claims: this is batching $l$ codewords into a unique one.

## (construction 8.2) IOR (4) from $\mathcal{R}_{\mathcal{c}, r + s + t}$ to $\mathcal{R}_{\mathcal{c}, 1}$

### Overview

Reduces the tuple $(\mathbb{i}, \mathbb{x}, \mathbb{w}) = ((\hat{\mathbf{p}}, M, N, k), ((\mathbf{\alpha_i}, \mu_i)_{i \in [r + s + t]}, \mathbf{\beta}, \eta), f)$ to $(\mathbb{i}, \mathbb{x}, \mathbb{w}) = ((\hat{\mathbf{p}}, M, N, k), ((\mathbf{\alpha}, \mu), \mathbf{\beta}, \eta), f)$. We got rid of the $r + s + t$ multilinear constraints to end up with a single one. Idea is to run sumcheck over the linear combinations of the $r + s + t$ multilinear evaluation claims (aka multilinear constraints batching).

According to lemma 8.3, the prover should run in $O(\max \{ 1, s\} \cdot n + t \cdot \log n)$ field operations.

## 𖦹 WARP 𖦹

Combines construction 6.3, 7.2 and 8.2 to obtain an IOR from $\mathcal{R}^{l}_{\mathcal{c}}$ to $\mathcal{R}_{\mathcal{c}}$.

WARP is built from using the FS transformation and a Merkle Commitment scheme on construction 9.4 to obtain an non-interative IOR in the ROM from $\mathcal{R}^{l_1}_{\circ}(\mathbb{F}) \times \mathcal{R}^{l_2}_{\mathcal{c}}$ to $R_{\mathcal{c}}$.

WARP will start with $l_1$ instance-witness tuples satisfying a system of polynomial equations $\hat{\mathbf{p}}$ and $l_2$ codewords (say previously accumulated ones) verifying a single multilinear evaluation and accumulates both into a single tuple in $R_{\mathcal{c}}$

## Remarks

- In [2025/055](https://eprint.iacr.org/2025/055.pdf), a variant of XMSS signatures is used. An implementation of XMSS signatures can be found [here](https://github.com/b-wagn/hash-sig) and the corresponding AIR [here (?)](https://github.com/han0110/hash-sig-agg/blob/main/crates/hash-sig-agg/src/air/mod.rs#L40). The issue is that the corresponding AIR is built from plonky3 and we would like to avoid having implementing the XMSS signature scheme using arkworks. However, [2025/055](https://eprint.iacr.org/2025/055.pdf) notes that *Assuming that verifying a single signature requires approximately 160 hash operations (or Poseidon2 permutations) [...] we estimate that aggregating up to 10,000 signatures [would require] to prove approximately $1.75 \cdot 10^6$ hashes per second*. Thus, a good first benchmark would be to run WARP on a Poseidon2 hash chaining task.

## Resources

- [Plonky3 multilinear utils](https://github.com/Plonky3/Plonky3/tree/main/multilinear-util)
- [nimue](https://github.com/arkworks-rs/spongefish)
- [WHIR multilinear poly routines](https://github.com/WizardOfMenlo/whir/blob/main/src/poly_utils/multilinear.rs)