ZK-SNARKs 的算术化方案

简介

零知识证明 (ZKP) 凭借其在将计算委派给不信任的服务器以及解决去中心化账本所遭受的可扩展性问题方面的诸多应用而越来越受欢迎。 ZKP 允许我们证明给定计算的有效性，而不会泄露敏感数据。 其中一个关键优势是证明是简短的（简洁的），并且其验证时间比计算的幼稚重新执行快得多。 我们可以在去中心化账本中利用这一点，其中每个节点都必须检查交易的正确性。 在这里，最弱的设备充当瓶颈。 如果我们现在可以通过检查一个小的证明（花费几毫秒）来验证交易的有效性，那么可扩展性问题就开始消失了。 我们还可以通过使用递归证明组合、证明聚合 或 折叠方案 来证明我们执行了数千个交易或操作。

为了证明计算的有效性并避免泄露敏感信息，ZKP 依赖于多项式及其属性。 多项式是 ( a_0+a_1x+a_2x^2+a_3x^3+\cdots a_n x^n ) 形式的表达式，其中系数 $a_k$ 是某个 环或域 的元素（例如，整数、实数或有限域的成员，例如 Z/7Z，模 7 的整数）。 现在，为了能够使用多项式，我们必须通过一个称为算术化的过程，能够用多项式来表达我们的计算。

算术化将计算的语句归结为涉及有界次数多项式的代数语句。 算术化可分为两类：

• 电路计算。 大多数 SNARK 使用这种方法。
• 机器计算。 STARK 使用这种方法。

电路计算更适合非结构化计算，并且相对容易支持可组合性。 另一方面，机器计算更适合统一的计算，并支持无界计算。

一些操作可以很容易地转换为算术运算，要么是因为它们是有限域上的代数运算，要么是因为我们可以通过一些细微的更改将它们转换为算术运算。 这导致人们对什么是一个昂贵或简单的计算的看法发生了转变。 例如，流密码是有效的加密方案，在明文（我们要加密的消息）和密钥流（伪随机的比特字符串）之间执行异或运算，处理器可以非常快速地计算异或运算。 然而，就它们的算术化和我们需要描述它们的方程的数量（即，约束的数量）而言，对于 SNARK 来说，它们是昂贵的操作。 SNARK 的代价高昂的运算示例包括按位运算（AND、XOR、OR）、边界检查和比较（因为这些需要将变量分解为比特）。

算术化会给计算时间增加显著的开销。 使用 SNARK 友好的操作，计算时间可能会增加近两个数量级，而对于非友好的操作，则会增加更多。

最近，已经提出了许多不同的优化来减少开销，例如：

• 查找表。
• SNARK 友好的加密原语（例如 Rescue、SAVER 或 Poseidon）。
• 并发证明生成。
• 硬件加速（例如使用 GPU 或 FPGA）。

一般来说，除了基本程序之外，算术化不能手动完成。 此外，使用幼稚的算术化会导致显著的开销。 为了解决这个问题，已经开发了接受高级编程语言的专用编译器，以及零知识虚拟机，例如 CAIRO。 我们将研究最流行的方案：R1CS、AIR 和 Plonkish 算术化。

R1CS

算术电路可以表示为（二次）秩一约束系统 (R1CS)。 这些是方程组，每个方程在每个变量中至多是二次的，形式为

$(\sumk A{ik}z_k)(\sumk B{ik}z_k) - (\sumk C{ik}z_k) = 0$

其中 $A{ik}, B{ik}, C_{ik}$ 是某个有限域 $F$ 中的元素，其中许多为零。 我们可以用这种方式写下任何复杂的计算。 例如，如果我们想计算 $w = x^4$，我们可以将其表示为

$x \times x = w_1$

$w_1 \times w_1 = w$

在这里，我们引入了一个额外的变量 $w_1$，我们必须决定它是公共变量还是私有变量。 重要的是要看到，用于描述给定计算的 R1CS 不是唯一的。 例如，我们可以将先前的计算表示为

$x \times x = w_1$

$x \times w_1 = w_2$

$x \times w_2 = w$

该系统等效于前一个系统，但多了一个约束。

为了实现 R1CS，程序有 gadgets，允许模块化地构建算术电路。 例如，如果我们想使用布尔变量，我们可以使用一个 gadget 来实现约束，这样变量只能取值 0 或 1。 如果我们调用变量 $b$，那么

$b(1-b) = 0$

如果我们想在 $a$ 和 $b$ 之间执行 OR 运算，那么布尔 gadget 也会实现

$a(1-a) = 0$

而 OR gadget 添加

$a + b - ab = c$

Arkworks 库包含用于基本数据类型和操作的 gadgets。 在 Zcash 协议规范 中可以找到运算符和范围检查的常见表达式。

代数中间表示 (AIR)

代数中间表示 (AIR) 是 StarkWare 在其虚拟机 CAIRO (CPU AIR) 中使用的算术化过程。 AIR 由以下三个元素组成：

