{"content":{"title":"【二】GKR 协议系列之Sum-Check","body":"GKR 协议在Interactive Protocol框架里是一套非常经典的协议，里面有很多细节值得关注一下，本系列专题主要通过手推的方式明确各个模块执行的时间成本：\r\n\r\n* [Multilinear Extensions](https://learnblockchain.cn/article/6186)\r\n* [Sum-Check](https://learnblockchain.cn/article/6188)\r\n* [Extended MUL/ADD](https://learnblockchain.cn/article/6189)\r\n* [Original GKR Protocol](https://learnblockchain.cn/article/6199)\r\n...\r\n\r\n\r\n本章节，我们就一个数气球的toy case 来detail 一下Sum-Check的逻辑。\r\n\r\n# 背景\r\n<br />\r\n\r\n假定有这么一个场景：\r\n\r\n<br />\r\n\r\n公园里的某个活动中有$n$ 个气球，只有两种颜色，红色和绿色，红色气球上标记为$1$，绿色气球上标记为$0$。现在有个任务，需要统计一下一共多少个红色气球。\r\n\r\n<br />\r\n\r\n我们邀请到Bob来完成这个任务，如果仅有他一个人的话，他只能挨个把所有气球上的标记数字加起来，得到最终结果$C$。这时对于Bob而言，时间成本为$O(n)$，那么有没有效率更高的算法呢？\r\n\r\n<br />\r\nSum-Check可以把效率提高到 $O(\\log{n})$，但前提是需要引入另外一个人Alice。那么，Sum-Check 在这里的intuitive overview是什么呢？\r\n\r\n<br /><br />\r\n\r\nBob把这个任务代理给Alice，具体让她来执行这个统计任务，期间Bob他可以做自己事情，等Alice 把最终的统计结果传过来之后，Bob只需要花较低的时间成本去校验这个结果的就行了，这个校验的时间成本就是 $O(\\log{n})$。\r\n\r\n\r\n# 问题算术化\r\n<br />\r\n\r\n要解决的问题：\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n& l = \\lceil {\\log{n}} \\rceil \\\\\r\n\r\n& g \\in \\mathbb{F^l} \\longrightarrow \\mathbb{F} \\\\\r\n\r\n& 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) \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n如果第$i $个气球为红色，$(b1​,b2​,...,bl​) $代表着$i $的二进制编码，则:​\r\n\r\n$$\r\ng(b_1^{(i)}, b_2^{(i)}, ..., b_l^{(i)}) = 1\r\n$$\r\n\r\n反之如果是绿色，则：​\r\n\r\n$$\r\ng(b_1^{(i)}, b_2^{(i)}, ..., b_l^{(i)}) = 0\r\n$$\r\n\r\n<br />\r\n\r\n在Sum-Check 协议中，对于Verifier Bob而言，他是不知道这$n$个气球的颜色或者标记的数字，或者说他不知道函数$g$ 的所有取值，但是Prover Alice 知道。\r\n\r\n<br />\r\n\r\nSum-Check的overview 是，Prover Alice通过brute force的方式把问题的解求出来，得到结果$C$，其时间成本为$O(n)$，并把结果告之Verifier Bob。Verifier Bob要做的是验证这个结果$C$对不对，整个验证的成本为$O(\\log{n})$，对比之前自己独自完成任务的时间成本$O(n)$要低很多。那如何验证呢？\r\n\r\n<br />\r\n\r\n为了方便理解，假定$n=14，C=5，q=11$，则$l=4$\r\n\r\n<br />\r\n\r\n| 气球编号   | 0    | 1    | 2        | 3    | 4        | 5    | 6    | 7    | 8        | 9        | 10   | 11   | 12       | 13   |\r\n| ------ | ---- | ---- | -------- | ---- | -------- | ---- | ---- | ---- | -------- | -------- | ---- | ---- | -------- | ---- |\r\n| **二进制编码** | 0000 | 0001 | **0010** | 0011 | **0100** | 0101 | 0110 | 0111 | **1000** | **1001** | 1010 | 1011 | **1100** | 1101 |\r\n| **数字标记** | 0    | 0    | 1        | 0    | 1        | 0    | 0    | 0    | 1        | 1        | 0    | 0    | 1        | 0    |\r\n\r\n# 详尽的执行过程\r\n<br />\r\n\r\n**The Start**\r\n<br />\r\n\r\nProver 把上面 length 为14的vector data encode 进一个MLE polynomial:\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n\\widetilde{g}(X_1, X_2, ..., X_4)  = & 1 \\cdot (1 - X_1)*X_2*(1 - X_3)*(1 - X_4) \\\\\r\n&+ 1 \\cdot (1 - X_1) * (1 - X_2) * X_3 * (1 - X_4) \\\\\r\n&+ 1 \\cdot (1 - X_1) * (1 - X_2) * (1 - X_3) * X_4 \\\\\r\n&+  1 \\cdot X_1 * (1 - X_2) * (1 - X_3) * X_4 \\\\\r\n&+ 1 \\cdot (1 - X_1) * (1 - X_2) * X_3 * X_4 \\\\\r\n\r\n\\end{aligned} \\\\\r\n$$\r\n\r\n同时Prover 初始的claim 值为5:​\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n\\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) \\\\\r\n\r\n&= 5\r\n\r\n\\end{aligned} \\\\\r\n$$\r\n\r\n<br />\r\n\r\n**Round One**\r\n\r\n<br />\r\n\r\nProver 首先需要证明初始的claim: $H_0 \\overset{?} = 5$， then：\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n& \\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 \\\\\r\n\r\n& \\text{Prover provide proof for } H_0 =5 \\\\\r\n& \\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 \\\\\r\n\r\n& \\text{Verifier verify the proof}: H_1(0) + H_1(1) \\overset{?} = H_0, \\text{ if true continues ...} \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n<br />\r\n\r\n**Round Two**\r\n\r\n<br />\r\n\r\nProver 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：\r\n\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n& \\text{Verifier generate a challenge factor say}:  r_1 = 4 \\text{ and sends to Prover} \\\\\r\n\r\n& \\Longrightarrow \\begin{cases}\r\n\r\nH_1(X_1) = h_1(X_1) \\textbf{ with high probability}, \\text{ continues if } H_1(4) = h_1(4) \\\\\r\n\r\nH_1(X_1) \\neq h_1(X_1) \\textbf{ with high probability}, \\text{ breaks while others} \\\\\r\n\r\n\\end{cases} \\\\\r\n\r\n& \\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 \\\\\r\n\r\n\r\n& \\text{Prover provides proof for } H_1(4) = h_1(4), \\\\\r\n& \\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 \\\\\r\n\r\n& \\text{Verifier verify the proof: } H_2(0) + H_2(1) = H_1(4) \\overset{?} = h_1(4),  \\text{ if true continues ...}  \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n<br />\r\n\r\n**Round Three**\r\n\r\n<br />\r\n\r\nProver 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：\r\n\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n& \\text{Verifier generate a challenge factor say}:  r_2 = 3 \\text{ and sends to Prover} \\\\\r\n\r\n& \\Longrightarrow \\begin{cases}\r\n\r\nH_2(X_2) = h_2(X_2) \\textbf{ with high probability}, \\text{ continues if } H_2(3) = h_2(3) \\\\\r\n\r\nH_2(X_2) \\neq h_2(X_2) \\textbf{ with high probability}, \\text{ breaks while others} \\\\\r\n\r\n\\end{cases} \\\\\r\n\r\n& \\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 \\\\\r\n\r\n\r\n& \\text{Prover provides proof for } H_2(3) = h_2(3), \\\\\r\n& \\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 \\\\\r\n\r\n& \\text{Verifier verify the proof: } H_3(0) + H_3(1) = H_2(3) \\overset{?} = h_2(3),  \\text{ if true continues ...}  \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n<br />\r\n\r\n**Round Four**\r\n\r\n​\r\n\r\nProver 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：\r\n\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n& \\text{Verifier generate a challenge factor say}:  r_3 = 2 \\text{ and sends to Prover} \\\\\r\n\r\n& \\Longrightarrow \\begin{cases}\r\n\r\nH_3(X_3) = h_3(X_3) \\textbf{ with high probability}, \\text{ continues if } H_3(2) = h_3(2) \\\\\r\n\r\nH_3(X_3) \\neq h_3(X_3) \\textbf{ with high probability}, \\text{ breaks while others} \\\\\r\n\r\n\\end{cases} \\\\\r\n\r\n& \\text{Prover owns the actual MLE function}: h_4(X_4) = \\widetilde{g}(4, 3, 2, X_4) = 21 - 7X_4 \\\\\r\n\r\n\r\n& \\text{Prover provides proof for } H_3(2) = h_3(2), \\\\\r\n& \\text{ claims again }: \\textcolor{red} {H_4(X_4) = h_4(X_4)} = \\widetilde{g}(4, 3, 2, X_4) =  21 - 7X_4 \\\\\r\n\r\n& \\text{Verifier verify the proof: } H_4(0) + H_4(1) = H_3(2) \\overset{?} = h_3(2),  \\text{ if true continues ...}  \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n<br />\r\n\r\n**The End**\r\n\r\n<br />\r\n\r\nProver need to prove what he claims last round：$H_4​(X_4​) \\overset{?} = h4_​(X_4​)$，according to the principle of **probabilistic proof system** then：\r\n\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n& \\text{Verifier generate a challenge factor say}:  r_4 = 1 \\text{ and sends to Oracle} \\\\\r\n\r\n& \\Longrightarrow \\begin{cases}\r\n\r\nH_4(X_4) = h_4(X_4) \\textbf{ with high probability}, \\text{ continues if } H_4(1) = h_4(1) \\\\\r\n\r\nH_4(X_4) \\neq h_4(X_4) \\textbf{ with high probability}, \\text{ breaks while others} \\\\\r\n\r\n\\end{cases} \\\\\r\n\r\n& \\text{Verifier retrives from Orcale}: h_4(1) = \\widetilde{g}(4, 3, 2, 1) = 14 \\mod 5 = 4 \\\\\r\n\r\n& \\text{Verifier verify that }: H_4(1)  \\overset{?} = h_4(1),  \\text{ if true accepts, otherwise rejects}  \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n# 参考文献\r\n【1】[Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation](https://eprint.iacr.org/2019/317.pdf)\r\n【2】[Proofs, Arguments, and Zero-Knowledge](https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf)"},"author":{"user":"https://learnblockchain.cn/people/15677","address":"0x6b5067C8dd6876eA31919F48Ad2Bb3A4554ba615"},"history":"bafkreibpaagivbya2ytlr7urxtzuf7j66k7mvsqtr4z5taivzjvgidcpwm","timestamp":1724661114,"version":1}