zk-SNARK证明的复杂性

Question

免责声明:我没有密码学的背景，我想问的一切都是我从过去几天疯狂阅读这个话题中学到的。任何帮助都是非常感谢的。

问:生成一个zkSNARK证明并验证它的计算复杂度是多少？

具体而言，在生成和验证一个证明时涉及多少个双线性配对、曲线点加法和标量乘法？这些约束在系统中的数量是线性的吗？

这里，我可以看到每个验证都需要验证器来计算11曲线对、3*m标量乘法和3(m+1)曲线点加法。首先，我的理解正确吗？第二，什么是m？这就是约束的数目吗？第三，如果我知道约束的数量，我如何同样地计算出验证程序必须计算的配对、加法和乘法数？

Answer 1

它取决于所使用的协议。最后一个也是更有效的是Groth16，它在其证明中只使用3个曲线点。您可以在Groth的论文的表2中看到键的大小和证据。该配对的计算复杂度取决于什么曲线。一般说来，ZoKrates/Ethereum和ZCash使用的是bn256曲线参数，而在它们的包中使用的配对算法(至少在高朗氏中)是米勒食材配对的算法1。

您可以看到，zk是各种作品的融合，其复杂性取决于日复一日的实现。