WHIR

tl;dr: Notes on WHIR¹.

Preliminaries

Assuming familiarity with:

• MLEs and $\eq(\X;\b)$ Lagrange polynomials
• Sumcheck
• Basic error correcting codes
  • Rate
  • unique decoding regime
  • $\delta$-far
• IOPPs

Reed-Solomon codes

A Reed-Solomon (RS) code is defined as a set of functions such that, for each function $f$ in the set, there exists a unique, degree $< 2^\term{m}\bydef \term{d}$, univariate polynomial $\hat{f}(X)$ such that $f(x) = \hat{f}(x),\forall x\in\term{\L}$ (a.k.a., $f$ and $\hat{f}$ “agree” over $\L$). $\emph{\L}$ here is the (smooth) evaluation domain of size $\term{n} \bydef 2^\term{\nu}$.

More formally: \begin{align} \term{\RS[\F,\L,m]} &\bydef \left\{ f : \L\rightarrow \F\ \middle|\ \exists! \hat{f} \in \F^{<2^m}[X]\ \text{s.t.}\ f(x) = \hat{f}(x),\forall x\in\L\right\} \end{align}

Alternatively, the definition can require that the underlying polynomial $\hat{f}$ be multilinear: \begin{align} \emph{\RS[\F,\L,m]} &\bydef \left\{ f : \L\rightarrow \F\ \middle|\ \exists! \hat{f} \in \F^{\le 1}[X_1,\ldots,X_m]\ \text{s.t.}\ f(x) = \hat{f}\left(x^{2^0},x^{2^1},\ldots,x^{2^{m-1}}\right),\forall x\in\L\right\} \end{align}

Notes:

1. A codeword here is the function $f : \L \rightarrow \F$, which is really just a vector of the $n$ evaluations of $f$ over $\L$.
2. I think both definitions assume $2^m \le n$.
3. I find both these definition annoying.
   • I think of the “code” as the encoding function with an input message space (i.e., $\F^{<2^m}[X]$) and an output codeword space (i.e., $\F^n$).
   • They seem to be defining the “code” as the set of codewords, by viewing the functions $f$ as size-$n$ vectors $f(x_1),\ldots,f(x_n)$ where $\L \bydef (x_i)_{i\in[n]}$.
   • Perhaps this is normal in coding theory

Since for each $f\in \RS[\F,\L,m]$ there exists a unique multilinear $\hat{f}$, I think we can abuse notation and also talk about the multilinears as $\hat{f}\in\RS[\F,\L,m]$?

Constrained Reed-Solomon codes

A Constrained Reed-Solomon (CRS) code is a Reed-Solomon (sub)code whose underlying $\hat{f}$’s are subject to an additional “sumcheck-like” constraint: \begin{align} \label{eq:sumcheck-like} \sum_{\b \in \binM} \term{\hat{w}}\left(\hat{f}(\b), \b\right) = \term{\sigma} \end{align} where $\emph{\hat{w}}$ is a constraint polynomial in $\F[Z, X_1, \ldots, X_m]$ and $\emph{\sigma}$ is a target (sum).

Figure out degree requirements on $\hat{w}$.

It’s interesting that all $\hat{f}\in \CRS[\F,\L,m,\hat{w},\sigma]$ are subject to the same $\left(\hat{w}(\cdot),\sigma\right)$ constraint!

More formally: \begin{align} \term{\CRS[\F,\L,m,\hat{w},\sigma]} % &\bydef \left\{ % f \in \RS[\F,\L,m] % \ \middle|\ % \exists! \hat{f} \in \F^{\le 1}[X_1,\ldots,X_m]\ \text{s.t.}\ \sum_{\b \in \binM} \hat{w}(\hat{f}(\b), \b) = \sigma % \right\}\\
&\bydef \left\{ f : \L\rightarrow \F \ \middle|\ \overbrace{\exists! \hat{f} \in \F^{\le 1}[X_1,\ldots,X_m]}^\grey{\text{as before for } \RS}\ \text{s.t.}\ \begin{cases} \overbrace{f(x) = \hat{f}\left(x^{2^0},x^{2^1},\ldots,x^{2^{m-1}}\right),\forall x\in\L}^\grey{\text{as before for } \RS} \\
\emph{\sum_{\b \in \binM} \hat{w}\left(\hat{f}(\b), \b\right) = \sigma} \end{cases} \right\} \end{align}

