原创 Star Li 星想法 2019-05-21 17:33
收录于话题#零知识证明技术36个内容
看zk-SNARK的文章或者资料的时候，经常会碰到一些算法名称，比如Groth16，GGPR13等等。这些名称是由算法提出的作者名称或者名称首字母以及相应的年份组成。Groth16，是由Jens Groth在2016年提出的算法。GGPR13，是由Rosario Gennaro，Craig Gentry，Bryan Parno，Mariana Raykova在2013年提出的算法。
零知识证明（zk-SNARK )，从QSP/QAP到Groth16，期间也有很多学者专家，提出各种优化（优化计算时间，优化证明的大小，优化电路的尺寸等等）。Groth16提出的算法，具有非常少的证明数据（2/3个证明数据）以及一个表达式验证。
Groth16论文（On the Size of Pairing-based Non-interactive Arguments）的下载地址：
https://eprint.iacr.org/2016/260.pdf
本文主要从工程应用理解的角度介绍Groth16算法的证明和验证过程。文章中所用的中文字眼可能和行业中不一样，欢迎批评指出。
1
术语介绍
Proofs - 在零知识证明的场景下，Proofs指具有完美的完备性（Completeness）以及完美的可靠性（Soundness）。也就是，具有无限计算资源也无法攻破。
Arguments - 在零知识证明的场景下，Arguments是指具有完美的完备性以及多项式计算的可靠性。也就是，在多项式计算能力下，是可靠的。
Schwartz-Zippel 定理
是个n元多项式，多项式总的阶为d。如果
是从有限集合S中随机选取，则
的概率是小于等于