本文解释了如何将一组算术约束转换为秩一约束系统 (Rank One Constraint System, R1CS)。

本文的重点在于实现：与其他资料相比，我们涵盖了在进行此类转换时更多的边界情况，讨论了优化方法，并解释了 Circom 库是如何实现它的。

先决条件

• 我们假设读者了解如何使用算术电路（zk circuits）来表示计算的有效性。
• 读者熟悉模算术 (modular arithmetic)。这里的所有操作都在有限域中进行，因此 $-5$ 实际上意味着 $5$ 模 $p$ 的加法逆元，而 $2/3$ 意味着 $3$ 模 $p$ 的乘法逆元乘以 $2$。

秩一约束系统 (Rank 1 Constraint System) 概述

秩一约束系统 (R1CS) 是一种算术电路，其要求是每个等式约束只能包含一次乘法（对加法的数量没有限制）。

这使得算术电路的表示能够兼容双线性配对 (bilinear pairings) 的使用。配对的输出 $G_1 \bullet G_2 \rightarrow G_T$ 无法再次进行配对，因为 $G_T$ 中的元素不能用作另一个配对输入的一部分。因此，我们每个约束只允许一次乘法。

见证向量 (The witness vector)

在算术电路中，见证 (witness) 是对满足方程约束的所有信号的赋值。

在秩一约束系统中，见证向量是一个 $1 \times n$ 的向量，其中包含了所有输入变量、输出变量以及中间变量的值。它表明你已经从头到尾执行了电路，并且知道输入、输出和所有的中间值。

按照惯例，第一个元素通常始终为 1，以使某些计算更加简便，我们稍后将对此进行演示。

例如，如果我们有约束条件

声称我们知道它的解，那么这必定意味着我们知道 $x$、$y$ 和 $z$。由于秩一约束系统要求每个约束只能进行一次乘法，上述多项式约束必须写成：

见证意味着我们不仅知道 $x$、$y$ 和 $z$，我们还必须知道这种展开形式中的每一个中间变量。具体来说，我们的见证是一个向量：

其中每一项的值都满足上述约束。

例如，

是一个有效的见证，因为当我们代入这些值时，

它满足以下约束

额外的 1 这一项在这个例子中没有被使用，它是为了方便起见，稍后我们将对其进行解释。

示例 1：将 $z = x \cdot y$ 转换为秩一约束系统

在我们的例子中，假设我们要证明 $41 \times 103 = 4223$。

因此，我们的见证向量是 $[1, 4223, 41, 103]$，作为对 $[1, z, x, y]$ 的赋值。

在创建 R1CS 之前，我们的约束需要呈现如下形式

Copy
result = left_hand_side × right_hand_side

幸运的是，它已经是了：

这显然是一个微不足道的例子，但通常从简单的例子开始是个不错的方法。

要创建一个有效的 R1CS，你需要一系列恰好包含一次乘法的公式。

稍后我们将讨论如何处理不恰好包含一次乘法的情况，比如 $z = x³$ 或 $z = x³ + y$。

我们的目标是创建一个具有以下形式的方程组：

其中 $\mathbf{O}$、$\mathbf{L}$ 和 $\mathbf{R}$ 是大小为 $n \times m$（$n$ 行 $m$ 列）的矩阵。

矩阵 $\mathbf{L}$ 编码乘号左侧的变量，$\mathbf{R}$ 编码乘号右侧的变量。$\mathbf{O}$ 编码结果变量。向量 $\mathbf{a}$ 是见证向量。

具体来说，$\mathbf{L}$、$\mathbf{R}$ 和 $\mathbf{O}$ 是列数与见证向量 $\mathbf{a}$ 相同的矩阵，并且每一列代表索引所使用的同一个变量。

因此，在我们的例子中，见证向量有 4 个元素 $(1, z, x, y)$，所以我们的每个矩阵将有 4 列，即 $m = 4$。

行数将对应于电路中约束的数量。在我们的例子中，我们只有一个约束：$z = x * y$，所以我们将只有一行，即 $n = 1$。

让我们直接来看答案，并解释我们是如何得到它的。

在这个例子中，矩阵中的每一项都作为一个指示变量，用来表示该列对应的变量是否存在。（严格来说，它是变量的系数，但我们稍后会讨论这一点）。

