# WHIR

## Introduction

[**WHIR**](https://eprint.iacr.org/2024/1586.pdf) is a follow-up paper to [STIR](https://eprint.iacr.org/2024/390), and it has advanced in 2 key aspects: **verification speed** and use **of multilinear polynomials** over univariate polynomials. WHIR can replace existing protocols such as FRI, [STIR](https://eprint.iacr.org/2024/390), and [Basefold](https://eprint.iacr.org/2023/1705.pdf). 

## Background

Please refer to [Basefold](https://fractalyze.gitbook.io/intro/~/revisions/0AAov1j5GF4J6Ca62R1w/zk/stark/basefold) and [STIR](https://fractalyze.gitbook.io/intro/~/revisions/0AAov1j5GF4J6Ca62R1w/zk/stark/stir) in advance.

### Constrained RS (CRS) Code 

An **RS (Reed-Solomon) code** with field $$\mathbb{F}$$, evaluation domain $$\mathcal{L} \subseteq \mathbb{F}$$, and degree $$d$$ can be interpreted   as evaluations over either a univariate polynomial or a multilinear polynomial as follows:

$$
\begin{align\*}
\mathsf{RS}\[\mathbb{F}, \mathcal{L}, m] :&= { f:\mathcal{L} \rightarrow \mathbb{F} : \exist \hat{g} \in \mathbb{F}^{2^m}\[X] \text{ s.t. }\forall x \in \mathcal{L}, f(x) = \hat{g}(x) } \\
&= { f:\mathcal{L} \rightarrow \mathbb{F} : \exist \hat{f} \in \mathbb{F}^{2}\[X\_1, \dots, X\_m] \text{ s.t. }\forall x \in \mathcal{L}, f(x) = \hat{f}(\mathsf{pow}(x, m)) }
\end{align\*}
$$

where $$\mathsf{pow}$$ is defined as:

$$
\mathsf{pow}(x, m) = ({x}^{2^0}, \space \dots, \space {x}^{2^{m - 1}})
$$

A **CRS (Constrained Reed-Solomon) code** extends the traditional RS code by introducing additional evaluation constraint $$\hat{f}(\bm{z})=\sigma$$.

Recall that $$\hat{f}$$ is defined as:

$$
\hat{f}(\bm{X}) = \sum\_{\bm{b}\in {0, 1}^m} \hat{f}(\bm{b}) \cdot \mathsf{eq}(\bm{b}, \bm{X})
$$

To incorporate the additional constraint $$\hat{f}(\bm{z})=\sigma$$, 

$$
\hat{f}(\bm{z}) = \sum\_{\bm{b} \in {0, 1} ^m } \hat{f}(\bm{b}) \cdot \mathsf{eq}(\bm{b}, \bm{z}) = \sum\_{\bm{b} \in {0, 1}^m} \hat{w}(\hat{f}(\bm{b}), \bm{b})  = \sigma
$$

where $$\hat{w}$$ is defined as: (and we call this weight polynomial, which we'll explain later).

$$
\hat{w}(Z, \bm{X}) = Z \cdot \mathsf{eq}(\bm{X}, \bm{z})
$$

Hence, **CRS (Constrained Reed-Solomon) code** code can be written as:

$$
\mathsf{CRS}\[\mathbb{F}, \mathcal{L}, m, \hat{w}, \sigma] := \left{ f \in \mathsf{RS}\[\mathbb{F}, \mathcal{L}, m] : \sum\_{\bm{b} \in {0, 1}^m} \hat{w}\_z(\hat{f}(\bm{b}), \bm{b}) = \sigma \right}
$$

## Protocol Explanation 

### Brief Overview

<figure><img src="https://lh7-rt.googleusercontent.com/docsz/AD_4nXfCRE8M13zX-eZfRO_qbnfFRFK5x0_xNCHbqTlrx7LXHKfXq-jQm15W9OOOTD92_QAskkJP2oiQzuNzgPS3TO0mtm891xaeF_ZwMhT4LQxhvOv6UI0vnM5l_sIuc-4N3you-D_t?key=tVMHVzVEPMgQ0q8cYYDOHXxW" alt=""><figcaption><p>Fig 1. Simple Diagram of the Query Phase in the STIR (left) and WHIR (right) Protocols</p></figcaption></figure>

The **query complexity** in WHIR remains the same as in STIR because the same idea of reducing the rate is applied. WHIR also uses **Out-Of-Domain Sampling**, which is employed in STIR. However, WHIR does not use **Quotienting**, or **Degree Correction**. Instead, it introduces two new methods, described below:

### Sumcheck

For each round in the [**Sumcheck protocol**](https://fractalyze.gitbook.io/intro/~/revisions/0AAov1j5GF4J6Ca62R1w/primitives/sumcheck), the verifier provides a random value, and the prover reduces the number of variables by one. With each variable reduction, the degree is also reduced by one. After $$k$$ rounds of sumcheck, $$k$$ variables can be eliminated, reducing the degree by $$k$$. This is the folding method used in WHIR, differing from the $$k$$-fold approach in STIR.

For example, when $$k = 2$$, the process operates as follows. First, let us assume that the evaluation constraint claimed by the CRS in the previous round is as follows:

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

1. The prover provides the verifier with a univariate polynomial $$\hat{h}\_0$$ defined as follows to prove the constraint:

$$
\hat{h}*{0}(X) = \sum*{\bm{b} \in {0, 1}^{m-1}} \hat{w}(\hat{f}(X, \bm{b}), X, \bm{b})
$$

2. The verifier then checks the following condition and rejects if the two sides are not equal:

$$
\hat{h}\_0(0) + \hat{h}\_0(1) \stackrel{?}= \sigma
$$

3. The verifier samples a random $$\alpha\_0$$​ and sends it to the prover.
4. The prover, using the random value $$\alpha\_0$$, provides the verifier with another univariate polynomial $$\hat{h}\_1$$₁ defined as follows:

$$
\hat{h}*1(X) = \sum*{\bm{b} \in {0, 1}^{m-2}} \hat{w}(\hat{f}(\alpha\_0, X, \bm{b}), \alpha\_0, X, \bm{b})
$$

5. The verifier checks the following condition and rejects if the two sides are not equal:

$$
\hat{h}\_1(0) + \hat{h}\_1(1) \stackrel{?}= \hat{h}\_0(\alpha\_0)
$$

5. The verifier samples a random value $$\alpha\_1$$​ and sends it to the prover.
6. The folded polynomial $$\hat{g}$$ can then be constructed as follows:

$$
\hat{g}(\bm{X}) = \hat{f}(\alpha\_0, \alpha\_1, \bm{X})
$$

### Weight Polynomial

#### Out-Of-Domain Sampling

1. The verifier samples random value $$z\_0 \stackrel{$}\leftarrow \mathbb{F}$$.
2. The prover sends $$y\_0 = \hat{g}(\mathsf{pow}(z\_0, m - k))$$.

#### Shift queries

1. The verifier samples random values $$z\_1, \dots, z\_{t\_i} \stackrel{$}\leftarrow \mathcal{L}\_i$$. The $$\mathcal{L}\_i$$ is the evaluation domain in each round $$i$$, and the value $$t$$ represents the number of queries required in each round $$i$$, determined by the security parameter $$\lambda$$.&#x20;
2. For each $$i \in \[t]$$, the verifier obtains $$y\_i$$ by querying $$f$$:

$$
y\_i = \mathsf{Fold}(f, \alpha\_0, \alpha\_1 )(z\_i)
$$

and $$\mathsf{Fold}$$ is defined as:

$$
\mathsf{Fold}(f, \alpha\_i, \dots, \alpha\_{j})(y) = \begin{cases}
\mathsf{Fold}(\mathsf{Fold}(f, \alpha\_i), \alpha\_{i + 1}, \dots, \alpha\_{j})(y^2) &\text{ if } i < j \\
\frac{f(x)  + f(-x)}{2} +\alpha\_i \cdot \frac{f(x) - f(-x)}{2 \cdot x} & \text { if } i = j
\end{cases}
$$

where $$y = x^2 = (-x)^2$$.

#### Recursive Claims

1. The verifier samples random value $$\gamma \stackrel{$}\leftarrow \mathbb{F}$$.
2. Using the random values and the computed results, the prover and the verifier constructs $$\hat{w}'$$ and $$\sigma'$$, which will be used in the new $$\mathsf{CRS}\[\mathbb{F}, \mathcal{L}, m - k, \hat{w}', \sigma']$$.

$$
\hat{w}'(Z, \bm{X}) := \hat{w}(Z, \alpha\_0, \dots, \alpha\_{k-1},  \bm{X}) + Z \cdot \sum\_{i = 0}^t \gamma^{i+1}\cdot \mathsf{eq}(\bm{X}, \bm{z\_i}) \\
\sigma' := \hat{h}*{k-1}(\alpha*{k-1}) + \sum\_{i = 0}^t \gamma^{i+1} \cdot y\_i
$$

### The Full WHIR Protocol

#### Parameters

* a constrained Reed-Solomon code $$\mathsf{CRS}\[\mathbb{F}, \mathcal{L}\_0, m\_0, \hat{w}\_0, \sigma\_0]$$;
* an iteration count $$M \in \mathbb{N}$$;
* folding parameter $$k\_0, \dots, k\_{M-1}$$ such that $$\sum\_{i=0}^{M-1}k\_i \le m$$;
* evaluation domain $$\mathcal{L}*1, \dots, \mathcal{L}*{M-1} \sube \mathbb{F}$$ where $$\mathcal{L}\_i$$ is a smooth coset of $$\mathbb{F}^\*$$ with order $$|\mathcal{L}\_i| \ge 2^{m\_i}$$;
* repetition parameters $$t\_0, \dots, t\_{M-1}$$ with $$t\_i \le |\mathcal{L}\_i|$$;
* define $$m\_0 := m$$ and $$m\_i := m - \sum\_{j\<i}k\_j$$;
* define $$d^\* := 1 + \deg\_Z(\hat{w}*0) + \max*{i \in \[m\_0]} \deg\_{X\_i}(\hat{w}\_0)$$ and $$d := \max { d^\*, 3}$$.

#### Inputs

The verifier has oracle access to $$f\_0: \mathcal{L}\_0 \rightarrow \mathbb{F}$$. In the honest case, $$f\_0 \in \mathsf{CRS}\[\mathbb{F}, \mathcal{L}\_0, m\_0, \hat{w}\_0, \sigma\_0]$$ and the prover receives $$\hat{f}\_0 \in \mathbb{F}^{< 2} \[X\_1, \dots, X\_m]$$ such that $$f\_0 = \hat{f}\_0(\mathcal{L}*0)$$ and $$\sum*{\bm{b} \in {0,1}^{m\_0}} \hat{w}\_0(\hat{f}\_0(\bm{b}), \bm{b} ) = \sigma\_0$$.

#### Query(Prover side)

1. **Initial sumcheck:** Set $$\pmb{\alpha}\_0 := \emptyset$$. For $$\ell = 1, \dots, k\_0$$:&#x20;
   1. The prover sends $$\hat{h}*{0, \ell} \in \mathbb{F}^{< d^\*}\[X]$$. In the honest case, $$\hat{h}*{0, \ell} := \sum\_{\bm{b} \in {0, 1}^{m\_0 - \ell - 1}} \hat{w}\_0(\hat{f}\_0(\alpha\_0, X, \bm{b}), \bm{\alpha}\_0, X, \bm{b})$$.<br>
   2. The verifier samples $$\alpha\_{0, \ell} \leftarrow \mathbb{F}$$. Append $$\alpha\_{0, \ell}$$ to set $$\bm{\alpha}\_0$$.
2. **Main loop**: For $$i = 1, \dots, M - 1$$:&#x20;
   1. **Send folded function**: The prover sends $$f\_i: \mathcal{L}*i \rightarrow \mathbb{F}$$. In the honest case, $$f\_i$$ is the evaluation of $$\hat{f}*i := \hat{f}*{i-1}(\bm{\alpha}*{i-1}, \cdot)$$ over $$\mathcal{L}\_i$$.
   2. **Out-of-domain sample**: The verifier sends $$z\_{i, 0} \stackrel{$}\leftarrow \mathbb{F}$$. Set $$\bm{z}*{i, 0} := \mathsf{pow}(z*{i, 0}, m\_i)$$.
   3. **Out-of-domain reply**: The prover sends $$y\_{i, 0} \in \mathbb{F}$$. In the honest case, $$y\_{i, 0} := \hat{f}*i(\mathbb{z}*{i, 0})$$.
   4. **Shift message**: The verifier samples $$z\_{i, 1}, \dots, z\_{i, t\_ {i- 1}} \stackrel{$}\leftarrow \mathcal{L}*{i-1}^{(2^{k*{i - 1}})}$$ and $$\gamma\_i \stackrel{$}\leftarrow \mathbb{F}$$. Set $$\bm{z}*{i, j} := \mathsf{pow}(z*{i, j}, m\_i)$$.
   5. **Sumcheck rounds:** Set $$\pmb{\alpha}\_0 := \emptyset$$. For $$\ell = 1, \dots, k\_i$$:&#x20;
      1. The prover sends $$\hat{h}*{i, \ell} \in \mathbb{F}^{< d}\[X]$$. In the honest case, $$\hat{h}*{i, \ell}(X) := \sum\_{\bm{b} \in {0, 1}^{m\_i - \ell - 1}} \hat{w}*i(\hat{f}*i(\alpha\_i, X, \bm{b}), \bm{\alpha}*i, X, \bm{b})$$ where $$\hat{w}*i(Z, X\_1, \dots, X*{m\_i}) := \hat{w}*{i -1}(Z, \bm{\alpha}*{i-1}, X\_1, \dots, X*{m\_i}) + Z \cdot \sum\_{j = 0}^{t\_{i-1}}\cdot \mathsf{eq}(\bm{z}*{i, j} , (X\_1, \dots, X*{m\_i}))$$.
      2. The verifier samples $$\alpha\_{i, \ell} \leftarrow \mathbb{F}$$. Append $$\alpha\_{i, \ell}$$ to set $$\bm{\alpha}\_i$$.
3. **Send final polynomial**: The prover sends $$\hat{f}*M \in \mathbb{F}^{<2}\[X\_1, \dots, X*{m\_M}]$$. In the honest case $$\hat{f}*M := \hat{f}*{M-1}(\bm{\alpha}\_{M-1}, \cdot)$$.
4. **Sample final randomness**: The verifier samples $$r\_1^{\mathsf{fin}}, \dots, r\_{t\_{M-1}}^{\mathsf{fin}} \stackrel{$}{\leftarrow} \mathcal{L}\_{M - 1}^{(2^{k \_{M - 1}})}$$.

#### Query(Verifier side)

1. **Check initial sumcheck**:
   1. Check that $$\sum\_{b \in {0, 1}} \hat{h}\_{0,1}(b) = \sigma\_0$$.
   2. Check that $$\sum\_{b \in {0, 1}} \hat{h}*{0, \ell}(b) = \hat{h}*{0, \ell-1}(\alpha\_{0, \ell-1})$$ for $$\ell \in {2, \dots, k\_0}$$.
2. **Check main loop**: For $$i = 1, \dots, M - 1$$:&#x20;
   1. Let $$g\_{i-1} := \mathsf{Fold}(f\_{i-1}, \bm{\alpha}\_{i-1})$$.
   2. Compute the points $${g\_{i-1}(z\_{i, j})}*{j \in \[t*{i-1}]}$$ by querying $$f\_{i-1}$$ at the appropriate locations.
   3. Check that $$\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}}  \cdot g\_{i-1}(z\_{i, j})$$.
   4. Check that $$\sum\_{b \in {0, 1}} \hat{h}*{i, \ell}(b) = \hat{h}*{i, \ell -1}(\alpha\_{i, \ell - 1})$$ for every $$\ell \in {2, \dots, k\_i}$$.
3. **Check final polynomial**:
   1. Check that, for every $$\ell \in \[t\_{M-1}]$$, $$\hat{f}*M(\bm{r}^{\mathsf{fin}}*\ell) = g\_{M-1}(r^{\mathsf{fin}}*\ell)$$ where $$\bm{r}*\ell^{\mathsf{fin}} := \mathsf{pow}(r^\mathsf{fin}\_\ell, m\_M)$$.
   2. For $$i = 1, \dots, M - 1$$ set $$\hat{w}*i(Z, X\_1, \dots, X*{m\_i}) := \hat{w}*{i-1}(Z, \bm{\alpha}*{i-1}, X\_1, \dots, X\_{m\_i}) + Z \cdot \sum\_{j=0}^{t\_{i-1}} \gamma\_i^{j+1} \cdot \mathsf{eq}(\bm{z}*{i,j}, X\_1, \dots, X*{m\_i})$$
   3. Check that $$\sum\_{\bm{b} \in {0, 1}^{m\_M}} \hat{w}*{M-1}(\hat{f}*M(\bm{b}), \bm{\alpha}*{M-1}, \bm{b}) = \hat{h}*{M-1, k\_{M-1}}(\alpha\_{M-1, k\_{M-1}})$$.

## Conclusion

<figure><img src="https://lh7-rt.googleusercontent.com/docsz/AD_4nXf8MIKbqeEjTXWgH5mDJLGp42iGfMYRg_tngPKqytFGf-QY2aRFp_zz7pexhst-kzPl-dV5ZsviwQLLWbXQkdwIt1whbOis3FlbDceP7PP6AGJVC4UfzqxX7Vwu-778SnHnLCEL?key=tVMHVzVEPMgQ0q8cYYDOHXxW" alt=""><figcaption><p>Fig 2. Comparison Table among BaseFold, FRI, STIR and WHIR</p></figcaption></figure>

The figure above is a table comparing BaseFold, FRI, STIR, and WHIR. It shows that WHIR, like STIR, has **the lowest query complexity**. Additionally, WHIR also achieves **the lowest verifier time complexity**. (For details on how WHIR's verifier time complexity is calculated, refer to Section 2.1.4, "Verifier Efficiency," in the paper.)&#x20;

<figure><img src="https://lh7-rt.googleusercontent.com/docsz/AD_4nXefS0md7Fw24T3Pg5tHmKDOzCahUz1rL_frT0uZApKor_9l3Jb8A3SBYlxWVuQ5R8KrkKZLP9gyNfS6KZF7vGjEgzqthDY_01ie5FHnZKq7yPs8BS6Dp7pce2Vf6lurDNJNbo0w?key=tVMHVzVEPMgQ0q8cYYDOHXxW" alt=""><figcaption><p>Fig 3. Benchmark Result among FRI, STIR and WHIR</p></figcaption></figure>

The benchmarking results, as derived from the table above, show a similar trend. In the [ZK Summit 12 presentation](https://www.youtube.com/watch?v=iPKzmxLDdII), Eylon Yogev highlighted that WHIR has **lower on-chain gas costs** than **Groth16**. Given that Groth16 is widely recognized for its low on-chain gas costs, this suggests an exciting possibility: we may not need to combine STARK-based proof generation with Groth16 verification in the future. This could mark the beginning of a more efficient era, though significant progress is still needed to make it a reality. For now, Groth16 verification remains the most cost-effective option. For more details, see [this discussion](https://ethresear.ch/t/on-the-gas-efficiency-of-the-whir-polynomial-commitment-scheme/21301).

## References

* <https://gfenzi.io/papers/whir/>

> Written by [Ryan Kim](https://app.gitbook.com/u/cPk8gft4tSd0Obi6ARBfoQ16SqG2 "mention") of Fractalyze