Quadratic Arithmetic Program

R1CS 是由一系列三向量组 $(\overrightarrow{a},\overrightarrow{b},\overrightarrow{c})$ 组成的序列，R1CS 有一个解向量 $\overrightarrow{s}$ ，需要满足：
$$⟨\overrightarrow{a_i},\overrightarrow{s}⟩\times ⟨\overrightarrow{b_i},\overrightarrow{s}⟩-⟨\overrightarrow{c_i},\overrightarrow{s}⟩=0\text{for}\mathrm{\forall }i$$
其中 $⟨\cdot ,\cdot ⟩$ 表示两个向量的点积。

把多项式写为 $z=x(op)y$ 的形式，其中 $op$ 是加减乘除等运算：

1: sym_1 = arg1 * arg2
2: sym_2 = w * sym_1
3: sym_3 = 1 - w
4: sym_4 = arg1 + arg2
5: sym_5 = sym_3 * sym_4
6: v = sym_2 + sym_5
7: w = w * w

上面的形式即算数电路（Arithmetic circuit），这个过程称为拍平（Flatten）。

为了将所有操作都转成 $z=x(op)y$ 的形式，我们加入了 $sym\mathrm{\_}1,sym\mathrm{\_}2,\cdots sym\mathrm{\_}5$ 中间变量。

有一种简单的方法可以把拍平后的算术电路转移为 R1CS。把电路中涉及的所有变量（包含中间变量）组成的下面向量作为解向量：
$$\overrightarrow{s}=\left(\begin{array}{c}1\\ w\\ arg1\\ arg2\\ sym\mathrm{\_}1\\ sym\mathrm{\_}2\\ sym\mathrm{\_}3\\ sym\mathrm{\_}4\\ sym\mathrm{\_}5\\ v\end{array}\right)$$
注意，上面 解向量 $\overrightarrow{s}$ 的首个分量固定为数字 1， 这是为了编码常量而故意留的，下面会看到这点。

有了这个解向量后，我们可以按下面方法寻找出满足条件的一系列三向量组 $(\overrightarrow{a},\overrightarrow{b},\overrightarrow{c})$ 。

针对第 1 行的约束 $arg1\times arg2=sym\mathrm{\_}1$ ，可以设置：

$$\begin{array}{rl}\overrightarrow{a_0}& =[0,0,1,0,0,0,0,0,0,0]\\ \overrightarrow{b_0}& =[0,0,0,1,0,0,0,0,0,0]\\ \overrightarrow{c_0}& =[0,0,0,0,1,0,0,0,0,0]\end{array}$$

它满足 R1CS 的要求： $⟨\overrightarrow{a_0},\overrightarrow{s}⟩\times ⟨\overrightarrow{b_0},\overrightarrow{s}⟩-⟨\overrightarrow{c_0},\overrightarrow{s}⟩=0$ ，这容易验证，把 $\overrightarrow{a_0},\overrightarrow{b_0},\overrightarrow{c_0},\overrightarrow{s}$ 代入进来就是 $arg1\times arg2-sym\mathrm{\_}1=0$ ，这显然成立。

针对第 2 行的约束 $w\times sym\mathrm{\_}1=sym\mathrm{\_}2$ ，可以设置：

$$\begin{array}{rl}\overrightarrow{a_1}& =[0,1,0,0,0,0,0,0,0,0]\\ \overrightarrow{b_1}& =[0,0,0,0,1,0,0,0,0,0]\\ \overrightarrow{c_1}& =[0,0,0,0,0,1,0,0,0,0]\end{array}$$

它也满足 R1CS 的要求： $⟨\overrightarrow{a_1},\overrightarrow{s}⟩\times ⟨\overrightarrow{b_1},\overrightarrow{s}⟩-⟨\overrightarrow{c_1},\overrightarrow{s}⟩=0$ ，这容易验证，把 $\overrightarrow{a_1},\overrightarrow{b_1},\overrightarrow{c_1},\overrightarrow{s}$ 代入进来就是 $w\times sym\mathrm{\_}1-sym\mathrm{\_}2=0$ ，这显然成立。

针对第 3 行的约束 $(1-w)\times 1=sym\mathrm{\_}3$ ，可以设置：

$$\begin{array}{rl}\overrightarrow{a_2}& =[1,-1,0,0,0,0,0,0,0,0]\\ \overrightarrow{b_2}& =[1,0,0,0,0,0,0,0,0,0]\\ \overrightarrow{c_2}& =[0,0,0,0,0,0,1,0,0,0]\end{array}$$

