1 Abstract

零知识证明作为隐私和可延展性的一个重要密码学工具，为了使得每个客户端都可以下载并验证一个证明，零知识证明方案必须做的很小，且验证开销也得很小

但是目前的使用方案，要么需要可信设置（预处理的zk-SNARK），要么验证所需的复杂度与待证明的关系呈线性

大多数zk-SNARK方案需要的CRS可以采用MPC协议生成，但是生成的参数局限于一个特定的关系，Groth等人提出了一个具有通用结构化引用串（URS）的方案，且该URS是可更新的，但是该URS很大，与待证明的关系（电路中的乘法门数量）呈二次关系，而且该方案中需要的群幂运算也是二次的，验证更新需要线性数量的配对运算，尽管Prover和Verifier对于给定的固定关系只需要一个特定于电路的CRS，但是从SRS导出该CRS需要利用开销很大的高斯消元过程，如果将其用于具体的环境会导致很大的计算开销（比如Zcash，其中包含$2^{17}$个乘法门，这意味着SRS会是TB级别）

因此这篇paper提出了一个新的zk-SNARK协议，称为Sonic，CRS满足通用性的同时，支持连续可更新，同时大小与待证明的关系呈线性

Sonic需要可信设置，但是SRS支持给定范围内的任意电路，且SRS大小与支持的电路呈线性关系，SRS无需针对给定电路进行专门化或预处理，这意味着其可以用于在大型分布式环境中

Sonic的验证只需要恒定数量的配对，而且所有证明元素都在同一个源群中（准确的说是只在第一源群，因为第二源群的计算开销更大），当同时验证多个证明时，只需要一次配对运算，因此证明过程的边际成本仅来自于群中少量的幂运算

Sonic的验证包括检查标量域中稀疏二元多项式的评估，本文引入了一种方法来简洁地检查这种评估（给定电路相关的预计算），从而确保zk-SNARK属性，正确性证明通过引入了一个新的置换论证和一个大乘积论证（grand-product）来实现

此外本文还引入了一种具有实践意义的技术，该技术中可以让不受信的参与方（称为助手，Helper）计算建议（Adivces），从而使得协议可以更有效的批量验证证明，若Helper收集了一些证明，则Sonic可以更高效的完成验证（在Helper技术的环境中，验证的边际成本与目前最有效的SNARK方案相当）

1.1 Related Work

表1中提供了我们讨论的所有方案的效率比较，表2中还提供了Sonic与文献中最快的zk-SNARK（Groth16）和Bulletproof的更具体的效率比较

2 DEFINITIONS FOR UPDATABLEREFERENCE STRINGS

本节重新讨论了Groth等人关于可更新SRS方案的定义，在对手可能破坏或参与生成公共引用字符串的情况下，定义了零知识证明的属性

本文第6节中的协议是交互式的（可在Random Oracle模型中转化为非交互式的），因此本文还提出了交互式协议的新定义，新定义中考虑了SRS生成的替代方法

2.1 Notation

这篇paper采用的记号和上一篇介绍URS的基本一致

  • $|x|$：若$x$为二进制串，$|x|$表示串的长度
  • $|S|$：若$S$为有限集，则$|S|$表示集合大小
  • $x\larr S$：表示从集合$S$中均匀随机选择一个元素并赋值给$x$
  • $\lambda \in \N$：安全参数，$1^\lambda$为一元表示法
  • $\epsilon$：空串
  • $PPT$：概率多项式时间
  • $DPT$：确定多项式时间
  • $y\larr A(x;r)$：算法$A$，输入$x$，随机性为$r$，输出为$y$
  • $y\larr A(x)$：省略随机性（或稍后解释随机性）

此外，我们在安全定义和证明中使用基于代码的游戏$[BR06]$，$Sec_{\mathcal A}(\lambda)$为关于安全定义$Sec$和敌手$\mathcal A$的主程序，其输出为安全游戏的输出，记输出1的概率为$Pr[Sec_{\mathcal A}(\lambda)]$

2.2 The Subvertible SRS Model

可颠复SRS（Subvertible SRS）模型$[3]$允许对手完全生成参考字符串，而可更新SRS模型允许对手通过执行某些更新来部分贡献其生成

可更新的SRS方案由两个PPT算法$Setup$和$Update$以及一个DPT算法$VerifySRS$定义，具体如下

  • $(srs,\rho)\larr Setup(1^\lambda)$：输入为安全参数，返回一个SRS串$srs$和正确性证明$\rho$
  • $(srs,\rho)\larr Update(1^\lambda,srs,(\rho_i)^n_{i=1})$：输入为安全参数、$srs$、和一系列的更新正确性证明$\rho_i$，输出更新后的SRS串$srs'$和indeed正确性证明$\rho'$
  • $b\larr VerifySRS(1^\lambda,srs,(\rho_i)^n_{i=1})$：输入为安全参数$\lambda$，公共参考串$srs$和CRS的更新证明列表$(\rho_i)^n_{i=1}$，输出为单比特$b$，$b=1$表示接受，否则表示拒绝

