GKR协议在InteractiveProtocol框架里是一套非常经典的协议,里面有很多细节值得关注一下,本系列专题会逐一detail出来:MultilinearExtensionsSum-CheckExtendedMUL/ADD...本章节手推了一下电路MUL/ADDga
GKR 协议在Interactive Protocol框架里是一套非常经典的协议,里面有很多细节值得关注一下,本系列专题主要通过手推的方式明确各个模块执行的时间成本:
要求解的问题:拿到一个MUL gate的MLE多项式表达MUL,如何进行求解。
$$ \widetilde{MUL}i(z) = \sum{a \in {0, 1}^{ki}} \chi{(a, in{1, i}(a), in{2, i}(a))}(z) $$
假定第0th层,$i=0$,把$\widetilde{MUL}_0(z)$进行拆解:
$$ \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) $$
<br />
等式右边第$1$项为第0th 层第$1$个节点MUL gate对应的Lagrange Basis Polynomial,我们有:
$$ \begin{aligned}
& in_{1, 0}(0) = (0, 0) \
& in_{2, 0}(0) = (0, 1) \
& z = (x_1, x_2, x_3, x_4) \
\end{aligned}
$$
求解公式:
$$ \chi{(in{1, 0}(0) , in{2, 0}(0))}(z) = \chi{(0, 0, 0, 1)}(x_1, x_2, x_3, x_4) =
\begin{cases}
1, \text{if } (in{1, 0}(0), in{2, 0}(0)) = (x_1, x_2, x_3, x_4) \ 0, \text{others}
\end{cases} \
\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 $$
<br /> <br />
同理,等式右边第2项为第0th 层第2个节点MUL gate对应的Lagrange Interpolation Polynomial,我们有: $$ \begin{aligned}
& in_{1, 0}(1) = (1, 0) \
& in_{2, 0}(1) = (1, 1) \
& z = (x_1, x_2, x_3, x_4) \
\end{aligned} $$
求解公式:
$$
\chi{(in{1, 0}(1) , in{2, 0}(1))}(z) = \chi{(1, 0, 1, 1)}(x_1, x_2, x_3, x_4) =
\begin{cases}
1, \textcolor{red} {\text{if and only if }} (in{1, 0}(1), in{2, 0}(1)) = (x_1, x_2, x_3, x_4) \ 0, \text{others}
\end{cases} \
\Longrightarrow \chi_{(1, 0, 1, 1)}(x_1, x_2, x_3, x_4) = x_1 (1 - x_2) x_3 x_4 $$
<br />
合并后我们就拿到了第0th 层的$\widetilde{MUL}_0(z)$表达式:
$$ \begin{aligned}
\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) \
&= \chi_{(0, 0, 0, 0, 1)}(x_0, x_1, x_2, x_3, x4) + \chi{(1, 1, 0, 1, 1)}(x_0, x_1, x_2, x_3, x_4) \
&= (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 \
\end{aligned} $$
<br />
比如说,Round 0 Prover 发出两个claims $W_0(0)=4,W_0(1)=2$,Round 1 会证明这两个claims,具体的执行过程如下:
<br />
STEP ONE
通过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$
<br />
其中第0th 层的$ \widetilde{MUL}_0(z) $表达式中
$$ \begin{aligned}
z &= (r_0, u, v) \
r_0 &= x_0 \
u &= (x_1, x_2) \
v &= (x_3, x_4) \
\end{aligned} $$
STEP TWO
Prover 向Verifier 发出两个claims $ \widetilde{W}_1(u) = 3, \widetilde{W}_1(v) = 1$,其中会指明$u $和$v $的取值,假定:
$$ u = (2, 4) \
v = (3, 2) \ $$
STEP THREE
Verifier 计算相应的$ \widetilde{MUL}_0(z) $值
$$ \begin{aligned}
\widetilde{MUL}_0(3, 2, 4, 3, 2)
&= (-2) (-1) (-3) (-2) 2 + 3 2 (-3) 3 2 \
&= -84 \mod 5 \
&= -4 \mod 5 \
&= 1 \
\end{aligned} $$
STEP FOUR
Verifier 验证Prover 上一个round的claims $W_0(0)=4,W_0(1)=2$
$$ \begin{aligned}
\widetilde{W}_0(r_0) &= \widetilde{MUL}_0(r_0, u, v) (\widetilde{W}_1(u) * \widetilde{W}_1(v)) \
\textcolor{red} {\Downarrow} \
\widetilde{W}_0(3) &= \widetilde{MUL}_0(3, 2, 4, 3, 2) (\widetilde{W}_1(2, 4) \widetilde{W}_1(3, 2)) \
&= 1 (3 1) \
&= 3
\end{aligned} $$
【1】Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation 【2】Proofs, Arguments, and Zero-Knowledge
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!