约束

我们的分析主要集中在运算的概念上。然而，该协议实际上并不是要「计算」，而是要检查输出值是否是操作数值的运算的正确结果。这就它被称为约束的原因，即验证者约束证明者为预定义的「程序」提供有效值，无论这个「程序」是什么。多个约束被称为约束系统（Constraint System）（在我们的例子中，它是一个一阶约束系统，Rank 1 Constraint System 或 R1CS）。

注：这意味着找到所有正确解决方案的一种方法是对所有可能的值组合执行暴力破解并仅选择「有效」的组合，或者使用更复杂的约束满足技术 [con18]。

译者注：这个约束定义在算术电路或布尔电路上，因为这两类电路的可满足性问题是 NP 完全问题。

我们也可以使用约束来确保其他关系。例如，如果我们想确保变量 \(a\) 的值只能是 \(0\) 或 \(1\)（即二进制），我们可以使用简单的约束来做到这一点：

$$\color{ForestGreen}{a}\quad \times \quad\color{blue}{a}\quad = \quad\color{red}{a}$$

我们也可以约束 \(a\) 只能为 \(2\)：

$$\color{ForestGreen}{(a - 2)}\quad \times \quad\color{blue}{1}\quad = \quad\color{red}{0}$$

一个更复杂的例子是确保数字 \(a\) 是一个 4 位（Bit）数字（也称为半字节），换句话说，可以用 4 位来表示 \(a\)。我们也可以称之为「确保数字范围」，因为 4 位数字可以表示 \(2^4\) 种组合，0 到 15 范围内有 16 个数字。在十进制数字系统中，任何数都可以表示为以 10（即我们手上手指的数量）为底的幂以及相应的系数的和，例如，\(123 = 1\cdot 10^2 + 2\cdot 10^1 + 3\cdot 10^0\)。同样，二进制数可以表示为以 2 为底的幂以及相应系数的和，例如，\(1011\ \text{(二进制)} = 1\cdot 2^3 + 0\cdot 2^2 + 1\cdot 2^1 + 1\cdot 2^0 = 11\ \text{(十进制)}\)。

因此，如果 \(a\) 是一个 4 位数字，那么对于某些布尔值 \(b_0, b_1, b_2, b_3\)，\(a = b_3\cdot 2^3 + b_2\cdot 2^2 + b_1\cdot 2^1 + b_0\cdot 2^0\)。约束可以如下：

$$1:\quad\color{ForestGreen}{a}\quad \times \quad\color{blue}{1}\quad = \quad\color{red}{8\cdot b_3 + 4\cdot b_2 + 2\cdot b_1 + 1\cdot b_0}$$

为了确保 \(b_0, b_1, b_2, b_3\) 只能是二进制，我们需要添加：

$$2:\quad\color{ForestGreen}{b_0}\quad \times \quad\color{blue}{b_0}\quad = \quad\color{red}{b_0}$$

$$3:\quad\color{ForestGreen}{b_1}\quad \times \quad\color{blue}{b_1}\quad = \quad\color{red}{b_1}$$

$$4:\quad\color{ForestGreen}{b_2}\quad \times \quad\color{blue}{b_2}\quad = \quad\color{red}{b_2}$$

$$5:\quad\color{ForestGreen}{b_3}\quad \times \quad\color{blue}{b_3}\quad = \quad\color{red}{b_3}$$

可以通过这种方式应用相当复杂的约束，以此来确保使用的值符合规则。需要注意的是，上述约束 1 在当前运算的结构中是不可能的：

$$\color{ForestGreen}{\sum_{i=1}^{n} c_{\textrm{l},i} \cdot v_i}\quad \times \quad\color{blue}{\sum_{i=1}^{n} c_{\textrm{r},i} \cdot v_i}\quad = \quad\color{red}{\sum_{i=1}^{n} c_{\textrm{o},i} \cdot v_i}$$

因为值 \(\color{blue}{1}\)（以及来自前一个约束的 \(\color{ForestGreen}{2}\)）必须通过 \(\color{blue}{c \cdot v_{one}}\) 来表示，其中 \(\color{blue}{c}\) 可以被固化在证明密钥中，但 \(\color{blue}{v_{one}}\) 可能为任何值，因为它是证明者提供的。虽然我们可以通过设置 \(c = 0\) 来强制 \(c \cdot v\) 为 \(0\)，但在我们受限的结构中很难找到一个约束来强制 \(v_{one}\) 为 \(1\)。因此，验证者应该有一种方法来设置 \(v_{one}\) 的值。

译者注：我们前文中提到的表达式的约束关系就被称为 R1CS。