R1CS

R1CS是Rank 1 Constraint System的简称，包含三个矩阵和一个见证(witness)向量。可将任意算术电路转换成R1CS。

例子

考虑下面的算术电路$x^3+6x+12=out$。我们将其转换成R1CS。 首先，我们需要拆分出中间变量和约束：

1. $x_{sq}=x\cdot x$
2. $x_{cu}=x_{sq}\cdot x$
3. $out=x_{cu}+6x+12$ 然后，我们组建见证向量$s$： $s=[1,out,x,x_{sq},x_{cu}{]}^T$

对于每一个约束，我们可以得到三个向量$a,b,o$使得$<a,s>\cdot <b,s>=<o,s>$ 其中$<a,s>$表示向量$a$和$s$的点乘。

于是我们有： $a_1=[0,0,1,0,0],b_1=[0,0,1,0,0],o_1=[0,0,0,1,0]$ $a_2=[0,0,0,1,0],b_2=[0,0,1,0,0],o_2=[0,0,0,0,1]$ $a_3=[12,0,6,0,1],b_3=[1,0,0,0,0],o_3=[0,1,0,0,0]$ 将$a_i,b_i,o_i$各自堆叠起来，我们得到了最终的矩阵$A,B,O$满足： $As\circ Bs=Os$ 其中$\circ$表示逐元素乘法（Hadamard product）。

对于一个证明者，只需提供一个具体的witness向量:$s=[1,57,3,9,27]$ 对于验证者来说，只需验证上述等式$As\circ Bs=Os$成立。