在零知识证明的背景下，算术电路是为 NP 中的问题建立模型的一个方程组。

我们在关于 P vs NP 的文章中的一个关键点是，P 或 NP 中问题的任何解都可以通过将该问题建模为布尔电路来验证。

然后，我们将原问题的解转换为布尔变量的一组值（称为 witness），这会使得布尔电路返回 true。

本文建立在上面链接的文章基础之上，因此请先阅读那一篇。

作为布尔电路替代方案的算术电路

使用布尔电路来表示问题解的一个缺点是，在表示加法或乘法等算术运算时，它可能会非常繁琐。

例如，如果我们想表达 $a + b = c$，其中 $a = 8, b = 4, c = 12$，我们必须将 $a$、$b$ 和 $c$ 转换为二进制数。二进制数中的每一位将对应一个独立的布尔变量。在这个例子中，假设我们需要 4 个比特（bit）来编码 $a$、$b$ 和 $c$，其中 $a₀$ 代表数字 $a$ 的最低有效位 (LSB)，$a₃$ 代表最高有效位 (MSB)，如下所示：

• a₃, a₂, a₁, a₀
  • $a = 1000$
• b₃, b₂, b₁, b₀
  • $b = 0100$
• c₃, c₂, c₁, c₀
  • $c = 1100$

（你现在不需要知道如何将数字转换为二进制，我们将在本文后面解释该方法）。

一旦我们将 $a$、$b$ 和 $c$ 写成二进制，我们就可以编写一个布尔电路，其输入是所有的二进制位 $(a₀, a₁, …, c₂, c₃)$。我们的目标是编写这样一个布尔电路，使得当且仅当 $a + b = c$ 时，该电路输出 true。

事实证明，这比预期的要复杂得多，如下方模拟二进制 $a + b = c$ 的大型电路所示。为了简洁起见，我们不展示推导过程。我们仅展示该公式以说明此类电路会有多么冗长：

Copy
((a₄ ∧ b₄ ∧ c₄) ∨ (¬a₄ ∧ ¬b₄ ∧ c₄) ∨ (¬a₄ ∧ b₄ ∧ ¬c₄) ∨ (a₄ ∧ ¬b₄ ∧ ¬c₄)) ∧

((a₃ ∧ b₃ ∧ ((a₂ ∧ b₂) ∨ (b₂ ∧ (a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀)))) ∨
 (¬a₃ ∧ ¬b₃ ∧ ((a₂ ∧ b₂) ∨ (b₂ ∧ (a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀)))) ∨
 (¬a₃ ∧ b₃ ∧ ¬((a₂ ∧ b₂) ∨ (b₂ ∧ (a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀)))) ∨
 (a₃ ∧ ¬b₃ ∧ ¬((a₂ ∧ b₂) ∨ (b₂ ∧ (a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀))))) ∧

((a₂ ∧ b₂ ∧ ((a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀))) ∨
 (¬a₂ ∧ ¬b₂ ∧ ((a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀))) ∨
 (¬a₂ ∧ b₂ ∧ ¬((a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀)))) ∨
 (a₂ ∧ ¬b₂ ∧ ¬((a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀))))) ∧

((a₁ ∧ b₁ ∧ c₀) ∨ (¬a₁ ∧ ¬b₁ ∧ c₀) ∨ (¬a₁ ∧ b₁ ∧ ¬c₀) ∨ (a₁ ∧ ¬b₁ ∧ ¬c₀)) ∧

((a₀ ∧ b₀ ∧ c₀) ∨ (¬a₀ ∧ ¬b₀ ∧ c₀) ∨ (¬a₀ ∧ b₀ ∧ ¬c₀) ∨ (a₀ ∧ ¬b₀ ∧ ¬c₀)) ∧

