4 Zero Knowledge Argument Protocols

4.1 Zero Knowledge Sumcheck

首先介绍如何为和校验协议添加零知识的性质

由于GKR协议中，双方需要对多项式在某些随机点上进行求值，很有可能泄露原始多项式的信息

$[4]$中给出了一种方法：通过添加一个随机多项式来隐藏原始多项式，从而为和校验协议添加零知识的性质

具体而言，对于原始多项式的声明$H=\sum_{x_i}f(x_1,\dots,x_l)$，Prover构造一个与原始多项式$f$具有相同变量数量的随机多项式$g$，声明并向Verifier发送$G=\sum_{x_i}g(x_1,\dots,x_l)$

之后Verifier选择随机性$\rho$，双方基于下列新的和校验多项式和声明，执行和校验协议

$$ H+\rho G=\sum_{x_1,\dots,x_l\in\{0,1\}}\Big(f(x_1,\dots,x_l)+\rho\cdot g(x_1,\dots,x_l)\Big) $$

在原始和校验协议的最后一轮，Prover需要在$(r_1,\dots,r_l)$处揭示$g$的承诺，Verifier利用承诺揭示和最后一条消息，计算$f(r_1,\dots,r_l)$，并与$f$的预言机访问进行对比

此时只要$g$的承诺与揭示为零知识的，则上述协议为零知识的，因为$f$的所有系数均被随机多项式$g$隐藏了，所以满足零知识性，而协议是对$f$和$g$的一个随机线性组合进行和校验协议，因此不会改变协议的合理性

但是这里存在一个效率问题：因为$g$和$f$一样大，且在一个随机点揭示$g$的开销也很大，这会导致Prover的开销降低至指数阶

本文给出了一个新的方法，利用一个小的多项式对$f$进行隐藏，来实现协议的零知识性

具体而言，令掩码多项式$g(x_1,\dots,x_l)=a_0+g_1(x_1)+\dots+g_l(x_l)$，其中$g_i(x_i)$为$d$阶单变量多项式（阶数与$f$相同），如下

$$ g_i(x_i)=\sum _{j=1}^d a_{i,j}\cdot x_i^j $$

不难看出$g$的大小仅为$O(d\cdot l)$，要比$f$的$O(2^l)$小不少，利用这个改进的点，我们可以得到优化后的和校验协议，如下图所示

协议的完备性和合理性不难理解，这里看一下协议的零知识性，看一下如何构建模拟器来模拟Verifier的脚本

首先模拟器$\mathcal S$选择一个随机多项式$g^*(x_1,\dots,x_l)=a^8_0+g^*_1(x_1)+g^*_2(x_2)+\dots+g^*_l(x_l)$，其中$g^*_i(x_i)$如下

$$ g^*_i(x_i)=\sum _{j=1}^d a^*_{i,j}\cdot x_i^j $$

然后$\mathcal S$向Verifier发送$H,G^*,\mathbf{com}_{g^*}=\mathbf{Commit}(g^*)$，Verifier选择随机性$\rho\neq 0$并返回给$\mathcal S$

$$ G^*=\sum_{x_1,\dots,x_l\in\{0,1\}}g^*(x_1,\dots,x_l) $$

之后$\mathcal S$选择一个$d$阶多项式$f^*$，满足

$$ H=\sum_{x_1,\dots,x_l\in\{0,1\}}f^*(x_1,\dots,x_l) $$

之后双方基于下列多项式进行和校验协议

$$ H+\rho G^*=\sum_{x_1,\dots,x_l\in\{0,1\}}\Big(f^*(x_1,\dots,x_l)+\rho\cdot g^*(x_1,\dots,x_l)\Big) $$

记$r$为Verifier在协议中选择的随机性向量，$\mathcal S$在$r$处向Verifier揭示$g^*$的承诺$(g^*(r),\pi)\larr \mathbf{Open}(g^*,r)$

由于$g,g^*$都是随机选择的多项式，且zkVPD满足零知识性，因此Construction 1协议的真实协议执行中的步骤1与步骤4和模拟器的输出不可区分，这里还需要证明步骤3也与真实协议执行不可区分

注意到在协议的第$i$轮中，Verifier回收到一个单变量多项式$h_i(x_i)$（多项式$h$满足$h=f+\rho\cdot g$）

