ZK-SNARKs中的算术化

• 原文：Arithmetization schemes for ZK-SNARKs
• 作者：Not a Monad Tutorial
• 译者：Kurt Pan

零知识证明（ZKP）正在因其在代理计算给不受信任的服务器，解决去中心化账本的可扩展性问题等方面的诸多应用而逐渐变得流行起来。ZKP 让我们可以在不泄露敏感数据的情况下证明给定计算的有效性。其主要优势是证明简短（简洁），且验证时间远比原始计算重新执行要快得多。可以在去中心化账本中利用这一点，这里每个节点都必须检查交易的正确性，性能最弱的设备会成为瓶颈。如果我们现在可以通过检查一个小证明（只需几毫秒）来验证交易的有效性，那么可扩展性问题就消失了。我们还可以使用递归证明组合、证明聚合或折叠方案，来生成表明我们执行了数千笔交易或操作的证明。

为了证明计算的有效性且避免泄露敏感信息, 零知识证明会依赖多项式的性质。多项式是形式为 $a_0+a_1x+a_2x^2+a_3x^3+…a_nx^n$ 的表达式, 其中系数 $a_k$ 是某个环或域（例如， 整数、实数或有限域, 如 $\mathbb Z/7\mathbb Z$，模7的整数）中的元素。

为了能够使用多项式，必须通过一个称为算术化的过程来将计算表示为多项式。 算术化将计算语句归约为关于有界次多项式的代数语句。

算术化可以分为两类:

1. 电路计算。大多数SNARK都使用这种方法。
2. 机器计算。STARK采用这种方法。

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

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

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

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

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

一般来说，除初级程序外，不要手动进行算术化。 此外，使用朴素算术化会导致大量开销。 为了解决这个问题，已经开发出了接受高级编程语言的专用编译器，以及零知识虚拟机，例如 CAIRO。 下面我们将介绍最流行的方案，R1CS、AIR 和 plonkish 算术化。

R1CS

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

$$ (∑\limitskA{ik}z_k)(∑\limitskB{ik}z_k)−(∑\limitskC{ik}z_k)=0\qquad \qquad(1) $$

其中$ A{ik},B{ik},C_{ik}$ 是有限域 $\mathbb F$ 中的元素，其中许多项为零。我们可以用这种方式表示任何复杂的计算。例如，如果我们想计算 $w=x^4$，我们可以表示为 $x×x=w_1\w_1×w_1=w$ 我们引入了一个额外的变量 $w_1$，需要制定是公开变量还是私有变量。重要的是描述给定计算的 R1CS 是不唯一的。 例如，我们可以将先前的计算表示为

$ x×x=w_1\x×w_1=w_2\x×w_2=w $这个系统等价于前一个系统，但就会有一个额外的约束。

要实现 R1CS，程序有小组件，允许模块化地构建算术电路。例如，如果我们想使用布尔变量，我们可以有一个小组件来实现约束，使得变量只能取值0或1。如果我们将变量称为 $b$，那么

$$ b(1−b)=0\qquad\qquad\qquad\qquad(2) $$ 如果我们想在 $a $和 $b$ 之间进行 OR 操作，那么布尔小组件也会实现

$$ a(1−a)=0\qquad\qquad\qquad\qquad(3) $$ 以及 OR 小组件添加了 $$ a+b−ab=c\qquad\qquad\qquad\quad\,(4) $$ Arkworks 库包含了对基本数据类型和操作的小组件。在 Zcash 协议规范中也可以找到操作符和范围检查的常用表达式。

代数中间表示（AIR）

代数中间表示（AIR）是 StarkWare 在其虚拟机 CAIRO（CPU AIR）中使用的算术化过程。AIR 包含以下三个元素：

1. 计算的执行迹。表示为执行迹矩阵 T，其行表示在给定时间点的计算状态，列对应于一个代数寄存器在所有计算步骤中的状态变化。
2. 转换约束约束了迹矩阵 T 两行或多行之间的关系。
3. 边界约束确保了执行中某些单元格和特定常量之间的相等关系。

算术化分为两个阶段：

• 生成执行迹和低次多项式约束。
• 将这二者转换为一个单变量多项式。