¬ ((a₄ ∧ b₄) ∨
     (b₄ ∧ (a₃ ∧ b₃) ∨ (b₃ ∧ (a₂ ∧ b₂) ∨ (b₂ ∧ (a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀))) ∨
     (a₃ ∧ (a₂ ∧ b₂) ∨ (b₂ ∧ (a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀))))

这里的关键是，如果我们受限于布尔输入和基本的布尔运算（AND、OR、NOT），对于基础问题而言，构建电路很快就会变得复杂且乏味，尤其是当涉及算术运算时。

相比之下，直接在电路中表示数字会更简单。与其用布尔公式对加法进行建模，我们不如直接对这些数字使用加法和乘法。

本文证明了使用算术电路也可以对 P 或 NP 中的任何问题进行建模。

算术电路

算术电路是一个仅使用加法、乘法和相等关系的方程组。与布尔电路一样，它检查所提供的一组输入是否有效，但不计算解。

下面是我们关于算术电路的第一个例子：

Copy
6 = x₁ + x₂
9 = x₁x₂

如果我们对输入变量的赋值能产生 true 的输出，我们就说布尔电路被满足 (satisfied)。类似地，如果存在对变量的赋值使得所有方程都成立，则算术电路被满足。

例如，上述电路被 x₁ = 3, x₂ = 3 所满足，因为电路中的两个方程均成立。反之，该电路不被 x₁ = 1, x₂ = 6 所满足，因为方程 9 = x₁x₂ 不成立。

因此，我们可以将算术电路与电路中的方程组等同看待。当且仅当一组输入使所有方程都为真时，这组输入才“满足该电路”。

符号与术语

算术电路中的变量被称为 signals（信号），因为我们将用来编写 ZK 证明的编程语言 Circom 是这样称呼它们的。

为了表达相等关系，我们将使用 === 运算符。我们使用这种表示法是因为 Circom 使用它来声明两个信号具有相等的值，所以我们最好习惯看到它。

我们强调 === 是在断言等式左侧和右侧相等。例如，在以下电路中：

c === a + b

我们并不是将 a 和 b 相加并将结果赋值给 c。相反，我们假设值 a、b 和 c 是作为输入提供的，并且我们在断言它们之间的关系成立。这就起到了将 a 和 b 之和约束 (constraining) 为 c 的作用。

将 c === a + b 视为完全等同于 assertEq(c, a + b)。类似地，表达式 a + b === c * d 完全等同于 assertEq(a + b, c * d)。从本质上讲，在电路中验证这些方程涉及检查是否满足了某些条件（约束）。证明其 witness 有效性的代理（agent）可以为 signals 分配任何值。但是，只有当满足所有约束时，他们的证明（witness）才会被视为有效。

例如，如果代理希望证明：

Copy
a === b + c + 3
a * u === x * y

他们必须从电路外部提供 (a, b, c, u, x, y) 并将它们分配给电路中的 signals。

请记住，上面的代码等同于：

Copy
assertEq(a, b + c + 3)
assertEq(a * u, x * y)

对于算术电路，一个有用的心智模型是：所有 signals 都被视为只有输入而没有输出。

为了更清楚地说明这一点，我们在以下视频中提供了一个可视化演示。所有 signals 都是输入，而 === 用于检查而不是赋值。

视频中的电路也可以写成这样：

Copy
z + y === x
x + y === u

且含义没有任何改变。

算术电路 x === x + 1 并不意味着递增 x。它是一个无解的算术电路，因为 x 不可能等于 x + 1。因此，是不可能满足该约束的。

解释算术电路

考虑以下电路：

Copy
x₁(x₁ - 1) === 0
x₁x₂ === x₁

第一个约束 x₁(x₁ - 1) === 0 将 x₁ 的可能值限制为只能是 0 或 1。x₁ 的任何其他值都无法满足此约束。

在第二个约束 x₁x₂ === x₁ 中，我们有两种可能的情况：

• 如果 x₁ = 1，那么 x₂ 也必须是 1，否则无法满足第二个约束。如果 x₁ = 1 且 x₂ ≠ 1，那么第二个方程就变成了 1 * x₂ === 1，它只能被 x₂ = 1 满足，从而产生冲突。
• 如果 x₁ = 0，那么 x₂ 可以是任何值，因为 0x₂ === 0 很容易满足。

以下对 (x₁, x₂) 的赋值都是有效的 witnesses：

• $(x₁, x₂) = (1, 1)$
• $(x₁, x₂) = (0, 2)$
• $(x₁, x₂) = (0, 1337)$
• $(x₁, x₂) = (0, 404)$

记住，一个方程组可以有多个解。类似地，一个算术电路也可以有多个解。不过通常，我们只对验证一个给定的解感兴趣。我们不需要找到算术电路的所有解。

布尔电路 vs 算术电路

下表展示了布尔电路和算术电路的不同之处，但请记住，它们的核心目的都是验证 witness：

除了在某些情况下使用较少变量的便利性之外，算术电路和布尔电路是完成相同工作的工具 —— 即证明你拥有一个 NP 问题的 witness。

回到最初的例子 a + b = c

让我们回顾一下上面的例子：编写一个布尔电路来表示方程 a + b = c，其中已知 c = 12。对于布尔电路，我们需要对 a、b 和 c 进行二进制编码，每个数字需要 4 个比特（在此示例中）。总共，该电路有 12 个输入。相比之下，算术电路只需要 3 个输入：a、b 和 c。输入数量的减少和整体电路规模的缩小正是我们在 ZK 应用中更喜欢使用算术电路的原因。

方程组与算术电路之间的相似之处

布尔电路总是有一个表达式，如果 witness 得到满足，它就会返回 true 或 false。

例如，如果我们有一组 signals $x$、$y$ 和 $z$，并且我们希望约束 $x$ 和 $y$ 的和为 $5$，那么我们需要为此提供一个单独的方程。任何我们希望约束 z 的方式都有其独立的方程。

为了证明算术电路和布尔电路是等价的，我们稍后将展示任何布尔电路都可以转化为算术电路。这表明，在证明代理具有 P 或 NP 问题的 witness 这一目的上，它们是可以互换使用的。

所有 P 问题都是 NP 问题的子集

正如前面关于 P vs NP 的章节中所讨论的，就验证 witness 的计算要求而言，所有 P 问题都是 NP 问题的子集，所以接下来我们将只提及 NP 问题，并默认它包含了 P。

我们的结论是，如果 NP 中某问题的任意解可以通过布尔电路进行建模，那么 NP（或 P）中某问题的任意解也就可以通过算术电路进行建模。

但在证明它们的等价性之前，我们将提供对 NP 问题求解进行建模的示例，以便我们对算术电路的使用建立直观认识。

算术电路示例

在我们的第一个示例中，我们将重做澳大利亚的 3 染色问题。在第二个示例中，我们将演示如何使用算术电路来证明一个列表已排序。

示例 1：使用算术电路对 3 染色问题进行建模

当我们使用布尔电路对 3 染色进行建模时，每个领地有 3 个布尔变量（每种颜色一个），以指示该地区是否被分配了该颜色。然后，我们添加了约束来强制每个领地必须刚好有一种颜色（颜色约束），以及强制相邻领地不能有相同颜色的约束（边界约束）。

使用算术电路对这个问题进行建模要容易得多，因为我们可以为每个领地分配一个单一的 signal，其可能的值为 $\set{1, 2, 3}$ 来对其颜色进行建模，而不是使用三个布尔变量。我们可以任意将颜色分配给数字，例如 blue = 1、red = 2 和 green = 3。

对于每个领地，我们将单一颜色约束写为：

Copy
0 === (1 - x) * (2 - x) * (3 - x)

以强制每个领地刚好有一种颜色。上述约束只有在 x 为 1、2 或 3 时才能被满足。

澳大利亚 3 染色问题

回想一下，澳大利亚有六个领地：

• WA = West Australia (西澳大利亚)
• SA = South Australia (南澳大利亚)
• NT = Northern Territory (北领地)
• Q = Queensland (昆士兰)
• NSW = New South Wales (新南威尔士)
• V = Victoria (维多利亚)

说 WA = 1 等同于说“把西澳大利亚涂成蓝色”。类似地，WA = 2 表示将“红色”分配给西澳大利亚，WA = 3 表示分配了“绿色”。

我们针对每个领地的颜色约束（约束每个领地为蓝色、红色或绿色）变为：

Copy
1) 0 === (1 - WA) * (2 - WA) * (3 - WA)
2) 0 === (1 - SA) * (2 - SA) * (3 - SA)
3) 0 === (1 - NT) * (2 - NT) * (3 - NT)
4) 0 === (1 - Q) * (2 - Q) * (3 - Q)
5) 0 === (1 - NSW) * (2 - NSW) * (3 - NSW)
6) 0 === (1 - V) * (2 - V) * (3 - V)