$$ h_i(x_i)=\sum_{b_{i+1},\dots,b_l\in\{0,1\}}h(r_1,\dots,r_{i-1},x_i,b_{i+1},\dots,b_l) $$

这里由于多项式$h$的阶为$d$，因此$h$中包含$d+1$个约束，Prover通过向Verifier发送的$h_i(0),h_i(1),\dots,h_i(d)$可以唯一确定多项式$h$

此外，若Prover为诚实的，则根据和校验协议，有$h_i(0)+h_i(1)=h_{i-1}(r_{i-1})$，因此$l$轮协议结束后，真实协议执行和模拟执行的Verifier都会得到总计$l(d+1)-(l-1)=ld+1$个独立的约束条件，分别对应于真实协议执行和模拟执行的多项式$h,h^*$

由于$h,h^*$均被掩码多项式$g,g^*$进行隐藏，因此这两个多项式的随机线性组合具有相同的分布，因此协议中的步骤3也是与真实协议执行不可区分的

综上，零知识性证毕

4.2 Zero knowledge GKR

基于上面的零知识和校验协议，来分析一下如何为GKR协议也实现零知识性

尽管上一节为和校验协议添加了零知识的性质，但是注意到在协议的阶数，Verifier需要在一个随机点处请求预言机对多项式求值，由于求值过程需要计算式1，这回导致泄露了$\tilde V_i$在两个点处的求值结果：$\tilde V_i(u),\tilde V_i(v)$

为了防止此类求值结果泄露多项式的信息，$[4]$给出的解决办法是将多线性扩展$\tilde V_i$进行低阶扩展$\dot V_i(z)$，如下

$$ \dot V_i(z)=\tilde V_i(z)+Z_i(z)\cdot \textstyle\sum_{w\in\{0,1\}^\lambda}R_i(z,w) \tag 2 $$

其中$Z(z)=\prod^{s_i}_{i=1}z_i\cdot (1-z_i)$，对于任意的$z\in \{0,1\}^{s_i}$，均有$Z(z)=0$，$R(z,w)$为一个随机的低阶多项式，$\lambda$表示安全参数

此时原来的式1就变成了下面这个多项式

$$ \begin{aligned} \dot V_i(g)=&\textstyle\sum_{x,y\in\{0,1\}^{s_{i+1}}}\tilde{mult}_{i+1}(g,x,y)\cdot (\dot V_{i+1}(x)\cdot \dot V_{i+1}(y))\\ &+\tilde{add}_{i+1}(g,x,y)\cdot (\dot V_{i+1}(x)+\dot V_{i+1}(y))+Z_i(g)\cdot \textstyle\sum_{w\in\{0,1\}^\lambda}R_i(g,w)\\ =&\textstyle\sum_{x,y\in\{0,1\}^{s_{i+1}},w\in\{0,1\}^\lambda}\big(I(\vec 0,w)\cdot \tilde{mult}_{i+1}(g,x,y)\cdot(\dot V_{i+1}(x)\cdot \dot V_{i+1}(y))\\ &+\tilde{add}_{i+1}(g,x,y)\cdot (\dot V_{i+1}(x)+\dot V_{i+1}(y))+I((x,y),\vec 0)\cdot Z_i(g)\cdot R_i(g,w)\big) \end{aligned}\tag 3 $$

其中$I$用于表示两个多项式是否相等，也即当且仅当$\vec a=\vec b$时，有$I(\vec a,\vec b)=0$

这里可以观察一下这个式子，由于$Z_i(z)$在任意的$z\in \{0,1\}^{s_i}$上取值为0，因此第一个等号中，对于所有的$\{0,1\}^{s_i}$，均有$\dot V_i=\tilde V_i$

第二个等号只是做了一些变换，使得$\dot V_i$的掩码为“和”的形式，这样就可以将其用于和校验中

此时对式3的第一个等号执行零知识和校验协议，根据式2的低阶扩展结果，$V_{i+1}$被$Z_{i+1}(z)\cdot \sum_wR_{i+1}(z,w)$隐藏，因此协议结束时Verifier收到的两个多项式求值$\dot V_{i+1}(u),\dot V_{i+1}(v)$不会泄露$V_{i+1}$的信息，这样一来就解决了协议不满足零知识性的问题