构造多项式约束集合使得：当且仅当执行迹有效（即迹表示一个有效计算）时，所有约束都能得到验证。这些约束是低次多项式，但不一定限于（比如R1CS情况下的）2次多项式。

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

下面的多项式约束可以囊括计算的正确性： $t1=0 \t{j+1}−t_j−aj=0 \ for \ j=1,2,…n \a{n+1}−t_{n+1}=0 \$

这种情况的优势在于多项式方程不受次数小于等于 2 的约束。乘法逆元$ x^{−1}$，满足 $x×x^{−1}=1$，可以用两种等价形式表示：

$x^{p−2}=yx×y−1=0$

第一个表达式使用了费马小定理，涉及到次数为$ p−2 $的门，第二个则为 2 次。

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

1. 获取执行迹。
2. 进行低次扩展。
3. 求解约束。
4. 将约束组合成组合多项式。

低次扩展操作如下：

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

解决问题的最简单方法是使用数论变换（快速傅里叶变换的有限域版本）。我们需要选择一个有限域，使其包含$ n$ 次单位根 $w_k$，使得 $w_k^n=1$，且 $n $是大于行数的 2 的幂次$（n=2^m）$。要获得所有$ n$ 次根，我们可以取生成元 $ω$ 的幂，$ω_0=1,ω=w_1,ω^2=w_2$,… 等等。要进行低次扩展，可以通过添加 $2n$ 次单位根来增加定义域，并使用之前的求值（或者 $4n$ 次单位根，这会导致4倍膨胀）。

要求值约束，需要：

1. 定义行之间的代数关系。
2. 将这些关系重新解释为在满足条件的点处具有根的多项式。
3. 从约束多项式中除掉根，将其转换为有理约束。

例如，如果我们在行之间有一些关系，如$ r{k+2}=r{k+1}^2+2r_k$ 我们可以将其解释为某个多项式 $f$，并将每个步骤与 $x_k=ω^k$ 关联，于是

$f(xω^2)=(f(xω)^2+2f(x))$ 多项式

$$ p(x)=f(xω^2)−(f(xω)^2+2f(x))\qquad\qquad\quad(6) $$

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

然后可以将其除以

$$ d(x)=∏\limits_k(x−ωk)\qquad\qquad\qquad\qquad\qquad\qquad(7) $$

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

$$ g(x)=\frac {p(x)}{d(x)}\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad(8) $$ 以下等式给出了一个实用的结果， $$ ∏\limits_{k=0}^{n=1}(x−ωk)=x^n−1\qquad\qquad\qquad\qquad\qquad\quad(9) $$ 因此，如果我们知道约束在大多数$ ω^κ$ 上成立，那么可以使用该等式高效地计算出$d(x)$。例如，如果$ n=256$，并且对除了 $k=128,194$ 外的所有行都成立，那么有

$$ d(x)=\frac {x^n−1}{(x−ω^{128})(x−ω^{194})}\qquad\qquad\qquad\qquad(10) $$ 对于之前的关系

$$ r{k+2}=r^2{k+1}+2r_k\qquad\qquad\qquad\qquad\qquad\,\,\,\,\qquad(11) $$ 设 $r_1=1,r_2=5$，我们想要计算到$r=1000$。我们将使用 $n=1024$，因为这是大于 1000 的最小的 2 的幂。约束除了对从 3 到 1000 的所有点有效外，我们还有两个初始值的约束： $f(ω^0)=1=f(1)\f(ω)=5$ 因此，我们得到了一些额外的多项式（如果条件确实成立）：$ p_1(x)=\frac {f(x)−1}{x−1}$

$$ p_2(x)=\frac {f(x)−5}{x−ω}\qquad\qquad\qquad\qquad\qquad\qquad\,\,\,(12) $$ $$ p_3(x)=\frac {f(xω^2)−(f(xω)^2+2f(x))}{d_3(x)}\qquad\qquad\quad(13) $$ 其中 $$ d3(x)=\frac {x^{1024}−1}{(x−1)(x−ω)∏^{1023}{k=1001}(x−ω^k)}\qquad\qquad(14) $$ 最后，我们可以通过对 $p1,p2,p3$ 取一个随机线性组合来获得组合多项式： $$ P(x)=α_1p_1+α_2p_2+α_3p_3\qquad\qquad\qquad\qquad\qquad(15) $$

