二次算数程序（QAP）构造 (4-1)

我们将在这里展示一种常见的构建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）问题定义如下：

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。