对于左侧项，$x$ 是乘法左侧存在的唯一变量，因此如果列代表 $[1, z, x, y]$，那么……

$\mathbf{L}$ 是 $[0, 0, 1, 0]$，因为 $x$ 存在，而其他所有变量都不存在。

$\mathbf{R}$ 是 $[0, 0, 0, 1]$，因为乘法右侧唯一的变量是 $y$，并且

$\mathbf{O}$ 是 $[0, 1, 0, 0]$，因为我们只在乘法的"输出"中拥有 $z$ 变量。

我们在任何地方都没有常量，所以表示 1 的列在所有地方都为零（我们稍后将讨论它何时非零）。

这个等式是正确的，我们可以用 Python 进行验证：

Copy
import numpy as np

# define the matrices
O = np.matrix([[0,1,0,0]])
L = np.matrix([[0,0,1,0]])
R = np.matrix([[0,0,0,1]])

# witness vector
a = np.array([1, 4223, 41, 103])

# Multiplication `*` is element-wise, not matrix multiplication.
# Result contains a bool indicating an element-wise indicator that the equality is true for that element.
result = np.matmul(O, a) == np.matmul(L, a) * np.matmul(R, a) 

# check that every element-wise equality is true
assert result.all(), "result contains an inequality"

你可能想知道这样做的意义何在，我们难道不是在用一种极不简洁的方式来说明 $41 \times 103 = 4223$ 吗？

你说得对。

R1CS 可能非常繁琐，但它们能很好地映射到二次算术程序 (Quadratic Arithmetic Programs, QAPs)，后者可以变得非常简洁。不过，我们在此不探讨 QAPs。

但这是 R1CS 的一个重要特点。R1CS 传达的信息与原始算术约束完全相同，但每个等式约束只有一次乘法。在这个例子中，我们只有一个约束，但我们将在下一个例子中添加更多。

示例 2：将 r = x * y * z * u 转换为 R1CS

在这个稍微复杂的例子中，我们现在需要处理中间变量。我们计算的每一行只能有一次乘法，因此我们必须将方程拆解如下：

并没有规定说我们必须这样拆解，以下方式同样有效：

在本例中，我们将使用第一种转换。

$\mathbf{L}$、$\mathbf{R}$ 和 $\mathbf{O}$ 矩阵的大小

因为我们要处理 7 个变量 $(r, x, y, z, u, v_1, v_2)$，所以我们的见证向量将有 8 个元素（第一个是常量 1），我们的矩阵将有 8 列。

因为我们有三个约束，所以矩阵将有 3 行。

左侧项和右侧项

这个例子将强烈强化“左侧项”和“右侧项”的概念。具体来说，$x$、$z$ 和 $v_1$ 是左侧项，而 $y$、$u$ 和 $v_2$ 是右侧项。

由左侧项构建矩阵 $\mathbf{L}$

让我们构建矩阵 A。我们知道它将有 3 行（因为有三个约束）和 8 列（因为有八个变量）。

我们的见证向量将被它相乘，因此让我们定义见证向量具有以下布局：

这告诉我们 $\mathbf{L}$ 的列代表什么：

$\mathbf{L}$ 的第一行

在第一行中，对于第一个左侧变量，我们有 $v₁ = xy$：

这意味着对于左侧，变量 $x$ 是存在的，而其他变量都不存在。因此，我们按照如下方式转换第一行：

回顾一下，$\mathbf{L}$ 的各列标签如下：

我们看到 $1$ 位于 $x$ 列中。

$\mathbf{L}$ 的第二行

继续往下看，我们发现方程组的左侧仅有 $z$ 存在。

因此，我们将那一行中除了代表 $z$ 的列以外的所有项都设为零。

$\mathbf{L}$ 的第三行

最后，在第三行的左侧操作数中，只有 $v₁$ 这一个存在的变量。

这就完成了矩阵 $\mathbf{L}$ 的构建：

下图应该能让这种映射关系更加清晰：

$\mathbf{L}$ 的另一种转换方法

我们也可以通过展开左侧值的方式来完成同样的练习：

展开为

我们可以这样做，因为添加零项并不会改变其值。我们只需要注意，展开的零变量需与我们定义的见证向量具有相同的“列”。

然后，如果我们提取出上述展开式中的系数（如方框所示），

我们就得到了刚才生成的相同的矩阵 $\mathbf{L}$。