It may be hard to imagine what such constraints look like. Here’s an example of how to set $\hat{w}$ to get a CRS where the underlying $\hat{f}$ polynomials evaluate to $\sigma$ at some point $\z\bydef(z^{2^0}, \ldots, z^{2^{m-1}})$: \begin{align} \hat{w}(Z, X_1, \ldots, X_m) = Z \cdot \eq(\X; (z^{2^0}, \ldots, z^{2^{m-1}})) \end{align} Plugging this into Eq. \ref{eq:sumcheck-like}, we get the following constraint: \begin{align} \sum_{\b \in \binM} \hat{w}\left(\hat{f}(\b), \b\right) &= \sigma\Leftrightarrow\\
\sum_{\b \in \binM} \hat{f}(\b) \cdot \eq(\b; z^{2^0},\ldots,z^{2^{m-1}}) &= \sigma\Leftrightarrow\\
\hat{f}(z^{2^0},\ldots,z^{2^{m-1}}) &= \sigma\Leftrightarrow\\
\hat{f}(\z) &= \sigma \end{align}

(Mutual) correlated agreement

Correlated agreement for Reed–Solomon codes is one of the main technical tools in the analysis of prior IOPPs such as FRI and STIR, and is also at the heart of the security proof of WHIR. – WHIR paper¹

$\RS[\F,\L,m]\bydef\C$ has $(\delta, \varepsilon)$ correlated agreement if for every $f_1,\ldots,f_\ell$, the following holds with probability $1-\varepsilon$:

If there exists $S\subseteq \L, |S| \ge (1-\delta)\cdot|\L|$, such that $f^*_\alpha \bydef \sum_{i=1}^\ell \alpha^{i-1} f_i$ “agrees” with $\C$ on $S$ (i.e., $\exists u\in \C$, s.t. $u(x) = f^*_\alpha(x),\forall x\in S$), then there exists $T\subseteq\L,|T|\ge(1-\delta)\cdot|L|$ such that every $f_i$ “agrees” with $\C$ on $T$.

Are $\delta,\varepsilon\in [0, 1)$? How big is $\ell$? Must it be powers of $\alpha$? (WHIR’s folding seems to be defined for any $\alpha_k$’s.)

WHIR proposes a strengthened variant of correlated agreement (with a simpler definition too):

Define that $f_i$’s are just functions from $\L$ to $\F$.

$\RS[\F,\L,m]\bydef\C$ has $(\delta, \varepsilon)$ mutual correlated agreement if for every $f_1,\ldots,f_\ell$, the following holds with probability $1-\varepsilon$:

For every $S\subseteq \L, |S| \ge (1-\delta)\cdot|\L|$, such that $f^*_\alpha \bydef \sum_{i=1}^\ell \alpha^{i-1} f_i$ “agrees” with $\C$ on $S$, it holds that every $f_i$ “agrees” with $\C$ on $S$.

WHIR paper’s conjecture (informal): Mutual correlated agreement and (standard) correlated agreement hold for essentially the same parameters.

The WHIR paper proves in Section 4.2. that the conjecture above holds in the unique decoding regime (i.e., $\delta \in \left(0,\frac{1-\rho}{2}\right)$, where $\rho\bydef 2^m / n$ is the rate of the code) IIRC, for Johnson bound, $\delta\in\left(0,1-\sqrt{\rho}\right)$. Since the rate $\rho\in(0,1)$, this means $\delta$ is “larger.” Therefore, there’s less restriction on $|S|$ to be large.

Unstructured notes

• The WHIR paper treats Reed-Solomon codes from a multilinear PoV, where codewords are MLEs, not univariates
• “list decoding conjecture” vs. “unique decoding regime”
• Higher folding factor $k\Rightarrow$ slower verifier but smaller proof
  • What about prover?
• Assumes $\F$ has characteristic $\ne 2$ so that $\F$ has a “2-smooth” multiplicative subgroup
• The last iteration of WHIR can either have the verifier directly check the CRS constraint or rely on the prover to help via a sumcheck, depending on what’s faster
  • I think, for efficiency, they stop the proving a bit earlier and don’t go for the full # of iterations?
• Folding “works” means that if $f$ is $\delta$-far from $\RS[\F,\L,m]$ then, w.h.p. over the choice of $\alpha$, $\fold(f, \alpha)$ is $\delta$-far from $\RS[\F,\emph{\L^2}, \emph{m-1}]$
  • This is thanks to correlated agreement and proved in [BCIKS20]²

Folding

For all $f\in\RS[\F,\L,m]$ and $\alpha\randget \F$, define $\fold(f,\alpha)$ as a codeword in $\RS[\F,\L^2, m-1]$

Knobs to turn for wrapping

• The field $\F$
• The rate $\rho\bydef 2^m / n$ of the RS code
• The hash function $H$ (or functions, for different levels of the tree)
• The folding parameter $k$
• The number of WHIR iterations we go for before we early-stop
• The arity of the Merkle tree
  • Could choose higher arity for, say, Poseidon, but binary for Blake3

Links

• Whirlaway, Lambdaclass

References

For cited works, see below 👇👇