{"content":{"title":"【三】GKR 协议系列之Extended MUL/ADD","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# 问题描述\r\n\r\n\r\n\r\n要求解的问题：拿到一个MUL gate的MLE多项式表达MUL，如何进行求解。\r\n\r\n\r\n$$\r\n\\widetilde{MUL}_i(z) = \\sum_{a \\in \\{0, 1\\}^{k_i}} \\chi_{(a, in_{1, i}(a), in_{2, i}(a))}(z) \r\n$$\r\n\r\n# 求解过程\r\n\r\n假定第**0th**层，$i=0$，把$\\widetilde{MUL}_0(z)$进行拆解：\r\n\r\n$$\r\n\\widetilde{MUL}_0(z) = \\chi_{(0, in_{1, 0}(0), in_{2, 0}(0))}(z) + \\chi_{(1, in_{1, 0}(1), in_{2, 0}(1))}(z) \r\n$$\r\n\r\n
\r\n\r\n等式右边第$1$项为第**0th** 层第$1$个节点MUL gate对应的Lagrange Basis Polynomial，我们有：\r\n\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n& in_{1, 0}(0) = (0, 0) \\\\\r\n\r\n& in_{2, 0}(0) = (0, 1) \\\\\r\n\r\n& z = (x_1, x_2, x_3, x_4) \\\\\r\n\r\n\\end{aligned}\r\n\r\n$$\r\n\r\n求解公式：\r\n\r\n\r\n$$\r\n\\chi_{(in_{1, 0}(0) , in_{2, 0}(0))}(z) = \\chi_{(0, 0, 0, 1)}(x_1, x_2, x_3, x_4) =\r\n\r\n\\begin{cases}\r\n\r\n1, \\text{if } (in_{1, 0}(0), in_{2, 0}(0)) = (x_1, x_2, x_3, x_4) \\\\\r\n0, \\text{others}\r\n\r\n\\end{cases} \\\\\r\n\r\n\\Longrightarrow \\chi_{(0, 0, 0, 1)}(x_1, x_2, x_3, x_4) = (1 - x_1) (1 - x_2) (1 - x_3) x_4\r\n$$\r\n\r\n
\r\n\r\n同理，等式右边第2项为第**0th** 层第2个节点MUL gate对应的Lagrange Interpolation Polynomial，我们有：\r\n$$\r\n\\begin{aligned}\r\n\r\n& in_{1, 0}(1) = (1, 0) \\\\\r\n\r\n& in_{2, 0}(1) = (1, 1) \\\\\r\n\r\n& z = (x_1, x_2, x_3, x_4) \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n求解公式：\r\n\r\n$$\r\n\r\n\\chi_{(in_{1, 0}(1) , in_{2, 0}(1))}(z) = \\chi_{(1, 0, 1, 1)}(x_1, x_2, x_3, x_4) =\r\n\r\n\\begin{cases}\r\n\r\n1, \\textcolor{red} {\\text{if and only if }} (in_{1, 0}(1), in_{2, 0}(1)) = (x_1, x_2, x_3, x_4) \\\\\r\n0, \\text{others}\r\n\r\n\\end{cases} \\\\\r\n\r\n\\Longrightarrow \\chi_{(1, 0, 1, 1)}(x_1, x_2, x_3, x_4) = x_1 (1 - x_2) x_3 x_4\r\n$$\r\n\r\n
\r\n\r\n合并后我们就拿到了第**0th** 层的$\\widetilde{MUL}_0(z)$表达式：\r\n\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n\\widetilde{MUL}_0(z) &= \\chi_{(0, in_{1, 0}(0), in_{2, 0}(0))}(z) + \\chi_{(1, in_{1, 0}(1), in_{2, 0}(1))}(z) \\\\\r\n\r\n&= \\chi_{(0, 0, 0, 0, 1)}(x_0, x_1, x_2, x_3, x_4) + \\chi_{(1, 1, 0, 1, 1)}(x_0, x_1, x_2, x_3, x_4) \\\\\r\n\r\n&= (1 - x_0) (1 - x_1) (1 - x_2) (1 - x_3) x_4 + x_0 x_1 (1 - x_2) x_3 x_4 \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n
\r\n\r\n# GKR 协议中应用 Extended MUL/ADD\r\n\r\n比如说，Round 0 Prover 发出两个claims $W_0(0)=4,W_0(1)=2$，Round 1 会证明这两个claims，具体的执行过程如下：\r\n\r\n
\r\n\r\n**STEP ONE**\r\n\r\n通过MLE 定理，Verifier sample 一个challenge factor $r_0 \\in \\mathbb{F}^1$。比如说 $r_0=3$，发送给Prover，需要Prover 证明 $W_0(3)=(4+3∗3) \\mod 5 = 3$\r\n\r\n
\r\n\r\n\r\n其中第0th 层的$ \\widetilde{MUL}_0(z) $表达式中 \r\n\r\n$$\r\n\\begin{aligned} \r\n\r\nz &= (r_0, u, v) \\\\\r\n\r\nr_0 &= x_0 \\\\\r\n\r\nu &= (x_1, x_2) \\\\ \r\n\r\nv &= (x_3, x_4) \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n**STEP TWO**\r\n\r\nProver 向Verifier 发出两个claims $ \\widetilde{W}_1(u) = 3, \\widetilde{W}_1(v) = 1$，其中会指明$u $和$v $的取值，假定：\r\n\r\n$$\r\nu = (2, 4) \\\\\r\n\r\nv = (3, 2) \\\\\r\n$$\r\n\r\n**STEP THREE**\r\n\r\nVerifier 计算相应的$ \\widetilde{MUL}_0(z) $值 \r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n\\widetilde{MUL}_0(3, 2, 4, 3, 2) \r\n\r\n&= (-2) * (-1) * (-3) * (-2) * 2 + 3 * 2 * (-3) * 3 * 2 \\\\\r\n\r\n&= -84 \\mod 5 \\\\\r\n\r\n&= -4 \\mod 5 \\\\\r\n\r\n&= 1 \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n**STEP FOUR**\r\n\r\n\r\nVerifier 验证Prover 上一个round的claims $W_0(0)=4,W_0(1)=2$\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n\\widetilde{W}_0(r_0) &= \\widetilde{MUL}_0(r_0, u, v) (\\widetilde{W}_1(u) * \\widetilde{W}_1(v)) \\\\\r\n\r\n\\textcolor{red} {\\Downarrow} \\\\\r\n\r\n\\widetilde{W}_0(3) &= \\widetilde{MUL}_0(3, 2, 4, 3, 2) * (\\widetilde{W}_1(2, 4) * \\widetilde{W}_1(3, 2)) \\\\\r\n\r\n&= 1 * (3 * 1) \\\\\r\n\r\n&= 3\r\n\r\n\\end{aligned}\r\n$$\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":"QmRqBhB9B9QrA4GDjH4Th1oA9gcQ2CsJy8FFEyYdPVDTbM","timestamp":1690258648,"version":1}