简洁非交互零知识证明综述

朱旭东， 张心轩， 邓 燚*

(1.中国科学院 信息工程研究所/信息安全国家重点实验室， 北京 100093； 2.中国科学院大学 网络空间安全学院， 北京 100049)

1 研究背景

Goldwasser等[1]给出了零知识证明(Zero-Knowledge Proofs, ZKP)的概念，零知识证明的出现在密码学上有着重要的意义，它给人们的现实生活也带来了巨大的冲击。零知识证明是一个强大的密码学工具，能让证明者向某个验证者证明某个断言是正确的而不透露其它任何信息，它需要满足3个性质：①完整性：如果证明者做出正确的证明，那么验证者一定会通过验证；②可靠性：如果证明者伪造一个虚假的证明，那么验证者除了可忽略的概率外会拒绝；③零知识性：验证者只能知道断言是正确的而不知道任何其他知识。

随着对零知识协议研究的深入,以及对其应用要求的增加，大家并不满足于需要双方进行交互的零知识证明系统。Blum等[2]在公共参考串模型下(Common Reference String model，CRS model)将零知识的概念延伸至非交互零知识证明的概念(Non-interactive Zero-knowledge proofs, NIZK proofs)，在这个系统里，证明者可以只发一条消息给验证者，然后验证者验证即可。NIZK在包括数字签名、选择密文攻击(Chosen-ciphertext Attack， CCA)和安全的公钥加密等非交互密码学方案中都十分有用。

在大数据时代的今天，互联网上的数据量日益增大，零知识证明作为一个被广泛应用的工具，大家对其通信复杂度和效率的要求也越发严格。于是简洁非交互零知识的知识论证(Zero-knowledge Succinct Non-interactive Arguments of Knowledge, zk-SNARKs)概念也被提出并被广泛研究，事实上zk-SNARKs是如今区块链等密码学应用领域上重要的一环。

早期的zk-SNARKs都是在CRS模型下讨论的，虽然目前已经可以在这种模型下构造十分高效的zk-SNARKs方案，但该模型需要依赖受信任的初始设置(Setup)。从现实的角度来看，实现可信的初始设置是很困难的，因为实现过程中往往会产生有害信息(toxic waste)，万一被泄漏，敌手则可以利用这些有害信息生成能够通过验证的伪造证明。此外，这些zk-SNARK的初始设置是特定电路的一次性受信任的初始设置，即由该初始设置产生的CRS只能针对特定电路，而不能针对任意的电路。为了避开这些问题出现了以下一系列的解决方法和新的研究路线。

1.1 通用可更新(Universal updatable)的zk-SNARKs

在这个模型下CRS可以被任意更新参与方非交互的更新，这个更新是可验证的，并且只要在所有参与方中至少有一个是诚实做的，那么模拟的陷门就不会被泄露，从而达到了取代可信第三方的目的。另外，这种可更新的CRS一般都是通用的(Universal)，也就是说它们的生成不依赖于具体电路，而是直接被用于针对任意电路的零知识证明之中。

1.2 透明的(Transparent)zk-SNARKs

这个模型主要研究CRS生成时无需可信第三方的SNARK协议。绝大多数透明的zk-SNARKs协议，其CRS是无结构的均匀随机串，有时候，也称这种使用无结构的均匀随机串的CRS模型为均匀随机串模型(Uniform Random String model, URS)。透明的zk-SNARKs的安全性通常是在随机预言机模型(Random Oracle Model)下证明的。

1.3 纯公钥模型(Bare Public Key model，BPK)下的zk-SNARKs

在该模型下的zk-SNARKs协议分为2个阶段，第一个阶段不同于CRS模型下由可信第三方来生成CRS，该模型下是由验证者生成CRS；第二个阶段再由证明者与验证者在这个CRS下执行零知识证明协议(当然为了保证零知识性质，目前的方案都需要证明者先对这个CRS进行一些验证)，因此，该模型不需要可信第三方，要比CRS模型更弱。

1.4 模拟多方安全计算(MPC-in-the-head)的zk-SNARKs

