GKR 协议在Interactive Protocol框架里是一套非常经典的协议，里面有很多细节值得关注一下，本系列专题主要通过手推的方式明确各个模块执行的时间成本：
本章节，我们就一个数气球的toy case 来detail 一下Sum-Check的逻辑。
背景
假定有这么一个场景：
公园里的某个活动中有n n n 1 1 1 0 0 0
我们邀请到Bob来完成这个任务，如果仅有他一个人的话，他只能挨个把所有气球上的标记数字加起来，得到最终结果C C C O ( n ) O(n) O ( n )
Sum-Check可以把效率提高到 $O(\log{n})$，但前提是需要引入另外一个人Alice。那么，Sum-Check 在这里的intuitive overview是什么呢？
Bob把这个任务代理给Alice，具体让她来执行这个统计任务，期间Bob他可以做自己事情，等Alice 把最终的统计结果传过来之后，Bob只需要花较低的时间成本去校验这个结果的就行了，这个校验的时间成本就是 O ( log n ) O(\log{n}) O ( log n )
问题算术化
要解决的问题：
l = ⌈ log n ⌉ g ∈ F l ⟶ F C = ∑ b 1 ∈ { 0 , 1 } ∑ b 2 ∈ { 0 , 1 } . . . ∑ b l ∈ { 0 , 1 } g ( b 1 , b 2 , . . . , b l ) \begin{aligned}
& l = \lceil {\log{n}} \rceil \\
& g \in \mathbb{F^l} \longrightarrow \mathbb{F} \\
& C = \sum_{b_1 \in \{0, 1\}} \sum_{b_2 \in \{0, 1\}} ... \sum_{b_l \in \{0, 1\}} g(b_1, b_2, ..., b_l) \\
\end{aligned} l = ⌈ log n ⌉ g ∈ F l ⟶ F C = b 1 ∈ { 0 , 1 } ∑ b 2 ∈ { 0 , 1 } ∑ ... b l ∈ { 0 , 1 } ∑ g ( b 1 , b 2 , ... , b l ) 如果第i i i ( b 1 , b 2 , . . . , b l ) (b1,b2,...,bl) ( b 1 , b 2 , ... , b l ) i i i
g ( b 1 ( i ) , b 2 ( i ) , . . . , b l ( i ) ) = 1 g(b_1^{(i)}, b_2^{(i)}, ..., b_l^{(i)}) = 1 g ( b 1 ( i ) , b 2 ( i ) , ... , b l ( i ) ) = 1 反之如果是绿色，则：
g ( b 1 ( i ) , b 2 ( i ) , . . . , b l ( i ) ) = 0 g(b_1^{(i)}, b_2^{(i)}, ..., b_l^{(i)}) = 0 g ( b 1 ( i ) , b 2 ( i ) , ... , b l ( i ) ) = 0 在Sum-Check 协议中，对于Verifier Bob而言，他是不知道这n n n g g g
Sum-Check的overview 是，Prover Alice通过brute force的方式把问题的解求出来，得到结果C C C O ( n ) O(n) O ( n ) C C C O ( log n ) O(\log{n}) O ( log n ) O ( n ) O(n) O ( n )
为了方便理解，假定n = 14 ， C = 5 ， q = 11 n=14，C=5，q=11 n = 14 ， C = 5 ， q = 11 l = 4 l=4 l = 4
气球编号 0 1 2 3 4 5 6 7 8 9 10 11 12 13 二进制编码 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 数字标记 0 0 1 0 1 0 0 0 1 1 0 0 1 0
详尽的执行过程
The Start
Prover 把上面 length 为14的vector data encode 进一个MLE polynomial:
g ~ ( X 1 , X 2 , . . . , X 4 ) = 1 ⋅ ( 1 − X 1 ) ∗ X 2 ∗ ( 1 − X 3 ) ∗ ( 1 − X 4 ) + 1 ⋅ ( 1 − X 1 ) ∗ ( 1 − X 2 ) ∗ X 3 ∗ ( 1 − X 4 ) + 1 ⋅ ( 1 − X 1 ) ∗ ( 1 − X 2 ) ∗ ( 1 − X 3 ) ∗ X 4 + 1 ⋅ X 1 ∗ ( 1 − X 2 ) ∗ ( 1 − X 3 ) ∗ X 4 + 1 ⋅ ( 1 − X 1 ) ∗ ( 1 − X 2 ) ∗ X 3 ∗ X 4 \begin{aligned}
\widetilde{g}(X_1, X_2, ..., X_4) = & 1 \cdot (1 - X_1)*X_2*(1 - X_3)*(1 - X_4) \\
&+ 1 \cdot (1 - X_1) * (1 - X_2) * X_3 * (1 - X_4) \\
&+ 1 \cdot (1 - X_1) * (1 - X_2) * (1 - X_3) * X_4 \\
&+ 1 \cdot X_1 * (1 - X_2) * (1 - X_3) * X_4 \\
&+ 1 \cdot (1 - X_1) * (1 - X_2) * X_3 * X_4 \\
\end{aligned} \\ g ( X 1 , X 2 , ... , X 4 ) = 1 ⋅ ( 1 − X 1 ) ∗ X 2 ∗ ( 1 − X 3 ) ∗ ( 1 − X 4 ) + 1 ⋅ ( 1 − X 1 ) ∗ ( 1 − X 2 ) ∗ X 3 ∗ ( 1 − X 4 ) + 1 ⋅ ( 1 − X 1 ) ∗ ( 1 − X 2 ) ∗ ( 1 − X 3 ) ∗ X 4 + 1 ⋅ X 1 ∗ ( 1 − X 2 ) ∗ ( 1 − X 3 ) ∗ X 4 + 1 ⋅ ( 1 − X 1 ) ∗ ( 1 − X 2 ) ∗ X 3 ∗ X 4 同时Prover 初始的claim 值为5:
Prover claims： H 0 = ∑ b 1 ∈ { 0 , 1 } ∑ b 2 ∈ { 0 , 1 } . . . ∑ b 4 ∈ { 0 , 1 } g ( b 1 , b 2 , . . . , b 4 ) = 5 \begin{aligned}
\text{Prover claims： } H_0 &= \sum_{b_1 \in \{0, 1\}} \sum_{b_2 \in \{0, 1\}} ... \sum_{b_4 \in \{0, 1\}} g(b_1, b_2, ..., b_4) \\
&= 5
\end{aligned} \\ Prover claims ： H 0 = b 1 ∈ { 0 , 1 } ∑ b 2 ∈ { 0 , 1 } ∑ ... b 4 ∈ { 0 , 1 } ∑ g ( b 1 , b 2 , ... , b 4 ) = 5 Round One
Prover 首先需要证明初始的claim: H 0 = ? 5 H_0 \overset{?} = 5 H 0 = ? 5
Prover owns the actual MLE function : h 1 ( X 1 ) = ∑ b 2 ∈ { 0 , 1 } . . . ∑ b 4 ∈ { 0 , 1 } g ~ ( X 1 , b 2 , . . . , b 4 ) = 3 ( 1 − X 1 ) + 1 Prover provide proof for H 0 = 5 claims again : H 1 ( X 1 ) = h 1 ( X 1 ) = ∑ b 2 ∈ { 0 , 1 } . . . ∑ b 4 ∈ { 0 , 1 } g ~ ( X 1 , b 2 , . . . , b 4 ) = 3 ( 1 − X 1 ) + 1 Verifier verify the proof : H 1 ( 0 ) + H 1 ( 1 ) = ? H 0 , if true continues ... \begin{aligned}
& \text{Prover owns the actual MLE function}: h_1(X_1) = \sum_{b_2 \in \{0, 1\}} ... \sum_{b_4 \in \{0, 1\}} \widetilde{g}(X_1, b_2, ..., b_4) = 3(1 - X_1) + 1 \\
& \text{Prover provide proof for } H_0 =5 \\
& \text{ claims again}: \textcolor{red} {H_1(X_1) = h_1(X_1)} = \sum_{b_2 \in \{0, 1\}} ... \sum_{b_4 \in \{0, 1\}} \widetilde{g}(X_1, b_2, ..., b_4) = 3(1 - X_1) + 1 \\
& \text{Verifier verify the proof}: H_1(0) + H_1(1) \overset{?} = H_0, \text{ if true continues ...} \\
\end{aligned} Prover owns the actual MLE function : h 1 ( X 1 ) = b 2 ∈ { 0 , 1 } ∑ ... b 4 ∈ { 0 , 1 } ∑ g ( X 1 , b 2 , ... , b 4 ) = 3 ( 1 − X 1 ) + 1 Prover provide proof for H 0 = 5 claims again : H 1 ( X 1 ) = h 1 ( X 1 ) = b 2 ∈ { 0 , 1 } ∑ ... b 4 ∈ { 0 , 1 } ∑ g ( X 1 , b 2 , ... , b 4 ) = 3 ( 1 − X 1 ) + 1 Verifier verify the proof : H 1 ( 0 ) + H 1 ( 1 ) = ? H 0 , if true continues ... Round Two
Prover need to prove what he claims last round：H 1 ( X 1 ) = ? h 1 ( X 1 ) H_1(X_1) \overset{?} = h_1(X_1) H 1 ( X 1 ) = ? h 1 ( X 1 ) probabilistic proof system then：
Verifier generate a challenge factor say : r 1 = 4 and sends to Prover ⟹ { H 1 ( X 1 ) = h 1 ( X 1 ) with high probability , continues if H 1 ( 4 ) = h 1 ( 4 ) H 1 ( X 1 ) ≠ h 1 ( X 1 ) with high probability , breaks while others Prover owns the actual MLE function : h 2 ( X 2 ) = ∑ b 3 ∈ { 0 , 1 } . . . ∑ b 4 ∈ { 0 , 1 } g ~ ( 4 , X 2 , . . . , b 4 ) = 2 X 2 − 5 Prover provides proof for H 1 ( 4 ) = h 1 ( 4 ) , claims again : H 2 ( X 2 ) = h 2 ( X 2 ) = ∑ b 3 ∈ { 0 , 1 } . . . ∑ b 4 ∈ { 0 , 1 } g ~ ( 4 , X 2 , . . . , b 4 ) = 2 X 2 − 5 Verifier verify the proof: H 2 ( 0 ) + H 2 ( 1 ) = H 1 ( 4 ) = ? h 1 ( 4 ) , if true continues ... \begin{aligned}
& \text{Verifier generate a challenge factor say}: r_1 = 4 \text{ and sends to Prover} \\
& \Longrightarrow \begin{cases}
H_1(X_1) = h_1(X_1) \textbf{ with high probability}, \text{ continues if } H_1(4) = h_1(4) \\
H_1(X_1) \neq h_1(X_1) \textbf{ with high probability}, \text{ breaks while others} \\
\end{cases} \\
& \text{Prover owns the actual MLE function}: h_2(X_2) = \sum_{b_3 \in \{0, 1\}} ... \sum_{b_4 \in \{0, 1\}} \widetilde{g}(4, X_2, ..., b_4) = 2X_2 - 5 \\
& \text{Prover provides proof for } H_1(4) = h_1(4), \\
& \text{ claims again }: \textcolor{red} {H_2(X_2) = h_2(X_2)} = \sum_{b_3 \in \{0, 1\}} ... \sum_{b_4 \in \{0, 1\}} \widetilde{g}(4, X_2, ..., b_4) = 2X_2 - 5 \\
& \text{Verifier verify the proof: } H_2(0) + H_2(1) = H_1(4) \overset{?} = h_1(4), \text{ if true continues ...} \\
\end{aligned} Verifier generate a challenge factor say : r 1 = 4 and sends to Prover ⟹ { H 1 ( X 1 ) = h 1 ( X 1 ) with high probability , continues if H 1 ( 4 ) = h 1 ( 4 ) H 1 ( X 1 ) = h 1 ( X 1 ) with high probability , breaks while others Prover owns the actual MLE function : h 2 ( X 2 ) = b 3 ∈ { 0 , 1 } ∑ ... b 4 ∈ { 0 , 1 } ∑ g ( 4 , X 2 , ... , b 4 ) = 2 X 2 − 5 Prover provides proof for H 1 ( 4 ) = h 1 ( 4 ) , claims again : H 2 ( X 2 ) = h 2 ( X 2 ) = b 3 ∈ { 0 , 1 } ∑ ... b 4 ∈ { 0 , 1 } ∑ g ( 4 , X 2 , ... , b 4 ) = 2 X 2 − 5 Verifier verify the proof: H 2 ( 0 ) + H 2 ( 1 ) = H 1 ( 4 ) = ? h 1 ( 4 ) , if true continues ... Round Three
Prover need to prove what he claims last round：H 2 ( X 2 ) = ? h 2 ( X 2 ) H_2(X_2) \overset{?} = h_2(X_2) H 2 ( X 2 ) = ? h 2 ( X 2 ) probabilistic proof system then：
Verifier generate a challenge factor say : r 2 = 3 and sends to Prover ⟹ { H 2 ( X 2 ) = h 2 ( X 2 ) with high probability , continues if H 2 ( 3 ) = h 2 ( 3 ) H 2 ( X 2 ) ≠ h 2 ( X 2 ) with high probability , breaks while others Prover owns the actual MLE function : h 3 ( X 3 ) = ∑ b 4 ∈ { 0 , 1 } g ~ ( 4 , 3 , X 3 , b 4 ) = 23 X 3 − 11 Prover provides proof for H 2 ( 3 ) = h 2 ( 3 ) , claims again : H 3 ( X 3 ) = h 3 ( X 3 ) = ∑ b 4 ∈ { 0 , 1 } g ~ ( 4 , 3 , X 3 , b 4 ) = 23 X 3 − 11 Verifier verify the proof: H 3 ( 0 ) + H 3 ( 1 ) = H 2 ( 3 ) = ? h 2 ( 3 ) , if true continues ... \begin{aligned}
& \text{Verifier generate a challenge factor say}: r_2 = 3 \text{ and sends to Prover} \\
& \Longrightarrow \begin{cases}
H_2(X_2) = h_2(X_2) \textbf{ with high probability}, \text{ continues if } H_2(3) = h_2(3) \\
H_2(X_2) \neq h_2(X_2) \textbf{ with high probability}, \text{ breaks while others} \\
\end{cases} \\
& \text{Prover owns the actual MLE function}: h_3(X_3) = \sum_{b_4 \in \{0, 1\}} \widetilde{g}(4, 3, X_3, b_4) = 23X_3 - 11 \\
& \text{Prover provides proof for } H_2(3) = h_2(3), \\
& \text{ claims again }: \textcolor{red} {H_3(X_3) = h_3(X_3)} = \sum_{b_4 \in \{0, 1\}} \widetilde{g}(4, 3, X_3, b_4) = 23X_3 - 11 \\
& \text{Verifier verify the proof: } H_3(0) + H_3(1) = H_2(3) \overset{?} = h_2(3), \text{ if true continues ...} \\
\end{aligned} Verifier generate a challenge factor say : r 2 = 3 and sends to Prover ⟹ { H 2 ( X 2 ) = h 2 ( X 2 ) with high probability , continues if H 2 ( 3 ) = h 2 ( 3 ) H 2 ( X 2 ) = h 2 ( X 2 ) with high probability , breaks while others Prover owns the actual MLE function : h 3 ( X 3 ) = b 4 ∈ { 0 , 1 } ∑ g ( 4 , 3 , X 3 , b 4 ) = 23 X 3 − 11 Prover provides proof for H 2 ( 3 ) = h 2 ( 3 ) , claims again : H 3 ( X 3 ) = h 3 ( X 3 ) = b 4 ∈ { 0 , 1 } ∑ g ( 4 , 3 , X 3 , b 4 ) = 23 X 3 − 11 Verifier verify the proof: H 3 ( 0 ) + H 3 ( 1 ) = H 2 ( 3 ) = ? h 2 ( 3 ) , if true continues ... Round Four
Prover need to prove what he claims last round：H 3 ( X 3 ) = ? h 3 ( X 3 ) H_3(X_3) \overset{?} = h_3(X_3) H 3 ( X 3 ) = ? h 3 ( X 3 ) probabilistic proof system then：
Verifier generate a challenge factor say : r 3 = 2 and sends to Prover ⟹ { H 3 ( X 3 ) = h 3 ( X 3 ) with high probability , continues if H 3 ( 2 ) = h 3 ( 2 ) H 3 ( X 3 ) ≠ h 3 ( X 3 ) with high probability , breaks while others Prover owns the actual MLE function : h 4 ( X 4 ) = g ~ ( 4 , 3 , 2 , X 4 ) = 21 − 7 X 4 Prover provides proof for H 3 ( 2 ) = h 3 ( 2 ) , claims again : H 4 ( X 4 ) = h 4 ( X 4 ) = g ~ ( 4 , 3 , 2 , X 4 ) = 21 − 7 X 4 Verifier verify the proof: H 4 ( 0 ) + H 4 ( 1 ) = H 3 ( 2 ) = ? h 3 ( 2 ) , if true continues ... \begin{aligned}
& \text{Verifier generate a challenge factor say}: r_3 = 2 \text{ and sends to Prover} \\
& \Longrightarrow \begin{cases}
H_3(X_3) = h_3(X_3) \textbf{ with high probability}, \text{ continues if } H_3(2) = h_3(2) \\
H_3(X_3) \neq h_3(X_3) \textbf{ with high probability}, \text{ breaks while others} \\
\end{cases} \\
& \text{Prover owns the actual MLE function}: h_4(X_4) = \widetilde{g}(4, 3, 2, X_4) = 21 - 7X_4 \\
& \text{Prover provides proof for } H_3(2) = h_3(2), \\
& \text{ claims again }: \textcolor{red} {H_4(X_4) = h_4(X_4)} = \widetilde{g}(4, 3, 2, X_4) = 21 - 7X_4 \\
& \text{Verifier verify the proof: } H_4(0) + H_4(1) = H_3(2) \overset{?} = h_3(2), \text{ if true continues ...} \\
\end{aligned} Verifier generate a challenge factor say : r 3 = 2 and sends to Prover ⟹ { H 3 ( X 3 ) = h 3 ( X 3 ) with high probability , continues if H 3 ( 2 ) = h 3 ( 2 ) H 3 ( X 3 ) = h 3 ( X 3 ) with high probability , breaks while others Prover owns the actual MLE function : h 4 ( X 4 ) = g ( 4 , 3 , 2 , X 4 ) = 21 − 7 X 4 Prover provides proof for H 3 ( 2 ) = h 3 ( 2 ) , claims again : H 4 ( X 4 ) = h 4 ( X 4 ) = g ( 4 , 3 , 2 , X 4 ) = 21 − 7 X 4 Verifier verify the proof: H 4 ( 0 ) + H 4 ( 1 ) = H 3 ( 2 ) = ? h 3 ( 2 ) , if true continues ... The End
Prover need to prove what he claims last round：H 4 ( X 4 ) = ? h 4 ( X 4 ) H_4(X_4) \overset{?} = h4_(X_4) H 4 ( X 4 ) = ? h 4 ( X 4 ) probabilistic proof system then：
Verifier generate a challenge factor say : r 4 = 1 and sends to Oracle ⟹ { H 4 ( X 4 ) = h 4 ( X 4 ) with high probability , continues if H 4 ( 1 ) = h 4 ( 1 ) H 4 ( X 4 ) ≠ h 4 ( X 4 ) with high probability , breaks while others Verifier retrives from Orcale : h 4 ( 1 ) = g ~ ( 4 , 3 , 2 , 1 ) = 14 m o d 5 = 4 Verifier verify that : H 4 ( 1 ) = ? h 4 ( 1 ) , if true accepts, otherwise rejects \begin{aligned}
& \text{Verifier generate a challenge factor say}: r_4 = 1 \text{ and sends to Oracle} \\
& \Longrightarrow \begin{cases}
H_4(X_4) = h_4(X_4) \textbf{ with high probability}, \text{ continues if } H_4(1) = h_4(1) \\
H_4(X_4) \neq h_4(X_4) \textbf{ with high probability}, \text{ breaks while others} \\
\end{cases} \\
& \text{Verifier retrives from Orcale}: h_4(1) = \widetilde{g}(4, 3, 2, 1) = 14 \mod 5 = 4 \\
& \text{Verifier verify that }: H_4(1) \overset{?} = h_4(1), \text{ if true accepts, otherwise rejects} \\
\end{aligned} Verifier generate a challenge factor say : r 4 = 1 and sends to Oracle ⟹ { H 4 ( X 4 ) = h 4 ( X 4 ) with high probability , continues if H 4 ( 1 ) = h 4 ( 1 ) H 4 ( X 4 ) = h 4 ( X 4 ) with high probability , breaks while others Verifier retrives from Orcale : h 4 ( 1 ) = g ( 4 , 3 , 2 , 1 ) = 14 mod 5 = 4 Verifier verify that : H 4 ( 1 ) = ? h 4 ( 1 ) , if true accepts, otherwise rejects 参考文献
【1】Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation Proofs, Arguments, and Zero-Knowledge