它也满足 R1CS 的要求： $⟨\overrightarrow{a_2},\overrightarrow{s}⟩\times ⟨\overrightarrow{b_2},\overrightarrow{s}⟩-⟨\overrightarrow{c_2},\overrightarrow{s}⟩=0$ ，这容易验证，把 $\overrightarrow{a_2},\overrightarrow{b_2},\overrightarrow{c_2},\overrightarrow{s}$ 代入进来就是 $(1-w)\times 1-sym\mathrm{\_}3=0$ ，这显然成立。

针对第 4 行的约束 $(arg1+arg2)\times 1=sym\mathrm{\_}4$ ，可以设置：

$$\begin{array}{rl}\overrightarrow{a_3}& =[0,0,1,1,0,0,0,0,0,0]\\ \overrightarrow{b_3}& =[1,0,0,0,0,0,0,0,0,0]\\ \overrightarrow{c_3}& =[0,0,0,0,0,0,0,1,0,0]\end{array}$$

它也满足 R1CS 的要求： $⟨\overrightarrow{a_3},\overrightarrow{s}⟩\times ⟨\overrightarrow{b_3},\overrightarrow{s}⟩-⟨\overrightarrow{c_3},\overrightarrow{s}⟩=0$ ，这容易验证，把 $\overrightarrow{a_3},\overrightarrow{b_3},\overrightarrow{c_3},\overrightarrow{s}$ 代入进来就是 $(arg1+arg2)\times 1-sym\mathrm{\_}4=0$ ，这显然成立。

针对第 5 行的约束 $sym\mathrm{\_}3\times sym\mathrm{\_}4=sym\mathrm{\_}5$ ，可以设置：

$$\begin{array}{rl}\overrightarrow{a_4}& =[0,0,0,0,0,0,1,0,0,0]\\ \overrightarrow{b_4}& =[0,0,0,0,0,0,0,1,0,0]\\ \overrightarrow{c_4}& =[0,0,0,0,0,0,0,0,1,0]\end{array}$$

它也满足 R1CS 的要求： $⟨\overrightarrow{a_4},\overrightarrow{s}⟩\times ⟨\overrightarrow{b_4},\overrightarrow{s}⟩-⟨\overrightarrow{c_4},\overrightarrow{s}⟩=0$ ，这容易验证，把 $\overrightarrow{a_4},\overrightarrow{b_4},\overrightarrow{c_4},\overrightarrow{s}$ 代入进来就是 $sym\mathrm{\_}3\times sym\mathrm{\_}4-sym\mathrm{\_}5=0$ ，这显然成立。

针对第 6 行的约束 $(sym\mathrm{\_}2+sym\mathrm{\_}5)\times 1=v$ ，可以设置：

$$\begin{array}{rl}\overrightarrow{a_5}& =[0,0,0,0,0,1,0,0,1,0]\\ \overrightarrow{b_5}& =[1,0,0,0,0,0,0,0,0,0]\\ \overrightarrow{c_5}& =[0,0,0,0,0,0,0,0,0,1]\end{array}$$

它也满足 R1CS 的要求： $⟨\overrightarrow{a_5},\overrightarrow{s}⟩\times ⟨\overrightarrow{b_5},\overrightarrow{s}⟩-⟨\overrightarrow{c_5},\overrightarrow{s}⟩=0$ ，这容易验证，把 $\overrightarrow{a_5},\overrightarrow{b_5},\overrightarrow{c_5},\overrightarrow{s}$ 代入进来就是 $(sym\mathrm{\_}2+sym\mathrm{\_}5)\times 1-v=0$ ，这显然成立。

针对第 7 行的约束 $w\times w=w$ ，可以设置：

$$\begin{array}{rl}\overrightarrow{a_6}& =[0,1,0,0,0,0,0,0,0,0]\\ \overrightarrow{b_6}& =[0,1,0,0,0,0,0,0,0,0]\\ \overrightarrow{c_6}& =[0,1,0,0,0,0,0,0,0,0]\end{array}$$

它也满足 R1CS 的要求： $⟨\overrightarrow{a_6},\overrightarrow{s}⟩\times ⟨\overrightarrow{b_6},\overrightarrow{s}⟩-⟨\overrightarrow{c_6},\overrightarrow{s}⟩=0$ ，这容易验证，把 $\overrightarrow{a_6},\overrightarrow{b_6},\overrightarrow{c_6},\overrightarrow{s}$ 代入进来就是 $w\times w-w=0$ ，这显然成立。

上面这一系列三向量组 $(\overrightarrow{a},\overrightarrow{b},\overrightarrow{c})$ 组成的序列就是 R1CS：

