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

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

背景

MLE 为解决Sum-Check 问题提供了一种最优的路径，要证明Sum-Check 多项式在cubic space 的output $C$ 是否正确或者可accept，通过MLE可以采样一个有限域上的challenge factor，$r \in \mathbb{F}^v$，只要证明MLE 在这个challenge factor上的output值正确，那么就可以在一定概率上accept 这个$C$值。

<br />

之所以说一定概率上accept 这个$C$值，而不是100%肯定就是这个$C$值，是因为crypto field本质是一个probabilistic proof system，在后续的章节中我们再展开讨论。回到本节的主题，首先明确Sum-Check 多项式表达：

$$ \begin{aligned}

& v = \log{n} \

& \widetilde{f}(x_1, x_2, ..., xv) = \sum{w \in {0, 1}^v} f(w) * \chi_w(x_1, x_2, ..., x_v) \

& \chi_w(x_1, x_2, ..., xv) = \prod{i = 1}^{i <= v}(w_i x_i + (1 - w_i) (1 - x_i))\

\end{aligned} $$

例子

我们举个例子，手推一下MLE evaluation的计算过程，评估一下时间复杂度：

<br />

假定上图中第1th 层的MLE 作用在有限域$\mathbb{F}_5$上，根据Lagrange Interpolation 我们可以拿到所有Lagrange Basis Polynomials $χ_w(x1,x2)$：

$$ \def\arraystretch{1.5}

\begin{array}{c:c:c} w & f(w) & \chi_w(x_1, x_2) \ \hline (0,0) & 1 & (1 - x_1) (1 - x_2) \ \hdashline (0, 1) & 4 & (1 - x_1) x_2 \ \hdashline (1, 0) & 2 & x_1 (1 - x_2) \ \hdashline (1, 1) & 1 & x_1 x_2 \end{array} $$

与$f(w)$ 相乘后求和即得到MLE 多项式：

$$ f​(x1​,x2​)=(1−x1​)∗(1−x2​)+4∗(1−x1​)∗x2​+2∗x1​∗(1−x2​)+x1​∗x2​​ $$

如果，我们想evaluate MLE上的一个点$r=(3,4)$。

方案一

<br />

更直接的方法是把$χ_w​(x1​,x2​) $作为一个独立的个体，也就是说，$w $每取一个值时它都会计算$v $次。最终计算MLE evaluation总的时间成本为$2^v∗v $次，即时间复杂度为 $O(nlogn)$。

<br />

仔细观察会发现$χ_w​(x1​,x2​)$ 其实是非常有规律的，可以运用动态规划，引入查表操作，把它的计算次数由$v $直接降低到$1 $。是这样吗？

方案二

<br />

分$v $个stage进行迭代，每个stage$ j$生成一个大小为$2^v $的数组$A^{(j)}$，这个数组的DP迭代公式为:

$$ A^{(j)}[(w_1, w_2, ..., w_j)] = A^{(j - 1)}[(w_1, w2, ..., w{j - 1})] * (w_j x_j + (1 - w_j) (1 - x_j)) $$

<br />

$j=1 $时：

$$ \def\arraystretch{1.5}

\begin{array}{c:c:c:c} w_1 & A^{(0)}[(w_0)]) & (w_j x_j + (1 - w_j) (1 - x_j)) & A^{(1)}[(w_1)] \ \hline 0 & \textcolor{red} {1} & (1 - x_1) & (1 - x_1) \\hdashline 1 & \textcolor{red} {1} & x_1 & x_1 \\hdashline \end{array} $$

<br />

$j=2 $时:

$$ \def\arraystretch{1.5}

\begin{array}{c:c:c:c:c} w_1 & w_2 & A^{(1)}[(w_1)]) & (w_j x_j + (1 - w_j) (1 - x_j)) & A^{(2)}[(w_1, w_2)] \ \hline 0 & 0 & \textcolor{red} {(1 - x_1)} & (1 - x_2) & (1 - x_1) (1 - x_2) \\hdashline 0 & 1 & \textcolor{red} {(1 - x_1)} & x_2 & (1 - x_1) x_2 \\hdashline 1 & 0 & \textcolor{red} {x_1} & (1 - x_2) & x_1 (1 - x_2) \\hdashline 1 & 1 & \textcolor{red} {x_1} & x_2 & x_1 x_2 \\hdashline \end{array} $$

到此为止，$χ_w​(x1​,x2​) $所有值就都拿到了，因为红色部分是通过查表拿到的，所以$w $每取一个值时，它只会计算$1 $次。也就是说，最终计算MLE evaluation总的时间成本为$2^v $次，即时间复杂度为 $O(n)$。

参考文献

【1】Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation 【2】Proofs, Arguments, and Zero-Knowledge