# WHIR: Reed–Solomon Proximity Testing with Super-Fast Verification

Inspired by paper and slides (images) from Giacomo Fenzi

## Introduction

**WHIR** is a new cryptographic protocol that drastically speeds up verification in interactive proofs. It achieves this by offering a *super-efficient* IOP of proximity for constrained Reed–Solomon codes. Unlike existing protocols such as FRI, STIR, or BaseFold, WHIR enables verification in just a few hundred microseconds—orders of magnitude faster than traditional approaches that take several milliseconds or more.

At its core, WHIR enables fast and succinct proofs for statements expressed via *polynomial IOPs* (poly-IOPs). These are interactive protocols where the prover's messages are evaluations of low-degree polynomials over a finite field. Poly-IOPs are widely used to construct SNARGs (Succinct Non-interactive Arguments), which are cryptographic proofs that are short and easy to verify. WHIR significantly improves this landscape by reducing the verifier time without sacrificing prover efficiency or increasing proof size.

### Context: SNARGs and Poly-IOPs

SNARGs are compact proofs used in many applications, from blockchain to cloud computing, where both proof size and verification time matter. A common way to build SNARGs is through poly-IOPs, where the prover is restricted to polynomial messages, and then compile these into SNARGs using polynomial commitment schemes like KZG or inner-product-based schemes. This pipeline has led to highly efficient SNARG systems.


Another prominent method uses *hash-based SNARGs*, which start from poly-IOPs and compile them via the BCS transformation. These only rely on random oracles (i.e., hash functions), and offer several advantages:
- Transparent setup: just pick a hash function.
- Post-quantum security: secure in the quantum random oracle model.
- Fast prover performance: enabled by working over small finite fields.

However, hash-based SNARGs still suffer from relatively slow verifiers, especially when the proximity proof system (e.g., FRI or STIR) is expensive.


### The bottleneck: Efficient compilers from Poly-IOPs


To optimize hash-based SNARGs, we need efficient compilers that translate a poly-IOP into a full IOP, without sacrificing key performance metrics:
- Prover time
- Proof size
- Verifier time

This process usually involves checking proximity to Reed–Solomon codes. For univariate poly-IOPs, this has been addressed using protocols like FRI and STIR, coupled with quotient checks. For multilinear poly-IOPs, compilation typically builds on the multilinear sumcheck protocol and results in an IOP that essentially acts as a polynomial commitment scheme for multilinear polynomials.

Each of these strategies makes trade-offs. For example, decreasing the rate of the Reed–Solomon code can reduce proof size and speed up verification, but it slows down the prover. A major technical challenge is to reduce verifier time without degrading prover efficiency or inflating the proof.

### Enter WHIR

WHIR solves this by offering an IOP of proximity with:
- Extremely low query complexity,
- Verification in microseconds,
- Compatibility with both univariate and multilinear poly-IOPs.

WHIR can replace prior proximity systems like FRI, STIR, and BaseFold. Its performance improvements translate directly into faster SNARG verification and smaller proofs in both univariate and multilinear settings. In particular, WHIR enables polynomial commitment schemes where, for example, committing and opening a degree-$2^{22}$ polynomial with 100-bit security takes 1.2 seconds of sender time, 63 KiB of communication, and just 360 microseconds for the verifier to check the opening.

In short, WHIR sets a new standard for fast, practical SNARGs and polynomial commitments.


## Notation and preliminaries

Before going further, let's clarify some of the notation and definitions used throughout the WHIR protocol. Each item below includes a concrete example to make the meaning clearer.

- A function with a hat, like $\hat{p}$, represents a **polynomial**. So $\hat{f}$ means we are treating $f$ as a polynomial rather than just a table of values.

:::info Example
If $\hat{f}(x_1, x_2) = 3 + 2x_1 + 4x_2 + x_1x_2$, then $f : \{0,1\}^2 \to F$ is the table of values obtained by evaluating $\hat{f}$ at $(0,0), (0,1), (1,0), (1,1)$.
:::

- For a polynomial $\hat{p} \in F[X_1, \dots, X_m]$, the **individual degree** $\deg(\hat{p})$ is the maximum degree in each variable.

:::info Example
If $\hat{p}(x_1, x_2) = 1 + x_1 + 2x_2 + 3x_1x_2$, then $\deg(\hat{p}) = 1$, since no variable is raised to a power higher than 1.
:::

- The **fractional Hamming distance** $\Delta(f, g)$ between two functions $f, g : L \to F$ is the fraction of points in $L$ where $f(x) \ne g(x)$.

:::info Example
If $L = \{1,2,3,4\}$ and $f = (1,2,3,4)$, $g = (1,0,3,0)$, then they differ at two positions: $x = 2$ and $x = 4$. So $\Delta(f, g) = 2/4 = 0.5$.
:::

- For a set $S$ of functions, $\Delta(f, S) := \min_{h \in S} \Delta(f, h)$ is the smallest distance from $f$ to any function in $S$.

:::info Example
If $S = \{(1,1,1), (2,2,2), (3,3,3)\}$ and $f = (1,2,3)$ over domain $L = \{1,2,3\}$, then:
- $\Delta(f, (1,1,1)) = 2/3$
- $\Delta(f, (2,2,2)) = 2/3$
- $\Delta(f, (3,3,3)) = 2/3$

So $\Delta(f, S) = 2/3$.
:::

- For $L \subseteq F$ and $k \in \mathbb{N}$, define $L^{(k)} := \{x^k \mid x \in L\}$.

:::info Example
Let's work in the finite field $\mathbb{F}_{17}$ and use a domain $L$ that has the special structure required for folding.

Let $L = \{1, 2, 4, 8, 9, 13, 15, 16\}$. The size of $L$ is 8.
Let $k = 2$. Then $L^{(2)}$ is the set of unique values from squaring every element in $L$ (modulo 17):
\begin{aligned}
L^{(2)} &= \{1^2, 2^2, 4^2, 8^2, 9^2, 13^2, 15^2, 16^2\} \\
L^{(2)} &= \{1, 4, 16, 13, 13, 16, 4, 1\}
\end{aligned}
The set of unique elements is $L^{(2)} = \{1, 4, 13, 16\}$.

Notice the size of the domain was **reduced from 8 to 4**. This happens because for every element $x$ in $L$, its negative $-x$ is also in $L$, causing pairs of elements (e.g., 2 and 15) to map to the same square (e.g., 4).
:::

