计算复杂性 + 度界限 STARKs 算术化

引言

这篇博客文章是我们正在进行的系列 STARKs 中的算术化 的第三篇也是最后一篇，该系列对我们论文 "STARKs 的算术化方法研究" 进行了高层次的探索。

💡

本报告比较了之前描述的两种方法，AIR 和 PAIR 的低阶界限，特别考虑邻近测试。它简要讨论了每种方法的计算复杂性以及如何在它们之间过渡，同时还探索了使用选择列来改善某些方面的不同方法。

如果你错过了该系列的前两篇文章，它们分别提供了 AIR 的介绍 和 预处理 AIR 的介绍，你可以对它们进行阅读。‎

‎

比较阶数界限的重要性

在密码协议的世界中，确保低阶邻近测试的健全性至关重要。为了增强这种健全性，必须减少某些多项式的阶数界限。在本文中，我们将首先比较代数中间表示 (AIR) 的复合多项式 和预处理 AIR (PAIR) 的组合约束多项式 的阶数界限。‎

FRI 的特定情况

让我们专注于快速 Reed-Solomon IOPP（FRI）协议，该协议通常在 STARKs 中使用。FRI 提交阶段累积了所有层的遵循阶数的投影轮次的误差。特别是，增加低阶界限会增加 FRI 的健全性错误（这是我们希望最小化的），对于固定批处理 FRI 邻近参数和速率参数。 ‎‎‎

有关更多详细信息，请参阅 "邻近差距" 论文 或 Ulrich Haböck 的 FRI 论文。

‎

AIR 对比 PAIR

考虑到上述细节，比较 和 的阶数界限在确定优化 Reed-Solomon 邻近测试的最佳方法中具有重要意义。为了确保公平比较，在这两种情况下使用的 约束是相同的，并由集合 索引。

AIR 复合多项式

回顾 在 AIR 中使用的复合多项式的公式为

它产生以下阶数界限：

其中 是迹域，并且关于约束 ， 是执行域，而 是表示约束中操作的 AIR 多元多项式。

PAIR 组合约束多项式

对于 PAIR 方法，组合约束公式为：

其紧密阶数界限为：

其中 是 PAIR 选择多项式， 是由集合索引的约束的执行域。

比较这两个表达式的数学复杂性相当技术化，我们在此将不再详细介绍，但如果你感兴趣，可以在我们的 论文 中找到它们。在其中，我们表明 PAIR 的阶数界限永远不会小于 AIR 的阶数界限， 即

事实上，在大多数可测试的情况下，PAIR 将导致明显更大的阶数界限，这对单轮 FRI 健全性来说是个坏消息 → 这需要执行更多的查询轮次，导致更大的证明。因此，在优化低阶邻近测试方面，将所有约束合并为单个约束的选择函数构造并不具优势，更不如使用相应的执行域的单独 AIR 约束。

‎

将选择器分解以优化 PAIR

观察 的公式，你会注意到这个界限随着 的像的基数（即 ）的增加而线性增加。让我们来看一下我们如何通过调整这个参数来降低这个界限。

假设我们处理 8 个不相交的约束，即 ，在不失一般性的情况下，假设 。我们可以像之前一样定义一个单一的选择器列，通过 的值，但是如果我们将选择器分解为 位的二进制表示呢？

具体地说，选择器列会将 约束标记为如下：

在这种适应版本的 PAIR 中，新的组合约束可以写为：

的阶数界限与 的差异为

这预测了每当分解选择器的平均阶数 小于常规选择器的阶数的 倍时，阶数界限会有所改善。虽然这不是对界限的显著提升，但确实为优化创造了较大的空间。

你选择分解选择器列的基数（在上面的例子中为 ）对你正在构建的证明系统有不同的影响，具体而言：基数越小，你需要的额外列就越多，以唯一表示原始值 - 而且你还必须进行低阶扩展 - 尽管阶数界限的优化空间将更大。在思考基数时，必须考虑这些相对的影响。