在该模型下，证明者在一些(至少3个)虚拟的服务器之间模拟一个MPC协议，然后将他们所看见的副本和每个服务器的中间状态承诺起来。此后，验证者可以让证明者打开这些承诺的一个子集来高效验证是否一致。由MPC的私密性可以保证证明者打开给验证者看的内容不会泄露额外信息，由MPC的正确性也可以保证证明者无法欺骗验证者。

2 公共参考串模型下的zk-SNARKs

零知识证明[1]，特别是非交互零知识证明[2]在密码学理论和实际密码学应用中都扮演着重要的角色。而在诸如文献[3-7]等大量的研究下，基于pairing的简洁非交互零知识的论证(Zero-knowledge Succinct Non-interactive Arguments of Knowledge, zk-SNARKs)出现在人们的视野中，并被不断发展。相比于非交互的零知识证明，zk-SNARKs最大的特点就是简洁性，事实上它甚至可以让证明者在证明长度仅为常数个群元素的情况下证明任意大小电路的可满足性。此外，为了满足不断提高的应用需求，如今许多的zk-SNARKs方案在计算效率方面也被设计得十分高效。

关于为什么CRS模型会被提出的背景，Goldreich等[8]提出在标准模型下，对于足够困难的语言想要构造一轮的协议来抵抗带辅助输入的证明者的攻击是不可能的，因此，需要考虑一个更强的模型——CRS模型。

另外，知识的论证(Argument of Knowledge/ Knowledge Soundness)是对合理性(Soundness)的强化定义，在该定义下，一个高效证明者争对某个断言生成的证明通过验证，不仅能说明该断言对应的证据的存在性，并且这个证据还能被高效地抽取出来。许多证明系统都满足这个性质，这个性质对于简洁论证系统的应用也有重要的影响。

概率可检验证明(Probabilistically Checkable Proofs, PCP)定理[9-12]为NP语言提供了一个新的、对证明系统产生深远影响的特征，它说明了NP断言拥有能在正常证明尺寸和对数多项式时间内被验证的概率可检验证明。Kilian[3]将这种新的NP特征应用于密码场景，证明可以对NP语言用PCP去构造交互论证。而通信量大小是零知识证明的一个重要表现参数，Klilian给出了第一个亚线性通信规模和验证时间的零知识证明，该方案需要发送的比特数少于需要被证明的断言，这样的论证系统被称为简洁的(Succinct)论证系统。

需要注意的是Klilian的协议需要4轮交互，而对于应用而言非交互显然更加有意义。因此，朝着这个方向尝试，Micali[4]通过让证明者在这些论证中使用密码学函数计算验证者的挑战，而在RO模型下构造出了一个公开可验证的简洁非交互论证方案。正如Kilian[13]所述，这种Fiat-Shamir启发式[14]可以把公开掷币(Public Coin)的零知识论证变成亚线性规模的NIZK方案。此外，还有一些早期工作，如文献[15-18]研究了怎么利用可抽取的抗碰撞哈希(Extractable Collision-resistant Hashing)[19-21]来去除Kilian的基于PCP的协议的交互，或者利用有一个可抽取同态性质的全同态加密(Fully-homomorphic Encryption with An Extractable Homomorphism Property)[22]去构造基于MIP(Multi-prover Interactive Proofs)的SNARKs。

经典的构造简洁论证的方法是首先给出一个信息论构造，然后在对证明者有某种约束的模型下利用一些概率检查(Probabilistic Checking)去验证计算(例如前面提到过的PCP模型[3-4,18-21,23]，或者其它的概率检查的模型[22,24-29])，最后再利用密码学工具将信息论构造编译成论证系统(此时对于证明者，除了要求其算法为高效的，并无其它约束)。然而如今的构造都偏离了这个方法而基于新的方法，新的方法有很多吸引人的好处，例如，公开可验证与证明只包含常数个群元素等。