- A set $L \subseteq F$ is smooth if it is a multiplicative coset of $F^*$ whose size is a power of two.

:::info Example
In $\mathbb{F}_{17}$, the set $L = \{1, 2, 4, 8, 9, 13, 15, 16\}$ is a smooth multiplicative subgroup of size 8, since it's closed under multiplication and $8 = 2^3$.
:::

- For interactive (oracle) algorithms $A$ and $B$, we write $\langle A(a), B(b) \rangle(c)$ for the random output of their interaction, with private inputs $a$, $b$ and shared input $c$.

:::info Example
$A$ proves that $x = 5$ satisfies some equation; $B$ verifies the proof using a random challenge. Both are given $c = x^2 = 25$, but $A$ knows $x$ and $B$ does not.
:::

- For a relation $R = \{(x, y, w)\}$, define the **induced language** $L(R) := \{(x, y) \mid \exists w : (x, y, w) \in R\}$.

:::info Example
Let $R = \{(x, y, w) \mid w = x \cdot y\}$. Then $L(R) = \{(x, y)\}$ for all $x, y \in F$, because a suitable $w$ always exists (just take $w = xy$).
:::

- For functions $f, g : L \to F$ and subset $S \subseteq L$, we write $f(S) = g(S)$ if $f(x) = g(x)$ for all $x \in S$.

:::info Example
Let $L = \{1,2,3,4\}$, $S = \{2,3\}$, $f = (1,5,7,2)$, $g = (1,5,7,9)$. Then $f(S) = g(S)$ because they agree on $x = 2$ and $x = 3$.
:::

- For a vector $x = (x_0, \dots, x_{m-1})$, define:

\begin{equation}
\text{pow}(x, m) := (x_0^2, x_1^2, \dots, x_{m-1}^2)
\end{equation}

:::info Example
Let $x = (2,3,4)$ and $m = 3$. Then $\text{pow}(x, m) = (4,9,16)$.
:::

## WHIR protocol: How it works

The goal of the WHIR protocol is to check if a function is close to being a valid Reed–Solomon codeword, under some extra constraint.

For a classical IOP of Proximity to Reed Solomon codes, the process is as follows:


But we want to do this with very fast verification time, ideally in just a few hundred microseconds. To achieve this, WHIR combines two key ideas from previous protocols:
- From BaseFold, it uses the **sumcheck** protocol, which efficiently verifies polynomial identities.
- From STIR, it uses **folding**, which reduces the size of the problem step by step.

By combining folding and sumcheck, WHIR turns a large proximity test into several small ones that are much faster to check.

### What is being tested?

#### Initial requirements

At the heart of WHIR is the need to verify a simple but fundamental constraint:

> I have a polynomial $\hat{f}$, and I claim that at a specific point $z \in F$, it evaluates to a known value $y$.

This sounds easy—but verifying this efficiently in a cryptographic proof system is *surprisingly costly*. That’s because in practice, we don’t work directly with $\hat{f}$. Instead, we work with an **encoded version** of it—typically its evaluations over a domain $L$—and we want to check that these evaluations *come from* a polynomial that satisfies $\hat{f}(z) = y$.

The standard strategy (as shown in the image) is to use a **Reed–Solomon Proximity Test** on the following virtual function:

\begin{equation}
f'(x) := \frac{f(x) - y}{x - z}
\end{equation}

This test is sound: if $f'$ is close to a low-degree polynomial, then $f$ must indeed satisfy $f(z) = y$. But it's expensive—it turns a small check into a full-blown proximity proof.

To better understand this cost, we break it into two parts:

- A **constraint check**: that $f(z) = y$ (captured by the quotient function $f'$),
- A **proximity check**: that $f'$ is close to a polynomial.

As the image highlights, most of the argument size (> 80%) is spent just verifying this proximity!


WHIR is designed to handle exactly this kind of situation *much more efficiently*. It does so by defining a new kind of code—a **constrained Reed–Solomon code**—that naturally handles this kind of constraint.

#### Constrained Reed–Solomon codes

Reed–Solomon codes traditionally represent functions as evaluations of univariate polynomials over a domain $L$, like:

\begin{equation}
\text{RS}[n, m, \rho] := \left\{ f : L \to F \ \middle|\ f = \hat{f}|_L,\ \hat{f} \in F^{<2^m}[X] \right\}
\end{equation}

But these codes can also be rewritten in terms of multilinear polynomials $\hat{f} \in F^{\leq 1}[X_1, \dots, X_m]$ over Boolean inputs, where $m = \log_2(\text{poly degree})$. This view allows us to naturally express constraints on $\hat{f}$ itself.

This leads to constrained RS codes:

\begin{equation}
\text{CRS}[n, m, \rho, \hat{w}, \sigma] := \left\{ f = \hat{f}|_L\ \middle|\ \sum_{b \in \{0,1\}^m} \hat{w}(\hat{f}(b), b) = \sigma \right\}
\end{equation}

Here, $\hat{w}$ is a constraint polynomial in $m + 1$ variables, and $\sigma$ is a fixed target value. When $\hat{w} = 0$, we recover the standard RS code: $\text{RS}[n, m, \rho] = \text{CRS}[n, m, \rho, 0, 0]$.

This constrained formulation makes it possible to efficiently encode conditions like *“the polynomial $\hat{f}$ evaluates to $y$ at point $r$”*, and forms the foundation of WHIR's fast verification mechanism.


#### Technical explanation of what is being tested

We are given a function $f : L \to F$ and we want to check if it satisfies the following:
1. $f$ comes from evaluating a multilinear polynomial $\hat{f}$ in $m$ variables.
2. This $\hat{f}$ satisfies a constraint of the form $\hat{w}(x_1, \dots, x_m, \hat{f}(x_1, \dots, x_m)) = \sigma$, where $\hat{w}$ is a fixed polynomial and $\sigma$ is a fixed target value.

The function $f$ is evaluated on a set $L \subseteq F$, which is called the evaluation domain. We assume $|L| = n$ is a power of two and $L$ is smooth (this helps with folding later).

This setup defines a special code, called a constrained Reed–Solomon code:

\begin{equation}
\text{CRS}[F, L, m, \hat{w}, \sigma]
\end{equation}

Here:
- $F$ is the finite field,
- $L$ is the domain (a subset of $F$),
- $m$ is the number of variables in the multilinear polynomial $\hat{f}$,
- $\hat{w}$ is the constraint polynomial (with $m + 1$ variables),
- $\sigma$ is the required value of the constraint.

The rate of this code is the number of valid codewords divided by the number of points in the domain:

\begin{equation}
\rho = \frac{2^m}{n}
\end{equation}

This is because $\hat{f}$ has $2^m$ degrees of freedom (over all Boolean inputs), and we are evaluating over $n$ points in $L$.

:::info

### Example

Let $F = \mathbb{F}_7$ (the field with 7 elements), and let $m = 2$. Then the multilinear polynomial $\hat{f}(x_1, x_2)$ could be:

\begin{equation}
\hat{f}(x_1, x_2) = 3 + 2x_1 + x_2 + 4x_1x_2
\end{equation}

This polynomial has $2^2 = 4$ possible inputs over $\{0,1\}^2$, so it defines a codeword of length 4.

Now suppose the domain $L = \{1, 2, 3, 4, 5, 6\}$ has size $n = 6$, and we extend $\hat{f}$ to a function $f : L \to F$ (e.g., by interpolating).

We also define a constraint like:

\begin{equation}
\hat{w}(x_1, x_2, y) = x_1 + x_2 + y
\end{equation}

and choose a target value $\sigma = 0$. The constraint is satisfied at each point if:

\begin{equation}
x_1 + x_2 + \hat{f}(x_1, x_2) = 0
\end{equation}

In this case, the verifier must check that this equation holds for all inputs in $L$, and that $f$ really comes from evaluating a degree-1 multilinear $\hat{f}$.

:::

### Folding the problem

#### Folding in FRI and STIR

Folding is a core idea in protocols like FRI and STIR. It reduces the size of the domain and the number of variables, allowing proximity tests to become progressively simpler. Specifically, folding reduces a Reed–Solomon code $\text{RS}[n, m, \rho]$ to $\text{RS}[n/2^k, m - k, \rho]$, where $k$ is the folding parameter.

The folding operation is defined using a random field element $\alpha \in F$ and combines evaluations of $f$ into a new virtual function:

\begin{equation}
\text{Fold}(f, \alpha)(x) := f_{\text{odd}}(x) + \alpha \cdot f_{\text{even}}(x)
\end{equation}

This is inspired by the structure of FFTs and generalizes to any $k$ that is a power of two. The key advantage is **locality**: computing $\text{Fold}(f, \alpha)(z)$ requires only $2^k$ queries to $f$. Moreover, **distance is preserved**: if $f$ is $\delta$-far from the code, then $\text{Fold}(f, \alpha)$ is still $\delta$-far from the folded code with high probability—ensuring the soundness of the proximity test remains intact as we fold.


#### Folding in WHIR

The core idea of WHIR is folding. In each round, we reduce the size of the function and the number of variables, transforming the problem into a smaller one.

Let $k \geq 1$ be the folding parameter. A single WHIR round reduces:
$$f \in \text{CRS}[F, L, m, \hat{w}, \sigma]$$to:$$f' \in \text{CRS}[F, L^{(2^k)}, m - k, \hat{w}', \sigma']$$
This means:

- The number of variables goes from $m$ to $m - k$.
- The domain $L$ becomes $L^{(2^k)} = \{ x^{2^k} \mid x \in L \}$, which is $1/2^k$ times the original size.
- The constraint changes from $\hat{w}$ to $\hat{w}'$, but is still cheap to evaluate.
- The target value becomes $\sigma'$.

The rate of the code also drops:
$$\rho' = 2^{1 - k} \cdot \rho$$
The key point is that we’ve made the problem smaller and easier to verify, without losing too much information.


:::info

### Example

Let’s say we are working over the field $F = \mathbb{F}_{17}$, and the original number of variables is $m = 3$. So we have a multilinear polynomial $\hat{f}(x_1, x_2, x_3)$.

Suppose the domain $L = \{1, 2, 3, 4, 5, 6, 7, 8\}$ has size $n = 8$. Then the rate of the code is:

\begin{equation}
\rho = \frac{2^3}{8} = \frac{8}{8} = 1
\end{equation}

Now we apply a WHIR round with folding parameter $k = 1$.

- The number of variables becomes $m - k = 2$
- The domain becomes $L^{(2)} = \{ x^2 \mid x \in L \} = \{1, 4, 9, 16, 2, 8, 13, 15\}$ (still size 8, but we take only distinct values, so we reduce it to about half)
- The new constraint $\hat{w}'$ depends on the new variables and folded values
- The new rate becomes:

\begin{equation}
\rho' = 2^{1 - 1} \cdot \rho = 1 \cdot \rho = \rho
\end{equation}

If we had used $k = 2$, the number of variables would drop from 3 to 1, and the new rate would be:

\begin{equation}
\rho' = 2^{1 - 2} \cdot \rho = \frac{1}{2} \cdot \rho
\end{equation}

So we lose some rate but gain a much smaller problem to verify.

:::

### Repeating the process

We repeat this process $M = m / k$ times. Each round folds the problem further until the function becomes small enough to check directly.

At iteration $i$, we are checking if:

\begin{equation}
f^{(i)} \in \text{CRS}[F, L^{(2^i)}, m - i \cdot k, \hat{w}^{(i)}, \sigma^{(i)}]
\end{equation}

Eventually, at iteration $M$, the function $f^{(M)}$ depends on only a few variables and is evaluated on a tiny domain. The prover just sends the coefficients of the final polynomial, and the verifier checks that it satisfies the constraint using either:
- A few direct evaluations of $\hat{w}^{(M)}$, or
- One last sumcheck protocol (this is what WHIR uses in practice).

### Query complexity and verifier time

In each round, the verifier makes $t_i$ queries. Over all rounds, the total number of queries is:

\begin{equation}
q_{\text{WHIR}} = O\left( \lambda + \frac{\lambda}{k} \cdot \log\left( \frac{m}{k} \right) \right)
\end{equation}

Here, $\lambda$ is the soundness parameter: the error probability is at most $2^{-\lambda}$.

The proof length (total amount of data sent by the prover) is:

\begin{equation}
\sum_{i=0}^{M-1} \frac{|L^{(2^i)}|}{2} = O(n)
\end{equation}

And the verifier time (in number of field operations) is:

\begin{equation}
O\left( q_{\text{WHIR}} \cdot (2^k + m) \right)
\end{equation}

This is much faster than previous systems like STIR, because each query is cheaper and the total number of queries is similar.

## Folding Reed–Solomon Codes and preserving distance

The folding operation is a key part of WHIR. It reduces the complexity of the function we’re checking without significantly affecting how far it is from being a valid codeword. This idea has been used before in other Reed–Solomon proximity protocols, and WHIR builds on it with some extra structure to preserve soundness more strongly.

### How folding works

Let $f : L \to F$ be the function we want to fold. Let $y \in L^{(2)}$, which means $y = x^2$ for some $x \in L$. Since $L$ is a multiplicative subgroup and its order is a power of two, both $x$ and $-x$ are in $L$.

Given some parameter $\alpha \in F$, we define the folded function as:

\begin{equation}
\text{Fold}(f, \alpha)(y) = \underbrace{\frac{f(x) + f(-x)}{2}}_{\text{average}} + \alpha \cdot \underbrace{\frac{f(x) - f(-x)}{2x}}_{\text{difference term}}
\end{equation}

This mixes together the values of $f(x)$ and $f(-x)$ to produce a new value at $y = x^2$.

We can also fold multiple times, using a vector of parameters $\alpha = (\alpha_1, \dots, \alpha_k) \in F^k$. The folding is then applied recursively $k$ times to reduce $f$ to a function on $L^{(2^k)}$.

### Why folding preserves distance

When we fold a function $f : L \to F$ to reduce the problem size, we want to make sure we’re not giving the prover a shortcut to cheat. That is, if $f$ is *far* from any codeword in a Reed–Solomon code, then the folded version $\text{Fold}(f, \alpha)$ should also be far from any codeword in the corresponding folded code.

This crucial property is ensured by a concept called **mutual correlated agreement**. It says that folding doesn’t create fake agreement with the code. If you apply a folding operation to a function that was far from the code, the result stays far.

To understand this, suppose we’re dealing with several functions $f_1, \dots, f_m$, and we form a random linear combination:

\begin{equation}
f^* := \sum_{i=1}^m r_i f_i
\end{equation}

Now suppose $f^*$ happens to look close to some codeword in a code $\mathcal{C}$. Then:

- **Agreement:** each $f_i$ must also be close to $\mathcal{C}$,
- **Correlated agreement:** not only are they close, but they agree with $\mathcal{C}$ on the same *subset* of the domain (think: same "stripe" of correct values),
- **Mutual correlated agreement:** this shared stripe is also the one where $f^*$ agrees with the code.

This rules out any trick where the prover tries to cancel out errors using combinations. Folding respects this structure: if the folded function is close to a codeword, then the original function was close too—and to a codeword that folds into it.

So we get the following important consequence:

> If $f$ is $\delta$-far from $\text{RS}[F, L, m]$, then with high probability over a random folding parameter $\alpha$, the folded function $\text{Fold}(f, \alpha)$ is also $\delta$-far from $\text{RS}[F, L^{(2)}, m - 1]$.

This is what makes recursive folding protocols sound and safe.


:::info

### Example

Let $F = \mathbb{F}_{17}$ and $L = \{1, 2, 4, 8, 9, 13, 15, 16\}$, a multiplicative subgroup of order 8. Suppose we have a function $f: L \to F$, and we choose a folding parameter $\alpha = 5$.

To compute the folded value at $y = x^2 = 9$, take $x = 3$ (so $-x = 14$), and use:

\begin{equation}
\text{Fold}(f, 5)(9) = \frac{f(3) + f(14)}{2} + 5 \cdot \frac{f(3) - f(14)}{2 \cdot 3}
\end{equation}

You repeat this for each $y \in L^{(2)}$ to construct the entire folded function.

Now suppose someone claims this folded function is close to a Reed–Solomon codeword. Thanks to mutual correlated agreement, that’s only possible if the original $f$ was also close to a codeword—and the folded version comes from folding that codeword. This makes the protocol secure against such fake claims.

:::

### Why folding preserves lists: decoding remains consistent

We’ve seen that folding preserves distance: if a function $f$ is far from the code, then $\text{Fold}(f, \alpha)$ is also far. But what if $f$ is *close* to multiple codewords? Could folding disrupt that structure or introduce new "fake" codewords?


The good news is: **folding behaves well with lists, too**. This is another benefit of mutual correlated agreement. It ensures that folding **commutes** with list decoding.

Here’s what that means.

Let:
* $\mathcal{C}$ be a Reed–Solomon code,
* $f$ be a function $f : L \to F$,
* $\Lambda(\mathcal{C}, f, \delta)$ be the list of codewords in $\mathcal{C}$ that are within distance $\delta$ of $f$.

Then folding satisfies:
$$\Lambda(\mathcal{C}, \text{Fold}(f, \alpha), \delta) = \left\{ \text{Fold}(u, \alpha) : u \in \Lambda(\mathcal{C}, f, \delta) \right\}$$
In plain terms:
* If $f$ is close to several codewords $u_1, \dots, u_t$, then $\text{Fold}(f, \alpha)$ is close to exactly the folded versions $\text{Fold}(u_1, \alpha), \dots, \text{Fold}(u_t, \alpha)$.
* No new codewords sneak into the list after folding.
* Every codeword in the folded list corresponds to one that was already close before folding.

This is critical for recursive protocols like WHIR. At every round of folding, we’re reducing the problem size. But we still want to know whether any codeword in the list satisfies the constraint. Thanks to list preservation, we know that folding won’t "hide" a bad function behind a good folded version.

The image illustrates the general principle behind this. It shows that taking a random linear combination of several functions and then list-decoding the result (the bottom path) is equivalent to list-decoding each function first and then taking the same random linear combination of the resulting codewords (the top path). Since folding is a specific type of random linear combination, this principle applies directly, ensuring that folding and list decoding commute.

This structural property is **stronger than what STIR requires** and makes WHIR especially robust. It ensures correctness and soundness in list decoding, even as the recursion goes deeper.

The takeaway:
> Folding doesn’t just preserve distance—it preserves *structure*. It keeps decoding safe, predictable, and cheat-resistant at every round.

## The WHIR protocol: core construction

This section describes the central piece of the WHIR protocol. The entire proximity proof system builds on this recursive process, combining folding, sumcheck, and constraint evaluation.

### Ingredients of WHIR


WHIR starts with a constrained Reed–Solomon code:

\begin{equation}
\text{CRS}[F, L_0, m_0, \hat{w}_0, \sigma_0]
\end{equation}

Here:
- $F$ is the finite field over which everything is defined,
- $L_0 \subseteq F$ is the evaluation domain,
- $m_0$ is the number of variables of the polynomial $\hat{f}_0$,
- $\hat{w}_0$ is a fixed constraint polynomial in $m_0 + 1$ variables,
- $\sigma_0 \in F$ is the target value the constraint must evaluate to.

We also fix:
- An iteration count $M$, which tells us how many times we will fold the problem,
- Folding parameters $k_0, \dots, k_{M-1}$, each determining how many variables we fold at each round,
- Evaluation domains $L_1, \dots, L_{M-1}$, where each $L_i$ is a smooth coset of $F$ large enough to support the reduced problem at step $i$,
- Repetition parameters $t_1, \dots, t_M$, determining how many queries the verifier will use to test folded functions.

For each step $i$, we define:
- $m_i := m - \sum_{j<i} k_j$, the number of variables remaining after $i$ folds,
- $d^* := 1 + \deg_Z(\hat{w}_0) + \max_i \deg_{X_i}(\hat{w}_0)$,
- $d := \max(d^*, 3)$, a technical degree bound for the polynomials used during sumcheck.

### Overview of protocol steps

The protocol has three main phases: Inputs, Interaction, and Decision. Each builds upon the previous one to ensure the function is a valid codeword that satisfies the constraint.


### 1. Inputs

The verifier begins with oracle access to a function $f_0 : L_0 \to F$. The prover knows a multilinear polynomial $\hat{f}_0$ such that:

- $f_0(x) = \hat{f}_0(x)$ for all $x \in L_0$,
- The following constraint holds over all Boolean inputs:

\begin{equation}
\sum_{b \in \{0,1\}^{m_0}} \hat{w}_0(\hat{f}_0(b), b) = \sigma_0
\end{equation}

This constraint says: over the Boolean cube, the values of $\hat{f}_0$ should satisfy a global arithmetic relation given by $\hat{w}_0$.

:::info

### Example

Let $F = \mathbb{F}_7$, $m_0 = 2$, and $L_0 = \{1, 2, 3, 4\}$.

Let the polynomial be:

\begin{equation}
\hat{f}_0(x_1, x_2) = 3 + 2x_1 + x_2 + x_1x_2
\end{equation}

Evaluate it on all Boolean inputs:
- $\hat{f}_0(0,0) = 3$
- $\hat{f}_0(0,1) = 4$
- $\hat{f}_0(1,0) = 5$
- $\hat{f}_0(1,1) = 0$ mod 7

Set the constraint to:

\begin{equation}
\hat{w}_0(y, x_1, x_2) = y + x_1 + x_2
\end{equation}

Then:

\begin{align*}
\hat{w}_0(3, 0, 0) &= 3 \\
\hat{w}_0(4, 0, 1) &= 5 \\
\hat{w}_0(5, 1, 0) &= 6 \\
\hat{w}_0(0, 1, 1) &= 2 \\
\text{Sum} &= 3 + 5 + 6 + 2 = 16 \equiv 2 \mod 7
\end{align*}

So $\sigma_0 = 2$. The verifier wants to be convinced that this constraint really holds, using only a few queries.

:::

### 2. Interaction phase

This is the interactive part where the prover and verifier exchange messages.

#### Step 1: Initial sumcheck

The verifier cannot evaluate $\hat{f}_0$ on all Boolean inputs directly. So we use the sumcheck protocol, which allows checking a multivariate sum using only univariate polynomials and random sampling.

For $\ell = 1, \dots, k_0$:
- The prover sends a univariate polynomial $\hat{h}_{0,\ell} \in F^{<d}[X]$.
- This polynomial represents a partial sum over the last $m_0 - \ell$ variables of the constraint.
- The verifier samples a random point $\alpha_{0,\ell} \in F$ and updates $\alpha_0 := (\alpha_{0,1}, \dots, \alpha_{0,\ell})$.

By the end of this, the verifier has reduced the entire constraint check to a single point of evaluation at $\alpha_0$.

#### Step 2: Main folding loop

Now we run the main loop for $i = 1, \dots, M - 1$. In each iteration, we fold the problem into a smaller one.

1. **Send folded function:**
The prover sends $f_i : L_i \to F$, which is the folded version of $f_{i-1}$ using the folding parameter $k_{i-1}$ and challenge point $\alpha_{i-1}$.
In the honest case, $f_i = \hat{f}_{i-1}(\alpha_{i-1}, \cdot)$.

2. **Out-of-domain check (Force unique commitment):**
To prevent the prover from remaining ambiguous about which low-degree polynomial he is using, the verifier forces him to commit to a single one. Indeed, the prover already submitted evaluations of $\hat{f}_i$ for all the points of the domain $L_i$. We then need to do an out-of-domain check to force the unique commitment. This is done by checking the claimed polynomial $\hat{f}_i$ at a random point outside of its original evaluation domain.
* The verifier sends a random out-of-domain point $z_{i,0} \in F$.
* The prover must reply with a single evaluation $y_{i,0} := \hat{f}_i(\text{pow}(z_{i,0}, m_i))$.

By providing this evaluation at a new point, the prover is locked into the unique low-degree polynomial that satisfies this check, as any other candidate polynomial would almost certainly produce a different value (thanks to Schwartz-Zippel Lemma).

3. **Query setup:**
- The verifier picks $t_i$ random points $z_{i,1}, \dots, z_{i,t_i-1}$ from $L_i^{(2^{k_i - 1})}$.
- The verifier also samples a random field element $\gamma_i$.

4. **Sumcheck rounds for constraints:**
Similar to the initial sumcheck, but using a new constraint polynomial $\hat{w}_i$ defined recursively as:

\begin{aligned}
\hat{w}_i(Z, X_1, \dots, X_{m_i}) &= \hat{w}_{i-1}(Z, \alpha_{i-1}, X_1, \dots, X_{m_i}) \\ &+ Z \cdot \sum_{j=0}^{t_{i-1}} \gamma_i^{j+1} \cdot \text{eq}(z_{i,j}, (X_1, \dots, X_{m_i}))
\end{aligned}

This mixes in the evaluation points and enforces consistency between $f_i$ and the expected values.

#### Step 3: Final polynomial

The prover now sends a final small polynomial:

\begin{equation}
\hat{f}_M = \hat{f}_{M-1}(\alpha_{M-1}, \cdot)
\end{equation}

This polynomial is low-degree and has very few variables, making it easy to verify.

**Step 4: Final queries**

The verifier samples $t_M$ random points from $L_{M-1}^{(2^{k_{M-1}})}$ to check that this final polynomial agrees with previous expectations.

#### 3. Decision Phase

The verifier performs several checks to confirm consistency:

1. **Initial sumcheck check:**
- Check that the final value equals $\sigma_0$.
- Check that each polynomial in the sumcheck chain evaluates correctly at the sampled points.

2. **Loop checks:**
For $i = 1, \dots, M-1$:
- Define $g_{i-1} := \text{Fold}(f_{i-1}, \alpha_{i-1})$.
- Check that:
\begin{equation}
\sum_{b \in \{0,1\}} \hat{h}_{i,1}(b) = \hat{h}_{i-1, k_{i-1}}(\alpha_{i-1,k_{i-1}}) + \gamma_i \cdot y_{i,0} + \sum_{j=1}^{t_{i-1}} \gamma_i^{j+1} \cdot g_{i-1}(z_{i,j})
\end{equation}
- Check that each sumcheck layer evaluates consistently.

3. **Final polynomial check:**
- Verify that $\hat{f}_M$ matches the expected folded values on random points.
- Evaluate the constraint polynomial using $\hat{f}_M$ and verify the final constraint.

## Domain shifting, OOD checks, and batching: The core of WHIR iteration

Each round in the WHIR protocol transforms a proximity check over a large domain into a smaller, easier one. This recursive structure is made possible by combining three essential ingredients: domain shifting, out-of-domain checks, and constraint batching. Together, they allow WHIR to compress the problem, force uniqueness, and maintain soundness at every step.

### Step 1: Folding and Domain Shifting

After the verifier sends a challenge vector $\alpha_1, \dots, \alpha_k$, the prover responds with a *folded* version of the function $f : L \to F$, defined over a smaller domain. This produces a new function $g : L^* \to F$, where:

- The domain $L^*$ is smaller: it typically has half the size of $L$.
- The polynomial $g$ is claimed to be derived from folding $f$ using the challenge vector.

This folding step reduces the number of variables (from $m$ to $m - k$) and compresses the proximity test—making it faster for the verifier to check. This is the **domain shift**: we move from $f$ defined on $L$ to $g$ defined on $L^*$.

\begin{equation}
f \xrightarrow{\text{fold } \alpha_1,\dots,\alpha_k} g \quad \text{with } L \rightsquigarrow L^*
\end{equation}


### Step 2: Out-of-Domain check (force uniqueness)

After folding, there might be *many* possible polynomials $g$ that are close to the new constraint set. To force the prover to commit to a **unique** codeword, we run an **Out-of-Domain (OOD)** check:

1. The verifier samples a random point $r \notin L^*$.
2. The prover returns $\beta := \hat{g}(r)$ — the claimed evaluation of the polynomial $g$ at $r$.
3. By the **Fundamental Theorem of Algebra**, two distinct polynomials of low enough degree cannot agree at a random point. So this step pins down the prover’s commitment to a unique $\hat{g}$.

This subprotocol ensures that the recursive proof always continues with a single, well-defined codeword. It is not optional—it’s vital for soundness.

> This step eliminates ambiguity: the prover “chooses” which codeword it commits to.


### Step 3: Batching Constraints

Now we need to verify that $g$ satisfies **many** constraints—usually one per original folded polynomial. Rather than checking each constraint separately (which would be inefficient), we **batch** them into a single constraint.

The verifier:
- Samples a random scalar $\gamma$.
- Forms a new constraint polynomial $\hat{w}^*$ as a random linear combination:
\begin{equation}
\hat{w}^*(Z, X) := \sum_{i=1}^\ell \gamma^{i-1} \cdot \hat{w}_i(Z, X)
\end{equation}
- Combines the target values:
\begin{equation}
\sigma^* := \sum_{i=1}^\ell \gamma^{i-1} \cdot \sigma_i
\end{equation}

So instead of checking $\ell$ separate conditions, the verifier only needs to check:

\begin{equation}
\sum_{b \in \{0,1\}^{m-k}} \hat{w}^*(\hat{g}(b), b) = \sigma^*
\end{equation}

This technique is standard in SNARK design and dramatically reduces query and proof size without sacrificing soundness.

> Batching lets us test all constraints **at once** with high confidence.


### Step 4: Prepare for recursion

At this point, the verifier has:

- A new function $g$ on a smaller domain,
- A **unique commitment** enforced via the OOD check,
- A **batched constraint** to be checked.

All of this is packaged into a new proximity test over a smaller constrained Reed–Solomon code:

\begin{equation}
g \in \text{CRS}\left[\frac{n}{2},\ m - k,\ \rho' = 2^{1-k} \cdot \rho,\ \hat{w}^*,\ \sigma^*\right]
\end{equation}

Then the next WHIR round begins—recursing on $g$ just like it did on $f$.

### Visual summary

Let’s summarize a single WHIR iteration with the help of the following diagram:


1. **Folding:** Prover folds $f$ to get $g$.
2. **OOD Check:** Verifier samples $r$; prover returns $\beta = \hat{g}(r)$.
3. **Domain Shift:** New function $g$ lives on $L^*$.
4. **Batching:** Combine constraints into $(\hat{w}^*, \sigma^*)$.
5. **Recurse:** Run the next WHIR iteration on $g$.

This trio of steps—**fold, OOD, batch**—is repeated until the function becomes small enough to check directly via final sumcheck rounds.

## Complexity of WHIR

Let’s now summarize the main complexity parameters:

- **Rounds:**
The protocol has:

\begin{equation}
O\left(M \cdot \sum_{i=0}^{M-1} k_i\right)
\end{equation}

rounds of interaction, corresponding to all the sumcheck layers.

- **Proof length:**
The prover sends one folded function and $k_i$ univariate polynomials per round:

\begin{equation}
O\left(\sum_{i=1}^{M-1} (|L_i| + k_i)\right)
\end{equation}

- **Input queries:**
The verifier queries $2^{k_0}$ points $t_0$ times in the initial step, grouped into $t_0$ query symbols.

- **Proof queries:**
In the main loop, the verifier queries $2^{k_i}$ points $t_i$ times from $f_i$, so the total number of symbols is:

\begin{equation}
O\left(\sum_{i=1}^{M-1} t_i\right)
\end{equation}

## Batching multiple constraints

In practice, we often want to check not just one constraint, but several. For example, in a SNARG system, a single polynomial might need to satisfy multiple algebraic checks. WHIR supports this by batching multiple constraints into one — without increasing the number of rounds or affecting soundness too much.

This idea is simple and powerful: instead of checking each constraint individually, we use random linear combinations of all constraints to create a single “combined” one. If the original constraints are not satisfied, the combined one likely won’t be either.

### Construction: batched constraint testing

We adapt an existing IOPP `(P_prx, V_prx)` designed to check a single constraint of the form:

\begin{equation}
\sum_{b \in \{0,1\}^m} \hat{w}(\hat{f}(b), b) = \sigma
\end{equation}

and extend it to check *multiple* constraints at once.

#### Ingredients

- A $k$-round IOPP `(P_prx, V_prx)` for constrained Reed–Solomon codes over:

\begin{equation}
\text{CRS}[F, L, m, \hat{w}, \sigma]
\end{equation}

- A set of $t$ constraint polynomials:

\begin{equation}
\hat{w}_1, \dots, \hat{w}_t \in F[Z, X_1, \dots, X_m]
\end{equation}

- Target values:

\begin{equation}
\sigma_1, \dots, \sigma_t \in F
\end{equation}

The prover claims that:

\begin{equation}
\sum_{b \in \{0,1\}^m} \hat{w}_i(\hat{f}(b), b) = \sigma_i \quad \text{for all } i \in [t]
\end{equation}

### Protocol steps

1. **Initial input:**

The verifier has oracle access to $f : L \to F$.
In the honest case:
- $f = \hat{f}|_L$ for some multilinear polynomial $\hat{f}$,
- $\hat{f}$ satisfies all $t$ constraints.

2. **Combination randomness:**

The verifier samples a random $\gamma \in F$ and sends it to the prover.

The verifier then combines the constraints into one:

\begin{equation}
\hat{w}(Z, X_1, \dots, X_m) := \sum_{i=1}^t \gamma^{i-1} \cdot \hat{w}_i(Z, X_1, \dots, X_m)
\end{equation}

and similarly combines the answers:

\begin{equation}
\sigma := \sum_{i=1}^t \gamma^{i-1} \cdot \sigma_i
\end{equation}

This new combined constraint is equivalent to all original constraints **with high probability**.

3. **Proximity test interaction:**

The prover and verifier now run the usual proximity test `(P_prx, V_prx)` to check that:

\begin{equation}
\sum_{b \in \{0,1\}^m} \hat{w}(\hat{f}(b), b) = \sigma
\end{equation}

Since $\hat{w}$ is a linear combination of all the $\hat{w}_i$, this check indirectly validates all $t$ original constraints.

4. **Decision phase:**

The verifier completes the standard decision checks of `(P_prx, V_prx)`.

### Why it works

If even one of the original constraints fails — say, $\hat{w}_j(\hat{f}(b), b)$ doesn't sum to $\sigma_j$ — then the random linear combination is very likely to fail as well.

Because $\gamma$ is chosen randomly from a large field, the only way the combined constraint will pass is if all individual constraints were already satisfied. This is a standard **soundness amplification technique** in zero-knowledge proofs.

### Complexity

- **Rounds:** Same as the original `(P_prx, V_prx)` — no extra interaction rounds needed.
- **Proof length and queries:** Also unchanged.
- **Verifier computation:** Slightly increased: the verifier needs to compute the combined $\hat{w}$ and $\sigma$, which takes $O(t)$ field operations.

So this technique gives **multi-constraint support** essentially for free.

:::info

#### Example

Let’s say we want to check that a polynomial $\hat{f}$ satisfies both:
1. $\sum_b \hat{f}(b)^2 = 10$
2. $\sum_b \hat{f}(b) \cdot b_1 = 3$

Then set:

\begin{align*}
\hat{w}_1(y, x_1, x_2) &= y^2 \\
\hat{w}_2(y, x_1, x_2) &= y \cdot x_1 \\
\sigma_1 &= 10,\quad \sigma_2 = 3
\end{align*}

Verifier samples random $\gamma = 4$ and computes:

\begin{align*}
\hat{w}(y, x_1, x_2) &= \hat{w}_1 + 4 \cdot \hat{w}_2 = y^2 + 4yx_1 \\
\sigma &= 10 + 4 \cdot 3 = 22
\end{align*}

Then run WHIR once with this single combined constraint. If it passes, both original constraints are satisfied with high probability.

:::





## From Σ-IOPs to IOPs: compiling structured queries into WHIR


A powerful aspect of the WHIR protocol is its ability to serve as a backend for general polynomial IOPs with rich query structures. These IOPs often go beyond the standard "evaluate a polynomial at a point" model and instead support queries like "sum this weighted constraint over the Boolean cube." To support such expressive query systems, WHIR compiles structured IOPs — called Σ-IOPs — into standard IOPs of proximity for constrained Reed–Solomon codes.

This section presents the key ideas behind this compilation. It proceeds in three main steps:

- defines a general framework of structured query IOPs (F-IOPs and Σ-IOPs).
- shows how to reduce a Σ-IOP to a standard IOP using WHIR.
- further extends the transformation to more general Σ-IOPs called $d$-Σ-IOPs.

### F-IOPs and Σ-IOPs: IOPs with structured queries

#### Structured queries over the boolean hypercube

Instead of querying a polynomial at one point, Σ-IOPs ask the prover to evaluate sums of constraint polynomials of the form:

\begin{equation}
\sum_{b \in \{0,1\}^m} \hat{w}(\hat{f}(b), b)
\end{equation}

These queries capture protocols like sumcheck and multilinear checks.

#### Definition of Σ-IOPs

Let $\Sigma = F$ be the field alphabet. A Σ-IOP is defined by a sequence of interactions over rounds, where the verifier specifies:
- Oracle sets $O_{i,j}$: the space of polynomials sent in round $i$,
- Query sets $W_{i,j}$: constraint polynomials $\hat{w} \in F[Z, X_1, \dots, X_m]$,
- Answer functions:

\begin{equation}
F_{i,j}(\hat{f}, \hat{w}) = \sum_{b \in \{0,1\}^m} \hat{w}(\hat{f}(b), b)
\end{equation}

The class of Σ-IOPs captures all protocols that query linear combinations of evaluations — like sumcheck — over the Boolean hypercube.

- A linear Σ-IOP (or 2-Σ-IOP) restricts $\deg_Z(\hat{w}) < 2$.
- A $d$-Σ-IOP allows constraint polynomials $\hat{w}$ with $\deg_Z < d$.

### Compiling linear Σ-IOPs into IOPs using WHIR

To make these protocols verifiable using standard IOPs like WHIR, we compile the structured query logic into a single multi-constrained proximity check over Reed–Solomon codes.

This compilation proceeds as follows.

#### Setup

Let:
- $(P_{\text{poly}}, V_{\text{poly}})$ be a $k_{\text{poly}}$-round linear Σ-IOP for relation $R$.
- Each round $i$ sends $s_i$ polynomials $\hat{f}_{i,j}$ over $m$ variables.
- The verifier asks $q_{\text{poly},\pi}$ structured queries over each $\hat{f}_{i,j}$.

We assume an evaluation domain $L \subseteq F$ of size at least $2^m$, and a proximity tester $(P_{\text{prx}}, V_{\text{prx}})$ such as WHIR for CRS codes with multi-constraints.

### Protocol Steps

#### 1. Simulate poly-IOP messages

In each round $i$:
- The prover sends $f_{i,j} = \hat{f}_{i,j}|_L$.
- The verifier samples an out-of-domain point $z_i \in F$ and receives $y_{i,j} = \hat{f}_{i,j}(z_i)$.

#### 2. Simulate poly-IOP verifier queries

The prover answers each structured query $\hat{w}$ by computing:

\begin{equation}
A_{i,j}[\hat{w}] = \sum_{b \in \{0,1\}^m} \hat{w}(\hat{f}_{i,j}(b), b)
\end{equation}

This gives the verifier all query answers needed to simulate $V_{\text{poly}}$.

#### 3. Reduce all queries to a WHIR check

To combine all structured queries into one proximity check, we batch them as constraints over a single Reed–Solomon codeword:

- The verifier samples randomness $\gamma \in F$.
- Define:

\begin{equation}
g(X) = \sum_{i=1}^{k_{\text{poly}}} \sum_{j=1}^{s_i} \gamma^{j + s_{<i}} \cdot \hat{f}_{i,j}(X)
\end{equation}

- For each query polynomial $\hat{w}$, define a folded constraint:

\begin{equation}
\hat{w}'(Z, X) := Z \cdot a(X) + \sum_{i,j} \gamma^{j + s_{<i}} \cdot c(X)
\end{equation}

where $\hat{w}(Z, X) = Z \cdot a(X) + c(X)$.

Then check:

\begin{equation}
\sum_{b \in \{0,1\}^m} \hat{w}'(g(b), b) = \sigma
\end{equation}

The verifier runs WHIR with this list of folded constraints $\hat{w}_1', \dots, \hat{w}_q'$ and target values $\sigma_1, \dots, \sigma_q$.

### Final Verifier Checks

1. **Check out-of-domain evaluations:**
Ensure each claimed $y_{i,j}$ matches the simulated query $A_{i,j}[Z \cdot \text{eq}(z_i, \cdot)]$.

2. **Run WHIR proximity check:**
Use WHIR to check that $g \in \text{CRS}[F, L, m, \{(\hat{w}_k', \sigma_k)\}]$.

3. **Simulate Poly-IOP Verifier:**
Run the decision logic of $V_{\text{poly}}$ using the simulated answers $A_{i,j}[\hat{w}]$.

### Complexity

Let:
- $s_{\text{poly}}$ be the total number of polynomials sent,
- $l_{\text{prx}}$ the length of WHIR proof,
- $q_{\text{poly},\pi}$ be the number of structured queries per oracle.

Then:

- **Rounds:**
$O(k_{\text{poly}} + k_{\text{prx}})$

- **Proof length:**
\begin{equation}
O(l_{\text{prx}} + s_{\text{poly}} \cdot (|L| + q_{\text{poly},\pi}))
\end{equation}

- **Input queries:**
Equal to $q_{\text{poly},y}$ — the number of times the verifier queries the original input.

- **Proof queries:**
\begin{equation}
O(s_{\text{poly}} \cdot q_{\text{prx},f} + q_{\text{prx},\pi})
\end{equation}

- **Verifier time:**
\begin{equation}
O(\text{vt}_{\text{poly}} + \text{vt}_{\text{prx}})
\end{equation}

where $\text{vt}_{\text{poly}}$ and $\text{vt}_{\text{prx}}$ are the running times of the poly-IOP and WHIR verifiers, respectively.

## Conclusion


WHIR introduces a powerful new direction for Reed–Solomon proximity testing—one that radically improves verifier performance while preserving strong soundness guarantees. By blending ideas from prior protocols like FRI, STIR, and BaseFold, WHIR constructs a fully recursive IOP that works efficiently over constrained Reed–Solomon codes and is compatible with both univariate and multilinear settings.

At the heart of WHIR are two key innovations:

1. **Constraint-aware proximity testing** using CRS codes, allowing the verifier to test structured relations like $\hat{f}(r) = y$ directly inside the code definition itself.

2. **Sound and efficient folding**, which reduces the problem size across recursive rounds without introducing errors or allowing dishonest strategies. Thanks to **mutual correlated agreement**, WHIR preserves not only the distance from the code but also the list of nearby codewords—ensuring robust soundness even under list decoding.

These techniques enable WHIR to achieve verifier times measured in **hundreds of microseconds**, proof sizes that remain **logarithmic in domain size**, and a **modular design** that supports batching, multiple constraints, and compilation from structured IOPs like Σ-IOPs.

As a result, WHIR sets a new benchmark for practical SNARG systems. It is especially impactful for:
- **Hash-based SNARGs**, where verifier performance is traditionally a bottleneck.
- **Multilinear commitment schemes**, where CRS codes match naturally with the algebraic structure of the proof.
- **Post-quantum cryptographic systems**, thanks to WHIR's compatibility with transparent setup and hash-based assumptions.

In summary, WHIR is not just a faster proximity test—it is a versatile and foundational building block for the next generation of fast, practical, and scalable proof systems.