1. 计算的执行轨迹。 这表示为一个轨迹执行矩阵 $T$，其行表示给定时间点的计算状态，其列对应于在所有计算步骤中跟踪的代数寄存器。
2. 转换约束强制执行轨迹矩阵 $T$ 的两行或多行之间的关系。
3. 边界约束强制执行执行的一些单元格与常量值之间的相等性。

算术化分两个阶段进行：

• 生成执行轨迹和低阶多项式约束。
• 将前两个转换为单个单变量多项式。

构造多项式约束集，以便当且仅当执行轨迹有效时（即，如果该轨迹代表有效的计算），才会验证所有约束。 约束是低阶多项式，但不一定像 R1CS 那样限制为 2 阶。

为了了解 AIR 的工作原理，让我们看几个例子。 假设我们要添加给定大小为 $n$ 的向量 $a=(a_1, a_2, a_3, \dots, a_n)$ 中的所有元素。 我们可以引入一个变量 $t$，从 0 开始，并在每个步骤中加上 $a$ 的一个分量的值。 轨迹矩阵包含两列； 第一列由 $a$ 的元素和 $t$ 中的部分和给出

以下多项式约束可以概括计算的正确性：

$t_1 = 0$

$t_{j+1} - t_j - a_j = 0$ 对于 $j = 1, 2, \dots n$

$a{n+1} - t{n+1} = 0$

在这种情况下，优势在于多项式方程不受限于二阶或更低阶。 乘法逆元 $x^{-1}$，例如 $x \times x^{-1} = 1$ 可以用两种等效形式写出：

$x^{p-2} = y$

$x \times y - 1 = 0$

第一个表达式使用费马小定理，并涉及一个 $p-2$ 阶的门，而第二个表达式的阶数为 2。

STARK 中使用的 AIR 过程遵循以下步骤：

1. 获取执行轨迹。
2. 执行低阶扩展。
3. 评估约束。
4. 将约束组合成组合多项式。

低阶扩展的工作方式如下：

1. 将每个寄存器（执行轨迹矩阵的每一列）作为某个多项式 $f$ 的评估。
2. 在轨迹域上插值 $f$ 以找到其系数。
3. 在更大的域上评估 $f$。

最简单的方法是使用数论变换（这是快速傅里叶变换的有限域版本）。 我们需要选择一个有限域，使其包含 $n$ 次单位根 $w_k$，使得 $w_k^n = 1$，并且 $n$ 是大于行数的 2 的幂 ($n = 2^m$)。 为了获得所有的 $n$ 次方根，我们可以取一个生成器的幂，$\omega$，$\omega^0 = 1, \omega = w_1, \omega^2 = w_2, \dots$ 等。 为了执行低阶扩展，我们可以通过添加 $2n$ 次方根来增加域，并利用我们之前的评估（或 $4n$ 次方根，从而导致 4 倍的膨胀）。

为了评估约束，

1. 定义行之间的代数关系。
2. 将这些关系重新解释为在条件成立的点处具有根的多项式。
3. 从约束多项式中分离出根，以将它们转换为有理约束。

例如，如果我们有行之间的一些关系，例如

$r{k+2} = r{k+1}^2 + 2r_k$

我们可以将其解释为某个多项式 $f$，并将每个步骤与 $x_k = \omega^k$ 相关联，因此

$f(x\omega^2) = (f(x\omega)^2 + 2f(x))$

多项式

$p(x) = f(x\omega^2) - (f(x\omega)^2 + 2f(x))$

在关系 $f$ 成立的点 $x$ 处有根。

然后，我们可以通过将它们除以

$d(x) = \prod_k (x - \omega^k)$

来取出根，其中乘积仅在约束成立的 $k$ 值上进行。 我们得到了所需的多项式，

$g(x) = \frac{p(x)}{d(x)}$

以下恒等式给出了一个实际结果，

$\prod_{k=0}^{n-1} (x - \omega^k) = x^n - 1$

因此，如果我们知道约束在大多数 $\omega_k$ 上成立，则可以使用该恒等式有效地计算 $d(x)$。 例如，如果 $n = 256$，并且它对除 $k = 128, 194$ 之外的所有行都成立，那么

$d(x) = \frac{x^n - 1}{(x - \omega^{128})(x - \omega^{194})}$

对于我们之前的关系

$r{k+2} = r{k+1}^2 + 2r_k$

假设 $r_1 = 1, r_2 = 5$，并且我们想计算直到 $r = 1000$。 我们将使用 $n = 1024$，因为这是大于 1000 的最小 2 的幂。 除了约束对从 3 到 1000 的所有点都有效之外，我们还有对两个初始值的约束：

$f(\omega^0) = 1 = f(1)$

$f(\omega) = 5$

因此，我们得到一些额外的多项式（如果条件成立）：

$p_1(x) = \frac{f(x) - 1}{x - 1}$

