这篇文章解释了如何将一组算术约束转化为 Rank One Constraint System (R1CS)。

本资源的重点是实现：我们讨论了这种转换的更多边界情况，讨论了优化，并解释了 Circom 库如何实现它。

先决条件

• 我们假设读者了解如何使用 算术电路 (zk circuits) 来表示计算的有效性。
• 读者熟悉 模算术。这里的所有操作都发生在一个有限域中，因此 -5 实际上是指 5 的模 p 加法逆元，而 2/3 表示 3 的模 p 乘法逆元乘以 2。

Rank 1 Constraint System 概述

Rank 1 Constraint System (R1CS) 是一个算术电路，其要求是每个等式约束有一个乘法（对加法的数量没有限制）。

这使得算术电路的表示与双线性配对的使用兼容。配对的输出 G1∙G2→GT 不能再次进行配对，因为在 GT 中的元素不能作为其他配对的输入。因此，我们每个约束只允许一个乘法。

见证向量

在一个算术电路中，见证是一个对所有信号的赋值，使其满足方程的约束。

在 Rank 1 Constraint System 中，见证向量是一个 1×n 向量，包含所有输入变量、输出变量和中间值的值。它表明你已经从头到尾执行了电路，知道输入、输出以及所有中间值。

通过约定，第一个元素总是 1，以便使一些计算更简单，我们稍后将演示。

例如，如果我们有约束

$$z = x^2y$$

我们宣称知道解，那么这必须意味着我们知道 x、y 和 z。因为 Rank One Constraint Systems 每个约束恰好要求一个乘法，上述多项式约束必须写作

$$ v₁ = xx $$ $$ z = v₁y $$

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

$$ [1, z, x, y, v₁]$$

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

例如，

[1,18,3,2,9]

是一个有效的见证，因为当我们将值代入时，₁[constant=1,z=18,x=3,y=2,v₁=9] 它满足约束

$$ [\text{constant} = 1, z = 18, x = 3, y = 2, v₁ = 9] $$

额外的 1 项在这个例子中没有使用，它只是一个方便，我们会稍后解释。

示例 1：将 z=x⋅y 转换为 Rank 1 Constraint System

在我们的例子中，我们将说我们在证明 41×103=4223。

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

在我们能够创建 R1CS 之前，我们的约束需要是以下形式

result = left_hand_side × right_hand_side

幸运的是，它已经是 $$ \underbrace{z}\text{result} = \underbrace{x}\text{left hand side} \times \underbrace{y}_\text{right hand side} $$

这显然是一个简单的例子，但简单的例子通常是一个很好的起点。

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

稍后我们将讨论如何处理不只有一个乘法的情况，例如 $z=x³$ 或 $z=x³+y$。

我们的目标是创建一个形式为：

$$ Oa=La∘Ra $$

的方程组，其中 $O$、$L$ 和 $R$ 是大小为 $n x m$ 的矩阵（$n$ 行和 $m$ 列）。

矩阵 L 编码乘法左侧的变量，R 编码乘法右侧的变量。O 编码结果变量。向量 a 是见证向量。

具体而言，L、R 和 O 是列数与见证向量 a 相同的矩阵，每列表示索引使用的相同变量。

因此，对于我们的例子，见证有 4 个元素 (1,z,x,y)，所以每个矩阵会有 4 列，所以 m=4。

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

让我们直接跳入答案并解释我们是如何获得的。

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

$$ \underbrace{\begin{bmatrix} 0 & 1 & 0 & 0 \ \end{bmatrix}}{\mathbf{O}}\mathbf{a} = \underbrace{\begin{bmatrix} 0 & 0 & 1 & 0 \ \end{bmatrix}}{\mathbf{L}}\mathbf{a}\circ \underbrace{\begin{bmatrix} 0 & 0 & 0 & 1 \ \end{bmatrix}}_{\mathbf{R}}\mathbf{a} $$

$$ \begin{bmatrix} 0 & 1 & 0 & 0 \ \end{bmatrix} \begin{bmatrix} 1 \ 4223 \ 41 \ 103 \ \end{bmatrix}= \begin{bmatrix} 0 & 0 & 1 & 0 \ \end{bmatrix} \begin{bmatrix} 1 \ 4223 \ 41 \ 103 \ \end{bmatrix}\circ \begin{bmatrix} 0 & 0 & 0 & 1 \ \end{bmatrix} \begin{bmatrix} 1 \ 4223 \ 41 \ 103 \ \end{bmatrix} $$

在这个例子中，矩阵中的每个项目都作为一个指示变量，用于表示与该列对应的变量是否存在。（从技术上讲，它是变量的系数，但我们稍后会讨论到）。

对于左侧条款，x 是出现在乘法左侧的唯一变量，因此如果这些列代表 [1,z,x,y]，那么…

