Circle STARKs：第三部分，Circle FFT - ZKSecurity

zksecurity
发布于 5天前
阅读 228

本文深入探讨了Circle FFT（快速傅里叶变换），详细阐述了其与经典Cooley-Tukey FFT的结构相似性，并着重分析了在圆曲线上的多项式空间与Circle FFT基所张成的空间之间的维度差异。Circle FFT通过投影映射和平方映射的组合，实现了在twin-coset上的高效插值，为构建Circle STARKs奠定了基础。

![Circle STARKs](https://img.learnblockchain.cn/2025/08/05/top.png)

## 回顾

在本系列的[第一部分](https://learnblockchain.cn/article/17872/)中，我们探讨了梅森素数上的高效域运算，以及使用它们来实例化 STARK 协议的一个关键挑战，即缺乏平滑的乘法子群。

在[第二部分](https://learnblockchain.cn/article/17856/)中，我们研究了如何使用圆群来解决这个问题。我们介绍了它的陪集结构，即孪生陪集和标准位置陪集，它们可以用于实例化 STARK 协议。我们还讨论了在圆群上定义的多项式的空间，以及在这些陪集上 vanishing polynomial 的构造。

## 介绍

表示一个次数小于 N 的单变量多项式 f(X) 有两种常见的方法：

1. **单项式基**:
f(X)=∑j=0N−1cj⋅bj(X)
其中 cj 是系数，bj(X) 是单项式基多项式，使得：
b(X)=\[1,X,X2,⋯,XN−1\]

2. **拉格朗日基**:
f(X)=∑j=0N−1vj⋅λj(X)
其中 vj=f(ωj) 是 f 在点 ωj 处的求值，λj(X) 是满足以下条件的拉格朗日基多项式：

- λj(ωj)=1
   - 对于所有 i≠j，λj(ωi)=0

拉格朗日基多项式定义为：
λj(X)=∏0≤i<N,i≠jX−ωiωj−ωi

一般来说，FFT 算法执行从一个多项式基到另一个多项式基的转换。 例如，它可以将多项式从单项式基转换为拉格朗日基，反之亦然。 这种基的变化很有用，因为某些操作（例如多项式乘法）在拉格朗日基中变得非常有效。

在 STARK 协议中，计算轨迹通常表示为一组多项式在乘法子群中的点的求值，这意味着可以使用 Cooley-Tukey 样式的 FFT 来计算多项式的系数。

在 Circle STARKs 中，乘法子群被 twin-coset 替换：不是一个群，而是单位圆的陪集的并集。 这些元素遵循“角度加法”或“复数乘法”的群律，并且每个元素对应于圆上的一个点 (x,y)。 在 Circle FFT 中，给定 twin-coset 上的求值，我们插值一个二元多项式。

在本文中，我们将通过与经典 Cooley-Tukey FFT 进行类比，来发展对 Circle FFT 的直观理解。 在整篇文章中，我们使用 FFT 来指代插值，即从拉格朗日基移动到单项式基，而 inverse FFT 指代求值，即从单项式基移动到拉格朗日基。

## Cooley-Tukey FFT

在本节中，我们介绍 Cooley-Tukey FFT 算法的通用版本。 这个通用版本最终将帮助我们理解 Circle FFT 作为通用构造的具体实例。 为了建立直觉，我们将结合一般描述，逐步介绍一个具体的例子。

### 问题陈述

给定大小为 N=kn 的域 Dn 上多项式的求值，我们的目标是计算多项式相对于某些基多项式的系数，使得：
f(X)=∑j=0kn−1cj⋅bj(n)(X)
这里，cj 是我们希望计算的系数，bj(n)(X) 表示基多项式。

例子

**k=2，n=3 的 Cooley-Tukey FFT**

给定一个多项式在大小为 N=23=8 的乘法子群 D3 上的求值 v→，目标是计算一个次数 <N=8 的多项式的系数 (c0,c1,…,c7)。

对于此示例，令 D3 为由 ω=9 生成的 F17∗ 的乘法子群。 那么：
D3={ωi∣i=0,1,…,7}=\[1,9,13,15,16,8,4,2\]

假设多项式在 D3 上的求值为：
v→={f(ωi)∣i=0,1,…,7}=\[11,10,15,1,9,11,15,6\]

### 算法

Cooley-Tukey FFT 算法遵循经典的分而治之策略。 它的步骤如下：

- **步骤 1**：将多项式 f(X) 分解为较低次数的多项式的集合，并在较小的域上找到这些较低次数的多项式的求值。

- **步骤 2**：将 FFT 递归地应用于每个较低次数的多项式，以计算它们的系数。

- **步骤 3**：组合较低次数的多项式的系数，以计算原始多项式 f(X) 的系数。

在 FFT 算法的每个递归层 l，我们使用以下关键组件分解多项式 f(X)：

- **ψ**: 多项式映射 ψ 是一个 k 对 1 的映射，这意味着它将域 Dl 的 k 个元素映射到较小域 Dl−1 中的单个元素。
ψ:Dl→Dl−1
由于 \|Dl\|=kl，这意味着 \|Dl−1\|=kl−1。 在乘法子群上，这种映射的一个常见示例是：
ψ(X)=Xk。

- **t0,t1,⋯,tk−1**: Twiddle 因子 t0,t1,⋯,tk−1 是将元素从域 Dl 映射到域 F 的多项式，即对于 j∈{0,1,⋯,k−1}，tj:Dl→F
对于固定的 z∈Dl−1，在映射 ψ 下的 z 的 [fiber](https://en.wikipedia.org/wiki/Fiber_(mathematics)) 包含 Dl 中映射到 z 的所有元素。 令 Sz 表示元素 z∈Dl−1 在多项式映射 ψ 下的 fiber，即：
Sz=ψ−1(z)={x∈Dl∣ψ(x)=z}={x0,x1,⋯,xk−1}

由于 ψ 是一个 k 对 1 的映射，因此每个 z∈Dl−1 的 fiber 是 Dl 的一个子集，恰好包含 k 个元素。
f(X) 对 fiber Sz 的限制是多项式 f(X)\|Sz，其求值为：
f\|Sz={f(x0),f(x1),⋯,f(xk−1)}
因此，f(X)\|Sz 的次数小于 k，并且它位于维度最多为 k 的多项式空间中。 必须选择 Twiddle 因子来跨越这个 k 维多项式空间。 这确保了多项式 f(X) 可以用 Twiddle 因子正确表达。 随着我们完成算法和示例，此要求将变得更加清晰。

多项式映射 ψ 和 Twiddle 因子 t0,t1,⋯,tk−1 不需要跨 FFT 算法的所有层都相同。 我们现在更详细地描述每个步骤。

#### 步骤 1：分解 f(X) 并计算子多项式的求值

我们将多项式 f(X) 分解为较小次数的多项式 fi(X)，如下所示：
f(X)=t0(X)⋅f0(ψ(X))+t1(X)⋅f1(ψ(X))+⋯+tk−1(X)⋅fk−1(ψ(X))

每个 fi(X) 都是一个次数低于 f(X) 的多项式，具体来说：
deg⁡(fi)≤deg⁡(f)deg⁡(ψ)<knk=kn−1.

接下来，我们使用 f(X) 在 Dn 上的求值来计算每个 fi(X) 在 Dn−1=ψ(Dn) 上的求值。 令 Sz 表示元素 z∈Dn−1 在多项式映射 ψ 下的 fiber。 由于它有 k 个元素，让我们将其表示如下：

Sz={x0,x1,⋯,xk−1}

使得对于所有 xi∈Sz，ψ(xi)=z。 将所有 xi∈Sz 代入 f(X) 的分解式，得到：

f(x0)=t0(x0)⋅f0(z)+t1(x0)⋅f1(z)+⋯+tk−1(x0)⋅fk−1(z)f(x1)=t0(x1)⋅f0(z)+t1(x1)⋅f1(z)+⋯+tk−1(x1)⋅fk−1(z)⋮f(xk−1)=t0(xk−1)⋅f0(z)+t1(xk−1)⋅f1(z)+⋯+tk−1(xk−1)⋅fk−1(z)

请注意，由于对于所有 xi∈Sz，ψ(xi)=z，因此 f0(z),f1(z),…,fk−1(z) 在所有方程中都相同。 这给了我们一个关于 k 个未知数 f0(z),f1(z),…,fk−1(z) 的 k 个线性方程组。 求解该系统使我们能够确定每个 fi(z) 的值。 由于系统的大小是常数 k，因此使用例如高斯消元法求解它需要常数时间。

注意

求解上述线性方程组相当于反转 k×k 的 Twiddle 矩阵，即
\[f0(z)f1(z)⋮fk−1(z)\]=\[t0(x0)t1(x0)⋯tk−1(x0)t0(x1)t1(x1)⋯tk−1(x1)⋮⋮⋱⋮t0(xk−1)t1(xk−1)⋯tk−1(xk−1)\]−1⋅\[f(x0)f(x1)⋮f(xk−1)\]
Twiddle 因子在大小为 k 的 fiber 上形成 k 维多项式空间的基的要求，确保 k×k 的 Twiddle 矩阵是可逆的，因此上述线性方程组具有唯一解。

另请注意，Twiddle 因子在算法开始之前初始化，因此可以预先计算相应的矩阵求逆，这使其成为 k2 而不是 k3 运算。

通过对每个 z∈Dn−1 重复此过程，我们获得了域 Dn−1 上所有多项式 f0,f1,…,fk−1 的完整求值集，从而使我们能够递归地将 FFT 应用于它们中的每一个。

例子

**步骤 1**：所有计算都在 F17 上进行，即模 17。 首先，使用映射 ψ(X)=X2 和 Twiddle 因子 t0(X)=1,t1(X)=X 分解多项式 f(X)：
f(X)=f0(X2)+Xf1(X2)

给定 f(X) 在域
D3=\[1,9,13,15,16,8,4,2\] 上的求值 v→=\[11,10,15,1,9,11,15,6\],
我们的目标是计算 f0 和 f1 在较小域
D2=ψ(D3)=\[1,13,16,4\] 上的求值。

对于 z=1∈D2，原像集为 Sz=\[1,16\], 因为 ψ(1)=1 且 ψ(16)=1。

将 Sz 中的值代入分解方程，我们得到：
f(1)=f0(ψ(1))+f1(ψ(1))⟹11=f0(1)+f1(1)f(16)=f0(ψ(16))+f1(ψ(16))⟹9=f0(1)+16⋅f1(1)

求解此方程组得出：
f0(1)=10,f1(1)=1

对所有 z∈D2 重复此过程，我们得到：
v0→=\[10,2,15,12\],v1→=\[1,16,0,14\]

#### 步骤 2：将 FFT 递归地应用于子多项式

现在我们有了每个 fi 在域 Dn−1 上的求值，下一步是计算它们的系数。 这使我们回到了与之前相同的问题，但是对于次数较小的多项式，即 deg⁡(fi)<kn−1 并且在较小的域 Dn−1 上。 我们应用相同的分而治之策略。

多项式映射 ψ 产生一个逐渐变小的域序列：
Dn→ψDn−1→ψ⋯→ψD0
其中每个域 Dj=ψ(Dj+1)，对于 j=0,1,…,n−1，并且 \|Dj\|=kj。 我们假设多项式映射 ψ 在所有层上都相同，但是通常，每一层可以使用不同的映射。

我们在较小的域上递归地应用 FFT，直到达到基本情况：常数多项式，其中域上的所有求值都相等。 在这种情况下，插值给出一个常数多项式，其唯一系数是求值本身。 因此，我们仅返回此求值作为系数。

一旦解决了基本情况，我们就通过递归调用向后工作，使用每一层的分解方程来重构原始 fi 的系数。

例子

**步骤 2**：给定 f0 和 f1 在 D2=\[1,13,16,4\] 上的求值：
v0→=\[10,2,15,12\],v1→=\[1,16,0,14\]
我们递归地应用 FFT 算法来计算 f0 和 f1 的系数。

在每一层，我们使用相同的多项式映射 ψ(X)=X2 和与之前相同的 Twiddle 因子 t0(X)=1,t1(X)=X 来分解多项式。 例如，f0(X) 的分解是：

f0(X)=f00(X2)+X⋅f01(X2)

省略递归调用的中间步骤，我们最终得到 f0(X) 和 f1(X) 的系数如下：

f0(X)=14+10X+7X2+13X3f1(X)=12+15X+14X2+11X3

#### 步骤 3：合并系数

最后，我们使用分解方程合并多项式 f0,f1,…,fk−1 的系数，以计算原始多项式 f(X) 的系数。
f(X)=t0(X)⋅f0(ψ(X))+t1(X)⋅f1(ψ(X))+⋯+tk−1(X)⋅fk−1(ψ(X))

例子

**步骤 3**：给定 f0(X) 和 f1(X) 的系数：
f0(X)=14+10X+7X2+13X3f1(X)=12+15X+14X2+11X3
我们使用分解重构原始多项式 f(X)：
f(X)=f0(X2)+X⋅f1(X2)

代入 f0 和 f1 的表达式，我们得到：
f(X)=14+10X2+7X4+13X6+X⋅(12+15X2+14X4+11X6)f(X)=14+12X+10X2+15X3+7X4+14X5+13X6+11X7

## Circle FFT 的域序列

在 Circle FFT 中，映射 ψ 由针对圆群设置定制的 2 对 1 映射实例化。 这里使用的域是 twin-coset：
Dn=Q⋅Gn−1∪Q−1⋅Gn−1,
其中 Gn−1 是大小为 2n−1 的圆群的子群，并且 Q≠Q−1，因此陪集 Q⋅Gn−1 和 Q−1⋅Gn−1 是 disjoint 的，并且 \|Dn\|=2n。 本节介绍 Dn 上的两个特定的 2 对 1 映射，它们对于 Circle FFT 构造至关重要：

1. **商映射 ϕJ**: 此映射将 Dn 中的每个点发送到商集 Dn/J 的一个元素：
ϕJ:Dn→Dn/J。

其中 J 表示反演映射 J(P)=−P。 商映射 ϕJ 将来自 Dn 的两个不同的点 P 和 J(P) 映射到 Dn/J 中的单个元素。 这可以解释为，如果两个点仅在符号上不同，则认为它们是等效的。 这与投影映射 πx 相同，该投影映射将点 (x,y) 和 (x,−y) 投影到相同的 x 坐标：
πx((x,y))=x

由于 ϕJ 或 πx 将 Dn 中的两个点映射到 Dn/J 中的单个元素，因此 Dn/J 的大小将是 Dn 大小的一半。

2. **平方映射 π**: 此映射在[第二部分](https://learnblockchain.cn/article/17856/)中介绍。 当应用于大小为 2n 的 twin-coset Dn 时，它会产生一个较小的大小为 2n−1 的 twin-coset Dn−1。 这也是一个 2 对 1 的映射，它将 Dn 的大小减半。 通过递归地应用此映射：
Dj=π(Dj+1)for j=n−1 down to 1,
我们生成一个 twin-coset 序列，直到到达 D1（大小为 2 的 twin-coset）。 此序列中的每个 Dj 对应于与子群 Gj−1 相关联的 twin-coset，并且大小为 \|Dj\|=2j。

在 Circle FFT 中，我们同时使用投影映射 πx 和平方映射 π 来构造域序列。 需要注意的一个关键属性是映射 πx 和 π 可交换，这意味着：
πx∘π(Dn)=π∘πx(Dn)。
直观上，这意味着投影到 x 坐标然后平方与先平方然后投影到 x 坐标相同。 以下两个动画进一步说明了这一点。

以下动画显示了将投影映射 πx 应用于 twin-coset D3，然后应用平方映射 π 来获得商域 S2。

以下动画显示了将平方映射 π 应用于 twin-coset D3，然后应用投影映射 πx 来获得商域 S2。

通过在每一层应用这些映射，我们获得了 Circle FFT 的域序列，类似于 Cooley-Tukey FFT 中的域。 关键区别在于映射的选择：在 Cooley-Tukey 中，我们在每一层应用单个多项式映射 ψ，而在 Circle FFT 中，我们在第一层应用 ψ=πx，然后在后续层中应用 ψ=π。

令 Sj=Dj/J 表示 involution J 下 twin-coset Dj 的商。 映射 π:Sj→Sj−1 是一个 2 对 1 的映射，定义为：
π:x↦2x2−1
这是通过使用加倍映射和等式 y2=1−x2 来计算 x 坐标获得的：
π(x,y)=(x,y)⋅(x,y)=(2x2−1,2xy)

Circle FFT 的域序列显示如下：
Dn→πxSn→πSn−1→π⋯→πS1
我们现在将描述在这些域序列上的 Circle FFT 算法。

## Circle FFT

令 Fp 为梅森素数域，其中 p=231−1，并令 F 表示其代数闭包。

给定 twin-coset Dn 上的求值，Circle FFT 从空间 LN(F) 插值一个二元多项式 f(X,Y)。 此空间由圆曲线 X2+Y2=1 上总次数 ≤N/2 的二元多项式组成：
LN(F)=F\[X,Y\]/(X2+Y2−1)

让我们逐步了解 Circle FFT 算法。 与 Cooley-Tukey 案例一样，我们还将结合算法逐步介绍一个具体的例子。

例子

**在梅森素数 p=25−1=31 上，对 twin-coset D3 进行 Circle FFT**

给定一个大小为 N=23=8 的 twin-coset D3 上二元多项式 f(X,Y) 的求值 v→，目标是计算 f(X,Y) 的系数。

考虑以下 twin-coset D3 和 f(X,Y) 在 D3 上的求值 v→：
D3=\[(7,18),(13,7),(24,13),(18,24),(7,13),(13,24),(24,18),(18,7)\]

v→=\[13,16,9,30,29,27,13,21\]

### 算法

Circle FFT 遵循与 Cooley-Tukey FFT 相同的分而治之策略。 首先将二元多项式分解为较低次数的多项式。 然后，我们递归地计算这些较小多项式的系数，最后将它们组合起来以计算原始多项式的系数。

关键区别在于多项式的拆分方式。 在 Cooley-Tukey FFT 中，单个映射 ψ 在每一层递归地应用。 相比之下，Circle FFT 使用两个不同的 2 对 1 映射：投影映射 πx 在第一步中应用，而平方映射 π 用于所有后续递归步骤中。

实际上，Circle FFT 镜像了 Cooley-Tukey，但是最初使用 ψ=πx 进行拆分，然后使用 ψ=π 进行递归拆分。 现在，我们详细介绍每个步骤。

#### 步骤 1：分解 f(X,Y) 并计算子多项式的求值

第一步，我们使用投影映射 πx 和 Twiddle 因子 t0(X,Y)=1, t1(X,Y)=Y 在 Dn 上拆分二元多项式 f(X,Y)：
f(X,Y)=t0(X,Y)⋅f0(πx(X,Y))+t1(X,Y)⋅f1(πx(X,Y))=f0(X)+Y⋅f1(X)

给定 f(X,Y) 在 Dn 上的求值，我们的目标是计算 f0(X) 和 f1(X) 在域 Sn=πx(Dn) 上的求值。

对于投射到同一 x∈Sn 的 Dn 中的任何一对点 P=(x,y) 及其共轭 J(P)=(x,−y)，代入分解式得出：
f(P)=f0(x)+y⋅f1(x),f(J(P))=f0(x)−y⋅f1(x)
此系统产生了关于未知数 f0(x) 和 f1(x) 的两个方程，可以直接求解。

将此应用于 Dn 中的所有点对，即可获得 f0(X) 和 f1(X) 在域 Sn 上的求值。

例子

**步骤 1**：所有计算都在 F31 上进行，即模 31。 首先，使用 Twiddle 因子 t0(X,Y)=1, t1(X,Y)=Y 和映射 ψ(X,Y)=πx(X,Y)=X 分解多项式 f(X,Y)：

f(X,Y)=t0(X,Y)⋅f0(ψ(X,Y))+t1(X,Y)⋅f1(ψ(X,Y))=f0(X)+Y⋅f1(X)

给定 f(X,Y) 在 twin-coset
D3=\[(7,18),(13,7),(24,13),(18,24),(7,13),(13,24),(24,18),(18,7)\]
上的求值 v→=\[13,16,9,30,29,27,13,21\]
，我们的目标是计算 f0 和 f1 在较小域 S3=πx(D3)=\[7,13,24,18\] 上的求值。
对于 D3 中在 πx 下具有相同投影 P=(7,18) 和 J(P)=(7,13)，将它们代入分解方程得出：
f(7,18)=f0(7)+18⋅f1(7)⟹13=f0(7)+18⋅f1(7)f(7,13)=f0(7)+13⋅f1(7)⟹29=f0(7)+13⋅f1(7)

求解此方程组得出：
f0(7)=21,f1(7)=3

对 D3 中的所有点对 P 和 J(P) 重复此过程，我们得到：
v0→=\[21,6,11,10\],v1→=\[3,28,7,6\]

#### 步骤 2：将 FFT 递归地应用于子多项式

给定 f0(X) 和 f1(X) 在 Sn 上的求值，我们现在计算它们的系数。

此步骤镜像了 Cooley-Tukey FFT 的递归结构。 使用平方映射 π(X)=2X2−1 递归地拆分每个多项式，并且该过程在连续较小的域上继续进行。

我们首先使用平方映射 π 和 Twiddle 因子 t00(X)=1, t01(X)=X 分解 f0(X)：
f0(X)=t00(X)⋅f00(π(X))+t01(X)⋅f01(π(X))=f00(π(X))+X⋅f01(π(X))

与以前一样，我们通过求解线性方程组来计算 f00(X) 和 f01(X) 在 Sn−1=π(Sn) 上的求值。

此递归过程一直持续到我们达到基本情况：多项式在域上的所有求值都相同。 在该级别，系数仅是常数多项式的求值。

最后，我们通过使用每一层的分解方程向后处理递归调用来重构 f0(X) 的系数。 相同的过程适用于计算 f1(X) 的系数。

例子

**步骤 2**：给定 f0 和 f1 在 S3=\[7,13,24,18\] 上的求值：
v0→=\[21,6,11,10\],v1→=\[3,28,7,6\]
我们递归地应用 FFT 算法来计算 f0 和 f1 的系数。

在每一层，我们使用多项式映射 π(X) 和 Twiddle 因子 t0(X)=1,t1(X)=X 来分解多项式，与之前一样。 例如，f0(X) 的分解是：

f0(X)=f00(π(X))+X⋅f01(π(X))

省略递归调用的中间步骤，我们最终得到 f0(X) 和 f1(X) 的系数如下：
f0(X)=12+26⋅X+π(X)+28⋅X⋅π(X)f1(X)=11+26⋅X+14⋅π(X)+20⋅X⋅π(X)

#### 步骤 3：合并系数

最后，我们使用分解式合并 f0(X) 和 f1(X) 的系数，以计算原始二元多项式 f(X,Y) 的系数：
f(X,Y)=f0(X)+Y⋅f1(X)

例子

**步骤 3**：给定 f0(X) 和 f1(X) 的系数：
f0(X)=12+26⋅X+π(X)+28⋅X⋅π(X)f1(X)=11+26⋅X+14⋅π(X)+20⋅X⋅π(X)
我们使用分解重构原始多项式 f(X,Y)：
f(X,Y)=f0(X)+Y⋅f1(X)

代入 f0 和 f1 的表达式，我们得到：
f(X)=12+26⋅X+π(X)+28⋅X⋅π(X)+Y⋅(11+26⋅X+14⋅π(X)+20⋅X⋅π(X))

f(X)=12+26⋅X+π(X)+28⋅X⋅π(X)+11⋅Y+26⋅X⋅Y+14⋅Y⋅π(X)+20⋅X⋅Y⋅π(X)

### 实现

这是用 SageMath 编写的 Circle FFT 实现。

```sage
def cfft(evals, D):
    n = len(evals)
    assert (n & (n - 1)) == 0

# Step 1: Split using map \pi_x
    # 步骤 1：使用映射 \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)))

# Step 2: Recursively apply FFT using map \pi
    # 步骤 2：使用映射 \pi 递归地应用 FFT
    coeffs0 = cfft_pi(eval0, S)
    coeffs1 = cfft_pi(eval1, S)

# Step 3: Recombine to compute coefficients
    # 步骤 3：重新组合以计算系数
    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 算法计算相对于基多项式 bj(n)(X) 的系数 cj，使得

f(X)=∑j=0kn−1cj⋅bj(n)(X)

计算系数所依据的基取决于在 FFT 算法的每一层使用的多项式映射 ψ 和 Twiddle 因子 t0,t1,⋯tk−1 的选择。

为了实际了解这一点，让我们逐步介绍一个简单的示例。 考虑大小为 4 的域上的 Cooley-Tukey FFT 算法，以计算最多 3 次多项式的系数。 首先，我们分解原始多项式 f(X)：
f(X)=t0(X)⋅f0(ψ(X))+t1(X)⋅f1(ψ(X))

然后，我们分解两个子多项式 f0(X) 和 f1(X)：
f0(X)=t0(X)⋅f00(ψ(X))+t1(X)⋅f01(ψ(X))

f1(X)=t0(X)⋅f10(ψ(X))+t1(X)⋅f11(ψ(X))

假设 f00(X)、f01(X)、f10(X) 和 f11(X) 是常数多项式。 那么

f0(X)=a⋅t0(X)+b⋅t1(X)

f1(X)=c⋅t0(X)+d⋅t1(X)

将上述值代入 f(X) 的分解式：

f(X)=t0(X)⋅(a⋅t0(ψ(X))+b⋅t1(ψ(X)))+t1(X)⋅(c⋅t0(ψ(X))+d⋅t1(ψ(X)))

因此，上述算法计算相对于以下基的系数：t0(X)⋅t0(ψ(X))、t0(X)⋅t1(ψ(X))、t1(X)⋅t0(ψ(X)) 和 t1(X)⋅t1(ψ(X))。

因此，根据多项式映射 ψ 和 Twiddle 因子 t0,t1 的选择，FFT 算法输出相对于特定基的系数。

- **选择 1**：我们使用多项式映射 ψ(X)=X2 和 Twiddle 因子 t0(X)=1,t1(X)=X。 这使我们获得了相对于单项式基的系数，如下所示：
b(X)={1,X,X2,X3}

- **选择 2**：我们使用多项式映射 ψ(X)=X2 和 Twiddle 因子 t0(X)=X,t1(X)=X+1。 这使我们获得了相对于以下基的系数：
b(X)={X⋅X2,X2⋅(X+1),X⋅(X2+1),(X2+1)⋅(X+1)}

类似地，circle FFT 输出相对于某些基 bj(n)(X,Y) 的系数 cj，使得：
f(X,Y)=∑j=02n−1cj⋅bj(n)(X,Y)

计算系数所依据的基取决于多项式映射和 Twiddle 因子的选择。 在 twin-coset D3 上的 circle FFT 的具体示例中，我们看到该算法计算了相对于以下基的系数：
bj(3)(X,Y)=\[1,X,π(X),X⋅π(X),Y,Y⋅X,Y⋅π(X),Y⋅X⋅π(X)\]

使用归纳法对 n 进行归纳，我们可以证明 Circle FFT 算法输出的系数与以下基相关 \[[定理 2, Circle STARKs](https://eprint.iacr.org/2024/278.pdf)]：

bj(n)(X,Y):=Yj0⋅Xj1⋅π(X)j2⋅π2(X)j3⋯πn−2(X)jn−1

其中 0≤j≤2n−1 且 (j0,…,jn−1)∈{0,1}n 是 j 的二进制表示，即 j=j0+j1⋅2+⋯+jn−1⋅2n−1。

注意

在论文中，基 b(n)(X,Y) 的元素定义为：

bjn(X,Y):=Yj0⋅v1(X)j1⋯vn−1(X)jn−1

这里，每个 vk(X) (对于 1≤k≤n−1) 是大小为 2k 的标准位置陪集的消失多项式，如 [第二部分](https://learnblockchain.cn/article/17856/) 中所述。

这与我们之前对基的定义一致，使用以下替换：
vk(X)=πk−1(X),1≤k≤n−1。

## 维度差距

令 b(n)(X,Y) 中基多项式所张成的空间为 LN′(F)。基 b(n)(X,Y) 共有 N=2n 个元素，因此空间 LN′(F) 的维度为 N。然而，圆曲线上的二元多项式空间为 LN(F)，其维度为 N+1，如 [第二部分](https://learnblockchain.cn/article/17856/) 中所述。

我们可以通过检查基来识别 LN′(F) 中缺失的最高总阶元素。基 b(n)(X,Y) 中最高总阶元素为：
Y⋅X⋅π(X)⋅π2(X)⋅π3(X)⋯πn−2(X)

使用 deg(πj(X)=2j)，上述项中 X 的最高阶为：
1+2+22+23+⋯+2n−2=2n−1−1=N/2−1

由于 LN′(F) 中 X 的最高阶为 N/2−1，我们可以将空间 LN′(F) 表示为：
LN′(F)=F\[X]≤N/2−1+Y⋅F\[X]≤N/2−1
其中 F\[X]≤N/2−1 表示在 F 中具有系数的阶最多为 N/2−1 的多项式。类似地，我们可以将空间 LN(F) 表示为：
LN(F)=F\[X]≤N/2+Y⋅F\[X]≤N/2−1

因此，空间 LN′(F) 不包括单项式 XN/2，它位于空间 LN(F) 中。因此，
LN(F)=LN′(F)+⟨XN/2⟩

由于 XN/2 张成的空间与消失多项式 vn(X) 张成的空间相同，后者具有阶 deg(vn)=2n−1=N/2，我们也可以写成：
LN(F)=LN′(F)+⟨vn⟩

这种维度差距的一个结果是，我们无法在圆上插值一些多项式，即那些具有 XN/2 的多项式。我们将在本系列的下一部分中看到如何处理这个问题。

## 结论

在这篇博客文章中，我们探讨了 Circle FFT 及其与经典 Cooley-Tukey FFT 的结构相似性。我们还讨论了圆曲线上的多项式空间与 Circle FFT 基张成的空间之间的维度差距。

我们没有介绍逆 FFT，即在给定点集处评估多项式。然而，该方法在概念上是相似的，并且所有操作都可以反向运行。这留给读者作为练习。

在下一部分中，我们将讨论如何在 FRI 协议中处理这种维度差距，并了解之前帖子中的所有想法如何结合在一起来构建 Circle STARK。

>- 原文链接： [blog.zksecurity.xyz/post...](https://blog.zksecurity.xyz/posts/circle-starks-3)
>- 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～

回顾

在本系列的第一部分中，我们探讨了梅森素数上的高效域运算，以及使用它们来实例化 STARK 协议的一个关键挑战，即缺乏平滑的乘法子群。

在第二部分中，我们研究了如何使用圆群来解决这个问题。我们介绍了它的陪集结构，即孪生陪集和标准位置陪集，它们可以用于实例化 STARK 协议。我们还讨论了在圆群上定义的多项式的空间，以及在这些陪集上 vanishing polynomial 的构造。

介绍

表示一个次数小于 N 的单变量多项式 f(X) 有两种常见的方法：

单项式基: f(X)=∑j=0N−1cj⋅bj(X) 其中 cj 是系数，bj(X) 是单项式基多项式，使得： b(X)=[1,X,X2,⋯,XN−1]
拉格朗日基: f(X)=∑j=0N−1vj⋅λj(X) 其中 vj=f(ωj) 是 f 在点 ωj 处的求值，λj(X) 是满足以下条件的拉格朗日基多项式：
- λj(ωj)=1
- 对于所有 i≠j，λj(ωi)=0

拉格朗日基多项式定义为： λj(X)=∏0≤i<N,i≠jX−ωiωj−ωi

一般来说，FFT 算法执行从一个多项式基到另一个多项式基的转换。例如，它可以将多项式从单项式基转换为拉格朗日基，反之亦然。这种基的变化很有用，因为某些操作（例如多项式乘法）在拉格朗日基中变得非常有效。

在 STARK 协议中，计算轨迹通常表示为一组多项式在乘法子群中的点的求值，这意味着可以使用 Cooley-Tukey 样式的 FFT 来计算多项式的系数。

在 Circle STARKs 中，乘法子群被 twin-coset 替换：不是一个群，而是单位圆的陪集的并集。这些元素遵循“角度加法”或“复数乘法”的群律，并且每个元素对应于圆上的一个点 (x,y)。在 Circle FFT 中，给定 twin-coset 上的求值，我们插值一个二元多项式。

在本文中，我们将通过与经典 Cooley-Tukey FFT 进行类比，来发展对 Circle FFT 的直观理解。在整篇文章中，我们使用 FFT 来指代插值，即从拉格朗日基移动到单项式基，而 inverse FFT 指代求值，即从单项式基移动到拉格朗日基。

Cooley-Tukey FFT

在本节中，我们介绍 Cooley-Tukey FFT 算法的通用版本。这个通用版本最终将帮助我们理解 Circle FFT 作为通用构造的具体实例。为了建立直觉，我们将结合一般描述，逐步介绍一个具体的例子。

问题陈述

给定大小为 N=kn 的域 Dn 上多项式的求值，我们的目标是计算多项式相对于某些基多项式的系数，使得： f(X)=∑j=0kn−1cj⋅bj(n)(X) 这里，cj 是我们希望计算的系数，bj(n)(X) 表示基多项式。

例子

k=2，n=3 的 Cooley-Tukey FFT

给定一个多项式在大小为 N=23=8 的乘法子群 D3 上的求值 v→，目标是计算一个次数 <N=8 的多项式的系数 (c0,c1,…,c7)。

对于此示例，令 D3 为由 ω=9 生成的 F17∗ 的乘法子群。那么： D3={ωi∣i=0,1,…,7}=[1,9,13,15,16,8,4,2]

假设多项式在 D3 上的求值为： v→={f(ωi)∣i=0,1,…,7}=[11,10,15,1,9,11,15,6]

算法

Cooley-Tukey FFT 算法遵循经典的分而治之策略。它的步骤如下：

步骤 1：将多项式 f(X) 分解为较低次数的多项式的集合，并在较小的域上找到这些较低次数的多项式的求值。
步骤 2：将 FFT 递归地应用于每个较低次数的多项式，以计算它们的系数。
步骤 3：组合较低次数的多项式的系数，以计算原始多项式 f(X) 的系数。

在 FFT 算法的每个递归层 l，我们使用以下关键组件分解多项式 f(X)：

ψ: 多项式映射 ψ 是一个 k 对 1 的映射，这意味着它将域 Dl 的 k 个元素映射到较小域 Dl−1 中的单个元素。 ψ:Dl→Dl−1 由于 |Dl|=kl，这意味着 |Dl−1|=kl−1。在乘法子群上，这种映射的一个常见示例是： ψ(X)=Xk。
t0,t1,⋯,tk−1: Twiddle 因子 t0,t1,⋯,tk−1 是将元素从域 Dl 映射到域 F 的多项式，即对于 j∈{0,1,⋯,k−1}，tj:Dl→F 对于固定的 z∈Dl−1，在映射 ψ 下的 z 的 fiber 包含 Dl 中映射到 z 的所有元素。令 Sz 表示元素 z∈Dl−1 在多项式映射 ψ 下的 fiber，即： Sz=ψ−1(z)={x∈Dl∣ψ(x)=z}={x0,x1,⋯,xk−1}

由于 ψ 是一个 k 对 1 的映射，因此每个 z∈Dl−1 的 fiber 是 Dl 的一个子集，恰好包含 k 个元素。 f(X) 对 fiber Sz 的限制是多项式 f(X)|Sz，其求值为： f|Sz={f(x0),f(x1),⋯,f(xk−1)} 因此，f(X)|Sz 的次数小于 k，并且它位于维度最多为 k 的多项式空间中。必须选择 Twiddle 因子来跨越这个 k 维多项式空间。这确保了多项式 f(X) 可以用 Twiddle 因子正确表达。随着我们完成算法和示例，此要求将变得更加清晰。

多项式映射 ψ 和 Twiddle 因子 t0,t1,⋯,tk−1 不需要跨 FFT 算法的所有层都相同。我们现在更详细地描述每个步骤。

步骤 1：分解 f(X) 并计算子多项式的求值

我们将多项式 f(X) 分解为较小次数的多项式 fi(X)，如下所示： f(X)=t0(X)⋅f0(ψ(X))+t1(X)⋅f1(ψ(X))+⋯+tk−1(X)⋅fk−1(ψ(X))

每个 fi(X) 都是一个次数低于 f(X) 的多项式，具体来说： deg⁡(fi)≤deg⁡(f)deg⁡(ψ)<knk=kn−1.

接下来，我们使用 f(X) 在 Dn 上的求值来计算每个 fi(X) 在 Dn−1=ψ(Dn) 上的求值。令 Sz 表示元素 z∈Dn−1 在多项式映射 ψ 下的 fiber。由于它有 k 个元素，让我们将其表示如下：

Sz={x0,x1,⋯,xk−1}

使得对于所有 xi∈Sz，ψ(xi)=z。将所有 xi∈Sz 代入 f(X) 的分解式，得到：

请注意，由于对于所有 xi∈Sz，ψ(xi)=z，因此 f0(z),f1(z),…,fk−1(z) 在所有方程中都相同。这给了我们一个关于 k 个未知数 f0(z),f1(z),…,fk−1(z) 的 k 个线性方程组。求解该系统使我们能够确定每个 fi(z) 的值。由于系统的大小是常数 k，因此使用例如高斯消元法求解它需要常数时间。

注意

求解上述线性方程组相当于反转 k×k 的 Twiddle 矩阵，即 [f0(z)f1(z)⋮fk−1(z)]=[t0(x0)t1(x0)⋯tk−1(x0)t0(x1)t1(x1)⋯tk−1(x1)⋮⋮⋱⋮t0(xk−1)t1(xk−1)⋯tk−1(xk−1)]−1⋅[f(x0)f(x1)⋮f(xk−1)] Twiddle 因子在大小为 k 的 fiber 上形成 k 维多项式空间的基的要求，确保 k×k 的 Twiddle 矩阵是可逆的，因此上述线性方程组具有唯一解。

另请注意，Twiddle 因子在算法开始之前初始化，因此可以预先计算相应的矩阵求逆，这使其成为 k2 而不是 k3 运算。

通过对每个 z∈Dn−1 重复此过程，我们获得了域 Dn−1 上所有多项式 f0,f1,…,fk−1 的完整求值集，从而使我们能够递归地将 FFT 应用于它们中的每一个。

例子

步骤 1：所有计算都在 F17 上进行，即模 17。首先，使用映射 ψ(X)=X2 和 Twiddle 因子 t0(X)=1,t1(X)=X 分解多项式 f(X)： f(X)=f0(X2)+Xf1(X2)

给定 f(X) 在域 D3=[1,9,13,15,16,8,4,2] 上的求值 v→=[11,10,15,1,9,11,15,6], 我们的目标是计算 f0 和 f1 在较小域 D2=ψ(D3)=[1,13,16,4] 上的求值。

对于 z=1∈D2，原像集为 Sz=[1,16], 因为 ψ(1)=1 且 ψ(16)=1。

将 Sz 中的值代入分解方程，我们得到： f(1)=f0(ψ(1))+f1(ψ(1))⟹11=f0(1)+f1(1)f(16)=f0(ψ(16))+f1(ψ(16))⟹9=f0(1)+16⋅f1(1)

求解此方程组得出： f0(1)=10,f1(1)=1

对所有 z∈D2 重复此过程，我们得到： v0→=[10,2,15,12],v1→=[1,16,0,14]

步骤 2：将 FFT 递归地应用于子多项式

现在我们有了每个 fi 在域 Dn−1 上的求值，下一步是计算它们的系数。这使我们回到了与之前相同的问题，但是对于次数较小的多项式，即 deg⁡(fi)<kn−1 并且在较小的域 Dn−1 上。我们应用相同的分而治之策略。

多项式映射 ψ 产生一个逐渐变小的域序列： Dn→ψDn−1→ψ⋯→ψD0 其中每个域 Dj=ψ(Dj+1)，对于 j=0,1,…,n−1，并且 |Dj|=kj。我们假设多项式映射 ψ 在所有层上都相同，但是通常，每一层可以使用不同的映射。

我们在较小的域上递归地应用 FFT，直到达到基本情况：常数多项式，其中域上的所有求值都相等。在这种情况下，插值给出一个常数多项式，其唯一系数是求值本身。因此，我们仅返回此求值作为系数。

一旦解决了基本情况，我们就通过递归调用向后工作，使用每一层的分解方程来重构原始 fi 的系数。

例子

步骤 2：给定 f0 和 f1 在 D2=[1,13,16,4] 上的求值： v0→=[10,2,15,12],v1→=[1,16,0,14] 我们递归地应用 FFT 算法来计算 f0 和 f1 的系数。

在每一层，我们使用相同的多项式映射 ψ(X)=X2 和与之前相同的 Twiddle 因子 t0(X)=1,t1(X)=X 来分解多项式。例如，f0(X) 的分解是：

f0(X)=f00(X2)+X⋅f01(X2)

省略递归调用的中间步骤，我们最终得到 f0(X) 和 f1(X) 的系数如下：

f0(X)=14+10X+7X2+13X3f1(X)=12+15X+14X2+11X3

步骤 3：合并系数

最后，我们使用分解方程合并多项式 f0,f1,…,fk−1 的系数，以计算原始多项式 f(X) 的系数。 f(X)=t0(X)⋅f0(ψ(X))+t1(X)⋅f1(ψ(X))+⋯+tk−1(X)⋅fk−1(ψ(X))

例子

步骤 3：给定 f0(X) 和 f1(X) 的系数： f0(X)=14+10X+7X2+13X3f1(X)=12+15X+14X2+11X3 我们使用分解重构原始多项式 f(X)： f(X)=f0(X2)+X⋅f1(X2)

代入 f0 和 f1 的表达式，我们得到： f(X)=14+10X2+7X4+13X6+X⋅(12+15X2+14X4+11X6)f(X)=14+12X+10X2+15X3+7X4+14X5+13X6+11X7

Circle FFT 的域序列

在 Circle FFT 中，映射 ψ 由针对圆群设置定制的 2 对 1 映射实例化。这里使用的域是 twin-coset： Dn=Q⋅Gn−1∪Q−1⋅Gn−1, 其中 Gn−1 是大小为 2n−1 的圆群的子群，并且 Q≠Q−1，因此陪集 Q⋅Gn−1 和 Q−1⋅Gn−1 是 disjoint 的，并且 |Dn|=2n。本节介绍 Dn 上的两个特定的 2 对 1 映射，它们对于 Circle FFT 构造至关重要：

商映射 ϕJ: 此映射将 Dn 中的每个点发送到商集 Dn/J 的一个元素： ϕJ:Dn→Dn/J。

其中 J 表示反演映射 J(P)=−P。商映射 ϕJ 将来自 Dn 的两个不同的点 P 和 J(P) 映射到 Dn/J 中的单个元素。这可以解释为，如果两个点仅在符号上不同，则认为它们是等效的。这与投影映射 πx 相同，该投影映射将点 (x,y) 和 (x,−y) 投影到相同的 x 坐标： πx((x,y))=x

由于 ϕJ 或 πx 将 Dn 中的两个点映射到 Dn/J 中的单个元素，因此 Dn/J 的大小将是 Dn 大小的一半。

平方映射 π: 此映射在第二部分中介绍。当应用于大小为 2n 的 twin-coset Dn 时，它会产生一个较小的大小为 2n−1 的 twin-coset Dn−1。这也是一个 2 对 1 的映射，它将 Dn 的大小减半。通过递归地应用此映射： Dj=π(Dj+1)for j=n−1 down to 1, 我们生成一个 twin-coset 序列，直到到达 D1（大小为 2 的 twin-coset）。此序列中的每个 Dj 对应于与子群 Gj−1 相关联的 twin-coset，并且大小为 |Dj|=2j。

在 Circle FFT 中，我们同时使用投影映射 πx 和平方映射 π 来构造域序列。需要注意的一个关键属性是映射 πx 和 π 可交换，这意味着： πx∘π(Dn)=π∘πx(Dn)。直观上，这意味着投影到 x 坐标然后平方与先平方然后投影到 x 坐标相同。以下两个动画进一步说明了这一点。

以下动画显示了将投影映射 πx 应用于 twin-coset D3，然后应用平方映射 π 来获得商域 S2。

以下动画显示了将平方映射 π 应用于 twin-coset D3，然后应用投影映射 πx 来获得商域 S2。

通过在每一层应用这些映射，我们获得了 Circle FFT 的域序列，类似于 Cooley-Tukey FFT 中的域。关键区别在于映射的选择：在 Cooley-Tukey 中，我们在每一层应用单个多项式映射 ψ，而在 Circle FFT 中，我们在第一层应用 ψ=πx，然后在后续层中应用 ψ=π。

令 Sj=Dj/J 表示 involution J 下 twin-coset Dj 的商。映射 π:Sj→Sj−1 是一个 2 对 1 的映射，定义为： π:x↦2x2−1 这是通过使用加倍映射和等式 y2=1−x2 来计算 x 坐标获得的： π(x,y)=(x,y)⋅(x,y)=(2x2−1,2xy)

Circle FFT 的域序列显示如下： Dn→πxSn→πSn−1→π⋯→πS1 我们现在将描述在这些域序列上的 Circle FFT 算法。

Circle FFT

令 Fp 为梅森素数域，其中 p=231−1，并令 F 表示其代数闭包。

给定 twin-coset Dn 上的求值，Circle FFT 从空间 LN(F) 插值一个二元多项式 f(X,Y)。此空间由圆曲线 X2+Y2=1 上总次数 ≤N/2 的二元多项式组成： LN(F)=F[X,Y]/(X2+Y2−1)

让我们逐步了解 Circle FFT 算法。与 Cooley-Tukey 案例一样，我们还将结合算法逐步介绍一个具体的例子。

例子

在梅森素数 p=25−1=31 上，对 twin-coset D3 进行 Circle FFT

给定一个大小为 N=23=8 的 twin-coset D3 上二元多项式 f(X,Y) 的求值 v→，目标是计算 f(X,Y) 的系数。

考虑以下 twin-coset D3 和 f(X,Y) 在 D3 上的求值 v→： D3=[(7,18),(13,7),(24,13),(18,24),(7,13),(13,24),(24,18),(18,7)]

v→=[13,16,9,30,29,27,13,21]

算法

Circle FFT 遵循与 Cooley-Tukey FFT 相同的分而治之策略。首先将二元多项式分解为较低次数的多项式。然后，我们递归地计算这些较小多项式的系数，最后将它们组合起来以计算原始多项式的系数。

关键区别在于多项式的拆分方式。在 Cooley-Tukey FFT 中，单个映射 ψ 在每一层递归地应用。相比之下，Circle FFT 使用两个不同的 2 对 1 映射：投影映射 πx 在第一步中应用，而平方映射 π 用于所有后续递归步骤中。

实际上，Circle FFT 镜像了 Cooley-Tukey，但是最初使用 ψ=πx 进行拆分，然后使用 ψ=π 进行递归拆分。现在，我们详细介绍每个步骤。

步骤 1：分解 f(X,Y) 并计算子多项式的求值

第一步，我们使用投影映射 πx 和 Twiddle 因子 t0(X,Y)=1, t1(X,Y)=Y 在 Dn 上拆分二元多项式 f(X,Y)： f(X,Y)=t0(X,Y)⋅f0(πx(X,Y))+t1(X,Y)⋅f1(πx(X,Y))=f0(X)+Y⋅f1(X)

给定 f(X,Y) 在 Dn 上的求值，我们的目标是计算 f0(X) 和 f1(X) 在域 Sn=πx(Dn) 上的求值。

对于投射到同一 x∈Sn 的 Dn 中的任何一对点 P=(x,y) 及其共轭 J(P)=(x,−y)，代入分解式得出： f(P)=f0(x)+y⋅f1(x),f(J(P))=f0(x)−y⋅f1(x) 此系统产生了关于未知数 f0(x) 和 f1(x) 的两个方程，可以直接求解。

将此应用于 Dn 中的所有点对，即可获得 f0(X) 和 f1(X) 在域 Sn 上的求值。

例子

步骤 1：所有计算都在 F31 上进行，即模 31。首先，使用 Twiddle 因子 t0(X,Y)=1, t1(X,Y)=Y 和映射 ψ(X,Y)=πx(X,Y)=X 分解多项式 f(X,Y)：

f(X,Y)=t0(X,Y)⋅f0(ψ(X,Y))+t1(X,Y)⋅f1(ψ(X,Y))=f0(X)+Y⋅f1(X)

给定 f(X,Y) 在 twin-coset D3=[(7,18),(13,7),(24,13),(18,24),(7,13),(13,24),(24,18),(18,7)] 上的求值 v→=[13,16,9,30,29,27,13,21] ，我们的目标是计算 f0 和 f1 在较小域 S3=πx(D3)=[7,13,24,18] 上的求值。对于 D3 中在 πx 下具有相同投影 P=(7,18) 和 J(P)=(7,13)，将它们代入分解方程得出： f(7,18)=f0(7)+18⋅f1(7)⟹13=f0(7)+18⋅f1(7)f(7,13)=f0(7)+13⋅f1(7)⟹29=f0(7)+13⋅f1(7)

求解此方程组得出： f0(7)=21,f1(7)=3

对 D3 中的所有点对 P 和 J(P) 重复此过程，我们得到： v0→=[21,6,11,10],v1→=[3,28,7,6]

步骤 2：将 FFT 递归地应用于子多项式

给定 f0(X) 和 f1(X) 在 Sn 上的求值，我们现在计算它们的系数。

此步骤镜像了 Cooley-Tukey FFT 的递归结构。使用平方映射 π(X)=2X2−1 递归地拆分每个多项式，并且该过程在连续较小的域上继续进行。

我们首先使用平方映射 π 和 Twiddle 因子 t00(X)=1, t01(X)=X 分解 f0(X)： f0(X)=t00(X)⋅f00(π(X))+t01(X)⋅f01(π(X))=f00(π(X))+X⋅f01(π(X))

与以前一样，我们通过求解线性方程组来计算 f00(X) 和 f01(X) 在 Sn−1=π(Sn) 上的求值。

此递归过程一直持续到我们达到基本情况：多项式在域上的所有求值都相同。在该级别，系数仅是常数多项式的求值。

最后，我们通过使用每一层的分解方程向后处理递归调用来重构 f0(X) 的系数。相同的过程适用于计算 f1(X) 的系数。

例子

步骤 2：给定 f0 和 f1 在 S3=[7,13,24,18] 上的求值： v0→=[21,6,11,10],v1→=[3,28,7,6] 我们递归地应用 FFT 算法来计算 f0 和 f1 的系数。

在每一层，我们使用多项式映射 π(X) 和 Twiddle 因子 t0(X)=1,t1(X)=X 来分解多项式，与之前一样。例如，f0(X) 的分解是：

f0(X)=f00(π(X))+X⋅f01(π(X))

省略递归调用的中间步骤，我们最终得到 f0(X) 和 f1(X) 的系数如下： f0(X)=12+26⋅X+π(X)+28⋅X⋅π(X)f1(X)=11+26⋅X+14⋅π(X)+20⋅X⋅π(X)

步骤 3：合并系数

最后，我们使用分解式合并 f0(X) 和 f1(X) 的系数，以计算原始二元多项式 f(X,Y) 的系数： f(X,Y)=f0(X)+Y⋅f1(X)

例子

步骤 3：给定 f0(X) 和 f1(X) 的系数： f0(X)=12+26⋅X+π(X)+28⋅X⋅π(X)f1(X)=11+26⋅X+14⋅π(X)+20⋅X⋅π(X) 我们使用分解重构原始多项式 f(X,Y)： f(X,Y)=f0(X)+Y⋅f1(X)

代入 f0 和 f1 的表达式，我们得到： f(X)=12+26⋅X+π(X)+28⋅X⋅π(X)+Y⋅(11+26⋅X+14⋅π(X)+20⋅X⋅π(X))

f(X)=12+26⋅X+π(X)+28⋅X⋅π(X)+11⋅Y+26⋅X⋅Y+14⋅Y⋅π(X)+20⋅X⋅Y⋅π(X)

实现

这是用 SageMath 编写的 Circle FFT 实现。

def cfft(evals, D):
    n = len(evals)
    assert (n & (n - 1)) == 0

    # Step 1: Split using map \pi_x
    # 步骤 1：使用映射 \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)))

    # Step 2: Recursively apply FFT using map \pi
    # 步骤 2：使用映射 \pi 递归地应用 FFT
    coeffs0 = cfft_pi(eval0, S)
    coeffs1 = cfft_pi(eval1, S)

    # Step 3: Recombine to compute coefficients
    # 步骤 3：重新组合以计算系数
    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 算法计算相对于基多项式 bj(n)(X) 的系数 cj，使得

f(X)=∑j=0kn−1cj⋅bj(n)(X)

计算系数所依据的基取决于在 FFT 算法的每一层使用的多项式映射 ψ 和 Twiddle 因子 t0,t1,⋯tk−1 的选择。

为了实际了解这一点，让我们逐步介绍一个简单的示例。考虑大小为 4 的域上的 Cooley-Tukey FFT 算法，以计算最多 3 次多项式的系数。首先，我们分解原始多项式 f(X)： f(X)=t0(X)⋅f0(ψ(X))+t1(X)⋅f1(ψ(X))

然后，我们分解两个子多项式 f0(X) 和 f1(X)： f0(X)=t0(X)⋅f00(ψ(X))+t1(X)⋅f01(ψ(X))

f1(X)=t0(X)⋅f10(ψ(X))+t1(X)⋅f11(ψ(X))

假设 f00(X)、f01(X)、f10(X) 和 f11(X) 是常数多项式。那么

f0(X)=a⋅t0(X)+b⋅t1(X)

f1(X)=c⋅t0(X)+d⋅t1(X)

将上述值代入 f(X) 的分解式：

f(X)=t0(X)⋅(a⋅t0(ψ(X))+b⋅t1(ψ(X)))+t1(X)⋅(c⋅t0(ψ(X))+d⋅t1(ψ(X)))

因此，上述算法计算相对于以下基的系数：t0(X)⋅t0(ψ(X))、t0(X)⋅t1(ψ(X))、t1(X)⋅t0(ψ(X)) 和 t1(X)⋅t1(ψ(X))。

因此，根据多项式映射 ψ 和 Twiddle 因子 t0,t1 的选择，FFT 算法输出相对于特定基的系数。

选择 1：我们使用多项式映射 ψ(X)=X2 和 Twiddle 因子 t0(X)=1,t1(X)=X。这使我们获得了相对于单项式基的系数，如下所示： b(X)={1,X,X2,X3}
选择 2：我们使用多项式映射 ψ(X)=X2 和 Twiddle 因子 t0(X)=X,t1(X)=X+1。这使我们获得了相对于以下基的系数： b(X)={X⋅X2,X2⋅(X+1),X⋅(X2+1),(X2+1)⋅(X+1)}

类似地，circle FFT 输出相对于某些基 bj(n)(X,Y) 的系数 cj，使得： f(X,Y)=∑j=02n−1cj⋅bj(n)(X,Y)

计算系数所依据的基取决于多项式映射和 Twiddle 因子的选择。在 twin-coset D3 上的 circle FFT 的具体示例中，我们看到该算法计算了相对于以下基的系数： bj(3)(X,Y)=[1,X,π(X),X⋅π(X),Y,Y⋅X,Y⋅π(X),Y⋅X⋅π(X)]

使用归纳法对 n 进行归纳，我们可以证明 Circle FFT 算法输出的系数与以下基相关 [定理 2, Circle STARKs]：

bj(n)(X,Y):=Yj0⋅Xj1⋅π(X)j2⋅π2(X)j3⋯πn−2(X)jn−1

其中 0≤j≤2n−1 且 (j0,…,jn−1)∈{0,1}n 是 j 的二进制表示，即 j=j0+j1⋅2+⋯+jn−1⋅2n−1。

注意

在论文中，基 b(n)(X,Y) 的元素定义为：

bjn(X,Y):=Yj0⋅v1(X)j1⋯vn−1(X)jn−1

这里，每个 vk(X) (对于 1≤k≤n−1) 是大小为 2k 的标准位置陪集的消失多项式，如第二部分中所述。

这与我们之前对基的定义一致，使用以下替换： vk(X)=πk−1(X),1≤k≤n−1。

维度差距

令 b(n)(X,Y) 中基多项式所张成的空间为 LN′(F)。基 b(n)(X,Y) 共有 N=2n 个元素，因此空间 LN′(F) 的维度为 N。然而，圆曲线上的二元多项式空间为 LN(F)，其维度为 N+1，如第二部分中所述。

我们可以通过检查基来识别 LN′(F) 中缺失的最高总阶元素。基 b(n)(X,Y) 中最高总阶元素为： Y⋅X⋅π(X)⋅π2(X)⋅π3(X)⋯πn−2(X)

使用 deg(πj(X)=2j)，上述项中 X 的最高阶为： 1+2+22+23+⋯+2n−2=2n−1−1=N/2−1

由于 LN′(F) 中 X 的最高阶为 N/2−1，我们可以将空间 LN′(F) 表示为： LN′(F)=F[X]≤N/2−1+Y⋅F[X]≤N/2−1 其中 F[X]≤N/2−1 表示在 F 中具有系数的阶最多为 N/2−1 的多项式。类似地，我们可以将空间 LN(F) 表示为： LN(F)=F[X]≤N/2+Y⋅F[X]≤N/2−1

因此，空间 LN′(F) 不包括单项式 XN/2，它位于空间 LN(F) 中。因此， LN(F)=LN′(F)+⟨XN/2⟩

由于 XN/2 张成的空间与消失多项式 vn(X) 张成的空间相同，后者具有阶 deg(vn)=2n−1=N/2，我们也可以写成： LN(F)=LN′(F)+⟨vn⟩

这种维度差距的一个结果是，我们无法在圆上插值一些多项式，即那些具有 XN/2 的多项式。我们将在本系列的下一部分中看到如何处理这个问题。

结论

我们没有介绍逆 FFT，即在给定点集处评估多项式。然而，该方法在概念上是相似的，并且所有操作都可以反向运行。这留给读者作为练习。

在下一部分中，我们将讨论如何在 FRI 协议中处理这种维度差距，并了解之前帖子中的所有想法如何结合在一起来构建 Circle STARK。

原文链接： blog.zksecurity.xyz/post...

登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～

翻译
学分: 8
分类: 密码学
标签: Circle FFT Cooley-Tukey FFT STARK 零知识证明多项式插值 twin-coset

本文参与登链社区写作激励计划，好文好收益，欢迎正在阅读的你也加入。

Circle STARKs：第三部分，Circle FFT - ZKSecurity

回顾

介绍

Cooley-Tukey FFT

问题陈述

算法

步骤 1：分解 f(X) 并计算子多项式的求值

步骤 2：将 FFT 递归地应用于子多项式

步骤 3：合并系数

Circle FFT 的域序列

Circle FFT

算法

步骤 1：分解 f(X,Y) 并计算子多项式的求值

步骤 2：将 FFT 递归地应用于子多项式

步骤 3：合并系数

实现

FFT 的基

维度差距

结论

0 条评论

文章目录