我们现在想要强制规定相邻领地不能拥有相同的颜色。实现这一点的一种方法是将相邻领地的 signals 相乘，并确保乘积是一个“可接受的”值。考虑以下针对相邻领地 x 和 y 的表格：

如果两个 signals（相邻领地）有相同的数字（颜色），那么它们的乘积将是 $\set{1,4,9}$ 中的一个，即上述的红色数字。如果 x 和 y 被约束为 1、2 或 3，且 x 和 y 彼此不相等，那么乘积 xy 将是 $\set{2, 3, 6}$ 中的一个。因此，如果 xy = 2 或 xy = 3 或 xy = 6，我们接受这种赋值，因为这意味着两个相邻地区有不同的颜色。

对于每对相邻领地 x 和 y，我们可以使用以下约束来强制它们彼此不相等：

Copy
0 === (2 - xy) * (3 - xy) * (6 - xy)

当且仅当乘积 xy 等于 2、3 或 6 时，上述方程才被满足。

边界约束是通过遍历边界并在每对相邻领地之间应用边界约束来创建的，如下方视频所示：

我们现在展示边界约束：

Copy
Western Australia and South Australia:
7) 0 === (2 - WA * SA) * (3 - WA * SA) * (6 - WA * SA)

Western Australia and Northern Territory
8) 0 === (2 - WA * NT) * (3 - WA * NT) * (6 - WA * NT)

