矩阵元 |【隐私计算笔谈】零知识证明系列专题（三）：初识zk-SNARK

本文转载自微信公众号 ：矩阵元

原创：汪海龙、邓燚

之前介绍过的零知识证明都不考虑任何交互之前的初始假设，因而它的安全性高度依赖交互与双方的随机性。八十年代末，Blum，Feldman和Micali引入了一个带有可信第三方的模型并在此模型中实现了一轮单向（非交互）零知识证明。这一模型中，可信第三方先生成一个公共参考/随机串，证明者在这个参考串下生成一个针对相关断言的证明并发送给验证者，然后验证者基于同一参考串验证该证明。

公共参考串模型中能够实现非交互零知识证明并不太令人意外。从证明者的角度，它提供的证明是可以模拟的：模拟器可以通过操纵公共参考串来生成一个可以通过验证的证明；从验证者的角度，只要信任生成公共参考串的第三方，它就可以相信证明者所证明的断言必然为真。

近年来金融科技的蓬勃发展对非交互零知识的效率和降低信任假设提出了非常高的要求，极大地促进了简洁高效的非交互零知识证明（zk-SNARK）的研究。在接下来的一系列文章里，我们将介绍zk-SNARK及其一些相关研究的发展历程和近年的研究进展。

在介绍zk-SNARK之前，我们想强调的是，从传统密码学的角度，所有的这些构造都高度依赖非常强的非传统的困难性假设（用Naor的话来说，不可证伪假设，如知识的假设等），其中许多假设是为了构造的效率而新提出的；此外它们通常还需要在非常强的模型—如随机预言机模型—中才能证明其安全性。当然，许多强的假设和模型确实是实现zk-SNARK所必需的：Gentry在2011年已经给出了一个负面分离结果，SNARK无法建立在可证伪假设上。

SNARK是Succinct Non-interactive Arguments of Knowledge的缩写，我们先从名字来解释它所具有的性质：

• Succinct（简洁性）：证明的长度与实际计算的长度比起来很短，是一个Polylog级别的大小（或者更短）。

• Non-interactive（非交互）：这个很好理解，在证明的过程中，证明者一次性地将整个证明发送出去，而验证者可以直接通过这个证明来验证断言的正确性。过程中不需要交互，也就是说双方不需要同时在线。

• Arguments（论据）：与Proof不同，Arguments意味着这个系统只能抵抗有限计算能力的恶意证明者。对于无穷计算能力的证明者来说，可以对一个错误的断言伪造一个能够被通过的证明。但这种安全性对于工业界来说已经足够了。

• Knowledge（知识性）：这条性质要求，如果一个证明者能够正确地证明一个断言，那么这个证明者一定知道这个断言对应的证据。对于一个不具备Knowledge性质的证明系统来说，证明者能够证明某个断言，只能说明这个断言是正确的，但并不代表这个证明者知道这个断言对应的证据。Knowledge性质是一个更高的要求。

• zk-SNARK：除了上述性质外，zk-SNARK还具备零知识性。

Zk-SANRK和传统的NIZK相比，主要的区别就是效率（zk-SANRK可以看作是NIZK的一个子类），虽然从定义上来说，只对证明长度做了具体的要求，但在实际的研究发展中，学界对证明时间、验证时间上也有着很高的要求，现在的主流的zk-SNARK方案已经能在一定程度上满足业界的要求。

而且随着应用场景的不同，人们也在尝试着去牺牲一些验证者时间和证明长度上的表现，来减小证明者的计算量。对于这些协议并没有一个严格的「性能指标」的要求，只要能更好的满足现实场景的要求即可。我们称这一类的协议为简洁高效的零知识证明协议。

从Gentry，Gennaro等人的开创性工作[GGPR13]以来，关于简洁高效的非交互零知识证明的研究开始进入了一个高速发展期，期间涌现出了大量的优秀方案，这些方案采用了各种各样巧妙而有效的技术，依赖于各种不同的密码学假设，在证明者时间、验证者时间、证明长度，安全性等有着不尽相同的表现。

在这里，我们按照不同的技术路线，可以将目前的简洁高效零知识证明方案大致分为五类（从不同的维度出发，会有不同的分类方式，比如还可以按照信任模型来划分，但这里我们决定按照技术路线的不同来给大家简要介绍）：

• 基于Linear PCP的方案。即zk-SNARK，是目前被研究得最多，也是成果最丰富的一类。

• 基于交互式（代理计算）协议的方案。从已有的高效交互式（代理计算）证明协议出发，构造高效的零知识证明方案（提升效率并添加零知识性质）。

• 基于MPC的方案。这一路线的核心思想是「MPC in the head」，证明者自己模拟MPC协议的所有的参与方，将这些参与方的view作为证据，通过检查MPC协议的正确性来验证所构造证明的正确性。

• 基于离散对数问题的方案。如bulletproof等。

• 基于short IOP的方案。从高效的IOP方案出发，构造高效的零知识证明方案。

我们从下一篇内容开始，会对每个技术路线做一个简单介绍，让大家对这些技术路线的思想和主要框架有一个大致的认识。下期见！

参考文献

[1].Gennaro, Rosario, et al. “Quadratic span programs and succinct NIZKs without PCPs.” Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 2013.

[2].Blum, Manuel, Paul Feldman, and Silvio Micali. “Non-interactive zero-knowledge and its applications.” Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali. 2019. 329-349.

[3].Gentry, Craig, and Daniel Wichs. “Separating succinct non-interactive arguments from all falsifiable assumptions.” Proceedings of the forty-third annual ACM symposium on Theory of computing. 2011.