Groth等[30-33]提出了基于pairing的NIZK证明，这也导致了标准假设下的第一个线性通信规模的证明诞生。Groth[5]结合这些技术和他此前提出的交互零知识论证的想法[34],在指数知识假设(Knowledge of Exponent Assumptions， KEA)[35-37]和双线性群下给出了第一个证明只包含常数个群元素的NIZK论证。Groth的常数规模的NIZK论证基于一系列多项式等式，并采用pairing的方式去高效地验证这些等式。Lipmaa[38]在同样的群和假设下使用了一个基于进展集合(progression sets)的新构造进一步压缩CRS的长度。文献[5, 38]都用到了不可证伪的假设，事实上Gentry等[39]给出了一个负面的结论——不可证伪的假设(包括知识假设和一些强的模型)是证明SNARK的知识的论证所必须的。

不同于基于之前所提到的概率检查的方法，Gennaro等[6]首先通过电路的编码和拉格朗日插值将电路可满足性问题规约到了更容易处理的代数可满足问题上，从而跳过了经典方法中的概率检查的步骤而直接构造具体的密码学工具来验证代数可满足问题，这种方式是对信息论材料和密码学材料的进一步区分。他们给出了2种新的代数可满足问题，一个是与证明布尔电路可满足性相对应的QSP(Quadratic Span Programs)，另一个是与证明算术电路可满足性相对应的QAP(Quadratic Arithmetic Programs)，并给出了一个CRS长度与断言和证据大小呈比例的基于pairing的zk-SNARK，这样构造出的SNARK拥有更加高效的验证时间和更短的证明长度。Lipmma[40]结合纠错码提出了更加高效的QSP。Danezis等[41]将 quadratic span programs 重新定义为了square span programs，并给出了一个针对布尔电路的包含4个群元素的zk-SNARK。 Bitansky等[42]给出了基于对域元素做线性编码的SNARKs的抽象模型——LIPs(Linear-interactive Proofs)，这个模型抓住了证明者被限制为只能使用线性操作计算消息的特征,此外,该文章给出了一个一般的转化——从2轮LIP结合基于pairing的技术转化为公开可验证的SNARK或者结合同态加密技术得到指定验证者的SNARK。在LIP的框架下，Groth[7]提出了迄今为止在验证时间和证明长度(证明只包含3个群元素)上表现最优的zk-SNARKs，也因此已被广泛用于电子货币等互联网领域中。

这些传统的zk-SNARKs方案虽然已经在通信量和效率上有了不错的结果，但是其还有2个比较大的缺陷：①其CRS生成都需要依赖可信第三方，因而在中心化系统中难以实现；②其大部分只能针对特定线路，即对每个不同线路的证明都需要重新生成一次CRS，这使得其在应用上受到限制。

当然，也存在CRS模型下的针对通用电路的zk-SNARKs。例如Libra[43]也需要CRS，但是其CRS是通用的，与具体电路逻辑无关而只与电路的输入长度有关。该方案也是第一个拥有最优证明者时间(证明时间为O(C)且与电路类型无关)和简洁证明长度/验证时间的零知识证明系统。特别地，如果令C是电路大小，d是电路深度，那么Libra的证明时间为O(C)，证明长度和验证时间都是O(dlogC)。该方案的核心技术有2个，一个是线性证明者时间的GKR协议(Goldwasser, Kalai和Rothblum的交互证明协议)；另一个是高效的将GKR协议转化为零知识协议的方法。

3 通用可更新的zk-SNARKs

为了取代CRS模型，Groth等[44]定义了可更新模型(Updatable Model)，这个模型是完全的CRS模型和完全的BPK模型的折衷模型，在这个模型下，CRS可以被任意更新参与方非交互地更新，这个更新是可验证的，并且只要在所有参与方中至少有一个是诚实的，那么模拟的陷门(Trapdoor)就不会被泄露，从而达到了取代可信第三方的目的。另外，一般这种可更新的CRS都是通用的(universal)，也就是说它们的生成不依赖于具体电路，因此，可以被用于对任意电路的零知识证明。

