R1CS

本文介绍零知识证明中的一对概念：R1CS和QAP

概述

zk-SNARKS是目前最常用的零知识证明系统，但是由于其复杂性，不能直接应用于任何计算问题，因此需要对计算问题进行一步步的转化，其中就包含了R1CS和QAP。

R1CS 全程 Rank-1 Con­straint Sys­tem，一阶约束系统，其本质是一个可计算的三元方程组。

而 QAP 全称 Qua­dratic Arith­metic Peoblem，二次算术问题，QAP 转换不仅可以将函数的代码转换为 QAP，还可以在转换的同时构建一个对应于代码输入的解（又称为 QAP 的 Wit­ness），之后再基于这个 wit­ness 构建一个实际的零知识证明系统。

本文的参考是V神

QAP

在V神的文章中，给出了一个例子：P希望向V证明其知道方程$x^3+x+5=35$的解（P知道这个方程的解，因此witness为$x=3$），接下来是如何转化为QAP问题

首先，我们用程序语言描述这个问题：

def find(x):
    y=x**3
    return y+x+5

Flattening

第一步就是将这个语言中的代码转换为下列两个操作

1.x=y（y可以是变量或数字）
2.x=y op z（op代表一种基本运算操作）

经过 Flat­ten­ing 后，上述的语言可以转换为下面这个结果

sym_1 = x * x
y = sym_1 * x
sym_2 = y + x
~out = sym_2 + 5

这里可以将上述转换后的每一行都理解为一个数学电路中的逻辑门（一个仅包含加法门和乘法门的电路），与原始代码相比，这里引入了两个中间变量 sym_1 和 sym_2，输出标记为 ~out，不难验证其与原始代码的等价性

~out = sym_2 + 5 = y + x + 5 = sym_1 * x + x + 5 = x * x * x + x + 5

R1CS

第二步需要将 Flat­ten­ing 的结果转化为一阶约束系统 R1CS，一个 R1CS 是一个由三个向量构成的向量组$(\vec a,\vec b,\vec c)$，假设 R1CS 的解也是一个向量，记为$\vec s$，则$\vec s$满足

$(\vec s \cdot \vec a)*(\vec s \cdot \vec b)-(\vec s \cdot \vec c)=0$

其中⋅⋅表示向量内积，∗∗表示算数乘法

举例，假设向量组和解向量分别如下：

$\vec a =[0,1,0,0,0,0]\\ \vec b=[0,1,0,0,0,0]\\ \vec c=[0,0,0,1,0,0]\\ \vec s=[1,3,35,9,27,30]$

此时这个$\vec s$满足R1CS

这个例子中只有一个约束条件（也即只有一个 R1CS），接下来需要将之前的每个逻辑门都转化为一个约束（也即将 Flat­ten­ing 之后的每一个语句都转化为一个 R1CS 向量组），转化的方法很简单，只需要声明何种运算与声明的参数是常量还是变量。

因此，将上述 Flat­ten­ing 的结果转化之前，需要先将所有用到的变量用解向量$\vec s$表示，根据前面的分析，需要有五个变量$(x,\sim out,sym\_1,y,sym\_2)$，此外还需要一个冗余变量表示数字 1，记为$\sim one$，因此得到解向量$\vec s$如下

$\vec s=[\sim one,x,\sim out,sym\_1,y,sym\_2]$

接下来看第一个逻辑门$sym\_1=x∗x$，其等价于$x∗x−sym\_1=0$，因此不难得出R1CS 向量组如下

$\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]\\$

然后第二个逻辑门$y=sym\_1∗x$同理，其等价于$sym\_1∗x−y=0$，得到第二个 R1CS 向量组

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

第三个逻辑门$sym_2=y+x$同理，其等价于$(y+x)∗1−sym_2=0$，得到第三个 R1CS 向量组

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

最后是第四个逻辑门$\sim out =sym\_2+5$同理，其等价于$(sym\_2+5)*1-(\sim out)=0$得到第四个 R1CS 向量组

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

此时之前的 wit­ness 为$x=3$，经过 R1CS 转换后 wit­ness 就转换为了使得这四个 R1CS 同时成立的解向量$\vec s$

$\vec s=[1,3,35,9,27,30]$

将上述结果整理一下，把每个 R1CS 中的三个向量分别整理成一个向量组

$A=\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)\\ B=\left( \begin{matrix} 0 & 1 & 0 &0 &0 &0\\ 0 & 1 & 0 &0 &0 &0\\ 1 & 0 & 0 &0 &1 &0\\ 1 & 0 & 0 &0 &0 &0 \end{matrix} \right)\\ C=\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)\\$

R1CS to QAP

下一步是将这个 R1CS 转换成 QAP 的形式，QAP 实现了与 R1CS 完全相同的逻辑，只不过使用的是多项式而不是向量内积，具体做法如下

在上述三个向量组A,B,C中，利用在每个$x$坐标处求多项式代表一个约束条件（每个向量组的第一个行向量代表$x=1$），将每个向量组的四个长度为 6 的行向量转换成六个长度为 4 的向量（六个阶为 3 的多项式）

也就是说，如果我们求出$x=1$处的多项式，我们就得到了第一组向量，如果我们求出$x=2$处的多项式，我们就得到第二组向量，以此类推

在每个$x$点处来评估不同的约束，每个向量组都有四个约束，因此我们分别用多项式在 $x=1,2,3,4$处来评估这四个向量组，然后使用拉格朗日差值公式来将 R1CS 转化为 QAP 形式

以向量组 A 举例，首先需要求出四个约束所对应的每个$\vec a$向量的第一个值的多项式，也就是对向量组 A 的第一列采用拉格朗日插值法，求过点(1,0),(2,0),(3,0),(4,5)四个点的多项式（可以用在线工具 Cubic Polynomial Generator 求解，或者自己写脚本也行），求得三阶多项式如下

$y_1=-5+9.166x-5x^2+0.833x^3$

将多项式的系数按$x$的阶数升序排列，得到系数向量(−5.0,9.166,−5.0,0.833)

不难验证，将$x=1,2,3,4$分别带入上述多项式，可以恢复向量组 A 的第一个列向量

同理可以求出剩下的17个系数向量

$A=\left( \begin{matrix} -5 & 9.166 & -5 &0.833\\ 8 & -11.333 & 5 &-0.666\\ 0 & 0 & 0 &0\\ -6 & 9.5 & -4 &0.5\\ 4 & -7 & 3.5 &-0.5\\ -1 & 1.833 & -1 &0.166\\ \end{matrix} \right)\\ B=\left( \begin{matrix} 3 & -5.166 & 2.5 &-0.333\\ -2 & 5.166 & -2.5 &0.333\\ 0 & 0 & 0 &0\\ 0 & 0 & 0 &0\\ 0 & 0 & 0 &0\\ 0 & 0 & 0 &0\\ \end{matrix} \right)\\ C=\left( \begin{matrix} 0 & 0 & 0 &0\\ 0 & 0 & 0 &0\\ -1 & 1.833 & -1 &0.166\\ 4 &-4.333 &1.5 &-0.166\\ -6 & 9.5 & -4 &0.5\\ 4 & -7 & 3.5 &-0.5 \end{matrix} \right)\\$

将$x=1$带入这些十八组系数构成的多项式，可以恢复出三个 R1CS 中第一个约束的三个向量(0,1,0,0,0,0),(0,1,0,0,0,0) 和(0,0,0,1,0,0)

将$x=2,3,4$带入这些多项式，则可以完全恢复三个 R1CS 向量组