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)