导语
本文是“零知识证明引论”系列的第四部分。前面我们介绍了零知识证明的背景，概念以及一些核心数学工具。本文我们将介绍匹诺曹协议和Groth16。
匹诺曹协议
其实，介绍完上述的核心数学工具，一个接近可工程实践版本的非交互性零知识证明协议已经呼之欲出了，这一套完整的过程就是目前一系列zkSnark算法的基础——[PGHR13]，俗称匹诺曹（Pinocchio）协议[7]。
这篇匹诺曹协议的论文的理论基础基于[GGPR13][8]，主要偏工程实践，也是首次用C语言实现了一个接近可用的零知识证明库。
1 引入随机偏移量
在具体实现上，和上述过程的区别是，为了防止暴力破解的可能（比如在特殊的情况下，系数的数量和取值范围都有限），prover在构造p(x)的过程中，加入一个随机偏移量δ：
令原多项式为：
加入
偏移量后为：
则
令
那么对于新的验证组合：
仍然可以通过验证，但是不暴露更多系数知识，无法被暴力破解。
2 协议全流程
• Setup
-
选择生成元G和加密配对e -
将变量总数为 n 其中输入/输出变量数位 m 的函数 
，拍平为数字电路并针对每个门电路改写为R1CS的形式，再转换为阶数为 d（和门的数量有关） 大小为 n+1 的多项式形式（QAP） -
选择随机数 -
设置 和操作数生成元 -
设置 proving key:
-
设置 verification key：
-
丢弃随机数
• Proving
-
代入输入值 u，执行 f(u)计算获取所有的中间变量值
-
把所有未加密的变量多项式赋值给
,并对 R(x) 和 O(x) 做同样的计算
-
-
计算
-
将 prover 的变量值赋值给加密的可变多项式
-
为其 α对变换赋值
-
为变量值一致性多项式赋值
-
计算并提交证明
• Verification
-
-
-
可变多项式约束检查:
-
变量值一致性检查:
-
有效性计算检查:
Groth16
Groth16（filecoin, Tornado.cash, 旧版Zcash）、PlONK（zkSync, Mina）和Halo（新版ZCash）等。其中应用最广泛的算法是Groth16。
Groth16算法是Jens Groth提出的一种匹诺曹协议的改进，相关论文[9]不仅对已有算法进行改进，而且讨论了基于配对的非交互式零知识论证的证明大小问题。Groth16因其精简的证明大小和高效的验证效率，已经完全具备了工程应用的条件，在早期的ZCash等匿名币项目中多有应用，是最经典的零知识证明算法，也是在区块链领域应用最早的算法。
算法的基本框架仍然是匹诺曹协议，分为setup、prooving、verication三个部分，其对于匹诺曹协议最大的升级是setup和verification部分，通过增强了一些双线性映射对的安全假设，缩减了Proving Key的大小，将K1的element数量从7个缩减为2个，进而减小了验证的数据量和计算量，从需要验证12个双线性对缩减为验证3个。
本文介绍了零知识证明协议的zkSnark族中可实用的最基础的两个协议——匹诺曹和Groth16。近期在区块链上应用比较火热的Plonk和Sonic算法，都是基于Groth16在可信设置上做的优化和改进。希望读者能够结合之前的数学工具，了解这两个算法的基本原理，为下篇文章的理解奠定基础。下篇文章我们将重点介绍这些改进算法和一些比较典型的非Snark算法。
参考文献：
[7] Parno B, Howell J, Gentry C, et al. Pinocchio: Nearly practical verifiable computation[C]//2013 IEEE Symposium on Security and Privacy. IEEE, 2013: 238-252.
[8] R. Gennaro, C. Gentry, B. Parno, and M. Raykova, “Quadratic span programs and succinct NIZKs without PCPs,” in EUROCRYPT, 2013. Originally published as Cryptology ePrint Archive, Report 2012/215.
[9] Groth J. On the size of pairing-based non-interactive arguments[C]//Annual international conference on the theory and applications of cryptographic techniques. Springer, Berlin, Heidelberg, 2016: 305-326.
原文始发于微信公众号（Numen Cyber Labs）：Numen | 零知识证明引论Part 4