$L$ 是 $[0,0,1,0]$，因为 $x$ 出现了，而其他变量没有。

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

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

我们没有任何常数，因此 1 列在任何地方都为零（稍后我们将讨论它何时非零）。

此方程是正确的，我们可以在 Python 中验证这一点

import numpy as np

## 定义矩阵
O = np.matrix([[0,1,0,0]])
L = np.matrix([[0,0,1,0]])
R = np.matrix([[0,0,0,1]])

## 见证向量
a = np.array([1, 4223, 41, 103])

## 乘法 `*` 是逐元素的，而不是矩阵乘法。
## Result 包含一个布尔值，指示该元素的逐元素指示该等式对该元素为真。
result = np.matmul(O, a) == np.matmul(L, a) * np.matmul(R, a) 

## 检查每个逐元素的等式是否为真
assert result.all(), "result contains an inequality"

你可能会想知道这有什么意义，我们是不是只是在用一种更不简洁的方式说 41×103=4223？

你是对的。

R1CS 可以相当冗长，但它们与 二次算术程序 (QAPs) 完美对应，可以简化。不过我们在这里不关心 QAP。

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

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

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

$$ v₁=xy $$ $$ v₂=zu $$ $$ r=v₁v₂ $$

没有规则要求我们必须这样分解，下面的分解也是有效的： $$ \begin{align} v_1 &= xy \ v_2 &= v_1z \ r &= v_2u \end{align} $$

我们将使用第一个变换作为这个例子的处理。

L、R 和 O 的大小

因为我们正在处理 7 个变量 $(r,x,y,z,u,v₁,v₂)$，所以我们的见证向量将有八个元素（第一个是常数 1），我们的矩阵将有八列。

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

左侧项和右侧项

这个例子将强烈强调“左侧项”和“右侧项”的概念。具体而言，x、z 和 v₁ 是左侧项，而 y、u 和 v₂ 是右侧项。

$$ \underbrace{ \begin{matrix} v_1 \ v2 \ r \ \end{matrix} }\text{ Output Terms } \begin{matrix} =\ =\

\end{matrix} \underbrace{ \begin{matrix} x \ z \ v1 \ \end{matrix} }\text{ Left Hand Terms } \begin{matrix} \times\ \times\ \times \end{matrix} \underbrace{ \begin{matrix} y \ u \ v2 \ \end{matrix} }\text{ Right Hand Terms } $$

基于左侧项构造矩阵 L

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

$$ \begin{bmatrix} & 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{bmatrix} $$

我们的见证向量将与这个相乘，所以让我们定义我们的见证向量布局为：

$$ \begin{bmatrix} 1 & r &x & y & z & u & v_1 & v_2 \end{bmatrix} $$

这告诉我们 L 的列代表的是什么：

$$ \mathbf{L} = \begin{bmatrix} l{1, 1} & l{1, r} & l{1, x} & l{1, y} & l{1, z} & l{1, u} & l_{1, v1} & l{1, v2} \ l{2, 1} & l{2, r} & l{2, x} & l{2, y} & l{2, z} & l{2, u} & l{2, v1} & l{2, v2} \ l{3, 1} & l{3, r} & l{3, x} & l{3, y} & l{3, z} & l{3, u} & l{3, v1} & l{3, v_2} \ \end{bmatrix} $$

L 的第一行

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

$$ \begin{matrix} v_1 \ v_2 \ r \ \end{matrix} \begin{matrix} =\ =\

\end{matrix} \underset{\mathbf{L}}{\boxed{ \begin{matrix} \color{red}{x} \ z \ v_1 \ \end{matrix} }} \begin{matrix} \times\ \times\ \times \end{matrix} \begin{matrix} y \ u \ v_2 \ \end{matrix} $$

这意味着就左侧而言，变量 x 是存在的，其他变量则不存在。因此，我们将第一行转化如下：

$$ \mathbf{L}=\begin{bmatrix} 0 & 0 & \color{red}{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, v1} & l{2, v2} \ l{3, 1} & l{3, r} & l{3, x} & l{3, y} & l{3, z} & l{3, u} & l{3, v1} & l{3, v_2} \ \end{bmatrix} $$

请记住，L 的列标记如下：

$$ \begin{bmatrix} 1 & r &x & y & z & u & v_1 & v_2\ \end{bmatrix} $$

我们看到 1 在 x 列中。

L 的第二行

继续向下，我们看到只有 z 是出现在我们方程组的左侧。

$$ \begin{matrix} v_1 \ v_2 \ r \ \end{matrix} \begin{matrix} =\ =\

\end{matrix} \underset{\mathbf{L}}{\boxed{ \begin{matrix} x \ \color{green}{z} \ v_1 \ \end{matrix} }} \begin{matrix} \times\ \times\ \times \end{matrix} \begin{matrix} y \ u \ v_2 \ \end{matrix} $$

