零知识证明（13）：R1CS与QAP

概述

接下来的文章逐渐进入zk-SNARKs等目前常用的零知识证明系统，但在正式介绍之前，先用几篇文章简要介绍一些预备知识

由于zk-SNARKs不能直接应用于任何计算问题，因此需要将计算问题一步步的转化为zk-SNARKs，以便对问题进行操作，其中就包含了R1CS和QAP

R1CS全程Rank-1 Constraint System，一阶约束系统，其本质是一个方程组

而QAP全称Quadratic Arithmetic Peoblem，二次算术问题，QAP转换不仅可以将函数的代码转换为QAP，还可以在转换的同时构建一个对应于代码输入的解（又称为QAP的Witness），之后再基于这个witness构建一个实际的零知识证明系统（这个过程极其复杂，会在后续的文章中介绍）

接下来以V神的文章$[1]$中的例子来说明，加入了一些个人的理解

QAP问题

比如，Prover希望向Verifier证明其知道方程$x^3+x+5=35$的解（P知道$x=3$为方程的解，因此witness为$x=3$），接下来看一下如何进行QAP转换

首先将该方程用一种特殊的程序设计语言描述

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

需要注意的是，这个特殊的程序设计语言仅支持最基本的算术运算（加减乘除）和常数次幂的运算（如当$c$为常数时可以计算$x^c$，但$c$不能为变量或未知数），此外，该语言还对计算步骤和逻辑有限制，也即不允许出现循环，不支持模运算$%$$%$和比较运算（$<,>,geq,leq,==,!=$），因为在有限循环群算法中没有直接进行模运算或比较的有效方法，如果确实存在的话，则意味着破解椭圆曲线的速度比二进制搜索和中国剩余定理还要快得多

（插个题外话，若想要支持模运算和比较运算，可以给这个特殊的语言增加位分解功能，使其作为一种辅助输入，从而达到相关的目的，在此不作深入讨论）

Flattening

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

1. x = y（其中y可以是变量或数字）
2. x = y (op) z （其中op表示加减乘除四种基本的算术运算，z可以是常量，变量或者一个表达式）

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

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

第二步需要将Flattening的结果转化为一阶约束系统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 $$

其中$\cdot$表示向量内积，$*$表示算数乘法

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

$$ \begin{matrix}\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] \end{matrix} $$

不难验证$\vec s$满足这个R1CS

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

因此，将上述Flattening的结果转化之前，需要先将所有用到的变量用解向量$\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向量组如下

$$ \begin{matrix}\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] \end{matrix} \tag 1 $$

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

$$ \begin{matrix}\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] \end{matrix} \tag 2 $$

第三个逻辑门$sym\_2 = y + x$同理，其等价于$(y + x)*1-sym\_2 = 0$，得到第三个R1CS向量组

$$ \begin{matrix}\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] \end{matrix} \tag 3 $$

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

$$ \begin{matrix}\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] \end{matrix} \tag 4 $$

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

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

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

$$ A=\begin{pmatrix} 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{pmatrix} \\ ,B=\begin{pmatrix} 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{pmatrix} \\ ,C=\begin{pmatrix} 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{pmatrix} $$

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_{Ploy}=\begin{pmatrix} -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{pmatrix} \\ ,B_{Ploy}=\begin{pmatrix} 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{pmatrix} \\ ,C_{Ploy}=\begin{pmatrix} 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{pmatrix} $$

将$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向量组

Check QAP

从R1CS转化为QAP后，此时可以通过多项式的内积运算来同时检查所有的约束而不是像R1CS那样单独的检查每一个约束，就像下图所示

需要说明的是，得到的多项式本身不一定是零（大多数情况下显然不是），因为其可能在“与逻辑门相对应的点”以外的点等于其他值，但只要在“与逻辑门相对应的点”上等于零就没问题了，因此为了检查正确性，不需要对每个逻辑门上对应的点计算其多项式$t=(A\cdot s) *(B\cdot s)-(C\cdot s)$，而只需要用一个多项式$Z(x)=(x-1)(x-2)(x-3)(x-4)$除t，若可以整除，说明结果没有余数，也即验证是通过的，因为$Z(x)$是通过所有约束条件与对应的点算出来的，这种等价形式可以很大程度上减少了计算的开销