算术电路的可满足性问题可以被归约到一系列有限域上的二次和仿射约束问题。二次约束是通用的，并且很容易在pairing场景下通过Hadamard乘积论证(Hadamard product argument)来对其进行证明。关于二次约束的证明，大部分zk-SNARKs构造的基础核心来源于文献[6]。而仿射约束是依赖电路的，因此，如何在通用CRS下高效地证明仿射关系是一个充满挑战的问题。

Groth等[44]给出的构造尽管只需要常数个群元素的证明长度和常数的验证时间，但需要用到花销很大的子空间论证(Subspace Argument)，它要求CRS和预处理的长度分别为电路大小的平方和立方。另外，更新CRS要求平方多个群指数运算，而验证更新的正确性则需要线性多个pairing计算。而Sonic[45]是第一个高效的、通用的、可更新的SNARK，它的证明长度为常数个群元素而且CRS规模仅与电路大小呈线性关系。Sonic的技术目标是去对一个代表NP-hard语言的约束系统的可满足性做零知识论证，而这个约束系统与Bulletproofs[46]中的约束系统类似，也表达为二元多项式等式。为了给多项式做承诺，该文章还用到了Kate等[47]提出的多项式承诺方案的一个变体，并证明这个承诺方案在代数群模型(Algebraic Group Model, AGM)下是安全的。对于正确赋值的证明，Sonic也给出了一个新的置换论证和一个Grand-product论证。Sonic的验证需要检查一个稀疏二元多项式的赋值，该文章提出了一个简洁地检查这个赋值的方法。总的来说，Sonic给出了2种不同的方式去证明仿射约束，一个方式是完全简洁的但并不是十分高效，另一个方式通过引入一个不受信任的第三方，在批验证场景下(Batch Verification Context)可以做得十分高效。由于Sonic的整个协议是公开掷币的，而其用到的子部件是Kate的承诺方案的一个变形，该承诺方案是可更新的且其安全性可以在代数群模型下被证明，因此，在RO模型、AGM下，Sonic是通用可更新的zk-SNARK。

Marlin[48]是Sonic的改进版，其拥有与电路规模呈线性的CRS长度和常数个群元素的证明长度且都比Sonic要短，Marlin的证明时间比Sonic快10倍，而验证者时间比Sonic快3倍。Marlin可以在标准假设下实现，也可以在代数群模型(Sonic也用到了这个模型)下实现以追求最大的效率。Marlin的技术核心是一个高效的争对R1CS(Rank-1 Constraint Satisfiability)的代数全息证明(Algebraic Holographic Proof， AHP)，它能在线性的证明长度和常数的问询复杂度(Query Complexity)下实现。事实上，构造一个“全息证明(holographic proofs)”[49]与在线下阶段对一个线路做预处理的能力息息相关。这意味着验证者可以不以电路的描述作为输入而是对其的编码做少量的问询。该文章中对电路描述的编码包括一些低次多项式，与此同时，证明本身也是一些低次数的多项式，这可以视为要求证明者是代数的，而这就构成了AHP。该文章扩展了Kate的多项式承诺方案[47]，设计了一个高效的AHP，并指出利用公开掷币的AHP和多项式承诺就可以得到简洁的交互论证系统，最后利用Fiat-Shamir转化，可以得到通用可更新的zk-SNARKs。

Plonk[50], 也是Sonic的改进，其相比于Sonic而言，Plonk提高了证明时间(群指数运算少7.5～20倍)。与Sonic[45]类似，Plonk也依赖于Bayer和Groth的置换论证[51]。然而Plonk关注的是子群上的赋值而非单项式的系数，因此，同时简化了这个置换论证和算术步骤。Plonk的构造思路是首先将电路的约束分为2种——门约束和置换约束，用一元多项式表达门约束，然后和之前的方案类似同样用了Kate多项式承诺[47]的变形来打开多项式在一个点的值进行证明，而用置换论证来证明置换约束(也要用到多项式承诺)。由于整个过程是公开掷币的，而Kate的承诺方案的变形是可更新的且与Sonic类似可以在代数群模型下证明安全性，使得在RO模型、AGM下，Plonk是通用可更新的。

