STARKs 系列第二部分 - 预处理的 AIR 的算术化

原文公式有缺失

这篇博客是我们持续系列“STARKs中的算术化”的第二部分，这是对我们论文STARKs的算术化方法研究的高层次探索。

你可以在这里阅读第一部分：AIR简介。

本系列的第二部分探索了一种不同的强制计算完整性声明的方法：预处理 AIR，或称PAIR。它构造了与AIR相同形式的多项式约束，但将多个不相交的约束组合成一个更大的约束，从而避免了应用不同的强制域。让我们开始吧！‎

PAIR的发现

在这篇博客中，我们探讨了预处理AIR（PAIR）的概念，这一概念最初出现在Aztec的帖子中。不重复太多文章，基本示例依赖于一个执行轨迹，它受到两个不同的不相交约束的限制；通过使用额外的数据输入 - 选择器列 - 我们可以将这些组合成一个更大的约束，如下所示：

其中 将是执行轨迹域中的一个点。可以很容易看出，当选择器取值时，约束 将被强制执行，并且约束 也是如此。

立即来看，这种方法似乎简化了在每一行中选择要应用的约束 — 毕竟，我们只需在选择器列中放入唯一标识约束的常数 — 或者至少看起来更符合程序员的习惯，对吧？

文章使用此示例仅作为解释不同概念的基础，并未进一步扩展此特定应用。我们发现这个想法非常引人入胜，并决定尝试将其正式化，并将其推广至多个约束，同时检查其优势和缺点。特别是，我们会关注这种方法如何影响随后的低阶接近测试的度数界限，以及它在相对于AIR对应物时对证明的计算复杂性有何影响。

执行轨迹

在我们进一步深入之前，回顾上一篇博客中对执行轨迹的定义，AIR简介。一个通用的轨迹可以通过如下表格表示：

查看这个示例以了解它的实际应用：

示例： 假设我们有一个 轨迹表，受到3个不同约束的限制：

这些可以解释为：

• 在第 行，轨迹值必须是 ,
• 在第 行和 行，轨迹值必须等于前一个值，和
• 在第 行、 行和 行，轨迹值是前一个值的两倍。

这个约束集合的有效轨迹将是：

‎

预处理AIR（PAIR）

预处理AIR是一种算术化程序，将多个不相交的约束组合为一个单一的约束，即那些不同时强制执行的约束。这是通过向轨迹表附加一列额外数据（因此称为预处理）来实现的，这将充当约束的选择器。

可以将Aztec的帖子中二元选择器的概念推广，以组合多个约束。选择 作为要组合为单个“更大”约束的不相交AIR约束的索引集。组合后的约束加入了 个不相交的AIR约束，其中 如果 ，则 ，其中. 在这种情况下，选择器函数 将在集合 中取值，以便仅选择一个可激活的 。

新列将被解释为选择器函数 在轨迹域 上的评估，如下所示。

回想一下，在AIR中，由 索引的约束将是诸如

我们希望将所有这些约束组合成单个语句，如

为此，我们可以简单地定义新的多项式 作为所有 的组合，使用选择器函数 ，如

其中 是可选的度数调整随机多项式，而 是集合 的消失多项式。（如果你不记得这是什么，请查看第一部分。）在实践中，选择器函数 将被构建为选择器列的插值多项式，以最小化其度数，同时完成其任务。

通过检查，我们可以看到函数 具有以下性质：

因此，在 ，函数 仅选择一个可激活的 ，如预期。

听起来复杂吗？让我们看看如何应用这个公式。

📝

前述示例的继续： 回想一下约束的逐行放置，附加相应的选择器列将得到以下预处理轨迹表：

通过直接应用公式 ，组合的约束多项式变为：

你可以很容易地检查出：

从而在其适当的强制域中强制执行预期的约束。

如论文中所述，这个组合多项式具有紧密的度数界限：

回顾这些 是多元AIR多项式，且它们的度数 衡量轨迹函数 在该约束中出现的乘法次数。例如， 对应于 ，而 将拥有 。

‎

PAIR中的代数放置与路由

接下来，我们将像对待AIR约束一样对APR进行操作，但注意到新的强制域只是所有单独约束的并集，我们称之为 。这样，如果函数 对每个 的元素都有一个根（诚实证明者的情况），那么

定义了一个适合低阶接近测试的新多项式。因此，我们可以在诚实证明者的情况下推导出该多项式的度数界限为

利用验证者已知的最紧的上界。关于完整性，当原始计算完整性声明有效时，这个约束成立。关于可靠性，如果未使用随机代数链接，则反向推论也成立；否则，该等价关系“仅仅”是很有可能成立。

总结

通过这一篇文章，你现在能够将不相交的AIR约束的强制转换为单一的、更大的约束，从而仅依赖一个包罗万象的强制域。在下一篇文章中，我们将比较这两种不同方法在赖德-所罗门接近测试中所产生的度数界限。你不会想错过本系列的第三部分！

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