如果诚实的更新者总是说服诚实的Verifier，则认为可更新的SRS是完美正确的

  • Definition 3.1：若一个可更新的SRS方案满足下列等式，则称其为完美正确的

$$ Pr[(srs,\rho)\larr Setup(1^\lambda):VerifySRS(1^\lambda,srs,\rho)=1]=1 $$

此外对于所有满足$VerifySRS(1^\lambda,srs,(\rho_i)^n_{i=1})=1$的$(\lambda,srs,(\rho_i)^n_{i=1})$，有

$$ Pr[(srs',\rho_{n+1})\larr Update(1^\lambda,srs,(\rho_i)^n_{i=1}):VerifySRS(1^\lambda,srs',(\rho_i)^{n+1}_{i=1})=1]=1 $$

上述算法定义和定理和Groth那篇可更新的URS中的完美正确的定义一样，那篇paper中写的是$crs$，这里写的是$srs$，叫法不同而已，本质上是同一个东西

但是根据$[3]$中的结论，协议不能同时满足可颠复零知识和可颠复合理性，这意味着假设敌手知道生成SRS过程中采用的随机性，则意味着敌手可以同时攻破方案的零知识性和合理性，因此这里考虑两个我们希望满足的最强的属性，也即可颠覆的零知识性和可更新的知识合理性

设$R$是具有三元组$(srs,\phi,w)$的多项式时间可判定关系，其中$w$为witness，$\phi$为由$srs$定义的实例（instance），满足$(srs,\phi,w)\in R$，此时考虑一个论证$(Prove,Verify)$，若敌对的Verifier（包括可以完全生成SRS的敌手）无法区分真实协议执行和模拟执行，则称其为可颠覆零知识的

  • Definition 3.2（Subvertible Zero-Knowledge）：若一个关于关系$R$的论证系统，其对于所有PPT算法$\mathcal A$，都有一个PPT抽取器$\chi$和一个模拟器$SimProve$，在$\lambda$下该敌手的优势$|2Pr[S-ZK_{\mathcal A,\chi}(1^\lambda)]-1|=negl$，则称其为可颠覆零知识的，其中安全游戏定义如下（$H$表示Random Oracle）

这里$\mathcal O_{pf}$可以知道$b$，若$b=0$，则利用抽取器抽取的模拟陷门，并向敌手返回模拟执行的脚本，否则返回真实执行的脚本，然后敌手根据$H$和$\mathcal O_{pf}$判断$b'?=b$

为了定义更新知识的可靠性，考虑一个能够影响SRS生成的敌手（允许敌手查询Oracle，其意图为Setup（第一次更新证明）、Update（所有后续更新证明）或Final（向SRS表示它将尝试伪造证明）），该Oracle仅在下列两种情况下设置SRS

  • 所有更新证明都已验证正确
  • Oracle负责生成了至少一个更新证明

此外，paper中并没有直接使用可更新的知识可靠性，但安全游戏中的这一部分（其中$\mathcal A$和U-Os交互以创建SRS）可以用于任何加密原语，paper中将可更新性概念用于第6.2节中提出的多项式承诺方案

  • Definition 3.3（Updatable Knowledge Soundness）：若一个关于关系$R$的论证系统，其对于所有PPT算法$\mathcal A$，都有一个PPT抽取器$\chi_{\mathcal A}$，其优势$Pr[U-KSND_{\mathcal A,\chi_{\mathcal A}}(1^\lambda)]=negl$，其中安全游戏定义如下

文章中通过考虑一个交互式定义来讨论Sonic的合理性（因为本文方案中的Verifier提供了两个挑战），因此不使用特殊合理性的标准定义，而是使用证据扩展仿真的广义概念（generalized notion of witness-extended emulation）$[4]$，证据扩展仿真为Bootle等人$[2]$给出的定义，具体如下

  • Definiton 3.4：令$P$为一关于关系$R$的论证系统，若其对于任意DPT $P^*$，都存在一个期望多项式时间评估器$\mathcal E$，满足对于所有PPT算法$\mathcal A$如下，则称其可更新witness扩展仿真（updatable witness-extended emulation）

其中预言机$\mathcal E^{<P^*(srs,\phi,w),V(srs,\phi)>}$允许Rewind到某个特定的点，并从该点以新的随机性重置Verifier

