将代数电路转换为 R1CS（秩一约束系统）

Last updated on Jan 22, 2026

本文解释了如何将一组算术约束转换为秩一约束系统 (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} ∙ G_{2} \to G_{T}$ 无法再次进行配对，因为 $G_{T}$ 中的元素不能用作另一个配对输入的一部分。因此，我们每个约束只允许一次乘法。

见证向量 (The witness vector)

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

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

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

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

z = x^{2} y

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

\begin{matrix} v_{1} = x x \\ z = v_{1} y \end{matrix}

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

[1, z, x, y, v_{1}]

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

例如，

[1, 18, 3, 2, 9]

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

[constant = 1, z = 18, x = 3, y = 2, v_{1} = 9]

它满足以下约束

\begin{matrix} v_{1} = x * x \to 9 = 3 \cdot 3 \\ z = v_{1} * y \to 18 = 9 \cdot 2 \end{matrix}

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

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

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

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

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

result = left_hand_side × right_hand_side

幸运的是，它已经是了：

\underset{result}{\underset{⏟}{z}} = \underset{left hand side}{\underset{⏟}{x}} \times \underset{right hand side}{\underset{⏟}{y}}

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

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

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

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

𝐎 𝐚 = 𝐋 𝐚 \circ 𝐑 𝐚

其中 $𝐎$ 、 $𝐋$ 和 $𝐑$ 是大小为 $n \times m$ （ $n$ 行 $m$ 列）的矩阵。

矩阵 $𝐋$ 编码乘号左侧的变量， $𝐑$ 编码乘号右侧的变量。 $𝐎$ 编码结果变量。向量 $𝐚$ 是见证向量。

具体来说， $𝐋$ 、 $𝐑$ 和 $𝐎$ 是列数与见证向量 $𝐚$ 相同的矩阵，并且每一列代表索引所使用的同一个变量。

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

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

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

𝐎 𝐚 = 𝐋 𝐚 \circ 𝐑 𝐚

\underset{𝐎}{\underset{⏟}{[\begin{matrix} 0 & 1 & 0 & 0 \end{matrix}]}} 𝐚 = \underset{𝐋}{\underset{⏟}{[\begin{matrix} 0 & 0 & 1 & 0 \end{matrix}]}} 𝐚 \circ \underset{𝐑}{\underset{⏟}{[\begin{matrix} 0 & 0 & 0 & 1 \end{matrix}]}} 𝐚

[\begin{matrix} 0 & 1 & 0 & 0 \end{matrix}] [\begin{matrix} 1 \\ 4223 \\ 41 \\ 103 \end{matrix}] = [\begin{matrix} 0 & 0 & 1 & 0 \end{matrix}] [\begin{matrix} 1 \\ 4223 \\ 41 \\ 103 \end{matrix}] \circ [\begin{matrix} 0 & 0 & 0 & 1 \end{matrix}] [\begin{matrix} 1 \\ 4223 \\ 41 \\ 103 \end{matrix}]

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

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

$𝐋$ 是 $[0, 0, 1, 0]$ ，因为 $x$ 存在，而其他所有变量都不存在。

$𝐑$ 是 $[0, 0, 0, 1]$ ，因为乘法右侧唯一的变量是 $y$ ，并且

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

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

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

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

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

\begin{matrix} v_{1} & = x y \\ v_{2} & = z u \\ r & = v_{1} v_{2} \end{matrix}

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

\begin{matrix} v_{1} & = x y \\ v_{2} & = v_{1} z \\ r & = v_{2} u \end{matrix}

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

$𝐋$ 、 $𝐑$ 和 $𝐎$ 矩阵的大小

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

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

左侧项和右侧项

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

\underset{Output Terms}{\underset{⏟}{\begin{matrix} v_{1} \\ v_{2} \\ r \end{matrix}}} \begin{matrix} = \\ = \\ = \end{matrix} \underset{Left Hand Terms}{\underset{⏟}{\begin{matrix} x \\ z \\ v_{1} \end{matrix}}} \begin{matrix} \times \\ \times \\ \times \end{matrix} \underset{Right Hand Terms}{\underset{⏟}{\begin{matrix} y \\ u \\ v_{2} \end{matrix}}}

