本文解释了如何思考和利用 PLONK 中使用的算术化类型。

原文标题：《From AIRs to RAPs - how PLONK-style arithmetization works》

撰文：Ariel Gabizon

编译：Xiang

我们在这篇文章中解释了如何思考和利用 PLONK 中使用的算术化类型。在其最一般的形式中，我们将这种算术化称为带预处理的随机性 Air，简称 RAP。然而，在实践中，处理 RAP 的约束情况通常会变得便利，我们称之为 turbo-Plonk 和 ultra-Plonk 程序。在本文中，我们将解释以上所有这些术语！

我们的起点是 Algebraic Intermediate Representations - AIRs；这是 STARKWARE 使用的算术化。

AIRs

一个 AIR [1] P 在一个域 F 有长度为 n, 和宽度为 w。

P 由一组 2w 个变量，预定义阶数 d 的约束多项式 定义 {f​i​​} 。

P 的执行轨迹 T 由 F 的元素长度为 w 的 n 个向量组成。我们认为是「行宽 w」。

T 是有效的，如果将任意两个连续行 [2]​​ 的 2w 值替换为任何约束多项式 fi，则计算结果为零。

STARK 可以证明我们知道有效 P 的执行轨迹与一些验证者定义的边界约束一致：例如，我们可以要求轨迹的第一行的第一个值应该为零。 （这与 SNARK 文献中所说的公共输入相同。）

让我们看一个经典的例子 —— 斐波那契数列。

我们使用宽度 w=2；作为边界条件，我们要求第一行包含两个。 然后我们使用约束多项式

有效的长度轨迹 n=4 看起来像这样：

也就是说，有效轨迹必须包含斐波那契数列的连续元素。因此，在第四行的第二个值 21 上添加边界条件将验证这确实是正确的第 8 个斐波那契元素。

PAIRs - 带有预处理列的 AIRs

在一个预处理 AIR（Preprocessed AIR), 或者说 PAIR T, 我们有一个额外的参数 t, 并且 t 预处理 / 预定义了列 c1,…,ct∈F^n。除了证明者提供的 w 列外，一个执行轨迹现在还包括 {ci} 。( 我们将证明者提供的列称为执行轨迹的见证部分。)

举例来说当 t=1，w=2，n=4，执行轨迹可能如下所示：

这个多项式约束 fi 将有 2(t+w) 个 变量 —— 换句话说，预定义值 ci,j 参与了约束。

为了说明 PAIRs 强大的功能，让我们看看如何使用它们来模拟 AIR，其中不同行的约束不同。​[3]​​ 一个天然的例子就是 AIR，其中对于某些行，我们希望执行的行值相加（并且，比如说，在下一行的第一列中获得加法结果）；对于其他行，我们希望执行乘法。

为此，我们将 PAIR P 定义如下：我们设置 t=1，并将列 c1​​ 定义为行中的一员，当然我们想要相加时为 1，以及当我们要相乘时为 0。

P 的单约束多项式为：

变量 C1​​ 是从预定义的列 c​1​​ 分配的。

很明显，根据 c1 的值强制执行加法或乘法关系。

例如，在我们希望执行两次加法然后执行一次乘法的程序中，执行轨迹可能如下所示（请注意最后一列不受约束）：

因为可以通过这种方式使用预定义的列来选择操作，所以它们通常被称为「选择器 (selecors)」。 ​[4]​​

门 (gate) 之间交替：

上面的例子示意并建议了人们设计 PAIR 的典型方式：我们预定义了几组约束，将每一组视为一个「门」。 然后，在设计我们的最终程序时，我们将这些门分配给每一行。如上例所示，选择器将用来为我们的程序“编译”成 PAIR。

值得注意的是，除了使用选择器在门之间切换外，很多时候门本身也会使用选择器来实现更大的灵活性。一个典型的例子是通过预定义点添加椭圆曲线的门 - 预定义点将在选择器的值中编码。

RAPs - 插入验证者随机性的 PAIRs

我们的最终模型是允许多轮交互，其中验证者发送域中随机元素，而证明者可以在看到这些域元素后随后添加更多列。

约束多项式现在可以使用验证者随机性作为附加变量。

我们将这样的程序称为 RAP (Randomized AIR with Preprocessing) 。

让我们用下面的例子来说明 RAP。假设我们有一个宽度为 2 的 AIR，并且想要检查证明者提供的列是否是彼此的排列。

假设这些列的值为 a1,…,an,b1,…,bn。

从 Schwartz-Zippel 引理我们知道，要检查它们是否是彼此的排列，只需检查对于统一选择的 γ∈F，我们有很高的概率。

上等式右侧（RHS）的因子都是非零的，在这种情况下，这相当于

一个 RAP 长度为 n + 1 和总宽度为 3 可以很容易地检查：

证明者首先发送列 (a1,…,an,0)，(b1,…,bn,0)

验证者随机发送 γ∈F。

证明者发送第三列 (1,z1,…,zn) 这样对于每个 i∈[n]

如果 z 是这样定义的，我们的排列检查相当于检查 zn=1。我们可以将其添加为边界约束。

此外，程序必须检查 z 确实是这样定义的。

以此目的