文章中提到了该定义使用了与Def 3.3中的设置稍有不同的设置：与其随意与更新预言机交互来设置SRS，不如给对手一个初始设置，然后允许以一次性的方式更新它，根据Groth等人$[5,Lemma 6]$（上一篇博客有提到），这两个定义对于Sonic是等价的，所以文章中选择了更简单的那个

3 BUILDING BLOCKS

本节介绍一些预备知识

3.1 Bilinear Groups

双线性群老朋友了

算法$BilinearGen(1^\lambda)$，输入为安全参数，输出为$bp=(p,\mathbb G_1,\mathbb G_2,\mathbb G_T,e,G,H)$，其中$\mathbb G_1,\mathbb G_2,\mathbb G_T$的阶为$p$，生成元$g\in\mathbb G_1,h\in\mathbb G_2,e(g,h)\in\mathbb G_T$，映射$e:\mathbb G_1\times \mathbb G_2\rarr \mathbb G_T$满足非退化性

要求电路最大大小的界为$d^2\leq \frac{p-1}{32}$，实践中预计$d^2\ll \frac{p-1}{32}$，使用双线性群生成器，生成III型双线性群的群（此类双线性群的两个源群$\mathbb G_1,\mathbb G_2$之间不存在可有效计算的同态，是目前最有效的双线性群）

3.2 The Algebraic Group Model

Fuchsbauer等人证明Sonic在代数群模型（Algebraic Group Model，AGM）中是安全的，同时证明了Groth16方案在离散对数假设的q-type变体下是安全的

在此之前，此方案的唯一安全性证明是在通用群模型（Generic Group Model，GGM）中提供的，但是GGM范围有限，且没有捕获利用其表示的特定于群的算法（如索引演算方法），因此采用AGM，AGM是介于标准模型和GGM之间，是一种有限的计算模型，涵盖特定于群的攻击，同时允许进行有意义的安全分析

假设对手受到限制（只能输出通过将群操作应用于先前接收的群元素而获得的新的群元素），与GGM不同的是，在AGM中，人们通过简化假设来证明安全影响（和标准模型中的证明一样）

不过目前还不知道AGM如何与指数知识假设（KOE Assumption）相关联，这些假设已被用于构建标准模型中已证明安全的所有已知SNARK（事实上在更标准的可证伪假设下，SNARK无法证明安全），这些KOE假设的格式类似于AGM，即为了证明假设不正确，都需要证明存在一个敌手，该敌手可以计算特定格式的群元素，但不能提取该群元素的代数表示（不能提取群元素的某个线性组合）

非对称双线性群中的KOE假设都要求敌手计算第二源群中的元素，但是本文的方案希望避免在第二个源群中引入证明元素，因此决定使用AGM

然后介绍一下算术的概念，对于给定群元素集合$\mathcal L=\{g_1,...,g_t\}$，若算法$\mathcal A_{alg}$输出了群$\mathbb G$中的一个元素$Z$，同时还可以输出一个表示$(z_1,...,z_t)\in\mathbb F^t_p$，满足$Z=\prod^t_{i=1}g_i^{z_i}$，则称该算法是算术的

与GGM不同的是，AGM通过归约来证明安全性，为了证明本文方案在算术群模型下的安全性，我们采用q-DLOG假设，具体如下

  • Assumption 4.1（q-DLOG）：假设$\mathcal A$为算数敌手，则下列概率在$1^\lambda$下为可忽略

$$ Pr[bp\larr BilinearGen(1^\lambda);x\larr \mathbb F_p;x'\larr \mathcal A(bp,\{g^{x^i},h^{x^i}\}^q_{i=-q}:x=x']=negl $$

3.3 Structured Reference String

本文的方案需要一个具有未知量$x$和$\alpha$的结构化引用字符串，其形式如下（其中$d$足够大以支持深度为$n$的电路）

$$ \Big\{ \{g^{x^i}\} ^d_{i=-d} , \{g^{\alpha x^i}\} ^d_{i=-d,i\neq 0} , \{h^{x^i},h^{\alpha x^i}\} ^d_{i=-d} ,e(g,h^\alpha) \Big\} $$

该字符串被设计为在CRS中省略$g^\alpha$，因此可以在必要时强制Prover在$x$中证明一个承诺多项式的常数项为0

3.4 Polynomial Commitment Scheme

Sonic使用两种主要原语作为构建块：多项式承诺方案和计算正确性签名