A
[0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[1, -1, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 0, 0, 1, 0]
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0]

B
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0]

C
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0]

R1CS 是使用向量点积来实现约束，下面介绍如何把这些约束转换为 QAP。

把前面得到的 $\overrightarrow{a}$ 序列组成矩阵 $A$ ：
$$A=\left(\begin{array}{cccccccccc}0& 0& 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0& 0& 0& 0& 0\\ 1& -1& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 0& 0& 1& 0\\ 0& 1& 0& 0& 0& 0& 0& 0& 0& 0\end{array}\right)$$

设 $l_0(x)$ 是经过点 $(1,0),(2,0),(3,1),(4,0),(5,0),(6,0),(7,0)$ （注： $x$ 为 $1,2,\cdots ,7$ ，而 $y$ 值依次是 $A$ 的第 1 列的每个元素）的多项式，由拉格朗日插值公式（利用这个公式，可以在已经某未知函数经过某些点的情况下，还原出函数。当然不一定要用拉格朗日插值公式，其它多项式插值方法也可以）可得：
$$l_0(x)=\frac{x^6}{48}-\frac{25x^5}{48}+\frac{247x^4}{48}-\frac{1219x^3}{48}+\frac{389x^2}{6}-\frac{949x}{12}+35$$

设 $l_1(x)$ 是经过点 $(1,0),(2,1),(3,-1),(4,0),(5,0),(6,0),(7,1)$ （注： $x$ 为 $1,2,\cdots ,7$ ，而 $y$ 值依次是 $A$ 的第 2 列的每个元素）的多项式，由拉格朗日插值公式可得：
$$l_1(x)=-\frac{x^6}{36}+\frac{17x^5}{24}-\frac{515x^4}{72}+\frac{869x^3}{24}-\frac{6863x^2}{72}+\frac{1447x}{12}-55$$

使用类似的方法，可以求得：

$$\begin{array}{rl}{l}_2(x)& =-\frac{19x^6}{720}+\frac{151x^5}{240}-\frac{845x^4}{144}+\frac{1297x^3}{48}-\frac{11449x^2}{180}+\frac{1447x}{20}-28\\ l_3(x)& =-\frac{x^6}{36}+\frac{2x^5}{3}-\frac{113x^4}{18}+\frac{88x^3}{3}-\frac{2545x^2}{36}+82x-35\\ l_4(x)& =0\\ l_5(x)& =-\frac{x^6}{120}+\frac{11x^5}{60}-\frac{19x^4}{12}+\frac{41x^3}{6}-\frac{1849x^2}{120}+\frac{1019x}{60}-7\\ l_6(x)& =\frac{x^6}{48}-\frac{23x^5}{48}+\frac{69x^4}{16}-\frac{925x^3}{48}+\frac{134x^2}{3}-\frac{201x}{4}+21\\ l_7(x)& =0\\ l_8(x)& =-\frac{x^6}{120}+\frac{11x^5}{60}-\frac{19x^4}{12}+\frac{41x^3}{6}-\frac{1849x^2}{120}+\frac{1019x}{60}-7\\ l_9(x)& =0\end{array}$$

同样地，我们根据 R1CS 中的矩阵 $B$ 可得 $r_0(x),r_1(x),\cdots ,r_9(x)$ ；根据 R1CS 中的矩阵 $C$ 可得 $o_0(x),o_1(x),\cdots ,o_9(x)$ 。此外， $t(x)=(x-1)(x-2)(x-3)(x-4)(x-5)(x-6)(x-7)$ 。

上面例子中，假设 $v=6$ ，Prover 想证明他知道的那个解为 $w=1,arg1=2,arg2=3$ ，则可以计算出中间变量 $sym\mathrm{\_}1=6,sym\mathrm{\_}2=6,sym\mathrm{\_}3=0,sym\mathrm{\_}4=5,sym\mathrm{\_}5=0$ ，从而 R1CS 的解为：
$$\overrightarrow{s}=\left(\begin{array}{c}1\\ 1\\ 2\\ 3\\ 6\\ 6\\ 0\\ 5\\ 0\\ 6\end{array}\right)$$

这个解就是 QAP 的一个解（witness），即 $\{u_0,u_1,u_2,u_3,u_4,u_5,u_6,u_7,u_8,u_9\}=\{1,1,2,3,6,6,0,5,0,6\}$

注：Vitalik Buterin 在文章 Quadratic Arithmetic Programs: from Zero to Hero 中介绍了从 R1CS 到 QAP 的转换，且在 https://github.com/ethereum/research/blob/master/zksnark/qap_creator.py 中使用 Python 编写了相应的转换程序。