从R1CS构建零知识证明

给定一个算术电路，可以将其编码为等级1约束系统，从而创建一个有见证的ZK证明，尽管不是简洁的。本文描述了如何实现这一点。

对于R1CS的零知识证明是通过将见证向量转换为有限域椭圆曲线点，并将Hadamard乘积替换为每一行的双线性配对。

给定一个等级1约束系统，其中每个矩阵有$n$行和$m$列，我们将其表示为

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

其中 $\mathbf{L}$, $\mathbf{R}$, $\mathbf{O}$ 是具有 $n$ 行和 $m$ 列的矩阵，而 $\mathbf{a}$ 是见证向量（包含算术电路中每个信号的满足赋值）。向量 $\mathbf{a}$ 具有1列和$m$行，$\circ$是逐元素相乘（Hadamard乘积）。

扩展形式看起来是

$$ \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 \\ am \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 \\ am \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} a1 l{1,1} + \cdots + am l{1,m} \\ \vdots \\ a1 l{n,1} + \cdots + am l{n,m} \end{array} \right] \circ \left[ \begin{array}{ccc} a1 r{1,1} + \cdots + am r{1,m} \\ \vdots \\ a1 r{n,1} + \cdots + am r{n,m} \end{array} \right] = \left[ \begin{array}{ccc} a1 o{1,1} + \cdots + am o{1,m} \\ \vdots \\ a1 o{n,1} + \cdots + am o{n,m} \end{array} \right] $$

$$ = \left[ \begin{array}{ccc} \sum_{i=1}^m ai l{1,i} \\ \sum_{i=1}^m ai l{2,i} \\ \vdots \\ \sum_{i=1}^m ai l{n,i} \end{array} \right] \circ \left[ \begin{array}{ccc} \sum_{i=1}^m ai r{1,i} \\ \sum_{i=1}^m ai r{2,i} \\ \vdots \\ \sum_{i=1}^m ai r{n,i} \end{array} \right] = \left[ \begin{array}{ccc} \sum_{i=1}^m ai o{1,i} \\ \sum_{i=1}^m ai o{2,i} \\ \vdots \\ \sum_{i=1}^m ai o{n,i} \end{array} \right] $$

$$ = \begin{array}{ccc} \sum_{i=1}^m ai l{1,i} \sum_{i=1}^m ai r{1,i} = \sum_{i=1}^m ai o{1,i} \\ \sum_{i=1}^m ai l{2,i} \sum_{i=1}^m ai r{2,i} = \sum_{i=1}^m ai o{2,i} \\ \vdots \\ \sum_{i=1}^m ai l{n,i} \sum_{i=1}^m ai r{n,i} = \sum_{i=1}^m ai o{n,i} \end{array} $$

在此设置中，我们可以向验证者证明我们有一个满足R1CS的见证向量 $\mathbf{a}$，只需将向量$\mathbf{a}$提供给他们，但显然的缺陷是这不是一个零知识证明！

R1CS的零知识证明算法

如果我们通过将每个条目与$G_1$或$G_2$相乘来“加密”见证向量，那么数学仍然有效！

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

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

也可以得到：

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

第二次矩阵乘法中的两个椭圆曲线点的离散对数与第一次矩阵乘法的元素相同。

换句话说，每次我们将列向量与平方矩阵的一行相乘时，我们都会进行两个椭圆曲线点乘法和一次椭圆曲线加法。

椭圆曲线的符号

我们说 $[aG_1]_1$ 是由将域元素 $a$ 倍乘 $G_1$ 创建的 $\mathbb{G}_1$ 椭圆曲线点。我们说 $[aG_2]_2$ 是通过将 $a$ 乘以生成元 $G_2$ 生成的 $\mathbb{G}_2$ 椭圆曲线点。由于离散对数问题，我们无法从 $[aG_1]_1$ 或 $[aG_2]_2$ 中提取出 $a$。给定点 $A \in \mathbb{G}_1$ 和 $B \in \mathbb{G}_2$，我们说两个点的配对是 $A\bullet B$。

证明步骤

让我们通过将每个条目与生成元点 $G_1$ 相乘来加密我们的 $\mathbf{a}$ 向量，从而生成椭圆曲线点 $[a_iG_1]_1$。

对于矩阵 $\mathbf{L}$，我们做如下操作：

$$ \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{a...