Lunar[52]与前面这些方案相比则有着更好的证明长度和证明者验证时间，而代价是其在验证密钥的长度和验证时间上有更高的限制。其技术贡献主要有如下2点：①提出了一种新的代数型IOPs(Interactive Oracle Proofs)变体——多项式全息IOPs(Polynomial Holographic IOPs, PHPs);②提出了一个新的编译器，它利用这个PHPs结合针对被承诺多项式的CP-SNARKs (Commit-and-Prove zkSNARKs)来构造通用的zk-SNARKs。其它的贡献包括对这些CP-SNARKs在pairing场景下实现、对R1CS和其新变体的PHPs构造的实现。另外，前面所说的编译器稍做改变可以变成第一个从IOPs到Commit-and-Prove的通用zk-SNARKs的编译器。

4 透明的zk-SNARKs

随着诸如区块链等去中心化的系统的发展与应用，类似文献[7]的传统CRS模型下的SNARK协议的需要可信第三方的特性成为了其在去中心化系统应用中的障碍。为了避免可信第三方的需求，一方面，正如前面所描述的，各种可更新CRS的zk-SNARK系统作为一种去中心化的解决方法被提出并得到广泛应用；另一方面，正如本节中将要介绍的，各种透明的zk-SNARK方案被构造提出并发展以实现去中心化。

与通用可更新的zk-SNARKs的CRS可更新并且只要更新用户中有一个用户是诚实可信的CRS就是安全的不同，透明的zk-SNARKs的CRS的生成不需要任何可信第三方。尽管透明的零知识协议的概念很早就被提出了，但是可实用的、透明的zk-SNARKs直到最近几年才出现。2018年Ben-Sasson等[53]提出了STARK方案。在STARK中，首先需要将待证明的线路或者约束条件转化成代数中间表示(algebraic intermediate representation, AIR)。简单来说，AIR将一个线路的执行表示成线路的中间状态(包括输入状态与输出状态)的转换，线路则可以表示成这些相邻状态的转换/约束。之后使用代数的布局与布线(Algebraic Placement and Routing，APR)技术优化线路的约束，并将线路的可满足性转化成2组Reed-Solomon有效性检测问题(Reed-Solomon Proximity Testing (RPT) Problem)。之后使用代数链接(Algebraic Linking)将上述2组RPT问题聚合成2个RPT问题，最后使用快速Reed-Solomon 有效性IOP协议(FRI)实现证明。大致来说，对于结构较好(拥有较多重复子线路)的线路而言，STARK可以实现O(nlog2n)的证明者时间与O(log2n)的验证者时间与通信量，其中n是线路的大小。

2019年由Chiesa等[56]提出的Fractal也是一种针对R1CS断言的SNARK。该方案通过对R1CS断言构造一种新的全息证明，并给出一种从全息IOP到透明的带预处理的SNARK的转化方式，从而实现了对R1CS类的透明的带预处理的SNARK构造。这个构造实现了O(nlogn)时间的预处理时间，O(nlogn)的证明者时间，O(|x|+log2n)的验证者时间与O(log2m)的证明长度。

同年，Setty[57]提出了另一种针对R1CS断言的SNARK——Spartan。该方案将一个R1CS实例x=(F,A,B,C,io,m,n)编码成3次的logm变量多项式G使得该实例是可满足的，当且仅当∑x∈{0,1}logm(x)=0。之后将上述等式转换成线性多变量多项式的Sum-Check，从而实现NIZK的构造。在预处理的情形下，这个NIZK是一个SNARK，并根据使用的多项式承诺不同，其效率表现也不同。其可以在证明者时间O(n)或者O(nlogn)的情形下，分别实现O(log2n)或者的验证者时间和证明长度。另外，文章中也提出了用SPARK等技术来提升方案的表现，使方案在实际运行中取得良好的表现。