多项式承诺方案由三个DPT协议组成

  • $F\larr Commit(bp,srs,max,f(X))$：以双线性群、SRS串、最大度和一个洛朗多项式（该多项式的度在$-d$和$max$之间），返回一个承诺值$F$
  • $(f(z),W)\larr Open(bp,srs,max,F,z,f(X))$：与$Commit$相同的输入，以及对应的承诺值$F$和域元素$z$，返回$f(z)$和一个正确性证明$W$
  • $b\larr pcV(bp,srs,max,F,z,v,W)$：输入为双线性群、SRS串、最大度、承诺值$F$、域上一个点$v$、一个点$z$和正确性证明$W$，输出单比特$b$，$b=1$表示接受，否则表示拒绝

对于多项式承诺方案有两个要求

  • 评估绑定性：给定承诺值$F$，敌手不能讲该承诺值揭示为两个不同的值$v_1\neq v_2$（或者敌手不能输出$(v_1,W_1)\neq(v_2,W_2)$，使得$(v_1,W_1),(v_2,W_2)$都可以通过$pcV$的验证）
  • 多项式有界可抽取：任意敌手可以提供一个合法的评估的揭示值时，意味着其知道度为$-d\leq i\leq max,i\neq d-max$的多项式$f(X)$的揭示值（或者说，对于任意敌手输出可通过验证的$(F,z,w,W)$都如此）

这两个性质要求对于可以更新SRS的敌手保持不变（比如在Def 3.3中可访问Oracle时也不变），在第6.2节中介绍了满足这两个性质的多项式承诺方案，定理6.3的GGM中证明了它的安全性

3.5 Signature of Correct Computation

计算正确性签名由两个DPT协议定义

  • $(s(z,y),sc)\larr scP(bp,srs,s(X,Y),(z,y))$：输入为双线性群、SRS、一个双变量多项式$s(X,Y)$和域上的两个点$z,y$，返回该多项式在该点的评估$s(z,y)$和正确性证明$sc$
  • $b\larr scV(bp,srs,s(X,Y),(z,y),s,sc)$：和$scP$类似的输入，返回单比特$b$，若$b=1$表示接受，否则拒绝

对于计算正确性方案有一个要求，也即要求其满足合理性：对于给定的$s,z,y$，当且仅当$s=s(z,y)$时敌手使得Verifier信服该计算正确性

文章中提供了两种构造在计算正确性签名的结构，一个在第8节，另一个在7节，第一个具有线性Verifier计算，但可以由不受信任的Helper聚合，以在批处理设置中实现恒定Verifier的计算，第二种方法具有恒定的Verifier计算，但具体开销较高，不过这两种结构都具有恒定的大小

4 SYSTEM OF CONSTRAINTS

Sonic表示使用Bootle等人提出的约束系统形式的电路，我们做了一些修改，以使他们的方法在我们的环境中实用

我们的约束系统有三个长度为$n$的向量$\boldsymbol a,\boldsymbol b,\boldsymbol c$，分别表示乘法约束下的左输入、右输入、输出，因此有

$$ \boldsymbol a\circ \boldsymbol b=\boldsymbol c $$

此外还有$Q$个线性约束，其中$\boldsymbol u_q,\boldsymbol v_q,\boldsymbol w_q\in \mathbb F^n$表示第$q$个线性约束向量，$k_q\in \mathbb F_p$为实例

$$ \boldsymbol a\cdot \boldsymbol u_q +\boldsymbol b\cdot \boldsymbol v_q+\boldsymbol c\cdot \boldsymbol w_q=k_q $$

举个例子，比如约束$x^2+y^2=z$可以表示为

  • $\boldsymbol a=(x,y),\boldsymbol b=(x,y),\boldsymbol c=(x^2,y^2)$
  • $\boldsymbol u_1=(1,0),\boldsymbol v_1=(-1,0),\boldsymbol w_1=(0,0),k_1=0$
  • $\boldsymbol u_1=(0,1),\boldsymbol v_1=(0,-1),\boldsymbol w_1=(0,0),k_2=0$
  • $\boldsymbol u_1=(0,0),\boldsymbol v_1=(0,0),\boldsymbol w_1=(1,1),k_3=z$

通过使用乘法约束确定乘法门，线性约束确定电路和加法门，任何算术电路都可以用约束系统表示，因此约束系统可以覆盖NP类

接下来将$n$个乘法约束进一步压缩成关于$Y$的不定多项式

$$ \sum^n_{i=1}(a_ib_i-c_i)Y^i=0 $$

为了满足下文中的论证，可以冗余的将这些约束中$Y$的指数编码为负数，也即

$$ \sum^n_{i=1}(a_ib_i-c_i)Y^{-i}=0 $$

以类似的方式压缩$Q$个线性约束，并在$Y$的指数上缩放$n$来确保两个约束线性独立