你可以查看基数对我们的 论文 的影响的详细信息。

‎

计算复杂性

我们现在将快速查看 PAIR 和 AIR 的计算要求，特别是与低阶扩展 (LDE) 相关的部分。

迹函数 、AIR 复合多项式 和 PAIR 组合约束多项式 的 LDE，是证明者在评估域上对上述函数的评估。简而言之，评估域是一个与较小的迹域不相交的大集（请查看我们的 论文 以获取更多详细信息 😉）。

LDE 是相关的性能评估点，因为它是算术化阶段中主要的函数评估步骤，在 RPT 之前，发生在整个评估域上，需要显著的计算努力。

PAIR 中 LDE 的计算缺点

PAIR 中 LDE 的主要缺点源于对额外选择多项式的插值和评估。这些操作会施加计算开销。此外，如果采用分解方法，则必须考虑支持由多个选择器列附加而创建的扩展迹表的系统要求。此外，PAIR 还需要评估所有约束和选择器列的消失多项式。然而，值得注意的是，没有选择器的 AIR 完全绕过了这些问题。

AIR 方法的缺点

相反，AIR 方法的主要缺点在于必须为每个单独的约束计算消失多项式。与此相比，PAIR 将所有约束合并为一个更大约束，仅需计算一个消失多项式。显然，当其根集与一个乘法群紧密对齐时，评估消失多项式会变得更加容易 [StarkWare 的 Medium 文章]。例如，

这避免了显式计算冗长乘积的需求。

考虑应用背景和性能评估

为了充分理解这些细微的计算差异对实际性能的影响，分析每个项目的特定应用背景至关重要。许多因素需要考虑，包括：

1. 证明者和验证者之间的任务分配，同时定义平衡标准。
2. 评估计算要求与处理能力、内存和网络需求，并进行全面的基准测试。
3. 进行现实世界的实践测试，以评估在现实环境中的表现。

在我们进入最后 30 分钟的 100 米冲刺之前，看一看这幅舒缓的森林风景。

‎

混合方法

我们已显示经过 AIR 的 RPT 之后的阶数界限将始终小于或等于相应（常规）PAIR 的阶数界限。然而，可能会在不降低阶数界限的情况下，享受 PAIR 的一些优势。具体而言，如果存在一组适当的约束子集，通过 PAIR 方法结合后最终导致阶数界限最多与 AIR 的复合多项式的阶数界限相同，则混合策略将避免此问题。在这种情况下，PAIR 程序可以在不影响最终低阶界限的情况下使用。

总而言之，我们可以利用 PAIR 组合约束构建一个复合多项式，以提高性能 - 主要是通过减少最终 RPT 分配中的消失多项式数量 - 同时通过获得与相应 AIR 相同的低阶界限来优化低阶邻近测试。

‎

从 PAIR 转回 AIR

让我们看看如何可以轻松地将 PAIR 实现转换为相应的 AIR，其中每个约束都独立定义并附带其执行域，而不是唯一的组合 PAIR 约束多项式 。

在 AIR 中主要的组件是组合约束的消失多项式，而在 PAIR 中是不存在的。那么我们如何获得它们呢？与 PAIR 博文 类似，在开始 PAIR 方法时，选择器值需要在执行轨迹中公开定义。这些值确定在每个执行轨迹行上强制执行的约束。为了开始过渡过程，这些选择器值用于生成执行域作为 的水平集。

完成此步骤后，该过程与 AIR 博文 中的一样，可以总结为：

1. 对每个个别约束多项式应用 APR，使用新定义的 。
2. 使用验证者提供的公共随机数进行 ALI 减少，以构建复合多项式。

总体而言，从 PAIR 转到 AIR 比从 AIR 转到 PAIR 更简单，唯一的重要补充是可选的交互步骤。

‎

总结

完成这系列博客文章后，你现在在构建自己的 STARKs 时更加能够做出设计选择。或者，如果你只是对这些概念感到好奇，我们希望你并且乐在其中！

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