本篇文章主要介绍 DeepFold 协议 [GLHQTZ24] 的主要思想。DeepFold 协议是一个针对多元线性多项式的承诺方案(polynomial commitment scheme, PCS) ，其结合了 DEEP-FRI [BGKS20] 和 BaseFold [ZCF24] 的思想。BaseFold 协议 [ZCF24] 也是一个针对多元线性多项式的 PCS，其结合了 FRI 协议和 sumcheck 协议，不过在其原始论文中，其限制在 unique decoding 下，如果能将其优化到在 list decoding 下，那么在达到相同的安全参数 λ 下， verifier 进行 query 的数量就能够变得更少，这样也能减少 verifier 的计算量和证明的大小。DeepFold 协议就采取了 DEEP-FRI 中的 DEEP 方法来实现这一点。不过在 [H24] 中，Haböck 证明了针对 Reed-Solomon 编码的 BaseFold 协议在 list decoding 下的安全性。另一方面，STIR 协议 [ACFY24a] 相比 DEEP-FRI 协议有更少的 query 数量，结合 STIR 协议和 BaseFold 协议得到的 WHIR 协议 [ACFY24b] ，相比 DeepFold 协议能实现更少的 query 数量，不过目前还没有严格证明其在 list decoding 下的安全性。
DEEP 方法：从唯一解码到列表解码 ¶ 首先，回顾下 BaseFold 协议。以一个三元(设 μ = 3 \mu = 3 μ = 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 3 + a 6 X 2 X 3 + a 7 X 1 X 2 X 3 \tilde{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_1X_3 + a_6 X_2 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 3 + a 6 X 2 X 3 + a 7 X 1 X 2 X 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 f f f f ~ \tilde{f} f ~ twin polynomials ，它们共享相同的系数 a ⃗ = ( a 0 , a 1 , ⋯ , a 7 ) \vec{a} = (a_0, a_1, \cdots, a_7) a = ( a 0 , a 1 , ⋯ , a 7 ) z ⃗ = { z 1 , z 2 , z 3 } \vec{z} = \{z_1, z_2, z_3\} z = { z 1 , z 2 , z 3 } f ~ \tilde{f} f ~ f ~ ( z ⃗ ) \tilde{f}(\vec{z}) f ~ ( z ) f ~ ( z ⃗ ) \tilde{f}(\vec{z}) f ~ ( z ) { 0 , 1 } 3 \{0,1\}^3 { 0 , 1 } 3
f ~ ( z ⃗ ) = ∑ b ⃗ ∈ { 0 , 1 } 3 f ~ ( b ⃗ ) ⋅ e q ~ ( b ⃗ , z ⃗ ) (1) \tilde{f}(\vec{z}) = \sum_{\vec{b} \in \{0,1\}^3} \tilde{f}(\vec{b}) \cdot \tilde{eq}(\vec{b}, \vec{z}) \tag{1} f ~ ( z ) = b ∈ { 0 , 1 } 3 ∑ f ~ ( b ) ⋅ e q ~ ( b , z ) ( 1 ) 其中 e q ~ ( b ⃗ , z ⃗ ) = ∏ i = 1 3 ( ( 1 − b ⃗ [ i ] ) ( 1 − z ⃗ [ i ] ) + b ⃗ [ i ] ⋅ z ⃗ [ i ] ) \tilde{eq}(\vec{b}, \vec{z}) = \prod_{i = 1}^3((1 - \vec{b}[i])(1 - \vec{z}[i]) + \vec{b}[i] \cdot \vec{z}[i]) e q ~ ( b , z ) = ∏ i = 1 3 (( 1 − b [ i ]) ( 1 − z [ i ]) + b [ i ] ⋅ z [ i ]) ( 1 ) (1) ( 1 ) f ~ \tilde{f} f ~ f ~ ( r 1 , r 2 , r 3 ) \tilde{f}(r_1, r_2, r_3) f ~ ( r 1 , r 2 , r 3 ) f f f v ⃗ = f ( 0 ) ( X ) ∣ L 0 ∈ R S [ F , L 0 , ρ ] \vec{v} = f^{(0)}(X)|_{L_0} \in \mathrm{RS}[\mathbb{F}, L_0, \rho] v = f ( 0 ) ( X ) ∣ L 0 ∈ RS [ F , L 0 , ρ ] f ( 0 ) ( X ) = f ( X ) f^{(0)}(X) = f(X) f ( 0 ) ( X ) = f ( X ) ρ = 2 3 / ∣ L 0 ∣ \rho = 2^{3} / |L_0| ρ = 2 3 /∣ L 0 ∣ L i + 1 = { x 2 : x ∈ L i } L_{i + 1} = \{x^2: x \in L_i\} L i + 1 = { x 2 : x ∈ L i } f ( 0 ) ( X ) f^{(0)}(X) f ( 0 ) ( X )
f ( 0 ) ( X ) = f E ( 1 ) ( X 2 ) + X ⋅ f O ( 1 ) ( X 2 ) = ( 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 ) \begin{aligned}
f^{(0)}(X) & = f_E^{(1)}(X^2) + X \cdot f_O^{(1)}(X^2) \\
& = (a_0 + a_2 X^2 + a_4 X^4 + a_6 X^6) + X \cdot (a_1 + a_3 X^2 + a_5 X^4 + a_7 X^6)
\end{aligned} f ( 0 ) ( X ) = f E ( 1 ) ( X 2 ) + X ⋅ f O ( 1 ) ( X 2 ) = ( 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 ) 再用和 sumcheck 同样的随机数 r 1 ∈ F r_1 \in \mathbb{F} r 1 ∈ F f E ( 1 ) f_E^{(1)} f E ( 1 ) f O ( 1 ) f_O^{(1)} f O ( 1 ) f ( 1 ) ( X ) f^{(1)}(X) f ( 1 ) ( X )
f ( 1 ) ( X ) = f E ( 1 ) ( X ) + r 1 ⋅ f O ( 1 ) ( X ) = ( a 0 + a 2 X + a 4 X 2 + a 6 X 3 ) + r 1 ⋅ ( a 1 + a 3 X + a 5 X 2 + a 7 X 3 ) \begin{aligned}
f^{(1)}(X) & = f_E^{(1)}(X) + r_1 \cdot f_O^{(1)}(X) \\
& = (a_0 + a_2 X + a_4 X^2 + a_6 X^3) + r_1 \cdot (a_1 + a_3 X + a_5 X^2 + a_7 X^3)
\end{aligned} f ( 1 ) ( X ) = f E ( 1 ) ( X ) + r 1 ⋅ f O ( 1 ) ( X ) = ( a 0 + a 2 X + a 4 X 2 + a 6 X 3 ) + r 1 ⋅ ( a 1 + a 3 X + a 5 X 2 + a 7 X 3 ) 可以发现 f ( 1 ) ( X ) f^{(1)}(X) f ( 1 ) ( X )
f ~ ( r 1 , X 2 , X 3 ) = a 0 + a 1 r 1 + a 2 X 2 + a 3 ⋅ r 1 X 2 + a 4 X 3 + a 5 ⋅ r 1 X 3 + a 6 X 2 X 3 + a 7 ⋅ r 1 X 2 X 3 = ( a 0 + a 2 X 2 + a 4 X 3 + a 6 X 2 X 3 ) + r 1 ⋅ ( a 1 + a 3 X 2 + a 5 X 3 + a 7 X 2 X 3 ) \begin{aligned}
\tilde{f}(r_1, X_2, X_3) & = a_0 + a_1 r_1 + a_2 X_2 + a_3 \cdot r_1 X_2 + a_4 X_3 + a_5 \cdot r_1X_3 + a_6 X_2 X_3 + a_7 \cdot r_1 X_2 X_3 \\
& = (a_0 + a_2 X_2 + a_4 X_3 + a_6 X_2X_3) + r_1 \cdot (a_1 + a_3 X_2 + a_5 X_3 + a_7 X_2X_3)
\end{aligned} f ~ ( r 1 , X 2 , X 3 ) = a 0 + a 1 r 1 + a 2 X 2 + a 3 ⋅ r 1 X 2 + a 4 X 3 + a 5 ⋅ r 1 X 3 + a 6 X 2 X 3 + a 7 ⋅ r 1 X 2 X 3 = ( a 0 + a 2 X 2 + a 4 X 3 + a 6 X 2 X 3 ) + r 1 ⋅ ( a 1 + a 3 X 2 + a 5 X 3 + a 7 X 2 X 3 ) prover 发送 Merkle 承诺 v ⃗ ( 1 ) = f ( 1 ) ∣ L 1 \vec{v}^{(1)} = f^{(1)}|_{L_1} v ( 1 ) = f ( 1 ) ∣ L 1 f ( i − 1 ) ( X ) f^{(i - 1)}(X) f ( i − 1 ) ( X )
f ( i − 1 ) ( X ) = f E ( i ) ( X 2 ) + X ⋅ f O ( i ) ( X 2 ) (2) f^{(i - 1)}(X) = f_E^{(i)}(X^2) + X \cdot f_O^{(i)}(X^2) \tag{2} f ( i − 1 ) ( X ) = f E ( i ) ( X 2 ) + X ⋅ f O ( i ) ( X 2 ) ( 2 ) 然后用随机数 r i r_i r i
f ( i ) ( X ) = f E ( i ) ( X ) + r i ⋅ f O ( i ) ( X ) (3) f^{(i)}(X) = f_E^{(i)}(X) + r_i \cdot f_O^{(i)}(X) \tag{3} f ( i ) ( X ) = f E ( i ) ( X ) + r i ⋅ f O ( i ) ( X ) ( 3 ) prover 发送 Merkle 承诺 v ⃗ ( i ) = f ( i ) ∣ L i \vec{v}^{(i)} = f^{(i)}|_{L_i} v ( i ) = f ( i ) ∣ L i f ( 3 ) ( X ) = f ~ ( r 1 , r 2 , r 3 ) f^{(3)}(X) = \tilde{f}(r_1, r_2, r_3) f ( 3 ) ( X ) = f ~ ( r 1 , r 2 , r 3 )
可以发现，在 BaseFold 协议中，FRI 协议的作用除了其协议本身的作用，即确保 v ⃗ \vec{v} v R S [ F , L 0 , ρ ] \mathrm{RS}[\mathbb{F}, L_0, \rho] RS [ F , L 0 , ρ ] f ( 3 ) f^{(3)} f ( 3 ) f ~ ( r 1 , r 2 , r 3 ) \tilde{f}(r_1, r_2, r_3) f ~ ( r 1 , r 2 , r 3 ) v ⃗ \vec{v} v i i i v ⃗ ( i ) \vec{v}^{(i)} v ( i ) i i i f ( i ) f^{(i)} f ( i ) v ⃗ ( i ) \vec{v}^{(i)} v ( i ) f ( i ) f^{(i)} f ( i ) v ⃗ ( i ) \vec{v}^{(i)} v ( i ) f ( i ) ′ f^{(i)^{'}} f ( i ) ′ f ( 3 ) ′ f^{(3)^{'}} f ( 3 ) ′
因此现在需要一个方法来确保在列表解码下保证 f ( μ ) = f ( 3 ) f^{(\mu)} = f^{(3)} f ( μ ) = f ( 3 ) i i i v ⃗ ( i ) \vec{v}^{(i)} v ( i ) f ( i ) f^{(i)} f ( i ) f ( i ) f^{(i)} f ( i ) f ~ ( r 1 , … , r i , X i + 1 , … , X μ ) \tilde{f}(r_1, \ldots, r_i, X_{i + 1}, \ldots, X_{\mu}) f ~ ( r 1 , … , r i , X i + 1 , … , X μ ) i i i F \mathbb{F} F α i \alpha_i α i L i L_i L i f ( i − 1 ) ( ± α i ) f^{(i - 1)}(\pm \alpha_i) f ( i − 1 ) ( ± α i ) f ( i ) ( α i 2 ) f^{(i)}(\alpha_i^2) f ( i ) ( α i 2 )
f E ( i ) ( X 2 ) = f ( i − 1 ) ( X ) + f ( i − 1 ) ( − X ) 2 , f O ( i ) ( X 2 ) = f ( i − 1 ) ( X ) − f ( i − 1 ) ( − X ) 2 X f^{(i)}_E(X^2) = \frac{f^{(i - 1)}(X) + f^{(i - 1)}(- X)}{2}, \quad f^{(i)}_O(X^2) = \frac{f^{(i - 1)}(X) - f^{(i - 1)}(- X)}{2X} f E ( i ) ( X 2 ) = 2 f ( i − 1 ) ( X ) + f ( i − 1 ) ( − X ) , f O ( i ) ( X 2 ) = 2 X f ( i − 1 ) ( X ) − f ( i − 1 ) ( − X ) 因此
f ( i ) ( X 2 ) = f E ( i ) ( X 2 ) + r i ⋅ f O ( i ) ( X 2 ) = f ( i − 1 ) ( X ) + f ( i − 1 ) ( − X ) 2 + r i ⋅ f ( i − 1 ) ( X ) − f ( i − 1 ) ( − X ) 2 X \begin{aligned}
f^{(i)}(X^2) & = f^{(i)}_E(X^2) + r_i \cdot f^{(i)}_O(X^2) \\
& = \frac{f^{(i - 1)}(X) + f^{(i - 1)}(- X)}{2} + r_i \cdot \frac{f^{(i - 1)}(X) - f^{(i - 1)}(- X)}{2X}
\end{aligned} f ( i ) ( X 2 ) = f E ( i ) ( X 2 ) + r i ⋅ f O ( i ) ( X 2 ) = 2 f ( i − 1 ) ( X ) + f ( i − 1 ) ( − X ) + r i ⋅ 2 X f ( i − 1 ) ( X ) − f ( i − 1 ) ( − X ) 代入 X = α i X = \alpha_i X = α i
f ( i ) ( α i 2 ) = f ( i − 1 ) ( α i ) + f ( i − 1 ) ( − α i ) 2 + r i ⋅ f ( i − 1 ) ( α i ) − f ( i − 1 ) ( − α i ) 2 ⋅ α i f^{(i)}(\alpha_i^2) = \frac{f^{(i - 1)}(\alpha_i) + f^{(i - 1)}(- \alpha_i)}{2} + r_i \cdot \frac{f^{(i - 1)}(\alpha_i) - f^{(i - 1)}(- \alpha_i)}{2 \cdot \alpha_i} f ( i ) ( α i 2 ) = 2 f ( i − 1 ) ( α i ) + f ( i − 1 ) ( − α i ) + r i ⋅ 2 ⋅ α i f ( i − 1 ) ( α i ) − f ( i − 1 ) ( − α i ) verifier 能根据上式计算出 f ( i ) ( α i 2 ) f^{(i)}(\alpha_i^2) f ( i ) ( α i 2 ) α i \alpha_i α i F \mathbb{F} F v ⃗ ( i ) \vec{v}^{(i)} v ( i ) f ( i ) f^{(i)} f ( i ) f ( i ) ( α i 2 ) f^{(i)}(\alpha_i^2) f ( i ) ( α i 2 ) α i \alpha_i α i f ( i ) f^{(i)} f ( i )
这里解释下为什么以极大概率只能有唯一的多项式 f ( i ) f^{(i)} f ( i ) f ( i ) ( α i 2 ) f^{(i)}(\alpha_i^2) f ( i ) ( α i 2 ) f 1 ( i ) f_1^{(i)} f 1 ( i ) f 2 ( i ) f_2^{(i)} f 2 ( i ) α ∈ F \alpha \in \mathbb{F} α ∈ F f 1 ( i ) ( α ) = f 2 ( i ) ( α ) f_1^{(i)}(\alpha) = f_2^{(i)}(\alpha) f 1 ( i ) ( α ) = f 2 ( i ) ( α ) v ⃗ ( i ) \vec{v}^{(i)} v ( i ) ∣ v ⃗ ( i ) ∣ = n |\vec{v}^{(i)}| = n ∣ v ( i ) ∣ = n Δ = 1 − ρ − ε \Delta = 1 - \rho - \varepsilon Δ = 1 − ρ − ε v ⃗ ( i ) \vec{v}^{(i)} v ( i ) L \mathcal{L} L ∣ L ∣ ≤ p o l y ( n ) |\mathcal{L}| \le \mathrm{poly}(n) ∣ L ∣ ≤ poly ( n ) f 1 ( i ) ( α ) = f 2 ( i ) ( α ) f_1^{(i)}(\alpha) = f_2^{(i)}(\alpha) f 1 ( i ) ( α ) = f 2 ( i ) ( α ) f 1 ( i ) − f 2 ( i ) f_1^{(i)} - f_2^{(i)} f 1 ( i ) − f 2 ( i ) f 1 ( i ) f_1^{(i)} f 1 ( i ) f 2 ( i ) f_2^{(i)} f 2 ( i ) n n n f 1 ( i ) − f 2 ( i ) f_1^{(i)} - f_2^{(i)} f 1 ( i ) − f 2 ( i ) n n n F \mathbb{F} F n n n α ∈ F \alpha \in \mathbb{F} α ∈ F f 1 ( i ) − f 2 ( i ) f_1^{(i)} - f_2^{(i)} f 1 ( i ) − f 2 ( i ) n / ∣ F ∣ n / |\mathbb{F}| n /∣ F ∣ v ⃗ ( i ) \vec{v}^{(i)} v ( i ) f 1 ( i ) f_1^{(i)} f 1 ( i ) f 2 ( i ) f_2^{(i)} f 2 ( i ) ( ∣ L ∣ 2 ) \binom{|\mathcal{L}|}{2} ( 2 ∣ L ∣ ) n ⋅ ( ∣ L ∣ 2 ) / ∣ F ∣ n \cdot \binom{|\mathcal{L}|}{2} / |\mathbb{F}| n ⋅ ( 2 ∣ L ∣ ) /∣ F ∣ ∣ F ∣ |\mathbb{F}| ∣ F ∣ α i 2 \alpha_i^2 α i 2 f ( i ) f^{(i)} f ( i ) f ( i ) ( α i 2 ) f^{(i)}(\alpha_i^2) f ( i ) ( α i 2 )
现在通过 DEEP 的技巧就能将列表解码转换成唯一解码了，解决了列表解码下可能出现 v ⃗ ( i ) \vec{v}^{(i)} v ( i ) f ( μ ) f^{(\mu)} f ( μ ) f ( i ) ( α i 2 ) f^{(i)}(\alpha_i^2) f ( i ) ( α i 2 )
确保 DEEP 方法求值的正确性 ¶ [GLHQTZ24] 论文中提到了在 DEEP-FRI 论文 [BGKS20] 中可以使用 quotient 方法来验证 f ( i ) ( α i 2 ) f^{(i)}(\alpha_i^2) f ( i ) ( α i 2 ) ( 3 ) (3) ( 3 )
f ( i ) ( X ) = f E ( i ) ( X ) + r i ⋅ f O ( i ) ( X ) f^{(i)}(X) = f_E^{(i)}(X) + r_i \cdot f_O^{(i)}(X) f ( i ) ( X ) = f E ( i ) ( X ) + r i ⋅ f O ( i ) ( X ) 可以构造出新的形式，即
f ( i ) ( X ) = ( f E ( i ) ( X ) + r i ⋅ f O ( i ) ( X ) ) − ( f E ( i ) ( α i 2 ) + r i ⋅ f O ( i ) ( α i 2 ) ) X − α i 2 (4) f^{(i)}(X) = \frac{(f_E^{(i)}(X) + r_i \cdot f_O^{(i)}(X)) - (f_E^{(i)}(\alpha_i^2) + r_i \cdot f_O^{(i)}(\alpha_i^2))}{X - \alpha_i^2} \tag{4} f ( i ) ( X ) = X − α i 2 ( f E ( i ) ( X ) + r i ⋅ f O ( i ) ( X )) − ( f E ( i ) ( α i 2 ) + r i ⋅ f O ( i ) ( α i 2 )) ( 4 ) 如果 f ( i ) ( α i 2 ) f^{(i)}(\alpha_i^2) f ( i ) ( α i 2 ) f ( i ) ( X ) f^{(i)}(X) f ( i ) ( X ) f ( i ) ( α i 2 ) f^{(i)}(\alpha_i^2) f ( i ) ( α i 2 ) f ( i ) f^{(i)} f ( i ) ( 4 ) (4) ( 4 ) f ( i ) ( α i 2 ) f^{(i)}(\alpha_i^2) f ( i ) ( α i 2 ) f ( μ ) f^{(\mu)} f ( μ ) f ~ ( r ⃗ ) \tilde{f}(\vec{r}) f ~ ( r )
DeepFold 协议中给出了一个新的方法来确保在这些点处 { α i } \{\alpha_i\} { α i } μ = 3 \mu = 3 μ = 3 i = 1 i = 1 i = 1 α 1 ← $ F \alpha_1 \leftarrow \$ \mathbb{F} α 1 ← $ F f ( 1 ) ( α 1 2 ) f^{(1)}(\alpha_1^2) f ( 1 ) ( α 1 2 ) f ( 0 ) ( ± α 1 ) f^{(0)}(\pm \alpha_1) f ( 0 ) ( ± α 1 ) f ( X ) f(X) f ( X )
f ( 0 ) ( ± α 1 ) = a 0 + a 1 ⋅ ( ± α 1 ) + a 2 ⋅ ( ± α 1 ) 2 + a 3 ⋅ ( ± α 1 ) 3 + a 4 ⋅ ( ± α 1 ) 4 + a 5 ⋅ ( ± α 1 ) 5 + a 6 ⋅ ( ± α 1 ) 6 + a 7 ⋅ ( ± α 1 ) 7 = a 0 + a 1 ⋅ ( ± α 1 ) + a 2 ⋅ α 1 2 + a 3 ⋅ ( ± α 1 ) ⋅ α 1 2 + a 4 ⋅ α 1 4 + a 5 ⋅ ( ± α 1 ) ⋅ α 1 4 + a 6 ⋅ α 1 2 ⋅ α 1 4 + a 7 ⋅ ( ± α 1 ) ⋅ α 1 2 ⋅ α 1 4 \begin{aligned}
f^{(0)}(\pm \alpha_1) & = a_0 + a_1 \cdot (\pm \alpha_1) + a_2 \cdot (\pm \alpha_1)^2 + a_3 \cdot (\pm \alpha_1)^3 \\
& \quad + a_4 \cdot (\pm \alpha_1)^4 + a_5 \cdot (\pm \alpha_1)^5 + a_6 \cdot (\pm \alpha_1)^6 + a_7 \cdot (\pm \alpha_1)^7 \\
& = a_0 + a_1 \cdot (\pm \alpha_1) + a_2 \cdot \alpha_1^2 + a_3 \cdot (\pm \alpha_1)\cdot \alpha_1^2 \\
& \quad + a_4 \cdot \alpha_1^4 + a_5 \cdot (\pm \alpha_1) \cdot \alpha_1^4 + a_6 \cdot \alpha_1^2 \cdot \alpha_1^4 + a_7 \cdot (\pm \alpha_1) \cdot \alpha_1^2 \cdot \alpha_1^4
\end{aligned} f ( 0 ) ( ± α 1 ) = a 0 + a 1 ⋅ ( ± α 1 ) + a 2 ⋅ ( ± α 1 ) 2 + a 3 ⋅ ( ± α 1 ) 3 + a 4 ⋅ ( ± α 1 ) 4 + a 5 ⋅ ( ± α 1 ) 5 + a 6 ⋅ ( ± α 1 ) 6 + a 7 ⋅ ( ± α 1 ) 7 = a 0 + a 1 ⋅ ( ± α 1 ) + a 2 ⋅ α 1 2 + a 3 ⋅ ( ± α 1 ) ⋅ α 1 2 + a 4 ⋅ α 1 4 + a 5 ⋅ ( ± α 1 ) ⋅ α 1 4 + a 6 ⋅ α 1 2 ⋅ α 1 4 + a 7 ⋅ ( ± α 1 ) ⋅ α 1 2 ⋅ α 1 4 其正好对应多元线性多项式 f ~ ( X 1 , X 2 , X 3 ) \tilde{f}(X_1, X_2, X_3) f ~ ( X 1 , X 2 , X 3 ) ( ± α 1 , α 1 2 , α 1 4 ) (\pm \alpha_1, \alpha_1^2, \alpha_1^4) ( ± α 1 , α 1 2 , α 1 4 )
f ~ ( ± α 1 , α 1 2 , α 1 4 ) = 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 3 + a 6 X 2 X 3 + a 7 X 1 X 2 X 3 = a 0 + a 1 ⋅ ( ± α 1 ) + a 2 ⋅ α 1 2 + a 3 ⋅ ( ± α 1 ) ⋅ α 1 2 + a 4 ⋅ α 1 4 + a 5 ⋅ ( ± α 1 ) ⋅ α 1 4 + a 6 ⋅ α 1 2 ⋅ α 1 4 + a 7 ⋅ ( ± α 1 ) ⋅ α 1 2 ⋅ α 1 4 \begin{aligned}
\tilde{f}(\pm \alpha_1, \alpha_1^2, \alpha_1^4) & = a_0 + a_1 X_1 + a_2 X_2 + a_3 X_1 X_2 + a_4 X_3 + a_5 X_1X_3 + a_6 X_2 X_3 + a_7 X_1 X_2 X_3 \\
& = a_0 + a_1 \cdot (\pm \alpha_1) + a_2 \cdot \alpha_1^2 + a_3 \cdot (\pm \alpha_1)\cdot \alpha_1^2 \\
& \quad + a_4 \cdot \alpha_1^4 + a_5 \cdot (\pm \alpha_1) \cdot \alpha_1^4 + a_6 \cdot \alpha_1^2 \cdot \alpha_1^4 + a_7 \cdot (\pm \alpha_1) \cdot \alpha_1^2 \cdot \alpha_1^4
\end{aligned} f ~ ( ± α 1 , α 1 2 , α 1 4 ) = 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 3 + a 6 X 2 X 3 + a 7 X 1 X 2 X 3 = a 0 + a 1 ⋅ ( ± α 1 ) + a 2 ⋅ α 1 2 + a 3 ⋅ ( ± α 1 ) ⋅ α 1 2 + a 4 ⋅ α 1 4 + a 5 ⋅ ( ± α 1 ) ⋅ α 1 4 + a 6 ⋅ α 1 2 ⋅ α 1 4 + a 7 ⋅ ( ± α 1 ) ⋅ α 1 2 ⋅ α 1 4 因此 f ( 0 ) ( ± α 1 ) = f ~ ( ± α 1 , α 1 2 , α 1 4 ) f^{(0)}(\pm \alpha_1) = \tilde{f}(\pm \alpha_1, \alpha_1^2, \alpha_1^4) f ( 0 ) ( ± α 1 ) = f ~ ( ± α 1 , α 1 2 , α 1 4 ) f ( 0 ) ( ± α 1 ) f^{(0)}(\pm \alpha_1) f ( 0 ) ( ± α 1 ) f ( 1 ) ( α 1 2 ) f^{(1)}(\alpha_1^2) f ( 1 ) ( α 1 2 )
f ( i ) ( α i 2 ) = f ( i − 1 ) ( α i ) + f ( i − 1 ) ( − α i ) 2 + r i ⋅ f ( i − 1 ) ( α i ) − f ( i − 1 ) ( − α i ) 2 ⋅ α i (5) f^{(i)}(\alpha_i^2) = \frac{f^{(i - 1)}(\alpha_i) + f^{(i - 1)}(- \alpha_i)}{2} + r_i \cdot \frac{f^{(i - 1)}(\alpha_i) - f^{(i - 1)}(- \alpha_i)}{2 \cdot \alpha_i} \tag{5} f ( i ) ( α i 2 ) = 2 f ( i − 1 ) ( α i ) + f ( i − 1 ) ( − α i ) + r i ⋅ 2 ⋅ α i f ( i − 1 ) ( α i ) − f ( i − 1 ) ( − α i ) ( 5 ) 与上面推导 f ( 0 ) ( ± α 1 ) f^{(0)}(\pm \alpha_1) f ( 0 ) ( ± α 1 ) f ( 1 ) ( α 1 2 ) f^{(1)}(\alpha_1^2) f ( 1 ) ( α 1 2 )
f ( 1 ) ( α 1 2 ) = f ~ ( r 1 , α 1 2 , α 1 4 ) f^{(1)}(\alpha_1^2) = \tilde{f}(r_1, \alpha_1^2, \alpha_1^4) f ( 1 ) ( α 1 2 ) = f ~ ( r 1 , α 1 2 , α 1 4 ) 现在为了确保 f ( 1 ) ( α 1 2 ) f^{(1)}(\alpha_1^2) f ( 1 ) ( α 1 2 ) f ( 1 ) ( − α 1 2 ) f^{(1)}(-\alpha_1^2) f ( 1 ) ( − α 1 2 ) ( 5 ) (5) ( 5 ) f ( 2 ) ( α 1 4 ) f^{(2)}(\alpha_1^4) f ( 2 ) ( α 1 4 )
f ( 2 ) ( α 1 4 ) = f ~ ( r 1 , r 2 , α 1 4 ) f^{(2)}(\alpha_1^4) = \tilde{f}(r_1, r_2, \alpha_1^4) f ( 2 ) ( α 1 4 ) = f ~ ( r 1 , r 2 , α 1 4 ) 现在就将 f ( 1 ) ( α 1 2 ) f^{(1)}(\alpha_1^2) f ( 1 ) ( α 1 2 ) f ( 2 ) ( α 1 4 ) f^{(2)}(\alpha_1^4) f ( 2 ) ( α 1 4 ) f ( 2 ) ( − α 1 4 ) f^{(2)}(-\alpha_1^4) f ( 2 ) ( − α 1 4 ) f ( 3 ) ( α 1 8 ) f^{(3)}(\alpha_1^8) f ( 3 ) ( α 1 8 )
f ( 3 ) ( α 1 8 ) = f ~ ( r 1 , r 2 , r 3 ) f^{(3)}(\alpha_1^8) = \tilde{f}(r_1, r_2, r_3) f ( 3 ) ( α 1 8 ) = f ~ ( r 1 , r 2 , r 3 ) 这样 f ( 2 ) ( α 1 4 ) f^{(2)}(\alpha_1^4) f ( 2 ) ( α 1 4 ) f ( 3 ) ( α 1 8 ) f^{(3)}(\alpha_1^8) f ( 3 ) ( α 1 8 ) f ~ ( r 1 , r 2 , r 3 ) \tilde{f}(r_1, r_2, r_3) f ~ ( r 1 , r 2 , r 3 )
通过上述过程也能发现，如果 i ≠ 1 i \neq 1 i = 1 i i i f ( i − 1 ) ( ± α i ) f^{(i-1)}(\pm \alpha_i) f ( i − 1 ) ( ± α i ) f ( i ) ( α i 2 ) f^{(i)}(\alpha_i^2) f ( i ) ( α i 2 ) f ( i ) ( − α i 2 ) f^{(i)}(-\alpha_i^2) f ( i ) ( − α i 2 ) f ( i + 1 ) ( α i 4 ) f^{(i + 1)}(\alpha_i^4) f ( i + 1 ) ( α i 4 ) f ( μ ) = f ~ ( r 1 , r 2 , … , r μ ) f^{(\mu)} = \tilde{f}(r_1, r_2, \ldots, r_{\mu}) f ( μ ) = f ~ ( r 1 , r 2 , … , r μ )
DeepFold 协议 ¶ 总结下上面 DEEP 方法的介绍，为了能避免在 list decoding 下，作恶的 prover 可能选取在 v ⃗ ( i ) \vec{v}^{(i)} v ( i ) f ( i ) ′ f^{(i)'} f ( i ) ′ F \mathbb{F} F α i \alpha_i α i f ( i ) f^{(i)} f ( i ) f ( i ) ( α i 2 ) f^{(i)}(\alpha_i^2) f ( i ) ( α i 2 ) f ( i ) ( α i 2 ) f^{(i)}(\alpha_i^2) f ( i ) ( α i 2 ) f ( i ) ( − α i 2 ) f^{(i)}(-\alpha_i^2) f ( i ) ( − α i 2 ) f ( i + 1 ) ( α i 4 ) f^{(i + 1)}(\alpha_i^4) f ( i + 1 ) ( α i 4 ) f ( μ ) = f ~ ( r 1 , … , r μ ) f^{(\mu)} = \tilde{f}(r_1, \ldots, r_{\mu}) f ( μ ) = f ~ ( r 1 , … , r μ )
在对 f ~ \tilde{f} f ~ C = ⟨ r t 0 , α , c ⟩ \mathcal{C} = \langle rt_0, \alpha, c \rangle C = ⟨ r t 0 , α , c ⟩
prover 计算 v ⃗ = f ( 0 ) ∣ L 0 \vec{v} = f^{(0)}|_{L_0} v = f ( 0 ) ∣ L 0 M T . C o m m i t ( v ⃗ ) → r t 0 \mathsf{MT.Commit}(\vec{v}) \rightarrow rt_0 MT.Commit ( v ) → r t 0 verifier 发送一个随机点 α ← $ F \alpha \stackrel{\$}{\leftarrow}\mathbb{F} α ← $ F prover 计算 c : = f ( 0 ) ( α ) c := f^{(0)}(\alpha) c := f ( 0 ) ( α ) c c c prover 想向 verifier 证明的是: 在查询点 z ⃗ = { z 1 , z 2 , z 3 } \vec{z} = \{z_1, z_2, z_3\} z = { z 1 , z 2 , z 3 } f ~ ( z 1 , z 2 , z 3 ) = y \tilde{f}(z_1, z_2, z_3) = y f ~ ( z 1 , z 2 , z 3 ) = y C = ⟨ r t 0 , α , c ⟩ \mathcal{C} = \langle rt_0, \alpha, c \rangle C = ⟨ r t 0 , α , c ⟩
第 1 步 ：令 A 0 : = { z ⃗ , α ⃗ } A_0:= \{\vec{z}, \vec{\alpha}\} A 0 := { z , α } α ⃗ = ( α , α 2 , α 4 ) \vec{\alpha} = (\alpha, \alpha^2, \alpha^4) α = ( α , α 2 , α 4 )
第 2 步 ： 对每一轮 i ∈ [ 3 ] i \in [3] i ∈ [ 3 ]
2.1 当 i = 1 i = 1 i = 1
a. verifier 向 prover 发送 α 1 ← $ F \alpha_1 \stackrel{\$}{\leftarrow} \mathbb{F} α 1 ← $ F A 0 : = { A 0 , α 1 ⃗ } = { z ⃗ , α ⃗ , α 1 ⃗ } A_0 := \{A_0, \vec{\alpha_1}\} = \{\vec{z}, \vec{\alpha}, \vec{\alpha_1}\} A 0 := { A 0 , α 1 } = { z , α , α 1 } α 1 ⃗ = ( α 1 , α 1 2 , α 1 4 ) \vec{\alpha_1} = (\alpha_1, \alpha_1^2, \alpha_1^4) α 1 = ( α 1 , α 1 2 , α 1 4 )
这一步发送的 α 1 \alpha_1 α 1 L 0 L_0 L 0 f ( 1 ) f^{(1)} f ( 1 ) α 1 ⃗ = ( α 1 , α 1 2 , α 1 4 ) \vec{\alpha_1} = (\alpha_1, \alpha_1^2, \alpha_1^4) α 1 = ( α 1 , α 1 2 , α 1 4 ) f ( 1 ) ( α 1 2 ) = f ~ ( r 1 , α 1 2 , α 1 4 ) f^{(1)}(\alpha_1^2) = \tilde{f}(r_1, \alpha_1^2, \alpha_1^4) f ( 1 ) ( α 1 2 ) = f ~ ( r 1 , α 1 2 , α 1 4 )
b. 令 A 1 : = ∅ A_1 := \emptyset A 1 := ∅ ω ⃗ ∈ A 0 = { z ⃗ , α ⃗ , α 1 ⃗ } \vec{\omega} \in A_0 = \{\vec{z}, \vec{\alpha}, \vec{\alpha_1}\} ω ∈ A 0 = { z , α , α 1 }
g z ⃗ [ 2 : ] = g ( z 2 , z 3 ) : = f ~ ( X , z 2 , z 3 ) g α ⃗ [ 2 : ] = g ( α 2 , α 4 ) : = f ~ ( X , α 2 , α 4 ) g α 1 ⃗ [ 2 : ] = g ( α 1 2 , α 1 4 ) : = f ~ ( X , α 1 2 , α 1 4 ) \begin{aligned}
& g_{\vec{z}_{[2:]}} = g_{(z_2, z_3)} := \tilde{f}(X, z_2, z_3) \\
& g_{\vec{\alpha}_{[2:]}} =g_{(\alpha^2, \alpha^4)} := \tilde{f}(X, \alpha^2, \alpha^4) \\
& g_{\vec{\alpha_1}_{[2:]}} =g_{(\alpha_1^2, \alpha_1^4)} := \tilde{f}(X, \alpha_1^2, \alpha_1^4)
\end{aligned} g z [ 2 : ] = g ( z 2 , z 3 ) := f ~ ( X , z 2 , z 3 ) g α [ 2 : ] = g ( α 2 , α 4 ) := f ~ ( X , α 2 , α 4 ) g α 1 [ 2 : ] = g ( α 1 2 , α 1 4 ) := f ~ ( X , α 1 2 , α 1 4 ) 令 A 1 : = { A 1 , w ⃗ [ 2 : ] } = { ( z 2 , z 3 ) , ( α 2 , α 4 ) , ( α 1 2 , α 1 4 ) } A_1 := \{A_1, \vec{w}_{[2:]}\} = \{(z_2, z_3), (\alpha^2, \alpha^4), (\alpha_1^2, \alpha_1^4)\} A 1 := { A 1 , w [ 2 : ] } = {( z 2 , z 3 ) , ( α 2 , α 4 ) , ( α 1 2 , α 1 4 )}
这一步中的 g ( X ) g(X) g ( X )
c. verifier 向 prover 发送 r 1 ← $ F r_1 \stackrel{\$}{\leftarrow} \mathbb{F} r 1 ← $ F
d. prover 计算折叠后的多项式 f ( 1 ) ( X ) = f E ( 1 ) ( X ) + r 1 ⋅ f O ( 1 ) ( X ) f^{(1)}(X) = f_E^{(1)}(X) + r_1 \cdot f_O^{(1)}(X) f ( 1 ) ( X ) = f E ( 1 ) ( X ) + r 1 ⋅ f O ( 1 ) ( X ) f E ( 1 ) ( X ) f_E^{(1)}(X) f E ( 1 ) ( X ) f O ( 1 ) ( X ) f_O^{(1)}(X) f O ( 1 ) ( X )
f ( 0 ) ( X ) = f E ( 1 ) ( X 2 ) + X ⋅ f O ( 1 ) ( X 2 ) f^{(0)}(X) = f_E^{(1)}(X^2) + X \cdot f_O^{(1)}(X^2) f ( 0 ) ( X ) = f E ( 1 ) ( X 2 ) + X ⋅ f O ( 1 ) ( X 2 ) 满足这个等式的含义是确保 f E ( 1 ) ( X 2 ) f_E^{(1)}(X^2) f E ( 1 ) ( X 2 ) f O ( 1 ) ( X 2 ) f_O^{(1)}(X^2) f O ( 1 ) ( X 2 ) f ( 0 ) ( X ) f^{(0)}(X) f ( 0 ) ( X )
e. 令 v ⃗ ( 1 ) = f ( 1 ) ∣ L 1 \vec{v}^{(1)} = f^{(1)}|_{L_1} v ( 1 ) = f ( 1 ) ∣ L 1 v ⃗ ( 1 ) \vec{v}^{(1)} v ( 1 ) M T . C o m m i t ( v ⃗ ( 1 ) ) → r t 1 \mathsf{MT.Commit}(\vec{v}^{(1)}) \rightarrow rt_1 MT.Commit ( v ( 1 ) ) → r t 1
2.2 当 i = 2 i = 2 i = 2
a. verifier 向 prover 发送 α 2 ← $ F \alpha_2 \stackrel{\$}{\leftarrow} \mathbb{F} α 2 ← $ F A 1 : = { A 1 , α 2 ⃗ } = { ( z 2 , z 3 ) , ( α 2 , α 4 ) , ( α 1 2 , α 1 4 ) , ( α 2 , α 2 2 ) } A_1 := \{A_1, \vec{\alpha_2}\} = \{(z_2, z_3), (\alpha^2, \alpha^4), (\alpha_1^2, \alpha_1^4), (\alpha_2, \alpha_2^2)\} A 1 := { A 1 , α 2 } = {( z 2 , z 3 ) , ( α 2 , α 4 ) , ( α 1 2 , α 1 4 ) , ( α 2 , α 2 2 )} α 2 ⃗ = ( α 2 , α 2 2 ) \vec{\alpha_2} = (\alpha_2, \alpha_2^2) α 2 = ( α 2 , α 2 2 )
注意这里 A 1 A_1 A 1 α 2 \alpha_2 α 2 f ( 2 ) ( X ) f^{(2)}(X) f ( 2 ) ( X ) f ( 2 ) ( X ) f^{(2)}(X) f ( 2 ) ( X ) α 2 2 \alpha_2^2 α 2 2 f ( 2 ) ( α 2 2 ) = f ~ ( r 1 , r 2 , α 2 2 ) f^{(2)}(\alpha_2^2) = \tilde{f}(r_1, r_2, \alpha_2^2) f ( 2 ) ( α 2 2 ) = f ~ ( r 1 , r 2 , α 2 2 )
b. 令 A 2 : = ∅ A_2 := \emptyset A 2 := ∅ ω ⃗ ∈ A 1 = { ( z 2 , z 3 ) , ( α 2 , α 4 ) , ( α 1 2 , α 1 4 ) , ( α 2 , α 2 2 ) } \vec{\omega} \in A_1 = \{(z_2, z_3), (\alpha^2, \alpha^4), (\alpha_1^2, \alpha_1^4), (\alpha_2, \alpha_2^2)\} ω ∈ A 1 = {( z 2 , z 3 ) , ( α 2 , α 4 ) , ( α 1 2 , α 1 4 ) , ( α 2 , α 2 2 )}
g z ⃗ [ 2 : ] = g ( z 3 ) : = f ~ ( r 1 , X , z 3 ) g α ⃗ [ 2 : ] = g ( α 4 ) : = f ~ ( r 1 , X , α 4 ) g α 1 ⃗ [ 2 : ] = g ( α 1 4 ) : = f ~ ( r 1 , X , α 1 4 ) g α 2 ⃗ [ 2 : ] = g ( α 2 2 ) : = f ~ ( r 1 , X , α 2 2 ) \begin{aligned}
& g_{\vec{z}_{[2:]}} = g_{(z_3)} := \tilde{f}(r_1, X, z_3) \\
& g_{\vec{\alpha}_{[2:]}} =g_{(\alpha^4)} := \tilde{f}(r_1, X, \alpha^4) \\
& g_{\vec{\alpha_1}_{[2:]}} =g_{(\alpha_1^4)} := \tilde{f}(r_1, X, \alpha_1^4) \\
& g_{\vec{\alpha_2}_{[2:]}} =g_{(\alpha_2^2)} := \tilde{f}(r_1, X, \alpha_2^2)
\end{aligned} g z [ 2 : ] = g ( z 3 ) := f ~ ( r 1 , X , z 3 ) g α [ 2 : ] = g ( α 4 ) := f ~ ( r 1 , X , α 4 ) g α 1 [ 2 : ] = g ( α 1 4 ) := f ~ ( r 1 , X , α 1 4 ) g α 2 [ 2 : ] = g ( α 2 2 ) := f ~ ( r 1 , X , α 2 2 ) 令 A 2 : = { A 2 , w ⃗ [ 2 : ] } = { ( z 3 ) , ( α 4 ) , ( α 1 4 ) , ( α 2 2 ) } A_2 := \{A_2, \vec{w}_{[2:]}\} = \{(z_3), (\alpha^4), (\alpha_1^4), (\alpha_2^2)\} A 2 := { A 2 , w [ 2 : ] } = {( z 3 ) , ( α 4 ) , ( α 1 4 ) , ( α 2 2 )}
c. verifier 向 prover 发送 r 2 ← $ F r_2 \stackrel{\$}{\leftarrow} \mathbb{F} r 2 ← $ F
d. prover 计算折叠后的多项式 f ( 2 ) ( X ) = f E ( 2 ) ( X ) + r 2 ⋅ f O ( 2 ) ( X ) f^{(2)}(X) = f_E^{(2)}(X) + r_2 \cdot f_O^{(2)}(X) f ( 2 ) ( X ) = f E ( 2 ) ( X ) + r 2 ⋅ f O ( 2 ) ( X ) f E ( 2 ) ( X ) f_E^{(2)}(X) f E ( 2 ) ( X ) f O ( 2 ) ( X ) f_O^{(2)}(X) f O ( 2 ) ( X )
f ( 1 ) ( X ) = f E ( 2 ) ( X 2 ) + X ⋅ f O ( 2 ) ( X 2 ) f^{(1)}(X) = f_E^{(2)}(X^2) + X \cdot f_O^{(2)}(X^2) f ( 1 ) ( X ) = f E ( 2 ) ( X 2 ) + X ⋅ f O ( 2 ) ( X 2 ) e. 令 v ⃗ ( 2 ) = f ( 2 ) ∣ L 2 \vec{v}^{(2)} = f^{(2)}|_{L_2} v ( 2 ) = f ( 2 ) ∣ L 2 v ⃗ ( 2 ) \vec{v}^{(2)} v ( 2 ) M T . C o m m i t ( v ⃗ ( 2 ) ) → r t 2 \mathsf{MT.Commit}(\vec{v}^{(2)}) \rightarrow rt_2 MT.Commit ( v ( 2 ) ) → r t 2
2.3 当 i = 3 i = 3 i = 3
a. verifier 向 prover 发送 α 3 ← $ F \alpha_3 \stackrel{\$}{\leftarrow} \mathbb{F} α 3 ← $ F A 2 : = { A 2 , α 3 ⃗ } = { ( z 3 ) , ( α 4 ) , ( α 1 4 ) , ( α 2 2 ) , ( α 3 ) } A_2 := \{A_2, \vec{\alpha_3}\} = \{(z_3), (\alpha^4), (\alpha_1^4), (\alpha_2^2), (\alpha_3)\} A 2 := { A 2 , α 3 } = {( z 3 ) , ( α 4 ) , ( α 1 4 ) , ( α 2 2 ) , ( α 3 )} α 3 ⃗ = ( α 3 ) \vec{\alpha_3} = (\alpha_3) α 3 = ( α 3 )
b. prover 向 verifier 发送线性函数
g ( X ) : = f ~ ( r 1 , r 2 , X ) g(X) := \tilde{f}(r_1, r_2, X) g ( X ) := f ~ ( r 1 , r 2 , X ) 现在是最后一轮，直接发送函数 g ( X ) g(X) g ( X )
c. verifier 向 prover 发送 r 3 ← $ F r_3 \stackrel{\$}{\leftarrow} \mathbb{F} r 3 ← $ F
d. prover 计算折叠后的多项式 f ( 3 ) ( X ) = f E ( 3 ) ( X ) + r 3 ⋅ f O ( 3 ) ( X ) f^{(3)}(X) = f_E^{(3)}(X) + r_3 \cdot f_O^{(3)}(X) f ( 3 ) ( X ) = f E ( 3 ) ( X ) + r 3 ⋅ f O ( 3 ) ( X ) f E ( 3 ) ( X ) f_E^{(3)}(X) f E ( 3 ) ( X ) f O ( 3 ) ( X ) f_O^{(3)}(X) f O ( 3 ) ( X )
f ( 2 ) ( X ) = f E ( 3 ) ( X 2 ) + X ⋅ f O ( 3 ) ( X 2 ) f^{(2)}(X) = f_E^{(3)}(X^2) + X \cdot f_O^{(3)}(X^2) f ( 2 ) ( X ) = f E ( 3 ) ( X 2 ) + X ⋅ f O ( 3 ) ( X 2 ) e. 令 v ⃗ ( 3 ) = f ( 3 ) ∣ L 3 \vec{v}^{(3)} = f^{(3)}|_{L_3} v ( 3 ) = f ( 3 ) ∣ L 3 f ( 3 ) ∈ F f^{(3)} \in \mathbb{F} f ( 3 ) ∈ F
进行到最后一轮时，FRI 最后会折叠成一个常数多项式，因此这里直接发送一个值 f ( 3 ) f^{(3)} f ( 3 )
接下来的步骤是 verifier 进行验证检查的过程。
第 3 步 ： verifier 检查
g z ⃗ [ 2 : ] ( z 1 ) = y g α ⃗ [ 2 : ] ( α ) = c g ( r 3 ) = f ( 3 ) \begin{aligned}
& g_{\vec{z}_{[2:]}}(z_1) = y \\
& g_{\vec{\alpha}_{[2:]}}(\alpha) = c \\
& g(r_{3}) = f^{(3)}
\end{aligned} g z [ 2 : ] ( z 1 ) = y g α [ 2 : ] ( α ) = c g ( r 3 ) = f ( 3 ) 根据 i = 1 i = 1 i = 1 i = 3 i = 3 i = 3 g ( X ) g(X) g ( X )
> > g z ⃗ [ 2 : ] ( z 1 ) = f ~ ( z 1 , z 2 , z 3 ) = y > g α ⃗ [ 2 : ] ( α ) = f ~ ( α , α 2 , α 4 ) = c > g ( r 3 ) = f ~ ( r 1 , r 2 , r 3 ) = f ( 3 ) > > > \begin{aligned}
> & g_{\vec{z}_{[2:]}}(z_1) = \tilde{f}(z_1, z_2, z_3) = y\\
> & g_{\vec{\alpha}_{[2:]}}(\alpha) = \tilde{f}(\alpha, \alpha^2, \alpha^4) = c\\
> & g(r_3) = \tilde{f}(r_1, r_2, r_3) = f^{(3)}
> \end{aligned}
> > > > > g z [ 2 : ] ( z 1 ) = f ~ ( z 1 , z 2 , z 3 ) = y g α [ 2 : ] ( α ) = f ~ ( α , α 2 , α 4 ) = c g ( r 3 ) = f ~ ( r 1 , r 2 , r 3 ) = f ( 3 ) > > 接着，对每一轮，verifier 还要进行如下检查。
3.1 当 i = 1 i = 1 i = 1
a. 对每一个 w ⃗ ∈ A 0 = { z ⃗ , α ⃗ , α 1 ⃗ } \vec{w} \in A_0 = \{\vec{z}, \vec{\alpha}, \vec{\alpha_1}\} w ∈ A 0 = { z , α , α 1 } g w ⃗ ( r 0 ) = g w ⃗ [ 2 : ] ( w 1 ) g_{\vec{w}}(r_0) = g_{\vec{w}_{[2:]}}(w_1) g w ( r 0 ) = g w [ 2 : ] ( w 1 )
g ( z 1 , z 2 , z 3 ) ( r 0 ) = g ( z 2 , z 3 ) ( z 1 ) g ( α , α 2 , α 4 ) ( r 0 ) = g ( α 2 , α 4 ) ( α ) g ( α 1 , α 1 2 , α 1 4 ) ( r 0 ) = g ( α 1 2 , α 1 4 ) ( α 1 ) \begin{aligned}
& g_{(z_1, z_2, z_3)}(r_0) = g_{(z_2, z_3)}(z_1) \\
& g_{(\alpha, \alpha^2, \alpha^4)}(r_0) = g_{(\alpha^2, \alpha^4)}(\alpha) \\
& g_{(\alpha_1, \alpha_1^2, \alpha_1^4)}(r_0) = g_{(\alpha_1^2, \alpha_1^4)}(\alpha_1)
\end{aligned} g ( z 1 , z 2 , z 3 ) ( r 0 ) = g ( z 2 , z 3 ) ( z 1 ) g ( α , α 2 , α 4 ) ( r 0 ) = g ( α 2 , α 4 ) ( α ) g ( α 1 , α 1 2 , α 1 4 ) ( r 0 ) = g ( α 1 2 , α 1 4 ) ( α 1 ) 🐞fix
我认为原论文中的第 3 步中
For each round i i i i ∈ [ μ ] i \in [\mu] i ∈ [ μ ] w ⃗ ∈ A i − 1 \vec{w} \in A_{i - 1} w ∈ A i − 1 i < μ i < \mu i < μ V \mathcal{V} V g w ⃗ ( r i ) = g w ⃗ [ 2 : ] ( w 1 ) g_{\vec{w}}(r_i) = g_{\vec{w}_{[2:]}}(w_1) g w ( r i ) = g w [ 2 : ] ( w 1 ) V \mathcal{V} V g w ⃗ ( r i ) = g ( w 1 ) g_{\vec{w}}(r_i) = g(w_1) g w ( r i ) = g ( w 1 )
应该改为，当 i < μ i < \mu i < μ g w ⃗ ( r i − 1 ) = g w ⃗ [ 2 : ] ( w 1 ) g_{\vec{w}}(r_{i - 1}) = g_{\vec{w}_{[2:]}}(w_1) g w ( r i − 1 ) = g w [ 2 : ] ( w 1 ) g w ⃗ ( r i − 1 ) = g ( w 1 ) g_{\vec{w}}(r_{i - 1}) = g(w_1) g w ( r i − 1 ) = g ( w 1 ) i = 2 i = 2 i = 2 g w ⃗ ( r 1 ) = g w ⃗ [ 2 : ] ( w 1 ) g_{\vec{w}}(r_1) = g_{\vec{w}_{[2:]}}(w_1) g w ( r 1 ) = g w [ 2 : ] ( w 1 )
其实上面最后一个式子是不需要检查的，即 g ( α 1 , α 1 2 , α 1 4 ) ( r 0 ) = g ( α 1 2 , α 1 4 ) ( α 1 ) g_{(\alpha_1, \alpha_1^2, \alpha_1^4)}(r_0) = g_{(\alpha_1^2, \alpha_1^4)}(\alpha_1) g ( α 1 , α 1 2 , α 1 4 ) ( r 0 ) = g ( α 1 2 , α 1 4 ) ( α 1 ) g ( X ) g(X) g ( X )
g ( z 1 , z 2 , z 3 ) ( r 0 ) = f ~ ( z 1 , z 2 , z 3 ) = y g ( z 2 , z 3 ) ( z 1 ) = f ~ ( z 1 , z 2 , z 3 ) g ( α , α 2 , α 4 ) ( r 0 ) = f ~ ( α , α 2 , α 4 ) = c g ( α 2 , α 4 ) ( α ) = f ~ ( α , α 2 , α 4 ) \begin{aligned}
& g_{(z_1, z_2, z_3)}(r_0) = \tilde{f}(z_1, z_2, z_3) = y & g_{(z_2, z_3)}(z_1) = \tilde{f}(z_1, z_2, z_3)\\
& g_{(\alpha, \alpha^2, \alpha^4)}(r_0) = \tilde{f}(\alpha, \alpha^2, \alpha^4) = c & g_{(\alpha^2, \alpha^4)}(\alpha) = \tilde{f}(\alpha, \alpha^2, \alpha^4)
\end{aligned} g ( z 1 , z 2 , z 3 ) ( r 0 ) = f ~ ( z 1 , z 2 , z 3 ) = y g ( α , α 2 , α 4 ) ( r 0 ) = f ~ ( α , α 2 , α 4 ) = c g ( z 2 , z 3 ) ( z 1 ) = f ~ ( z 1 , z 2 , z 3 ) g ( α 2 , α 4 ) ( α ) = f ~ ( α , α 2 , α 4 ) 3.2 当 i = 2 i = 2 i = 2
a. 对每一个 w ⃗ ∈ A 1 = { ( z 2 , z 3 ) , ( α 2 , α 4 ) , ( α 1 2 , α 1 4 ) , ( α 2 , α 2 2 ) } \vec{w} \in A_1 = \{(z_2, z_3), (\alpha^2, \alpha^4), (\alpha_1^2, \alpha_1^4), (\alpha_2, \alpha_2^2)\} w ∈ A 1 = {( z 2 , z 3 ) , ( α 2 , α 4 ) , ( α 1 2 , α 1 4 ) , ( α 2 , α 2 2 )} g w ⃗ ( r 1 ) = g w ⃗ [ 2 : ] ( w 1 ) g_{\vec{w}}(r_1) = g_{\vec{w}_{[2:]}}(w_1) g w ( r 1 ) = g w [ 2 : ] ( w 1 )
g ( z 2 , z 3 ) ( r 1 ) = g ( z 3 ) ( z 2 ) g ( α 2 , α 4 ) ( r 1 ) = g ( α 4 ) ( α 2 ) g ( α 1 2 , α 1 4 ) ( r 1 ) = g ( α 1 4 ) ( α 1 2 ) g ( α 2 , α 2 2 ) ( r 1 ) = g ( α 2 2 ) ( α 2 ) \begin{aligned}
& g_{(z_2, z_3)}(r_1) = g_{(z_3)}(z_2) \\
& g_{(\alpha^2, \alpha^4)}(r_1) = g_{(\alpha^4)}(\alpha^2) \\
& g_{(\alpha_1^2, \alpha_1^4)}(r_1) = g_{(\alpha_1^4)}(\alpha_1^2) \\
& g_{(\alpha_2, \alpha_2^2)}(r_1) = g_{(\alpha_2^2)}(\alpha_2)
\end{aligned} g ( z 2 , z 3 ) ( r 1 ) = g ( z 3 ) ( z 2 ) g ( α 2 , α 4 ) ( r 1 ) = g ( α 4 ) ( α 2 ) g ( α 1 2 , α 1 4 ) ( r 1 ) = g ( α 1 4 ) ( α 1 2 ) g ( α 2 , α 2 2 ) ( r 1 ) = g ( α 2 2 ) ( α 2 ) 最后一个式子并不需要检查 g ( α 2 , α 2 2 ) ( r 1 ) = g ( α 2 2 ) ( α 2 ) g_{(\alpha_2, \alpha_2^2)}(r_1) = g_{(\alpha_2^2)}(\alpha_2) g ( α 2 , α 2 2 ) ( r 1 ) = g ( α 2 2 ) ( α 2 ) 1 , 2 1,2 1 , 2 g ( X ) g(X) g ( X )
g ( z 2 , z 3 ) ( r 1 ) = f ~ ( r 1 , z 2 , z 3 ) g ( z 3 ) ( z 2 ) = f ~ ( r 1 , z 2 , z 3 ) g ( α 2 , α 4 ) ( r 1 ) = f ~ ( r 1 , α 2 , α 4 ) g ( α 4 ) ( α 2 ) = f ~ ( r 1 , α 2 , α 4 ) g ( α 1 2 , α 1 4 ) ( r 1 ) = f ~ ( r 1 , α 1 2 , α 1 4 ) g ( α 1 4 ) ( α 1 2 ) = f ~ ( r 1 , α 1 2 , α 1 4 ) \begin{aligned}
& g_{(z_2, z_3)}(r_1) = \tilde{f}(r_1, z_2, z_3) & g_{(z_3)}(z_2) = \tilde{f}(r_1, z_2, z_3)\\
& g_{(\alpha^2, \alpha^4)}(r_1) = \tilde{f}(r_1, \alpha^2, \alpha^4) & g_{(\alpha^4)}(\alpha^2) = \tilde{f}(r_1, \alpha^2, \alpha^4)\\
& g_{(\alpha_1^2, \alpha_1^4)}(r_1) = \tilde{f}(r_1, \alpha_1^2, \alpha_1^4) & g_{(\alpha_1^4)}(\alpha_1^2) = \tilde{f}(r_1, \alpha_1^2, \alpha_1^4)
\end{aligned} g ( z 2 , z 3 ) ( r 1 ) = f ~ ( r 1 , z 2 , z 3 ) g ( α 2 , α 4 ) ( r 1 ) = f ~ ( r 1 , α 2 , α 4 ) g ( α 1 2 , α 1 4 ) ( r 1 ) = f ~ ( r 1 , α 1 2 , α 1 4 ) g ( z 3 ) ( z 2 ) = f ~ ( r 1 , z 2 , z 3 ) g ( α 4 ) ( α 2 ) = f ~ ( r 1 , α 2 , α 4 ) g ( α 1 4 ) ( α 1 2 ) = f ~ ( r 1 , α 1 2 , α 1 4 ) 3.2 当 i = 3 i = 3 i = 3
a. 对每一个 w ⃗ ∈ A 2 = { ( z 3 ) , ( α 4 ) , ( α 1 4 ) , ( α 2 2 ) , ( α 3 ) } \vec{w} \in A_2 = \{(z_3), (\alpha^4), (\alpha_1^4), (\alpha_2^2), (\alpha_3)\} w ∈ A 2 = {( z 3 ) , ( α 4 ) , ( α 1 4 ) , ( α 2 2 ) , ( α 3 )} g w ⃗ ( r 2 ) = g ( w 1 ) g_{\vec{w}}(r_2) = g(w_1) g w ( r 2 ) = g ( w 1 )
g ( z 3 ) ( r 2 ) = g ( z 3 ) g ( α 4 ) ( r 2 ) = g ( α 4 ) g ( α 1 4 ) ( r 2 ) = g ( α 1 4 ) g ( α 2 2 ) ( r 2 ) = g ( α 2 2 ) g ( α 3 ) ( r 2 ) = g ( α 3 ) \begin{aligned}
& g_{(z_3)}(r_2) = g(z_3) \\
& g_{(\alpha^4)}(r_2) = g(\alpha^4) \\
& g_{(\alpha_1^4)}(r_2) = g(\alpha_1^4) \\
& g_{(\alpha_2^2)}(r_2) = g(\alpha_2^2) \\
& g_{(\alpha_3)}(r_2) = g(\alpha_3)
\end{aligned} g ( z 3 ) ( r 2 ) = g ( z 3 ) g ( α 4 ) ( r 2 ) = g ( α 4 ) g ( α 1 4 ) ( r 2 ) = g ( α 1 4 ) g ( α 2 2 ) ( r 2 ) = g ( α 2 2 ) g ( α 3 ) ( r 2 ) = g ( α 3 ) 同样地，上面最后一个式子不需要进行检查，即检查 g ( α 3 ) ( r 2 ) = g ( α 3 ) g_{(\alpha_3)}(r_2) = g(\alpha_3) g ( α 3 ) ( r 2 ) = g ( α 3 ) 2 , 3 2,3 2 , 3 g ( X ) g(X) g ( X )
g ( z 3 ) ( r 2 ) = f ~ ( r 1 , r 2 , z 3 ) g ( z 3 ) = f ~ ( r 1 , r 2 , z 3 ) g ( α 4 ) ( r 2 ) = f ~ ( r 1 , r 2 , α 4 ) g ( α 4 ) = f ~ ( r 1 , r 2 , α 4 ) g ( α 1 4 ) ( r 2 ) = f ~ ( r 1 , r 2 , α 1 4 ) g ( α 1 4 ) = f ~ ( r 1 , r 2 , α 1 4 ) g ( α 2 2 ) ( r 2 ) = f ~ ( r 1 , r 2 , α 2 2 ) g ( α 2 2 ) = f ~ ( r 1 , r 2 , α 2 2 ) \begin{aligned}
& g_{(z_3)}(r_2) = \tilde{f}(r_1, r_2, z_3) & g(z_3) = \tilde{f}(r_1, r_2, z_3)\\
& g_{(\alpha^4)}(r_2) = \tilde{f}(r_1, r_2, \alpha^4) & g(\alpha^4) = \tilde{f}(r_1, r_2, \alpha^4)\\
& g_{(\alpha_1^4)}(r_2) = \tilde{f}(r_1, r_2, \alpha_1^4) & g(\alpha_1^4) = \tilde{f}(r_1, r_2, \alpha_1^4) \\
& g_{(\alpha_2^2)}(r_2) = \tilde{f}(r_1, r_2, \alpha_2^2) & g(\alpha_2^2) = \tilde{f}(r_1, r_2, \alpha_2^2)
\end{aligned} g ( z 3 ) ( r 2 ) = f ~ ( r 1 , r 2 , z 3 ) g ( α 4 ) ( r 2 ) = f ~ ( r 1 , r 2 , α 4 ) g ( α 1 4 ) ( r 2 ) = f ~ ( r 1 , r 2 , α 1 4 ) g ( α 2 2 ) ( r 2 ) = f ~ ( r 1 , r 2 , α 2 2 ) g ( z 3 ) = f ~ ( r 1 , r 2 , z 3 ) g ( α 4 ) = f ~ ( r 1 , r 2 , α 4 ) g ( α 1 4 ) = f ~ ( r 1 , r 2 , α 1 4 ) g ( α 2 2 ) = f ~ ( r 1 , r 2 , α 2 2 ) 第 4 步 ：重复查询 s s s
a. verifier 向 prover 发送 β 0 ← $ L 0 \beta_0 \stackrel{\$}{\leftarrow} L_0 β 0 ← $ L 0 i ∈ [ 3 ] i \in [3] i ∈ [ 3 ] β i : = β i − 1 2 \beta_i := \beta_{i - 1}^2 β i := β i − 1 2
b. 对于每一个 i ∈ [ 3 ] i \in [3] i ∈ [ 3 ] M T . O p e n \mathsf{MT.Open} MT.Open f ( i − 1 ) ( β i − 1 ) f^{(i - 1)}(\beta_{i - 1}) f ( i − 1 ) ( β i − 1 ) f ( i − 1 ) ( − β i − 1 ) f^{(i - 1)}(-\beta_{i - 1}) f ( i − 1 ) ( − β i − 1 )
c. verifier 检查 prover 发送的结果是否正确，调用 M T . V e r i f y \mathsf{MT.Verify} MT.Verify
d. 对于每一个 i ∈ [ 3 ] i \in [3] i ∈ [ 3 ]
( β i − 1 , f ( i − 1 ) ( β i − 1 ) ) , ( − β i − 1 , f ( i − 1 ) ( − β i − 1 ) ) , ( r i , f ( i ) ( β i ) ) \left(\beta_{i - 1}, f^{(i - 1)}(\beta_{i - 1})\right), \quad \left(-\beta_{i - 1}, f^{(i - 1)}(-\beta_{i - 1})\right), \quad \left(r_i, f^{(i)}(\beta_{i})\right) ( β i − 1 , f ( i − 1 ) ( β i − 1 ) ) , ( − β i − 1 , f ( i − 1 ) ( − β i − 1 ) ) , ( r i , f ( i ) ( β i ) ) 这一步 verifier 就是在进行 FRI 折叠的查询，随机检查折叠是否正确，重复查询 s s s
第 5 步 ：如果上面所有的检查都通过，那么 verifier 输出 1 ，表示接受；否则输出 0 ，表示拒绝。
DeepFold 与 sumcheck 的联系 ¶ 由于 DEEP-FRI 的引入，DeepFold 整个协议在每一轮中都需要多引入证明多元线性多项式 f ~ \tilde{f} f ~ n = 3 n = 3 n = 3
这些值的证明隐式地调用了 sumcheck 协议，直到都进行到 sumcheck 最后一步，需要获得 f ~ ( r 1 , r 2 , r 3 ) \tilde{f}(r_1, r_2, r_3) f ~ ( r 1 , r 2 , r 3 )
下面以证明 f ~ ( z 1 , z 2 , z 3 ) = y \tilde{f}(z_1, z_2, z_3) = y f ~ ( z 1 , z 2 , z 3 ) = y
可以发现两个协议在构造一元多项式的方式上有所不同，同时 Verifier 检查的式子也有所不同。
Basefold 中的 sumcheck ¶ Basefold 协议中的 sumcheck 协议比较好理解，因为它的求和的形式比较明显。先将 f ~ ( z 1 , z 2 , z 3 ) \tilde{f}(z_1, z_2, z_3) f ~ ( z 1 , z 2 , z 3 ) { 0 , 1 } 3 \{0,1\}^3 { 0 , 1 } 3
f ~ ( z 1 , z 2 , z 3 ) = ∑ b 3 = { 0 , 1 } ∑ b 2 = { 0 , 1 } ∑ b 1 = { 0 , 1 } f ~ ( b 1 , b 2 , b 3 ) ⋅ e q ~ ( ( b 1 , b 2 , b 3 ) , ( z 1 , z 2 , z 3 ) ) \tilde{f}(z_1, z_2, z_3) = \sum_{b_3 = \{0,1\}}\sum_{b_2= \{0,1\}} \sum_{b_1= \{0,1\}} \tilde{f}(b_1, b_2, b_3) \cdot \tilde{eq}((b_1,b_2,b_3), (z_1, z_2, z_3)) f ~ ( z 1 , z 2 , z 3 ) = b 3 = { 0 , 1 } ∑ b 2 = { 0 , 1 } ∑ b 1 = { 0 , 1 } ∑ f ~ ( b 1 , b 2 , b 3 ) ⋅ e q ~ (( b 1 , b 2 , b 3 ) , ( z 1 , z 2 , z 3 )) 证明 f ~ ( z 1 , z 2 , z 3 ) = y \tilde{f}(z_1, z_2, z_3) = y f ~ ( z 1 , z 2 , z 3 ) = y
∑ b 3 = { 0 , 1 } ∑ b 2 = { 0 , 1 } ∑ b 1 = { 0 , 1 } f ~ ( b 1 , b 2 , b 3 ) ⋅ e q ~ ( ( b 1 , b 2 , b 3 ) , ( z 1 , z 2 , z 3 ) ) = y (6) \sum_{b_3 = \{0,1\}}\sum_{b_2= \{0,1\}} \sum_{b_1= \{0,1\}} \tilde{f}(b_1, b_2, b_3) \cdot \tilde{eq}((b_1,b_2,b_3), (z_1, z_2, z_3)) = y \tag{6} b 3 = { 0 , 1 } ∑ b 2 = { 0 , 1 } ∑ b 1 = { 0 , 1 } ∑ f ~ ( b 1 , b 2 , b 3 ) ⋅ e q ~ (( b 1 , b 2 , b 3 ) , ( z 1 , z 2 , z 3 )) = y ( 6 ) 上式是对 8 个数进行求和的形式，先将 8 个数求和问题转换为两个 4 个数求和问题，分解成两个小问题，接着再用随机数 r 1 r_1 r 1
split: 求和分解 ∑ b 3 = { 0 , 1 } ∑ b 2 = { 0 , 1 } ∑ b 1 = { 0 , 1 } f ~ ( b 1 , b 2 , b 3 ) ⋅ e q ~ ( ( b 1 , b 2 , b 3 ) , ( z 1 , z 2 , z 3 ) ) = ∑ b 3 = { 0 , 1 } ∑ b 2 = { 0 , 1 } f ~ ( 0 , b 2 , b 3 ) ⋅ e q ~ ( ( 0 , b 2 , b 3 ) , ( z 1 , z 2 , z 3 ) ) + ∑ b 3 = { 0 , 1 } ∑ b 2 = { 0 , 1 } f ~ ( 1 , b 2 , b 3 ) ⋅ e q ~ ( ( 1 , b 2 , b 3 ) , ( z 1 , z 2 , z 3 ) ) : = g 1 ( 0 ) + g 1 ( 1 ) \begin{align}
& \sum_{b_3 = \{0,1\}}\sum_{b_2= \{0,1\}} \sum_{b_1= \{0,1\}} \tilde{f}(b_1, b_2, b_3) \cdot \tilde{eq}((b_1,b_2,b_3), (z_1, z_2, z_3)) \\
= & \sum_{b_3 = \{0,1\}}\sum_{b_2= \{0,1\}} \tilde{f}(0, b_2, b_3) \cdot \tilde{eq}((0,b_2,b_3), (z_1, z_2, z_3)) \\
& + \sum_{b_3 = \{0,1\}}\sum_{b_2= \{0,1\}} \tilde{f}(1, b_2, b_3) \cdot \tilde{eq}((1,b_2,b_3), (z_1, z_2, z_3)) \\ \\
:= & g_1(0) + g_1(1)
\end{align} = := b 3 = { 0 , 1 } ∑ b 2 = { 0 , 1 } ∑ b 1 = { 0 , 1 } ∑ f ~ ( b 1 , b 2 , b 3 ) ⋅ e q ~ (( b 1 , b 2 , b 3 ) , ( z 1 , z 2 , z 3 )) b 3 = { 0 , 1 } ∑ b 2 = { 0 , 1 } ∑ f ~ ( 0 , b 2 , b 3 ) ⋅ e q ~ (( 0 , b 2 , b 3 ) , ( z 1 , z 2 , z 3 )) + b 3 = { 0 , 1 } ∑ b 2 = { 0 , 1 } ∑ f ~ ( 1 , b 2 , b 3 ) ⋅ e q ~ (( 1 , b 2 , b 3 ) , ( z 1 , z 2 , z 3 )) g 1 ( 0 ) + g 1 ( 1 ) 因此证明
∑ b 3 = { 0 , 1 } ∑ b 2 = { 0 , 1 } ∑ b 1 = { 0 , 1 } f ~ ( b 1 , b 2 , b 3 ) ⋅ e q ~ ( ( b 1 , b 2 , b 3 ) , ( z 1 , z 2 , z 3 ) ) = y \sum_{b_3 = \{0,1\}}\sum_{b_2= \{0,1\}} \sum_{b_1= \{0,1\}} \tilde{f}(b_1, b_2, b_3) \cdot \tilde{eq}((b_1,b_2,b_3), (z_1, z_2, z_3)) = y b 3 = { 0 , 1 } ∑ b 2 = { 0 , 1 } ∑ b 1 = { 0 , 1 } ∑ f ~ ( b 1 , b 2 , b 3 ) ⋅ e q ~ (( b 1 , b 2 , b 3 ) , ( z 1 , z 2 , z 3 )) = y 可以转换为证明
∑ b 3 = { 0 , 1 } ∑ b 2 = { 0 , 1 } f ~ ( 0 , b 2 , b 3 ) ⋅ e q ~ ( ( 0 , b 2 , b 3 ) , ( z 1 , z 2 , z 3 ) ) = g 1 ( 0 ) ∑ b 3 = { 0 , 1 } ∑ b 2 = { 0 , 1 } f ~ ( 1 , b 2 , b 3 ) ⋅ e q ~ ( ( 1 , b 2 , b 3 ) , ( z 1 , z 2 , z 3 ) ) = g 1 ( 1 ) \begin{align}
\sum_{b_3 = \{0,1\}}\sum_{b_2= \{0,1\}} \tilde{f}(0, b_2, b_3) \cdot \tilde{eq}((0,b_2,b_3), (z_1, z_2, z_3)) = g_1(0) \\
\sum_{b_3 = \{0,1\}}\sum_{b_2= \{0,1\}} \tilde{f}(1, b_2, b_3) \cdot \tilde{eq}((1,b_2,b_3), (z_1, z_2, z_3)) = g_1(1)
\end{align} b 3 = { 0 , 1 } ∑ b 2 = { 0 , 1 } ∑ f ~ ( 0 , b 2 , b 3 ) ⋅ e q ~ (( 0 , b 2 , b 3 ) , ( z 1 , z 2 , z 3 )) = g 1 ( 0 ) b 3 = { 0 , 1 } ∑ b 2 = { 0 , 1 } ∑ f ~ ( 1 , b 2 , b 3 ) ⋅ e q ~ (( 1 , b 2 , b 3 ) , ( z 1 , z 2 , z 3 )) = g 1 ( 1 ) 以及证明 split 是正确的，即证明
g 1 ( 0 ) + g 1 ( 1 ) = y g_1(0) + g_1(1) = y g 1 ( 0 ) + g 1 ( 1 ) = y 总结下将原来的求和问题进行 split 后需要证明 3 项：
(1) split 分解正确：g 1 ( 0 ) + g 1 ( 1 ) = y g_1(0) + g_1(1) = y g 1 ( 0 ) + g 1 ( 1 ) = y
(2) 第一部分求和正确：∑ b 3 = { 0 , 1 } ∑ b 2 = { 0 , 1 } f ~ ( 0 , b 2 , b 3 ) ⋅ e q ~ ( ( 0 , b 2 , b 3 ) , ( z 1 , z 2 , z 3 ) ) = g 1 ( 0 ) \sum_{b_3 = \{0,1\}}\sum_{b_2= \{0,1\}} \tilde{f}(0, b_2, b_3) \cdot \tilde{eq}((0,b_2,b_3), (z_1, z_2, z_3)) = g_1(0) ∑ b 3 = { 0 , 1 } ∑ b 2 = { 0 , 1 } f ~ ( 0 , b 2 , b 3 ) ⋅ e q ~ (( 0 , b 2 , b 3 ) , ( z 1 , z 2 , z 3 )) = g 1 ( 0 )
(3) 第二部分求和正确：∑ b 3 = { 0 , 1 } ∑ b 2 = { 0 , 1 } f ~ ( 1 , b 2 , b 3 ) ⋅ e q ~ ( ( 1 , b 2 , b 3 ) , ( z 1 , z 2 , z 3 ) ) = g 1 ( 1 ) \sum_{b_3 = \{0,1\}}\sum_{b_2= \{0,1\}} \tilde{f}(1, b_2, b_3) \cdot \tilde{eq}((1,b_2,b_3), (z_1, z_2, z_3)) = g_1(1) ∑ b 3 = { 0 , 1 } ∑ b 2 = { 0 , 1 } f ~ ( 1 , b 2 , b 3 ) ⋅ e q ~ (( 1 , b 2 , b 3 ) , ( z 1 , z 2 , z 3 )) = g 1 ( 1 )
可以发现分解之后，证明 (2) 和 (3) 都相比证明原来的问题 ( 6 ) (6) ( 6 ) ( 6 ) (6) ( 6 ) ( 6 ) (6) ( 6 ) r 1 r_1 r 1
fold：通过随机数将证明 (2) 和 (3) 转换为证明 ∑ b 3 = { 0 , 1 } ∑ b 2 = { 0 , 1 } f ~ ( r 1 , b 2 , b 3 ) ⋅ e q ~ ( ( r 1 , b 2 , b 3 ) , ( z 1 , z 2 , z 3 ) ) = g 1 ( r 1 ) (7) \sum_{b_3 = \{0,1\}}\sum_{b_2= \{0,1\}} \tilde{f}(r_1, b_2, b_3) \cdot \tilde{eq}((r_1,b_2,b_3), (z_1, z_2, z_3)) = g_1(r_1) \tag{7} b 3 = { 0 , 1 } ∑ b 2 = { 0 , 1 } ∑ f ~ ( r 1 , b 2 , b 3 ) ⋅ e q ~ (( r 1 , b 2 , b 3 ) , ( z 1 , z 2 , z 3 )) = g 1 ( r 1 ) ( 7 ) 上式相比证明 ( 6 ) (6) ( 6 ) ( 6 ) (6) ( 6 ) ( 7 ) (7) ( 7 )
至此总结下证明 ( 6 ) (6) ( 6 )
split 正确：g 1 ( 0 ) + g 1 ( 1 ) = y g_1(0) + g_1(1) = y g 1 ( 0 ) + g 1 ( 1 ) = y 规模减半的子问题： ∑ b 3 = { 0 , 1 } ∑ b 2 = { 0 , 1 } f ~ ( r 1 , b 2 , b 3 ) ⋅ e q ~ ( ( r 1 , b 2 , b 3 ) , ( z 1 , z 2 , z 3 ) ) = g 1 ( r 1 ) \sum_{b_3 = \{0,1\}}\sum_{b_2= \{0,1\}} \tilde{f}(r_1, b_2, b_3) \cdot \tilde{eq}((r_1,b_2,b_3), (z_1, z_2, z_3)) = g_1(r_1) b 3 = { 0 , 1 } ∑ b 2 = { 0 , 1 } ∑ f ~ ( r 1 , b 2 , b 3 ) ⋅ e q ~ (( r 1 , b 2 , b 3 ) , ( z 1 , z 2 , z 3 )) = g 1 ( r 1 ) 下面就可以对上式继续用 split 以及 fold 的过程，不断将问题的规模减小到一个 Verfier 更容易验证的问题。因此 sumcheck 协议的整个过程可以用这种 split-and-fold 的视角来重新看待，整个流程如下图所示。
Deepfold 中的 sumcheck ¶ DeepFold 中的 sumcheck 协议，同样也是这种 split-and-fold 的思想来证明 f ~ ( z 1 , z 2 , z 3 ) = y \tilde{f}(z_1, z_2, z_3) = y f ~ ( z 1 , z 2 , z 3 ) = y
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 3 + a 6 X 2 X 3 + a 7 X 1 X 2 X 3 \tilde{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_1X_3 + a_6 X_2 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 3 + a 6 X 2 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 3 + a 6 X 2 X 3 + a 7 X 1 X 2 X 3 = ( a 0 + a 2 X 2 + a 4 X 3 + a 6 X 2 X 3 ) + X 1 ⋅ ( a 1 X 1 + a 3 X 2 + a 5 X 3 + a 7 X 2 X 3 ) : = f ~ e v e n ( X 2 , X 3 ) + X 1 ⋅ f ~ o d d ( X 2 , X 3 ) (8) \begin{align}
\tilde{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_1X_3 + a_6 X_2 X_3 + a_7 X_1 X_2 X_3 \\
& = (a_0 + a_2 X_2 + a_4 X_3 + a_6 X_2X_3) + X_1 \cdot (a_1X_1 + a_3 X_2 + a_5 X_3 + a_7 X_2 X_3) \\
& : = \tilde{f}_{even}(X_2, X_3) + X_1 \cdot \tilde{f}_{odd}(X_2, X_3)
\end{align} \tag{8} 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 3 + a 6 X 2 X 3 + a 7 X 1 X 2 X 3 = ( a 0 + a 2 X 2 + a 4 X 3 + a 6 X 2 X 3 ) + X 1 ⋅ ( a 1 X 1 + a 3 X 2 + a 5 X 3 + a 7 X 2 X 3 ) := f ~ e v e n ( X 2 , X 3 ) + X 1 ⋅ f ~ o dd ( X 2 , X 3 ) ( 8 ) 由于
f ~ ( z 1 , z 2 , z 3 ) = a 0 + a 1 z 1 + a 2 z 2 + a 3 z 1 z 2 + a 4 z 3 + a 5 z 1 z 3 + a 6 z 2 z 3 + a 7 z 1 z 2 z 3 \tilde{f}(z_1, z_2, z_3) = a_0 + a_1 z_1 + a_2 z_2 + a_3 z_1 z_2 + a_4 z_3 + a_5 z_1z_3 + a_6 z_2 z_3 + a_7 z_1 z_2 z_3 f ~ ( z 1 , z 2 , z 3 ) = a 0 + a 1 z 1 + a 2 z 2 + a 3 z 1 z 2 + a 4 z 3 + a 5 z 1 z 3 + a 6 z 2 z 3 + a 7 z 1 z 2 z 3 那么证明 f ~ ( z 1 , z 2 , z 3 ) = y \tilde{f}(z_1, z_2, z_3) = y f ~ ( z 1 , z 2 , z 3 ) = y
a 0 + a 1 z 1 + a 2 z 2 + a 3 z 1 z 2 + a 4 z 3 + a 5 z 1 z 3 + a 6 z 2 z 3 + a 7 z 1 z 2 z 3 = y (9) a_0 + a_1 z_1 + a_2 z_2 + a_3 z_1 z_2 + a_4 z_3 + a_5 z_1z_3 + a_6 z_2 z_3 + a_7 z_1 z_2 z_3 = y \tag{9} a 0 + a 1 z 1 + a 2 z 2 + a 3 z 1 z 2 + a 4 z 3 + a 5 z 1 z 3 + a 6 z 2 z 3 + a 7 z 1 z 2 z 3 = y ( 9 ) split ：对上面的求和式按照 ( 8 ) (8) ( 8 ) a 0 + a 1 z 1 + a 2 z 2 + a 3 z 1 z 2 + a 4 z 3 + a 5 z 1 z 3 + a 6 z 2 z 3 + a 7 z 1 z 2 z 3 = ( a 0 + a 2 z 2 + a 4 z 3 + a 6 z 2 z 3 ) + z 1 ⋅ ( a 1 + a 3 z 2 + a 5 z 3 + a 7 z 2 z 3 ) = f ~ e v e n ( z 2 , z 3 ) + z 1 ⋅ f ~ o d d ( z 2 , z 3 ) \begin{align}
& a_0 + a_1 z_1 + a_2 z_2 + a_3 z_1 z_2 + a_4 z_3 + a_5 z_1z_3 + a_6 z_2 z_3 + a_7 z_1 z_2 z_3 \\
= & (a_0 + a_2 z_2 + a_4 z_3 + a_6 z_2z_3) + z_1 \cdot (a_1 + a_3 z_2 + a_5 z_3 + a_7 z_2 z_3) \\
= & \tilde{f}_{even}(z_2, z_3) + z_1 \cdot \tilde{f}_{odd}(z_2, z_3)
\end{align} = = a 0 + a 1 z 1 + a 2 z 2 + a 3 z 1 z 2 + a 4 z 3 + a 5 z 1 z 3 + a 6 z 2 z 3 + a 7 z 1 z 2 z 3 ( a 0 + a 2 z 2 + a 4 z 3 + a 6 z 2 z 3 ) + z 1 ⋅ ( a 1 + a 3 z 2 + a 5 z 3 + a 7 z 2 z 3 ) f ~ e v e n ( z 2 , z 3 ) + z 1 ⋅ f ~ o dd ( z 2 , z 3 ) 这样分解之后，证明 f ~ ( z 1 , z 2 , z 3 ) = y \tilde{f}(z_1, z_2, z_3) = y f ~ ( z 1 , z 2 , z 3 ) = y
(1) split 分解正确：f ~ e v e n ( z 2 , z 3 ) + z 1 ⋅ f ~ o d d ( z 2 , z 3 ) = y \tilde{f}_{even}(z_2, z_3) + z_1 \cdot \tilde{f}_{odd}(z_2, z_3) = y f ~ e v e n ( z 2 , z 3 ) + z 1 ⋅ f ~ o dd ( z 2 , z 3 ) = y
(2) 第一部分求和正确：a 0 + a 2 z 2 + a 4 z 3 + a 6 z 2 z 3 = f ~ e v e n ( z 2 , z 3 ) a_0 + a_2 z_2 + a_4 z_3 + a_6 z_2z_3 = \tilde{f}_{even}(z_2, z_3) a 0 + a 2 z 2 + a 4 z 3 + a 6 z 2 z 3 = f ~ e v e n ( z 2 , z 3 )
(3) 第二部分求和正确：a 1 + a 3 z 2 + a 5 z 3 + a 7 z 2 z 3 = f ~ o d d ( z 2 , z 3 ) a_1 + a_3 z_2 + a_5 z_3 + a_7 z_2 z_3 = \tilde{f}_{odd}(z_2, z_3) a 1 + a 3 z 2 + a 5 z 3 + a 7 z 2 z 3 = f ~ o dd ( z 2 , z 3 )
fold：用随机数 r 1 r_1 r 1 ( a 0 + r 1 a 1 ) + ( a 2 + r 1 a 3 ) z 2 + ( a 4 + r 1 a 5 ) z 3 + ( a 6 + r 1 a 7 ) z 2 z 3 = f ~ e v e n ( z 2 , z 3 ) + r 1 ⋅ f ~ o d d ( z 2 , z 3 ) (a_0 + r_1 a_1) + (a_2 + r_1 a_3) z_2 + (a_4 + r_1 a_5) z_3 + (a_6 + r_1 a_7) z_2z_3 = \tilde{f}_{even}(z_2, z_3) + r_1 \cdot \tilde{f}_{odd}(z_2, z_3) ( a 0 + r 1 a 1 ) + ( a 2 + r 1 a 3 ) z 2 + ( a 4 + r 1 a 5 ) z 3 + ( a 6 + r 1 a 7 ) z 2 z 3 = f ~ e v e n ( z 2 , z 3 ) + r 1 ⋅ f ~ o dd ( z 2 , z 3 ) 若令 y ′ = f ~ e v e n ( z 2 , z 3 ) + r 1 ⋅ f ~ o d d ( z 2 , z 3 ) y' = \tilde{f}_{even}(z_2, z_3) + r_1 \cdot \tilde{f}_{odd}(z_2, z_3) y ′ = f ~ e v e n ( z 2 , z 3 ) + r 1 ⋅ f ~ o dd ( z 2 , z 3 )
a 0 ′ = a 0 + r 1 a 1 a 1 ′ = a 2 + r 1 a 3 a 2 ′ = a 4 + r 1 a 5 a 3 ′ = a 6 + r 1 a 7 \begin{align}
a_0' = a_0 + r_1 a_1 \quad a_1' = a_2 + r_1 a_3 \quad a_2' = a_4 + r_1 a_5 \quad a_3' = a_6 + r_1 a_7
\end{align} a 0 ′ = a 0 + r 1 a 1 a 1 ′ = a 2 + r 1 a 3 a 2 ′ = a 4 + r 1 a 5 a 3 ′ = a 6 + r 1 a 7 可以看到证明的问题规模减半，即证明
a 0 ′ + a 1 ′ z 2 + a 2 ′ z 3 + a 3 ′ z 2 z 3 = y ′ a_0' + a_1' z_2 + a_2' z_3 + a_3' z_2z_3 = y' a 0 ′ + a 1 ′ z 2 + a 2 ′ z 3 + a 3 ′ z 2 z 3 = y ′ 并且该求和形式与 ( 9 ) (9) ( 9 )
至此总结下证明 ( 9 ) (9) ( 9 )
split 证明：f ~ e v e n ( z 2 , z 3 ) + z 1 ⋅ f ~ o d d ( z 2 , z 3 ) = y \tilde{f}_{even}(z_2, z_3) + z_1 \cdot \tilde{f}_{odd}(z_2, z_3) = y f ~ e v e n ( z 2 , z 3 ) + z 1 ⋅ f ~ o dd ( z 2 , z 3 ) = y 规模减半的子问题： ( a 0 + r 1 a 1 ) + ( a 2 + r 1 a 3 ) z 2 + ( a 4 + r 1 a 5 ) z 3 + ( a 6 + r 1 a 7 ) z 2 z 3 = f ~ e v e n ( z 2 , z 3 ) + r 1 ⋅ f ~ o d d ( z 2 , z 3 ) (a_0 + r_1 a_1) + (a_2 + r_1 a_3) z_2 + (a_4 + r_1 a_5) z_3 + (a_6 + r_1 a_7) z_2z_3 = \tilde{f}_{even}(z_2, z_3) + r_1 \cdot \tilde{f}_{odd}(z_2, z_3) ( a 0 + r 1 a 1 ) + ( a 2 + r 1 a 3 ) z 2 + ( a 4 + r 1 a 5 ) z 3 + ( a 6 + r 1 a 7 ) z 2 z 3 = f ~ e v e n ( z 2 , z 3 ) + r 1 ⋅ f ~ o dd ( z 2 , z 3 ) 通过 f ~ ( X 1 , X 2 , X 3 ) \tilde{f}(X_1, X_2, X_3) f ~ ( X 1 , X 2 , X 3 )
f ~ e v e n ( z 2 , z 3 ) + r 1 ⋅ f ~ o d d ( z 2 , z 3 ) = ( a 0 + a 2 z 2 + a 4 z 3 + a 6 z 2 z 3 ) + r 1 ⋅ ( a 1 + a 3 z 2 + a 5 z 3 + a 7 z 2 z 3 ) = a 0 + a 1 r 1 + a 2 z 2 + a 3 r 1 z 2 + a 4 z 3 + a 5 r 1 z 3 + a 6 z 2 z 3 + a 7 r 1 z 2 z 3 = f ~ ( r 1 , z 2 , z 3 ) \begin{align}
& \tilde{f}_{even}(z_2, z_3) + r_1 \cdot \tilde{f}_{odd}(z_2, z_3) \\
= & (a_0 + a_2 z_2 + a_4 z_3 + a_6 z_2z_3) + r_1 \cdot (a_1 + a_3 z_2 + a_5 z_3 + a_7 z_2 z_3) \\
= & a_0 + a_1 r_1 + a_2 z_2 + a_3 r_1 z_2 + a_4 z_3 + a_5 r_1z_3 + a_6 z_2 z_3 + a_7 r_1 z_2 z_3 \\
= & \tilde{f}(r_1, z_2, z_3)
\end{align} = = = f ~ e v e n ( z 2 , z 3 ) + r 1 ⋅ f ~ o dd ( z 2 , z 3 ) ( a 0 + a 2 z 2 + a 4 z 3 + a 6 z 2 z 3 ) + r 1 ⋅ ( a 1 + a 3 z 2 + a 5 z 3 + a 7 z 2 z 3 ) a 0 + a 1 r 1 + a 2 z 2 + a 3 r 1 z 2 + a 4 z 3 + a 5 r 1 z 3 + a 6 z 2 z 3 + a 7 r 1 z 2 z 3 f ~ ( r 1 , z 2 , z 3 ) 令 g 1 ( X ) = f ~ ( X , z 2 , z 3 ) g_1(X) = \tilde{f}(X, z_2, z_3) g 1 ( X ) = f ~ ( X , z 2 , z 3 ) f ~ e v e n ( z 2 , z 3 ) + r 1 ⋅ f ~ o d d ( z 2 , z 3 ) = g 1 ( r 1 ) \tilde{f}_{even}(z_2, z_3) + r_1 \cdot \tilde{f}_{odd}(z_2, z_3) = g_1(r_1) f ~ e v e n ( z 2 , z 3 ) + r 1 ⋅ f ~ o dd ( z 2 , z 3 ) = g 1 ( r 1 )
f ~ e v e n ( z 2 , z 3 ) = g 1 ( 0 ) f ~ o d d ( z 2 , z 3 ) = g 1 ( 1 ) − g 1 ( 0 ) f ~ e v e n ( z 2 , z 3 ) + z 1 ⋅ f ~ o d d ( z 2 , z 3 ) = g 1 ( 0 ) + z 1 ( g 1 ( 1 ) − g 1 ( 0 ) ) = g 1 ( z 1 ) \begin{align}
& \tilde{f}_{even}(z_2, z_3) = g_1(0) \\
& \tilde{f}_{odd}(z_2, z_3) = g_1(1) - g_1(0) \\
& \tilde{f}_{even}(z_2, z_3) + z_1 \cdot \tilde{f}_{odd}(z_2, z_3) = g_1(0) + z_1(g_1(1) - g_1(0)) = g_1(z_1)
\end{align} f ~ e v e n ( z 2 , z 3 ) = g 1 ( 0 ) f ~ o dd ( z 2 , z 3 ) = g 1 ( 1 ) − g 1 ( 0 ) f ~ e v e n ( z 2 , z 3 ) + z 1 ⋅ f ~ o dd ( z 2 , z 3 ) = g 1 ( 0 ) + z 1 ( g 1 ( 1 ) − g 1 ( 0 )) = g 1 ( z 1 ) 那么这个证明可以写为
split 证明：g 1 ( 0 ) + z 1 ( g 1 ( 1 ) − g 1 ( 0 ) ) = y g_1(0) + z_1(g_1(1) - g_1(0)) = y g 1 ( 0 ) + z 1 ( g 1 ( 1 ) − g 1 ( 0 )) = y 规模减半的子问题： ( a 0 + r 1 a 1 ) + ( a 2 + r 1 a 3 ) z 2 + ( a 4 + r 1 a 5 ) z 3 + ( a 6 + r 1 a 7 ) z 2 z 3 = g 1 ( r 1 ) (a_0 + r_1 a_1) + (a_2 + r_1 a_3) z_2 + (a_4 + r_1 a_5) z_3 + (a_6 + r_1 a_7) z_2z_3 = g_1(r_1) ( a 0 + r 1 a 1 ) + ( a 2 + r 1 a 3 ) z 2 + ( a 4 + r 1 a 5 ) z 3 + ( a 6 + r 1 a 7 ) z 2 z 3 = g 1 ( r 1 ) 接着用同样的方式对上式用 split-and-fold 。DeepFold 协议中的 sumcheck 流程如下图所示。
References ¶ [GLHQTZ24] Yanpei Guo, Xuanming Liu, Kexi Huang, Wenjie Qu, Tianyang Tao, and Jiaheng Zhang. “DeepFold: Efficient Multilinear Polynomial Commitment from Reed-Solomon Code and Its Application to Zero-knowledge Proofs.” Cryptology ePrint Archive (2024). [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). [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. [BGKS20] Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, and Shubhangi Saraf. “DEEP-FRI: sampling outside the box improves soundness.” arXiv preprint arXiv:1903.12243 (2019). [H24] Ulrich Haböck. “Basefold in the List Decoding Regime.” Cryptology ePrint Archive (2024).