$$ \sum^Q_{q=1}(\boldsymbol a\cdot \boldsymbol u_q+\boldsymbol b\cdot \boldsymbol v_q+\boldsymbol c\cdot \boldsymbol w_q-k_q)Y^{q+n}=0 $$

其中$u_i(Y),v_i(Y),w_i(Y),k(Y)$定义如下

$$ \begin{aligned} u_i(Y)&=\sum^Q_{q=1}Y^{q+n}u_{q,i}\\ u_i(Y)&=\sum^Q_{q=1}Y^{q+n}v_{q,i}\\ w_i(Y)&=-Y^i-Y^{-i}+sum^Q_{q=1}Y^{q+n}w_{q,i}\\ k(Y)&=\sum^Q_{q=1}Y^{q+n}k_q \end{aligned} $$

将乘法和线性约束结合在一起，可以得到方程

$$ \boldsymbol a\cdot \boldsymbol u(Y)+\boldsymbol b\cdot \boldsymbol v(Y)+\boldsymbol c\cdot \boldsymbol w(Y)+\sum^n_{i=q}a_ib_i(Y^i+Y^{-i})-k(Y)=0\tag1 $$

对于给定的$(\boldsymbol a,\boldsymbol b,\boldsymbol c,k(Y))$，若其满足约束系统，则式(1)在所有点均成立，若不满足约束系统，则对于足够大的域，其中大部分点都有式(1)不成立

然后利用Bootle等人的技术将式(1)的左侧嵌入到第二个不定多项式$t(X,Y)$中的常数项，此外本文还构造了一个多项式$r(X,Y)$，满足$r(X,Y)=r(XY,1)$

$$ \begin{aligned} r(X,Y)&=\sum^n_{i=1}(a_iX^iY^i+b_iX^{-i}Y^{-i}+c_iX^{-i-n}Y^{-i-n})\\ s(X,Y)&=\sum^n_{i=1}(u_i(Y)X^{-i}+v_i(Y)X^i+w_i(Y)X^{i+n})\\ r'(X,Y)&=r(X,Y)+s(X,Y)\\ t(X,Y)&=r(X,Y)r'(X,Y)-k(Y) \end{aligned} $$

此时$t(X,Y)$中项$X^0$的系数即为式(1)等号左侧的项，Sonic通过证明$t(X,Y)$中的常数项为零来证明约束系统的满足性

5 THE BASIC SONIC PROTOCOL

Sonic是零知识的知识论证，允许Prover证明一个约束系统（第五节中的约束系统）满足一个隐藏的证据$(\boldsymbol a,\boldsymbol b,\boldsymbol c)$及其公开的实例$\boldsymbol k$，实例$\boldsymbol k$通过多项式$k(Y)$上传到约束系统中，给定一个$r(X,Y)$，若对于随机的$y\in \mathbb F_p$，$t(X,y)$的常数项为0，则该约束系统满足的概率很高

Sonic协议基于多项式承诺方案和计算正确性签名构建，如下图所示

这里讨论基本的Sonic协议，6.2节中提供了一个合适的有界可提取多项式承诺方案，并在AGM中证明了该方案的安全性，在第7节和第8节中，我们讨论了构造正确计算签名的两种不同方法，一种产生独立的zk-SNARK，另一种通过使用不受信任的Helper获得更好的实际结果

协议从使用其witness的Prover构造$r(X,Y)$开始，首先对$r(X,1)$承诺，然后令最大度为$n$，Verifier发送一个随即挑战$y$，然后Prover对$t(X,y)$承诺，根据4.4节提到的，承诺方案确保了该多项式没有常数项，然后Verifier发送第二个挑战$z$，Prover揭示其对多项式的承诺$r(z,1),r(z,y),t(z,y)$，此时Verifier可以计算$r'(z,y)$，然后检查$r(z,y)r'(z,y)-k(y)=t(z,y)$

注意到公共多项式$k(Y)$的系数由Prover声明的实例决定，若上述等式成立，则Verifier可以知道多项式的评估是由知道合法witness的Prover计算的，具体的可以看下面这个图

这里Prover的第一步会有四个随机性$c_{n+1},c_{n+2},c_{n+3},c_{n+4}\in \mathbb F_p$，这四个随机性的目的是确保（可颠覆的）零知识性，具体可以看下面定理6.1的证明

Verifier需要在域上检查二次多项式是否满足，这意味着避免了在配对的两侧都有证明元素，这有助于提高效率，同时也不会与Groth关于需要二次约束的NILPs的结果相矛盾（这么做可以在在批处理时避免了每次证明都要检查一个配对方程，而是可以每次证明中仅检查一个域方程）

