Yu Guo [email protected]
最后更新时间：2025-06-05
Ligerito [NA25] 是在 Ligero [AHIV17] 基础上，模仿 FRI 协议进行递归证明的 MLE 多项式承诺方案。在理解过 Ligerito 协议之后，我发现它的递归协议调用的思路与 FRI 协议类似，在协议中加入 Paritial Sumcheck 协议的思路应该是源于 Basefold。在递归调用过程中的 Sumcheck 协议可以和上一次迭代中的 Paritial Sumcheck 协议可以进行合并，这一思路与 Whir 协议中对 Shift Queries 的处理几乎一摸一样。在论文第 13 页中的 Discussion 一节中，作者这么写道：
Remco Bloemen and Giacomo Fenzi have commented that this protocol is structurally similar to the WHIR protocol of [ACFY24], though we note that Ligerito uses general linear codes, the logarithmic randomness of [DP24], and as far as we can tell, results in concretely different (and smaller) numbers in the unique decoding regime. A natural open question is whether there is a simple generalization of both protocols that can recast them in a common framework.
本文带着大家概览下 Ligerito 协议的核心思想，并对比下和 Whir 协议的在表述上有哪些不同点。最后，笔者感觉两者没有实质上的差别，尽管两个协议设计的路径不同，但最终的协议在核心流程上几乎一样。Whir 此外增加了 Out-of-domain Query 的步骤，并且有在迭代过程中倾向使用更大的 Domain 去计算中间多项式的 RS Code，目的是提高码率，降低 Query 次数。
思路:
回顾 Ligero 协议 Sumcheck 的关键作用 递归调用 1. Ligero ¶ 我们通过一个简单的例子来过一遍 Ligero 协议的流程，方便读者快速理解这个协议。这里假设一个仅有四个变量的 MLE 多项式，其定义如下：
f ( x 0 , x 1 , x 2 , x 3 ) = ∑ i = 0 2 4 − 1 a i ⋅ e q ( b i t s ( i ) , ( x 0 , x 1 , x 2 , x 3 ) ) f(x_0, x_1, x_2, x_3) = \sum_{i=0}^{2^4-1} a_i \cdot eq(\mathsf{bits}(i), (x_0, x_1, x_2, x_3)) f ( x 0 , x 1 , x 2 , x 3 ) = i = 0 ∑ 2 4 − 1 a i ⋅ e q ( bits ( i ) , ( x 0 , x 1 , x 2 , x 3 )) 其中向量 a ⃗ = ( a 0 , a 1 , ⋯ , a 15 ) \vec{a}=(a_0, a_1, \cdots, a_{15}) a = ( a 0 , a 1 , ⋯ , a 15 ) f f f { 0 , 1 } 4 \{0, 1\}^4 { 0 , 1 } 4
计算承诺 ¶ 我们可以把这个向量 a ⃗ \vec{a} a 4 × 4 4\times 4 4 × 4 A A A
A = [ a 0 a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a 9 a 10 a 11 a 12 a 13 a 14 a 15 ] A=
\begin{bmatrix}
a_0 & a_1 & a_2 & a_3 \\
a_4 & a_5 & a_6 & a_7 \\
a_8 & a_9 & a_{10} & a_{11} \\
a_{12} & a_{13} & a_{14} & a_{15}
\end{bmatrix} A = ⎣ ⎡ a 0 a 4 a 8 a 12 a 1 a 5 a 9 a 13 a 2 a 6 a 10 a 14 a 3 a 7 a 11 a 15 ⎦ ⎤ 我们用一个线性编码，C [ F , 4 , 8 ] C[\mathbb{F}, 4, 8] C [ F , 4 , 8 ] G ∈ F 4 × 8 G\in\mathbb{F}^{4\times 8} G ∈ F 4 × 8 1 / 2 1/2 1/2
e n c ( a 0 , a 1 , a 2 , a 3 ) = [ a 0 a 1 a 2 a 3 ] G \mathsf{enc}(a_0, a_1, a_2, a_3) =
\begin{bmatrix}
a_0 & a_1 & a_2 & a_3
\end{bmatrix}
G enc ( a 0 , a 1 , a 2 , a 3 ) = [ a 0 a 1 a 2 a 3 ] G 我们可以选择 RS Code 当然也可以选择任何定义在有限域 F q \mathbb{F}_q F q e n c ( a 0 , a 1 , a 2 , a 3 ) \mathsf{enc}(a_0, a_1, a_2, a_3) enc ( a 0 , a 1 , a 2 , a 3 ) ( e 0 , e 1 , e 2 , e 3 , e 4 , e 5 , e 6 , e 7 ) (e_0, e_1, e_2, e_3, e_4, e_5, e_6, e_7) ( e 0 , e 1 , e 2 , e 3 , e 4 , e 5 , e 6 , e 7 ) G G G B B B 4 × 8 4\times 8 4 × 8
B = A G = [ e 0 e 1 e 2 e 3 e 4 e 5 e 6 e 7 e 8 e 9 e 10 e 11 e 12 e 13 e 14 e 15 e 16 e 17 e 18 e 19 e 20 e 21 e 22 e 23 e 24 e 25 e 26 e 27 e 28 e 29 e 30 e 31 ] B= AG =
\begin{bmatrix}
e_0 & e_1 & e_2 & e_3 & e_4 & e_5 & e_6 & e_7 \\
e_8 & e_9 & e_{10} & e_{11} & e_{12} & e_{13} & e_{14} & e_{15} \\
e_{16} & e_{17} & e_{18} & e_{19} & e_{20} & e_{21} & e_{22} & e_{23} \\
e_{24} & e_{25} & e_{26} & e_{27} & e_{28} & e_{29} & e_{30} & e_{31}
\end{bmatrix} B = A G = ⎣ ⎡ e 0 e 8 e 16 e 24 e 1 e 9 e 17 e 25 e 2 e 10 e 18 e 26 e 3 e 11 e 19 e 27 e 4 e 12 e 20 e 28 e 5 e 13 e 21 e 29 e 6 e 14 e 22 e 30 e 7 e 15 e 23 e 31 ⎦ ⎤ 与任何的基于 Hash 的 PCS 协议一样，我们用 Merkle Tree 对 B B B B B B B B B
t 0 = M e r k l e R o o t ( e 0 , e 8 , e 16 , e 24 ) t 1 = M e r k l e R o o t ( e 1 , e 9 , e 17 , e 25 ) ⋮ t 7 = M e r k l e R o o t ( e 7 , e 15 , e 23 , e 31 ) \begin{aligned}
\mathsf{t}_0 &= \mathsf{MerkleRoot}(e_0, e_8, e_{16}, e_{24}) \\
\mathsf{t}_1 &= \mathsf{MerkleRoot}(e_1, e_9, e_{17}, e_{25}) \\
\vdots \\
\mathsf{t}_7 &= \mathsf{MerkleRoot}(e_7, e_{15}, e_{23}, e_{31}) \\
\end{aligned} t 0 t 1 ⋮ t 7 = MerkleRoot ( e 0 , e 8 , e 16 , e 24 ) = MerkleRoot ( e 1 , e 9 , e 17 , e 25 ) = MerkleRoot ( e 7 , e 15 , e 23 , e 31 ) 然后我们再把这 8 个根作为一颗新的 Merkle Tree 的叶子节点，计算它们的根，
t = M e r k l e R o o t ( t 0 , t 1 , ⋯ , t 7 ) \mathsf{t} = \mathsf{MerkleRoot}(\mathsf{t}_0, \mathsf{t}_1, \cdots, \mathsf{t}_7) t = MerkleRoot ( t 0 , t 1 , ⋯ , t 7 ) 最后，我们得到的 t \mathsf{t} t B B B B B B t \mathsf{t} t
证明随机点求值的正确性 ¶ Prover 可以按照上面的方式提前 Commit 一个 MLE 多项式，并且发送其承诺 t \mathsf{t} t r 0 , r 1 , r 2 , r 3 r_0, r_1, r_2, r_3 r 0 , r 1 , r 2 , r 3 v v v π e v a l \pi_{eval} π e v a l
π e v a l : v = f ( r 0 , r 1 , r 2 , r 3 ) \pi_{eval}: v=f(r_0, r_1, r_2, r_3) π e v a l : v = f ( r 0 , r 1 , r 2 , r 3 ) 我们快速过一下 Ligero 的思路。
第一步 ：Prover 计算 B B B t \mathsf{t} t
第二步 ：Verifier 随机选取一个随机点 ( r 0 , r 1 , r 2 , r 3 ) ∈ F q 4 (r_0, r_1, r_2, r_3)\in\mathbb{F}_q^{4} ( r 0 , r 1 , r 2 , r 3 ) ∈ F q 4
第三步 ：Prover 利用 r 3 , r 2 r_3, r_2 r 3 , r 2 A A A a ⃗ ′ \vec{a}' a ′
a ⃗ ′ = [ ( 1 − r 2 ) ( 1 − r 3 ) r 2 ( 1 − r 3 ) r 3 ( 1 − r 2 ) r 2 r 3 ] [ a 0 a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a 9 a 10 a 11 a 12 a 13 a 14 a 15 ] \vec{a}' =
\begin{bmatrix}
(1-r_2)(1-r_3) & r_2(1-r_3) & r_3(1-r_2) & r_2r_3 \\
\end{bmatrix}
\begin{bmatrix}
a_0 & a_1 & a_2 & a_3 \\
a_4 & a_5 & a_6 & a_7 \\
a_8 & a_9 & a_{10} & a_{11} \\
a_{12} & a_{13} & a_{14} & a_{15}
\end{bmatrix} a ′ = [ ( 1 − r 2 ) ( 1 − r 3 ) r 2 ( 1 − r 3 ) r 3 ( 1 − r 2 ) r 2 r 3 ] ⎣ ⎡ a 0 a 4 a 8 a 12 a 1 a 5 a 9 a 13 a 2 a 6 a 10 a 14 a 3 a 7 a 11 a 15 ⎦ ⎤ 这里需要注意的是，因为矩阵总共有 4 行，而 Prover 仅需要两个随机数就可以折叠 4 行，这是因为我们可以利用 k k k 2 k 2^k 2 k
r ˉ = ( 1 − r 2 , r 2 ) ⊗ ( 1 − r 3 , r 3 ) \bar{r} = (1-r_2, r_2) \otimes (1-r_3, r_3) r ˉ = ( 1 − r 2 , r 2 ) ⊗ ( 1 − r 3 , r 3 ) 我们借助 Ligerito 论文的符号 r ˉ \bar{r} r ˉ log n \log{n} log n n n n ⊗ \otimes ⊗ r ˉ \bar{r} r ˉ
r ˉ = [ ( 1 − r 2 ) ( 1 − r 3 ) ( 1 − r 2 ) r 3 r 2 ( 1 − r 3 ) r 2 r 3 ] \bar{r} =
\begin{bmatrix}
(1-r_2)(1-r_3) &
(1-r_2)r_3 &
r_2(1-r_3) &
r_2r_3
\end{bmatrix} r ˉ = [ ( 1 − r 2 ) ( 1 − r 3 ) ( 1 − r 2 ) r 3 r 2 ( 1 − r 3 ) r 2 r 3 ] 上面写的数学符号如果并不容易理解，我们下面采用更形象的方式来解释这个 a ⃗ ′ \vec{a}' a ′
我们先引入一个新的符号 f o l d ( r , c ⃗ ) \mathsf{fold}(r, \vec{c}) fold ( r , c ) c ⃗ \vec{c} c r r r
f o l d ( r , ( c 0 , c 1 , c 2 , … , c 7 ) T ) = [ ( 1 − r ) ⋅ c 0 + r ⋅ c 4 ( 1 − r ) ⋅ c 1 + r ⋅ c 5 ( 1 − r ) ⋅ c 2 + r ⋅ c 6 ( 1 − r ) ⋅ c 3 + r ⋅ c 7 ] = [ c 0 ′ c 1 ′ c 2 ′ c 3 ′ ] = c ⃗ ′ \mathsf{fold}(r, (c_0,c_1,c_2,\ldots, c_7)^T) =
\begin{bmatrix}
(1-r)\cdot c_0 + r\cdot c_4 \\
(1-r)\cdot c_1 + r\cdot c_5 \\
(1-r)\cdot c_2 + r\cdot c_6 \\
(1-r)\cdot c_3 + r\cdot c_7
\end{bmatrix}
=\begin{bmatrix}
c_0' \\
c_1' \\
c_2' \\
c_3'
\end{bmatrix}
=\vec{c}' fold ( r , ( c 0 , c 1 , c 2 , … , c 7 ) T ) = ⎣ ⎡ ( 1 − r ) ⋅ c 0 + r ⋅ c 4 ( 1 − r ) ⋅ c 1 + r ⋅ c 5 ( 1 − r ) ⋅ c 2 + r ⋅ c 6 ( 1 − r ) ⋅ c 3 + r ⋅ c 7 ⎦ ⎤ = ⎣ ⎡ c 0 ′ c 1 ′ c 2 ′ c 3 ′ ⎦ ⎤ = c ′ 这个 fold 函数可以理解成把向量对半拆分成两部分，然后将前一半乘上 ( 1 − r ) (1-r) ( 1 − r ) r r r
如果我们继续对上面折叠后的向量，记为 c ⃗ ′ = ( c 0 ′ , c 1 ′ , c 2 ′ , c 3 ′ ) T \vec{c}'=(c_0', c_1', c_2', c_3')^T c ′ = ( c 0 ′ , c 1 ′ , c 2 ′ , c 3 ′ ) T r ′ r' r ′
f o l d ( r ′ , c ⃗ ′ ) = [ ( 1 − r ′ ) ⋅ c 0 ′ + r ′ ⋅ c 2 ′ ( 1 − r ′ ) ⋅ c 1 ′ + r ′ ⋅ c 3 ′ ] = [ ( 1 − r ′ ) ( 1 − r ) ⋅ c 0 + ( 1 − r ′ ) r ⋅ c 4 + r ′ ( 1 − r ) ⋅ c 2 + r ′ r ⋅ c 6 ( 1 − r ′ ) ( 1 − r ) ⋅ c 1 + ( 1 − r ′ ) r ⋅ c 5 + r ′ ( 1 − r ) ⋅ c 3 + r ′ r ⋅ c 7 ] = c ⃗ ′ ′ \mathsf{fold}(r', \vec{c}') =
\begin{bmatrix}
(1-r')\cdot c_0' + r'\cdot c_2' \\
(1-r')\cdot c_1' + r'\cdot c_3' \\
\end{bmatrix}
=
\begin{bmatrix}
(1-r')(1-r)\cdot c_0 + (1-r')r\cdot c_4 + r'(1-r)\cdot c_2 + r'r\cdot c_6 \\
(1-r')(1-r)\cdot c_1 + (1-r')r\cdot c_5 + r'(1-r)\cdot c_3 + r'r\cdot c_7 \\
\end{bmatrix}
= \vec{c}'' fold ( r ′ , c ′ ) = [ ( 1 − r ′ ) ⋅ c 0 ′ + r ′ ⋅ c 2 ′ ( 1 − r ′ ) ⋅ c 1 ′ + r ′ ⋅ c 3 ′ ] = [ ( 1 − r ′ ) ( 1 − r ) ⋅ c 0 + ( 1 − r ′ ) r ⋅ c 4 + r ′ ( 1 − r ) ⋅ c 2 + r ′ r ⋅ c 6 ( 1 − r ′ ) ( 1 − r ) ⋅ c 1 + ( 1 − r ′ ) r ⋅ c 5 + r ′ ( 1 − r ) ⋅ c 3 + r ′ r ⋅ c 7 ] = c ′′ 我们如果允许f o l d \mathsf{fold} fold
f o l d ( r ′ , r , a ⃗ ) = f o l d ( r ′ , f o l d ( r , a ⃗ ) ) = a ⃗ ′ ′ \mathsf{fold}(r', r, \vec{a}) = \mathsf{fold}(r', \mathsf{fold}(r, \vec{a}))
= \vec{a}'' fold ( r ′ , r , a ) = fold ( r ′ , fold ( r , a )) = a ′′ 继续我们的例子，这时我们可以借助 f o l d \mathsf{fold} fold a ⃗ ′ \vec{a}' a ′
a ⃗ ′ = [ f o l d ( r 2 , r 3 , ( a 0 , a 4 , a 8 , a 12 ) ) f o l d ( r 2 , r 3 , ( a 1 , a 5 , a 9 , a 13 ) ) f o l d ( r 2 , r 3 , ( a 2 , a 6 , a 10 , a 14 ) ) f o l d ( r 2 , r 3 , ( a 3 , a 7 , a 11 , a 15 ) ) ] \vec{a}' =
\begin{bmatrix}
\mathsf{fold}(r_2, r_3, (a_0, a_4, a_8, a_{12})) \\
\mathsf{fold}(r_2, r_3, (a_1, a_5, a_9, a_{13})) \\
\mathsf{fold}(r_2, r_3, (a_2, a_6, a_{10}, a_{14})) \\
\mathsf{fold}(r_2, r_3, (a_3, a_7, a_{11}, a_{15}))
\end{bmatrix} a ′ = ⎣ ⎡ fold ( r 2 , r 3 , ( a 0 , a 4 , a 8 , a 12 )) fold ( r 2 , r 3 , ( a 1 , a 5 , a 9 , a 13 )) fold ( r 2 , r 3 , ( a 2 , a 6 , a 10 , a 14 )) fold ( r 2 , r 3 , ( a 3 , a 7 , a 11 , a 15 )) ⎦ ⎤ 第四步 ：Verifier 抽样 Q ⊂ { 0 , 1 , 2 , … , 7 } Q\subset\{0, 1, 2, \ldots, 7\} Q ⊂ { 0 , 1 , 2 , … , 7 }
Q = { q 0 , q 1 , … , q l − 1 } Q = \{q_0, q_1, \ldots, q_{l-1}\} Q = { q 0 , q 1 , … , q l − 1 } Verifier 随机抽样的目的是检查 Prover 是否诚实地按照 f o l d ( r 2 , r 3 , ⋅ ) \mathsf{fold}(r2,r_3,\cdot) fold ( r 2 , r 3 , ⋅ ) a ⃗ ′ \vec{a}' a ′ Proximity Gap 的神奇性质，折叠后的线性编码要么仍然是一个正确的编码，要么极大概率距离一个正确的编码很远。所谓编码距离是衡量两个码字之间不同元素的数量的度量，也被称为 Hamming Distance。这样 Verifier 可以只抽样少量的码字中的位置，来检查折叠过程是否正确即可。当然 Verifier 抽样越多越安全，但是抽样越多，证明通讯量（Proof Size）就越大。我们一般可以通过概率公式来保证安全性的前提下，采用最少的抽样次数。这里我们把抽样次数记为 l l l
第五步 ：Prover 回应 Verifier 的随机抽样，发送 Q = { q i } Q=\{q_i\} Q = { q i } q i q_i q i B B B b ⃗ q i \vec{b}_{q_i} b q i t q i \mathsf{t}_{q_i} t q i t q i \mathsf{t}_{q_i} t q i t \mathsf{t} t π q i \pi_{q_i} π q i
例如 q 0 = 2 q_0=2 q 0 = 2 ( e 2 , e 10 , e 18 , e 26 ) (e_2, e_{10}, e_{18}, e_{26}) ( e 2 , e 10 , e 18 , e 26 ) t 2 \mathsf{t}_{2} t 2 t 2 \mathsf{t}_{2} t 2 t \mathsf{t} t
验证步 ：Verifier 需要验证下面的等式是否成立：
所有的 t q i \mathsf{t}_{q_i} t q i t \mathsf{t} t
t q i = ? M e r k l e R o o t ( b ⃗ q i ) , ∀ q i ∈ Q \mathsf{t}_{q_i} \overset{?}{=} \mathsf{MerkleRoot}(\vec{b}_{q_i}), \quad \forall q_i\in Q t q i = ? MerkleRoot ( b q i ) , ∀ q i ∈ Q t q i t_{q_i} t q i t \mathsf{t} t
M e r k l e T r e e . v e r i f y ( t , t q i , π q i ) = ? 1 , ∀ q i ∈ Q \mathsf{MerkleTree.verify}(\mathsf{t}, \mathsf{t}_{q_i}, \pi_{q_i}) \overset{?}{=} 1, \quad \forall q_i\in Q MerkleTree.verify ( t , t q i , π q i ) = ? 1 , ∀ q i ∈ Q 计算 b ⃗ q i \vec{b}_{q_i} b q i a ⃗ ′ G \vec{a}'G a ′ G f o l d ( r 2 , r 3 , b ⃗ q i ) = ? a ⃗ ′ T G q i , ∀ q i ∈ Q \mathsf{fold}(r_2, r_3,\vec{b}_{q_i}) \overset{?}{=} \vec{a}'^TG_{q_i}, \quad \forall q_i\in Q fold ( r 2 , r 3 , b q i ) = ? a ′ T G q i , ∀ q i ∈ Q 这里 G q i G_{q_i} G q i G G G q i q_i q i
验证 a ⃗ ′ \vec{a}' a ′ a ⃗ ′ T ⋅ ( ( 1 − r 0 , r 0 ) ⊗ ( 1 − r 1 , r 1 ) ) = ? v \vec{a}'^T\cdot\big((1-r_0,r_0)\otimes(1-r_1,r_1)\big)\overset{?}{=}v a ′ T ⋅ ( ( 1 − r 0 , r 0 ) ⊗ ( 1 − r 1 , r 1 ) ) = ? v 至此，如果上面四个检查步骤都通过，Verifier 则接受证明：
π e v a l : f ( r 0 , r 1 , r 2 , r 3 ) = v \pi_{eval}:f(r_0, r_1, r_2, r_3) = v π e v a l : f ( r 0 , r 1 , r 2 , r 3 ) = v 2. Sumcheck 的关键作用 ¶ 上一节的协议有一个明显的问题，那就是 Verifier 必须在 Prover 承诺 f f f
这就我们需要引入 Sumcheck 协议。具体地说，我们在 Ligero 协议的基础之上，只需要引入一个部分运行 的 Sumcheck 子协议，就能完成一个 MLE 多项式的在任意点求值证明。这个思路实际上是来源于 Basefold [ZCF23]。这里我们假设读者已经熟悉 Sumcheck 协议，或者请读者参考我们之前写的文章。(TODO)
我们仍然采用之前的仅有四个未知数的 MLE 多项式 f f f f f f u ⃗ = ( u 0 , u 1 , u 2 , u 3 ) \vec{u}=(u_0, u_1, u_2, u_3) u = ( u 0 , u 1 , u 2 , u 3 ) ( a 0 , a 1 , a 2 , … , a 15 ) (a_0, a_1, a_2, \ldots, a_{15}) ( a 0 , a 1 , a 2 , … , a 15 )
f ( u 0 , u 1 , u 2 , u 3 ) = ∑ b ⃗ ∈ { 0 , 1 } 4 f ( b 0 , b 1 , b 2 , b 3 ) ⋅ e q ( ( b 0 , b 1 , b 2 , b 3 ) , ( u 0 , u 1 , u 2 , u 3 ) ) f(u_0, u_1, u_2, u_3) = \sum_{\vec{b}\in\{0,1\}^4} f(b_0,b_1,b_2,b_3) \cdot eq\big((b_0, b_1, b_2, b_3), (u_0, u_1, u_2, u_3)\big) f ( u 0 , u 1 , u 2 , u 3 ) = b ∈ { 0 , 1 } 4 ∑ f ( b 0 , b 1 , b 2 , b 3 ) ⋅ e q ( ( b 0 , b 1 , b 2 , b 3 ) , ( u 0 , u 1 , u 2 , u 3 ) ) 我们再次强调： u ⃗ = ( u 0 , u 1 , u 2 , u 3 ) \vec{u}=(u_0, u_1, u_2, u_3) u = ( u 0 , u 1 , u 2 , u 3 ) e q ( b ⃗ , u ⃗ ) eq(\vec{b}, \vec{u}) e q ( b , u )
e q ( b ⃗ , u ⃗ ) = ∏ i = 0 n − 1 ( ( 1 − b i ) ( 1 − u i ) + b i ⋅ u i ) eq(\vec{b}, \vec{u}) = \prod_{i=0}^{n-1} \big((1-b_i)(1-u_i) + b_i\cdot u_i\big) e q ( b , u ) = i = 0 ∏ n − 1 ( ( 1 − b i ) ( 1 − u i ) + b i ⋅ u i ) 其中 n n n n = 4 n=4 n = 4 b ⃗ ∈ { 0 , 1 } 4 \vec{b}\in\{0,1\}^4 b ∈ { 0 , 1 } 4 w i w_i w i e q ( b i t s ( i ) , u ⃗ ) eq(\mathsf{bits}(i), \vec{u}) e q ( bits ( i ) , u )
w i = e q ( b i t s ( i ) , ( u 0 , u 1 , u 2 , u 3 ) ) w_i = eq(\mathsf{bits}(i), (u_0, u_1, u_2, u_3)) w i = e q ( bits ( i ) , ( u 0 , u 1 , u 2 , u 3 )) 到此为止，我们可以看到下面的等式成立：
f ( u 0 , u 1 , u 2 , u 3 ) = ∑ i = 0 2 4 − 1 a i ⋅ w i f(u_0, u_1, u_2, u_3) = \sum_{i=0}^{2^4-1} a_i \cdot w_i f ( u 0 , u 1 , u 2 , u 3 ) = i = 0 ∑ 2 4 − 1 a i ⋅ w i 上面我们说过 a ⃗ = ( a 0 , a 1 , a 2 , … , a 15 ) \vec{a}=(a_0, a_1, a_2, \ldots, a_{15}) a = ( a 0 , a 1 , a 2 , … , a 15 ) f f f
a ⃗ = [ f ( 0 , 0 , 0 , 0 ) f ( 1 , 0 , 0 , 0 ) f ( 0 , 1 , 0 , 0 ) f ( 1 , 1 , 0 , 0 ) ⋮ f ( 1 , 1 , 1 , 1 ) ] \vec{a} = \begin{bmatrix}
f(0,0,0,0) \\
f(1,0,0,0) \\
f(0,1,0,0) \\
f(1,1,0,0) \\
\vdots \\
f(1,1,1,1)
\end{bmatrix} a = ⎣ ⎡ f ( 0 , 0 , 0 , 0 ) f ( 1 , 0 , 0 , 0 ) f ( 0 , 1 , 0 , 0 ) f ( 1 , 1 , 0 , 0 ) ⋮ f ( 1 , 1 , 1 , 1 ) ⎦ ⎤ 即
a i = f ( b i t s ) a_i=f(\mathsf{bits}) a i = f ( bits ) 鉴于 f ( u 0 , u 1 , u 2 , u 3 ) f(u_0, u_1, u_2, u_3) f ( u 0 , u 1 , u 2 , u 3 ) a ⃗ \vec{a} a w ⃗ \vec{w} w
f ( u 0 , u 1 , u 2 , u 3 ) = ∑ b ⃗ ∈ { 0 , 1 } 4 f ( b 0 , b 1 , b 2 , b 3 ) ⋅ w ~ ( b 0 , b 1 , b 2 , b 3 ) f(u_0, u_1, u_2, u_3) = \sum_{\vec{b}\in\{0,1\}^4} f(b_0, b_1, b_2, b_3) \cdot \tilde{w}(b_0, b_1, b_2, b_3) f ( u 0 , u 1 , u 2 , u 3 ) = b ∈ { 0 , 1 } 4 ∑ f ( b 0 , b 1 , b 2 , b 3 ) ⋅ w ~ ( b 0 , b 1 , b 2 , b 3 ) 其中 w ~ \tilde{w} w ~ w ⃗ \vec{w} w
f ( u 0 , u 1 , u 2 , r 3 ) = ∑ b ⃗ ∈ { 0 , 1 } 3 f ( b 0 , b 1 , b 2 , r 3 ) ⋅ w ~ ( b 0 , b 1 , b 2 , r 3 ) f(u_0, u_1, u_2, {\color{red}r_3}) = \sum_{\vec{b}\in\{0,1\}^3} f(b_0, b_1, b_2, {\color{red}r_3}) \cdot \tilde{w}(b_0, b_1, b_2, {\color{red}r_3}) f ( u 0 , u 1 , u 2 , r 3 ) = b ∈ { 0 , 1 } 3 ∑ f ( b 0 , b 1 , b 2 , r 3 ) ⋅ w ~ ( b 0 , b 1 , b 2 , r 3 ) 这里 r 3 r_3 r 3
f ( u 0 , u 1 , r 2 , r 3 ) = ∑ b ⃗ ∈ { 0 , 1 } 2 f ( b 0 , b 1 , r 2 , r 3 ) ⋅ w ~ ( b 0 , b 1 , r 2 , r 3 ) f(u_0, u_1, {\color{red}r_2}, r_3) = \sum_{\vec{b}\in\{0,1\}^2} f(b_0, b_1, {\color{red}r_2}, r_3) \cdot \tilde{w}(b_0, b_1, {\color{red}r_2}, r_3) f ( u 0 , u 1 , r 2 , r 3 ) = b ∈ { 0 , 1 } 2 ∑ f ( b 0 , b 1 , r 2 , r 3 ) ⋅ w ~ ( b 0 , b 1 , r 2 , r 3 ) 这时候，求和等式右边的 f ( X 0 , X 1 , r 2 , r 3 ) f(X_0, X_1, r_2, r_3) f ( X 0 , X 1 , r 2 , r 3 ) X 0 , X 1 X_0,X_1 X 0 , X 1 A A A r 2 , r 3 r_2, r_3 r 2 , r 3
[ f ( 0 , 0 , r 2 , r 3 ) f ( 0 , 1 , r 2 , r 3 ) f ( 1 , 0 , r 2 , r 3 ) f ( 1 , 1 , r 2 , r 3 ) ] = [ f o l d ( r 2 , r 3 , ( a 0 , a 4 , a 8 , a 12 ) ) f o l d ( r 2 , r 3 , ( a 1 , a 5 , a 9 , a 13 ) ) f o l d ( r 2 , r 3 , ( a 2 , a 6 , a 10 , a 14 ) ) f o l d ( r 2 , r 3 , ( a 3 , a 7 , a 11 , a 15 ) ) ] \begin{bmatrix}
f(0,0,r_2,r_3) \\
f(0,1,r_2,r_3) \\
f(1,0,r_2,r_3) \\
f(1,1,r_2,r_3)
\end{bmatrix}
=
\begin{bmatrix}
\mathsf{fold}(r_2, r_3, (a_0, a_4, a_8, a_{12})) \\
\mathsf{fold}(r_2, r_3, (a_1, a_5, a_9, a_{13})) \\
\mathsf{fold}(r_2, r_3, (a_2, a_6, a_{10}, a_{14})) \\
\mathsf{fold}(r_2, r_3, (a_3, a_7, a_{11}, a_{15}))
\end{bmatrix} ⎣ ⎡ f ( 0 , 0 , r 2 , r 3 ) f ( 0 , 1 , r 2 , r 3 ) f ( 1 , 0 , r 2 , r 3 ) f ( 1 , 1 , r 2 , r 3 ) ⎦ ⎤ = ⎣ ⎡ fold ( r 2 , r 3 , ( a 0 , a 4 , a 8 , a 12 )) fold ( r 2 , r 3 , ( a 1 , a 5 , a 9 , a 13 )) fold ( r 2 , r 3 , ( a 2 , a 6 , a 10 , a 14 )) fold ( r 2 , r 3 , ( a 3 , a 7 , a 11 , a 15 )) ⎦ ⎤ 我们可以用向量的第一个元素 f ( 0 , 0 , r 2 , r 3 ) f(0,0,r_2,r_3) f ( 0 , 0 , r 2 , r 3 )
f ( 0 , 0 , r 2 , r 3 ) = ∑ i = 0 3 a i ⋅ e q ( b i t s ( i ) , ( 0 , 0 , r 2 , r 3 ) ) = f ( 0 , 0 , 0 , 0 ) ⋅ e q ( b i t s ( 0 ) , ( 0 , 0 , r 2 , r 3 ) ) + f ( 0 , 0 , 1 , 0 ) ⋅ e q ( b i t s ( 4 ) , ( 0 , 0 , r 2 , r 3 ) ) + f ( 0 , 0 , 0 , 1 ) ⋅ e q ( b i t s ( 8 ) , ( 0 , 0 , r 2 , r 3 ) ) + f ( 0 , 0 , 1 , 1 ) ⋅ e q ( b i t s ( 12 ) , ( 0 , 0 , r 2 , r 3 ) ) = a 0 ⋅ e q ( b i t s ( 0 ) , ( r 2 , r 3 ) ) + a 4 ⋅ e q ( b i t s ( 1 ) , ( r 2 , r 3 ) ) + a 8 ⋅ e q ( b i t s ( 2 ) , ( r 2 , r 3 ) ) + a 12 ⋅ e q ( b i t s ( 3 ) , ( r 2 , r 3 ) ) = a 0 ⋅ e q ( 0 , r 2 ) e q ( 0 , r 3 ) + a 4 ⋅ e q ( 1 , r 2 ) e q ( 0 , r 3 ) + a 8 ⋅ e q ( 0 , r 2 ) e q ( 1 , r 3 ) + a 12 ⋅ e q ( 1 , r 2 ) e q ( 1 , r 3 ) = e q ( 0 , r 2 ) ⋅ ( a 0 ⋅ e q ( 0 , r 3 ) + a 8 ⋅ e q ( 1 , r 3 ) ) + e q ( 1 , r 2 ) ⋅ ( a 4 ⋅ e q ( 0 , r 3 ) + a 12 ⋅ e q ( 1 , r 3 ) ) = e q ( 0 , r 2 ) ⋅ ( f o l d ( r 3 , ( a 0 , a 8 ) ) ) + e q ( 1 , r 2 ) ⋅ ( f o l d ( r 3 , ( a 4 , a 12 ) ) ) = f o l d ( r 2 , r 3 , ( a 0 , a 4 , a 8 , a 12 ) ) \begin{aligned}
f(0,0,r_2,r_3) &= \sum_{i=0}^{3} a_i \cdot eq(\mathsf{bits}(i), (0,0,r_2,r_3)) \\
&= f(0,0,0,0) \cdot eq(\mathsf{bits}(0), (0,0,r_2,r_3)) + f(0,0,1,0) \cdot eq(\mathsf{bits}(4), (0,0,r_2,r_3)) \\
& + f(0,0,0,1) \cdot eq(\mathsf{bits}(8), (0,0,r_2,r_3)) + f(0,0,1,1) \cdot eq(\mathsf{bits}(12), (0,0,r_2,r_3)) \\
&= a_0 \cdot eq(\mathsf{bits}(0), (r_2,r_3)) + a_4 \cdot eq(\mathsf{bits}(1), (r_2,r_3)) \\
& + a_8 \cdot eq(\mathsf{bits}(2), (r_2,r_3)) + a_{12} \cdot eq(\mathsf{bits}(3), (r_2,r_3)) \\
& = a_0 \cdot eq(0,r_2)eq(0,r_3) + a_4 \cdot eq(1,r_2)eq(0,r_3) + a_8 \cdot eq(0,r_2)eq(1,r_3) + a_{12} \cdot eq(1,r_2)eq(1,r_3) \\
& = eq(0,r_2)\cdot \Big(a_0 \cdot eq(0,r_3) + a_8 \cdot eq(1,r_3)\Big) + eq(1,r_2)\cdot \Big(a_4 \cdot eq(0,r_3) + a_{12} \cdot eq(1,r_3)\Big) \\
&=eq(0,r_2)\cdot \Big(\mathsf{fold}(r_3,(a_0,a_8))\Big) + eq(1,r_2)\cdot \Big(\mathsf{fold}(r_3,(a_4,a_{12}))\Big) \\
&= \mathsf{fold}(r_2, r_3, (a_0, a_4, a_8, a_{12})) \\
\end{aligned} f ( 0 , 0 , r 2 , r 3 ) = i = 0 ∑ 3 a i ⋅ e q ( bits ( i ) , ( 0 , 0 , r 2 , r 3 )) = f ( 0 , 0 , 0 , 0 ) ⋅ e q ( bits ( 0 ) , ( 0 , 0 , r 2 , r 3 )) + f ( 0 , 0 , 1 , 0 ) ⋅ e q ( bits ( 4 ) , ( 0 , 0 , r 2 , r 3 )) + f ( 0 , 0 , 0 , 1 ) ⋅ e q ( bits ( 8 ) , ( 0 , 0 , r 2 , r 3 )) + f ( 0 , 0 , 1 , 1 ) ⋅ e q ( bits ( 12 ) , ( 0 , 0 , r 2 , r 3 )) = a 0 ⋅ e q ( bits ( 0 ) , ( r 2 , r 3 )) + a 4 ⋅ e q ( bits ( 1 ) , ( r 2 , r 3 )) + a 8 ⋅ e q ( bits ( 2 ) , ( r 2 , r 3 )) + a 12 ⋅ e q ( bits ( 3 ) , ( r 2 , r 3 )) = a 0 ⋅ e q ( 0 , r 2 ) e q ( 0 , r 3 ) + a 4 ⋅ e q ( 1 , r 2 ) e q ( 0 , r 3 ) + a 8 ⋅ e q ( 0 , r 2 ) e q ( 1 , r 3 ) + a 12 ⋅ e q ( 1 , r 2 ) e q ( 1 , r 3 ) = e q ( 0 , r 2 ) ⋅ ( a 0 ⋅ e q ( 0 , r 3 ) + a 8 ⋅ e q ( 1 , r 3 ) ) + e q ( 1 , r 2 ) ⋅ ( a 4 ⋅ e q ( 0 , r 3 ) + a 12 ⋅ e q ( 1 , r 3 ) ) = e q ( 0 , r 2 ) ⋅ ( fold ( r 3 , ( a 0 , a 8 )) ) + e q ( 1 , r 2 ) ⋅ ( fold ( r 3 , ( a 4 , a 12 )) ) = fold ( r 2 , r 3 , ( a 0 , a 4 , a 8 , a 12 )) 全部四个值排在一起，恰好就是上一节协议中 A A A a ⃗ ′ \vec{a}' a ′ r 2 , r 3 r_2, r_3 r 2 , r 3 f ( u 0 , u 1 , u 2 , u 3 ) f(u_0, u_1, u_2, u_3) f ( u 0 , u 1 , u 2 , u 3 )
换句话说，Sumcheck 协议的用处是可以证明 MLE 多项式在任意一个公开点的求值，并且将其转换为 f f f
此时，Prover 只需要将 a ⃗ ′ \vec{a}' a ′ a ⃗ ′ ⋅ ( 1 − u 0 , u 0 ) ⊗ ( 1 − u 1 , u 1 ) \vec{a}'\cdot (1-u_0,u_0)\otimes(1-u_1,u_1) a ′ ⋅ ( 1 − u 0 , u 0 ) ⊗ ( 1 − u 1 , u 1 ) f ~ ( u 0 , u 1 , r 2 , r 3 ) \tilde{f}(u_0, u_1, r_2, r_3) f ~ ( u 0 , u 1 , r 2 , r 3 ) a ⃗ ′ \vec{a}' a ′ A A A r 2 , r 3 r_2, r_3 r 2 , r 3
我们下面给出协议的流程，读者可以对照上面的解释理解下协议的全貌。
协议流程 ¶ 公共输入 ：t \mathsf{t} t u ⃗ = ( u 0 , u 1 , u 2 , u 3 ) \vec{u}=(u_0, u_1, u_2, u_3) u = ( u 0 , u 1 , u 2 , u 3 )
Witness ：a ⃗ = ( a 0 , a 1 , a 2 , … , a 15 ) \vec{a}=(a_0, a_1, a_2, \ldots, a_{15}) a = ( a 0 , a 1 , a 2 , … , a 15 )
承诺： ¶ Prover 计算编码矩阵 B = A G B=AG B = A G
B = [ e n c ( a 0 , a 1 , a 2 , a 3 ) e n c ( a 4 , a 5 , a 6 , a 7 ) e n c ( a 8 , a 9 , a 10 , a 11 ) e n c ( a 12 , a 13 , a 14 , a 15 ) ] = [ e 0 e 1 e 2 e 3 e 4 e 5 e 6 e 7 e 8 e 9 e 10 e 11 e 12 e 13 e 14 e 15 e 16 e 17 e 18 e 19 e 20 e 21 e 22 e 23 e 24 e 25 e 26 e 27 e 28 e 29 e 30 e 31 ] B = \begin{bmatrix}
\mathsf{enc}(a_0, a_1, a_2, a_3) \\
\mathsf{enc}(a_4, a_5, a_6, a_7) \\
\mathsf{enc}(a_8, a_9, a_{10}, a_{11}) \\
\mathsf{enc}(a_{12}, a_{13}, a_{14}, a_{15})
\end{bmatrix}
=
\begin{bmatrix}
e_0 & e_1 & e_2 & e_3 & e_4 & e_5 & e_6 & e_7 \\
e_8 & e_9 & e_{10} & e_{11} & e_{12} & e_{13} & e_{14} & e_{15} \\
e_{16} & e_{17} & e_{18} & e_{19} & e_{20} & e_{21} & e_{22} & e_{23} \\
e_{24} & e_{25} & e_{26} & e_{27} & e_{28} & e_{29} & e_{30} & e_{31}
\end{bmatrix} B = ⎣ ⎡ enc ( a 0 , a 1 , a 2 , a 3 ) enc ( a 4 , a 5 , a 6 , a 7 ) enc ( a 8 , a 9 , a 10 , a 11 ) enc ( a 12 , a 13 , a 14 , a 15 ) ⎦ ⎤ = ⎣ ⎡ e 0 e 8 e 16 e 24 e 1 e 9 e 17 e 25 e 2 e 10 e 18 e 26 e 3 e 11 e 19 e 27 e 4 e 12 e 20 e 28 e 5 e 13 e 21 e 29 e 6 e 14 e 22 e 30 e 7 e 15 e 23 e 31 ⎦ ⎤ 然后对 B B B
t 0 = M e r k l e R o o t ( e 0 , e 8 , e 16 , e 24 ) t 1 = M e r k l e R o o t ( e 1 , e 9 , e 17 , e 25 ) ⋮ t 7 = M e r k l e R o o t ( e 7 , e 15 , e 23 , e 31 ) \begin{aligned}
\mathsf{t}_0 &= \mathsf{MerkleRoot}(e_0, e_8, e_{16}, e_{24}) \\
\mathsf{t}_1 &= \mathsf{MerkleRoot}(e_1, e_9, e_{17}, e_{25}) \\
\vdots \\
\mathsf{t}_7 &= \mathsf{MerkleRoot}(e_7, e_{15}, e_{23}, e_{31}) \\
\end{aligned} t 0 t 1 ⋮ t 7 = MerkleRoot ( e 0 , e 8 , e 16 , e 24 ) = MerkleRoot ( e 1 , e 9 , e 17 , e 25 ) = MerkleRoot ( e 7 , e 15 , e 23 , e 31 ) 最后对这些根计算 Merkle Tree，得到一个根 t \mathsf{t} t
t = M e r k l e R o o t ( t 0 , t 1 , ⋯ , t 7 ) \mathsf{t} = \mathsf{MerkleRoot}(\mathsf{t}_0, \mathsf{t}_1, \cdots, \mathsf{t}_7) t = MerkleRoot ( t 0 , t 1 , ⋯ , t 7 ) Evaluation 证明 ¶ 第一步 ：Prover 与 Verifier 进行第一轮的 Sumcheck 协议：Prover 发送 h ( 0 ) ( X ) h^{(0)}(X) h ( 0 ) ( X )
h ( 0 ) ( X ) = f ( u 0 , u 1 , u 2 , X ) = ∑ b ⃗ ∈ { 0 , 1 } 3 a ~ ( b 0 , b 1 , b 2 , X ) ⋅ w ~ ( b 0 , b 1 , b 2 , X ) h^{(0)}(X) = f(u_0, u_1, u_2, X) = \sum_{\vec{b}\in\{0,1\}^3} \tilde{a}(b_0, b_1, b_2, X) \cdot \tilde{w}(b_0, b_1, b_2, X) h ( 0 ) ( X ) = f ( u 0 , u 1 , u 2 , X ) = b ∈ { 0 , 1 } 3 ∑ a ~ ( b 0 , b 1 , b 2 , X ) ⋅ w ~ ( b 0 , b 1 , b 2 , X ) 第二步 : Verifier 发送随机数 r 3 ∈ F r_3\in\mathbb{F} r 3 ∈ F
f ( u 0 , u 1 , u 2 , u 3 ) = ? h ( 0 ) ( 0 ) + h ( 0 ) ( 1 ) f(u_0, u_1, u_2, u_3)\overset{?}{=}h^{(0)}(0)+h^{(0)}(1) f ( u 0 , u 1 , u 2 , u 3 ) = ? h ( 0 ) ( 0 ) + h ( 0 ) ( 1 ) 第三步 ：Prover 发送 h ( 1 ) ( X ) h^{(1)}(X) h ( 1 ) ( X )
h ( 1 ) ( X ) = f ( u 0 , u 1 , X , r 3 ) = ∑ b ⃗ ∈ { 0 , 1 } 2 a ~ ( b 0 , b 1 , X , r 3 ) ⋅ w ~ ( b 0 , b 1 , X , r 3 ) h^{(1)}(X) =f(u_0, u_1, X, r_3) = \sum_{\vec{b}\in\{0,1\}^2} \tilde{a}(b_0, b_1, X, r_3) \cdot \tilde{w}(b_0, b_1, X, r_3) h ( 1 ) ( X ) = f ( u 0 , u 1 , X , r 3 ) = b ∈ { 0 , 1 } 2 ∑ a ~ ( b 0 , b 1 , X , r 3 ) ⋅ w ~ ( b 0 , b 1 , X , r 3 ) 第四步 ：Verifier 发送随机数 r 2 ∈ F q r_2\in\mathbb{F}_q r 2 ∈ F q
h ( 0 ) ( r 3 ) = f ( u 0 , u 1 , u 2 , r 3 ) = ? h ( 1 ) ( 0 ) + h ( 1 ) ( 1 ) h^{(0)}(r_3) = f(u_0, u_1, u_2, r_3) \overset{?}{=}h^{(1)}(0)+h^{(1)}(1) h ( 0 ) ( r 3 ) = f ( u 0 , u 1 , u 2 , r 3 ) = ? h ( 1 ) ( 0 ) + h ( 1 ) ( 1 ) 第五步 ：Prover 停止 Sumcheck 协议，发送折叠后的 a ⃗ ′ \vec{a}' a ′
a ⃗ ′ = [ f o l d ( r 2 , r 3 , ( a 0 , a 4 , a 8 , a 12 ) ) f o l d ( r 2 , r 3 , ( a 1 , a 5 , a 9 , a 13 ) ) f o l d ( r 2 , r 3 , ( a 2 , a 6 , a 10 , a 14 ) ) f o l d ( r 2 , r 3 , ( a 3 , a 7 , a 11 , a 15 ) ) ] \vec{a}' = \begin{bmatrix}
\mathsf{fold}(r_2, r_3, (a_0, a_4, a_8, a_{12})) \\
\mathsf{fold}(r_2, r_3, (a_1, a_5, a_9, a_{13})) \\
\mathsf{fold}(r_2, r_3, (a_2, a_6, a_{10}, a_{14})) \\
\mathsf{fold}(r_2, r_3, (a_3, a_7, a_{11}, a_{15}))
\end{bmatrix} a ′ = ⎣ ⎡ fold ( r 2 , r 3 , ( a 0 , a 4 , a 8 , a 12 )) fold ( r 2 , r 3 , ( a 1 , a 5 , a 9 , a 13 )) fold ( r 2 , r 3 , ( a 2 , a 6 , a 10 , a 14 )) fold ( r 2 , r 3 , ( a 3 , a 7 , a 11 , a 15 )) ⎦ ⎤ 第六步 ：Verifier 抽样 Q ⊂ { 0 , 1 , 2 , … , 7 } Q\subset\{0, 1, 2, \ldots, 7\} Q ⊂ { 0 , 1 , 2 , … , 7 } ∣ Q ∣ = l |Q|=l ∣ Q ∣ = l
Q = { q 0 , q 1 , … , q l − 1 } Q = \{q_0, q_1, \ldots, q_{l-1}\} Q = { q 0 , q 1 , … , q l − 1 } 第七步：Prover 发送 Q = { q i } Q=\{q_i\} Q = { q i } q i q_i q i B B B b ⃗ q i \vec{b}_{q_i} b q i t q i \mathsf{t}_{q_i} t q i t q i \mathsf{t}_{q_i} t q i t \mathsf{t} t π q i \pi_{q_i} π q i
验证步：Verifier 验证下面的等式是否成立：
所有的 t q i \mathsf{t}_{q_i} t q i t \mathsf{t} t
t q i = M e r k l e R o o t ( b ⃗ q i ) , ∀ q i ∈ Q \mathsf{t}_{q_i} = \mathsf{MerkleRoot}(\vec{b}_{q_i}), \quad \forall q_i\in Q t q i = MerkleRoot ( b q i ) , ∀ q i ∈ Q t q i t_{q_i} t q i t \mathsf{t} t
M e r k l e T r e e . v e r i f y ( t , t q i , π q i ) = 1 , ∀ q i ∈ Q \mathsf{MerkleTree.verify}(\mathsf{t}, \mathsf{t}_{q_i}, \pi_{q_i}) = 1, \quad \forall q_i\in Q MerkleTree.verify ( t , t q i , π q i ) = 1 , ∀ q i ∈ Q 计算 b ⃗ q i \vec{b}_{q_i} b q i a ⃗ ′ T G \vec{a}'^T G a ′ T G f o l d ( r 2 , r 3 , b ⃗ q i ) = ? a ⃗ ′ T G q i , ∀ q i ∈ Q \mathsf{fold}(r_2, r_3,\vec{b}_{q_i}) \overset{?}{=} \vec{a}'^T G_{q_i}, \quad \forall q_i\in Q fold ( r 2 , r 3 , b q i ) = ? a ′ T G q i , ∀ q i ∈ Q 其中 G q i G_{q_i} G q i q i q_i q i
检查向量的内积 a ⃗ ′ ⋅ w ~ ( u 0 , u 1 , r 2 , r 3 ) = ? h ( 1 ) ( r 2 ) = f ~ ( u 0 , u 1 , r 2 , r 3 ) \vec{a}'\cdot\tilde{w}(u_0, u_1, r_2, r_3)\overset{?}{=}h^{(1)}(r_2) = \tilde{f}(u_0, u_1, r_2, r_3) a ′ ⋅ w ~ ( u 0 , u 1 , r 2 , r 3 ) = ? h ( 1 ) ( r 2 ) = f ~ ( u 0 , u 1 , r 2 , r 3 ) 3. 递归调用 ¶ 我们引入一个新的多项式 f ′ ( X 0 , X 1 ) f'(X_0, X_1) f ′ ( X 0 , X 1 ) f ( X 0 , X 1 , X 2 , X 3 ) f(X_0, X_1, X_2, X_3) f ( X 0 , X 1 , X 2 , X 3 ) X 2 = r 2 , X 3 = r 3 X_2=r_2, X_3=r_3 X 2 = r 2 , X 3 = r 3 22 的多项式：
f ′ ( X 0 , X 1 ) = f ( X 0 , X 1 , r 2 , r 3 ) f'(X_0, X_1) = f(X_0, X_1, r_2, r_3) f ′ ( X 0 , X 1 ) = f ( X 0 , X 1 , r 2 , r 3 ) 在上一节协议的第五步 开始，Prover 和 Verifier 实际上可以看成是在证明
f ′ ( u 0 , u 1 ) = h ( 1 ) ( r 2 ) f'(u_0, u_1) = h^{(1)}(r_2) f ′ ( u 0 , u 1 ) = h ( 1 ) ( r 2 ) 而且不难验证， f ′ ( X 0 , X 1 ) f'(X_0, X_1) f ′ ( X 0 , X 1 ) a ⃗ ′ = ( a 0 ′ , a 1 ′ , a 2 ′ , a 3 ′ ) \vec{a}'=(a'_0, a'_1, a'_2, a'_3) a ′ = ( a 0 ′ , a 1 ′ , a 2 ′ , a 3 ′ )
f ′ ( X 0 , X 1 ) = f ( X 0 , X 1 , r 2 , r 3 ) = a 0 ′ ⋅ w ~ ( X 0 , X 1 , r 2 , r 3 ) + a 1 ′ ⋅ w ~ ( X 0 , X 1 , r 2 , r 3 ) + a 2 ′ ⋅ w ~ ( X 0 , X 1 , r 2 , r 3 ) + a 3 ′ ⋅ w ~ ( X 0 , X 1 , r 2 , r 3 ) \begin{aligned}
f'(X_0, X_1) &= f(X_0, X_1, r_2, r_3) \\
&= a'_0\cdot\tilde{w}(X_0, X_1, r_2, r_3) + a'_1\cdot\tilde{w}(X_0, X_1, r_2, r_3) + a'_2\cdot\tilde{w}(X_0, X_1, r_2, r_3) + a'_3\cdot\tilde{w}(X_0, X_1, r_2, r_3)
\end{aligned} f ′ ( X 0 , X 1 ) = f ( X 0 , X 1 , r 2 , r 3 ) = a 0 ′ ⋅ w ~ ( X 0 , X 1 , r 2 , r 3 ) + a 1 ′ ⋅ w ~ ( X 0 , X 1 , r 2 , r 3 ) + a 2 ′ ⋅ w ~ ( X 0 , X 1 , r 2 , r 3 ) + a 3 ′ ⋅ w ~ ( X 0 , X 1 , r 2 , r 3 ) 只是这个证明过程被压缩成： Prover 简单粗暴地把多项式表示（即 a ⃗ ′ \vec{a}' a ′ f ′ f' f ′
请注意！这里我们可以换个思路，上一节描述的前半段协议实际上是把验证目标（验证步的第四步）
f ( u 0 , u 1 , u 2 , u 3 ) = ? v f(u_0, u_1, u_2, u_3) \overset{?}{=} v f ( u 0 , u 1 , u 2 , u 3 ) = ? v 的转换为下面的证明目标：
f ′ ( u 0 , u 1 ) = f ( u 0 , u 1 , r 2 , r 3 ) = ? h ( 1 ) ( r 2 ) f'(u_0, u_1) = f(u_0, u_1, r_2, r_3) \overset{?}{=} h^{(1)}(r_2) f ′ ( u 0 , u 1 ) = f ( u 0 , u 1 , r 2 , r 3 ) = ? h ( 1 ) ( r 2 ) 即证明 MLE 多项式 f ′ ( X 0 , X 1 ) f'(X_0, X_1) f ′ ( X 0 , X 1 ) ( u 0 , u 1 ) (u_0, u_1) ( u 0 , u 1 )
因此，我们可以让 Prover 和 Verifier 递归地调用上一节的协议，把这个 MLE 的求值证明 f ′ ( u 0 , u 1 ) = v ′ f'(u_0, u_1)=v' f ′ ( u 0 , u 1 ) = v ′
观察验证步的第三项 ，是 Verifier 检查 l l l
f o l d ( r 2 , r 3 , b ⃗ q ) = ? a ⃗ ′ G q , ∀ q ∈ Q \mathsf{fold}(r_2, r_3,\vec{b}_{q}) \overset{?}{=} \vec{a}'G_{q}, \quad \forall q\in Q fold ( r 2 , r 3 , b q ) = ? a ′ G q , ∀ q ∈ Q 注意到等式左边可以由 Verifier 计算，等式右边是一个长度为 N / N ′ N/N' N / N ′ N N N f f f N = 2 n N=2^n N = 2 n n n n N ′ N' N ′ f f f N ′ × N 1 N'\times N_1 N ′ × N 1 a ⃗ ′ \vec{a}' a ′ N 1 = N / N ′ N_1=N/N' N 1 = N / N ′
等式右边的矩阵乘法可以拆分为 l l l
协议的递归流程 ¶ 我们假设初始的 MLE 多项式为 f ( 0 ) ( X 0 , X 1 , ⋯ , X n − 1 ) f^{(0)}(X_0, X_1, \cdots, X_{n-1}) f ( 0 ) ( X 0 , X 1 , ⋯ , X n − 1 ) N = 2 n N=2^n N = 2 n
第一次协议调用将多项式的求值形式折叠为 N ′ × N 1 N'\times N_1 N ′ × N 1 A 0 A_0 A 0 N 1 = 2 n 1 N_1=2^{n_1} N 1 = 2 n 1 N ′ = 2 n 0 N'=2^{n_0} N ′ = 2 n 0 n 0 + n 1 = n n_0 + n_1 = n n 0 + n 1 = n N 1 ⋅ N ′ = N N_1\cdot N'=N N 1 ⋅ N ′ = N
A 0 = [ a 0 a 1 ⋯ a N 1 − 1 a N 1 a N 1 + 1 ⋯ a 2 N 1 − 1 ⋮ ⋮ ⋱ ⋮ a ( N 1 − 1 ) N ′ a ( N 1 − 1 ) N ′ + 1 ⋯ a N − 1 ] A_0 = \begin{bmatrix}
a_0 & a_1 & \cdots & a_{N_1-1} \\
a_{N_1} & a_{N_1+1} & \cdots & a_{2N_1-1} \\
\vdots & \vdots & \ddots & \vdots \\
a_{(N_1-1)N'} & a_{(N_1-1)N'+1} & \cdots & a_{N-1}
\end{bmatrix} A 0 = ⎣ ⎡ a 0 a N 1 ⋮ a ( N 1 − 1 ) N ′ a 1 a N 1 + 1 ⋮ a ( N 1 − 1 ) N ′ + 1 ⋯ ⋯ ⋱ ⋯ a N 1 − 1 a 2 N 1 − 1 ⋮ a N − 1 ⎦ ⎤ 承诺计算为
B 0 = A 0 G 1 = [ b 0 b 1 ⋯ b N 1 − 1 b N 1 b N 1 + 1 ⋯ b 2 N 1 − 1 ⋮ ⋮ ⋱ ⋮ b N ′ − 1 b N ′ − 1 + 1 ⋯ b N − 1 ] B_0 = A_0G_1 = \begin{bmatrix}
b_0 & b_1 & \cdots & b_{N_1-1} \\
b_{N_1} & b_{N_1+1} & \cdots & b_{2N_1-1} \\
\vdots & \vdots & \ddots & \vdots \\
b_{N'-1} & b_{N'-1+1} & \cdots & b_{N-1}
\end{bmatrix} B 0 = A 0 G 1 = ⎣ ⎡ b 0 b N 1 ⋮ b N ′ − 1 b 1 b N 1 + 1 ⋮ b N ′ − 1 + 1 ⋯ ⋯ ⋱ ⋯ b N 1 − 1 b 2 N 1 − 1 ⋮ b N − 1 ⎦ ⎤ t ( 0 ) = M e r k l e R o o t ( t 0 , t 1 , ⋯ , t N 1 − 1 ) \mathsf{t}^{(0)} = \mathsf{MerkleRoot}(\mathsf{t}_0, \mathsf{t}_1, \cdots, \mathsf{t}_{N_1-1}) t ( 0 ) = MerkleRoot ( t 0 , t 1 , ⋯ , t N 1 − 1 ) 公共输入 ：
u ⃗ = ( u 0 , u 1 , ⋯ , u n 1 − 1 , u n 1 , u n 1 + 1 , ⋯ , u n − 1 ) \vec{u}=(u_0, u_1, \cdots, u_{n_1-1}, u_{n_1}, u_{n_1+1}, \cdots, u_{n-1}) u = ( u 0 , u 1 , ⋯ , u n 1 − 1 , u n 1 , u n 1 + 1 , ⋯ , u n − 1 ) t ( 0 ) \mathsf{t}^{(0)} t ( 0 ) 协议循环 ：i = 0 , 1 , ⋯ , l − 1 i=0, 1, \cdots, l-1 i = 0 , 1 , ⋯ , l − 1 i i i
循环第一步 ：如果 i = 0 i=0 i = 0
如果 i ≠ 0 i\neq 0 i = 0 f ( i ) f^{(i)} f ( i ) N ′ × N i N'\times N_i N ′ × N i A ( i ) A^{(i)} A ( i ) B ( i ) B^{(i)} B ( i ) t ( i ) \mathsf{t}^{(i)} t ( i ) t ( i ) \mathsf{t}^{(i)} t ( i )
循环第二步 ：Prover 与 Verifier 进行 k = log 2 ( N ′ ) k=\log_2(N') k = log 2 ( N ′ ) r k − 1 ( i ) , r k − 2 ( i ) , ⋯ , r 0 ( i ) r^{(i)}_{k-1}, r^{(i)}_{k-2}, \cdots, r^{(i)}_{0} r k − 1 ( i ) , r k − 2 ( i ) , ⋯ , r 0 ( i ) h ( i ) ( X ) h^{(i)}(X) h ( i ) ( X )
h ( i ) ( X ) = f ~ ( i ) ( u 0 , u 1 , u n 1 − 1 , X , r 1 ( i ) , … , r k − 1 ( i ) ) = ∑ b ⃗ ∈ { 0 , 1 } n 1 a ~ ( i ) ( b ⃗ , X ) ⋅ w ~ ( i ) ( b ⃗ , X ) h^{(i)}(X) = \tilde{f}^{(i)}(u_0, u_1, u_{n_1-1}, X, r^{(i)}_{1},\ldots, r^{(i)}_{k-1}) = \sum_{\vec{b}\in\{0,1\}^{n_1}} \tilde{a}^{(i)}(\vec{b}, X) \cdot \tilde{w}^{(i)}(\vec{b}, X) h ( i ) ( X ) = f ~ ( i ) ( u 0 , u 1 , u n 1 − 1 , X , r 1 ( i ) , … , r k − 1 ( i ) ) = b ∈ { 0 , 1 } n 1 ∑ a ~ ( i ) ( b , X ) ⋅ w ~ ( i ) ( b , X ) 而 h ( i ) ( r 0 ( i ) ) h^{(i)}(r^{(i)}_{0}) h ( i ) ( r 0 ( i ) ) f ~ ( i + 1 ) \tilde{f}^{(i+1)} f ~ ( i + 1 ) ( u 0 , u 1 , ⋯ , u n i − 1 ) (u_0, u_1, \cdots, u_{n_i-1}) ( u 0 , u 1 , ⋯ , u n i − 1 ) v ( i + 1 ) v^{(i+1)} v ( i + 1 )
v ( i + 1 ) = h ( i ) ( r 0 ( i ) ) = f ~ ( i + 1 ) ( u 0 , u 1 , ⋯ , u n i − 1 ) v^{(i+1)}= h^{(i)}(r^{(i)}_{0}) = \tilde{f}^{(i+1)}(u_0, u_1, \cdots, u_{n_i-1}) v ( i + 1 ) = h ( i ) ( r 0 ( i ) ) = f ~ ( i + 1 ) ( u 0 , u 1 , ⋯ , u n i − 1 ) 不难推导，v ( i + 1 ) v^{(i+1)} v ( i + 1 ) a ⃗ ( i + 1 ) \vec{a}^{(i+1)} a ( i + 1 ) w ⃗ ∗ \vec{w}^* w ∗
v ∗ = a ⃗ ( i + 1 ) ⋅ w ⃗ ∗ v^* = \vec{a}^{(i+1)}\cdot\vec{w}^* v ∗ = a ( i + 1 ) ⋅ w ∗ 这里
a ⃗ ( i + 1 ) = f o l d ( ( r 0 ( i ) , r 1 ( i ) , ⋯ , r k − 1 ( i ) ) , a ⃗ ( i ) ) \vec{a}^{(i+1)} = \mathsf{fold}((r^{(i)}_{0}, r^{(i)}_{1}, \cdots, r^{(i)}_{k-1}), \vec{a}^{(i)}) a ( i + 1 ) = fold (( r 0 ( i ) , r 1 ( i ) , ⋯ , r k − 1 ( i ) ) , a ( i ) ) w ⃗ ∗ = f o l d ( ( r 0 ( i ) , r 1 ( i ) , ⋯ , r k − 1 ( i ) ) , w ⃗ ( i ) ) \vec{w}^*= \mathsf{fold}((r^{(i)}_{0}, r^{(i)}_{1}, \cdots, r^{(i)}_{k-1}), \vec{w}^{(i)}) w ∗ = fold (( r 0 ( i ) , r 1 ( i ) , ⋯ , r k − 1 ( i ) ) , w ( i ) ) 请注意，这里我们先不着急占用符号 w ( i + 1 ) w^{(i+1)} w ( i + 1 ) w ⃗ ∗ \vec{w}^* w ∗
循环第三步 ：Verifier 抽样 Q ⊂ { 0 , 1 , 2 , 3 } Q\subset\{0, 1, 2, 3\} Q ⊂ { 0 , 1 , 2 , 3 } ∣ Q ∣ |Q| ∣ Q ∣
Q = { q 0 , q 1 , … , q ∣ Q ∣ − 1 } Q = \{q_0, q_1, \ldots, q_{|Q|-1}\} Q = { q 0 , q 1 , … , q ∣ Q ∣ − 1 } 循环第四步 ：Prover 发送 Q Q Q q ∈ Q q\in Q q ∈ Q B B B b ⃗ q \vec{b}_{q} b q t q ( i ) \mathsf{t}^{(i)}_{q} t q ( i ) t q ( i ) \mathsf{t}^{(i)}_{q} t q ( i ) t ( i ) \mathsf{t}^{(i)} t ( i ) π q ( i ) \pi^{(i)}_{q} π q ( i )
循环第五步 ：Verifier 验证下面的等式是否成立：
所有的 t q ( i ) \mathsf{t}^{(i)}_{q} t q ( i ) t ( i ) \mathsf{t}^{(i)} t ( i )
t q ( i ) = M e r k l e R o o t ( b ⃗ q ) , ∀ q ∈ Q \mathsf{t}^{(i)}_{q} = \mathsf{MerkleRoot}(\vec{b}_{q}), \quad \forall q\in Q t q ( i ) = MerkleRoot ( b q ) , ∀ q ∈ Q t q ( i ) \mathsf{t}^{(i)}_{q} t q ( i ) t ( i ) \mathsf{t}^{(i)} t ( i )
M e r k l e T r e e . v e r i f y ( t ( i ) , t q ( i ) , π q ( i ) ) = 1 , ∀ q ∈ Q \mathsf{MerkleTree.verify}(\mathsf{t}^{(i)}, \mathsf{t}^{(i)}_{q}, \pi^{(i)}_{q}) = 1, \quad \forall q\in Q MerkleTree.verify ( t ( i ) , t q ( i ) , π q ( i ) ) = 1 , ∀ q ∈ Q 循环第六步 ：对于每一个 q ∈ Q q\in Q q ∈ Q a ⃗ ( i + 1 ) \vec{a}^{(i+1)} a ( i + 1 ) G q ( i ) G^{(i)}_q G q ( i ) y q ( i ) y^{(i)}_q y q ( i )
y q ( i ) = a ⃗ ( i + 1 ) ⋅ G q ( i ) y^{(i)}_q = \vec{a}^{(i+1)}\cdot G^{(i)}_q y q ( i ) = a ( i + 1 ) ⋅ G q ( i ) 这里 G q ( i ) G^{(i)}_q G q ( i ) C [ F q , N i , R N i ] C[\mathbb{F}_q,N_i, \mathcal{R}N_i] C [ F q , N i , R N i ] G ( i ) G^{(i)} G ( i ) q q q
循环第七步 ：Verifier 发送随机数 β ( i ) \beta^{(i)} β ( i ) y q ( i ) y^{(i)}_q y q ( i ) v ∗ v^* v ∗
v ( i + 1 ) = v ∗ + β ( i ) ⋅ y 0 ( i ) + β ( i ) 2 ⋅ y 1 ( i ) + ⋯ + β ( i ) ∣ Q ∣ ⋅ y ∣ Q ∣ − 1 ( i ) {v}^{(i+1)} =v^* + \beta^{(i)}\cdot y^{(i)}_0 + {\beta^{(i)}}^2\cdot y^{(i)}_1 + \cdots + {\beta^{(i)}}^{|Q|}\cdot y^{(i)}_{|Q|-1} v ( i + 1 ) = v ∗ + β ( i ) ⋅ y 0 ( i ) + β ( i ) 2 ⋅ y 1 ( i ) + ⋯ + β ( i ) ∣ Q ∣ ⋅ y ∣ Q ∣ − 1 ( i ) 如果 Prover 诚实，那么它应该是下面两个向量的内积：
w ⃗ ( i + 1 ) = w ⃗ ∗ + β ( i ) ⋅ G q 0 ( i ) + β ( i ) 2 ⋅ G q 1 ( i ) + ⋯ + β ( i ) ∣ Q ∣ ⋅ G q ∣ Q ∣ − 1 ( i ) \vec{w}^{(i+1)} = \vec{w}^* + \beta^{(i)}\cdot G^{(i)}_{q_0} + {\beta^{(i)}}^2\cdot G^{(i)}_{q_1} + \cdots + {\beta^{(i)}}^{|Q|}\cdot G^{(i)}_{q_{|Q|-1}} w ( i + 1 ) = w ∗ + β ( i ) ⋅ G q 0 ( i ) + β ( i ) 2 ⋅ G q 1 ( i ) + ⋯ + β ( i ) ∣ Q ∣ ⋅ G q ∣ Q ∣ − 1 ( i ) 其中 G q i G_{q_i} G q i q i q_i q i
循环终止步 ：如果 n i ≤ n ′ n_i \leq n' n i ≤ n ′ 循环第一步 ，令 i ← i + 1 i\leftarrow i+1 i ← i + 1
循环外第一步 ：Prover 直接发送 a ⃗ ( l ) \vec{a}^{(l)} a ( l )
循环外第二步 ：Verifier 计算 w ⃗ ( l ) \vec{w}^{(l)} w ( l )
v ( l ) = ? a ⃗ ( l ) ⋅ w ⃗ ( l ) v^{(l)} \overset{?}{=} \vec{a}^{(l)}\cdot\vec{w}^{(l)} v ( l ) = ? a ( l ) ⋅ w ( l ) 协议完成 。
值得注意的是 a ⃗ ( l ) \vec{a}^{(l)} a ( l ) w ⃗ ( l ) \vec{w}^{(l)} w ( l ) N l N_l N l
4. 降低 Verifier 的计算量 ¶ 上面这个协议的第七步中，计算 w ⃗ ( i + 1 ) \vec{w}^{(i+1)} w ( i + 1 ) w ⃗ ∗ \vec{w}^* w ∗ O ( ∣ Q ∣ ⋅ N ) O(|Q|\cdot N) O ( ∣ Q ∣ ⋅ N )
论文 [NA25] 讨论了如果线性编码是一类特殊的编码，其生成矩阵的每一列都具有 Tensor Structure，那么 Verifier 用指数级的时间复杂度计算出 w ⃗ ( l ) \vec{w}^{(l)} w ( l )
主要想法是，如果有两个向量 r ⃗ \vec{r} r w ⃗ \vec{w} w
r ⃗ = r 0 ⊗ r 1 ⊗ ⋯ ⊗ r k − 1 w ⃗ = w 0 ⊗ w 1 ⊗ ⋯ ⊗ w k − 1 \begin{aligned}
\vec{r} &= r_0 \otimes r_1 \otimes \cdots \otimes r_{k-1} \\
\vec{w} &= w_0 \otimes w_1 \otimes \cdots \otimes w_{k-1} \\
\end{aligned} r w = r 0 ⊗ r 1 ⊗ ⋯ ⊗ r k − 1 = w 0 ⊗ w 1 ⊗ ⋯ ⊗ w k − 1 那么 r ⃗ \vec{r} r w ⃗ \vec{w} w
r ⃗ ⋅ w ⃗ = ∏ i = 0 k − 1 r i ⋅ w i \vec{r}\cdot\vec{w} = \prod_{i=0}^{k-1} r_i \cdot w_i r ⋅ w = i = 0 ∏ k − 1 r i ⋅ w i References ¶