WHIR

Presentation: https://youtu.be/JdHqAIMihxg

Last updated 2 months ago

WHIR

Presentation: https://youtu.be/JdHqAIMihxg

Introduction

is a follow-up paper to , 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, , and .

Background

Please refer to and 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

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 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

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})

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

The verifier samples a random $\alpha_0$ and sends it to the prover.
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})

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)

The verifier samples a random value $\alpha_1$ and sends it to the prover.
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

The verifier samples random value $z_0 \stackrel{\$}\leftarrow \mathbb{F}$ .
The prover sends $y_0 = \hat{g}(\mathsf{pow}(z_0, m - k))$ .

Shift queries

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$ .
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

The verifier samples random value $\gamma \stackrel{\$}\leftarrow \mathbb{F}$ .
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)

Initial sumcheck: Set $\pmb{\alpha}_0 := \emptyset$ . For $\ell = 1, \dots, k_0$ :
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})$ .
2. The verifier samples $\alpha_{0, \ell} \leftarrow \mathbb{F}$ . Append $\alpha_{0, \ell}$ to set $\bm{\alpha}_0$ .
Main loop: For $i = 1, \dots, M - 1$ :
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$ :
  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$ .
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)$ .
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)

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\}$ .
Check main loop: For $i = 1, \dots, M - 1$ :
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\}$ .
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

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.)

References

PreviousSTIR NextDistributed ZK

Last updated 2 months ago

Introduction

Background

Please refer to and in advance.

Constrained RS (CRS) Code

\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

Sumcheck

For each round in the , 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

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})

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

The verifier samples a random $\alpha_0$ and sends it to the prover.
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})

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)

The verifier samples a random value $\alpha_1$ and sends it to the prover.
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

The verifier samples random value $z_0 \stackrel{\$}\leftarrow \mathbb{F}$ .
The prover sends $y_0 = \hat{g}(\mathsf{pow}(z_0, m - k))$ .

Shift queries

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$ .
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

The verifier samples random value $\gamma \stackrel{\$}\leftarrow \mathbb{F}$ .
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

Query(Prover side)

Initial sumcheck: Set $\pmb{\alpha}_0 := \emptyset$ . For $\ell = 1, \dots, k_0$ :
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})$ .
2. The verifier samples $\alpha_{0, \ell} \leftarrow \mathbb{F}$ . Append $\alpha_{0, \ell}$ to set $\bm{\alpha}_0$ .
Main loop: For $i = 1, \dots, M - 1$ :
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$ :
  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$ .
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)$ .
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)

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\}$ .
Check main loop: For $i = 1, \dots, M - 1$ :
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\}$ .
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

The benchmarking results, as derived from the table above, show a similar trend. In the , 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 .

References

Written by from