1 Introduction
跳过，没啥好看的
塞一张效率对比图吧
2 Preliminaries
- $x_i$：表示向量$x$的第$i$个值
- $\mathbf A$：大写粗体表示数组
- $bp=(p,\mathbb G,\mathbb G_T,g,e)$：双线性对，$g$为$\mathbb G$的生成元，$\mathbb G,\mathbb G_T$的阶均为$p$
本文方案中多变量多项式的阶为多项式中变量的最大阶
此外，本文的方案基于q-SBDH假设及其PKE扩展版本
GKR Protocol
首先介绍一下GKR协议中的相关预备知识
GKR协议基于和校验协议构建，这两个知识点之前有介绍过，具体可以看$[3]$，这里不再展开
对于阶为$d$的多项式，其$l$轮和校验协议的合理性误差为$\epsilon=\frac{d\cdot l}{|\mathbb F|}$
这里还需要多线性扩展的相关知识，也可以看$[3]$
多线性扩展还作用于数组，如果需要对一个数组$\mathbf A=(a_0,\dots,a_{n-1})$进行多线性扩展，此时可以将该数组视为一个函数$A:\{0,1\}^{\log n}\rarr \mathbb F$，满足$\forall i \in [0,n-1],A(i)=a_i$，此时再对该函数$A$进行多线性扩展即可，对应的扩展结果为$\tilde A$
GKR协议的相关符号和记法如下
- $S_i$：表示电路第$i$层中计算门的数量，电路最顶层为第0层，最底层为第$d$层，不失一般性假设$S_i$为2的幂次
- $s_i=\lceil \log S_i \rceil$
- $V_i:\{0,1\}^{s_i}\rarr \mathbb F$：输入长度为$s_i$的船，输出电路第$i$层的门标签，由于最顶层为第0层，因此$V_0$为输出标签，$V_d$为输入标签
- $add_i/mult_i:\{0,1\}^{s_{i-1}+2s_i}\rarr \{0,1\}$：文献中称为导线谓词（wiring predicates），输入为第$i-1$层的门标签$z$和两个第$i$层的门标签$x,y$，当且仅当门$z$的输出与门$x,y$的输入相对应时，$add/mult$输出1，否则输出0
根据上述定义，$V_i$可以表示为下列形式
$$ \begin{aligned} V_i(z)=&\textstyle\sum_{x,y\in \{0,1\}^{s_i+1}}(add_{i+1}(z,x,y)\cdot V_{i+1}(x)+V_{i+1}(y))\\ +&mult_{i+1}(z,x,y)\cdot (V_{i+1}(x)\cdot V_{i+1}(y)) \end{aligned} $$
由于$V_i$为多变量多项式，因此可以对其进行多线性扩展$\tilde V_i$
$$ \begin{aligned} \tilde V_i(g)=&\textstyle\sum_{x,y\in\{0,1\}^{s_{i+1}}}f_i(x,y)\\ =&\textstyle\sum_{x,y\in\{0,1\}^{s_{i+1}}}(\tilde {add}_{i+1}(g,x,y)\cdot \tilde V_{i+1}(x)+\tilde V_{i+1}(y))\\ &+\tilde {mult}_{i+1}(g,x,y)\cdot (\tilde V_{i+1}(x)\cdot \tilde V_{i+1}(y)) \end{aligned} \tag 1 $$
GKR协议基于多项式$\tilde V_i$，Prover首先向Verifier声明电路的输出，Verifier首先构建多项式$\tilde V_0$，选择随机向量$g\in \mathbb F^{s_0}$，计算$\tilde V_0(g)$
之后双方基于$\tilde V_0$执行和校验协议，但是对于深度为$d$的电路，和校验协议需要递归执行，最终执行次数与$d$的指数相关
为了解决这个问题，这里有两种方法
第一种方法是$[2]$中合二为一的思想，对于第$i$层的两个预言机查询$\tilde V_i(u),\tilde V_i(v)$，Verifier定义一个映射$\gamma$，满足$\gamma(0)=u,\gamma(1)=v$，并将$\gamma$发送给Prover
之后Prover需要返回一个阶为$s_i$的单变量多项式$h(x)=\tilde V_i(\gamma(x))$，此时Verifier验证是否有$h(0)=\tilde V_i(u),h(1)=\tilde V_i(v)$
若验证通过，则Verifier选择一个随机值$r$，计算$h(r)=\tilde V_i(\gamma(r))=\tilde V_i(w)$，满足$w=\gamma(r)$，Verifier将$r,w$发送给Prover，从而将两个预言机查询减少为一个查询$\tilde V_i(w)$
将上述方法与和校验协议一同使用，双方可以将第$i$层的声明归约至第$i+1$层的声明，最终可归约至输入层的声明，从而完成GKR协议
第二种方法来自于$[4]$，通过构造一个随机线性组合来解决：Verifier选择两个随机值$\alpha_i,\beta_i$，计算一个随机线性组合$\alpha_i\cdot \tilde V_i(u)+\beta_i\cdot \tilde V_i(v)$，之后双方基于这个随机线性组合进行和校验协议
此时和校验协议结束时，双方仍然只需要处理两个$\tilde V_{i+1}$的声明，递归执行上述步骤，选择新的随机性并构造新的随机线性组合，直至到输入层为止，从而完成GKR协议
Libra采用第二种方案，完整的GKR协议如下图所示
Zero-Knowledge Verifiable Polynomial Delegation Scheme
本文用到了零知识可验证多项式委派的方案
记$\mathcal F$为域$\mathbb F$上的$l$变量多项式族，$d$为变量的阶，对于$f\in \mathcal F,t\in \mathbb F^l$，zkVPD方案为算法五元组$(KeyGen,Commit,CheckComm,Open,Verify)$，方案满足完美完备性，绑定性，合理性和零知识性
这里的相关定义可以看原文，不再展开
3 GKR Protocol with Linear Prover Time
本节为GKR协议的Prover构造了一种新的算法，算法可以在线性阶时间内运行，适用于任意分层电路
首先介绍一些算法的构建块
3.1 Linear-time sumcheck for a multilinear function
$[5]$中介绍了一种线性Prover Time的$l$变量多线性函数的和校验协议，这里回顾一下（具体如算法2所示）
对于和校验协议的第$i$轮，Prover需要向Verifier发送一个单变量多项式，如下
$$ f_i(x_i)=\sum_{b_{i+1},\dots,b_l\in\{0,1\}}f(r_1,\dots,r_{i-1},x_i,b_{i+1},\dots,b_l) $$
之后Prover需要向Verifier发送该多项式在0和1上的求值，也即Prover需要发送$f_i(0),f_i(1)$
为了计算上述的求和结果，Prover需要为$f$本地保存一个数组$\mathbf A$，对于第$i$轮交互，Prover需要对于所有的$b_i,\dots, b_l$，计算下列求值，并向数组中存入$2^{l-i+1}$个值
$$ f(r_1,\dots,r_{i-1},b_i,b_{i+1},\dots,b_l) $$
之后Prover根据算法1的步骤4计算$f_i(0),f_i(1)$即可
显然，上述和校验协议的执行时间为$O(2^l)$，比较大，原文给出了相关的解决办法，感兴趣可以看原文
3.2 Linear-time sumcheck for products of multilinear functions
这里介绍一下如何将和校验协议推广为两个多线性函数的乘积$f\cdot g$的和校验
由于$f\cdot g$不为多线性的，因此不能直接使用上一节中的算法2进行和校验
不过两个函数和单个函数的情况类似，此时Prover需要在协议第$i$轮在三个点$t=0,1,2$进行求值
$$ \sum_{b_{i+1},\dots,b_l\in\{0,1\}}f(r_1,\dots,r_{i-1},t,b_{i+1},\dots,b_l)\cdot g(r_1,\dots,r_{i-1},t,b_{i+1},\dots,b_l) $$
上述求和式可以分别调用算法1进行处理，处理的方式如下列算法3所示
3.3 Linear-time sumcheck for GKR functions
接下来考虑与GKR协议相关的特定函数的和校验协议问题
对于给定的点$g$，记大小为$2^l$的数组$\mathbf A_{f_2},\mathbf A_{f_3}$的多线性扩展为$f_2,f_3$，$f_1:\mathbb F^{3l}\rarr \mathbb F$为某个稀疏性为$O(2^l)$（有$O(2^l)$个非零元素）的稀疏数组的多线性扩展，此时考虑下面这个多项式
$$ \sum_{x,y\in\{0,1\}^l}f_1(g,x,y)\cdot f_2(x,)\cdot f_3(y) \tag a $$
如果用算法1的FunctionEvaluations来处理这一类多项式，由于$f_1$有$2^{2l}$个元素需要求和，复杂度为$O(2^{2l})$，因此Prover Time会降低至平方阶
可以通过在数组$\mathbf A$内保存$f_1$中的$2^l$个非零元素来将开销减少至$O(2^l)$，此时算法1的总开销为$O(l\cdot 2^l)$，这里介绍一下如何进一步降低开销
主要思想是将和校验协议拆分为两个阶段
- 对于协议的前$l$轮，将变量$x$绑定至某个随机点$u$
- 协议的后$l$轮，将变量$y$绑定至随机点$v$
此时令$h_g(x)=\textstyle \sum_{y\in\{0,1\}^l}f_1(g,x,y)\cdot f_3(y)$，式a可以改写为
$$ \begin{aligned} \textstyle\sum_{x,y\in\{0,1\}^l}f_1(g,x,y)\cdot f_2(x,)\cdot f_3(y)&=\textstyle\sum_{x\in\{0,1\}^l}f_2(x)\cdot \textstyle\sum_{y\in\{0,1\}^l}f_1(g,x,y)\cdot f_3(y)\\ &=\textstyle\sum_{x\in\{0,1\}^l}f_2(x)\cdot h_g(x) \end{aligned} $$
然后看一下如何在两个阶段处理这个多项式
Phase One
第一阶段中，双方对$f_2\cdot h_g$进行和校验检查，由于$y$可以视为常数，因此这两个函数中仅包含一个变量$x$
因此前$l$轮中，利用算法3对$f_2\cdot h_g$进行和校验
原文给了一个效率优化的办法，不过不是重点，这里不再展开，感兴趣可以看原文
Phase Two
经过第一阶段的处理，此时所有$x$都可以用一个随机数$u$进行表示，此时需要求和的等式变为了
$$ \textstyle \sum_{y\in\{0,1\}^l}f_1(g,u,y)\cdot f_2(u)\cdot f_3(y) $$
第一阶段中已经把$f_2(u)$计算好了，因此这里可以视为常数，而$f_1,f_3$都包含变量$y$，因此与第一阶段相同，对其调用算法3进行验证
这里有一个点需要注意：对$f_1(g,u,y)$和$f_3(y)$调用算法3，而不是对$f_1(g,x,y)$调用算法3
Generalizations
这里可以将上述分阶段处理的思想扩展到$c$个多项式
$$ \textstyle \sum_{x_1,\dots,x_c\in\{0,1\}^c}f_0(g,x_1,\dots,x_c)f_1(x_1)\dots f_c(x_c) $$
这里有几个要求
- $c$为常数
- $f_i$为多线性多项式
- $f_0$包含线性数量的非零值
根据上面的思想，处理这个多项式拆分为$c$个阶段即可
3.4 Putting everything together
这里复制粘贴一下GKR协议的验证等式（式1）
$$ \begin{aligned} \tilde V_i(g)=&\textstyle\sum_{x,y\in\{0,1\}^{s_{i+1}}}f_i(x,y)\\ =&\textstyle\sum_{x,y\in\{0,1\}^{s_{i+1}}}(\tilde {add}_{i+1}(g,x,y)\cdot \tilde V_{i+1}(x)+\tilde V_{i+1}(y))\\ &+\tilde {mult}_{i+1}(g,x,y)\cdot (\tilde V_{i+1}(x)\cdot \tilde V_{i+1}(y)) \end{aligned} \tag 1 $$
不难看出，第二项$\textstyle\sum_{x,y\in\{0,1\}^{s_{i+1}}}\tilde {mult}_{i+1}(g,x,y)\cdot (\tilde V_{i+1}(x)\cdot \tilde V_{i+1}(y))$与式a的形式相同，而第一项可以拆分为两项进行处理
$$ \textstyle\sum_{x,y\in\{0,1\}^{s_{i+1}}}\tilde {add}_{i+1}(g,x,y)\cdot \tilde V_{i+1}(x)+\textstyle\sum_{x,y\in\{0,1\}^{s_{i+1}}}\tilde {add}_{i+1}(g,x,y)\cdot \tilde V_{i+1}(y) $$
上述两个求和式中，第一个求和式可以视为不包含$f_3$的式a，第二个求和式可以视为不包含$f_2$的式a
根据和校验协议的线性性质，双方可以在协议的同一轮中并行执行这三个和校验的实例
原文的附录A介绍了关于效率优化的相关方式，这里不再展开
References
$[1]$ Tiancheng Xie, Jiaheng Zhang, Yupeng Zhang, Charalampos Papamanthou, Dawn Song:Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation. IACR Cryptol. ePrint Arch. 2019: 317 (2019)
$[2]$ Shafi Goldwasser, Yael Tauman Kalai, Guy N. Rothblum:Delegating Computation: Interactive Proofs for Muggles. J. ACM 62(4): 27:1-27:64 (2015)
$[3]$ 多项式扩展与和校验协议 - 三两老友杂的小岛 (snowolf0620.xyz)
$[4]$ Alessandro Chiesa, Michael A. Forbes, Nicholas Spooner:A Zero Knowledge Sumcheck and its Applications. IACR Cryptol. ePrint Arch. 2017: 305 (2017)
$[5]$ Justin Thaler:Time-Optimal Interactive Proofs for Circuit Evaluation. CRYPTO (2) 2013: 71-89
$[6]$ Yupeng Zhang, Daniel Genkin, Jonathan Katz, Dimitrios Papadopoulos, Charalampos Papamanthou:A Zero-Knowledge Version of vSQL. IACR Cryptol. ePrint Arch. 2017: 1146 (2017)
$[7]$ sunblaze-ucb/Libra: Libra zero knowledge proof system (github.com)