Northern Territory and South Australia
9) 0 === (2 - NT * SA) * (3 - NT * SA) * (6 - NT * SA)

Northern Territory and Queensland
10) 0 === (2 - NT * Q) * (3 - NT * Q) * (6 - NT * Q)

South Australia and Queensland
11) 0 === (2 - SA * Q) * (3 - SA * Q) * (6 - SA * Q)

South Australia and New South Wales
12) 0 === (2 - SA * NSW) * (3 - SA * NSW) * (6 - SA * NSW)

South Australia and Victoria
13) 0 === (2 - SA * V) * (3 - SA * V) * (6 - SA * V)

Queensland and New South Wales
14) 0 === (2 - Q * NSW) * (3 - Q * NSW) * (6 - Q * NSW)

New South Wales and Victoria
15) 0 === (2 - NSW * V) * (3 - NSW * V) * (6 - NSW * V)

将两者结合起来，我们看到了完整的算术电路，用于证明我们对澳大利亚有一个有效的 3 染色：

Copy
// color constraints
0 === (1 - WA) * (2 - WA) * (3 - WA)
0 === (1 - SA) * (2 - SA) * (3 - SA)
0 === (1 - NT) * (2 - NT) * (3 - NT)
0 === (1 - Q) * (2 - Q) * (3 - Q)
0 === (1 - NSW) * (2 - NSW) * (3 - NSW)
0 === (1 - V) * (2 - V) * (3 - V)

// boundary constraints
0 === (2 - WA * SA) * (3 - WA * SA) * (6 - WA * SA)
0 === (2 - WA * NT) * (3 - WA * NT) * (6 - WA * NT)
0 === (2 - NT * SA) * (3 - NT * SA) * (6 - NT * SA)
0 === (2 - NT * Q) * (3 - NT * Q) * (6 - NT * Q)
0 === (2 - SA * Q) * (3 - SA * Q) * (6 - SA * Q)
0 === (2 - SA * NSW) * (3 - SA * NSW) * (6 - SA * NSW)
0 === (2 - SA * V) * (3 - SA * V) * (6 - SA * V)
0 === (2 - Q * NSW) * (3 - Q * NSW) * (6 - Q * NSW)
0 === (2 - NSW * V) * (3 - NSW * V) * (6 - NSW * V)

就像布尔电路一样我们有 15 个约束，但变量 (signals) 的数量只有它的 1/3。 我们为每个领地设置一个 signal，而不是 3 个布尔变量。对于更大的电路，这种复杂性和空间上的减少是相当可观的。

示例 2：证明列表已排序

给定一个数字列表 [a₁, a₂, ..., aₙ]，如果 aₙ ≥ aₙ₋₁ ≥ … a₃ ≥ a₂ ≥ a₁，我们说该列表是“已排序的”。换句话说，从后往前看，数字是非递增的。

我们的目标是编写一个验证列表已排序的算术电路。

为此，我们需要一个算术电路来表达两个 signals 的 a ≥ b。这比第一眼看起来要复杂得多，因为算术电路只允许相等、加法和乘法运算，不允许进行比较。

但假设我们有这样一个“大于或等于”的电路 —— 称之为 GTE(a,b)。然后我们将构建电路来比较列表中相邻的每一对元素：GTE(aₙ, aₙ₋₁), ..., GTE(a₃, a₂), GTE(a₂, a₁)，如果它们都被满足，那么该列表就是已排序的。