为了说明，下面是这个程序的有效执行轨迹，是当 b 只是 a 的一个移位时：

这里可能在哲学上很有趣的是，随机性使局部约束（相邻行之间）能够验证全局属性（列是彼此的排列）。

turbo-PLONK 和 ultra-PLONK 程序 - 便于 RAPs 的特别用例

RAPs 比 PAIRs 更强大，但是对于程序设计通常想到一个 PAIR 是很方便的，同时允许自己将 RAP 的一些特殊功能使用黑盒，稍后，这个程序会编译成最后的 RAP。

RAP 的一种非常有用的特殊功能是强制复制约束。

这意味着强制轨迹的某些元素相等。例如「第一列的第二个元素 a​2 ​​必须等于第二列的第 40 个元素 b40​​」。这就赋予了程序一定的长时记忆能力。

turbo-plonk 程序 是一个 PAIR，具有在执行轨迹的任意两个元素之间定义复制约束的额外能力。

「在 turbo-Plonk 中编程」的实用方法：

复制约束使设计人员能够抽象出对执行轨迹和 PAIR 的明确思考，而是设计如下程序：

• 我们有一组见证变量，其值只能在程序中设置一次。
• 我们在每个步骤中选择将哪个门应用于哪些变量。

上面的内容可能看起来微不足道，也并没有说太多。然而，复制约束对于这种简化的设计方法至关重要的原因是，当见证变量参与两个门时，复制约束将确保两个门中确实使用相同的值，即使它们最终可能会出现在实际 RAP 中完全不同的行。

ultra-Plonk 编程

一个 ultra-Plonk 程序 ​[5] ​​是一个 turbo-Plonk 程序，带有一个额外的、非常强大的门类型，称为查找门（lookup gate）。

这意味着作为设计程序的一部分，我们定义了一组表 T1，... ,Tk。这些表的元素是一定长度 t（这将是程序的参数）的域元素的元组 (tuples)。

现在，在设计程序时；我们被允许使用具有以下形式的查找门：「检查这些 t witness 变量的元组是否在表 T4 中（例如）。」

在这一点上，从 RAP 到具有此类功能的程序的飞跃似乎有点神奇。有关如何通过我们在上一节中展示的多重集检查确实可以实现复制约束和查找表的详细信息，请参阅这篇文章。

何时使用 lookup gates

启用查找门在最终的 SNARK 中有很大的成本；根据经验，一旦查找次数与表一样大，它就会得到回报。

总的来说：

对于程序设计者来说，使用 turbo 和 ultra-plonk 程序通常会很方便，考虑将哪些门应用于哪些见证变量。这已经很底层了，而且足够复杂和通用！然而，有时最好记住引擎盖下有一个 RAP，当需要时，可以利用验证者的随机性来获得更具体 / 更有效的功能。

这一切与 R1CS 有什么关系？

如果你熟悉 SNARK 开发和文献，可能已经看过 R1CS 约束格式，其中所有约束都具有以下形式

R1CS 很好地捕捉了从 [GGPR] 到 Groth 优化版本的一系列作品的约束格式。这项工作依赖于检查指数中秘密元素的验证者方程。正如我们目前拥有的加密货币 k- 线性映射仅适用于 k = 2 个（通过椭圆曲线配对），R1CS 确实是这些协议可以使用的最通用的约束形式。

然而，构建 SNARK 的多项式 IOP 方法（可能明确地从 Sonic 开始）支持更灵活的约束格式。特别是，可以使用大于二的阶数约束。

当使用 GGPR 方法时，R1CS 有一个很好的理论优势——不需要随机预言机模型；还有一个很好的实际优势——证明者组指数的数量不依赖于加法门的数量或 fan-in。然而，获得这些优势需要为每个电路的做可信设置。

假设我们正在使用 Sonic、Plonk 和 Marlin 这样的通用设置系统，可能更难说我们应该将自己限制在 R1CS 上。

Ariel Gabizon 著。感谢 Suyash Bagad, Eli Ben-Sasson and Daira Hopwood 的建议与修正。

[1] 有关 STARKWARE 对 AIR 的全面描述，请参阅此处的定义。

[2] 有人可能会问为什么只在两个连续行的元素之间有约束？实际上，AIR 的一般定义是由一组“掩码” (i1,j1),...,(is,js) 参数化的，并且对集合施加了约束执行跟踪中距某行开头这些偏移量处的元素的数量。我们坚持使用连续两行的版本，既是为了简化演示，也是因为在最终的 SNARK 中有许多偏移量的效率价值，通常主要是证明长度。 

[3] 事实上，STARKWARE 对 AIRs 的一般定义确实有部分能力可以对不同的行有不同的约束。它是部分的，因为验证者必须为该行子集的消失多项式的算术复杂性付出代价。 （同样，请参阅此处了解详细信息。） 

[4] 有关使用选择器的更多示例，请参阅 Plonk 论文和 turbo-Plonk 论文的第 6 节。 

[5] Electric Coin Company 在 Halo 2 项目中定义了一个非常相似的 ultra-Plonk Arithmetization 概念。一个主要区别是它们的定义和实现都允许在任意偏移量的行之间进行约束。