Fiat-Shamir变换采用交互式论证，并用哈希函数的输出代替Verifier的挑战，上述方案在交互式环境中描述Sonic，其中所有验证器挑战都是随机域元素，在实践中可以假设应用Fiat-Shamir启发式，从而可以获得随机预言模型中的非交互零知识论证

  • Theorem 6.1：假设可以提取被破坏的参考串（Subverted Reference String）的陷门，则Sonic满足subversion零知识性
  • Theorem 6.2：当使用安全多项式承诺方案和合理性的计算正确性签名进行实例化时，Sonic具有witness扩展仿真性

定理6.1证明如下

  • Proof（Thm 6.1）：证明该定理不仅需要证明可以计算陷门的抽取器$\chi_{\mathcal A}$存在，还需要证明模拟器算法$SimProve$在给定模拟陷门时产生的分布与真实协议不可区分，这里对抽取器的存在性不做证明（具体可以看上一篇博客的Lemma 4）

对于给定的模拟陷门$g^\alpha$，模拟器选择两个长度为$n$的随机向量$\boldsymbol a,\boldsymbol b\in\mathbb F_p$，并计算$\boldsymbol c=\boldsymbol a\cdot \boldsymbol b$，然后按照第五节中计算$r(X,Y),r'(X,Y),t(X,Y)$，并按照图2中的Prover执行协议即可

但是由于模拟器不知道witness，因此计算出来的$t(X,Y)$极大概率在常数项（也就是$X^0$这一项的系数）不为零，但是Prover和模拟器都评估了$g^{r(x,1)},r(z,1),r(zy,1)$这三个点，由于Prover在第一步中加入了四个随机性$c_{n+1},c_{n+2},c_{n+3},c_{n+4}\in \mathbb F_p$，分别对应于$r(X,Y)$中指数为$-2n-1,-2n-2,-2n-3,-2n-4$的项，对于得到少于三个评估值的Verifier而言，模拟器计算的随机多项式与Prover的真实多项式不可区分，而图2描述的协议中，除了多项式$r(X,Y)$外，其他组成部分要么是由Prover（或模拟器）之前的计算唯一确定的，要么是独立于witness的（且由Prover和模拟器采用相同的方式生成），因此该协议满足可颠覆的零知识性

定理6.2证明如下

  • Proof（Thm 6.2）：计算正确性签名的合理性意味着有$s=s(z,y)$

而其多项式有界可抽取性意味着对于关系$R$，其包含了多项式

$$ r(X,1)=\sum^n_{i=-d,i\neq-d+n}r_iX^i $$

而$T$包含多项式

$$ \tau(X)=\sum^d_{i=-d,i\neq0}\tau_iX^i $$

注意到本文的多项式约束系统中，有$3n<d$（否则无法承诺$t(X,Y)$），因此$r(X,Y)$没有$-d+n$的项

由于方案满足评估绑定性，因此必然有$a=r(z,1),b=r(zy,1)=r(z,y)$，之后Verifier可以检查$t=a(b+s)-k(y)=\tau(z)$

假设Verifier验证等式对于$n+Q+1$个不同的随即挑战$y\in\mathbb F_p$均成立，因为$n+Q+1$阶非零多项式不会有$n+Q$个根，因此$r(X)(r(X,Y)+s(X,Y))-k(Y)$不可能有常数项，从而$r(X,y)$一定是一个合法的witness

5.1 Efficiency

如图2所示，Prover使用两个多项式承诺，这两个多项式承诺在三个点揭示，此外它还使用一个计算正确性签名

方案背后的理念如下：给定两个多项式承诺$F_1,F_2$，若Verifier选择随机值$r_1,r_2$，则当且仅当敌手可以以高概率揭示$F_1,F_2$时，其才可以揭示$F_1^{r_1},F_2^{r_2}$，多项式$k(Y)$为稀疏多项式，其由instance确定，且需要$O(l)$次域运算来计算该多项式

5.2 Polynomial Commitment Scheme

Sonic使用多项式承诺方案，这是Kate等人的多项式承诺方案的变体，该方案对任意大小多项式都具有常数大小的证明

本文要求该方案具有评估绑定性，也即给定承诺值$F$，敌手不能将$F$揭示为两个不同的评估值$v_1\neq v_2$，，该证明的评估绑定性直接来自于Kate等人的工作，其可以归约至q-SDH假设

此外还要求方案是有界多项式可抽取的，也即可以揭示承诺值$F$的算数敌手都知道一个多项式$f(X)$的揭示，该多项式的幂为$-d\leq i\leq max,i\neq 0$

