二次算数程序（QAP）构造

我们将在这里展示一种常见的构建SNARKs的方法论，这些构造中的一些代表了这个领域的最新技术（state of the art）。大多数SNARKs的构造和实现以Gennaro等作者在[1]中引入的基于二次程序（quadratic programs）的框架为中心起点。这个通用框架允许为实例化成布尔（boolean）或者算数（arithmetic）电路（circuit）的程序构建SNARKs。

这种方法促进的实际可验证计算（verifiable computation）的快速发展。例如，使用arithmetic circuits的跨度程序（span program），也就是我们说的QAP，Pinocchio在[2]中提供证据表明，验证的远程计算可以比本地计算更快。同时，他们的构造是zero-knowledge的，使服务器能够保持计算中的中间值（intermediate）和附加值的隐私。

基于QAP方法优化的SNARK版本被用于各种实际应用中，包括加密货币（cryptocurrency），如Zcash[3]，通过ZK特性保证匿名性（anonymity），同时防止双重支付（double-spending）。

一个用于circuit的SNARK方案必须能够验证（arithmetic或boolean）电路可满足性（Circ-SAT）问题的proof，即给定一个circuit，prover必须让verifier相信它知道一个使输出为真的输入分配（assignment）。在以下定义中，我们可以把circuit[公式] 看作一个可满足（satisfiability）问题的逻辑规范（logical specification）。

• 算数电路（Arithmetic Circuits）：非正式地，一个arithmetic circuit由一些导线（wire）和门（gate）组成。Wire用来传输取自域（field） 𝔽 的值，以及连接到加法（addition）和乘法（multiplication）gate。

output

c₆

×

c₅

×

＋

c₁、c₂、c₃、c₄

Arithmetic Circuit

• 布尔电路（Boolean Circuits）：一个boolean circuit由逻辑门（logical gate）和gate之间的一组wire组成。这些Wire传输取自 {0，1} 的值。

output

c₁、c₂、c₃、c₄、c₅、c₆、c₇、c₈、c₉

Boolean Circuit

我们把任意circuit关联的可满足性（satisfaction）问题定义如下：

定义（Circuit Satisfaction， Circ-SAT）：对于一个circuit C ： lᵤ × lω → {0，1} ，circuit satisfaction问题由关系（relation） Rᴄ＝{(u，w)∈lᵤ × lω：C(u，w)＝1} 定义，其语言为 Ըᴄ＝{u∈lᵤ：∃w ∈ lω，C(u，w)＝1} 。

标准结果表明，多项式大小的circuit和在多项式时间内运行的图灵机（Turing machine）（相差一个logarithmic factor）是等价的，尽管通过circuit计算和在本地硬件上计算的实际效率很大程度上取决于应用；例如，矩阵乘法（matrix multiplication）的arithmetic circuit基本上没有额外的开销，而整数乘法的boolean circuit效率就要低得多了。

回到2013年，Gennaro, Gentry, Parno and Raykova在[1]中提出了使用二次跨度程序（QSP，Quadratic Span Program），一种对Karchmer and Wigderson[4]定义的span program的自然扩展，对复杂度类NP进行一种新的、有影响力的描述（characterization）。

随后出现了一些QSP的变体和改进，在[5]中，Lipmaa通过将现有技术和线性纠错码（ECC，error-correcting code）相结合，提出了一类更高效的QSP。

Parno等作者[2]定义了QAP，这是一种用于arithmetic circuit的类似概念，即二次算数程序（Quadratic Arithmetic Program）。最近，[6]提出了用于boolean circuit的改进版本，称为平方跨度程序（SSP，Square Span Program）。自然地，这引出了相同思路的arithmetic circuit的简化版本，即平方算数程序（SAP，Square Arithmetic Program），由[7]提出。

这些方法用于编码计算，以便获取高效的zk-SNARK。主要思路是将每个gate的输入和输出表示为一个变量（variable）。然后，我们可以将每个gate重写成一个方程（equation），由一些variable表示gate的输入和输出wire。这些equation只能由满足gate的logic或arithmetic specification的wire的值满足。通过为circuit中所有gate组合这样的约束（constraint），任何circuit的satisfying assignment可以首先指定为一组二次方程，然后转化为一组多项式上的跨度（span）的constraint，定义相应circuit的QSP/SSP。因此，prover需要通过找到一个等效多项式问题的解来说服verifier所有的二次方程都是satisfiable的。

[1] Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. Quadratic span programs and succinct NIZKs without PCPs. In Thomas Johansson and Phong Q. Nguyen, editors,EUROCRYPT 2013, volume 7881 of LNCS, pages 626–645. Springer, Heidelberg, May 2013.

[2] Bryan Parno, Jon Howell, Craig Gentry, and Mariana Raykova. Pinocchio: Nearly practical verifiable computation. In2013 IEEE Symposium on Security and Privacy, pages 238–252. IEEE Computer Society Press, May 2013.

[3] Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, and Madars Virza. Zerocash: Decentralized anonymous payments from bitcoin. In2014 IEEE Symposium on Security and Privacy, pages 459–474. IEEE Computer Society Press, May 2014.

[4] M. Karchmer and A. Wigderson. On span programs. In IEEE Computer Society Press, editor,In Proc. of the 8th IEEE Structure in Complexity Theory, pages 102–111, Gaithersburg, MD, USA, 1993. IEEE Computer Society Press.

[5] Helger Lipmaa. Succinct non-interactive zero knowledge arguments from span programs and linear error-correcting codes. In Kazue Sako and Palash Sarkar, editors,ASIACRYPT 2013, Part I, volume 8269 of LNCS, pages 41–60. Springer, Heidelberg, December 2013.

[6] George Danezis, Cédric Fournet, Jens Groth, and Markulf Kohlweiss. Square span programs with applications to succinct NIZK arguments. In Palash Sarkar and Tetsu Iwata, editors,ASIACRYPT 2014, Part I, volume 8873 of LNCS, pages 532–550. Springer, Heidelberg, December 2014.

[7] Jens Groth and Mary Maller. Snarky signatures: Minimal signatures of knowledge from simulation-extractable SNARKs. LNCS, pages 581–612. Springer, Heidelberg, 2017.

数学联邦政治世界观提示您：看后求收藏（笔尖小说网http://www.bjxsw.cc），接着再看更方便。