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

定义（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的。

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