在2016年，Bootle等[58]为Pedesen承诺设计了一种新的内积求值的递推论证技术，并使用这个技术为代数线路的可满足性设计了一种对数的通信复杂度的交互式零知识论证协议。在其基础上，Bünz等[46]于2018年提出了一种新的透明的短证明SNARK协议，名为Bulletproof。Bulletproof优化了先前的内积求值的递推论证技术，实现了证明者验证者时间为O(n)，证明大小为O(logn)的透明的SNARK协议。

某种程度上，Bulletproof蕴含着一个无需可信第三方的具备内积求值功能的多项式承诺方案，事实上许多CRS可更新的SNARK协议，如sonic和plonk等，都可以视作是通过多项式承诺与多项式IOP的结合。其之所以是可更新的而不是透明的，原因在于其使用的多项式承诺不是透明的。最近Bünz等[59]在未知阶群上使用Diophantine Argument of Knowledge (DARK)技术构造了新的多项式承诺。未知阶群可以使用RSA群或者类群，当使用类群时，多项式承诺不需要任何可信方。DARK多项式承诺(1)需要特别说明的是，在Crypto 2021的文献[60]中，Block等指出在DARK多项式承诺方案的安全性证明中存在着一处错误。目前尚不知这个错误能否在方案不变的情况下被修复。拥有常数的参数与承诺大小，当承诺μ个变量的d次多项式时，其多项式上点的打开需要O(dμμlogd)EXP的证明时间，O(μlogd)EXP的验证时间与2μlogdU的证明长度，其中EXP指的是类群上的一次λ-bit指数操作(所需的时间),U指的是未知阶群上的元素(长度)。Bünz等利用DARK承诺方案改进了Sonic方案，得到了Supersonic方案，后者是透明的SNARK，证明者时间为O(nlogn)EXP，验证者时间为3log (n)EXP，证明长度为2lognU。当证明n=220规模的线路时，Supersonic仅需要10.1 KB的证明大小。

5 纯公钥模型下的zk-SNARKs

不同于通用可更新和透明的zk-SNARKs构造思想，还有一些值得考虑的可实现去中心化的比CRS模型更弱的模型，例如在由文献[61]中提出的参数篡改(Parameter Subversion)模型下，考虑生成公共参数的一方有可能被敌手控制进而生成有利于敌手的参数，并最终导致协议丧失可靠性或零知识性。构造该模式下安全的zk-SNARKs协议将避免传统协议下对于可信第三方的依赖。另外，为了在更强的零知识概念下(如并发零知识、可重置零知识)进一步降低协议的轮复杂性，Canetti等[62]提出了一个比CRS模型更弱的纯公钥(BPK, Bare Public Key)模型。与参数篡改模型类似，BPK模型也不需要可信第三方来生成CRS，而是验证者在与证明者执行协议之前在公共文件夹里放上自己的公钥，显然该模型下也存在参数篡改所带来的威胁。事实上BPK模型下的验证者就是参数篡改模型下的参数篡改敌手，正如文献[63]所证，这2个模型几乎可以被认为是等价的。文献[61]第一个研究了在非交互零知识证明(NIZK，Non-interactive Zero Knowledge Proofs)的可信参数被篡改时所保持的安全性定义：防篡改可靠性与防篡改零知识性，并揭示了2者无法同时满足；此外，他们证明了同时满足防篡改零知识性和可靠性的协议是存在的，并构造了一个满足这些性质的NIZK协议，但该NIZK协议只有理论意义，实用价值不高。文献[64]基于提出新的知识假设，给出了比文献[61]更强的抗参数篡改的安全性定义，在文献[7]的方案下通过在CRS中添加部分信息并让证明者执行一个高效的CRS验证算法，以确保CRS的良好结构，使得其同时具备防篡改零知识性和知识可靠性(Knowledge Soundness)。文献[65]同样提出了新的知识假设以及新的模拟技术，在不扩大CRS尺寸的情况下，遵循文献[61]的安全性定义并展示了包括文献[7]提出的方案在内的大多数基于QAP的zk-SNARK方案都可以同时实现防篡改零知识性和知识可靠性。文献[66]通过改进文献[64]的方案，总结了构造抗参数篡改zk-SNARK的一般方法，并将文献[65]中的模拟技术应用于文献[64]的方案之中。

