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

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

问题描述

要求解的问题：拿到一个MUL gate的MLE多项式表达MUL，如何进行求解。

$$ \widetilde{MUL}i(z) = \sum{a \in {0, 1}^{k_i}} \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, x_4) + \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 />

GKR 协议中应用 Extended MUL/ADD

比如说，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