Circle STARKs（三）： Circle FFT
原文：https://blog.zksecurity.xyz/posts/circle-starks-3/
作者：Varun Thakore
译者：Kurt Pan
回顾
在本系列的第一部分中，我们探讨了梅森素域上的高效算术，以及使用它们来实例化 STARK 协议的一个关键挑战，即缺乏平滑乘法子群。
在第二部分中，我们研究了如何使用圆群来解决这个问题。我们介绍了圆群陪集的结构，即孪生陪集和标准位置陪集，它们可以用来实例化 STARK 协议。我们还讨论了定义在圆群上的多项式空间，以及在这些陪集上构造消失多项式的方法。
介绍
有两种常用方法表示次数小于 的单变量多项式 ：
单项式基：
，其中 为系数， 为单项式基多项式，满足：
拉格朗日基：
其中 是点 处 的求值， 是满足以下条件的拉格朗日基多项式：
对所有 ，
拉格朗日基多项式定义为：
一般来说，FFT 算法会将一个多项式基转换为另一个多项式基。例如，它可以将一个多项式从单项式基转换为拉格朗日基，反之亦然。这种基的转换非常有用，因为某些运算（例如多项式乘法）在拉格朗日基中会变得非常高效。
在 STARK 协议中，计算迹通常表示为乘法子群中点的一组多项式求值，这意味着可以使用 Cooley-Tukey 风格的 FFT 来计算多项式的系数。
在Circle STARK 中，乘法子群被孪生陪集取代：它不是一个群，而是单位圆陪集的并集。元素遵循“角度加法”或“复数乘法”群律，每个元素对应于圆上的一个点 。在Circle FFT 中，给定孪生陪集的求值，插值一个二元多项式。
本文将通过与经典的 Cooley-Tukey FFT 进行比较，对 Circle FFT 进行直观理解。在整篇文章中，使用 FFT 来表示插值，从拉格朗日基过渡到单项式基；使用逆 FFT 来表示求值，从单项式基过渡到拉格朗日基。
Cooley-Tukey FFT
本节将介绍 Cooley-Tukey FFT 算法的通用版本。这个通用版本最终将帮助我们理解 Circle FFT 作为通用结构的具体实例。为了建立直观的理解，我们将结合该通用描述，伴随讲解一个具体示例。
问题陈述
给定在大小为 的求值域 上的多项式求值，我们的目标是根据某些基多项式计算多项式的系数，使得：
其中， 是我们希望计算的系数， 表示基多项式。
例子：Cooley－Tukey FFT，其中 给定大小为 的乘法子群 上的多项式的求值 ，目标是计算次数为 的多项式的系数 。 对于此例，令 为 的一个乘法子群，由 生成。则：
假设 上的多项式的求值为：
算法
Cooley－Tukey FFT 算法遵循经典的分治策略。其流程如下：
步骤 1：将多项式 分解为一系列低次多项式，并在较小的求值域上找到这些低次多项式的求值。 步骤 2：递归地对每个低次多项式应用 FFT 来计算它们的系数。 步骤 3：合并低次多项式的系数，计算原多项式 的系数。
在FFT算法的每个递归层 ，我们使用以下关键组成部分来分解多项式 ：
：多项式映射 是一个 到 1 的映射，这意味着它将求值域 的 个元素映射到更小求值域 中的单个元素。
由于 ，这意味着 。在乘法子群上这种映射的一个常见例子是：
：旋转因子 是将求值域 中的元素映射到域 的多项式，即对于
对于固定的 在映射 下的纤维由 中所有映射到 的元素组成。令 表示元素 在多项式映射 下的纤维，即：
https://en.wikipedia.org/wiki/Fiber_(mathematics)
由于 是一个 到 1 的映射，每个 的纤维是 的子集，恰好包含 个元素。 在纤维 上的限制是一个多项式 ，具有以下求值：
因此 的次数小于 ，它位于维数至多为 的多项式空间中。旋转因子必须选择为能够张成这个 维多项式空间。这确保了多项式 可以正确地用旋转因子来表示。因此，旋转因子必须构成纤维上 维多项式空间的一组基。当我们详细讨论算法和示例时，这个要求会变得更加清晰。
多项式映射 和旋转因子 在FFT算法的所有层中不必相同。我们现在更详细地描述每个步骤。
步骤1：分解 并计算子多项式的求值
将多项式 分解为次数更低的多项式 ，如下所示：
每个 都是比 次数更低的多项式，具体而言： 。 接下来，使用 在 上的求值来计算每个 在 上的求值。令 表示元素 在多项式映射 下的纤维。由于它有 个元素，我们将其表示为：
使得对于所有 ，都有 将所有 代入 的分解式中得到：
注意，由于对于所有 ，都有 ，因此 在所有方程中都是相同的。这给我们一个包含 个未知数 的 个线性方程组成的系统。求解这个系统使我们能够确定每个 的值。由于系统的大小为常数 ，因此使用例如高斯消元法求解只需常数时间。
求解上述线性方程组归结为对 的旋转因子矩阵求逆，即：
旋转因子在大小为 的纤维上构成 维多项式空间的基这一要求，确保了 旋转因子矩阵是可逆的，因此上述线性方程组有唯一解。
还要注意的是，旋转因子在算法开始前初始化，因此相应的矩阵求逆可以预计算，使其运算复杂度为 而不是 。
通过对每个 重复这个过程，我们获得了所有多项式 在求值域 上的完整求值集合，使我们能够对每个多项式递归地应用FFT。
示例 步骤1：所有计算都在 上进行，即模17运算。首先，使用映射 和旋转因子 分解多项式 ：
给定 在求值域
上的求值 ，我们的目标是计算 和 在较小求值域
上的求值。 对于 ，原像集合是 ，因为 且 。 将集合 中的值代入分解方程，我们得到
求解这个方程组得到：
对所有 重复这个过程，我们得到：
步骤2：递归地对子多项式应用FFT
现在我们已经有了每个 在求值域 上的求值，下一步是计算它们的系数。这使我们回到了与之前相同的问题，但是针对次数更小的多项式，即 ，并且在更小的求值域 上。应用相同的分治策略。
多项式映射 导出一系列逐渐变小的求值域：
其中每个求值域 ，对于 ，且 。假设多项式映射 在所有层中都相同，但一般情况下，每一层可能使用不同的映射。
在更小的求值域上递归地应用FFT，直到达到基本情况：常数多项式，其中求值域上的所有求值都相等。在这种情况下，插值得到一个常数多项式，其唯一的系数就是求值本身。因此，简单地返回这个求值作为系数。
一旦基本情况得到解决，通过递归调用向后工作，在每一层使用分解方程来重构原始 的系数。
示例 步骤2：给定 和 在 上的求值：
递归地应用FFT算法来计算 和 的系数。 在每一层，使用与之前相同的多项式映射 和相同的旋转因子 来分解多项式。例如， 的分解为：
省略递归调用的中间步骤，最终得到 和 的系数如下：
步骤3：组合系数
最后，使用分解方程组合多项式 的系数来计算原始多项式 的系数。
示例 步骤3：给定 和 的系数：
使用分解式重构原始多项式 ：
代入 和 的表达式，得到：
Circle FFT的求值域序列
在Circle FFT中，映射 通过为圆群设置特定的 2 对 1 映射来实例化。这里使用的求值域是孪生陪集：
其中 是大小为 的圆群的子群，且 ，因此陪集 和 是不相交的，且 。本节描述了 上的两个特定的2对1映射，它们是Circle FFT构造的核心：
商映射 ：该映射将 中的每个点映射到商集 的一个元素：
其中 表示反转映射 。商映射 将 中的两个不同的点 和 映射到 中的单个元素。这可以解释为：如果两个点仅在符号上不同，则它们被认为是等价的。这与投影映射 相同，它将点 和 投影到相同的 坐标：
由于 或 将 中的两个点映射到 中的单个元素， 的大小将是 大小的一半。
平方映射 ：该映射在系列第二部分中引入。当应用于大小为 的孪生陪集 时，它产生一个大小为 的更小孪生陪集 。这也是一个 2 对 1 映射，将 的大小减半。通过递归地应用该映射：
生成一系列孪生陪集，直到到达 （大小为 2 的孪生陪集）。该序列中的每个 对应于与子群 相关联的孪生陪集，并具有大小 。
在Circle FFT中，同时使用投影映射 和平方映射 来构造求值域序列。需要注意的一个关键性质是映射 和 是可交换的，意味着：
直观地说，这意味着先投影到 坐标然后平方与先平方然后投影到 坐标是相同的。以下两个动画进一步说明了这一点。
下面的动画显示了先对孪生陪集 应用投影映射 ，然后应用平方映射 以获得商求值域 。
以下动画展示了将平方映射 应用于孪生陪集 ，然后应用投影映射 来获取商求值域 。
通过在每一层应用这些映射，我们获得了 Circle FFT 的一系列求值域，类似于 Cooley－Tukey FFT 中的求值域。关键区别在于映射的选择：在 Cooley－Tukey 中，在每一层应用单个多项式映射 ，而在 Circle FFT 中，在第一层应用 ，然后在后续层应用 。
令 表示孪生陪集 在对合 下的商。映射 是一个二对一映射，定义为：
这是通过倍点映射和等式 计算 坐标得到的：
Circle FFT 的求值域序列如下所示：
我们现在将描述基于这些求值域序列的 Circle FFT 算法。
Circle FFT
令 为梅森素域，其中 ，令 表示其代数闭包。
给定孪生陪集 上的求值，Circle FFT 从空间 中插值出一个二元多项式 。该空间由圆曲线 上的二元多项式组成，总次数为 ：
让我们来详细了解一下 Circle FFT 算法。与 Cooley－Tukey 算法一样，我们也将结合具体示例来演示该算法。
例子：在梅森素数 上的孪生陪集 上进行Circle FFT给定二元多项式 在大小为 的孪生陪集 上的求值 ，目标是计算 的系数。 考虑以下孪生陪集 和 对 的求值 ：
算法
Circle FFT遵循与Cooley－Tukey FFT相同的分治策略。二元多项式首先被分解为次数更低的多项式。然后递归地计算这些较小多项式的系数，最后将它们组合起来计算原始多项式的系数。
关键区别在于多项式的 分解方式。在Cooley－Tukey FFT中，单个映射 在每一层递归地应用。相比之下，Circle FFT使用两个不同的 2 对 1 映射：投影映射 在第一步中应用，平方映射 在所有后续递归步骤中使用。
实际上，Circle FFT就是对应于Cooley－Tukey，只不过最初使用 进行 分解，随后使用 进行递归 分解。我们现在详细介绍每个步骤。
步骤1：分解 并计算子多项式的求值
在第一步中，我们使用投影映射 和旋转因子 在 上 分解二元多项式 ：
给定 在 上的求值，目标是计算 和 在求值域 上的求值。
对于 中任何一对点 及其共轭 ，它们投影到相同的 ，代入分解式得到：
这个方程组在未知数 和 中产生两个方程，可以直接求解。
对 中的所有点对应用此方法，得到 和 在求值域 上的求值。
示例 步骤1：所有计算都在 上进行，即模31运算。首先，使用旋转因子 和映射 分解多项式
给定 在孪生陪集
上的求值 ，我们的目标是计算 和 在较小求值域 上的求值
对于 中在 下具有相同投影的 和 ，将它们代入分解方程得到：
求解这个方程组得到：
对 中的所有对 和 重复这个过程，得到：
步骤2：递归地对子多项式应用FFT
给定 和 在 上的求值，现在计算它们的系数。
这一步对应Cooley－Tukey FFT的递归结构。每个多项式使用平方映射 递归地 分解，过程在逐渐变小的求值域上继续。
首先使用平方映射 和旋转因子 分解 ：
像之前一样，通过求解线性方程组来计算 和 在 上的求值。
这个递归过程继续，直到达到基本情况：多项式在求值域上的所有求值都相同。在该层，系数就是常数多项式的求值。
最后，通过递归调用向后工作，在每一层使用分解方程来重构 的系数。相同的过程适用于计算 的系数。
示例 步骤2 给定 和 在 上的求值：
递归地应用FFT算法来计算 和 的系数。 在每一层，像之前一样使用多项式映射 和旋转因子 来分解多项式。例如， 的分解为：
省略递归调用的中间步骤，最终得到 和 的系数如下：
步骤3：组合系数
最后，使用分解式组合 和 的系数来计算原始二元多项式 的系数：
示例 步骤3 给定 和 的系数：
使用分解式重构原始多项式 ：
代入 和 的表达式，得到：
实现
这是用 SageMath 编写的 Circle FFT 实现。
def cfft(evals, D):
n = len(evals)
assert (n & (n - 1)) == 0
# 第一步：使用映射\pi_x 分解
S = pi_x(D)
eval0 = []
eval1 = []
for e0, e1, P in zip(evals[:n//2], evals[n//2:], D):
eval0.append((e0 + e1) / 2)
eval1.append((e0 - e1) / (2 * get_y(P)))
# 第二步：使用映射\pi 递归应用FFT
coeffs0 = cfft_pi(eval0, S)
coeffs1 = cfft_pi(eval1, S)
# 第三步：重新组合以计算系数
coeffs = to_natural_order(coeffs0 + coeffs1)
return coeffs
def cfft_pi(evals, S):
n = len(evals)
assert (n & (n - 1)) == 0
if n == 1:
return [evals[0]]
S_next = pi(S)
eval0 = []
eval1 = []
for e0, e1, x in zip(evals[:n//2], evals[n//2:], S):
eval0.append((e0 + e1) / 2)
eval1.append((e0 - e1) / (2 * x))
coeffs0 = cfft_pi(eval0, S_next)
coeffs1 = cfft_pi(eval1, S_next)
return coeffs0 + coeffs1
FFT 的基
FFT算法计算相对于某些基多项式的系数。例如，Cooley－Tukey算法计算相对于基多项式 的系数 ，使得
计算系数所依据的基取决于FFT算法每一层所使用的多项式映射 和旋转因子 的选择。
为了看到这一点的实际效果，让我们通过一个简单的例子。考虑在大小为 4 的求值域上的Cooley－Tukey FFT算法，用于计算次数至多为 3 的多项式的系数。首先，分解原始多项式 ：
然后，分解两个子多项式 和 ：
假设 和 是常数多项式。那么
将上述值代入 的分解式中：
因此，上述算法计算相对于以下基的系数： 和 。
因此，根据多项式映射 和旋转因子 的选择，FFT算法输出相对于特定基的系数。
选择1：使用多项式映射 和旋转因子 。这给出相对于单项式基的系数如下：
选择2：使用多项式映射 和旋转因子 。这给出相对于以下基的系数：
类似地，Circle FFT输出相对于某个基 的系数 ，使得：
计算系数所依据的基取决于多项式映射和旋转因子的选择。在孪生陪集 上的Circle FFT的具体例子中，我们看到算法计算了相对于以下基的系数：
使用对 的归纳，可以证明Circle FFT算法输出相对于以下基的系数［定理2，Circle STARKs］：
其中 ，且 是 的二进制表示，即
在论文中，基 的元素定义为：
这里，每个 （对于 ）是大小为 的标准位置陪集的消失多项式，如第二部分所述。 这与我们早期的基定义一致，使用替换：
维数缺口
设由 中的基多项式张成的空间为 。基 共有 个元素，因此空间 的维数为 。然而，圆曲线上的二元多项式空间是 ，如第二部分所讨论的，它的维数为 。
我们可以通过检查基来识别 中缺失的最高总次数元素。基 中的最高总次数元素是：
使用 ，上述项中 的最高次数为：
由于 中 的最高次数是 ，我们可以将空间 表示为：
其中 表示系数在 中、次数至多为 的多项式。类似地，可以将空间 表示为：
因此，空间 不包含单项式 ，而它位于空间 中。因此，
由于 张成的空间与消失多项式 张成的空间相同，其次数为 ，也可以写成：
这个维数缺口的一个后果是，我们无法在圆上插值某些多项式，即那些包含 的多项式。我们将在本系列的下一部分看到如何处理这个问题。
结论
在本文中，我们探讨了Circle FFT 及其与经典 Cooley-Tukey FFT 的结构相似性。我们还讨论了圆曲线上的多项式空间与Circle FFT 基所张成的空间之间的维数缺口。
我们没有讲解逆 FFT，即在给定的一组点处求多项式的值。不过，这种方法在概念上是类似的，所有运算都可以反向进行。这留给读者作为练习。
在下一部分中，我们将讨论如何在 FRI 协议中处理这个维数缺口，并介绍如何把之前文章中的所有想法结合在一起以构建 Circle STARK。