为了在没有 $≥$ 运算符的情况下比较两个十进制数，我们首先需要一个能够验证所提供的数字二进制表示形式的算术电路，因此我们先绕个小弯来讨论一下二进制数。

前置知识：二进制编码

我们用下标 2 来书写二进制数。例如，11₂ 是 3，101₂ 是 5。每一个 1 和 0 都被称为一个比特 (bit)。我们称最左边的比特为最高有效位 (MSB)，最右边的比特为最低有效位 (LSB)。

正如我们稍后将展示的那样，在转换为十进制的过程中，最高有效位乘以最大的系数，最低有效位乘以最小的系数。因此，如果我们将一个四位二进制数写成 b₃b₂b₁b₀，那么 b₃ 就是 MSB，b₀ 就是 LSB。

下面的视频演示了将 1101₂ 转换为 13 的过程：

如视频所示，一个四位二进制数可以通过以下公式转换为十进制数 v：

v = 8b₃ + 4b₂ + 2b₁ + b₀

这也可以写成：

v = 2³b₃ + 2²b₂ + 2¹b₁ + 2⁰b₀

例如，1001₂ = 9，1010₂ = 10，以此类推。对于一般的 n 位二进制数，转换公式为：

v = 2ⁿ⁻¹b₃ + ... + 2¹b₁ + 2⁰b₀

我们省略了关于如何将十进制数转换为二进制的讨论。目前，如果读者想要将其转换为二进制，可以使用 Python 内置的 bin 函数：

Copy
>>> bin(3)
'0b11'
>>> bin(9)
'0b1001'
>>> bin(10)
'0b1010'
>>> bin(1337)
'0b10100111001'
>>> bin(404)
'0b110010100'

我们可以创建一个算术电路，断言“v 是一个具有四位二进制表示 b₃、b₂、b₁、b₀ 的十进制数”，方法是使用以下电路：

Copy
8b₃ + 4b₂ + 2b₁ + b₀ === v

// force the "bits" to be zero or one
b₀(b₀ - 1) === 0
b₁(b₁ - 1) === 0
b₂(b₂ - 1) === 0
b₃(b₃ - 1) === 0

signals b₃, b₂, b₁, b₀ 被约束为 v 的二进制表示。如果 b₃, b₂, b₁, b₀ 不是二进制的，或者不是 v 的二进制表示，那么电路就无法被满足。

请注意，当 v > 15 时，不存在能满足 signals (v, b₃, b₂, b₁, b₀) 的赋值。 也就是说，如果我们将 b₃, b₂, b₁, b₀ 全部设置为约束所允许的最高值 1，那么总和将是 15。不可能相加得到更高的值。在 ZK 中，这有时被称为对 v 的范围检查 (range check)。上述电路不仅展示了 v 的二进制表示，它还强制 v < 16。

我们可以将其推广到以下电路，该电路约束了 $v < 2^n$ 并同时给出了 v 的二进制表示：

Copy
2ⁿ⁻¹bₙ₋₁ +...+ 2²b₂ + 2¹b₁ + b₀ === v
b₀(b₀ - 1) === 0
b₁(b₁ - 1) === 0
//...
bₙ₋₁(bₙ₋₁ - 1) === 0

说数字 v 最多用 n 个比特进行编码，等同于说 $v < 2^n$。

为了直观感受 $2^n$ 作为 $n$ 的函数是如何变化的，请参考下表：

请注意，二进制数字 $2^n$ 比起值 $2^n - 1$ 需要多 1 个比特来存储。通过将编码一个数字的比特数约束为 $n$ 个比特，它强制该数字必须小于 $2^n$。

记住 $2$ 的幂与其所需存储的比特数之间的关系会很有帮助。

• $2^n$ 需要 $n + 1$ 个比特来存储。例如，$2^0=1_2$，$2^1 = 10_2$，$2^2=100_2$，$2^3=1000_2$ 以此类推。
• $2^{n-1}$ 是 $2^n$ 的一半，需要 $n$ 个比特来存储。
• $2^n − 1$ 需要 $n$ 个比特来存储。这是当所有位都设置为 $1$ 时，我们用 $n$ 个比特能存储的最大值。

如果我们取数字 $n$ 并计算 $2^n$，我们会得到一个 $n + 1$ 位的数字，其最高有效位为 1，其余全为 0。在下面的例子中 $n = 3$：

