零知识证明系统的比较：Plonk 与 Groth16
本文主要介绍两种ZK-SNARK协议，Groth16和Plonk，并指出关键内容，并从可用性、性能和安全性等方面进行比较。
零知识证明背景回顾
零知识协议由两个参与方组成，即证明者（P）希望说服验证者（V），某个陈述x (instance) 为真，使用秘密w (witness) 而不向验证者或其他人透露w。
例如，我想说服别人我的银行账户有足够的资金，但我不愿透露我的实际余额。
在这种情况下，“我的余额超过1000万美元”是陈述（公共输入, instance），而证人（秘密输入, witness）是我的实际余额。
每个ZK协议都需要满足以下基本要求：
(1). 完备性：诚实的P总是能够说服诚实的V。
(2). 可靠性：不诚实的P无法说服诚实的V。
(3). 零知识：不诚实的V除了陈述的真实性之外不得知任何其他信息。
区块链上的ZK协议必须满足短的证明大小和合理的时间复杂度的要求，此外，由于区块链中的可扩展性和性能问题，证明者和验证者之间的多轮交互是不可取的。
区块链中通常使用非交互式的零知识证明，即证明者生成证据并将其发送给验证者。密码学家解决了上述问题，提出了一种新类型的ZK协议，即知识简洁非交互知识论证（ZK-SNARK）。
消除参与方之间的多次通信不仅提升了协议性能，而且任何一方都不需要保持在线状态。
为了消除证明者和验证者之间的额外轮次，有两种方法，即随机预言机模型和公共参考字符串（CRS）。
在本节，我们将讨论CRS的方法，因为Groth16和Plonk协议都采用了这种模型。从理论上讲，有一个可信和诚实的第三方负责生成随机值r，并利用该随机值创建CRS参数（证明密钥pk和验证密钥vk）。
拥有随机值r的任何人都可以生成伪造证据。为增强协议安全性，ZK-SNARK通常利用多方计算，其中所有参与方共同计算一个函数，无需任何信任的第三方机构。
根据本文，只要至少有一个诚实的参与方，最终参数就是安全的。
注：由MPC仪式 (MPC Ceremony) 生成的所有安全参数应通过一个安全的过程删除。
让我们像对ZK协议一样定义SNARK的属性：
1. 简洁：证据的大小与陈述或证人的大小相比非常小。
2. 非交互式：P和V之间不需要多次交互。
3. 知识论证：除非不诚实的P知道某个秘密“证人”，否则无法说服诚实的V。
4. 零知识：不透露除公共信息之外的任何内容。
总结一下，ZK-SNARK由三个阶段组成：通过MPC协议进行可信设置以生成证明和验证密钥，证明者使用证明密钥公共输入和秘密输入（witness）生成证据，并验证证据。
主要的算法如下：
CRS( randomness r , statement x) — -→(pk,vk)
Prover (pk, statement x, witness w) — ->proof pi
Verifier( vk, pi, statement x) — --> accept or reject proof pi
Groth16
2016年，Groth引入了一种基于多项式方程(QAP)和基于配对的非对称密码体系，构建了一套ZK-SNARK协议。
基于配对的SNARKs遵循一些规则，其中证明者使用通用群操作计算一些群元素，验证者使用配对来检查证明的正确性。
在Groth16方案中，任何具有公共输入x和私有证据w的程序F(x,w)=y，都可以被转换为算术电路C。
为了证明电路C的正确性，我们必须验证每个门的正确性。为此，Groth16使用QAP来编码电路。QAP定义了多项式P(z)=Ui(z).Vi(z)-Wi(z)，它编码了所有乘法门，其中多项式Ui，Vi和Wi分别表示第i个门的左侧、右侧和输出，而(a1,...,am)表示电路线值。
定义一个目标多项式T(z)=(z-r1)(z-r2)...(z-rn)，其中r1,...,rn是随机变量，n表示电路中乘法门的数量。基本思想是，多项式P(z)被定义为可被T(z)整除。
这意味着存在一个多项式H(z)，使得P(z)=H(z)T(z)。因此，如果有一个可信的方在随机点s处评估这些多项式(U(z), V(z), W(z))，将它们放入CRS，那么证明者可以生成一个证明，验证者可以验证它。
Plonk
PlonK协议通过引入通用和可更新的SRS来解决一次性的可信设置问题。换句话说，只要电路大小不超过CRS阈值限制，多个程序可以共享CRS。
同样，Plonk将每个程序转换为乘法和加法门的算术电路。然而，Plonk证明电路的正确性和一致性的方式，和Groth16是截然不同的。
为了证明Plonk电路的正确性，我们需要证明每个门约束的有效性，以及门之间的关系。除了对多项式方程的验证外，还采用了一种数学的排列论证方法来验证门之间的约束关系，即复制约束 (Copy Constraint)。
性能比较
PlonK提供两个变体，一个具有9(n+a)次多项式，另一个具有11(n+a)次多项式。
前者的证明大小较大，但与后者相比，证明计算减少了约10%。
这里，n代表乘法门，‘a’代表电路中的加法门。
下面是Groth16和Plonk的两个变体之间的性能和安全性比较。
证明复杂性分析：
在普通电路中，加法门和乘法门的比例为2:1。基于这个电路假设，这意味着相较于Groth16，PlonK的证明时间要差2.25倍。
由于证明生成可以在链下离线完成，不需要担心证明时间复杂性。然而，应该考虑证明大小，它会影响交易大小和区块链网络吞吐量。回想一下，每个群元素是F域中的一对x和y点。
Groth16证明大小：2G1.(2 F) + 1 G2（计算4F元素）= 6F
Plonk证明大小：9G1+ 7F = 16F
假设每个元素占用256位。根据Vitalik的帖子，Groth16在128位的安全级别下，证明大小约为200字节，而PLonk在相同的安全级别下需要约500-1000字节。
验证复杂性分析：
Groth16的验证算法与其公共输入大小呈线性关系，而Plonk则需要固定数量的指数和配对计算。
结论
理论上，Groth16和Plonk都依赖于数学问题的假设，且都不具备量子抗性。然而，相比于Groth16，Plonk需要更弱的安全假设。
就证明大小而言，Plonk的证明大小约为Groth16的2倍至5倍，但Plonk全局可更新的SRS的优势，而Groth16没有。
作者: Mehri Rezaei
翻译： 杨赟博
来源：https://medium.com/@mehialiabadi/plonk-vs-groth16-50254c157196
END
2.笔记分享｜组队学习密码学（5）— 密码数学基础：初等数论
推荐4.论文分享｜基于Vector OLE构造的恶意安全的PSI协议（VOLE-PSI）