Kate等人证明了他们方案为强正确性的，也即若敌手知道具有多项式度的$f(X)$的揭示，则该$f(X)$的度以$d$为界，从这个意义上说，Kate等人的方案隐式依赖于知识假设，因为无法保证能够开启承诺的对手知道承诺中的多项式

本文的证明采用了$f(X)-f(z)$可被$(X-z)$整除的事实（洛朗多项式上该结论也成立），也即

$$ \begin{aligned} f(X)-f(z)&=\sum^d_{-d}a_iX^i-a_iz^i\\ &=\sum^d_{i=1}a_i(X-z)(X^{i-1}+zX^{i-2}+...+z^{i-1})+0\cdot a_0\\ &=\sum^{-d}_{i=-1}a_i(X-z)(-z^{-1}X^{-i}-z^{-2}X^{-i+1}-...-z^{-i}X^{-1}) \end{aligned} $$

  • Theorem 6.3：算术群模型下（AGM），图三中描述的多项式承诺方案在2d-DLOG假设下具有评估绑定性和多项式有界可抽取性

具体证明可看原文$[1]$，有点长

6 SUCCINCT SIGNATURES OF CORRECTCOMPUTATION

回忆一下第5节中提到的，Sonic利用计算正确性签名来确保对于一个已知的多项式$s(X,Y)$，计算元素$s$与$s(z,y)$相等，也即

$$ s(X,Y)=\sum^d_{i,j=-d}s_{i,j}X^iY^j $$

方案需要满足合理性，也即除非$s=s(z,y)$，否则任何敌手都无法说服Verifier $scV$，且该属性即便在可更新SRS的敌手下也成立

本文提供了计算正确性签名的两种实现方法，第一种本节描述，由Prover计算，在大小和Verifier计算方面是简洁的，第二个方案通过考虑不受信任的Helper来提高实际效率，第八节描述第二个方案

利用$s(X,Y)$的结构是为了利用置换论证来提供正确性计算，因为置换论证本身具有一个大内积论证作为基础组件

首先令$s(X,Y)$限制为$M$个多项式之和的约束系统，其中对于给定的项式置换$\sigma_j$和系数$\psi_{j,i}\in \mathbb F$，第$j$个多项式如下

$$ \Psi_j(X,Y)=\sum^n_{i=1}\psi_{j,\sigma_{j,i}}X^iY^{\sigma_{j,i}} $$

通过引入额外的乘法约束来替换不符合此格式的任何线性约束，我们可以将第5节中的任何约束系统强制转换为正确的形式

为了进一步扩展，我们的约束系统由三个长度为$n$的向量$\boldsymbol u_q,\boldsymbol v_q,\boldsymbol w_q$决定，这些向量通常是稀疏的，为了以期望的形式表示$\Psi_j$，我们要求$s(X,Y)$中所有$Y$的幂出现的次数不超过$M$次，这意味着对于所有的$1\leq i\leq n$，只有$\boldsymbol u_q,\boldsymbol v_q,\boldsymbol w_q$这三个值可以为非零值，若$\boldsymbol u_q$太密集，可以将原始约束拆分为两个或更多的约束，令$\sum^{n-l}_{i=1}a_iu_{q,i}-a_{n+1}=0$和$k_q=a_{n+1}+\sum^n_{i=n-l+1}a_iu_{q,i}+\boldsymbol b\cdot \boldsymbol v_q+\boldsymbol c\cdot \boldsymbol w_q$

不过这么做会将$\boldsymbol a$的长度扩展一倍，因此还必须将$\boldsymbol b$和$\boldsymbol c$的长度也扩展一倍

附加乘法约束的精确数量取决于加法约束的数量（本质上，这意味着如果算术电路中存在超过$2n$个加法约束，则这些约束不再是自由的），在实践中，我们发现当$M=3$时，SHA256电路的乘法约束数的增加约为3倍

计算正确性签名采用多项式置换参数，其本身使用一个大乘积论证，置换论证允许我们验证每个包含$\Psi_j(X,y)$的多项式承诺，此后可以在点$z$揭示该承诺，以验证$\Psi_j(z,y)$计算是否正确

该论证的目的是将Verifier的计算转移到Prover上，使用附录C中所述的批处理技术后，我们得到了大约1kB的验证大小

置换Verifier本身不采用置换，而是导出一个参考串$srs_\Psi$，该参考串可使用$\mathbb G_1$中大小为$n$的四次幂运算从全局SRS和置换$\Psi$中生成，当协议在多个实例上运行时，导出引用字符串的计算开销会均摊至这些实例

6.1 Polynomial Permutation Argument