$2^{n-1}$ 等同于 $2^n / 2$。由于它被写成 2 的某个幂，所以它仍然具有最高有效位（MSB）为 1 且其余为 0 的二进制数“形状”，但它需要 $n$ 个比特来编码，而不是 $n + 1$ 个比特。

$2^n − 1$ 是一个所有比特位均设置为 1 的 $n$ 位数字。

在二进制中计算 ≥

如果我们处理的是固定大小（即 $n$ 位）的二进制数，那么数字 $2^{n-1}$ 就很特殊了，因为我们可以很容易地断言一个 $n$ 位的二进制数是否大于或等于 $2^{n-1}$ —— 或者是小于它。我们将 $2^{n-1}$ 称为“中点（midpoint）”。下面的视频演示了如何将一个 $n$ 位数的大小与 $2^{n-1}$ 进行比较：

通过检查 $n$ 位数字的最高有效位，我们就能判断该数字是大于等于 $2^{n-1}$ 还是小于 $2^{n-1}$。

如果我们计算 $2^{n-1} + \Delta$ 并观察该和的最高有效位，我们就能迅速判断出 $\Delta$ 是正还是负。如果 $\Delta$ 是负数，那么 $2^{n-1} + \Delta$ 必然小于 $2^{n-1}$。

检测是否 $u \ge v$

如果我们将 $\Delta$ 替换为 $u - v$，那么 $2^{n-1} + (u - v)$ 的最高有效位就能告诉我们是 $u ≥ v$ 还是 $u < v$。

防止 $2^{n-1} + (u - v)$ 溢出

如果我们限制 $u$ 和 $v$ 最多用 $n - 1$ 个比特来表示，而 $2^{n-1}$ 用 $n$ 个比特来表示，那么就不会发生下溢和上溢。当 $u$ 和 $v$ 都最多用 $n - 1$ 个比特表示时，$|u - v|$ 的最大绝对值就是一个 $n - 1$ 位的数字。

我们看到在这种情况下 $2^{n-1} + (u - v)$ 不会下溢，因为 $2^{n-1}$ 至少比 $|u - v|$ 大 1 个比特。

现在考虑上溢情况。不失一般性，假设 $n = 4$，即四位数字，中点为 $2^{n-1} = 2^{4-1} = 8$ 或 $1000_2$。在此情况下，$|u - v|$ 作为一个 3 位数字所能容纳的最大值为 $111_2$。将 $1000_2 + 111_2$ 相加得出 $1111_2$，这并未产生上溢。

当 $u$ 和 $v$ 为 $n - 1$ 位数字时，判定 $u ≥ v$ 的算术电路总结

• 我们约束 $u$ 和 $v$ 成为最多用 $n - 1$ 位表示的数字。
• 我们创建一个使用 $n$ 个比特编码 $2^{n-1} + (u - v)$ 二进制表示形式的算术电路。
• 如果 $2^{n-1} + (u - v)$ 的最高有效位是 1，则 $u \geq v$，反之亦然。

用于检查是否 $u \geq v$ 的最终算术电路如下。我们将 $n = 4$ 固定下来，这意味着必须将 $u$ 和 $v$ 约束为 3 位数字。感兴趣的读者可以将其推广到其他的 $n$ 值：

Copy
// u and v are represented with at most 3 bits:
2²a₂ + 2¹a₁ + a₀ === u
2²b₂ + 2¹b₁ + b₀ === v

// 0 1 constraints for aᵢ, bᵢ
a₀(a₀ - 1) === 0
a₁(a₁ - 1) === 0
a₂(a₂ - 1) === 0
b₀(b₀ - 1) === 0
b₁(b₁ - 1) === 0
b₂(b₂ - 1) === 0

// 2ⁿ⁻¹ + (u - v) binary representation
2³ + (u - v) === 8c₃ + 4c₂ + 2c₁ + c₀

// 0 1 constraints for cᵢ
c₀(c₀ - 1) === 0
c₁(c₁ - 1) === 0
c₂(c₂ − 1) === 0
c₃(c₃ − 1) === 0

// Check that the MSB is 1
c₃ === 1

断言列表已排序

既然我们有了一个算术电路来比较成对的 signals，我们就对列表中的每个相邻对重复使用该电路，以验证它是否已排序。

示例总结

我们已经展示了如何创建一个算术电路，对上一章中的问题解进行建模。

