【三】GKR 协议系列之Extended MUL/ADD

  • 白菜
  • 更新于 2023-07-25 12:17
  • 阅读 1897

GKR协议在InteractiveProtocol框架里是一套非常经典的协议,里面有很多细节值得关注一下,本系列专题会逐一detail出来:MultilinearExtensionsSum-CheckExtendedMUL/ADD...本章节手推了一下电路MUL/ADDga

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

问题描述

image.png

要求解的问题:拿到一个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 />

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

点赞 0
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
白菜
白菜
0x6b50...a615
crypto