Plonkish 算术化

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

Plonk 的约束系统（考虑扇入2的门）写为

$$ q_Lx_a+q_Rx_b+q_OxC+q_Mx_ax_b+q_C=0\qquad\qquad\quad(16) $$ 这可以表示在R1CS中包括的操作，且可以实现自定义门。Plonk 的原始算术化方案包括将计算迹编码为多项式，必须检查连线的正确性，包括多项式是否正确地编码输入，每个门是否正确地求值，以及最后一个门的输出。

预处理AIR（PAIR）通过添加新的列 $c_1,c_2,…c_m$ 来扩展执行迹，这样的新列将参与约束。这些变量可以让我们改变迹矩阵中不同行之间的关系。例如，我们可以在偶数行和奇数行之间交替进行不同的操作。比如我们可能想要以下内容：

$x{2n}=x^2{2n−1}\x{2n+1}=2×x{2n} $可以通过执行以下操作来编码这种关系： $$ c_1(xn−x^2{n−1})+(1−c_1)(xn−2x{n−1})\qquad\qquad\qquad\,(17) $$ 其中 $c_1=1$ 在偶数行，$c_1=0$ 在奇数行。因为我们可以用它们来选择要执行的操作，所以它们被称为选择子。我们可以使用更多的选择子来描述复杂的操作，例如椭圆曲线加法。

我们可以使用大连乘检验来检查两个向量$ a,b$ 是否是彼此的置换。给定有限域$\mathbb F$ 中的一个随机数$ γ$，以下等式应成立： $$ ∏(a_i+γ)=∏(b_i+γ)\qquad\qquad\qquad\qquad\qquad\quad(18) $$ 根据 Schartz-Zippel 引理，我们知道两个多项式在随机采样值处相等的概率小于$ (1−d)/|\mathbb F|$，其中$ d$ 是多项式的次数，$|\mathbb F|$ 是有限域元素的数量。

为了检查这个操作是否被正确执行，我们可以引入一个额外的变量 $v$，使得 $v_1=1\vk=v{k−1}×(a{k−1}+γ)/(b{k−1}+γ) \ for\ k=2,n+1$ 如果最后一个值$ v_{n+1}$ 等于1，那么我们就知道，以非常高的概率，列 $a,b$ 是彼此的置换。

Plonk 可以包括查找论证。这种论证可帮助我们通过查找具有预先计算的有效$ (a,b,c)$ 的表，来检查两个变量$a,b $之间的给定操作产生的输出 $c$ 是否正确。 为此，我们需要引入一个表$ t$，其中的行给出所有可能的输入/输出组合。例如，我们可以取 $a,b$ 是8比特字符串，并提供异或操作的结果，$c=a⊕b$。这给出了总共 $2^{16}$ 种组合。为了检查结果是否正确，我们可以使用一个随机变量$ β$，并计算 $f_k=a_k+βb_k+β^2c_k $和 $gk=t{k1}+βt{k2}+β^2t{k3}$。其中 $t_{ki}$ 是表中的元素。我们将在后续文章中介绍这类论证。

总结

在生成可验证计算的zk-SNARKs的过程中，一个关键步骤是将给定的计算机程序转换为多项式。这个过程被称为算术化。我们有一些高效的方案来实现算术化，如 R1CS、AIR 和 Plonkish 算术化。在R1CS中，我们需要小组件来实现数据类型（如布尔类型、u8 和 i64 变量）及其相关操作。而对于 AIR 和 Plonkish，我们需要获取程序的执行迹，建立行之间的关系并插值多项式。两种方法都需要仔细实现，因为朴素的方法可能导致更多的约束和显著的开销。幸运的是，新的 SNARK 友好原语、查找论证、自定义门和硬件加速（如使用 GPU 和 FPGA）的发展可以降低算术复杂性或提高计算速度，使得证明和验证时间更短，为许多新颖和激动人心的现实世界中应用敞开了大门。

本文首发于：https://cryptography.land/2023/04/04/arithmetization