现在我们可以将此推广：我们可以使用算术电路来对 NP 中的任何问题进行建模。

如何用算术电路对布尔电路进行建模

任何布尔电路都可以使用算术电路进行建模。这意味着我们可以定义一个过程，将布尔电路 B 转换为算术电路 A，这样满足 B 的一组输入就可以转化为满足 A 的一组 signals。下面，我们将概述这一过程的关键组成部分，并详细介绍将特定布尔电路转换为算术电路的示例。

假设我们有以下布尔公式：out = (x ∧ ¬ y) ∨ z。如果（x 为 true 且 y 为 false）或 z 为 true，则该公式为 true。

我们将 x、y 和 z 编码为算术电路 signals，并约束它们的值为 0 或 1。

以下算术电路只有在 x、y 和 z 各自为 0 或 1 时才能得到满足。

Copy
x(x - 1) === 0
y(y - 1) === 0
z(z - 1) === 0

现在让我们展示如何将布尔电路操作符映射为算术电路操作符，假设输入变量已经被约束为 0 或 1。

AND 门

我们将布尔 AND（与）t = u ∧ v 转换为如下算术电路：

Copy
u(u - 1) === 0
v(v - 1) === 0
t === uv

只有当 u 和 v 均为 1 时，t 才为 1，因此该算术电路建模了一个 AND 门。由于约束 u(u - 1) = 0 和 v(v - 1) = 0，t 只能为 0 或 1。

NOT 门

我们将布尔 NOT（非）t = ¬u 转换为如下算术电路：

Copy
u(u - 1) === 0
t === 1 - u

当 u 为 0 时 t 为 1，反之亦然。由于约束 u(u - 1) === 0，t 只能为 0 或 1。

OR 门

我们将布尔 OR（或）t === u ∨ v 转换为如下算术电路：

Copy
u(u - 1) === 0
v(v - 1) === 0
t === u + v - uv

要了解它为何能建模 OR 门，请考虑下表：

如果 u 或 v 是 1，那么 t 至少为 1。为了防止 t 等于 2（这是布尔运算符的无效输出），我们减去 uv，因为当 u 和 v 都为 1 时，它也等于 1。

请注意，对于上述所有逻辑门，我们都不需要应用约束 t(t - 1) === 0。输出 t 被隐式约束为 0 或 1，因为对输入的不存在任何会导致 t 取值为 2 或更大的赋值情况。

将 out = (x ∧ ¬ y) ∨ z 转换为算术电路

现在我们已经了解了如何将布尔电路的所有允许操作转换为算术电路，让我们看一个将布尔电路转换为算术电路的例子。

创建 0 1 约束

Copy
x(x - 1) === 0
y(y - 1) === 0
z(z - 1) === 0

用 NOT 的算术电路替换 ¬ y

out = (x ∧ ¬ y) ∨ z

out = (x ∧ (1 - y)) ∨ z

用 AND 的算术电路替换 ∧

out = (x ∧ (1 - y)) ∨ z

out = (x(1 - y)) ∨ z

用 OR 的算术电路替换 ∨

out = (x(1 - y)) ∨ z

out = (x(1 - y)) + z - (x(1 - y))z

我们针对 out = (x ∧ ¬ y) ∨ z 的最终算术电路是：

Copy
x(x - 1) === 0
y(y - 1) === 0
z(z - 1) === 0
out === (x(1 - y)) + z - (x(1 - y))z

如果需要，我们可以简化最后一个方程：

Copy
out === (x(1 - y)) + z - ((x(1 - y))z)
out === x - xy + z - ((x - xy)z)
out === x - xy + z - (xz - xyz)

out === x - xy + z - xz + xyz

我们也可以将算术电路写成如下形式，且含义没有任何改变：

Copy
x² === x
y² === y
z² === z
out === x - xy + z - xz + xyz

总结

如果 NP 中每个问题的解都可以用布尔电路建模，而且每个布尔电路都可以转换为等效的算术电路，那么由此得出：NP 中每个问题的解都可以用算术电路建模。

在实际应用中，ZK 开发者更倾向于使用算术电路而不是布尔电路，因为如上文的示例所示，它们通常需要更少的变量来完成相同的任务。

我们不需要先计算布尔电路然后再将其转换为算术电路。我们可以直接用算术电路对 NP 问题的解进行建模。

下一步

本文我们掩盖了两个非常重要的细节。实际上还存在一些其他需要解决的挑战。例如：