但是新的问题又来了，掩码多项式$R_i$非常的大，尤其是安全参数$\lambda$很大的时候，Prover在一个随机点揭示$R_i$的开销为指数阶的（无论其使用PCP还是zkVPD的方式，都是指数阶）

解决这个问题的方式是将$R_i$的规模缩小，使其只包含两个变量的阶为2，协议的第$i-1$轮种，Verifier收到$\dot V_i(u),\dot V_i(v)$，第$i$轮种，Verifier在点$c$处揭示$R_i(u,c),R_i(v,c)$，如果采用zkVPD对$R_i$进行承诺和揭示的华， 可以确保这四个求值结果线性独立

之后将式2的低阶多项式修改为$Z_i(z)\cdot \sum_{w\in\{0,1\}}R_i(z_1,w)$即可，这里$R_i$只包含两个变量：$z_1$和$w\in \{0,1\}$，两个变量的阶均为2

综上，修改后的协议如下图所示

上述协议完备性基于零知识和校验协议的完备性，合理性基于具有低阶扩展的GKR协议的合理性，零知识性可以看原文

4.3 Zero knowledge VPD

看一下如何实现零知识的VPD协议

对于每个中间层$i$，利用前面提到的$g_i,R_i$来实现多项式的隐藏，对于输入层的zkVPD，这里构造一个基于[6]中的zkVPD的协议来处理输入层

回顾一下GKR协议的结尾，Verifier可以得到$\dot V_d(z)$在点$z=u^{(d)},z=v^{(d)}$处的求值结果，但是本文的零知识协议中（下面的4.4节介绍），Prover需要利用zkVPD对$\dot V_d(z)$进行承诺，然后再在这两个点揭示$\dot V_d(z)$

注意到$\dot V_d(z)$是输入的低阶扩展，该多项式可以被分解为两个部分：多线性多项式$\tilde V_d(z)$的求和，以及$Z_d(z)\cdot \sum_{w\in\{0,1\}}R_d(z_1,w)$，由于$Z_d(u^{(d)}),Z_d(v^{(d)})$可以由Verifier计算，因此Prover只需要对$\tilde V_d(z),\sum_{w\in\{0,1\}}R_d(z_1,w)$两个多项式进行承诺，后续在对应点处揭示即可

另一个对电路的优化方式为：注意到Construction 2中，$R_d(z_1,w)$不需要在这两个点揭示，因此可以直接令$\dot V_d(z)=\tilde V_d(z)+Z_d(z)\cdot R_d(z_1)$即可

完整协议如下图所示

4.4 Putting Everything Together

最后把之前的所有东西捏起来，得到本文的方案

和之前的其他方案类似，对于由$x,w$定义的读哦像是，给定随机点上多项式求值的预言机方案，可以证明其电路的可满足性，本文的方案采用zkVPD来实例化预言机

相关的电路可满足关系为$\mathcal R$，如下

$$ \mathcal R=\{(C,x;w):C\in \mathcal C_{\mathbb F}\wedge |x|+|w|\leq n\wedge C(x;w)=1\} $$

零知识论证如下图所示

协议的完备性和合理性均基于GKR协议和zkVPD

对于零知识性而言，模拟器$\mathcal S$调用GKR协议的模拟器$\mathcal S_{GKR}$来处理输入层，此时模拟器需要在知道求值点$u^{(d)},v^{(d)}$之前，对$\dot V^*_d$进行承诺

如果$\mathcal S$诚实的揭示承诺，则求值结果很大概率与GKR协议的最后一条消息（第$d-1$层的和校验协议的最后一条消息）不同，从而Verifier可以将其与真是协议执行区分开来

这里的解决办法是利用zkVPD的模拟器$\mathcal S_{VPD}$，对于$KeyGen$算法中的陷门$\mathbf {trap}$，VPD模拟器$\mathcal S_{VPD}$可以以零知识的方式将承诺值在任意一个点进行揭示，这意味着可以使得揭示的值与GKR协议的最后一条消息对应，从而完成$\mathcal S$的模拟过程

协议复杂度分析看原文吧

5 Implementation and Evaluation

$[7]$是本文的cpp实现，感兴趣可以看一下

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)