由右侧项构建矩阵 $\mathbf{R}$

矩阵 $\mathbf{R}$ 代表我们方程的右侧项：

矩阵 $\mathbf{R}$ 必须用 1 来表示 $y$、$u$ 和 $v_2$。矩阵中的行对应于算术约束的行，即我们可以对约束（行）进行如下编号：

因此，第一行在 $y$ 列中有一个 1，第二行在 $u$ 列中有一个 1，第三行在 $v_2$ 列中有一个 1。其余一切均为零。

这就得出了如下的矩阵 $\mathbf{R}$：

该图说明了这种转换过程。

构建矩阵 $\mathbf{O}$

将确定矩阵 $\mathbf{O}$ 为

作为留给读者的练习（使用与前面矩阵一致的列标签）。

提醒一下，$\mathbf{C}$ 是从乘法的结果中推导出来的

并且列标签如下所示

为 $r = x \cdot y \cdot z \cdot u$ 检查我们的工作

Copy
import numpy as np

# enter the A B and C from above
L = np.matrix([[0,0,1,0,0,0,0,0],
              [0,0,0,0,1,0,0,0],
              [0,0,0,0,0,0,1,0]])
              
R = np.matrix([[0,0,0,1,0,0,0,0],
              [0,0,0,0,0,1,0,0],
              [0,0,0,0,0,0,0,1]])
              
O = np.matrix([[0,0,0,0,0,0,1,0],
              [0,0,0,0,0,0,0,1],
              [0,1,0,0,0,0,0,0]])

# random values for x, y, z, and u
import random
x = random.randint(1,1000)
y = random.randint(1,1000)
z = random.randint(1,1000)
u = random.randint(1,1000)

# compute the algebraic circuit
r = x * y * z * u
v1 = x*y
v2 = z*u

# create the witness vector
a = np.array([1, r, x, y, z, u, v1, v2])

# element-wise multiplication, not matrix multiplication
result = np.matmul(O, a) == np.multiply(np.matmul(L, a), np.matmul(R, a))

assert result.all(), "system contains an inequality"

示例 3：与常量相加

如果我们想要为以下方程构建一个秩一约束系统呢？

这正是 1 这一列派上用场的地方。

加法是免费的

在 ZK-SNARKs 的背景下，你可能听说过“加法是免费的”这种说法。这意味着当有加法操作时，我们不需要创建一个额外的约束。

我们可以将上述公式写成

但那会使我们的 R1CS 变得比实际需要的更大。

相反，我们可以将其写成

这样当我们用见证向量将 $\mathbf{a}$ 与 $\mathbf{O}$ 相乘时，变量 $z$ 和常量 $-2$ 就会自动“结合”在一起。

我们的见证向量形式为 [1, z, x, y]，因此我们的矩阵 $\mathbf{L}$、$\mathbf{R}$ 和 $\mathbf{O}$ 如下所示：

只要存在加法常量，我们就只需将它们放置在 $1$ 所在的列中，按照惯例，这是第一列。

再次，让我们对我们的数学计算进行一些单元测试：

Copy
import numpy as np
import random

# Define the matrices
L = np.matrix([[0,0,1,0]])
R = np.matrix([[0,0,0,1]])
O = np.matrix([[-2,1,0,0]])

# pick random values to test the equation
x = random.randint(1,1000)
y = random.randint(1,1000)
z = x * y + 2 # witness vector
a = np.array([1, z, x, y])

# check the equality
result = O.dot(a) == np.multiply(np.matmul(L, a), R.dot(a))
assert result.all(), "result contains an inequality"

示例 4：与常量相乘

在上面所有的例子中，我们从未将变量与常量相乘。这就是为什么 R1CS 中的项始终为 1。正如你可能从上一个例子中猜到的那样，矩阵中的项就是变量所乘常量的相同值，如下例所示。

让我们求出以下方程的解

请注意，当我们说“每个约束只有一次乘法”时，我们指的是两个变量之间的乘法。与常量相乘并不是“真正”的乘法，因为它实际上只是同一个变量的重复相加。

以下解决方案是有效的，但会创建不必要的行：

更优的解决方案如下：

使用更优的解决方案，我们的见证向量形式将为 [1, out, x, y]。

矩阵的定义将如下：

在 R1CS 形式中，象征性地将上述矩阵乘以 [1, z, x, y] 就能还原我们最初的方程：

