Gemini 协议 [BCH+22] 为我们提供了一种将 multilinear polynomial PCS 转换为一元多项式承诺方案的思路。简单回顾下，即为了证明一个 MLE 多项式在某个点的打开值为 v v v
下面借鉴HyperPlonk 论文 [BBBZ23] 附录 B 中的描述，给出 Gemini 对接 FRI PCS 的详细协议。
协议描述 ¶ 证明目标：对于一个有 n n n f ~ ( X 0 , X 1 , … , X n − 1 ) \tilde{f}(X_0, X_1, \ldots, X_{n - 1}) f ~ ( X 0 , X 1 , … , X n − 1 )
f ~ ( X 0 , X 1 , … , X n − 1 ) = ∑ i = 0 2 n − 1 c i ⋅ X 0 i 0 X 1 i 1 ⋯ X n − 1 i n − 1 \tilde{f}(X_0, X_1, \ldots, X_{n - 1}) = \sum_{i = 0}^{2^n - 1}c_i \cdot X_0^{i_0} X_1^{i_1} \cdots X_{n - 1}^{i_{n-1}} f ~ ( X 0 , X 1 , … , X n − 1 ) = i = 0 ∑ 2 n − 1 c i ⋅ X 0 i 0 X 1 i 1 ⋯ X n − 1 i n − 1 其中 ( i 0 , i 1 , … , i n − 1 ) (i_0, i_1,\ldots,i_{n - 1}) ( i 0 , i 1 , … , i n − 1 ) i i i i 0 i_0 i 0 i = ∑ j = 0 n − 1 i j 2 j i = \sum_{j=0}^{n-1}i_j 2^{j} i = ∑ j = 0 n − 1 i j 2 j
证明的目标是证明 f ~ ( X 0 , X 1 , … , X n − 1 ) \tilde{f}(X_0, X_1, \ldots, X_{n - 1}) f ~ ( X 0 , X 1 , … , X n − 1 ) u ⃗ = ( u 0 , u 1 , … , u n − 1 ) \vec{u} = (u_0,u_1, \ldots, u_{n - 1}) u = ( u 0 , u 1 , … , u n − 1 ) v = f ~ ( u 0 , u 1 , … , u n − 1 ) v = \tilde{f}(u_0,u_1, \ldots, u_{n - 1}) v = f ~ ( u 0 , u 1 , … , u n − 1 )
公共输入 ¶ FRI 协议参数：Reed Solomon 编码选取的区域 D n ⊂ D n − 1 ⊂ ⋯ ⊂ D 0 = D D_n \subset D_{n-1} \subset \cdots \subset D_0 = D D n ⊂ D n − 1 ⊂ ⋯ ⊂ D 0 = D l l l 多项式 f ( X ) f(X) f ( X ) C f C_f C f C f = c m ( [ f ( x ) ∣ x ∈ D ] ) = M T . c o m m i t ( [ f ( x ) ∣ x ∈ D ] ) C_f = \mathsf{cm}([f(x)|_{x \in D}]) = \mathsf{MT.commit}([f(x)|_{x \in D}]) C f = cm ([ f ( x ) ∣ x ∈ D ]) = MT.commit ([ f ( x ) ∣ x ∈ D ]) 其中 f ( X ) f(X) f ( X ) 2 n − 1 2^n - 1 2 n − 1 f ~ \tilde{f} f ~ c ⃗ \vec{c} c
f ( X ) = ∑ i = 0 2 n − 1 c i ⋅ X i f(X) = \sum_{i = 0}^{2^n - 1} c_i \cdot X^i f ( X ) = i = 0 ∑ 2 n − 1 c i ⋅ X i 求值点 u ⃗ = ( u 0 , u 1 , … , u n − 1 ) \vec{u} = (u_0,u_1, \ldots, u_{n - 1}) u = ( u 0 , u 1 , … , u n − 1 ) v = f ~ ( u 0 , u 1 , … , u n − 1 ) v = \tilde{f}(u_0,u_1, \ldots, u_{n - 1}) v = f ~ ( u 0 , u 1 , … , u n − 1 ) Witness ¶ 多元多项式 f ~ ( X 0 , X 1 , … , X n − 1 ) \tilde{f}(X_0, X_1, \ldots, X_{n - 1}) f ~ ( X 0 , X 1 , … , X n − 1 ) c ⃗ = ( c 0 , c 1 , … , c 2 n − 1 ) \vec{c} = (c_0,c_1, \ldots, c_{2^n - 1}) c = ( c 0 , c 1 , … , c 2 n − 1 ) Round 1 ¶ Prover 记 h 0 ( X ) = f ( X ) h_0(X) = f(X) h 0 ( X ) = f ( X ) h 1 ( X ) , h 2 ( X ) , … , h n − 1 ( X ) h_1(X), h_2(X), \ldots, h_{n-1}(X) h 1 ( X ) , h 2 ( X ) , … , h n − 1 ( X ) i = 1 , … , n − 1 i = 1, \ldots, n-1 i = 1 , … , n − 1 h i ( X 2 ) = h i − 1 ( X ) + h i − 1 ( − X ) 2 + u i − 1 ⋅ h i − 1 ( X ) − h i − 1 ( − X ) 2 X h_{i}(X^{2}) = \frac{h_{i - 1}(X) + h_{i - 1}(-X)}{2} + u_{i - 1} \cdot \frac{h_{i - 1}(X) - h_{i - 1}(-X)}{2X} h i ( X 2 ) = 2 h i − 1 ( X ) + h i − 1 ( − X ) + u i − 1 ⋅ 2 X h i − 1 ( X ) − h i − 1 ( − X ) Prover 计算承诺 ( C h 1 , C h 2 , … , C h n − 1 ) (C_{h_{1}},C_{h_{2}}, \ldots, C_{h_{n-1}}) ( C h 1 , C h 2 , … , C h n − 1 ) i = 1 , … , n − 1 i = 1, \ldots, n-1 i = 1 , … , n − 1 C h i = c m ( [ h i ( x ) ∣ x ∈ D ] ) = M T . c o m m i t ( [ h i ( x ) ∣ x ∈ D ) C_{h_{i}} = \mathsf{cm}([h_{i}(x)|_{x \in D}]) = \mathsf{MT.commit}([h_{i}(x)|_{x \in D}) C h i = cm ([ h i ( x ) ∣ x ∈ D ]) = MT.commit ([ h i ( x ) ∣ x ∈ D ) Round 2 ¶ Verifier 发送随机数 β ← $ F ∗ ∖ D \beta \stackrel{\$}{\leftarrow} \mathbb{F}^* \setminus D β ← $ F ∗ ∖ D Prover 计算 { h i ( β ) , h i ( − β ) , h i ( β 2 ) } i = 0 n − 1 \{h_i(\beta), h_{i}(- \beta), h_i(\beta^2)\}_{i = 0}^{n-1} { h i ( β ) , h i ( − β ) , h i ( β 2 ) } i = 0 n − 1 Round 3 ¶ Verifier 发送随机数 r ← $ F r \stackrel{\$}{\leftarrow} \mathbb{F} r ← $ F 先对每一个多项式 h i ( X ) ( i = 1 , … , n ) h_{i}(X)(i = 1, \ldots, n) h i ( X ) ( i = 1 , … , n ) 2 n − 1 2^{n}- 1 2 n − 1 deg ( h i ) = 2 n − i − 1 \deg(h_i)=2^{n-i}-1 deg ( h i ) = 2 n − i − 1 i = 1 , … , n − 1 i = 1, \ldots, n - 1 i = 1 , … , n − 1 h i ′ ( X ) h'_i(X) h i ′ ( X ) 方法一：
h i ′ ( X ) = h i ( X ) + r ⋅ X 2 n − 2 n − i ⋅ h i ( X ) h'_i(X)=h_i(X)+r\cdot X^{2^{n} - 2^{n-i}} \cdot h_i(X) h i ′ ( X ) = h i ( X ) + r ⋅ X 2 n − 2 n − i ⋅ h i ( X ) 方法二：若采用 STIR 论文 [ACFY24] 中的 degree correction 方法，则
h i ′ ( X ) = ∑ j = 0 2 n − 2 n − i r j ⋅ X j ⋅ h i ( X ) = h i ( X ) + r ⋅ X ⋅ h i ( X ) + r 2 ⋅ X 2 ⋅ h i ( X ) + … + r 2 n − 2 n − i ⋅ X 2 n − 2 n − i ⋅ h i ( X ) h'_i(X)=\sum_{j = 0}^{2^{n}- 2^{n - i}} r^{j} \cdot X^{j} \cdot h_i(X)=h_i(X)+r\cdot X \cdot h_i(X)+r^{2} \cdot X^2 \cdot h_i(X) + \ldots + r^{2^n - 2^{n-i}} \cdot X^{2^n - 2^{n-i}} \cdot h_i(X) h i ′ ( X ) = j = 0 ∑ 2 n − 2 n − i r j ⋅ X j ⋅ h i ( X ) = h i ( X ) + r ⋅ X ⋅ h i ( X ) + r 2 ⋅ X 2 ⋅ h i ( X ) + … + r 2 n − 2 n − i ⋅ X 2 n − 2 n − i ⋅ h i ( X ) 注：方法二会比方法一有更高的安全性。([ACFY24, 2.3])
将 h 0 ( X ) h_0(X) h 0 ( X ) h 1 ′ ( X ) , … , h n − 1 ′ ( X ) h_1'(X), \ldots, h_{n-1}'(X) h 1 ′ ( X ) , … , h n − 1 ′ ( X ) r r r 方法一：计算
h ∗ ( X ) = h 0 ( X ) + r 1 + ( 0 ) ⋅ h 1 ′ ( X ) + r 2 + ( 0 + 1 ) ⋅ h 2 ′ ( X ) + r 3 + ( 0 + 1 + 1 ) ⋅ h 3 ′ ( X ) + … + r n − 1 + ( 0 + 1 ⋅ ( n − 2 ) ) ⋅ h n − 1 ′ ( X ) = h 0 ( X ) + r ⋅ h 1 ′ ( X ) + r 3 ⋅ h 2 ′ ( X ) + r 5 ⋅ h 3 ′ ( X ) + … + r 2 n − 3 ⋅ h n − 1 ′ ( X ) (1) \begin{align*}
h^*(X) & = h_0(X) + r^{1 + (0)} \cdot h_1'(X) + r^{2 + (0 + 1)} \cdot h_2'(X) + r^{3 + (0 + 1 + 1)} \cdot h_3'(X)+ \ldots + r^{n - 1 + (0 + 1 \cdot (n - 2))} \cdot h_{n-1}'(X) \\
& = h_0(X) + r \cdot h_1'(X) + r^{3} \cdot h_2'(X) + r^{5} \cdot h_3'(X)+ \ldots + r^{2n-3} \cdot h_{n-1}'(X)
\end{align*} \tag{1} h ∗ ( X ) = h 0 ( X ) + r 1 + ( 0 ) ⋅ h 1 ′ ( X ) + r 2 + ( 0 + 1 ) ⋅ h 2 ′ ( X ) + r 3 + ( 0 + 1 + 1 ) ⋅ h 3 ′ ( X ) + … + r n − 1 + ( 0 + 1 ⋅ ( n − 2 )) ⋅ h n − 1 ′ ( X ) = h 0 ( X ) + r ⋅ h 1 ′ ( X ) + r 3 ⋅ h 2 ′ ( X ) + r 5 ⋅ h 3 ′ ( X ) + … + r 2 n − 3 ⋅ h n − 1 ′ ( X ) ( 1 ) 方法二：若采用 STIR 论文中的 degree correction 方法，则此时 batch 的多项式计算为
h ∗ ( X ) = h 0 ( X ) + r 1 + ( 0 ) ⋅ h 1 ′ ( X ) + r 2 + ( 0 + e 1 ) ⋅ h 2 ′ ( X ) + r 3 + ( 0 + e 1 + e 2 ) ⋅ h 3 ′ ( X ) + … + r n − 1 + ( 0 + e 1 + e 2 + … + e n − 2 ) ⋅ h n − 1 ′ ( X ) = h 0 ( X ) + r ⋅ h 1 ′ ( X ) + r 2 + 2 n − 2 n − 1 ⋅ h 2 ′ ( X ) + r 2 + ∑ i = 1 2 ( 2 n − 2 i ) ⋅ h 3 ′ ( X ) + … + r n − 1 + ∑ i = 1 n − 2 ( 2 n − 2 i ) ⋅ h n − 1 ′ ( X ) (2) \begin{align*}
h^*(X) & = h_0(X) + r^{1 + (0)} \cdot h_1'(X) + r^{2 + (0 + e_1)} \cdot h_2'(X) + r^{3 + (0 + e_1 + e_2)} \cdot h_3'(X)\\
& \quad + \ldots + r^{n - 1 + (0 + e_1 + e_2 + \ldots + e_{n-2})} \cdot h_{n-1}'(X) \\
& = h_0(X) + r \cdot h_1'(X) + r^{2 + 2^n - 2^{n -1}} \cdot h_2'(X) + r^{2 + \sum_{i=1}^{2}(2^n-2^i)} \cdot h_3'(X) \\
& \quad + \ldots + r^{n - 1+\sum_{i=1}^{n-2}(2^n-2^i)} \cdot h_{n-1}'(X)
\end{align*} \tag{2} h ∗ ( X ) = h 0 ( X ) + r 1 + ( 0 ) ⋅ h 1 ′ ( X ) + r 2 + ( 0 + e 1 ) ⋅ h 2 ′ ( X ) + r 3 + ( 0 + e 1 + e 2 ) ⋅ h 3 ′ ( X ) + … + r n − 1 + ( 0 + e 1 + e 2 + … + e n − 2 ) ⋅ h n − 1 ′ ( X ) = h 0 ( X ) + r ⋅ h 1 ′ ( X ) + r 2 + 2 n − 2 n − 1 ⋅ h 2 ′ ( X ) + r 2 + ∑ i = 1 2 ( 2 n − 2 i ) ⋅ h 3 ′ ( X ) + … + r n − 1 + ∑ i = 1 n − 2 ( 2 n − 2 i ) ⋅ h n − 1 ′ ( X ) ( 2 ) 计算商多项式 q ′ ( X ) q'(X) q ′ ( X ) h ∗ ( X ) h^*(X) h ∗ ( X ) ( β , − β , β 2 ) (\beta,-\beta,\beta^2) ( β , − β , β 2 ) q ′ ( X ) = h ∗ ( X ) − h ∗ ( β ) X − β + h ∗ ( X ) − h ∗ ( − β ) X + β + h ∗ ( X ) − h ∗ ( β 2 ) X − β 2 q'(X) = \frac{h^*(X)-h^*(\beta)}{X-\beta} + \frac{h^*(X)-h^*(-\beta)}{X+\beta} + \frac{h^*(X)-h^*(\beta^2)}{X-\beta^2} q ′ ( X ) = X − β h ∗ ( X ) − h ∗ ( β ) + X + β h ∗ ( X ) − h ∗ ( − β ) + X − β 2 h ∗ ( X ) − h ∗ ( β 2 ) 上述商多项式的构造参考论文 [H22] Multi-point queries 小节。
Round 4 ¶ 这一轮将商多项式 q ′ ( X ) q'(X) q ′ ( X )
Verifier 发送随机数 λ ← $ F \lambda \stackrel{\$}{\leftarrow} \mathbb{F} λ ← $ F Prover 计算 q ( X ) = ( 1 + λ ⋅ X ) q ′ ( X ) q(X) = (1 + \lambda \cdot X) q'(X) q ( X ) = ( 1 + λ ⋅ X ) q ′ ( X ) 在 D D D
Round 5 ¶ Prover 和 Verifier 进行 FRI 的 low degree test 证明交互，证明 q ( X ) q(X) q ( X ) 2 n 2^n 2 n
π q = F R I . L D T ( q ( X ) , 2 n ) \pi_{q} = \mathsf{FRI.LDT}(q(X), 2^n) π q = FRI.LDT ( q ( X ) , 2 n ) 这里包含 n n n i i i i i i
记 q ( 0 ) ( x ) ∣ x ∈ D : = q ( x ) ∣ x ∈ D q^{(0)}(x)|_{x \in D} := q(x)|_{x \in D} q ( 0 ) ( x ) ∣ x ∈ D := q ( x ) ∣ x ∈ D
对于 i = 1 , … , n i = 1,\ldots, n i = 1 , … , n
Verifier 发送随机数 α ( i ) \alpha^{(i)} α ( i ) 对于任意的 y ∈ D i y \in D_i y ∈ D i D i − 1 D_{i - 1} D i − 1 x x x x 2 = y x^2 = y x 2 = y q ( i ) ( y ) = q ( i − 1 ) ( x ) + q ( i − 1 ) ( − x ) 2 + α ( i ) ⋅ q ( i − 1 ) ( x ) − q ( i − 1 ) ( − x ) 2 x q^{(i)}(y) = \frac{q^{(i - 1)}(x) + q^{(i - 1)}(-x)}{2} + \alpha^{(i)} \cdot \frac{q^{(i - 1)}(x) - q^{(i - 1)}(-x)}{2x} q ( i ) ( y ) = 2 q ( i − 1 ) ( x ) + q ( i − 1 ) ( − x ) + α ( i ) ⋅ 2 x q ( i − 1 ) ( x ) − q ( i − 1 ) ( − x ) 如果 i < n i < n i < n [ q ( i ) ( x ) ∣ x ∈ D i ] [q^{(i)}(x)|_{x \in D_{i}}] [ q ( i ) ( x ) ∣ x ∈ D i ] c m ( q ( i ) ( X ) ) = c m ( [ q ( i ) ( x ) ∣ x ∈ D i ] ) = M T . c o m m i t ( [ q ( i ) ( x ) ∣ x ∈ D i ] ) \mathsf{cm}(q^{(i)}(X)) = \mathsf{cm}([q^{(i)}(x)|_{x \in D_{i}}]) = \mathsf{MT.commit}([q^{(i)}(x)|_{x \in D_{i}}]) cm ( q ( i ) ( X )) = cm ([ q ( i ) ( x ) ∣ x ∈ D i ]) = MT.commit ([ q ( i ) ( x ) ∣ x ∈ D i ]) 如果 i = n i = n i = n x 0 ∈ D n x_0 \in D_{n} x 0 ∈ D n q ( i ) ( x 0 ) q^{(i)}(x_0) q ( i ) ( x 0 ) 📝 Notes
如果折叠次数 r < n r < n r < n r r r
Round 6 ¶ 这一轮是接着 Prover 与 Verifier 进行 FRI 协议的 low degree test 交互的查询阶段，Verifier 重复查询 l l l D 0 D_0 D 0 i i i
重复 l l l
Verifier 从 D 0 D_0 D 0 s ( 0 ) ← $ D 0 s^{(0)} \stackrel{\$}{\leftarrow} D_0 s ( 0 ) ← $ D 0
Prover 打开 { h i ( s ( 0 ) ) } i = 0 n − 1 \{h_i(s^{(0)})\}_{i = 0}^{n-1} { h i ( s ( 0 ) ) } i = 0 n − 1 { h i ( − s ( 0 ) ) } i = 0 n − 1 \{h_i(-s^{(0)})\}_{i = 0}^{n-1} { h i ( − s ( 0 ) ) } i = 0 n − 1
{ ( h i ( s ( 0 ) ) , π h i ( s ( 0 ) ) ) } i = 0 n − 1 ← { M T . o p e n ( [ h i ( x ) ∣ x ∈ D 0 ] , s ( 0 ) ) } i = 0 n − 1 \{(h_i(s^{(0)}), \pi_{h_i}(s^{(0)}))\}_{i = 0}^{n-1} \leftarrow \{\mathsf{MT.open}([h_i(x)|_{x \in D_0}], s^{(0)})\}_{i = 0}^{n-1} {( h i ( s ( 0 ) ) , π h i ( s ( 0 ) )) } i = 0 n − 1 ← { MT.open ([ h i ( x ) ∣ x ∈ D 0 ] , s ( 0 ) ) } i = 0 n − 1 { ( h i ( − s ( 0 ) ) , π h i ( − s ( 0 ) ) ) } i = 0 n − 1 ← { M T . o p e n ( [ h i ( x ) ∣ x ∈ D 0 ] , − s ( 0 ) ) } i = 0 n − 1 \{(h_i(-s^{(0)}), \pi_{h_i}(-s^{(0)}))\}_{i = 0}^{n-1} \leftarrow \{\mathsf{MT.open}([h_i(x)|_{x \in D_0}], -s^{(0)})\}_{i = 0}^{n-1} {( h i ( − s ( 0 ) ) , π h i ( − s ( 0 ) )) } i = 0 n − 1 ← { MT.open ([ h i ( x ) ∣ x ∈ D 0 ] , − s ( 0 ) ) } i = 0 n − 1 Prover 计算 s ( 1 ) = ( s ( 0 ) ) 2 s^{(1)} = (s^{(0)})^2 s ( 1 ) = ( s ( 0 ) ) 2
对于 i = 1 , … , n − 1 i = 1, \ldots, n - 1 i = 1 , … , n − 1
Prover 发送 q ( i ) ( s ( i ) ) , q ( i ) ( − s ( i ) ) q^{(i)}(s^{(i)}), q^{(i)}(-s^{(i)}) q ( i ) ( s ( i ) ) , q ( i ) ( − s ( i ) ) { ( q ( i ) ( s ( i ) ) , π q ( i ) ( s ( i ) ) ) } ← M T . o p e n ( [ q ( i ) ( x ) ∣ x ∈ D i ] , s ( i ) ) \{(q^{(i)}(s^{(i)}), \pi_{q^{(i)}}(s^{(i)}))\} \leftarrow \mathsf{MT.open}([q^{(i)}(x)|_{x \in D_i}], s^{(i)}) {( q ( i ) ( s ( i ) ) , π q ( i ) ( s ( i ) ))} ← MT.open ([ q ( i ) ( x ) ∣ x ∈ D i ] , s ( i ) ) { ( q ( i ) ( − s ( i ) ) , π q ( i ) ( − s ( i ) ) ) } ← M T . o p e n ( [ q ( i ) ( x ) ∣ x ∈ D i ] , − s ( i ) ) \{(q^{(i)}(-s^{(i)}), \pi_{q}^{(i)}(-s^{(i)}))\} \leftarrow \mathsf{MT.open}([q^{(i)}(x)|_{x \in D_i}], -s^{(i)}) {( q ( i ) ( − s ( i ) ) , π q ( i ) ( − s ( i ) ))} ← MT.open ([ q ( i ) ( x ) ∣ x ∈ D i ] , − s ( i ) ) Prover 计算 s ( i + 1 ) = ( s ( i ) ) 2 s^{(i + 1)} = (s^{(i)})^2 s ( i + 1 ) = ( s ( i ) ) 2 如果折叠次数 r < n r < n r < n q ( r ) ( s ( r ) ) q^{(r)}(s^{(r)}) q ( r ) ( s ( r ) )
Proof ¶ Prover 发送的证明为
π = ( C h 1 , C h 2 , … , C h n − 1 , { h i ( β ) , h i ( − β ) , h i ( β 2 ) } i = 0 n − 1 , π q ) \pi = (C_{h_{1}},C_{h_{2}}, \ldots, C_{h_{n-1}}, \{h_i(\beta), h_{i}(- \beta), h_i(\beta^2)\}_{i = 0}^{n-1}, \pi_{q}) π = ( C h 1 , C h 2 , … , C h n − 1 , { h i ( β ) , h i ( − β ) , h i ( β 2 ) } i = 0 n − 1 , π q ) 用符号 { ⋅ } l \{\cdot\}^l { ⋅ } l l l l
π q = ( c m ( q ( 1 ) ( X ) ) , … , c m ( q ( n − 1 ) ( X ) ) , q ( n ) ( x 0 ) , { h 0 ( s ( 0 ) ) , π h 0 ( s ( 0 ) ) , h 0 ( − s ( 0 ) ) , π h 0 ( − s ( 0 ) ) , ⋯ , h n − 1 ( s ( 0 ) ) , π h n − 1 ( s ( 0 ) ) , h n − 1 ( − s ( 0 ) ) , π h n − 1 ( − s ( 0 ) ) , q ( 1 ) ( s ( 1 ) ) , π q ( 1 ) ( s ( 1 ) ) , q ( 1 ) ( − s ( 1 ) ) , π q ( 1 ) ( − s ( 1 ) ) , … , q ( n − 1 ) ( s ( n − 1 ) ) , π q ( n − 1 ) ( s ( n − 1 ) ) , q ( n − 1 ) ( − s ( n − 1 ) ) , π q ( i ) ( − s ( n − 1 ) ) } l ) \begin{aligned}
\pi_{q} = & ( \mathsf{cm}(q^{(1)}(X)), \ldots, \mathsf{cm}(q^{(n - 1)}(X)),q^{(n)}(x_0), \\
& \, \{h_0(s^{(0)}), \pi_{h_0}(s^{(0)}), h_0(- s^{(0)}), \pi_{h_0}(-s^{(0)}), \cdots ,\\
& \quad h_{n-1}(s^{(0)}), \pi_{h_{n-1}}(s^{(0)}), h_{n-1}(- s^{(0)}), \pi_{h_{n-1}}(-s^{(0)}), \\
& \quad q^{(1)}(s^{(1)}), \pi_{q^{(1)}}(s^{(1)}),q^{(1)}(-s^{(1)}), \pi_{q^{(1)}}(-s^{(1)}), \ldots, \\
& \quad q^{(n - 1)}(s^{(n - 1)}), \pi_{q^{(n - 1)}}(s^{(n - 1)}),q^{(n - 1)}(-s^{(n - 1)}), \pi_{q^{(i)}}(-s^{(n - 1)})\}^l)
\end{aligned} π q = ( cm ( q ( 1 ) ( X )) , … , cm ( q ( n − 1 ) ( X )) , q ( n ) ( x 0 ) , { h 0 ( s ( 0 ) ) , π h 0 ( s ( 0 ) ) , h 0 ( − s ( 0 ) ) , π h 0 ( − s ( 0 ) ) , ⋯ , h n − 1 ( s ( 0 ) ) , π h n − 1 ( s ( 0 ) ) , h n − 1 ( − s ( 0 ) ) , π h n − 1 ( − s ( 0 ) ) , q ( 1 ) ( s ( 1 ) ) , π q ( 1 ) ( s ( 1 ) ) , q ( 1 ) ( − s ( 1 ) ) , π q ( 1 ) ( − s ( 1 ) ) , … , q ( n − 1 ) ( s ( n − 1 ) ) , π q ( n − 1 ) ( s ( n − 1 ) ) , q ( n − 1 ) ( − s ( n − 1 ) ) , π q ( i ) ( − s ( n − 1 ) ) } l ) Verification ¶ Verifier 验证折叠过程是否正确，对于 i = 1 , … , n − 1 i = 1, \ldots, n - 1 i = 1 , … , n − 1 h i ( β 2 ) = ? h i − 1 ( β ) + h i − 1 ( − β ) 2 + u i − 1 ⋅ h i − 1 ( β ) − h i − 1 ( − β ) 2 β h_{i}(\beta^{2}) \stackrel{?}{=} \frac{h_{i - 1}(\beta) + h_{i - 1}(-\beta)}{2} + u_{i - 1} \cdot \frac{h_{i - 1}(\beta) - h_{i - 1}(-\beta)}{2\beta} h i ( β 2 ) = ? 2 h i − 1 ( β ) + h i − 1 ( − β ) + u i − 1 ⋅ 2 β h i − 1 ( β ) − h i − 1 ( − β ) Verifier 验证最后是否折叠为常数 v v v h n − 1 ( β ) + h n − 1 ( − β ) 2 + u n − 1 ⋅ h n − 1 ( β ) − h n − 1 ( − β ) 2 β = ? v \frac{h_{n - 1}(\beta) + h_{n - 1}(-\beta)}{2} + u_{n - 1} \cdot \frac{h_{n - 1}(\beta) - h_{n - 1}(-\beta)}{2\beta} \stackrel{?}{=} v 2 h n − 1 ( β ) + h n − 1 ( − β ) + u n − 1 ⋅ 2 β h n − 1 ( β ) − h n − 1 ( − β ) = ? v 验证 q ( X ) q(X) q ( X ) F R I . L D T . v e r i f y ( π q , 2 n ) = ? 1 \mathsf{FRI.LDT.verify}(\pi_{q}, 2^n) \stackrel{?}{=} 1 FRI.LDT.verify ( π q , 2 n ) = ? 1 具体验证过程为，重复 l l l
验证 { h i ( s ( 0 ) ) } i = 0 n − 1 \{h_i(s^{(0)})\}_{i = 0}^{n-1} { h i ( s ( 0 ) ) } i = 0 n − 1 { h i ( − s ( 0 ) ) } i = 0 n − 1 \{h_i(-s^{(0)})\}_{i = 0}^{n-1} { h i ( − s ( 0 ) ) } i = 0 n − 1 i = 0 , … , n − 1 i = 0, \ldots, n - 1 i = 0 , … , n − 1 M T . v e r i f y ( c m ( h i ( X ) ) , h i ( s ( 0 ) ) , π h i ( s ( 0 ) ) ) = ? 1 \mathsf{MT.verify}(\mathsf{cm}(h_i(X)), h_i(s^{(0)}), \pi_{h_i}(s^{(0)})) \stackrel{?}{=} 1 MT.verify ( cm ( h i ( X )) , h i ( s ( 0 ) ) , π h i ( s ( 0 ) )) = ? 1 M T . v e r i f y ( c m ( h i ( X ) ) , h i ( − s ( 0 ) ) , π h i ( − s ( 0 ) ) ) = ? 1 \mathsf{MT.verify}(\mathsf{cm}(h_i(X)), h_i(-s^{(0)}), \pi_{h_i}(-s^{(0)})) \stackrel{?}{=} 1 MT.verify ( cm ( h i ( X )) , h i ( − s ( 0 ) ) , π h i ( − s ( 0 ) )) = ? 1 Verifier 根据 { h i ( s ( 0 ) ) } i = 0 n − 1 \{h_i(s^{(0)})\}_{i = 0}^{n-1} { h i ( s ( 0 ) ) } i = 0 n − 1 { h i ( − s ( 0 ) ) } i = 0 n − 1 \{h_i(-s^{(0)})\}_{i = 0}^{n-1} { h i ( − s ( 0 ) ) } i = 0 n − 1 h ∗ ( s ( 0 ) ) h^*(s^{(0)}) h ∗ ( s ( 0 ) ) h ∗ ( − s ( 0 ) ) h^*(-s^{(0)}) h ∗ ( − s ( 0 ) ) { h i ( β ) } i = 0 n − 1 , { h i ( − β ) } i = 0 n − 1 , { h i ( β 2 ) } i = 0 n − 1 \{h_i(\beta)\}_{i = 0}^{n-1}, \{h_i(-\beta)\}_{i = 0}^{n-1}, \{h_i(\beta^2)\}_{i = 0}^{n-1} { h i ( β ) } i = 0 n − 1 , { h i ( − β ) } i = 0 n − 1 , { h i ( β 2 ) } i = 0 n − 1 h ∗ ( β ) , h ∗ ( − β ) , h ∗ ( β 2 ) h^*(\beta), h^*(-\beta), h^*(\beta^2) h ∗ ( β ) , h ∗ ( − β ) , h ∗ ( β 2 ) x ∈ { s ( 0 ) , − s ( 0 ) , β , − β , β 2 } x \in \{s^{(0)}, -s^{(0)}, \beta, -\beta, \beta^2\} x ∈ { s ( 0 ) , − s ( 0 ) , β , − β , β 2 } h ∗ ( x ) h^*(x) h ∗ ( x ) 方法一：对于 i = 1 , … , n − 1 i = 1, \ldots, n - 1 i = 1 , … , n − 1
h i ′ ( x ) = h i ( x ) + r ⋅ ( x ) 2 n − 2 n − i ⋅ h i ( x ) h'_i(x)=h_i(x)+r\cdot (x)^{2^{n} - 2^{n-i}} \cdot h_i(x) h i ′ ( x ) = h i ( x ) + r ⋅ ( x ) 2 n − 2 n − i ⋅ h i ( x ) 接着计算
h ∗ ( x ) = h 0 ( x ) + r ⋅ h 1 ′ ( x ) + r 3 ⋅ h 2 ′ ( x ) + r 5 ⋅ h 3 ′ ( x ) + … + r 2 n − 3 ⋅ h n − 1 ′ ( x ) \begin{align*}
h^*(x) & = h_0(x) + r \cdot h_1'(x) + r^{3} \cdot h_2'(x) + r^{5} \cdot h_3'(x)+ \ldots + r^{2n-3} \cdot h_{n-1}'(x)
\end{align*} h ∗ ( x ) = h 0 ( x ) + r ⋅ h 1 ′ ( x ) + r 3 ⋅ h 2 ′ ( x ) + r 5 ⋅ h 3 ′ ( x ) + … + r 2 n − 3 ⋅ h n − 1 ′ ( x ) 方法二：若采用 STIR 论文 [ACFY24] 中的 degree correction 方法，对于 i = 1 , … , n − 1 i = 1, \ldots, n - 1 i = 1 , … , n − 1
h i ′ ( x ) = ∑ j = 0 2 n − 2 n − i r j ⋅ ( x ) j ⋅ h i ( x ) = { h i ( x ) ⋅ 1 − ( r ⋅ x ) 2 n − 2 n − i + 1 1 − r ⋅ x if r ⋅ x ≠ 0 h i ( x ) ⋅ ( 2 n − 2 n − i + 1 ) if r ⋅ x = 0 h'_i(x)=\sum_{j = 0}^{2^{n}- 2^{n - i}} r^{j} \cdot (x)^{j} \cdot h_i(x) = \begin{cases}
h_i(x) \cdot \frac{1 - (r \cdot x)^{2^n - 2^{n-i} + 1}}{1 - r \cdot x} & \text{if } r \cdot x \neq 0\\
h_i(x) \cdot (2^n - 2^{n-i} + 1) & \text{if } r \cdot x = 0
\end{cases} h i ′ ( x ) = j = 0 ∑ 2 n − 2 n − i r j ⋅ ( x ) j ⋅ h i ( x ) = { h i ( x ) ⋅ 1 − r ⋅ x 1 − ( r ⋅ x ) 2 n − 2 n − i + 1 h i ( x ) ⋅ ( 2 n − 2 n − i + 1 ) if r ⋅ x = 0 if r ⋅ x = 0 接着计算得到
h ∗ ( x ) = h 0 ( x ) + r ⋅ h 1 ′ ( x ) + r 2 + 2 n − 2 n − 1 ⋅ h 2 ′ ( x ) + r 2 + ∑ i = 1 2 ( 2 n − 2 i ) ⋅ h 3 ′ ( x ) + … + r n − 1 + ∑ i = 1 n − 2 ( 2 n − 2 i ) ⋅ h n − 1 ′ ( x ) \begin{align*}
h^*(x) & = h_0(x) + r \cdot h_1'(x) + r^{2 + 2^n - 2^{n -1}} \cdot h_2'(x) + r^{2 + \sum_{i=1}^{2}(2^n-2^i)} \cdot h_3'(x) \\
& \quad + \ldots + r^{n - 1+\sum_{i=1}^{n-2}(2^n-2^i)} \cdot h_{n-1}'(x)
\end{align*} h ∗ ( x ) = h 0 ( x ) + r ⋅ h 1 ′ ( x ) + r 2 + 2 n − 2 n − 1 ⋅ h 2 ′ ( x ) + r 2 + ∑ i = 1 2 ( 2 n − 2 i ) ⋅ h 3 ′ ( x ) + … + r n − 1 + ∑ i = 1 n − 2 ( 2 n − 2 i ) ⋅ h n − 1 ′ ( x ) Verifier 计算
q ′ ( s ( 0 ) ) = h ∗ ( s ( 0 ) ) − h ∗ ( β ) s ( 0 ) − β + h ∗ ( s ( 0 ) ) − h ∗ ( − β ) s ( 0 ) + β + h ∗ ( s ( 0 ) ) − h ∗ ( β 2 ) s ( 0 ) − β 2 q'(s^{(0)}) = \frac{h^*(s^{(0)})-h^*(\beta)}{s^{(0)}-\beta} + \frac{h^*(s^{(0)})-h^*(-\beta)}{s^{(0)}+\beta} + \frac{h^*(s^{(0)})-h^*(\beta^2)}{s^{(0)}-\beta^2} q ′ ( s ( 0 ) ) = s ( 0 ) − β h ∗ ( s ( 0 ) ) − h ∗ ( β ) + s ( 0 ) + β h ∗ ( s ( 0 ) ) − h ∗ ( − β ) + s ( 0 ) − β 2 h ∗ ( s ( 0 ) ) − h ∗ ( β 2 ) q ′ ( − s ( 0 ) ) = h ∗ ( − s ( 0 ) ) − h ∗ ( β ) − s ( 0 ) − β + h ∗ ( − s ( 0 ) ) − h ∗ ( − β ) − s ( 0 ) + β + h ∗ ( − s ( 0 ) ) − h ∗ ( β 2 ) − s ( 0 ) − β 2 q'(-s^{(0)}) = \frac{h^*(-s^{(0)})-h^*(\beta)}{-s^{(0)}-\beta} + \frac{h^*(-s^{(0)})-h^*(-\beta)}{-s^{(0)}+\beta} + \frac{h^*(-s^{(0)})-h^*(\beta^2)}{-s^{(0)}-\beta^2} q ′ ( − s ( 0 ) ) = − s ( 0 ) − β h ∗ ( − s ( 0 ) ) − h ∗ ( β ) + − s ( 0 ) + β h ∗ ( − s ( 0 ) ) − h ∗ ( − β ) + − s ( 0 ) − β 2 h ∗ ( − s ( 0 ) ) − h ∗ ( β 2 ) q ( 0 ) ( s ( 0 ) ) = ( 1 + λ ⋅ s ( 0 ) ) q ′ ( s ( 0 ) ) q^{(0)}(s^{(0)}) = (1 + \lambda \cdot s^{(0)}) q'(s^{(0)}) q ( 0 ) ( s ( 0 ) ) = ( 1 + λ ⋅ s ( 0 ) ) q ′ ( s ( 0 ) ) q ( 0 ) ( − s ( 0 ) ) = ( 1 − λ ⋅ s ( 0 ) ) q ′ ( − s ( 0 ) ) q^{(0)}(-s^{(0)}) = (1 - \lambda \cdot s^{(0)}) q'(-s^{(0)}) q ( 0 ) ( − s ( 0 ) ) = ( 1 − λ ⋅ s ( 0 ) ) q ′ ( − s ( 0 ) ) 验证 q ( 1 ) ( s ( 1 ) ) , q ( 1 ) ( − s ( 1 ) ) q^{(1)}(s^{(1)}), q^{(1)}(-s^{(1)}) q ( 1 ) ( s ( 1 ) ) , q ( 1 ) ( − s ( 1 ) ) M T . v e r i f y ( c m ( q ( 1 ) ( X ) ) , q ( 1 ) ( s ( 1 ) ) , π q ( 1 ) ( s ( 1 ) ) ) = ? 1 \mathsf{MT.verify}(\mathsf{cm}(q^{(1)}(X)), q^{(1)}(s^{(1)}), \pi_{q^{(1)}}(s^{(1)})) \stackrel{?}{=} 1 MT.verify ( cm ( q ( 1 ) ( X )) , q ( 1 ) ( s ( 1 ) ) , π q ( 1 ) ( s ( 1 ) )) = ? 1 M T . v e r i f y ( c m ( q ( 1 ) ( X ) ) , q ( 1 ) ( − s ( 1 ) ) , π q ( 1 ) ( − s ( 1 ) ) ) = ? 1 \mathsf{MT.verify}(\mathsf{cm}(q^{(1)}(X)), q^{(1)}(-s^{(1)}), \pi_{q^{(1)}}(-s^{(1)})) \stackrel{?}{=} 1 MT.verify ( cm ( q ( 1 ) ( X )) , q ( 1 ) ( − s ( 1 ) ) , π q ( 1 ) ( − s ( 1 ) )) = ? 1 q ( 1 ) ( s ( 1 ) ) = ? q ( 0 ) ( s ( 0 ) ) + q ( 0 ) ( − s ( 0 ) ) 2 + α ( 1 ) ⋅ q ( 0 ) ( s ( 0 ) ) − q ( 0 ) ( − s ( 0 ) ) 2 ⋅ s ( 0 ) q^{(1)}(s^{(1)}) \stackrel{?}{=} \frac{q^{(0)}(s^{(0)}) + q^{(0)}(- s^{(0)})}{2} + \alpha^{(1)} \cdot \frac{q^{(0)}(s^{(0)}) - q^{(0)}(- s^{(0)})}{2 \cdot s^{(0)}} q ( 1 ) ( s ( 1 ) ) = ? 2 q ( 0 ) ( s ( 0 ) ) + q ( 0 ) ( − s ( 0 ) ) + α ( 1 ) ⋅ 2 ⋅ s ( 0 ) q ( 0 ) ( s ( 0 ) ) − q ( 0 ) ( − s ( 0 ) ) 对于 i = 2 , … , n − 1 i = 2, \ldots, n - 1 i = 2 , … , n − 1
验证 q ( i ) ( s ( i ) ) , q ( i ) ( − s ( i ) ) q^{(i)}(s^{(i)}), q^{(i)}(-s^{(i)}) q ( i ) ( s ( i ) ) , q ( i ) ( − s ( i ) ) M T . v e r i f y ( c m ( q ( i ) ( X ) ) , q ( i ) ( s ( i ) ) , π q ( i ) ( s ( i ) ) ) = ? 1 \mathsf{MT.verify}(\mathsf{cm}(q^{(i)}(X)), q^{(i)}(s^{(i)}), \pi_{q^{(i)}}(s^{(i)})) \stackrel{?}{=} 1 MT.verify ( cm ( q ( i ) ( X )) , q ( i ) ( s ( i ) ) , π q ( i ) ( s ( i ) )) = ? 1 M T . v e r i f y ( c m ( q ( i ) ( X ) ) , q ( i ) ( − s ( i ) ) , π q ( i ) ( − s ( i ) ) ) = ? 1 \mathsf{MT.verify}(\mathsf{cm}(q^{(i)}(X)), q^{(i)}(-s^{(i)}), \pi_{q^{(i)}}(-s^{(i)})) \stackrel{?}{=} 1 MT.verify ( cm ( q ( i ) ( X )) , q ( i ) ( − s ( i ) ) , π q ( i ) ( − s ( i ) )) = ? 1 q ( i ) ( s ( i ) ) = ? q ( i − 1 ) ( s ( i − 1 ) ) + q ( i − 1 ) ( − s ( i − 1 ) ) 2 + α ( i ) ⋅ q ( i − 1 ) ( s ( i − 1 ) ) − q ( i − 1 ) ( − s ( i − 1 ) ) 2 ⋅ s ( i − 1 ) q^{(i)}(s^{(i)}) \stackrel{?}{=} \frac{q^{(i-1)}(s^{(i - 1)}) + q^{(i - 1)}(- s^{(i - 1)})}{2} + \alpha^{(i)} \cdot \frac{q^{(i - 1)}(s^{(i - 1)}) - q^{(i - 1)}(- s^{(i - 1)})}{2 \cdot s^{(i - 1)}} q ( i ) ( s ( i ) ) = ? 2 q ( i − 1 ) ( s ( i − 1 ) ) + q ( i − 1 ) ( − s ( i − 1 ) ) + α ( i ) ⋅ 2 ⋅ s ( i − 1 ) q ( i − 1 ) ( s ( i − 1 ) ) − q ( i − 1 ) ( − s ( i − 1 ) ) 验证最后是否折叠到常数多项式
q ( n ) ( x 0 ) = ? q ( n − 1 ) ( s ( n − 1 ) ) + q ( n − 1 ) ( − s ( n − 1 ) ) 2 + α ( n ) ⋅ q ( n − 1 ) ( s ( n − 1 ) ) − q ( n − 1 ) ( − s ( n − 1 ) ) 2 ⋅ s ( n − 1 ) q^{(n)}(x_0) \stackrel{?}{=} \frac{q^{(n-1)}(s^{(n - 1)}) + q^{(n - 1)}(- s^{(n - 1)})}{2} + \alpha^{(n)} \cdot \frac{q^{(n - 1)}(s^{(n - 1)}) - q^{(n - 1)}(- s^{(n - 1)})}{2 \cdot s^{(n - 1)}} q ( n ) ( x 0 ) = ? 2 q ( n − 1 ) ( s ( n − 1 ) ) + q ( n − 1 ) ( − s ( n − 1 ) ) + α ( n ) ⋅ 2 ⋅ s ( n − 1 ) q ( n − 1 ) ( s ( n − 1 ) ) − q ( n − 1 ) ( − s ( n − 1 ) ) Reference ¶ [BCH+22] Bootle, Jonathan, Alessandro Chiesa, Yuncong Hu, et al. “Gemini: Elastic SNARKs for Diverse Environments.” Cryptology ePrint Archivehttps:// [BBBZ23] Chen, Binyi, Benedikt Bünz, Dan Boneh, and Zhenfei Zhang. “Hyperplonk: Plonk with linear-time prover and high-degree custom gates.” In Annual International Conference on the Theory and Applications of Cryptographic Techniques , pp. 499-530. Cham: Springer Nature Switzerland, 2023. [H22] Haböck, Ulrich. “A summary on the FRI low degree test.” Cryptology ePrint Archive (2022). [ACFY24] Arnon, Gal, 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.