1 前置知识

首先介绍一些多项式相关的前置知识

  • 域上多项式：多项式的系数和取值均来自于域$\mathbb F$中
  • 单项式的阶：单项式中每个变量的指数之和为该单项式的阶
  • 多变量多项式：变量数量大于1个
  • 多线性多项式：多变量多项式，且每个变量的阶均为1，比如$(1-x_1)(1-x_2)$是多线性多项式，$x_1^2x_2$就不是
  • 低阶多项式：若域$\mathbb F$上的多变量多项式中每个变量的阶与$|\mathbb F|$相比均为指数小的，则称为低阶多项式

这里还需要介绍一个新的概念：低阶扩展（Low-Degree Extension，LDE），记函数$g:\{0,1\}^m\rarr \mathbb F$将长度为$m$比特的串映射到域$\mathbb F$上的一个元素，$g$的多项式扩展为一个低阶$m$变量多项式$\tilde g(\cdot)$，且对于所有的$x\in \{0,1\}^m$，均有$\tilde g(x)=g(x)$

多线性多项式的扩展（称为多线性扩展，Multilinear Extension，MLE）也是一个低阶扩展，扩展的结果也是一个多线性多项式，对于给定的函数$Z:\{0,1\}^m\rarr \mathbb F$，$Z$的多线性扩展为一个唯一的多线性多项式$\tilde Z:\mathbb F^m\rarr \mathbb F$，如下