因此我们知道自己对 $\mathbf{L}$、$\mathbf{R}$ 和 $\mathbf{O}$ 的设置是正确的。

在这里，我们有一行（约束）和一个“真正”的乘法。作为一个通用的规则：

秩一约束系统中的约束数量应该等于非常量乘法的数量。

示例 5：大型约束

让我们做一些不那么简单的练习，把上面学到的东西都结合起来

假设我们有以下约束：

我们将其拆解如下：

请注意所有的加法项是如何移到左边的（这也是我们在前面加法示例中所做的，但在这里更为明显）。

在第三行中将右侧保留为 $5xy$ 是随意的。我们可以两边同时除以 5，并将最终的约束变为

然而这并不会改变见证向量，因此两者都是有效的。由于所有计算都是在有限域中进行的，此操作实际上是将左侧和右侧同时乘以 5 的乘法逆元。

我们的见证向量形式将是

并且我们的矩阵将有三行，因为我们有三个约束：

我们用红色标记了输出 $\mathbf{O}$，用绿色标记了左侧 $\mathbf{L}$，并用紫色标记了右侧 $\mathbf{R}$。这就产生了以下矩阵：

及其列标签

像往常一样，我们来检查一下我们的计算。

Copy
import numpy as np
import random

# Define the matrices
L = np.array([[0,0,3,0,0,0],
               [0,0,0,0,1,0],
               [0,0,5,0,0,0]])

R = np.array([[0,0,1,0,0,0],
               [0,0,0,1,0,0],
               [0,0,0,1,0,0]])

O = np.array([[0,0,0,0,1,0],
               [0,0,0,0,0,1],
               [-3,1,1,2,0,-1]])

# pick random values for x and y
x = random.randint(1,1000)
y = random.randint(1,1000)

# this is our orignal formula
out = 3 * x * x * y + 5 * x * y - x - 2 * y + 3 # the witness vector with the intermediate variables inside
v1 = 3*x*x
v2 = v1 * y
w = np.array([1, out, x, y, v1, v2])

result = O.dot(w) == np.multiply(L.dot(w),R.dot(w))
assert result.all(), "result contains an inequality"

秩一约束系统并不要求以单个多项式为起点

为了保持简单，我们一直使用形如 $z = xy + ...$ 的例子，但大多数现实中的算术约束将是一组算术约束，而不是单一的一个。

例如，假设我们要证明一个数组 $[x₁, x₂, x₃, x₄]$ 是二进制形式的，且 $v$ 小于 16。这组约束条件将是

为了将其转化为秩一约束系统，我们注意到最后一行没有任何乘法，因此我们可以将 $x_1$ 代入第一个约束条件中：

假设我们的见证向量是 $[1, v, x_1, x_2, x_3, x_4]$，我们可以如下创建 R1CS：

进行代换并非绝对必要，但它可以为 R1CS 节省一行。在后面的小节中，我们将展示一个不做代换的有效 R1CS。

R1CS 中的所有操作都在对素数取模下进行

在上述例子中，为了简便起见，我们使用了传统算术，但现实世界中的实现会使用模算术。

原因很简单：编码像 2/3 这样的数字会导致表现不佳的浮点数，而浮点数计算密集且极易出错。

如果我们在对一个素数（比如 23）取模的条件下进行所有数学运算，那么编码 $2/3$ 就变得非常直接。它等同于 $2 \cdot 3^{-1}$，在模算术中，乘以 2 和求负 1 次方都是非常直接的操作。

Circom 实现

在 Circom（一种用于构建秩一约束系统的语言）中，有限域使用的是素数 21888242871839275222246405745257275088548364400416034343698204186575808495617（这等于我们在有限域上的椭圆曲线 (Elliptic Curves over Finite Fields)中所讨论的 BN128 曲线的阶）。

这意味着在那种表示下，$-1$ 是

Copy
p = 21888242871839275222246405745257275088548364400416034343698204186575808495617

# 1 - 2 = -1
(1 - 2) % p

# 21888242871839275222246405745257275088548364400416034343698204186575808495616

out = x * y 的 Circom 实现

如果我们在 Circom 中编写 out = x * y，它看起来会像下面这样：

Copy
pragma circom 2.0.0;

template Multiply2() {
    signal input x;
    signal input y;
    signal output out;

    out <== x * y;
 }