似乎说的有点绕，简单来说就是，检查多项式$A(x)*B(x)-C(x)$在$x=1,2,3,4$处是否均等于0，等价于这个多项式是否能被$Z(x)=(x-1)(x-2)(x-3)(x-4)$整除，简单的代数原理

之前提到的解向量$\vec s= [1, 3, 35, 9, 27, 30]$，这里将解向量分别与三个系数多项式做内积，也即

$$ A(x)*B(x)-C(x)=(A_{Ploy} \cdot \vec s)*(B_{Ploy} \cdot \vec s)-(C_{Ploy} \cdot \vec s) $$

用之前得到的三个多项式向量组分别与解向量$\vec s$做内积，以$A_{Ploy}$为例，计算过程如下

$$ \begin{matrix} (-5) * 1 + 8 * 3 + 0 * 35 +(- 6) * 9 + 4 * 27 +(- 1) * 30=43\\ 9.166 * 1 +(- 11.333) * 3 + 0 * 35 + 9.5 * 9 +(- 7) * 27 + 1.833 * 30=-73.333&\\ (-5)*1 +5*3+0*35+(-4)*9+3.5*27+(-1)*30=38.5\\ 0.833*1+(-0.666)*3+0*35+0.5*9+(-0.5)*27+).166*30=-5.166 \end{matrix} $$

因此得到

$$ A_{Ploy} \cdot \vec s=(43, -73.333, 38.5, -5.166) $$

也即

$$ A(x)= -5.166 x^3 + 38.5 x^2 - 73.333 x + 43 $$

注意多项式的系数向量按$x$的阶数升序排序

同理可得到

$$ \begin{matrix}B_{Ploy} \cdot \vec s=(-3, 10.333, -5, 0.666),B(x)= 0.666 x^3 - 5 x^2 + 10.333 x - 3\\ C_{Ploy} \cdot \vec s=(-41, 71.666, -24.5, 2.833),C(x)= 2.833 x^3 - 24.5 x^2 + 71.666 x - 41 \end{matrix} $$

则

$$ t=(A\cdot s) *(B\cdot s)-(C\cdot s)=(-88, 592.652, -1063.75, 805.789, -294.72, 51.471, -3.441) $$

此处系数仍然按$x$的阶数升序排列

然后$Z(x)=(x-1)(x-2)(x-3)(x-4)$，也即$Z_{Ploy}=(24,-50,35,-10,1)$，不难验证

$$ H=t/Z=(-3.666,17.055,-3.444) $$

此处$H$必须是没有任何余数，也即$t/Z_{Ploy}$必须是整除

经过上面的步骤，我们得到了QAP的解，如果我们试图伪造R1CS中的一个变量，而这个R1CS会得到另一个QAP的解，例如将解向量的最后一个数30改为31，此时得到的多项式$t$不再是$Z$的倍数

小结

到这里zk-SNARKs的一个基本的组件介绍完毕了，之后的工作主要围绕优化方式展开，不难看出上面的计算中出现了大量的小数，采用小数运算的话会因为其精度导致计算误差，然而在实际中我们会在有限域上做算术运算，这样结果都是整数，从而也就不存在误差了

本系列文章撰写于研一，受笔者知识面与理解能力的局限，部分概念与定理的表述难免有不准确与不严谨的地方，烦请各位专业人士斧正

参考文章

$[1]$浅谈零知识证明之二：简短无交互证明（SNARK）

$[2]$Quadratic Arithmetic Programs: from Zero to Hero - Vitalik Buterin

$[3]$对QAP深入浅出的分析

$[4]$白话零知识证明（二）- ViviCheung

$[5]$ （以）Odeb Gol­dre­ich 著；温巧燕，杨义先译。密码学基础 $[M]$. 北京：人民邮电出版社.2003.

$[6]$ Zero-Knowledge Proof-Wiki

$[7]$ The 9th BIU Winter School on Cryptography | BIU Cyber Center