Standard Reed–Solomon Code (RS)

A Reed–Solomon code is a type of error-correcting code that represents a polynomial $f(X)$ evaluated over a fixed domain $L$. It is defined as:

$RS[F, L, d] = \{ f : L \to F \mid f(X) \text{ is a polynomial of degree } < d \}$

where:

Constrained Reed–Solomon Code (CRS)

WHIR introduces constrained Reed–Solomon codes (CRS), which impose additional sum check-like constraints on the polynomial’s evaluations. The CRS definition is:

$CRS[F, L, m, \hat{w}, \sigma] = \{ f \in RS[F, L, m] \mid \sum_{b \in \{0,1\}^m} \hat{w}(\hat{f}(b), b) = \sigma \}$

where:

Example Constraint in CRS

For a multilinear function $\hat{f}$, a common constraint is:

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

This is useful in proving polynomial evaluations without sending the full function.

WHIR Protocol Steps

WHIR reduces the problem size recursively across multiple rounds.