component main = Multiply2();

让我们将其转换为一个 R1CS 文件，并打印该 R1CS 文件：

Copy
circom multiply2.circom --r1cs --sym
snarkjs r1cs print multiply2.r1cs

我们得到如下输出：

这看起来与我们的 R1CS 解决方案有很大不同，但它实际上编码的是相同的信息。

以下是 Circom 实现中的不同之处：

• 值为零的列不会被打印
• Circom 将 $\mathbf{O}\mathbf{a} = \mathbf{L}\mathbf{a}\circ\mathbf{R}\mathbf{a}$ 写成 $\mathbf{L}\mathbf{a}\circ\mathbf{R}\mathbf{a} - \mathbf{O}\mathbf{a} = \mathbf{0}$

那么那个实际上代表 -1 的 21888242871839275222246405745257275088548364400416034343698204186575808495616 又是怎么回事呢？

Circom 的解决方案是

尽管负 1 可能有些出人意料，但配合见证向量 [1 out x y]，这实际上与 $\mathbf{L}\mathbf{a}\circ\mathbf{R}\mathbf{a} - \mathbf{O}\mathbf{a} = \mathbf{0}$ 的形式是一致的。（我们稍后就会看到，Circom 确实使用了这种列分配方式）。

你可以代入 $x$、$y$ 和 out 的值，就会发现 $\mathbf{L}\mathbf{a}\circ\mathbf{R}\mathbf{a} - \mathbf{O}\mathbf{a} = \mathbf{0}$ 这个等式是成立的。

让我们来看看 Circom 的变量到列的分配方式。让我们使用 Wasm 求解器重新编译我们的电路：

Copy
circom multiply2.circom --r1cs --wasm --sym

cd multiply2_js/

我们创建 input.json 文件

Copy
echo '{"x": "11", "y": "9"}' > input.json

然后计算见证向量

Copy
node generate_witness.js multiply2.wasm input.json witness.wtns

snarkjs wtns export json witness.wtns witness.json

cat witness.json

我们得到以下结果：

很明显，Circom 使用了与我们一直以来的相同的列布局：[1, out, x, y]，因为在我们的 input.json 中，$x$ 被设为 $11$，$y$ 被设为 $9$。

如果我们使用 Circom 生成的见证向量（为了可读性，将那个巨大的数字替换为 -1），那么我们会发现 Circom 的 R1CS 是正确的

对于 $x$，$\mathbf{L}$ 有一个系数 $-1$；对于 $y$，$\mathbf{R}$ 有一个系数 $+1$；对于 $\text{out}$，$\mathbf{O}$ 有 $-1$。在模数形式下，这与上面终端输出的内容完全相同：

检查我们其余的工作

作为复习，我们探讨过的公式包括

我们在上一节中刚刚完成了 (1)，对于本节，我们将说明“非常量乘法的数量即为约束的数量”这一原则。

(2) 的电路如下：

Copy
pragma circom 2.0.8;

template Multiply4() {
    signal input x;
    signal input y;
    signal input z;
    signal input u;
    
    signal v1;
    signal v2;
    
    signal out;
    
    v1 <== x * y;
    v2 <== z * u;
    
    out <== v1 * v2;
}

component main = Multiply4();

有了到目前为止我们所讨论的一切，Circom 的输出和注释应该是不言自明的。

考虑到这一点，我们的其他公式应该具备如下的约束数量：

编写 Circom 电路并验证上述内容将作为留给读者的练习。

计算 R1CS 并不需要见证向量

请注意，在 Circom 代码中，我们在计算 R1CS 之前从未提供过见证向量。我们早些时候提供见证向量是为了让例子不那么抽象，且易于检查我们的计算，但这并非必需。这一点非常重要，因为如果验证者（verifier）需要见证向量来构建 R1CS，那么证明者（prover）就不得不把隐藏的解泄露出去！

当我们提到“见证向量”时，我们指的是一个填满具体数值的向量。验证者知道见证向量的“结构”，即变量到列的分配方式，但他并不知道具体的数值。

即使未经优化，R1CS 依然有效

从多项式到 R1CS 的有效转换并不是唯一的。你可以用更多的约束条件来编码同一个问题，但这种方式效率较低。以下是一个例子。

在一些 R1CS 教程中，像

这样的公式的约束被转换成了