因此，在该行中，我们将所有归零，除了代表 z 的列。

$$ \mathbf{L}=\begin{bmatrix} 0 & 0 & \color{red}{1} & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & \color{green}{1} & 0 & 0 & 0 \ l{3, 1} & l{3, r} & l{3, x} & l{3, y} & l{3, z} & l{3, u} & l_{3, v1} & l{3, v_2} \ \end{bmatrix} $$

L 的第三行

最后，我们在第三行中唯一出现在左侧运算符的变量是 ( v₁ )

$$ \begin{matrix} v_1 \ v_2 \ r \ \end{matrix} \begin{matrix} =\ =\

\end{matrix} \underset{\mathbf{L}}{\boxed{ \begin{matrix} x \ z \ \color{violet}{v_1} \ \end{matrix} }} \begin{matrix} \times\ \times\ \times \end{matrix} \begin{matrix} y \ u \ v_2 \ \end{matrix} $$

这完成了矩阵 L。

$$ \mathbf{L}=\begin{bmatrix} 0 & 0 & \color{red}{1} & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & \color{green}{1} & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & 0 & 0 & \color{violet}{1} & 0 \ \end{bmatrix} $$

下图应使映射更清晰：

$$ \begin{matrix} v_1 \ v_2 \ r \ \end{matrix} \begin{matrix} =\ =\

\end{matrix} \underset{\mathbf{L}}{\boxed{ \begin{matrix} \color{red}{x} \ \color{green}{z} \ \color{violet}{v_1} \ \end{matrix} }} \begin{matrix} \times\ \times\ \times \end{matrix} \begin{matrix} y \ u \ v_2 \ \end{matrix} \space\space\space\space \begin{array}{c} \begin{array}{cc} \begin{matrix} 1 & r & x & y & z & u & v_1 & v_2 \ \end{matrix} \end{array} \[10pt] \begin{array}{cc} \begin{bmatrix} 0 & 0 & \color{red}{1} & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & \color{green}{1} & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & 0 & 0 & \color{violet}{1} & 0 \ \end{bmatrix} \end{array} \end{array} $$

L 的替代变换

我们可以通过展开左侧值来完成相同的操作

$$ \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{align} v_1 &= (0\cdot 1 + 0\cdot r + \boxed{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 + \boxed{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 + \boxed{1\cdot v_1} + 0\cdot v_2) \times v_2 \ \end{align} $$

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

然后，如果我们将上面展开中的系数（以框表示）拿出来，

$$ \begin{align} v_1 &= (\boxed{0}\cdot 1 + \boxed{0}\cdot r + \boxed{1}\cdot x + \boxed{0}\cdot y + \boxed{0}\cdot z + \boxed{0}\cdot u + \boxed{0}\cdot v_1 + \boxed{0}\cdot v_2) \times y\ v_2 &= (\boxed{0}\cdot 1 + \boxed{0}\cdot r + \boxed{0}\cdot x + \boxed{0}\cdot y + \boxed{1}\cdot z + \boxed{0}\cdot u + \boxed{0}\cdot v_1 + \boxed{0}\cdot v_2) \times u\ r &= (\boxed{0}\cdot 1 + \boxed{0}\cdot r + \boxed{0}\cdot x + \boxed{0}\cdot y + \boxed{0}\cdot z + \boxed{0}\cdot u + \boxed{1}\cdot v_1 + \boxed{0}\cdot v_2) \times v_2 \ \end{align} $$

我们获得的 L 矩阵与刚才生成的相同。

$$ \mathbf{L}=\begin{bmatrix} 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{bmatrix} $$

从右侧项构造矩阵 R

$$ R = \begin{bmatrix} r{1,1} & r{1,r} & r{1,x} & r{1,y} & r{1,z} & r{1,u} & r_{1,v1} & r{1,v2} \ r{2,1} & r{2,r} & r{2,x} & r{2,y} & r{2,z} & r{2,u} & r{2,v1} & r{2,v2} \ r{3,1} & r{3,r} & r{3,x} & r{3,y} & r{3,z} & r{3,u} & r{3,v1} & r{3,v_2} \ \end{bmatrix} $$

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

$$ \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{\mathbf{R}}{\boxed{ \begin{matrix} y \ u \ v_2 \ \end{matrix}}} $$

矩阵 R 必须有 1 代表 $y$、$u$ 和 $v₂$。矩阵中的行对应于算术约束的行，即我们可以将约束（行）编号如下：

$$ \begin{matrix} (1) \ (2) \ (3) \ \end{matrix} \space\space \begin{matrix} v_1 \ v_2 \ r \ \end{matrix} \begin{matrix} =\ =\

\end{matrix} { \begin{matrix} x \ z \ v_1 \ \end{matrix} } \beg...