5-QAP问题转换

接下来我们需要考虑如何采用计算机来存储和验证 $P(x)$ 。我们引入QAP的概念，并且我们可以P(x)转换为QAP问题。QAP（Quadratic Arithmetic Programs）翻译是二次算术程序。

QAP是一种非常适合于计算机进行表达和运算的形式。一个QAP问题包含一系列的算数表达式，这些算数表达式都是具有最多两个输入和一个输出的形式。例如 $y=x_1+x_2$

扁平化展开

以 $P(x) = x^3+x+5$ 为例，求 $P(x)=35$ 的解。我们将P(x)按照QAP展开，得到：

$sym_1=x*x$
$sym_2=x*sym_1$
$sym_3=sym_2+x$
$out=sym_3+5$

这样我们就把一个多项式问题拍扁成了4个算数表达式，并且引入了一些中间变量 $out, sym_1, sym_2, sym_3$ 。上面这4个表达式，我们称为4个约束条件。我们需要留意的是，这四个约束条件，也可以被理解为4个门电路。

R1CS转换

我们可以建立4组向量 $(\vec a, \vec b, \vec c)$ 来表达上面的4个约束。 $\vec s$ 是满足 $\vec s \cdot \vec a* \vec s \cdot \vec b- \vec s \cdot \vec c=0$ 的解。考虑到上述的4个表达式包含的参数信息，我们令 $\vec s=(1，x, out, sym_1, sym_2, sym_3)$

第一个约束（第一个门电路）

根据第一个约束我们建立第一组向量 $(\vec a_1, \vec b_1, \vec c_1)$ ，转换为 $x*x-sym_1=0$ 。那么这第一组向量，如何能够满足 $\vec s \cdot \vec a_1* \vec s \cdot \vec b_1- \vec s \cdot \vec c_1=0$ 呢？这里大部分文章都没有讲清楚。我们在这里细讲一下。

由于s向量是已知的，我们列出以下表格。

$\vec s$	$\vec a_1$	$\vec s$	$\vec b_1$	$\vec s$	$\vec c_1$
1	?	1	?	1	?
x	?	x	?	x	?
out	?	out	?	out	?
sym1	?	sym1	?	sym1	?
sym2	?	sym2	?	sym2	?
sym3	?	sym3	?	sym3	?

那我们直接：

令 $\vec a_1$ 的第2个分量为1，其他分量为0；

令 $\vec b_1$ 的第2个分量为1，其他分量为0；

令 $\vec c_1$ 的第4个分量为1，其他分量为0；

也就是：

$\vec s$	$\vec a_1$	$\vec s$	$\vec b_1$	$\vec s$	$\vec c_1$
1	0	1	0	1	0
x	1	x	1	x	0
out	0	out	0	out	0
sym1	0	sym1	0	sym1	1
sym2	0	sym2	0	sym2	0
sym3	0	sym3	0	sym3	0

那么这个方程的计算结果刚好就是 $x*x-sym_1=0$ ，也就意味着这样的 $(\vec a_1, \vec b_1, \vec c_1)$ 和解向量是满足第一个约束（门电路）。其中：

$\vec a_1$ = [0, 1, 0, 0, 0, 0]
$\vec b_1$ = [0, 1, 0, 0, 0, 0]
$\vec c_1$ = [0, 0, 0, 1, 0, 0]

第二个约束（第二个门电路）

$\vec a_2$ = [0, 0, 0, 1, 0, 0]
$\vec b_2$ = [0, 1, 0, 0, 0, 0]
$\vec c_2$ = [0, 0, 0, 0, 1, 0]

第三个约束（第三个门电路）

$\vec a_3$ = [0, 1, 0, 0, 1, 0]
$\vec b_3$ = [1, 0, 0, 0, 0, 0]
$\vec c_3$ = [0, 0, 0, 0, 0, 1]

第四个约束（第四个门电路）

$\vec a_4$ = [5, 0, 0, 0, 0, 1]
$\vec b_4$ = [1, 0, 0, 0, 0, 0]
$\vec c_4$ = [0, 0, 1, 0, 0, 0]

汇总

$\vec a = \left\{ \begin{matrix} \vec a_1 \\ \vec a_2 \\ \vec a_3 \\ \vec a_4 \end{matrix} \right\} = \left\{ \begin{matrix} 0, 1, 0, 0, 0, 0 \\ 0, 0, 0, 1, 0, 0 \\ 0, 1, 0, 0, 1, 0 \\ 5, 0, 0, 0, 0, 1 \end{matrix} \right\}$

$\vec b = \left\{ \begin{matrix} \vec b_1 \\ \vec b_2 \\ \vec b_3 \\ \vec b_4 \end{matrix} \right\} = \left\{ \begin{matrix} 0, 1, 0, 0, 0, 0 \\ 0, 1, 0, 0, 0, 0 \\ 1, 0, 0, 0, 0, 0 \\ 1, 0, 0, 0, 0, 0 \end{matrix} \right\}$

$\vec c = \left\{ \begin{matrix} \vec c_1 \\ \vec c_2 \\ \vec c_3 \\ \vec c_4 \end{matrix} \right\} = \left\{ \begin{matrix} 0, 0, 0, 1, 0, 0 \\ 0, 0, 0, 0, 1, 0 \\ 0, 0, 0, 0, 0, 1 \\ 0, 0, 1, 0, 0, 0 \end{matrix} \right\}$

$\vec s=(1，x, out, sym_1, sym_2, sym_3)$

令 $P(X) = \vec s \cdot \vec a_X* \vec s \cdot \vec b_X- \vec s \cdot \vec c_X=0$ ，则当 $X=1，2，3，4$ 时，都满足 $\vec s \cdot \vec a_X* \vec s \cdot \vec b_X- \vec s \cdot \vec c_X=0$