论文分享｜QuickSilver：任意域上的用于电路和多项式的可负担的高效零知识证明

论文名称：Yang K, Sarkar P, Weng C, et al. Quicksilver: Efficient and affordable zero-knowledge proofs for circuits and polynomials over any field

论文来源：Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. 2021: 2986-3001.     

论文整理 ：济南大学信息科学与工程学院2021级硕士研究生孙奎恒

论文链接：https://dl.acm.org/doi/pdf/10.1145/3460120.3484556

现有较为流行的非交互式零知识证明方案(如，Groth16、Virgo等)都具有证明内存占用大，即可扩展性差的问题。这已成为了零知识证明系统可处理计算规模的重要瓶颈。这引起了广泛关注。有些方案尽管尝试解决可扩展性差的问题，如基于无隐私混淆电路的零知识协议、基于MPC-in-the-head的零知识证明协议等，但因为其在计算及通信效率方面的表现不是很理想，导致其无法进入实用。

2.1 协议的三个阶段

首先是预处理阶段（即，线下阶段），证明者及验证者需要进行初始化操作，生成相应数量的随机sVOLE实例，用于线上阶段对线值进行承诺。

其次是线上阶段，首先便是对线值承诺。sVOLE具有加法同态的性质，因此加法门可以在本地进行计算，无需双方进行通信。这时只需对电路输入值及乘法门的输出值进行承诺，在本文的协议，对于个sVOLE实例，这共需个域元素通信，其中代表输入值的大小及代表乘法门的数量。

最后便是线上验证阶段，需要向证明乘法门的输出正确性及电路输出。第一种方法是将基于sVOLE的承诺作为黑盒使用；第二种便是形同LPZK方案，利用IT-MAC的线性关系。

2.2 乘法门的验证及证明

设双方已经拥有乘法门输入及输出的承诺，其中且对于，。为了防止恶意证明者，需要对是否等于进行验证。若，应该满足以下公式：

且可以通过由验证者随机采样值实现对乘法门的批量认证：

2.3 扩展sVOLE及VOPE协议

扩展sVOLE用于协议中全局密钥的生成及随机sVOLE生成。VOPE(vector oblivious polynomial evaluation)被用于协议双方生成随机多项式关系，用于零知识证明协议中对发送值进行屏蔽。

2.4 针对电路可满足性的零知识证明协议

这个协议具有完美完备性、错误为的可靠性及完美零知识特性。这个协议的通信量为，与输入值大小及乘法门数量呈线性关系。证明计算复杂度及验证计算复杂度与乘法门数量呈线性关系。且此协议的线上阶段可以通过Fiat-Shamir范式实现非交互式线上阶段。

4.1 基于电路的零知识证明协议

本文使用AND/MULT门验证电路来对ZK协议的性能进行基准测试。

在布尔电路中，QuickSilver与最先进的协议Wolverine相比，计算提高了6倍，通信提高了7倍；对于算术电路，与Wolverine和Mac'n'Cheese相比，QuickSilver协议在计算方面至少提高了7倍，在通信方面提高了3-4倍。

对于4核CPU的m5.2xlarge 类型的 Amazon EC2 机器，QuickSilver协议在布尔电路的计算速度为每秒 530 万到 730 万门，算术电路的速度为每秒 220 万到 300 万门。

4.2 基于多项式的零知识证明协议

在下面的所有实验中，对二进制域使用20 Mbps的网络带宽，对61比特域使用500 Mbps的网络带宽，并且始终使用单线程。

对于内积测试，证明者想要证明两个向量的内积等于一个公开值。在下表对处理见证及证明内积在不同的域及不同长度的向量下进行了测试。

其次，对矩阵乘法进行测试，QuickSilver中基于多项式的零知识证明协议比基于电路的协议快31倍，通信比基于电路的协议少340倍。QuickSilver的证明体积仍然明显大于 Spartan 和 Virgo，但在执行时间和内存占用方面有优势。

对于证明解决基于格的问题(SIS)，证明者证明其拥有向量，使得。其中矩阵和向量是公开的。各种协议的通信量及执行时间如下。