$$ \begin{aligned} \tilde Z(x_1,\dots,x_m)&=\sum_{e\in \{0,1\}^l} Z(e)\cdot \prod^m_{i=1}(x_i\cdot e_i+(1-x_i)\cdot (1-e_i))\\ &=\sum_{e\in \{0,1\}^l} Z(e)\cdot \tilde{eq}(x,e)\\ &=\lang (Z(0),\dots,Z(2^m-1)),(\tilde{eq}(x,0),\dots,\tilde{eq} (x,2^m-1)\rang \end{aligned} $$

其中$\tilde {eq} =\prod^m_{i=1}(e_i\cdot x_i+(1-e_i)\cdot (1-x_i))$，表示多线性多项式的基多项式（与拉氏基多项式的概念类似），当$x=e$时，有$eq(x,e)=1$，否则等于0

这里引用一个ZKP MOOC 2023的例子解释一下会比较清楚

比如现在有一个函数$f$，将$\{0,1\}^2$的串映射至域$\mathbb F$上的元素，如下图所示

该函数对应的多线性扩展如下

构造的方式和前面提到的一样，利用基多项式$eq$，对$(0,0),(0,1),(1,0),(1,1)$四个点进行插值即可，这里不难验证$\tilde f(0,0)=1,\tilde f(0,1)=2,\tilde f(1,0)=8,\tilde f(1,1)=10$​

上面这个图只是举个例子，$\tilde f$与下面表格中的白色区域无关，但是可以验证$\tilde f$在绿色部分中的取值与表格对应

2 Sum-check Protocol

记 $\mu$个变量的低阶多项式$g:\mathbb F^\mu\rarr \mathbb F$，其中每个变量的阶至多为$l$，此时Prover声明$T$满足下列等式

$$ T=\sum_{b_1\in \{0,1\}}\sum_{b_2\in \{0,1\}} \dots \sum_{b_\mu\in \{0,1\}} g(b_1,b_2\dots,b_\mu) $$

Prover最直接的方式是将$g$发送给Verifier，然后Verifier自己计算并验证结果是否等于$T$，但是Verifier的验证开销会在指数级别

为了解决Verifier验证开销过于庞大的问题，Lund等人于1990年首次提出了和校验协议（summ-check protocol），旨在优化Verifier验证上述等式时的计算开销

和校验协议是一个交互式协议，协议会执行$\mu$轮（$\mu$个变量需要$\mu$轮），协议满足完备性、合理性（合理性错误上界为$\frac{\mu\cdot l}{|\mathbb F|}$）和简洁性（这里的简洁性表示Prover和Verifier之间的通信开销为$O(\mu \cdot l)$个域元素）

接下来介绍协议如何进行

首先Prover向Verifier发送一个值$T$，且该值满足上面的式1，之后Prover和Verifier之间进行$\mu$轮交互

在协议的第一轮中，Prover向Verifier发送一个单变量多项式$s_1(X)$，并声明该多项式与下列多项式相等

$$ H_1(X_1)=\sum_{b_2\in \{0,1\}} \dots \sum_{b_\mu\in \{0,1\}} g(X_1,b_2\dots,b_\mu) $$

此时Verifier收到多项式$s_1(X)$后，可以验证是否有$T=s_1(0)+s_1(1)$（因为只有一个变量，其他变量均固定，因此只需要一次求和即可），若验证通过，则Verifier在域$\mathbb F$上随机选择一个数$r_1$并发送给Prover，双方计算$s_1(r_1)$

接下来基于$s_1(r_1)$（也就是用$s_1(r_1)$来代替上面的$T$），双方递归执行上述步骤，直至最后一轮，记该过程中Verifier发送的随机数为$(r_1,\dots,r_{\mu-1})$

在最后一轮中，Prover发送第$\mu$个单变量多项式$s_\mu(X)$，此时Verifier和上面一样，需要先验证是否有$s_{\mu-1}(r_{\mu-1})=s_\mu(0)+s_\mu(1)$​

若等式成立，则Verifier向Prover发送最后一个随机数$r_\mu$，然后Prover利用这$\mu$个随机数$(r_1,\dots,r_{\mu})$，计算$g(r_1,\dots,r_{\mu})$并发送给Verifier，Verifier验证是否有等式$g(r_1,\dots,r_{\mu})=s_\mu(r_\mu)$成立，若成立则接受Prover，否则拒绝Prover

这么讲不太直观，主要是求和符号太多了，这里可以举一个例子

假设有一个包含四个变量的多线性多项式，如下

$$ g(b_1,b_2,b_3,b_4)=9b_1b_2(1-b_3)+2(1-b_1)b_2b_4-6(1-b_1)(1-b_3)+7b_3b_4 $$

此时Prover声明一个$T=26$，如下

$$ T=\sum_{b_1\in \{0,1\}}\sum_{b_2\in \{0,1\}}\sum_{b_3\in \{0,1\}}\sum_{b_4\in \{0,1\}} g(b_1,b_2,b_3,b_4)=26 $$

可以用python写一个求和代码验证一下

首先执行协议的第一轮，Prover向Verifier发送一个单变量多项式$s_1(X)$，如下

$$ s_1(X)=\sum_{b_2\in \{0,1\}}\sum_{b_3\in \{0,1\}}\sum_{b_4\in \{0,1\}} g(X,b_2,b_3,b_4)=38X-6 $$

此时$s_1(0)=-6,s_1(1)=32$，有$T=s_1(0)+s_1(1)$成立，验证通过，因此Verifier在域上选择第一个随机数$r_1=2$，发送给Prover，并且双方均计算$s_1(r_1)=s_1(2)=70$

协议第二轮基于$s_1(2)$进行，Prover在收到$r_1=2$后，计算第二个单变量多项式$s_2(X)$如下

$$ s_2(X)=\sum_{b_3\in \{0,1\}}\sum_{b_4\in \{0,1\}} g(2,X,b_3,b_4)=32X+19 $$

此时$s_2(0)=19,s_2(1)=51$，有$s_1(2)=s_2(0)+s_2(1)$成立，验证通过，因此Verifier在域上选择第二个随机数$r_2=3$，发送给Prover，并且双方均计算$s_2(r_2)=s_2(3)=115$

协议第三轮基于$s_2(3)$进行，Prover在收到$r_2=3$后，计算第三个单变量多项式$s_3(X)$如下

$$ s_3(X)=\sum_{b_4\in \{0,1\}} g(2,3,X,b_4)=-113X+114 $$

此时$s_3(0)=114,s_3(1)=1$，有$s_2(3)=s_3(0)+s_3(1)$成立，验证通过，因此Verifier在域上选择第三个随机数$r_3=2$，发送给Prover，并且双方均计算$s_3(r_3)=s_3(3)=-112$

协议第四轮基于$s_3(2)$进行，Prover在收到$r_3=2$后，计算第四个单变量多项式$s_4(X)$如下

$$ s_4(X)= g(2,3,2,b_4)=8X-60 $$

此时$s_4(0)=-60,s_4(1)=-52$，有$s_3(2)=s_4(0)+s_4(1)$成立，验证通过，Verifier选择最后一个随机数$r_4=4$，发送给Prover，Verifier计算$s_4(r_4)=s_4(4)=-28$

最后Prover利用所有的四个随机数$(r_1,r_2,r_3,r_4)$，计算$g(r_1,r_2,r_3,r_4)=g(2,3,2,4)=-28$，并将结果发送给Verifier，Verifier验证$g(r_1,r_2,r_3,r_4)=s_4(4)$，协议结束

接下来分析一下协议的性质

完备性显然成立，因为整个过程是在多项式的多线性扩展上完成计算的，因此诚实的Prover一定可以说服诚实的Verifier

之后是合理性，若Prover未按照协议要求发送相关的多项式，则协议结束时（最后一个验证等式），Verifier拒绝的概率至少为$1-\frac{\mu\cdot d}{|\mathbb F|}$（这里$d$为多项式中变量的最高阶数）

假设$|\mathbb F|=8$，上面那个例子中多项式的变量均为1，变量数量$\mu =4$，因此协议结束后Verifier拒绝恶意的Prover的概率至少为$1-\frac{4\times 1}{8}=\frac{1}{2}$​

当然只是个例子，实际应用中通常有$|\mathbb F|=2^{128},d=5,\mu=60$，此时Verifier拒绝的概率为$1-\frac{5\times 60}{2^{128}}\approx 2^{-120}$

3 Application

举一个简单的例子，假设有一个$n$个顶点以邻接矩阵的形式表示的图，对应的$n$阶方阵$A\in \{0,1\}^{n*n}$，现在需要求该图中有多少个不同的三角形

对于这个问题，最朴素的方法是遍历图中的每三个顶点构成的三元组，若其有边构成三角形，则计数器加一，也即计算$\sum_{(i,j,k)\in[n]^3}A_{ij}\cdot A_{jk}\cdot A_{ik}$，此时算法开销为$O(n^3)$

不过这个问题有一种更快的方法，计算这个矩阵的三维超立方，也即计算$A^3$，此时算法的复杂度归约至矩阵乘法的复杂度，目前已知的最快的矩阵乘法算法的开销为$O(n^{2.37})$

接下来尝试用上面的和校验协议来进一步优化

首先将$A$视为一个将$\{0,1\}^{\log n}\times \{0,1\}^{\log n}$映射到$\mathbb F$上的函数，然后利用前面提到的多项式扩展，将$A$扩展为一个域$\mathbb F$上的多项式$\tilde A$

接下来定义多项式$g(X,Y,Z)=\tilde A(X,Y)\cdot \tilde A(Y,Z)\cdot \tilde A(X,Z)$，Prover和Verifier在下列多项式上执行和校验协议

$$ \sum_{(a,b,c)\in \{0,1\}^{3\log n}}g(a,b,c) $$

可以分析一下，因为求和的数量为$3\log n$，因此双方在协议中需要的通信量为$O(\log n)$，Verifier需要的计算量为$O(n^2)$，主要来自于计算$g(r_1,r_2,r_3)=\tilde A(r_1,r_2)\cdot \tilde A(r_2,r_3)\cdot \tilde A(r_1,r_3)$，通过引入一些通信量的方式，我们可以将计算复杂度降低至比上面的矩阵乘法还要小一点

不过Prover的开销仍然是$O(n^3)$，有倒霉蛋

后记

多线性多项式扩展与和校验这两个概念，主要是上学期看Spartan的论文，看了一段时间，一直没明白

这次碰巧发现了一个ZKP的春季MOOC，看了一下第四节课的内容，豁然开朗

主要是以前都是公式，全都是求和符号，$\Sigma$开会属实是顶不住，这次MOOC中有一个比较直观的例子，教授也讲的比较详细，不像论文里面就是几行公式带过，真不懂

既然看懂了，那必然也要发个博客纪念一下

References

$[1]$ Srinath T. V. Setty:Spartan: Efficient and general-purpose zkSNARKs without trusted setup. IACR Cryptol. ePrint Arch. 2019: 550 (2019)

$[2]$ ZKP MOOC Lecture 4: Interactive Proofs - YouTube

$[3]$ Zero Knowledge Proofs (zk-learning.org)

$[4]$ Zero Knowledge Proofs MOOC 2023 - Lecture 4 - Silde