文献[63]认为CRS模型下的防篡改零知识性等价于BPK模型下的没有辅助输入的非黑盒的零知识。文献[67]提出了个体化规约技术并利用这个技术构造了2轮延迟输入的零知识协议等应用，事实上也提供了一个构造BPK模型下的NIZK的构造框架。这个框架目前只能被用来构造BPK模型下的NIZK方案而不是BPK模型下的zk-SNARK。尽管如文献[7]中的十分高效的zk-SNARKs已经有办法被改造成抗参数篡改的版本，但是这些改造都需要引入不可证伪的知识假设并且它们的零知识性只能满足防篡改零知识，换句话说，在BPK模型下只能实现没有辅助输入的非黑盒零知识。除此之外，文献[68]还研究了如何在零知识方面保证防篡改零知识性的同时在可靠性方面保证模拟可抽取(Simulation-Extractable)。

6 模拟多方安全计算的zk-SNARKs

姚期智先生在1982年提出了著名的百万富翁问题，进而诞生了安全多方计算(Secure Muti-part Computation, MPC)这一概念[69]。MPC技术能使彼此互不信任的多方协同计算任何函数并输出计算结果，并保证任何一方均无法得到除应得的计算结果之外的其他任何信息。2007年， Ishai等[70]首次提出MPC-in-the-head的概念，这个概念是指证明者先在“头脑中”执行MPC协议然后再对“头脑中”各个参与方的看到的副本进行承诺并发送给验证者，随后验证者V再与P交互，来判断是否相信P的断言。基于这个框架做的zk-SNARKs的优点是不需要可信的设置、证明时间高效而且抗量子攻击。基于这个范式， Giacomelli等[71]发表了ZKBoo方案，该方案相比方案[70]取消了交互，且验证时间和在此之前的zk-SNARKs差不多的情况下，证明时间几乎快了1 000倍，缺点是其通信复杂度与电路大小呈线性关系。ZKBoo主要是通过用一个电路分解的方法来取代MPC协议从而扩展了方案[70]的想法，这意味着该证明者不需要完全遵循MPC协议的性质从而获得更高的效率。Chase等[72]对方案[71]进行了改进，在不增加计算成本的前提下将证明长度减少了一半以上。Ames等[73]将高效的安全多方计算和Ishai等[70]提出的将MPC协议转化为零知识交互PCPs(ZKIPCP)的一般转换的变形相结合，从而将通信复杂度几乎降低到了验证电路大小的根号级别，其证明长度大约比方案[72]短4倍。

7 总 结

零知识证明理论在密码学中处于极其重要的基础地位。从应用上来说，零知识证明所具有的强大的隐私保护特性使得它被广泛应用于身份认证、群签名、安全多方计算、密码货币、电子投票等领域之中。从零知识证明到非交互零知识证明再到zk-SNARKs，目前的零知识证明在功能性、简洁性和效率上都已经做得很好但仍有很多提升空间。尽管目前文献[7]提出的CRS模型下的方案在证明长度和验证效率上达到了最优，但在是现实上依然存在中心化的问题。而通用可更新的zk-SNARKs的研究目前比较热门，出现了很多各有优劣的新方案，未来主要是研究如何在效率和通信量上做到更优。透明的zk-SNARKs相比较存在可信第三方的SNARKs，其通信量与验证者时间仍有较大差距，这也是其实用化的最大障碍，因此，其研究重点在于如何进一步减少验证者计算量与通信量。而BPK模型下的zk-SNARK主要依靠添加额外CRS验证算法来解决CRS模型下的中心化问题，但目前这个验证算法的的运行时间并不理想，未来如何提出更高效的解决方式是一个待研究的课题。模拟多方安全计算的zk-SNARKs相比于其它SNARKs的缺点主要在于通信量，因此其研究重点在于如何在保证效率的同时设计通信量更小的方案。