多项式置换参数由三个DPT协议定义

  • $srs_\Psi \larr Derive(bp,srs,\Psi(X,Y))$：导出参考串$srs_\Psi$算法
  • $(\psi,perm)\larr permP(srs_\Psi,y,z,\Psi(X,Y))$：输入域元素$y,z$，输出一个置换$\psi=\Psi(z,y)$和证明$perm$
  • $0/1\larr permV(srs_\Psi,y,z,(\psi,perm))$：验证置换是否正确

要求上述方案满足合理性，也即敌手只能使得Verifier相信$\psi=\Psi(z,y)$和之前一样，要求即使在面对可更新SRS的敌手时也能保持这种能力

具体的多项式置换论证在附录A中给出

  • Theorem 7.1：在使用满足合理性的置换论证时，图5中的计算签名方案满足合理性

具体证明可看原文$[1]$

6.2 Grand-Product Argument

多项式置换变元的主要组成部分之一是一个大乘积论证，大乘积论证由两个DPT协议定义

  • $gprod\larr gprodP(bp,srs,A,B,a(X),b(X))$：其中$A,B$为两个多项式承诺，$a(X),b(X)$为对应的承诺揭示，满足$\prod_ia_i=\prod_i b_i$
  • $0/1\larr permV(bp,srs,A,B,gprod)$：验证乘积是否正确

要求方案满足知识合理性，也即当且仅当敌手知道$A,B$的揭示具有相同的grand-product时（$\prod_ia_i=\prod_i b_i$）其才可以使Verifier相信（同样要求这一点在对抗能够更新SRS的对手时保持不变）

7 SIGNATURES OF CORRECTCOMPUTATION WITH EFFICIENT HELPED VERIFICATION

回想一下，Sonic使用正确计算的签名来确保元素s等于已知多项式的$s(z,y)$，满足

$$ s(X,Y)=\sum^d_{i,j=-d}s_{i,j}X^iY^j $$

第7节中描述了一个由Prover直接计算的正确计算签名，该签名在大小和Verifier计算上具有简洁性，当然也可以在某些设置中，利用不受信任的Helper来提高实际效率

本节介绍在Helper设置中，证明大小和Prover计算效率可以显著提高，也即使用Helper来同时聚合多个正确计算的签名，Helper提供的证明具有简洁性，任何人都可以作为Helper（Helper不需要来自Prover的任何秘密信息，在区块链中，Helper可以是矿工）

表3给出了效率概述

图7给出了在help下的计算正确性签名，其中Helper由$hscP$表示，Verifieir表示为$hscV$

简单来说就是，对于每个$y_j$，Helper计算其承诺值$s(X,y_j)$，然后Verifier提供随即挑战$u$，Helper计算承诺值$s(u,X)$，然后在点$u$处揭示承诺$s(X,y_j)$，同时在所有的$y_j$处揭示承诺$s(u,X)$，并验证这两个值相等，之后Verifier提供随即挑战$v$，Helper在点$v$处揭示承诺$s(u,X)$，然后Verifier计算$s(u,v)$并验证Helper计算正确

  • Theorem 8.1：当使用安全多项式承诺方案实例化时，图7中计算正确性的聚合签名是可靠的

证明看原文$[1]$

总结

在上一篇可更新的URS上进一步优化得到的方案

Groth等人的可更新的URS方案种URS的大小和最大电路大小呈平方关系，这意味着如果需要证明一个很大的电路的话，Groth等人的方案会得到一个极大的URS，从中再导出的CRS也不会太小

本篇paper主要关注减少URS的大小，通过利用洛朗多项式和多项式承诺等方案，将URS的大小减少至电路大小的线性阶

不过后面的计算正确性签名、乘积论证和置换论证没看懂，需要一点时间积累和消化，或许和Groth16一样，过段时间再回来看就懂了

References

$[1]$ Mary Maller, Sean Bowe, Markulf Kohlweiss, Sarah Meiklejohn:Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updatable Structured Reference Strings. CCS 2019: 2111-2128

$[2]$ J. Bootle, A. Cerulli, P. Chaidos, J. Groth, and C. Petit. Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting. In EUROCRYPT,2016.

$[3]$ M. Bellare, G. Fuchsbauer, and A. Scafuro. NIZKs with an untrusted CRS: security in the face of parameter subversion. In ASIACRYPT, pages 777–804, 2016.

$[4]$ Y. Lindell. Parallel coin-tossing and constant-round secure two-party computa-tion. J. Cryptology, 16(3):143–184, 2003.

$[5]$ Jens Groth, Markulf Kohlweiss, Mary Maller, Sarah Meik­le­john, Ian Miers:Up­dat­a­ble and Uni­ver­sal Com­mon Ref­er­ence Strings with Ap­pli­ca­tions to zk-SNARKs. CRYPTO 33 2018: 698-728