• 我们没有讨论使用什么数据类型来存储算术电路的 signals，以及如何处理加法或乘法期间的溢出问题。
• 我们无法在不损失精度的前提下表达值 2/3。我们选择的任何定点或浮点表示法都会存在舍入问题。

为了处理这些问题，算术电路的计算是在*有限域 (finite fields)*上进行的：这是数学的一个分支，其中所有的加法和乘法都是在一个素数上取模进行的。

模运算符的引入使得有限域算术与常规算术有着一些令人惊讶的区别，因此下一章将详细探讨它们。

通过 RareSkills 了解更多

欢迎在我们的免费 ZK 图书中了解有关零知识证明 (Zero Knowledge Proofs)的更多信息。本教程正是该书的其中一章。

练习题

1. 创建一个算术电路，接收 signals x₁、x₂、…、xₙ，如果至少有一个 signal 为 0，则该电路得到满足。

2. 创建一个算术电路，接收 signals x₁、x₂、…、xₙ，如果所有 signals 都为 1，则该电路得到满足。

3. 二分图 (bipartite graph) 是一种可以用两种颜色进行染色的图，使得任意两个相邻节点不会拥有相同的颜色。设计一个算术电路方案，以证明你拥有该图有效 2 染色的 witness。提示：本教程中的方案需要进行调整，然后才能适用于 2 染色。

4. 创建一个算术电路，约束 k 为 x、y 或 z 中的最大值。也就是说，如果 x 是最大值，k 应该等于 x，对 y 和 z 也是同理。

5. 创建一个算术电路，接收 signals x₁、x₂、…、xₙ，约束它们为二进制，如果至少有一个 signal 为 1，则输出 1。提示：这比看起来要棘手得多。考虑结合你在前两个问题中学到的知识，并使用 NOT 门。

6. 创建一个算术电路来确定 signal v 是否是 2 的幂（1、2、4、8 等）。提示：创建一个算术电路，约束另一组 signals 来对 v 的二进制表示进行编码，然后对这些 signals 施加额外的限制。

7. 创建一个算术电路来模拟 子集求和问题 (Subset sum problem)。给定一组整数（假设它们都是非负的），确定是否存在一个总和等于给定值 $k$ 的子集。例如，给定集合 $\set{3,5,17,21}$ 且 $k = 22$，则存在一个总和为 $22$ 的子集 $\set{5, 17}$。当然，子集求和问题不一定有解。

   提示 (Hint)

   
   如果一个数字属于该子集，则使用值为 0 或 1 的“开关 (switch)”。

8. 覆盖集问题（covering set problem）从一个集合 $S = \set{1, 2, …, 10}$ 以及 $S$ 的几个定义明确的子集开始，例如：$\set{1, 2, 3}$，$\set{3, 5, 7, 9}$，$\set{8, 10}$，$\set{5, 6, 7, 8}$，$\set{2, 4, 6, 8}$，并询问我们是否最多可以抽取 $k$ 个 $S$ 的子集，使得它们的并集为 $S$。在上面的示例问题中，当 $k = 4$ 时答案是肯定的，因为我们可以使用 $\set{1, 2, 3}$，$\set{3, 5, 7, 9}$，$\set{8, 10}$，$\set{2, 4, 6, 8}$。请注意，对于每个问题，我们可以使用的子集是在一开始就决定好的。我们无法自行构建子集。如果给定子集是 $\set{1,2,3}$，$\set{4,5}$，$\set{7,8,9,10}$，那么将无解，因为数字 $6$ 不在这些子集中。

   另一方面，如果给定 $S = \set{1,2,3,4,5}$ 以及子集 $\set{1}, \set{1,2}, \set{3, 4}, \set{1, 4, 5}$，并问是否可以用 $k = 2$ 个子集进行覆盖，则不存在解。然而，如果 $k = 3$，那么一个有效解将是 $\set{1, 2}, \set{3, 4}, \set{1, 4, 5}$。

   我们的目标是针对给定的集合 $S$ 和定义的 $S$ 子集列表进行证明，看我们是否可以挑出一组子集使得它们的并集为 $S$。具体来说，问题是我们能否用 $k$ 个或更少的子集来做到这一点。我们希望通过将该问题编码为算术电路，以证明我们知道要使用哪 $k$ 个（或更少）子集。

最初发表于 2024 年 4 月 23 日