WHIR: Reed-Solomon Proximity Testing with Super-Fast Verification
本篇文章主要介绍 WHIR (Weights Help Improving Rate) 协议[ACFY24b]。和 FRI[BBHR18]、STIR [ACFY24a] 以及 BaseFold [ZCF24] 协议一样，WHIR 也是一个 IOPP 协议，但其有较小的查询复杂度以及比较快的验证时间。论文 [ACFY24b] 中提到 WHIR 的 verifier 通常运行几百微秒(1 微秒 = 10-6 秒)，而其他协议的 verifier 则需要几毫秒 (1 毫秒 = 10-3 秒)。另外 WHIR 是针对 constrained Reed-Solomon codes (CRS) 的 IOPP 协议，CRS 使得 WHIR 同时支持对多元线性多项式和对单变量多项式的查询，这也是为什么 WHIR 可以同时和 BaseFold、FRI 以及 STIR 进行比较[ACFY24b]。整体上来看，WHIR 结合了 BaseFold 和 STIR 的思想，使得 WHIR 协议能在不牺牲 Prover 效率以及 argument 大小的情况下，支持多元线性多项式，同时也有较小的查询复杂度。
从一元多项式到多元线性多项式 ¶ 对于一个有限域 F \mathbb{F} F L ⊆ F \mathcal{L} \subseteq \mathbb{F} L ⊆ F d ∈ N d \in \mathbb{N} d ∈ N F \mathbb{F} F d d d L \mathcal{L} L R S [ F , L , d ] \mathrm{RS}[\mathbb{F}, \mathcal{L}, d] RS [ F , L , d ] L \mathcal{L} L F ∗ \mathbb{F}^* F ∗ L \mathcal{L} L d = 2 m d = 2^m d = 2 m m m m
先举一个 d = 2 3 d = 2^3 d = 2 3
f ( x ) = a 0 + a 1 x + a 2 x 2 + a 3 x 3 + a 4 x 4 + a 5 x 5 + a 6 x 6 + a 7 x 7 f(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + a_4 x^4 + a_5 x^5 + a_6 x^6 + a_7 x^7 f ( x ) = a 0 + a 1 x + a 2 x 2 + a 3 x 3 + a 4 x 4 + a 5 x 5 + a 6 x 6 + a 7 x 7 令 X 1 = x , X 2 = x 2 , X 3 = x 4 X_1 = x, X_2 = x^2 , X_3 = x^4 X 1 = x , X 2 = x 2 , X 3 = x 4 f ( x ) f(x) f ( x )
f ( x ) = a 0 + a 1 x + a 2 x 2 + a 3 x 3 + a 4 x 4 + a 5 x 5 + a 6 x 6 + a 7 x 7 = a 0 + a 1 X 1 + a 2 X 2 + a 3 X 1 X 2 + a 4 X 3 + a 5 X 1 X 2 + a 6 X 1 X 3 + a 7 X 1 X 2 X 3 \begin{aligned}
f(x) & = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + a_4 x^4 + a_5 x^5 + a_6 x^6 + a_7 x^7 \\
& = a_0 + a_1 X_1 + a_2 X_2 + a_3 X_1X_2 + a_4 X_3 + a_5 X_1 X_2 + a_6 X_1 X_3 + a_7 X_1 X_2 X_3
\end{aligned} f ( x ) = a 0 + a 1 x + a 2 x 2 + a 3 x 3 + a 4 x 4 + a 5 x 5 + a 6 x 6 + a 7 x 7 = a 0 + a 1 X 1 + a 2 X 2 + a 3 X 1 X 2 + a 4 X 3 + a 5 X 1 X 2 + a 6 X 1 X 3 + a 7 X 1 X 2 X 3 记新的多元线性多项式为
f ^ ( X 1 , X 2 , X 3 ) = a 0 + a 1 X 1 + a 2 X 2 + a 3 X 1 X 2 + a 4 X 3 + a 5 X 1 X 2 + a 6 X 1 X 3 + a 7 X 1 X 2 X 3 \hat{f}(X_1, X_2, X_3) = a_0 + a_1 X_1 + a_2 X_2 + a_3 X_1X_2 + a_4 X_3 + a_5 X_1 X_2 + a_6 X_1 X_3 + a_7 X_1 X_2 X_3 f ^ ( X 1 , X 2 , X 3 ) = a 0 + a 1 X 1 + a 2 X 2 + a 3 X 1 X 2 + a 4 X 3 + a 5 X 1 X 2 + a 6 X 1 X 3 + a 7 X 1 X 2 X 3 这样 f ( x ) f(x) f ( x ) X 1 = x , X 2 = x 2 , X 3 = x 4 X_1 = x, X_2 = x^2 , X_3 = x^4 X 1 = x , X 2 = x 2 , X 3 = x 4
对于 RS code R S [ F , L , d ] \mathrm{RS}[\mathbb{F}, \mathcal{L}, d] RS [ F , L , d ]
R S [ F , L , d ] : = { f : L → F : ∃ g ^ ∈ F < 2 m [ X ] s.t. ∀ x ∈ L , f ( x ) = g ^ ( x ) } = { f : L → F : ∃ f ^ ∈ F < 2 [ X 1 , … , X m ] s.t. ∀ x ∈ L , f ( x ) = f ^ ( x 2 0 , x 2 1 , … , x 2 m − 1 ) } \begin{aligned}
\mathrm{RS}[\mathbb{F}, \mathcal{L}, d] & := \{f: \mathcal{L} \rightarrow \mathbb{F}: \exists \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}: \exists \hat{f} \in \mathbb{F}^{< 2}[X_1, \ldots, X_m] \text{ s.t. } \forall x \in \mathcal{L}, f(x) = \hat{f}(x^{2^0}, x^{2^1},\ldots, x^{2^{m-1}})\}
\end{aligned} RS [ F , L , d ] := { f : L → F : ∃ g ^ ∈ F < 2 m [ X ] s.t. ∀ x ∈ L , f ( x ) = g ^ ( x )} = { f : L → F : ∃ f ^ ∈ F < 2 [ X 1 , … , X m ] s.t. ∀ x ∈ L , f ( x ) = f ^ ( x 2 0 , x 2 1 , … , x 2 m − 1 )} 上式中的 g ^ ( x ) \hat{g}(x) g ^ ( x ) f ^ ( X 1 , … , X m ) \hat{f}(X_1, \ldots, X_m) f ^ ( X 1 , … , X m ) m m m
另外，和在 FRI 协议中一致，用随机数 α 1 \alpha_1 α 1 α 1 \alpha_1 α 1
例如对上述的 f ( x ) = a 0 + a 1 x + a 2 x 2 + a 3 x 3 + a 4 x 4 + a 5 x 5 + a 6 x 6 + a 7 x 7 f(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + a_4 x^4 + a_5 x^5 + a_6 x^6 + a_7 x^7 f ( x ) = a 0 + a 1 x + a 2 x 2 + a 3 x 3 + a 4 x 4 + a 5 x 5 + a 6 x 6 + a 7 x 7 α 1 \alpha_1 α 1
f ( x ) = a 0 + a 2 x 2 + a 4 x 4 + a 6 x 6 + x ( a 1 + a 3 x 2 + a 5 x 4 + a 7 x 6 ) : = f 1 ( x 2 ) + x f 2 ( x 2 ) \begin{aligned}
f(x) & = a_0 + a_2 x^2 + a_4 x^4 + a_6 x^6 + x (a_1 + a_3 x^2 + a_5 x^4 + a_7 x^6) \\
& := f_1(x^2) + x f_2(x^2)
\end{aligned} f ( x ) = a 0 + a 2 x 2 + a 4 x 4 + a 6 x 6 + x ( a 1 + a 3 x 2 + a 5 x 4 + a 7 x 6 ) := f 1 ( x 2 ) + x f 2 ( x 2 ) 折叠之后的多项式为
f ( 1 ) ( x ) = f 1 ( x ) + α 1 f 2 ( x ) = a 0 + a 2 x + a 4 x 2 + a 6 x 3 + α 1 ( a 1 + a 3 x + a 5 x 2 + a 7 x 3 ) = a 0 + a 2 X 1 + a 4 X 2 + a 6 X 1 X 2 + α 1 ( a 1 + a 3 X 1 + a 5 X 2 + a 7 X 1 X 2 ) \begin{aligned}
f^{(1)}(x) & = f_1(x) + \alpha_1 f_2(x) \\
& = a_0 + a_2 x + a_4 x^2 + a_6 x^3 + \alpha_1 (a_1 + a_3 x + a_5 x^2 + a_7 x^3) \\
& = a_0 + a_2 X_1 + a_4 X_2 + a_6 X_1X_2 + \alpha_1 (a_1 + a_3 X_1 + a_5 X_2 + a_7 X_1X_2)
\end{aligned} f ( 1 ) ( x ) = f 1 ( x ) + α 1 f 2 ( x ) = a 0 + a 2 x + a 4 x 2 + a 6 x 3 + α 1 ( a 1 + a 3 x + a 5 x 2 + a 7 x 3 ) = a 0 + a 2 X 1 + a 4 X 2 + a 6 X 1 X 2 + α 1 ( a 1 + a 3 X 1 + a 5 X 2 + a 7 X 1 X 2 ) 其等价于对原来的多元多项式 f ^ ( X 1 , X 2 , X 3 ) \hat{f}(X_1,X_2,X_3) f ^ ( X 1 , X 2 , X 3 )
先将 X 1 X_1 X 1 α 1 \alpha_1 α 1 f ^ ( α 1 , X 2 , X 3 ) = a 0 + a 1 ⋅ α 1 + a 2 X 2 + a 3 ⋅ α 1 X 2 + a 4 X 3 + a 5 ⋅ α 1 X 2 + a 6 X 2 X 3 + a 7 ⋅ α 1 X 2 X 3 = a 0 + a 2 X 2 + a 4 X 3 + a 6 X 2 X 3 + α 1 ( a 1 + a 3 X 2 + a 5 X 2 + a 7 X 2 X 3 ) \begin{aligned}
\hat{f}(\alpha_1,X_2,X_3) & = a_0 + a_1 \cdot \alpha_1 + a_2 X_2 + a_3 \cdot \alpha_1 X_2 + a_4 X_3 + a_5 \cdot \alpha_1 X_2 + a_6 X_2 X_3 + a_7 \cdot \alpha_1 X_2 X_3 \\
& = a_0 + a_2 X_2 + a_4 X_3 + a_6 X_2 X_3 + \alpha_1 (a_1 + a_3 X_2 + a_5 X_2 + a_7 X_2 X_3)
\end{aligned} f ^ ( α 1 , X 2 , X 3 ) = a 0 + a 1 ⋅ α 1 + a 2 X 2 + a 3 ⋅ α 1 X 2 + a 4 X 3 + a 5 ⋅ α 1 X 2 + a 6 X 2 X 3 + a 7 ⋅ α 1 X 2 X 3 = a 0 + a 2 X 2 + a 4 X 3 + a 6 X 2 X 3 + α 1 ( a 1 + a 3 X 2 + a 5 X 2 + a 7 X 2 X 3 ) 令新的变量 X 1 = X 2 X_1 = X_2 X 1 = X 2 X 2 = X 3 X_2 = X_3 X 2 = X 3 f ^ ( 1 ) ( X 1 , X 2 ) = a 0 + a 2 X 1 + a 4 X 2 + a 6 X 1 X 2 + α 1 ( a 1 + a 3 X 1 + a 5 X 2 + a 7 X 1 X 2 ) = f ( 1 ) ( x ) \begin{aligned}
\hat{f}^{(1)}(X_1, X_2) & = a_0 + a_2 X_1 + a_4 X_2 + a_6 X_1 X_2 + \alpha_1 (a_1 + a_3 X_1 + a_5 X_2 + a_7 X_1 X_2) \\
& = f^{(1)}(x)
\end{aligned} f ^ ( 1 ) ( X 1 , X 2 ) = a 0 + a 2 X 1 + a 4 X 2 + a 6 X 1 X 2 + α 1 ( a 1 + a 3 X 1 + a 5 X 2 + a 7 X 1 X 2 ) = f ( 1 ) ( x ) 可以看出两种折叠方式得到的多项式是等价的，只是 f ( 1 ) ( x ) f^{(1)}(x) f ( 1 ) ( x ) f ^ ( 1 ) ( X 1 , X 2 ) \hat{f}^{(1)}(X_1, X_2) f ^ ( 1 ) ( X 1 , X 2 )
如果要对原来的多项式 f ( x ) f(x) f ( x ) f ( 1 ) ( x ) f^{(1)}(x) f ( 1 ) ( x )
f ( 1 ) ( x ) = a 0 + a 2 x + a 4 x 2 + a 6 x 3 + α 1 ( a 1 + a 3 x + a 5 x 2 + a 7 x 3 ) = ( a 0 + α 1 a 1 ) + ( a 2 + α 1 a 3 ) ⋅ x + ( a 4 + α 1 a 5 ) ⋅ x 2 + ( a 6 + α 1 a 7 ) ⋅ x 3 = ( ( a 0 + α 1 a 1 ) + ( a 4 + α 1 a 5 ) ⋅ x 2 ) + x ⋅ ( ( a 2 + α 1 a 3 ) + ( a 6 + α 1 a 7 ) ⋅ x 2 ) : = f 1 ( 1 ) ( x 2 ) + x f 2 ( 1 ) ( x 2 ) \begin{aligned}
f^{(1)}(x) & = a_0 + a_2 x + a_4 x^2 + a_6 x^3 + \alpha_1 (a_1 + a_3 x + a_5 x^2 + a_7 x^3) \\
& = (a_0 + \alpha_1 a_1) + (a_2 + \alpha_1 a_3) \cdot x + (a_4 + \alpha_1 a_5) \cdot x^2 + (a_6 + \alpha_1 a_7) \cdot x^3 \\
& = ((a_0 + \alpha_1 a_1) + (a_4 + \alpha_1 a_5) \cdot x^2) + x \cdot ((a_2 + \alpha_1 a_3) + (a_6 + \alpha_1 a_7) \cdot x^2) \\
& := f_1^{(1)}(x^2) + x f_2^{(1)}(x^2)
\end{aligned} f ( 1 ) ( x ) = a 0 + a 2 x + a 4 x 2 + a 6 x 3 + α 1 ( a 1 + a 3 x + a 5 x 2 + a 7 x 3 ) = ( a 0 + α 1 a 1 ) + ( a 2 + α 1 a 3 ) ⋅ x + ( a 4 + α 1 a 5 ) ⋅ x 2 + ( a 6 + α 1 a 7 ) ⋅ x 3 = (( a 0 + α 1 a 1 ) + ( a 4 + α 1 a 5 ) ⋅ x 2 ) + x ⋅ (( a 2 + α 1 a 3 ) + ( a 6 + α 1 a 7 ) ⋅ x 2 ) := f 1 ( 1 ) ( x 2 ) + x f 2 ( 1 ) ( x 2 ) 用随机数 α 2 \alpha_2 α 2
f ( 2 ) ( x ) = f 1 ( 1 ) ( x ) + α 2 f 2 ( 1 ) ( x ) = ( ( a 0 + α 1 a 1 ) + ( a 4 + α 1 a 5 ) x ) + α 2 ( ( a 2 + α 1 a 3 ) + ( a 6 + α 1 a 7 ) x ) = ( ( a 0 + α 1 a 1 ) + ( a 4 + α 1 a 5 ) X 1 ) + α 2 ( ( a 2 + α 1 a 3 ) + ( a 6 + α 1 a 7 ) X 1 ) \begin{aligned}
f^{(2)}(x) & = f_1^{(1)}(x) + \alpha_2 f_2^{(1)}(x) \\
& = ((a_0 + \alpha_1 a_1) + (a_4 + \alpha_1 a_5) x) + \alpha_2 ((a_2 + \alpha_1 a_3) + (a_6 + \alpha_1 a_7) x) \\
& = ((a_0 + \alpha_1 a_1) + (a_4 + \alpha_1 a_5) X_1) + \alpha_2 ((a_2 + \alpha_1 a_3) + (a_6 + \alpha_1 a_7) X_1)
\end{aligned} f ( 2 ) ( x ) = f 1 ( 1 ) ( x ) + α 2 f 2 ( 1 ) ( x ) = (( a 0 + α 1 a 1 ) + ( a 4 + α 1 a 5 ) x ) + α 2 (( a 2 + α 1 a 3 ) + ( a 6 + α 1 a 7 ) x ) = (( a 0 + α 1 a 1 ) + ( a 4 + α 1 a 5 ) X 1 ) + α 2 (( a 2 + α 1 a 3 ) + ( a 6 + α 1 a 7 ) X 1 ) 从多元线性多项式的角度来看，可以对 2 折之后的多元线性多项式 f ^ ( 1 ) ( X 1 , X 2 ) \hat{f}^{(1)}(X_1, X_2) f ^ ( 1 ) ( X 1 , X 2 )
将 X 1 X_1 X 1 α 2 \alpha_2 α 2 f ^ ( 1 ) ( α 2 , X 2 ) = a 0 + a 2 α 2 + a 4 X 2 + a 6 α 2 X 2 + α 1 ( a 1 + a 3 α 2 + a 5 X 2 + a 7 α 2 X 2 ) = ( ( a 0 + α 1 a 1 ) + ( a 4 + α 1 a 5 ) X 2 ) + α 2 ( ( a 2 + α 1 a 3 ) + ( a 6 + α 1 a 7 ) X 2 ) \begin{aligned}
\hat{f}^{(1)}(\alpha_2, X_2) & = a_0 + a_2 \alpha_2 + a_4 X_2 + a_6 \alpha_2 X_2 + \alpha_1 (a_1 + a_3 \alpha_2 + a_5 X_2 + a_7 \alpha_2 X_2) \\
& = ((a_0 + \alpha_1 a_1) + (a_4 + \alpha_1 a_5) X_2) + \alpha_2 ((a_2 + \alpha_1 a_3) + (a_6 + \alpha_1 a_7) X_2)
\end{aligned} f ^ ( 1 ) ( α 2 , X 2 ) = a 0 + a 2 α 2 + a 4 X 2 + a 6 α 2 X 2 + α 1 ( a 1 + a 3 α 2 + a 5 X 2 + a 7 α 2 X 2 ) = (( a 0 + α 1 a 1 ) + ( a 4 + α 1 a 5 ) X 2 ) + α 2 (( a 2 + α 1 a 3 ) + ( a 6 + α 1 a 7 ) X 2 ) 令新的变量 X 1 = X 2 X_1 = X_2 X 1 = X 2 f ^ ( 2 ) ( X 1 ) = ( ( a 0 + α 1 a 1 ) + ( a 4 + α 1 a 5 ) X 1 ) + α 2 ( ( a 2 + α 1 a 3 ) + ( a 6 + α 1 a 7 ) X 1 ) \hat{f}^{(2)}(X_1) = ((a_0 + \alpha_1 a_1) + (a_4 + \alpha_1 a_5) X_1) + \alpha_2 ((a_2 + \alpha_1 a_3) + (a_6 + \alpha_1 a_7) X_1) f ^ ( 2 ) ( X 1 ) = (( a 0 + α 1 a 1 ) + ( a 4 + α 1 a 5 ) X 1 ) + α 2 (( a 2 + α 1 a 3 ) + ( a 6 + α 1 a 7 ) X 1 ) 可以发现对于多折，用一元多项式进行折叠和直接用多元线性多项式进行折叠是等价的。用随机数 ( α 1 , α 2 ) (\alpha_1, \alpha_2) ( α 1 , α 2 ) f ^ ( 2 ) ( X 1 ) = f ^ ( α 1 , α 2 , X 1 ) \hat{f}^{(2)}(X_1) = \hat{f}(\alpha_1, \alpha_2, X_1) f ^ ( 2 ) ( X 1 ) = f ^ ( α 1 , α 2 , X 1 )
下面引入论文[ACFY24b]给出的折叠函数的定义，其折叠方式与 FRI 协议中的折叠方式是一致的。
定义 1 [ACFY24b, Definition 4.14] 令 f : L → F f: \mathcal{L} \rightarrow \mathbb{F} f : L → F α ∈ F \alpha \in \mathbb{F} α ∈ F F o l d ( f , α ) : L 2 → F \mathrm{Fold}(f, \alpha): \mathcal{L}^2 \rightarrow \mathbb{F} Fold ( f , α ) : L 2 → F
∀ x ∈ L 2 , F o l d ( f , α ) ( x 2 ) = f ( x ) + f ( − x ) 2 + α ⋅ f ( x ) − f ( − x ) 2 ⋅ x \forall x \in \mathcal{L}^2, \; \mathrm{Fold}(f, \alpha)(x^2) = \frac{f(x) + f(-x)}{2} + \alpha \cdot \frac{f(x) - f(-x)}{2 \cdot x} ∀ x ∈ L 2 , Fold ( f , α ) ( x 2 ) = 2 f ( x ) + f ( − x ) + α ⋅ 2 ⋅ x f ( x ) − f ( − x ) 为了计算 F o l d ( f , α ) ( x 2 ) \mathrm{Fold}(f, \alpha)(x^2) Fold ( f , α ) ( x 2 ) f f f x x x − x -x − x
对于 k ≤ m k \le m k ≤ m α = ( α 1 , α 2 , … , α k ) ∈ F k \boldsymbol{\alpha} = (\alpha_1, \alpha_2, \ldots, \alpha_k) \in \mathbb{F}^k α = ( α 1 , α 2 , … , α k ) ∈ F k F o l d ( f , α ) : L ( 2 k ) → F \mathrm{Fold}(f, \boldsymbol{\alpha}) : \mathcal{L}^{(2^k)} \rightarrow \mathbb{F} Fold ( f , α ) : L ( 2 k ) → F F o l d ( f , α ) : = f k \mathrm{Fold}(f, \boldsymbol{\alpha}) := f_k Fold ( f , α ) := f k f 0 : = f f_0 := f f 0 := f f i : = F o l d ( f i − 1 , α i ) f_i := \mathrm{Fold}(f_{i-1}, \alpha_i) f i := Fold ( f i − 1 , α i )
下面的命题告诉我们，对一个 Reed-Solomon code 在任意点的集合进行折叠，其结果依然是一个 Reed-Solomon code。([ACFY24b])
命题 1 [ACFY24b, Claim 4.15] 令 f : L → F f: \mathcal{L} \rightarrow \mathbb{F} f : L → F α ∈ F k \boldsymbol{\alpha} \in \mathbb{F}^k α ∈ F k g : = F o l d ( f , α ) g:= \mathrm{Fold}(f, \boldsymbol{\alpha}) g := Fold ( f , α ) f ∈ R S [ F , L , m ] f \in \mathrm{RS}[\mathbb{F}, \mathcal{L}, m] f ∈ RS [ F , L , m ] k ≤ m k \le m k ≤ m g ∈ R S [ F , L ( 2 k ) , m − k ] g \in \mathrm{RS}[\mathbb{F}, \mathcal{L}^{(2^k)}, m-k] g ∈ RS [ F , L ( 2 k ) , m − k ] g g g g ^ ( X k , … , X m ) : = f ^ ( α , X k , … , X m ) \hat{g}(X_k, \ldots, X_m) := \hat{f}(\boldsymbol{\alpha}, X_k, \ldots, X_m) g ^ ( X k , … , X m ) := f ^ ( α , X k , … , X m ) f ^ \hat{f} f ^ f f f
命题中给出的 g ^ ( X k , … , X m ) : = f ^ ( α , X k , … , X m ) \hat{g}(X_k, \ldots, X_m) := \hat{f}(\boldsymbol{\alpha}, X_k, \ldots, X_m) g ^ ( X k , … , X m ) := f ^ ( α , X k , … , X m ) f f f f ^ \hat{f} f ^ α \boldsymbol{\alpha} α f ^ ( α , X k , … , X m ) \hat{f}(\boldsymbol{\alpha}, X_k, \ldots, X_m) f ^ ( α , X k , … , X m )
回顾 FRI 协议，就是不断用随机数 ( α 1 , … , α m ) (\alpha_1, \ldots, \alpha_m) ( α 1 , … , α m ) f f f f ^ ( α 1 , … , α m ) \hat{f}(\alpha_1, \ldots, \alpha_m) f ^ ( α 1 , … , α m ) f ^ ( α 1 , … , α m ) \hat{f}(\alpha_1, \ldots, \alpha_m) f ^ ( α 1 , … , α m ) ( α 1 , … , α m ) (\alpha_1, \ldots, \alpha_m) ( α 1 , … , α m )
CRS: Constrained Reed-Solomon codes ¶ 下面给出 WHIR论文 [ACFY24b] 给出的 constrained Reed-Solomon codes 的定义，它是 Reed-Solomon codes 的一个子集，但是新增了一个类似 Sumcheck 的约束。
定义 2 [ACFY24b, Definition 1] 对于域为 F \mathbb{F} F L ⊆ F \mathcal{L} \subseteq \mathbb{F} L ⊆ F m ∈ N m \in \mathbb{N} m ∈ N w ^ ∈ F [ Z , X 1 , … , X m ] \hat{w} \in \mathbb{F}[Z, X_1, \ldots, X_m] w ^ ∈ F [ Z , X 1 , … , X m ] σ ∈ F \sigma \in \mathbb{F} σ ∈ F constrained Reed-Solomon code ，定义为
C R S [ F , L , m , w ^ , σ ] : = { f ∈ R S [ F , L , m ] : ∑ b ∈ { 0 , 1 } m w ^ ( f ^ ( b ) , b ) = σ } . \mathrm{CRS}[\mathbb{F}, \mathcal{L}, m, \hat{w}, \sigma] := \left\{ f \in \mathrm{RS}[\mathbb{F}, \mathcal{L}, m]: \sum_{\mathbf{b} \in \{0,1\}^m} \hat{w}(\hat{f}(\mathbf{b}), \mathbf{b}) = \sigma \right\}. CRS [ F , L , m , w ^ , σ ] := ⎩ ⎨ ⎧ f ∈ RS [ F , L , m ] : b ∈ { 0 , 1 } m ∑ w ^ ( f ^ ( b ) , b ) = σ ⎭ ⎬ ⎫ . 从定义可以看出，CRS(constrained Reed-Solomon code) 首先是 RS code，即定义中的 f ∈ R S [ F , L , m ] f \in \mathrm{RS}[\mathbb{F}, \mathcal{L}, m] f ∈ RS [ F , L , m ] ∑ b ∈ { 0 , 1 } m w ^ ( f ^ ( b ) , b ) = σ \sum_{\mathbf{b} \in \{0,1\}^m} \hat{w}(\hat{f}(\mathbf{b}), \mathbf{b}) = \sigma ∑ b ∈ { 0 , 1 } m w ^ ( f ^ ( b ) , b ) = σ
[ACFY24b] 论文中提到定义中的权重多项式 w ^ \hat{w} w ^ f ^ ( z ) = σ \hat{f}(\mathbf{z}) = \sigma f ^ ( z ) = σ f ^ \hat{f} f ^ z ∈ F m \mathbf{z} \in \mathbb{F}^m z ∈ F m f ∈ R S [ F , L , m ] f \in \mathrm{RS}[\mathbb{F}, \mathcal{L}, m] f ∈ RS [ F , L , m ]
f ^ ( X ) = ∑ b ∈ { 0 , 1 } m f ( b ) ⋅ e q ( b , X ) \hat{f}(\mathbf{X}) = \sum_{\mathbf{b} \in \{0,1\}^m} f(\mathbf{b}) \cdot \mathrm{eq}(\mathbf{b}, \mathbf{X}) f ^ ( X ) = b ∈ { 0 , 1 } m ∑ f ( b ) ⋅ eq ( b , X ) 其中 e q ( b , X ) = ∏ i = 1 m ( b i X i + ( 1 − b i ) ⋅ ( 1 − X i ) ) \mathrm{eq}(\mathbf{b}, \mathbf{X}) = \prod_{i=1}^m (b_i X_i + (1 - b_i) \cdot (1 - X_i)) eq ( b , X ) = ∏ i = 1 m ( b i X i + ( 1 − b i ) ⋅ ( 1 − X i )) b , X ∈ { 0 , 1 } m \mathbf{b},\mathbf{X} \in \{0,1\}^m b , X ∈ { 0 , 1 } m b = X \mathbf{b} = \mathbf{X} b = X e q ( b , X ) = 1 \mathrm{eq}(\mathbf{b}, \mathbf{X}) = 1 eq ( b , X ) = 1 b ≠ X \mathbf{b} \neq \mathbf{X} b = X e q ( b , X ) = 0 \mathrm{eq}(\mathbf{b}, \mathbf{X}) = 0 eq ( b , X ) = 0
f ^ ( z ) = ∑ b ∈ { 0 , 1 } m f ( b ) ⋅ e q ( b , z ) = ∑ b ∈ { 0 , 1 } m w ^ ( f ^ ( b ) , b ) \hat{f}(\mathbf{z}) = \sum_{\mathbf{b} \in \{0,1\}^m} f(\mathbf{b}) \cdot \mathrm{eq}(\mathbf{b}, \mathbf{z}) = \sum_{\mathbf{b} \in \{0,1\}^m} \hat{w}(\hat{f}(\mathbf{b}), \mathbf{b}) f ^ ( z ) = b ∈ { 0 , 1 } m ∑ f ( b ) ⋅ eq ( b , z ) = b ∈ { 0 , 1 } m ∑ w ^ ( f ^ ( b ) , b ) 权重多项式 w ^ ( Z , X ) \hat{w}(Z, \mathbf{X}) w ^ ( Z , X )
w ^ ( Z , X ) = Z ⋅ e q ( X , z ) . \hat{w}(Z, \mathbf{X}) = Z \cdot \mathrm{eq}(\mathbf{X}, \mathbf{z}). w ^ ( Z , X ) = Z ⋅ eq ( X , z ) . 这样就可以用权重多项式来表示一个求值约束了。可以基于此来构造对应的 PCS(来自[ACFY24b, 1.1 Hash-based PCS from CRS codes])，分两种情况：
约束多元线性多项式 f ^ \hat{f} f ^ z ∈ F m \mathbf{z} \in \mathbb{F}^m z ∈ F m w ^ ( Z , X ) = Z ⋅ e q ( X , z ) . \hat{w}(Z, \mathbf{X}) = Z \cdot \mathrm{eq}(\mathbf{X}, \mathbf{z}). w ^ ( Z , X ) = Z ⋅ eq ( X , z ) . 约束一个单变量多项式 f f f z ∈ F z \in \mathbb{F} z ∈ F z = ( z 2 0 , … , z 2 m − 1 ) \mathbf{z} = (z^{2^0}, \ldots, z^{2^{m-1}}) z = ( z 2 0 , … , z 2 m − 1 ) w ^ ( Z , X ) = Z ⋅ e q ( X , ( z 2 0 , … , z 2 m − 1 ) ) . \hat{w}(Z, X) = Z \cdot \mathrm{eq}(\mathbf{X}, (z^{2^0}, \ldots, z^{2^{m-1}})). w ^ ( Z , X ) = Z ⋅ eq ( X , ( z 2 0 , … , z 2 m − 1 )) . WHIR 的一次迭代 ¶ 前面提到 BaseFold 将 Sumcheck 和 FRI 协议结合了起来，而 WHIR 协议结合了 BaseFold 和 STIR 的思想，将 BaseFold 中的 FRI 协议改为了 STIR 协议，相比 FRI 协议，STIR 协议的查询复杂度更小。STIR 协议的核心思想是降低每一次迭代的码率，使得 Prover 发送的消息中的冗余增加，从而减少 Verifier 的查询复杂度。
下面深入 WHIR 协议的一次迭代(来自[ACFYb, 2.1.3 WHIR protocol])，看看 WHIR 是如何具体结合 BaseFold 与 STIR 协议的。经过一次迭代，将测试 f ∈ C : = C R S [ F , L , m , w ^ , σ ] f \in \mathcal{C} := \mathrm{CRS}[\mathbb{F}, \mathcal{L}, m, \hat{w}, \sigma] f ∈ C := CRS [ F , L , m , w ^ , σ ] f ′ ∈ C ′ : = C R S [ F , L ( 2 ) , m − k , w ^ ′ , σ ′ ] f' \in \mathcal{C}' := \mathrm{CRS}[\mathbb{F}, \mathcal{L}^{(2)}, m - k, \hat{w}', \sigma'] f ′ ∈ C ′ := CRS [ F , L ( 2 ) , m − k , w ^ ′ , σ ′ ]
Sumcheck rounds. Prover 和 Verifier 针对 C R S [ F , L , m , w ^ , σ ] \mathrm{CRS}[\mathbb{F}, \mathcal{L}, m, \hat{w}, \sigma] CRS [ F , L , m , w ^ , σ ]
∑ b ∈ { 0 , 1 } m w ^ ( f ^ ( b ) , b ) = σ \sum_{\mathbf{b} \in \{0,1\}^m} \hat{w}(\hat{f}(\mathbf{b}), \mathbf{b}) = \sigma b ∈ { 0 , 1 } m ∑ w ^ ( f ^ ( b ) , b ) = σ 进行 k k k f ^ \hat{f} f ^ f f f
a. Prover 向 Verifier 发送一个单变量多项式 h ^ 1 ( X ) : = ∑ b ∈ { 0 , 1 } m − 1 w ^ ( f ^ ( X , b ) , X , b ) \hat{h}_1(X) := \sum_{\mathbf{b} \in \{0,1\}^{m-1}} \hat{w}(\hat{f}(X, \mathbf{b}), X, \mathbf{b}) h ^ 1 ( X ) := ∑ b ∈ { 0 , 1 } m − 1 w ^ ( f ^ ( X , b ) , X , b ) h ^ 1 ( 0 ) + h ^ 1 ( 1 ) = σ \hat{h}_1(0) + \hat{h}_1(1) = \sigma h ^ 1 ( 0 ) + h ^ 1 ( 1 ) = σ α 1 ← F \alpha_1 \leftarrow \mathbb{F} α 1 ← F h ^ 1 ( α 1 ) : = ∑ b ∈ { 0 , 1 } m − 1 w ^ ( f ^ ( α 1 , b ) , α 1 , b ) \hat{h}_1(\alpha_1) := \sum_{\mathbf{b} \in \{0,1\}^{m-1}} \hat{w}(\hat{f}(\alpha_1, \mathbf{b}), \alpha_1, \mathbf{b}) h ^ 1 ( α 1 ) := ∑ b ∈ { 0 , 1 } m − 1 w ^ ( f ^ ( α 1 , b ) , α 1 , b ) i i i i i i k k k
h ^ i ( X ) : = ∑ b ∈ { 0 , 1 } m − i w ^ ( f ^ ( α 1 , … , α i − 1 , X , b ) , α 1 , … , α i − 1 , X , b ) \hat{h}_i(X) := \sum_{\mathbf{b} \in \{0,1\}^{m-i}} \hat{w}(\hat{f}(\alpha_1, \ldots, \alpha_{i - 1}, X, \mathbf{b}), \alpha_1, \ldots, \alpha_{i - 1}, X, \mathbf{b}) h ^ i ( X ) := b ∈ { 0 , 1 } m − i ∑ w ^ ( f ^ ( α 1 , … , α i − 1 , X , b ) , α 1 , … , α i − 1 , X , b ) Verifier 检查 h ^ i ( 0 ) + h ^ i ( 1 ) = h ^ i − 1 ( α i − 1 ) \hat{h}_{i}(0) + \hat{h}_{i}(1) = \hat{h}_{i-1}(\alpha_{i-1}) h ^ i ( 0 ) + h ^ i ( 1 ) = h ^ i − 1 ( α i − 1 ) α i ← F \alpha_i \leftarrow \mathbb{F} α i ← F
∑ b ∈ { 0 , 1 } m − i w ^ ( f ^ ( α 1 , … , α i − 1 , α i , b ) , α 1 , … , α i − 1 , α i , b ) = h ^ i ( α i ) \sum_{\mathbf{b} \in \{0,1\}^{m-i}} \hat{w}(\hat{f}(\alpha_1, \ldots, \alpha_{i - 1}, \alpha_i, \mathbf{b}), \alpha_1, \ldots, \alpha_{i - 1}, \alpha_i, \mathbf{b}) = \hat{h}_i(\alpha_i) b ∈ { 0 , 1 } m − i ∑ w ^ ( f ^ ( α 1 , … , α i − 1 , α i , b ) , α 1 , … , α i − 1 , α i , b ) = h ^ i ( α i ) 因此经过上述 k k k ( h ^ 1 , … , h ^ k ) (\hat{h}_1, \ldots, \hat{h}_k) ( h ^ 1 , … , h ^ k ) α = ( α 1 , … , α k ) ∈ F k \boldsymbol{\alpha} = (\alpha_1, \ldots, \alpha_k) \in \mathbb{F}^k α = ( α 1 , … , α k ) ∈ F k
∑ b ∈ { 0 , 1 } m − k w ^ ( f ^ ( α , b ) , α , b ) = h ^ k ( α k ) \sum_{\mathbf{b} \in \{0,1\}^{m-k}} \hat{w}(\hat{f}(\boldsymbol{\alpha}, \mathbf{b}), \boldsymbol{\alpha}, \mathbf{b}) = \hat{h}_k(\alpha_k) b ∈ { 0 , 1 } m − k ∑ w ^ ( f ^ ( α , b ) , α , b ) = h ^ k ( α k ) Send folded function. Prover 发送函数 g : L ( 2 ) → F g: \mathcal{L}^{(2)} \rightarrow \mathbb{F} g : L ( 2 ) → F g ^ ≡ f ^ ( α , ⋅ ) \hat{g} \equiv \hat{f}(\boldsymbol{\alpha}, \cdot) g ^ ≡ f ^ ( α , ⋅ ) g g g g ^ \hat{g} g ^ L ( 2 ) \mathcal{L}^{(2)} L ( 2 )
这里的意思是先对 f ^ \hat{f} f ^ α \boldsymbol{\alpha} α 2 k 2^k 2 k g ^ = f ^ ( α , ⋅ ) \hat{g} = \hat{f}(\boldsymbol{\alpha}, \cdot) g ^ = f ^ ( α , ⋅ ) g ^ : L ( 2 k ) → F \hat{g} : \mathcal{L}^{(2^k)} \rightarrow \mathbb{F} g ^ : L ( 2 k ) → F L ( 2 k ) \mathcal{L}^{(2^k)} L ( 2 k ) g ^ \hat{g} g ^ L ( 2 ) \mathcal{L}^{(2)} L ( 2 ) g g g g ^ \hat{g} g ^ L ( 2 ) \mathcal{L}^{(2)} L ( 2 )
Out-of-domain sample. Verifier 选取一个随机数 z 0 ← F z_0 \leftarrow \mathbb{F} z 0 ← F z 0 : = ( z 0 2 0 , … , z 0 2 m − k − 1 ) \boldsymbol{z}_0 := (z_0^{2^0}, \ldots, z_0^{2^{m-k - 1}}) z 0 := ( z 0 2 0 , … , z 0 2 m − k − 1 )
Out-of-domain answers. Prover 发送 y 0 ∈ F y_0 \in \mathbb{F} y 0 ∈ F y 0 : = g ^ ( z 0 ) y_0 := \hat{g}(\boldsymbol{z}_0) y 0 := g ^ ( z 0 )
Shift quiers and combination randomness. 对于 Verifier，对于每一个 i ∈ [ t ] i \in [t] i ∈ [ t ] z i ← L ( 2 k ) z_i \leftarrow \mathcal{L}^{(2^k)} z i ← L ( 2 k ) f f f y i : = F o l d ( f , α ) ( z i ) y_i := \mathrm{Fold}(f, \boldsymbol{\alpha})(z_i) y i := Fold ( f , α ) ( z i ) z i : = ( z i 2 0 , … , z i 2 m − k − 1 ) \boldsymbol{z}_i := (z_i^{2^0}, \ldots, z_i^{2^{m- k - 1}}) z i := ( z i 2 0 , … , z i 2 m − k − 1 ) γ ← F \gamma \leftarrow \mathbb{F} γ ← F
Recursive claim. Prover 和 Verifier 定义新的权重多项式与目标值：
w ^ ′ ( Z , X ) : = w ^ ( Z , α , X ) + Z ⋅ ∑ i = 0 t γ i + 1 ⋅ e q ( z i , X ) \hat{w}'(Z, \boldsymbol{X}) := \hat{w}(Z, \boldsymbol{\alpha}, \boldsymbol{X}) + Z \cdot \sum_{i = 0}^t \gamma^{i+1} \cdot \mathrm{eq}(\boldsymbol{z}_i, \boldsymbol{X}) w ^ ′ ( Z , X ) := w ^ ( Z , α , X ) + Z ⋅ i = 0 ∑ t γ i + 1 ⋅ eq ( z i , X ) σ ′ : = h ^ k ( α k ) + ∑ i = 0 t γ i + 1 ⋅ y i , \sigma' := \hat{h}_k(\alpha_k) + \sum_{i = 0}^t \gamma^{i+1} \cdot y_i, σ ′ := h ^ k ( α k ) + i = 0 ∑ t γ i + 1 ⋅ y i , 接着，递归地测试 g ∈ C R S [ F , L ( 2 ) , m − k , w ^ ′ , σ ′ ] g \in \mathrm{CRS}[\mathbb{F}, \mathcal{L}^{(2)}, m - k, \hat{w}', \sigma'] g ∈ CRS [ F , L ( 2 ) , m − k , w ^ ′ , σ ′ ]
下面先说明 g ∈ C R S [ F , L ( 2 ) , m − k , w ^ ′ , σ ′ ] g \in \mathrm{CRS}[\mathbb{F}, \mathcal{L}^{(2)}, m - k, \hat{w}', \sigma'] g ∈ CRS [ F , L ( 2 ) , m − k , w ^ ′ , σ ′ ]
∑ b ∈ { 0 , 1 } m − k w ^ ′ ( g ( b ) , b ) = σ ′ \sum_{\boldsymbol{b} \in \{0,1\}^{m-k}} \hat{w}'(g(\boldsymbol{b}), \boldsymbol{b}) = \sigma' b ∈ { 0 , 1 } m − k ∑ w ^ ′ ( g ( b ) , b ) = σ ′ 代入 w ^ ′ \hat{w}' w ^ ′ σ ′ \sigma' σ ′
∑ b ∈ { 0 , 1 } m − k w ^ ( g ( b ) , α , b ) + ∑ b ∈ { 0 , 1 } m − k g ( b ) ⋅ ∑ i = 0 t γ i + 1 ⋅ e q ( z i , b ) = h ^ k ( α k ) + ∑ i = 0 t γ i + 1 ⋅ y i \sum_{\boldsymbol{b} \in \{0,1\}^{m-k}} \hat{w}(g(\boldsymbol{b}), \boldsymbol{\alpha}, \boldsymbol{b}) + \sum_{\boldsymbol{b} \in \{0,1\}^{m-k}} g(\boldsymbol{b}) \cdot \sum_{i = 0}^t \gamma^{i+1} \cdot \mathrm{eq}(\boldsymbol{z}_i, \boldsymbol{b}) = \hat{h}_k(\alpha_k) + \sum_{i = 0}^t \gamma^{i+1} \cdot y_i b ∈ { 0 , 1 } m − k ∑ w ^ ( g ( b ) , α , b ) + b ∈ { 0 , 1 } m − k ∑ g ( b ) ⋅ i = 0 ∑ t γ i + 1 ⋅ eq ( z i , b ) = h ^ k ( α k ) + i = 0 ∑ t γ i + 1 ⋅ y i 分两部分证明：
证明
∑ b ∈ { 0 , 1 } m − k w ^ ( g ( b ) , α , b ) = h ^ k ( α k ) \sum_{\boldsymbol{b} \in \{0,1\}^{m-k}} \hat{w}(g(\boldsymbol{b}), \boldsymbol{\alpha}, \boldsymbol{b}) = \hat{h}_k(\alpha_k) b ∈ { 0 , 1 } m − k ∑ w ^ ( g ( b ) , α , b ) = h ^ k ( α k ) 由协议的第 2 步可知 g ( b ) = f ^ ( α , b ) g(\boldsymbol{b}) = \hat{f}(\boldsymbol{\alpha}, \boldsymbol{b}) g ( b ) = f ^ ( α , b )
∑ b ∈ { 0 , 1 } m − k w ^ ( g ( b ) , α , b ) = ∑ b ∈ { 0 , 1 } m − k w ^ ( f ^ ( α , b ) , α , b ) = h ^ k ( α k ) \begin{aligned}
\sum_{\boldsymbol{b} \in \{0,1\}^{m-k}} \hat{w}(g(\boldsymbol{b}), \boldsymbol{\alpha}, \boldsymbol{b}) & = \sum_{\boldsymbol{b} \in \{0,1\}^{m-k}} \hat{w}(\hat{f}(\boldsymbol{\alpha}, \boldsymbol{b}), \boldsymbol{\alpha}, \boldsymbol{b}) \\
& = \hat{h}_k(\alpha_k)
\end{aligned} b ∈ { 0 , 1 } m − k ∑ w ^ ( g ( b ) , α , b ) = b ∈ { 0 , 1 } m − k ∑ w ^ ( f ^ ( α , b ) , α , b ) = h ^ k ( α k ) 上式的最后一个等式是由协议的第 1 步 sumcheck 最后的声明得到的。
证明 ∑ b ∈ { 0 , 1 } m − k g ( b ) ⋅ ∑ i = 0 t γ i + 1 ⋅ e q ( z i , b ) = ∑ i = 0 t γ i + 1 ⋅ y i \sum_{\boldsymbol{b} \in \{0,1\}^{m-k}} g(\boldsymbol{b}) \cdot \sum_{i = 0}^t \gamma^{i+1} \cdot \mathrm{eq}(\boldsymbol{z}_i, \boldsymbol{b}) = \sum_{i = 0}^t \gamma^{i+1} \cdot y_i b ∈ { 0 , 1 } m − k ∑ g ( b ) ⋅ i = 0 ∑ t γ i + 1 ⋅ eq ( z i , b ) = i = 0 ∑ t γ i + 1 ⋅ y i 证明：
∑ b ∈ { 0 , 1 } m − k g ( b ) ⋅ ∑ i = 0 t γ i + 1 ⋅ e q ( z i , b ) = ∑ i = 0 t γ i + 1 ⋅ ∑ b ∈ { 0 , 1 } m − k g ( b ) ⋅ e q ( z i , b ) = ∑ i = 0 t γ i + 1 ⋅ g ( z i ) = ∑ i = 0 t γ i + 1 ⋅ y i \begin{aligned}
\sum_{\boldsymbol{b} \in \{0,1\}^{m-k}} g(\boldsymbol{b}) \cdot \sum_{i = 0}^t \gamma^{i+1} \cdot \mathrm{eq}(\boldsymbol{z}_i, \boldsymbol{b}) & = \sum_{i = 0}^t \gamma^{i+1} \cdot \sum_{\boldsymbol{b} \in \{0,1\}^{m-k}} g(\boldsymbol{b}) \cdot \mathrm{eq}(\boldsymbol{z}_i, \boldsymbol{b}) \\
& = \sum_{i = 0}^t \gamma^{i+1} \cdot g(\boldsymbol{z}_i) \\
& = \sum_{i = 0}^t \gamma^{i+1} \cdot y_i
\end{aligned} b ∈ { 0 , 1 } m − k ∑ g ( b ) ⋅ i = 0 ∑ t γ i + 1 ⋅ eq ( z i , b ) = i = 0 ∑ t γ i + 1 ⋅ b ∈ { 0 , 1 } m − k ∑ g ( b ) ⋅ eq ( z i , b ) = i = 0 ∑ t γ i + 1 ⋅ g ( z i ) = i = 0 ∑ t γ i + 1 ⋅ y i 其中 ∑ b ∈ { 0 , 1 } m − k g ( b ) ⋅ e q ( z i , b ) = g ( z i ) \sum_{\boldsymbol{b} \in \{0,1\}^{m-k}} g(\boldsymbol{b}) \cdot \mathrm{eq}(\boldsymbol{z}_i, \boldsymbol{b}) = g(\boldsymbol{z}_i) ∑ b ∈ { 0 , 1 } m − k g ( b ) ⋅ eq ( z i , b ) = g ( z i ) w ^ ( Z , X ) = Z ⋅ e q ( X , z ) \hat{w}(Z, \mathbf{X}) = Z \cdot \mathrm{eq}(\mathbf{X}, \mathbf{z}) w ^ ( Z , X ) = Z ⋅ eq ( X , z )
至此也就说明 g ∈ C R S [ F , L ( 2 ) , m − k , w ^ ′ , σ ′ ] g \in \mathrm{CRS}[\mathbb{F}, \mathcal{L}^{(2)}, m - k, \hat{w}', \sigma'] g ∈ CRS [ F , L ( 2 ) , m − k , w ^ ′ , σ ′ ]
新的权重多项式的定义 w ^ ′ \hat{w}' w ^ ′
w ^ ′ ( Z , X ) : = w ^ ( Z , α , X ) + Z ⋅ ∑ i = 0 t γ i + 1 ⋅ e q ( z i , X ) \hat{w}'(Z, \boldsymbol{X}) := \hat{w}(Z, \boldsymbol{\alpha}, \boldsymbol{X}) + Z \cdot \sum_{i = 0}^t \gamma^{i+1} \cdot \mathrm{eq}(\boldsymbol{z}_i, \boldsymbol{X}) w ^ ′ ( Z , X ) := w ^ ( Z , α , X ) + Z ⋅ i = 0 ∑ t γ i + 1 ⋅ eq ( z i , X ) 分为两部分：
第一部分 w ^ ( Z , α , X ) \hat{w}(Z, \boldsymbol{\alpha}, \boldsymbol{X}) w ^ ( Z , α , X ) k k k 第二部分 Z ⋅ ∑ i = 0 t γ i + 1 ⋅ e q ( z i , X ) Z \cdot \sum_{i = 0}^t \gamma^{i+1} \cdot \mathrm{eq}(\boldsymbol{z}_i, \boldsymbol{X}) Z ⋅ ∑ i = 0 t γ i + 1 ⋅ eq ( z i , X ) g g g z i \boldsymbol{z}_i z i t + 1 t + 1 t + 1 g ( z 0 ) = y 0 g(\boldsymbol{z}_0) = y_0 g ( z 0 ) = y 0 i ∈ [ t ] i \in [t] i ∈ [ t ] g ( z i ) = y i g(\boldsymbol{z}_i) = y_i g ( z i ) = y i 由此也可见权重多项式定义的灵活性，能一次实现多个约束。
WHIR 与 BaseFold 的联系 ¶ WHIR 采用了 BaseFold 的思想，本身 CRS 的定义就引入了类似 sumcheck 的约束。在协议的第 1 步，先做 k k k α = ( α 1 , … , α k ) \boldsymbol{\alpha} = (\alpha_1, \ldots, \alpha_k) α = ( α 1 , … , α k ) f ^ \hat{f} f ^ g ^ = f ^ ( α , ⋅ ) \hat{g} = \hat{f}(\boldsymbol{\alpha}, \cdot) g ^ = f ^ ( α , ⋅ ) f ^ \hat{f} f ^ 2 k 2^k 2 k
WHIR 与 STIR 的联系 ¶ 在协议第 1 步使用 sumcheck 之后，后续的第 2-5 步与 STIR 协议类似。下图是 STIR 协议的一次迭代流程。
STIR 协议的核心思想是在每一次迭代中降低码率，具体做法是在下一次迭代中，得到的折叠多项式 g ^ \hat{g} g ^ L ( 2 k ) \mathcal{L}^{(2^k)} L ( 2 k ) L \mathcal{L} L L ( 2 ) \mathcal{L}^{(2)} L ( 2 )
对于 f ∈ C : = C R S [ F , L , m , w ^ , σ ] f \in \mathcal{C} := \mathrm{CRS}[\mathbb{F}, \mathcal{L}, m, \hat{w}, \sigma] f ∈ C := CRS [ F , L , m , w ^ , σ ] ρ = 2 m ∣ L ∣ \rho = \frac{2^m}{|\mathcal{L}|} ρ = ∣ L ∣ 2 m f ′ ∈ C ′ : = C R S [ F , L ( 2 ) , m − k , w ^ ′ , σ ′ ] f' \in \mathcal{C}' := \mathrm{CRS}[\mathbb{F}, \mathcal{L}^{(2)}, m - k, \hat{w}', \sigma'] f ′ ∈ C ′ := CRS [ F , L ( 2 ) , m − k , w ^ ′ , σ ′ ]
ρ ′ = 2 m − k ∣ L ( 2 ) ∣ = 2 m − k ∣ L ∣ 2 = 2 m − k + 1 ∣ L ∣ = 2 1 − k ⋅ ρ = ( 1 2 ) k − 1 ⋅ ρ \rho' = \frac{2^{m - k}}{|\mathcal{L}^{(2)}|} = \frac{2^{m - k}}{\frac{|\mathcal{L}|}{2}} = \frac{2^{m - k + 1}}{|\mathcal{L}|} = 2^{1 - k} \cdot \rho = \left(\frac{1}{2}\right)^{k - 1} \cdot \rho ρ ′ = ∣ L ( 2 ) ∣ 2 m − k = 2 ∣ L ∣ 2 m − k = ∣ L ∣ 2 m − k + 1 = 2 1 − k ⋅ ρ = ( 2 1 ) k − 1 ⋅ ρ 当 k ≥ 2 k \ge 2 k ≥ 2 ρ ′ \rho' ρ ′
[BCIKS20] 论文中给出的 correlated agreement 定理是证明 FRI 和 STIR 协议安全性的一个关键定理，其能确保在 FRI 协议或 STIR 协议中用随机数对原来的函数进行折叠的过程是安全的。在 WHIR 的安全性分析中，引入了一个新的概念 mutual correlated agreement ，其结论比 correlated agreement 更强。
[ACFYb, 1.2 Mutual correlated agreement] 给出了correlated agreement 与 mutual correlated agreement 相关定义。码 C : = RS [ F , L , m ] \mathcal{C} := \text{RS}[\mathbb{F}, \mathcal{L}, m] C := RS [ F , L , m ] ( δ , ε ) (\delta, \varepsilon) ( δ , ε ) f 1 , … , f ℓ f_1, \ldots, f_\ell f 1 , … , f ℓ α ← F \alpha \leftarrow \mathbb{F} α ← F 1 − ε 1 - \varepsilon 1 − ε S ⊆ L S \subseteq \mathcal{L} S ⊆ L ∣ S ∣ ≥ ( 1 − δ ) ⋅ ∣ L ∣ |S| \geq (1 - \delta) \cdot |\mathcal{L}| ∣ S ∣ ≥ ( 1 − δ ) ⋅ ∣ L ∣ S S S f α ∗ : = ∑ i = 1 ℓ α i − 1 ⋅ f i f^*_\alpha := \sum_{i=1}^\ell \alpha^{i-1} \cdot f_i f α ∗ := ∑ i = 1 ℓ α i − 1 ⋅ f i C \mathcal{C} C T ⊆ L T \subseteq \mathcal{L} T ⊆ L ∣ T ∣ ≥ ( 1 − δ ) ⋅ ∣ L ∣ |T| \geq (1 - \delta) \cdot |\mathcal{L}| ∣ T ∣ ≥ ( 1 − δ ) ⋅ ∣ L ∣ T T T f i f_i f i C \mathcal{C} C
上述定义中描述一个函数 f f f C \mathcal{C} C S S S C \mathcal{C} C u ∈ C u \in \mathcal{C} u ∈ C x ∈ S x \in S x ∈ S f ( x ) = u ( x ) f(x) = u(x) f ( x ) = u ( x )
correlated agreement 的定义如下图所示(参照视频 ZK12: WHIR: Reed-Solomon Proximity Testing with Super-Fast Verification )。
[BCIKS20] 论文给出码率为 ρ 的 Reed-Solomon 码具有 ( δ , ε ) (\delta, \varepsilon) ( δ , ε ) δ ∈ ( 0 , 1 − ρ ) \delta \in (0, 1 - \sqrt{\rho}) δ ∈ ( 0 , 1 − ρ ) ε : = poly ( 2 m , 1 / ρ ) ∣ F ∣ \varepsilon := \frac{\text{poly}(2^m, 1/\rho)}{|\mathbb{F}|} ε := ∣ F ∣ poly ( 2 m , 1/ ρ ) δ ∈ ( 0 , 1 − ρ ) \delta \in (0, 1 - \sqrt{\rho}) δ ∈ ( 0 , 1 − ρ )
Pr α ∈ F [ Δ ( f α ∗ , C ) ≤ δ ] > ε = poly ( 2 m , 1 / ρ ) ∣ F ∣ \Pr_{\alpha \in \mathbb{F}} \left[ \Delta(f^*_\alpha, \mathcal{C}) \le \delta \right] > \varepsilon = \frac{\text{poly}(2^m, 1/\rho)}{|\mathbb{F}|} α ∈ F Pr [ Δ ( f α ∗ , C ) ≤ δ ] > ε = ∣ F ∣ poly ( 2 m , 1/ ρ ) 那么，存在集合 T ⊆ L T \subseteq \mathcal{L} T ⊆ L c 0 , … , c l ∈ C c_0, \ldots, c_l \in \mathcal{C} c 0 , … , c l ∈ C
∣ T ∣ ≥ ( 1 − δ ) ⋅ ∣ L ∣ |T| \geq (1 - \delta) \cdot |\mathcal{L}| ∣ T ∣ ≥ ( 1 − δ ) ⋅ ∣ L ∣ 在 T T T f i f_i f i c i c_i c i 可以发现 ( δ , ε ) (\delta, \varepsilon) ( δ , ε ) S S S T T T mutual correlated agreement ，其要求 S S S T T T ZK12: WHIR: Reed-Solomon Proximity Testing with Super-Fast Verification )：
在 WHIR 论文中给出了关于 mutual correlated agreement 如下的一个猜想。
猜想 1 [ACFY24b, Conjecture 1] (informal). 对于每一个 Reed-Solomon 码 C = RS [ F , L , m ] \mathcal{C} = \text{RS}[\mathbb{F}, \mathcal{L}, m] C = RS [ F , L , m ] ( δ , ε ) (\delta, \varepsilon) ( δ , ε ) ε = poly ( 2 m , 1 / ρ ) ∣ F ∣ \varepsilon = \frac{\text{poly}(2^m, 1/\rho)}{|\mathbb{F}|} ε = ∣ F ∣ poly ( 2 m , 1/ ρ ) ( δ , ε ′ ) (\delta, \varepsilon') ( δ , ε ′ ) ε ′ = poly ( 2 m , 1 / ρ ) ∣ F ∣ \varepsilon' = \frac{\text{poly}(2^m, 1/\rho)}{|\mathbb{F}|} ε ′ = ∣ F ∣ poly ( 2 m , 1/ ρ )
WHIR 论文中证明了在唯一解码情况下，即 δ ∈ ( 0 , 1 − ρ 2 ) \delta \in (0, \frac{1 - \rho}{2}) δ ∈ ( 0 , 2 1 − ρ ) ε ′ = ε \varepsilon' = \varepsilon ε ′ = ε
WHIR 协议结合了 BaseFold 与 STIR 的思想。首先对于 RS 编码中的一元多项式，可以通过变量替换的方式，看做等价的多元线性多项式，对于一元多项式的折叠也等价于对对应的多元线性多项式进行折叠。这样就使得 WHIR 既支持一元多项式也支持多元线性多项式。
其次，给出了新的 CRS 编码定义，在 RS 编码的基础上增加了一个类似 sumcheck 的约束，也就是对权重多项式 w ^ \hat{w} w ^
随后，通过深入 WHIR 的一次迭代协议，可以看出其与 BaseFold 和 STIR 协议的联系。这里的关键还是先搭建起一元多项式与多元线性多项式的桥梁，单变量函数 f f f f ^ \hat{f} f ^
∑ b ∈ { 0 , 1 } m w ^ ( f ^ ( b ) , b ) = σ \sum_{\mathbf{b} \in \{0,1\}^m} \hat{w}(\hat{f}(\mathbf{b}), \mathbf{b}) = \sigma b ∈ { 0 , 1 } m ∑ w ^ ( f ^ ( b ) , b ) = σ 因此结合 BaseFold 的思想，先进行 k k k f ^ \hat{f} f ^ α \boldsymbol{\alpha} α k k k f ^ \hat{f} f ^ α \boldsymbol{\alpha} α L ( 2 ) \mathcal{L}^{(2)} L ( 2 )
最后，介绍了 WHIR 协议安全性证明中用到的一个比 correlated agreement 结论更强的 mutual correlated agreement 结论。
References ¶ [ACFY24a] Gal Arnon, Alessandro Chiesa, Giacomo Fenzi, and Eylon Yogev. “STIR: Reed-Solomon proximity testing with fewer queries.” In Annual International Cryptology Conference , pp. 380-413. Cham: Springer Nature Switzerland, 2024. [ACFY24b] Gal Arnon, Alessandro Chiesa, Giacomo Fenzi, and Eylon Yogev. “WHIR: Reed–Solomon Proximity Testing with Super-Fast Verification.” Cryptology ePrint Archive (2024). [BBHR18] Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. “Fast Reed–Solomon Interactive Oracle Proofs of Proximity”. In: Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP) , 2018. [BCIKS20] Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, and Shubhangi Saraf. Proximity Gaps for Reed–Solomon Codes. In Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science , pages 900–909, 2020. [ZCF24] Hadas Zeilberger, Binyi Chen, and Ben Fisch. “BaseFold: efficient field-agnostic polynomial commitment schemes from foldable codes.” Annual International Cryptology Conference. Cham: Springer Nature Switzerland, 2024. Blog: WHIR: Reed–Solomon Proximity Testing with Super-Fast Verification video: ZK12: WHIR: Reed-Solomon Proximity Testing with Super-Fast Verification