由左侧项构建矩阵 $𝐋$

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

[\begin{matrix} l_{1,2} & l_{1,3} & l_{1,4} & l_{1,5} & l_{1,6} & l_{1,7} & l_{1,8} \\ l_{2,2} & l_{2,3} & l_{2,4} & l_{2,5} & l_{2,6} & l_{2,7} & l_{2,8} \\ l_{3,2} & l_{3,3} & l_{3,4} & l_{3,5} & l_{3,6} & l_{3,7} & l_{3,8} \end{matrix}]

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

[\begin{matrix} 1 & r & x & y & z & u & v_{1} & v_{2} \end{matrix}]

这告诉我们 $𝐋$ 的列代表什么：

𝐋 = [\begin{matrix} l_{1, 1} & l_{1, r} & l_{1, x} & l_{1, y} & l_{1, z} & l_{1, u} & l_{1, v_{1}} & l_{1, v_{2}} \\ l_{2, 1} & l_{2, r} & l_{2, x} & l_{2, y} & l_{2, z} & l_{2, u} & l_{2, v_{1}} & l_{2, v_{2}} \\ l_{3, 1} & l_{3, r} & l_{3, x} & l_{3, y} & l_{3, z} & l_{3, u} & l_{3, v_{1}} & l_{3, v_{2}} \end{matrix}]

$𝐋$ 的第一行

在第一行中，对于第一个左侧变量，我们有 $v_{1} = x y$ ：

\begin{matrix} v_{1} \\ v_{2} \\ r \end{matrix} \begin{matrix} = \\ = \\ = \end{matrix} \underset{𝐋}{\begin{matrix} x \\ z \\ v_{1} \end{matrix}} \begin{matrix} \times \\ \times \\ \times \end{matrix} \begin{matrix} y \\ u \\ v_{2} \end{matrix}

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

𝐋 = [\begin{matrix} 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ l_{2, 1} & l_{2, r} & l_{2, x} & l_{2, y} & l_{2, z} & l_{2, u} & l_{2, v_{1}} & l_{2, v_{2}} \\ l_{3, 1} & l_{3, r} & l_{3, x} & l_{3, y} & l_{3, z} & l_{3, u} & l_{3, v_{1}} & l_{3, v_{2}} \end{matrix}]

回顾一下， $𝐋$ 的各列标签如下：

[\begin{matrix} 1 & r & x & y & z & u & v_{1} & v_{2} \end{matrix}]

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

$𝐋$ 的第二行

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

\begin{matrix} v_{1} \\ v_{2} \\ r \end{matrix} \begin{matrix} = \\ = \\ = \end{matrix} \underset{𝐋}{\begin{matrix} x \\ z \\ v_{1} \end{matrix}} \begin{matrix} \times \\ \times \\ \times \end{matrix} \begin{matrix} y \\ u \\ v_{2} \end{matrix}

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

𝐋 = [\begin{matrix} 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ l_{3, 1} & l_{3, r} & l_{3, x} & l_{3, y} & l_{3, z} & l_{3, u} & l_{3, v_{1}} & l_{3, v_{2}} \end{matrix}]

$𝐋$ 的第三行

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

\begin{matrix} v_{1} \\ v_{2} \\ r \end{matrix} \begin{matrix} = \\ = \\ = \end{matrix} \underset{𝐋}{\begin{matrix} x \\ z \\ v_{1} \end{matrix}} \begin{matrix} \times \\ \times \\ \times \end{matrix} \begin{matrix} y \\ u \\ v_{2} \end{matrix}

这就完成了矩阵 $𝐋$ 的构建：

