GKR 协议在Interactive Protocol框架里是一套非常经典的协议，里面有很多细节值得关注一下，本系列专题主要通过手推的方式明确各个模块执行的时间成本：

• Multilinear Extensions
• Sum-Check
• Extended MUL/ADD
• Original GKR Protocol ...

本章节，我们就一个数气球的toy case 来detail 一下Sum-Check的逻辑。

背景

<br />

假定有这么一个场景：

<br />

公园里的某个活动中有$n$ 个气球，只有两种颜色，红色和绿色，红色气球上标记为$1$，绿色气球上标记为$0$。现在有个任务，需要统计一下一共多少个红色气球。

<br />

我们邀请到Bob来完成这个任务，如果仅有他一个人的话，他只能挨个把所有气球上的标记数字加起来，得到最终结果$C$。这时对于Bob而言，时间成本为$O(n)$，那么有没有效率更高的算法呢？

<br /> Sum-Check可以把效率提高到 $O(\log{n})$，但前提是需要引入另外一个人Alice。那么，Sum-Check 在这里的intuitive overview是什么呢？

<br /><br />

Bob把这个任务代理给Alice，具体让她来执行这个统计任务，期间Bob他可以做自己事情，等Alice 把最终的统计结果传过来之后，Bob只需要花较低的时间成本去校验这个结果的就行了，这个校验的时间成本就是 $O(\log{n})$。

问题算术化

<br />

要解决的问题：

$$ \begin{aligned}

& l = \lceil {\log{n}} \rceil \

& g \in \mathbb{F^l} \longrightarrow \mathbb{F} \

& C = \sum_{b1 \in {0, 1}} \sum{b2 \in {0, 1}} ... \sum{b_l \in {0, 1}} g(b_1, b_2, ..., b_l) \

\end{aligned} $$

如果第$i $个气球为红色，$(b1​,b2​,...,bl​) $代表着$i $的二进制编码，则:​

$$ g(b_1^{(i)}, b_2^{(i)}, ..., b_l^{(i)}) = 1 $$

相反，则：​

$$ g(b_1^{(i)}, b_2^{(i)}, ..., b_l^{(i)}) = 0 $$

<br />

在Sum-Check 中，对于Verifier Bob而言，他是不知道这$n$个气球的颜色或者标记的数字，或者说他不知道函数$g$ 的所有取值，但是Prover Alice 知道。

<br />

Sum-Check的overview 是，Prover Alice提前通过brute force的方式，时间成本为$O(n)$，把问题的解求出来，得到结果$C$，Verifier Bob要做的是校验这个结果$C$对不对，整个校验的成本为$O(\log{n})$，对比之前自己独自完成任务的时间成本$O(n)$要低很多。那如何验证呢？

<br />

为了方便理解，假定$n=14，C=5，q=11$，则$l=4$

<br />

详尽的执行过程

<br />

The Start <br />

Prover owns the full MLE function g​ over g based on 14 points above:

$$ \begin{aligned}

\widetilde{g}(X_1, X_2, ..., X_4) = & (1 - X_1)X_2(1 - X_3)(1 - X_4) \ &+ (1 - X_1) (1 - X_2) X_3 (1 - X_4) \ &+ (1 - X_1) (1 - X_2) (1 - X_3) X_4 \ &+ X_1 (1 - X_2) (1 - X_3) X_4 \ &+ (1 - X_1) (1 - X_2) X_3 * X_4 \

\end{aligned} \ $$

Prover has the initial claim output within cubic space:​

$$ \begin{aligned}

\text{Prover claims： } H0 &= \sum{b1 \in {0, 1}} \sum{b2 \in {0, 1}} ... \sum{b_4 \in {0, 1}} g(b_1, b_2, ..., b_4) \

&= 5

\end{aligned} \ $$

<br />

Round One

<br />

Prover need to prove what he claims just now: $H_0 \overset{?} = 5$， then：

$$ \begin{aligned}

& \text{Prover owns the actual MLE function}: h_1(X1) = \sum{b2 \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(X1)} = \sum{b2 \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} $$

<br />

Round Two

<br />

Prover need to prove what he claims last round：$H_1​(X_1​) \overset{?} = h_1​(X_1​)$，according to the principle of probabilistic proof system then：

$$ \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(X2) = \sum{b3 \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(X2)} = \sum{b3 \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} $$

<br />

Round Three

<br />

Prover need to prove what he claims last round：$H_2​(X_2​) \overset{?} = h_2​(X_2​)$，according to the principle of probabilistic proof system then：

$$ \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(X3) = \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(X3)} = \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} $$

<br />

Round Four

​

Prover need to prove what he claims last round：$H_3​(X_3​) \overset{?} = h_3​(X_3​)$，according to the principle of probabilistic proof system then：

$$ \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} $$

<br />

The End

<br />

Prover need to prove what he claims last round：$H_4​(X4​) \overset{?} = h4​(X_4​)$，according to the principle of probabilistic proof system then：

$$ \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} $$

参考文献

【1】Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation 【2】Proofs, Arguments, and Zero-Knowledge