Source: https://rareskills.io/zh-cn/post/r1cs-zkp

给定一个编码为 一阶约束系统（Rank 1 Constraint System） 的 算术电路（arithmetic circuit） ，我们有可能创建一个证明拥有见证（witness）的 ZK-proof，尽管它并不是简洁的（succinct）。本文将描述如何实现这一目标。

针对 R1CS 的零知识证明，其实现方式是将见证向量转换为有限域椭圆曲线点 ，并将每一行的阿达马乘积（Hadamard product）替换为 双线性配对（bilinear pairing） 。

给定一个 Rank 1 Constraint System，其中每个矩阵有 $n$ 行和 $m$ 列，我们将其写为

$\mathbf{L}\mathbf{a}\circ\mathbf{R}\mathbf{a}=\mathbf{O}\mathbf{a}$

<aside> 💡 💡 一句话理解：这行就是 R1CS 的『考试题与标准答案』。$\mathbf{a}$ 是你填的一整张答题卡（每个信号的取值），$\mathbf{L}$、$\mathbf{R}$、$\mathbf{O}$ 是三套评分规则。先用 $\mathbf{L}$、$\mathbf{R}$ 分别给答题卡打分得到两列分数，再让这两列分数『逐行相乘』，看看是不是正好等于用 $\mathbf{O}$ 打出来的那列分数。$\circ$（阿达马乘积）就是『对应位置各乘各的』，第 1 行配第 1 行、第 2 行配第 2 行，互不串台。每一行其实就对应电路里的一个乘法门，比如 $x\times y=z$。

</aside>

其中 $\mathbf{L}$ 、 $\mathbf{R}$ 、 $\mathbf{O}$ 是具有 $n$ 行和 $m$ 列的矩阵， $\mathbf{a}$ 是见证向量（包含对算术电路中每个信号满足条件的赋值）。向量 $\mathbf{a}$ 有 1 列和 $m$ 行， $\circ$ 表示逐元素乘法（阿达马乘积）。

展开后如下所示：

$\left[ \begin{array}{ccc} l_{1,1} & \cdots & l_{1,m} \\ \vdots & \ddots & \vdots \\ l_{n,1} & \cdots & l_{n,m} \end{array} \right] \left[ \begin{array}{c} a_1 \\ \vdots \\ a_m \end{array} \right] \circ \left[ \begin{array}{ccc} r_{1,1} & \cdots & r_{1,m} \\ \vdots & \ddots & \vdots \\ r_{n,1} & \cdots & r_{n,m} \end{array} \right] \left[ \begin{array}{c} a_1 \\ \vdots \\ a_m \end{array} \right]

\left[ \begin{array}{ccc} o_{1,1} & \cdots & o_{1,m} \\ \vdots & \ddots & \vdots \\ o_{n,1} & \cdots & o_{n,m} \end{array} \right] \left[ \begin{array}{c} a_1 \\ \vdots \\ a_m \end{array} \right]$

$= \left[ \begin{array}{ccc} a_1 l_{1,1} + \cdots + a_m l_{1,m} \\ \vdots \\ a_1 l_{n,1} + \cdots + a_m l_{n,m} \end{array} \right] \circ \left[ \begin{array}{ccc} a_1 r_{1,1} + \cdots + a_m r_{1,m} \\ \vdots \\ a_1 r_{n,1} + \cdots + a_m r_{n,m} \end{array} \right]

\left[ \begin{array}{ccc} a_1 o_{1,1} + \cdots + a_m o_{1,m} \\ \vdots \\ a_1 o_{n,1} + \cdots + a_m o_{n,m} \end{array} \right]$

$= \left[ \begin{array}{ccc} \sum_{i=1}^m a_i l_{1,i} \\ \sum_{i=1}^m a_i l_{2,i} \\ \vdots \\ \sum_{i=1}^m a_i l_{n,i} \end{array} \right] \circ \left[ \begin{array}{ccc} \sum_{i=1}^m a_i r_{1,i} \\ \sum_{i=1}^m a_i r_{2,i} \\ \vdots \\ \sum_{i=1}^m a_i r_{n,i} \end{array} \right]

\left[ \begin{array}{ccc} \sum_{i=1}^m a_i o_{1,i} \\ \sum_{i=1}^m a_i o_{2,i} \\ \vdots \\ \sum_{i=1}^m a_i o_{n,i} \end{array} \right]$

$= \begin{array}{ccc} \sum_{i=1}^m a_i l_{1,i} \sum_{i=1}^m a_i r_{1,i} = \sum_{i=1}^m a_i o_{1,i} \\ \sum_{i=1}^m a_i l_{2,i} \sum_{i=1}^m a_i r_{2,i} = \sum_{i=1}^m a_i o_{2,i} \\ \vdots \\ \sum_{i=1}^m a_i l_{n,i} \sum_{i=1}^m a_i r_{n,i} = \sum_{i=1}^m a_i o_{n,i} \end{array}$

<aside> 💡 💡 这里最绕的是那一堆 $\sum$ 符号，其实它只是『一行点乘』的紧凑写法。$\sum_{i=1}^m a_i l_{1,i}$ 意思是把第 1 条规则 $l_{1,1},l_{1,2},\dots$ 和你的答案 $a_1,a_2,\dots$ 对位相乘再全部加起来，得到一个数。举个小例子：规则 $[0,2,0]$ 配答案 $[5,7,9]$，算出来就是 $0\times5+2\times7+0\times9=14$。所以整个大矩阵等式，最后被压缩成了 $n$ 个普通的『左边的数 × 右边的数 = 结果的数』，每行一道乘法小题。

</aside>

在这种设置下，我们只需向验证者（verifier）提供向量 $\mathbf{a}$ ，就可以向其证明我们拥有一个满足该 R1CS 的见证向量 $\mathbf{a}$ ，但这里有一个明显的缺陷——这并不是一个零知识证明！

<aside> 💡 💡 为什么说这还不是零知识：因为你把整张答题卡 $\mathbf{a}$ 原原本本交给了验证者。这就像考官说『证明你会解这道题』，结果你直接把写满步骤和答案的草稿纸给了他——他确实信了，但你的秘密（比如那个私密的 $x$）也全曝光了。零知识的目标是：让他相信你会，却一个数字都看不到。下面就要动手把答案『锁起来』。

</aside>

R1CS 的零知识证明算法

如果我们将见证向量“加密”，即将其每个元素乘以 $G_1$ 或 $G_2$ ，数学运算依然能够正常进行！

<aside> 💡 💡 打个比方：把每个数字 $a$ 乘上椭圆曲线生成元 $G_1$，就像把它塞进一个『单向快递柜』变成 $aG_1$。别人能看到柜子，却打不开拿回原来的 $a$（这就是离散对数难题）。神奇的是，这种『锁』支持运算——柜子可以相加、可以整体乘一个公开系数，锁里的数字会跟着同步变化。所以矩阵乘法照样能在『锁住的状态』下进行，验证者全程不知道你锁的是几。

</aside>

为了理解这一点，考虑一下如果我们执行矩阵乘法：

$\begin{bmatrix} 1 & 2 \\ 3 & 4 \\ \end{bmatrix} \begin{bmatrix} 4 \\ 5 \end{bmatrix} = \begin{bmatrix} 14 \\ 32 \end{bmatrix}$