$p_2(x) = \frac{f(x) - 5}{x - \omega}$

$p_3(x) = \frac{f(x\omega^2) - (f(x\omega)^2 + 2f(x))}{d_3(x)}$

其中

$$ d3(x) = \frac{x^{1024}-1 }{(x-1 )(x-\omega) \prod{k = 1001}^{1023}(x-\omega^k) } $$

我们最终可以通过取 $p_1, p_2, p_3$ 的随机线性组合来获得组合多项式：

$P(x) = \alpha_1 p_1 + \alpha_2 p_2 + \alpha_3 p_3$

Plonkish 算术化

Plonk 使用的算术化被称为带有预处理的随机代数中间表示（简称 RAP）。 TurboPlonk 和 UltraPlonk 是 RAP 的受限情况。 和以前一样，我们的起点是执行轨迹矩阵 $T$，它由 $n$ 行和 $w$ 列组成。

Plonk 的约束系统（考虑两个扇入门）可以写为

$q_L x_a + q_R x_b + q_O x_C + q_M x_a x_b + q_C = 0$

这可以表示 R1CS 中找到的操作，并允许实现自定义门。 Plonk 原始的算术化方案包括将计算轨迹编码为多项式，为此我们必须检查布线的正确性、多项式是否正确编码输入、每个门是否都正确评估以及最后一个门的输出。

预处理的 AIR (PAIR) 通过添加新列 $c_1, c_2, \dots c_m$ 来扩展执行轨迹，以便新列将参与约束。 这些变量允许我们更改轨迹矩阵中不同行之间的关系。 例如，我们可以交替偶数行和奇数行之间的关系，执行不同的操作。 例如，我们可能想要以下内容：

$x{2n} = x{2n-1}^2$

$x{2n+1} = 2 \times x{2n}$

我们可以通过以下方式对这种关系进行编码

$c_1(xn - x{n-1}^2) + (1 - c_1)(xn - 2x{n-1})$

其中 $c_1 = 1$ 在偶数行中，$c_1 = 0$ 在奇数行中。 因为我们可以使用它们来选择我们要执行的操作，所以它们被称为选择器。 我们可以使用更多的选择器来描述复杂的操作，例如椭圆曲线加法。

我们可以使用 grand product check 来检查两个向量 $a, b$ 是否彼此置换。 给定有限域 $F$ 中的一个随机 $\gamma$，以下等式应该成立：

$\prod (a_i + \gamma) = \prod (b_i + \gamma)$

由于 Schartz-Zippel 引理，我们知道两个多项式在随机采样值处相等的概率小于 $1 - d/|F|$，其中 $d$ 是多项式的次数，$|F|$ 是有限域的元素数。

为了检查此操作是否已正确执行，我们可以引入一个额外的变量 $v$，使得

$v_1 = 1$

$vk = v{k-1} \times \frac{(a{k-1} + \gamma)}{(b{k-1} + \gamma)}$ 对于 $k = 2, n+1$

如果最后一个值 $v_{n+1}$ 等于 1，那么我们以非常高的概率知道列 $a, b$ 是彼此的排列。

Plonk 允许包含查找参数。 这些可以帮助我们通过查看具有预先计算的有效 $(a, b, c)$ 的表来检查两个变量 $a, b$ 之间的给定操作是否产生正确的输出 $c$。 为此，我们需要包含一个表 $t$，其中行给出所有可能的输入/输出组合。 例如，我们可以将 $a, b$ 作为 8 位字符串，并提供 XOR 运算的结果 $c = a \oplus b$。 这总共给出了 $2^{16}$ 种组合。 为了检查结果是否正确，我们可以使用一个随机变量 $\beta$，并计算 $f_k = a_k + \beta b_k + \beta^2 c_k$ 和 $gk = t{k1} + \beta t{k2} + \beta^2 t{k3}$，其中 $t_{ki}$ 是表的元素。 我们将在即将发布的文章中介绍这些参数。

总结

为可验证计算生成 zk-SNARK 的关键步骤之一是将给定的计算机程序转换为多项式。 这个过程被称为算术化，我们有一些方案可以有效地做到这一点，例如 R1CS、AIR 和 Plonkish 算术化。 在第一个中，我们需要 gadgets 来实现数据类型（例如布尔变量、u8 和 i64 变量）及其相关的操作。 在 AIR 和 Plonkish 的情况下，我们需要获取程序的执行轨迹，建立行之间的关系并插值多项式。 这两种方法都需要仔细实施，因为幼稚的方法这样做会导致更多的约束和显著的开销。 幸运的是，新的 SNARK 友好原语、查找参数、自定义门和硬件加速（例如使用 GPU 和 FPGA）的开发可以降低算术复杂度或提高执行计算的速度，并实现更短的证明和验证时间，为现实世界中许多新的、令人兴奋的应用程序打开了大门。

• 原文链接： blog.lambdaclass.com/ari...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～