{"content":{"title":"【四】GKR 协议(原始版本)","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]()\r\n...\r\n\r\n\r\n本章节重点detail 原始版本的GKR 协议，掌握它的详尽执行过程。\r\n\r\n# 预备知识\r\n* 主要为前三个章节的内容\r\n\r\n# 问题描述\r\n\r\n\r\n\r\n\r\n给定一个电路结构，Prover 给定电路的输出，Verifier 如何验证它？\r\n\r\n# 第0层\r\n\r\n## 初始claims\r\n\r\n
\r\nProver 发出两个claims:\r\n\r\n$$\r\nW_0(0) = 4 \\\\\r\nW_0(1) = 2 \\\\\r\n$$\r\n\r\n
\r\n\r\nVerifier 据此通过Lagrange Interploation 拿到第0层电路的MLE:\r\n$$\r\n\\widetilde{W}_0(r) = 4(1 - r) + 2r = 4 - 2r \\mod 5 = 4 + 3r\r\n$$\r\n\r\n
\r\n\r\n为了证明Prover的两个claims，根据MLE 定理，Verifier 向Prover 发送一个随机的challenge factor，$r^{(0)} \\in \\mathbb{F^1}$，假定$r^{(0)} = 3$，Verifier 与 Prover 各自计算自己的MLE 取值：\r\n\r\n$$\r\n\\text{For Verifier}: \\widetilde{W}_0(3) = 3 \\\\\r\n\r\n\\text{For Prover}: \\widetilde{W'}_0(3) = ? \\\\\r\n$$\r\n\r\n
\r\n\r\n对于Verifier 而言他是看到不Prover 真实的MLE $\\widetilde{W'}_0(r)$，所以接下来需要做的就是证明：\r\n\r\n$$\r\n\\widetilde{W'}_0(3) = \\widetilde{W}_0(3) = 3\r\n$$\r\n\r\n## 进入Sum-Check 协议\r\n> 协议的推导细节可以参考之前章节，[GKR 协议系列之Sum-Check](https://learnblockchain.cn/article/6188)\r\n\r\n\r\n
\r\n\r\n假定$\\widetilde{W'}_0(r) = \\widetilde{W}_0(r) $，我们把它的多项式展开：\r\n\r\n$$\r\n\\widetilde{W}_0(r^{(0)}) = \\sum_{x \\in \\{0, 1\\}^{s_1}} \\sum_{y \\in \\{0, 1\\}^{s_1}} \\widetilde{MUL}_1(r^{(0)}, x, y) (\\widetilde{W}_1(x) * \\widetilde{W}_1(y)) + \\widetilde{ADD}_1(r^{(0)}, x, y) (\\widetilde{W}_1(x) + \\widetilde{W}_1(y))\r\n$$\r\n\r\n
\r\n\r\n为了简化，我们这里只取乘法gate，上面的多项式变为：\r\n\r\n$$\r\n\\widetilde{W}_0(r^{(0)}) = \\sum_{x \\in \\{0, 1\\}^{s_1}} \\sum_{y \\in \\{0, 1\\}^{s_1}} \\widetilde{MUL}_1(r^{(0)}, x, y) (\\widetilde{W}_1(x) * \\widetilde{W}_1(y)) \\\\\r\n\r\n3 \\overset{?} = \\sum_{x \\in \\{0, 1\\}^{s_1}} \\sum_{y \\in \\{0, 1\\}^{s_1}} \\widetilde{MUL}_1(3, x, y) (\\widetilde{W}_1(x) * \\widetilde{W}_1(y)) \\\\\r\n$$\r\n\r\n
\r\n\r\n这是一个标准的Sum-Check 求解过程，根据上一章节内容[Extended ADD/MUL](https://learnblockchain.cn/article/6189)，我们很容易得到如下展开式：\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n3 &\\overset{?} = f_3^{(0)}(x, y)= \\sum_{x \\in \\{0, 1\\}^{s_1}} \\sum_{y \\in \\{0, 1\\}^{s_1}} \\widetilde{MUL}_1(3, x, y) (\\widetilde{W}_1(x) * \\widetilde{W}_1(y)) \\\\\r\n\r\n&= \\sum_{x_1 \\in \\{0, 1\\}} \\sum_{x_2 \\in \\{0, 1\\}} ... \\sum_{x_{s_1} \\in \\{0, 1\\}} \\sum_{y_1 \\in \\{0, 1\\}} \\sum_{y_2 \\in \\{0, 1\\}} ... \\sum_{y_{s_1} \\in \\{0, 1\\}} \\widetilde{MUL}_1(3, x_1, x_2, ..., x_{s_1}, y_1, y_2, ..., y_{s_1}) \r\n\r\n(\\widetilde{W}_1(x_1, x_2, ..., x_{s_1}) * \\widetilde{W}_1(y_1, y_2, ..., y_{s_1})) \\\\\r\n\r\n&= \\sum_{x_1 \\in \\{0, 1\\}} \\sum_{x_2 \\in \\{0, 1\\}} ... \\sum_{x_{s_1} \\in \\{0, 1\\}} \\sum_{y_1 \\in \\{0, 1\\}} \\sum_{y_2 \\in \\{0, 1\\}} ... \\sum_{y_{s_1} \\in \\{0, 1\\}} [-2 (1 - x_1) (1 - x_2) (1 - x_3) x_4 + 3 x_1 (1 - x_2) x_3 x_4] \\\\\r\n\r\n& * [(1 - x_1)(1 - x_2) + 4 (1 - x_1) x_2 + 2 x_1 (1 - x_2) + x_1 x_2] \\\\\r\n& * [(1 - x_3)(1 - x_4) + 4 (1 - x_3) x_4 + 2 x_3 (1 - x_4) + x_3 x_4] \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n
\r\n\r\n一共需要迭代$2s_1$ 个round，Verifier 会依次向Prover 发送$2s_1$ 个challenge factor，作为响应Verifier 会收到来自Prover的$2s_1$ 个单变量多项式\r\n\r\n$$\r\nz = (3, r_{1}^{(0)}, r_{2}^{(0)}, ..., r_{s_1}^{(0)}, r_{s_1 + 1}^{(0)}, r_{s_1 + 2}^{(0)}, ..., r_{2{s_1}}^{(0)}) \\\\\r\n\r\n\\textcolor{red} {\\Downarrow} \\\\\r\n\r\n(h_1^{(0)}(X), h_2^{(0)}(X), ..., h_{s_1}^{(0)}(X), h_{s_1 + 1}^{(0)}(X), h_{s_1 + 2}^{(0)}(X), ..., h_{2s_1}^{(0)}(X)) \\\\\r\n$$\r\n\r\n
\r\n\r\n其中$s_1 = \\log{|S_1|}$，$S_1 $为第1层gate的个数，第0层 Sum-Check 具体的执行过程：\r\n\r\n$$\r\n\\def\\arraystretch{1.5}\r\n\r\n\\begin{array}{c:c:c:c:c}\r\n \\text{Round i} & h_i^{(0)}(X) & h_i^{(0)}(0) + h_i^{(0)}(1) & r_{i}^{(0)} & h_i^{(0)}(r_{i}^{(0)}) \\\\ \\hline\r\n 0 & & & 3 & 3 \\\\ \\hdashline\r\n 1 & 8(X_1^2 - 1) + 3X_1(1 + X_1) & 3 \\textcolor{red} \\checkmark & 2 & 2 \\\\ \\hdashline\r\n 2 & 14(3 - 5X_2)(1 - X_2) & 2 \\textcolor{red} \\checkmark & 0 & 2 \\\\ \\hdashline\r\n 3 & 3(2 + 4X_3)(4 - 3X_3) & 2 \\textcolor{red} \\checkmark & 1 & 3 \\\\ \\hdashline\r\n 4 & 18X_4(2 - X_4) & 3 \\textcolor{red} \\checkmark & 4 & 4 \\\\ \\hdashline\r\n\\end{array}\r\n$$\r\n\r\n## 最后一个Round 的验证\r\n\r\n
\r\n\r\n在第0层Sum-Check最后一个Round，Verifier 会拿着$ = (r^{(0)}, u, v) = (3, 2, 0, 1, 4)$从Oracle 查询得到 $\\widetilde{MUL}_1(z) = 6 * 4 = 24$，另外为了完成最后一步验证，需要Prover 提供两个claims：\r\n\r\n$$\r\n\\widetilde{W}_1(u) = \\widetilde{W}_1(2, 0) = 3 \\\\\r\n\r\n\\widetilde{W}_1(v) = \\widetilde{W}_1(1, 4) = -2 \\\\\r\n$$\r\n\r\n
\r\n\r\nVerifier 拿着这两个claims 进行第0层最后一步验证：\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n \\widetilde{MUL}_1(z) * (\\widetilde{W}_1(u) * \\widetilde{W}_1(v)) \r\n& = 24 * 3 * -2 \\\\\r\n&= -144 \\mod 5 \\\\\r\n&= 4 \\\\\r\n&= h_4^{(0)}(r_{4}^{(0)}) \\textcolor{red} \\checkmark \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n## One More ...\r\n
\r\n\r\n为了把两个claims 压缩到一个claims里，这里用了一个技巧替代了上面的最后一步验证：\r\n\r\n\r\n$$\r\n\\exists l^{(0)}: \\mathbb{F^1} \\longrightarrow \\mathbb{F^{s_1}} \\\\\r\n\r\nl^{(0)}(t) = (a_1 t + b_1, a_2 t + b_2) \\\\\r\n$$\r\n\r\n
\r\n\r\n满足条件：\r\n\r\n$$\r\n\\text{satisfies}: \r\n\r\n\\begin{cases}\r\n\r\nl^{(0)}(0) = u = (2, 0) \\\\\r\nl^{(0)}(1) = v = (1, 4) \\\\\r\n\r\n\\end{cases} \\\\\r\n\r\n\\Longrightarrow l^{(0)}(t) = (-t + 2, 4t) \\\\\r\n$$\r\n\r\n
\r\n\r\n把 $\\widetilde{W}_1(x_1, x_2)$ 由$\\mathbb{F^{s_1}}$ 降维到 $\\mathbb{F^1}$，得到：\r\n\r\n$$\r\n\r\nq(t) = \\widetilde{W}_1(l^{(0)}(t)) = (1 - 4t)(3 - t) + 4t(3t - 2) \\\\\r\n\r\n\\Longrightarrow\r\n\r\n\\begin{cases}\r\n\r\nq(0) = \\widetilde{W}_1(u) = \\widetilde{W}_1(2, 0) = 3 \\\\\r\n\r\nq(1) = \\widetilde{W}_1(v) = \\widetilde{W}_1(1, 4) = -2 \\\\\r\n\r\n\\end{cases}\r\n$$\r\n\r\n
\r\n\r\n把基于$\\mathbb{F^1}$的多项式$q(t) $作为$\\widetilde{W}_1(x_1, x_2) $的替代传递给Verifier，这样Verifiery 就可以拿着它进行最后一步校验了：\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n \\widetilde{MUL}_1(z) * (q(0) *q(1)) \r\n& = 24 * 3 * -2 \\\\\r\n&= -144 \\mod 5 \\\\\r\n&= 4 \\\\\r\n&= h_4^{(0)}(r_{4}^{(0)}) \\textcolor{red} \\checkmark \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n## 新的claims\r\n
\r\n\r\n接下来第1层的迭代就会去校验上面的claims，Verifier 随机采样一个challenge factor $t \\in \\mathbb{F^1}$\r\n\r\n$$\r\n\\text{assumes}: t = 3 \\\\\r\n\r\nr^{(1)} = l(t) = (-1, 12) \\mod 5 = (4, 2) \\\\\r\n$$\r\n\r\n
\r\n\r\n如果不用上面的策略的话，这里的challenge factor 会是 $t \\in \\mathbb{F^2}$。基于这个采样点，拿到下一层Sum-Check 的claims值：\r\n\r\n$$\r\nq(t) = q(3) = 12 * 7 = 84 \\mod 5 = 4\r\n$$\r\n\r\n# 第1层 ...\r\n\r\n同样运用Sum-Check 协议来验证：\r\n\r\n$$\r\n\\widetilde{W}_1(r^{(1)}) = \\sum_{x \\in \\{0, 1\\}^{s_2}} \\sum_{y \\in \\{0, 1\\}^{s_2}} \\widetilde{MUL}_2(r^{(1)}, x, y) (\\widetilde{W}_2(x) * \\widetilde{W}_2(y)) \\\\\r\n\r\n4 \\overset{?} = \\sum_{x \\in \\{0, 1\\}^{s_2}} \\sum_{y \\in \\{0, 1\\}^{s_2}} \\widetilde{MUL}_2(4, 2, x, y) (\\widetilde{W}_2(x) * \\widetilde{W}_2(y)) \\\\\r\n$$\r\n\r\n后面的逻辑跟第0层一样，这里不再赘述。\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":null},"history":null,"timestamp":1690259093,"version":1}