基于QAP的零知识证明

基于二次算术程序（Quadratic Arithmetic Programs，QAP）的一类零知识证明在现今非常常见，其代表方案有PGHR13 、Groth16 、GKMMM18 等。
这些方案的逻辑基本上遵循一下范式：

1. 将计算函数转化为算术电路（Arithmetic Circuit）
2. 利用QAP，将算术电路可满足性（Circuit-Satisfaction，C-SAT）问题规约为多项式间的整除性问题
3. 设计方案，使得方案满足完备性、可靠性、零知识性

一、算术电路

算术电路是一组由“门”和“线”组成的算术结构，“门”用于表示运算符，“线”用于表示运算数值。
定义： 给定一个映射 \(\mathcal{C}:\mathbb{F}^n \times \mathbb{F}^h \rightarrow \mathbb{F}^l\) ，其将 \(n+l\) 个有限域 \(\mathbb{F}\) 上的元素映射到 \(l\) 个有限域 \(\mathbb{F}\) 上的元素。
（在这里，我们将输入分为两类，一类是包含 \(n\) 个元素的公开输入，一类是包含 \(h\) 个元素的隐私输入）

C-SAT问题可以被描述为：给定一个电路与一组电路输出，判定是否存在一组电路输入使得电路中所有“线”的赋值合法。
基于QAP的零知识证明的构造原理在于将C-SAT问题转化为多项式间的关系问题。

二、QAP

定义： 一个在域 \(\mathbb{F}\) 上由算术电路 \(\mathcal{C}\) 转换而来的QAP \(\mathcal{Q}\) 包含了三组多项式集合 \(A=\{A_k(x)\}\)，\(B=\{B_k(x)\}\)，\(C=\{C_k(x)\}\)，\(（ k\in\{0,1,...,m\}\)，以及一个目标多项式 \(t(x)\)。若\(\{a_1,a_2,...,a_N\}\in \mathbb{F}^N\)是算术电路\(\mathcal{C}\)的一组合法赋值，那么可以构造多项式\(P(x)\)被目标多项式\(t(x)\)整除。其中，\(P(x)=(A_0(x)+\sum^m_{i=1} a_i A_i(x))\)\(\cdot (B_0(x)+\sum^{m}_{i=1} a_i B_i(x))\)$-(C_0(x)+\sum^m_{i=1}a_iC_i) $

关于QAP的定义，有以下几点需要被理解：

1. 变量\(x\)可以被抽象为对“乘法门”的描述
2. \(t(x)=(x−r_1)(x−r_2),...,(x−r_g)\)，\(g\)为乘法门的个数
3. \(r_i\in \{r_1,r_2,...,r_g\}\)为乘法门的抽象赋值，可以理解为门的编号
4. \(m\)数值表示电路中“特殊线”的个数，特殊线为"电路的输入线"或"乘法门的输出线"
5. 电路中共有\(N\)条线，其中有\(m\)条特殊线，\(n+l \leq m \leq N\)
6. \(a_i\)表示线\(i\)的赋值，定义中隐含地约定\(\{a_1,a_2,...,a_m\}\)为特殊线
7. 当门\(x\)的左输入为特殊线\(i\)时\(A_i(x)=1\)，否则\(A_i(x)=0\)
8. 当门\(x\)的右输入为特殊线\(i\)时\(B_i(x)=1\)，否则\(B_i(x)=0\)
9. 当门\(x\)的输出为特殊线\(i\)时\(C_i(x)=1\)，否则\(C_i(x)=0\)
10. \(A_0(x)\)，\(B_0(x)\)，\(C_0(x)\)描述了门\(x\)的常数输入/输出

\(P(x)\)描述了这样一个事实，即对于每一个乘法门，其左输入与右输入的乘积等于输出。所以， \(P(x)\) 在其 \(g\) 个乘法门处的求值为\(0\)，根据多项式的性质，\(P(x)\)必然可以被\(t(x)\)整除。根据这一特性，我们将C-SAT问题转化为

例子：给定下图所示电路，构造QAP

约定输入为\(C1\)和\(C2\)，输出为\(C5\)的门的编号为\(r_5\)；输入为\(C5\)和一条普通线，输出为\(C6\)的门的编号为\(r_6\)。那么，可以构造目标多项式\(t(x)=(x-r_5)(x-r_6)\)