𝐋 = [\begin{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 \end{matrix}]

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

\begin{matrix} v_{1} \\ v_{2} \\ r \end{matrix} \begin{matrix} = \\ = \\ = \end{matrix} \underset{𝐋}{\begin{matrix} x \\ z \\ v_{1} \end{matrix}} \begin{matrix} \times \\ \times \\ \times \end{matrix} \begin{matrix} y \\ u \\ v_{2} \end{matrix} \begin{matrix} \begin{matrix} \begin{matrix} 1 & r & x & y & z & u & v_{1} & v_{2} \end{matrix} \end{matrix} \\ \begin{matrix} [\begin{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 \end{matrix}] \end{matrix} \end{matrix}

$𝐋$ 的另一种转换方法

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

\begin{matrix} v_{1} \\ v_{2} \\ r \end{matrix} \begin{matrix} = \\ = \\ = \end{matrix} \begin{matrix} x \\ z \\ v_{1} \end{matrix} \begin{matrix} \times \\ \times \\ \times \end{matrix} \begin{matrix} y \\ u \\ v_{2} \end{matrix}

展开为

\begin{matrix} v_{1} & = (0 \cdot 1 + 0 \cdot r + 1 \cdot x + 0 \cdot y + 0 \cdot z + 0 \cdot u + 0 \cdot v_{1} + 0 \cdot v_{2}) \times y \\ v_{2} & = (0 \cdot 1 + 0 \cdot r + 0 \cdot x + 0 \cdot y + 1 \cdot z + 0 \cdot u + 0 \cdot v_{1} + 0 \cdot v_{2}) \times u \\ r & = (0 \cdot 1 + 0 \cdot r + 0 \cdot x + 0 \cdot y + 0 \cdot z + 0 \cdot u + 1 \cdot v_{1} + 0 \cdot v_{2}) \times v_{2} \end{matrix}

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

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

\begin{matrix} v_{1} & = (0 \cdot 1 + 0 \cdot r + 1 \cdot x + 0 \cdot y + 0 \cdot z + 0 \cdot u + 0 \cdot v_{1} + 0 \cdot v_{2}) \times y \\ v_{2} & = (0 \cdot 1 + 0 \cdot r + 0 \cdot x + 0 \cdot y + 1 \cdot z + 0 \cdot u + 0 \cdot v_{1} + 0 \cdot v_{2}) \times u \\ r & = (0 \cdot 1 + 0 \cdot r + 0 \cdot x + 0 \cdot y + 0 \cdot z + 0 \cdot u + 1 \cdot v_{1} + 0 \cdot v_{2}) \times v_{2} \end{matrix}

我们就得到了刚才生成的相同的矩阵 $𝐋$ 。

𝐋 = [\begin{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 \end{matrix}]

由右侧项构建矩阵 $𝐑$

R = [\begin{matrix} r_{1,1} & r_{1, r} & r_{1, x} & r_{1, y} & r_{1, z} & r_{1, u} & r_{1, v_{1}} & r_{1, v_{2}} \\ r_{2,1} & r_{2, r} & r_{2, x} & r_{2, y} & r_{2, z} & r_{2, u} & r_{2, v_{1}} & r_{2, v_{2}} \\ r_{3,1} & r_{3, r} & r_{3, x} & r_{3, y} & r_{3, z} & r_{3, u} & r_{3, v_{1}} & r_{3, v_{2}} \end{matrix}]

矩阵 $𝐑$ 代表我们方程的右侧项：

\begin{matrix} v_{1} \\ v_{2} \\ r \end{matrix} \begin{matrix} = \\ = \\ = \end{matrix} \begin{matrix} x \\ z \\ v_{1} \end{matrix} \begin{matrix} \times \\ \times \\ \times \end{matrix} \underset{𝐑}{\begin{matrix} y \\ u \\ v_{2} \end{matrix}}

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

\begin{matrix} (1) \\ (2) \\ (3) \end{matrix} \begin{matrix} v_{1} \\ v_{2} \\ r \end{matrix} \begin{matrix} = \\ = \\ = \end{matrix} \begin{matrix} x \\ z \\ v_{1} \end{matrix} \begin{matrix} \times \\ \times \\ \times \end{matrix} \underset{𝐑}{\begin{matrix} y \\ u \\ v_{2} \end{matrix}}

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

这就得出了如下的矩阵 $𝐑$ ：

\begin{matrix} \begin{matrix} \begin{matrix} 1 & r & x & y & z & u & v_{1} & v_{2} \end{matrix} \end{matrix} \\ \begin{matrix} [\begin{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 \end{matrix}] \end{matrix} \end{matrix}

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

\begin{matrix} v_{1} \\ v_{2} \\ r \end{matrix} \begin{matrix} = \\ = \\ = \end{matrix} \begin{matrix} x \\ z \\ v_{1} \end{matrix} \begin{matrix} \times \\ \times \\ \times \end{matrix} \underset{𝐑}{\begin{matrix} y \\ u \\ v_{2} \end{matrix}} \begin{matrix} \begin{matrix} \begin{matrix} 1 & r & x & y & z & u & v_{1} & v_{2} \end{matrix} \end{matrix} \\ \begin{matrix} [\begin{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 \end{matrix}] \end{matrix} \end{matrix}

构建矩阵 $𝐎$

将确定矩阵 $𝐎$ 为

𝐎 = [\begin{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 \end{matrix}]

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

提醒一下， $𝐂$ 是从乘法的结果中推导出来的

\underset{𝐂}{\begin{matrix} v_{1} \\ v_{2} \\ r \end{matrix}} \begin{matrix} = \\ = \\ = \end{matrix} \begin{matrix} x \\ z \\ v_{1} \end{matrix} \begin{matrix} \times \\ \times \\ \times \end{matrix} \begin{matrix} y \\ u \\ v_{2} \end{matrix}

并且列标签如下所示

\begin{matrix} \begin{matrix} \begin{matrix} 1 & r & x & y & z & u & v_{1} & v_{2} \end{matrix} \end{matrix} \\ \begin{matrix} [\begin{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 \end{matrix}] \end{matrix} \end{matrix}

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

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：与常量相加

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

z = x * y + 2

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

加法是免费的

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

我们可以将上述公式写成

\begin{matrix} v_{1} = x y \\ z = v_{1} + 2 \end{matrix}

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

相反，我们可以将其写成

- 2 + z = x y

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

我们的见证向量形式为 [1, z, x, y]，因此我们的矩阵 $𝐋$ 、 $𝐑$ 和 $𝐎$ 如下所示：

𝐋 = [\begin{matrix} 0 & 0 & 1 & 0 \end{matrix}]

𝐑 = [\begin{matrix} 0 & 0 & 0 & 1 \end{matrix}]

𝐎 = [\begin{matrix} - 2 & 1 & 0 & 0 \end{matrix}]

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

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

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。正如你可能从上一个例子中猜到的那样，矩阵中的项就是变量所乘常量的相同值，如下例所示。

让我们求出以下方程的解

z = 2 x^{2} + y

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

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

\begin{matrix} v_{1} & = x x \\ z & = 2 v_{1} + y \end{matrix}

更优的解决方案如下：

- y + z = 2 x x

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

矩阵的定义将如下：

\begin{matrix} 𝐋 & = [\begin{matrix} 0 & 0 & 2 & 0 \end{matrix}] \\ 𝐑 & = [\begin{matrix} 0 & 0 & 1 & 0 \end{matrix}] \\ 𝐎 & = [\begin{matrix} 0 & 1 & 0 & - 1 \end{matrix}] \end{matrix}

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

[\begin{matrix} 0 & 1 & 0 & - 1 \end{matrix}] [\begin{matrix} 1 \\ z \\ x \\ y \end{matrix}] = [\begin{matrix} 0 & 0 & 2 & 0 \end{matrix}] [\begin{matrix} 1 \\ z \\ x \\ y \end{matrix}] \circ [\begin{matrix} 0 & 0 & 1 & 0 \end{matrix}] [\begin{matrix} 1 \\ z \\ x \\ y \end{matrix}]

z - y = 2 x x

z = 2 x^{2} + y

因此我们知道自己对 $𝐋$ 、 $𝐑$ 和 $𝐎$ 的设置是正确的。

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

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

示例 5：大型约束

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

假设我们有以下约束：

z = 3 x^{2} y + 5 x y - x - 2 y + 3

我们将其拆解如下：

\begin{matrix} v_{1} & = 3 x x \\ v_{2} & = v_{1} y \\ - v_{2} + x + 2 y - 3 + z & = 5 x y \end{matrix}

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

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

\frac{- v_{2}}{5} + \frac{x}{5} + \frac{2 y}{5} - \frac{3}{5} + \frac{z}{5} = x y

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

我们的见证向量形式将是

[1, z, x, y, v_{1}, v_{2}]

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

\begin{matrix} v_{1} & = 3 x x \\ v_{2} & = v_{1} y \\ - v_{2} + x + 2 y - 3 + z & = 5 x y \end{matrix}

我们用红色标记了输出 $𝐎$ ，用绿色标记了左侧 $𝐋$ ，并用紫色标记了右侧 $𝐑$ 。这就产生了以下矩阵：

L = [\begin{matrix} 0 & 0 & 3 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 5 & 0 & 0 & 0 \end{matrix}]

R = [\begin{matrix} 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \end{matrix}]

O = [\begin{matrix} 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ - 3 & 1 & 1 & 2 & 0 & - 1 \end{matrix}]

及其列标签

[\begin{matrix} 1 & out & x & y & v_{1} & v_{2} \end{matrix}]

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

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 = x y + . . .$ 的例子，但大多数现实中的算术约束将是一组算术约束，而不是单一的一个。

例如，假设我们要证明一个数组 $[x_{1}, x_{2}, x_{3}, x_{4}]$ 是二进制形式的，且 $v$ 小于 16。这组约束条件将是

\begin{matrix} x_{1}^{2} & = x_{1} \\ x_{2}^{2} & = x_{2} \\ x_{3}^{2} & = x_{3} \\ x_{4}^{2} & = x_{4} \\ v & = 8 x_{4} + 4 x_{3} + 2 x_{2} + x_{1} \end{matrix}

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

\begin{matrix} x_{1}^{2} & = v - 8 x_{4} - 4 x_{3} - 2 x_{2} \\ x_{2}^{2} & = x_{2} \\ x_{3}^{2} & = x_{3} \\ x_{4}^{2} & = x_{4} \end{matrix}

假设我们的见证向量是 $[1, v, x_{1}, x_{2}, x_{3}, x_{4}]$ ，我们可以如下创建 R1CS：

\begin{matrix} 𝐋 & = [\begin{matrix} 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix}] \\ 𝐑 & = [\begin{matrix} 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix}] \\ 𝐎 & = [\begin{matrix} 0 & 1 & 0 & - 2 & - 4 & - 8 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix}] \end{matrix}

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

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

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

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

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

Circom 实现

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

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

p = 21888242871839275222246405745257275088548364400416034343698204186575808495617

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

# 21888242871839275222246405745257275088548364400416034343698204186575808495616

`out = x * y` 的 Circom 实现

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

pragma circom 2.0.0;

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

    out <== x * y;
 }

component main = Multiply2();

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

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

我们得到如下输出：

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

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

值为零的列不会被打印
Circom 将 $𝐎 𝐚 = 𝐋 𝐚 \circ 𝐑 𝐚$ 写成 $𝐋 𝐚 \circ 𝐑 𝐚 - 𝐎 𝐚 = 𝟎$

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

Circom 的解决方案是

\begin{matrix} A & = [\begin{matrix} 0 & 0 & - 1 & 0 \end{matrix}] \\ B & = [\begin{matrix} 0 & 0 & 0 & 1 \end{matrix}] \\ C & = [\begin{matrix} 0 & - 1 & 0 & 0 \end{matrix}] \end{matrix}

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

你可以代入 $x$ 、 $y$ 和 out 的值，就会发现 $𝐋 𝐚 \circ 𝐑 𝐚 - 𝐎 𝐚 = 𝟎$ 这个等式是成立的。

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

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

cd multiply2_js/

我们创建 input.json 文件

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

然后计算见证向量

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 是正确的

\begin{matrix} 𝐚 & = [\begin{matrix} 1 & 99 & 11 & 9 \end{matrix}] \\ 𝐋 & = [\begin{matrix} 0 & 0 & - 1 & 0 \end{matrix}] \to 𝐋 𝐚 = - 11 \\ 𝐑 & = [\begin{matrix} 0 & 0 & 0 & 1 \end{matrix}] \to 𝐑 𝐚 = 9 \\ 𝐎 & = [\begin{matrix} 0 & - 1 & 0 & 0 \end{matrix}] \to 𝐎 𝐚 = - 99 \end{matrix}

\begin{matrix} A w \cdot B w - C w & = 0 \\ (- 11) (9) - (- 99) & = 0 \\ - 99 + 99 & = 0 \end{matrix}

对于 $x$ ， $𝐋$ 有一个系数 $- 1$ ；对于 $y$ ， $𝐑$ 有一个系数 $+ 1$ ；对于 $out$ ， $𝐎$ 有 $- 1$ 。在模数形式下，这与上面终端输出的内容完全相同：

检查我们其余的工作

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

\begin{matrix} z & = x * y \\ z & = x * y * z * u \\ z & = x * y + 2 \\ z & = 3 x^{2} y + 5 x y - x - 2 y + 3 \end{matrix}

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

(2) 的电路如下：

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 的输出和注释应该是不言自明的。

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

\begin{matrix} z & = x * y & 1 constraint \\ z & = x * y * z * u & 3 constraints \\ z & = x * y + 2 & 1 constraint \\ z & = 3 x^{2} y + 5 x y - x - 2 y + 3 & 3 constraints \end{matrix}

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

计算 R1CS 并不需要见证向量

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

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

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

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

在一些 R1CS 教程中，像

z = x^{2} + y

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

\begin{matrix} v_{1} & = x x \\ z & = v_{1} + y \end{matrix}

正如我们所指出的那样，这并不是高效的做法。然而，你可以使用本文中的方法为此创建一个有效的 R1CS。我们只需添加一个虚拟乘法（dummy multiplication），如下所示：

\begin{matrix} v_{1} & = x x \\ z & = (v_{1} + y) * 1 \end{matrix}

我们的见证向量形式为 $[1, z, x, y, v 1]$ ，且 $𝐋$ 、 $𝐑$ 和 $𝐎$ 定义如下：

𝐋 = [\begin{matrix} 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 \end{matrix}]

𝐑 = [\begin{matrix} 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \end{matrix}]

𝐎 = [\begin{matrix} 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 \end{matrix}]

$𝐋$ 的第二行完成了加法运算，而乘以 1 则是通过使用 $𝐑$ 第二行的第一个元素来完成的。

这样做是完全有效的，但该解法比实际所需的行数多了一行，列数多了一列。

如果没有乘法怎么办？

如果我们想要编码以下电路怎么办？

z = x + y

这在实践中相当无用，但为了完整起见，可以通过乘以 1 这样一个虚拟乘法来解决。

o u t = (x + y) * 1

使用我们典型的见证向量布局 $[1, z, x, y]$ ，我们得到以下矩阵：

\begin{matrix} 𝐋 & = [\begin{matrix} 0 & 0 & 1 & 1 \end{matrix}] \\ 𝐑 & = [\begin{matrix} 1 & 0 & 0 & 0 \end{matrix}] \\ 𝐎 & = [\begin{matrix} 0 & 1 & 0 & 0 \end{matrix}] \end{matrix}

秩一约束系统是为了提供便利

原始的 Groth16 论文并未提及“秩一约束系统”这一术语。从实现的角度来看，R1CS 非常方便，但从纯数学的角度来看，它仅仅是对不同变量的系数进行显式标注和分组而已。因此，当你阅读有关该主题的学术论文时，它通常会被省略，因为这只是一个更为抽象概念的实现细节。

实用资源

这个用于计算 R1CS 的网络工具能够处理一组约束（但它仅适用于单个输入和输出变量）。
Vitalik 的著名示例 x**3 + x + 5 == 35
Zero knowledge 博客的 R1CS 教程

通过 RareSkills 了解更多

这篇博客文章摘自我们零知识证明课程的学习资料。