Circle STARKs：第二部分，圆 - ZKSECURITY

在这篇文章中，我们将开始探索圆形 STARKs 的代数。 实际上这非常容易。

复数

你还记得高中数学中的复数 C 吗？ 有些高中老师比其他老师更擅长表达这一点， 但“构造”复数的方法是将多项式环 R[X] 除以由不可约多项式 X2+1∈R[X] 生成的理想： C=R[X]/(X2+1) 换句话说，多项式加上/减去 X2+1 的倍数。 更常见的思考复数的方式是 a+b⋅i 其中 i 和 −i 是多项式 X2+1 的根，即 i2+1=0 且 (−i)2+1=0。 这两种观点通过以下方式是同构的（相同的）：

ϕ:a+b⋅i↦a+b⋅X

为了完整起见，让我们简要回顾一下复数的代数：

你“按坐标”加复数： (a+b⋅i)+(c+d⋅i)=(a+c)+(b+d)⋅i 这是因为，正如我们所见，它们实际上只是（等价类）伪装的多项式 这就是你如何加多项式的。 类似地，你这样乘复数： (a+b⋅i)⋅(c+d⋅i)=(a⋅c−b⋅d)+(a⋅d+b⋅c)⋅i 这等同于 F[X] 中多项式的乘法， 然后对 X2+1 取模进行约简。 最后，因此，如果你将一个复数乘以自身，你会得到： (a+b⋅i)⋅(a+b⋅i)=(a2−b2)+2⋅a⋅b⋅i 因为，你知道，i2=−1。 我们还有复数 z¯ 的 “复共轭”，它通过翻转虚部 i 来定义，即 (x+iy)―=x−iy。 这分布在乘法和加法上：z1⋅z2―=z1¯⋅z2¯ 和 z1+z2―=z1¯+z2¯。 回想一下，i 和 −i 都是多项式 X2+1 的根， 因此可以将共轭视为在 i 和 −i 的任意选择之间切换。 如果你觉得很花哨，你可以将这样的映射称为域自同构： 它从域映射到自身并保留域运算。

实数没有什么特别之处

在上面的章节中，我们构造了复数作为多项式环 R[X] 的商 通过由不可约多项式 X2+1∈R[X] 生成的理想。 对于任何 域 F（在上面的例子中 F=R）来说，这完全一样， 特别是对于有限域： 假设我们有一个有限域 F=Fq， 那么你可以考虑多项式 X2+1∈Fq[X] 并用这个多项式的根扩展域。即，将 Fq 的 “2 次扩展” 形式化为：

Fq2=Fq[X]/(X2+1)

请注意，X2+1 需要在域 Fq 中是不可约的 例如，F=F2 将不起作用，因为：

(X+1)2=X2+1+2X=X2+1

单位圆作为一个群

你还记得高中数学中的实数单位圆吗？ 当然记得，它在这里： S1={(x,y)∣x2+y2=1}⊂R2 这仅仅意味着 R 中每个 “l2 范数为 1” 的元素： 每个距离原点 “距离 1” 的点，或者如果你愿意，每个长度为 1 的向量。

如果我们考虑范数为 1 的复数，我们得到复平面中的单位圆： S1={z∈C∣|z|=1}={z=x+iy∈C∣z⋅z¯=1} 通过这样观察圆，我们可以看到它在乘法下是一个群， 如果你将两个范数为 1 的复数 z1,z2∈C 相乘， 你会得到一个范数为 1 的复数 z1⋅z2， 如下所示： (z1⋅z2)⋅z1⋅z2―=(z1⋅z¯1)⋅(z2⋅z¯2)=1⋅1=1 如果你在高中时真正注意听讲，你甚至可能还记得Euler公式， 它是范数为 1 的复数的另一种表示形式： eiθ=cos⁡(θ)+isin⁡(θ)∈S1 这很有用，因为它在角度 θ 和单位圆上的点之间进行转换， 如下面的动画所示：

所以我们也可以把它写成：

S1={(x,y)∣x2+y2=1}={z∈C∣|z|=1}={eiθ∣θ∈R}

因此，单位圆具有群结构， 我们可以通过几种方式看待它：

• 作为复数的乘法： (x1+iy1)⋅(x2+iy2)=(x1x2−y1y2)+i(x1y2+x2y1)

• 作为角度的加法 θ1+θ2： eiθ1⋅eiθ2=ei(θ1+θ2)

单位元素是角度 θ=0 处的点， 它是点 (x,y)=(1,0) 或 1∈C：

1+0i=ei0=1

z=x+iy=eiθ 的倒数是角度相同但方向相反的点：

J(z)=ei(−θ)=x−iy

这个点总是正好位于圆上 z 点的对面， 所以我们所要做的就是翻转 y 坐标： z 的复共轭。 这在下面用一个点及其围绕圆移动的倒数来说明：

从群结构的两种解释中可以清楚地看出：

• 作为复数的乘法： z⋅J(z)=(x+iy)⋅(x−iy)=x2+y2=1

• 作为角度的加法： eiθ⋅J(eiθ)=eiθ⋅e−iθ=eiθ−iθ=ei⋅0=1

既然我们有一个群，那么很自然地看看从群到自身的映射。 其中最核心的将是不起眼的 “平方” 或 “加倍” 映射， 具体取决于我们选择哪种视角： π:S1→S1 哪个简单地：

• 对范数为 1 的复数 z=x+iy 求平方： π(x+iy)=(x+iy)⋅(x+iy)=(x2−y2)+i(2xy)=2x2−1+i(2xy)
• 或者，等效地，将点 z=eiθ 的角度加倍： π(eiθ)=eiθ⋅eiθ=ei⋅2θ

因为我们有 x2+y2=1， 我们可以用 1−x2 替换 y2 并写成 π(x+iy)=2x2−1+i(2xy)。 请注意，加倍点的 x 坐标（“实部”）2x2−1 不依赖于 y， 这意味着我们可以仅使用 x 坐标和公式 xn+1=2⋅xn2−1 来计算重复加倍的 x 坐标（“实部”）， 这是一项很好的优化，稍后会派上用场。

圆有多“大”？

我们刚刚看到圆复数乘法群的一个子群， 我们之前也看到，实数的 2 次扩展与任何其他域相比没有什么 “特殊的”， 特别是有限域。

下一个自然的问题是：我们引入的这个圆群有多 “大”？ 即它的阶是多少？ 即，在任意域上单位圆上有多少个点？ 为了弄清楚这一点，我们创建了一个从圆到具有 “额外点” 的投影线的双射映射。 为了探索这一点，请考虑以 (−1,0) 为中心的 y 轴上的 “立体投影”： 直线 ((−1,0),(x,y)) 与 y 轴的交点。 如下图所示：

因此，当我们围绕圆移动点时，我们可以 “击中” y 轴上的每个值 AND 特殊值 “在无穷远处”， 当 (x,y)=(−1,0) 时： 它将圆上的任何点发送到 R∪{∞}。

也很容易看出该映射是单射的，即每个点 R∪{∞} 对应于圆上的一个唯一的点。 因此，单位圆和具有无穷远处点的投影线之间存在同构。 当 x≠−1 时，显式映射和逆映射由下式给出：

t=yx+1,(x,y)=(1−t21+t2,2t1+t2)

虽然上面的图示仅对实数有意义，但映射（上面的方程式）适用于任何域 F。 这意味着域 F 上单位圆上的点数为 |F|+1， 对应于投影线 F AND 无穷远处的点。 当 |F|=2k−1（梅森素数）时，单位圆有 2k 个点，即它是我们可以用于 FFT 和 FRI 的平滑群 正如本系列的第一部分中讨论的那样。

作为一个完整性检查： 假设我们有一个任意域 F （例如，某个素数域 Fp）， 2 次扩展 C=F[X]/(X2+1) 中的元素总数为 |C|=|F|2， 乘法群 C∗ 中的元素数为 |C∗|=|F|2−1， 除了 0 之外的所有元素都有一个倒数。 因此 |S1|=|F|+1 符合预期地除以 |C∗|=|F|2−1： 由于圆是乘法群 C∗ 的一个子群， 这是拉格朗日定理所要求的。

现在我们知道单位圆是一个阶数为 2k 的循环群， 让我们更多地了解它的子群和陪集。

单位圆的子群

在前一节中，我们确定了单位圆上的点数为 |F|+1 即，单位圆是一个阶数为 |F|+1 的循环群。 阶数为 |F|+1 的循环群 对于 |F|+1 的每个除数 N，都有一个阶数为 N 的子群。

在复数的情况下，由于圆中有 2π 弧度，因此 ω=eiθ， 其中 θ=2πN， 生成一个阶数为 N 的循环子群。 我们将大小为 N=2n 的循环子群表示为 Gn。 在 STARK 协议中，计算跟踪被编码为使用 FFT 算法在某个域 D 上的低次多项式。 对于圆形 STARK， 域 D 是圆曲线上一组点。 我们现在将探索适用于圆形 FFT 的域。

考虑 Gn−1，大小为 2n−1 的循环子群及其两个陪集 Q⋅Gn−1 和 Q−1⋅Gn−1。 两个陪集的并集 D=Q⋅Gn−1∪Q−1⋅Gn−1 使得 Q⋅Gn−1∩Q−1⋅Gn−1=∅ 称为大小为 N=2n 的双陪集。 在梅森素数上定义的圆形群的情况下， 双陪集 D 是由以下给出的子群 Gn 的陪集

D=Q⋅Gn=Q⋅Gn−1∪Q−1⋅Gn−1,

我们将 D 称为大小为 N=2n 的标准位置陪集。 这组 D 形成了我们的圆形 FFT 的迹域。 我们将使用以下示例来理解双陪集和标准位置陪集的结构。

该动画演示了 G2，一个大小为 4 的子群，用橙色点表示。 然后显示两个陪集：Q⋅G2 和 Q−1⋅G2。

1. 旋转 Q： 将 G2 乘以 Q 对应于以角度 δ 逆时针旋转 G2。 这被可视化为表示 Q⋅G2 的旋转橙色点。

2. 旋转 Q−1： 类似地，将 G2 乘以 Q−1 顺时针旋转 G2 δ。 这显示为表示 Q−1⋅G2 的旋转蓝色点。

两个集合的并集 D=Q⋅G2∪Q−1⋅G2 形成了大小为 8 的双陪集。 Q 的不同值对应于不同角度 δ 的旋转。 对于 Q 的特定选择 （例如，旋转 δ=π/8=0.125π），双陪集 D 变为子群 G8 的陪集。 在这种情况下，D 是大小为 8 的标准位置陪集。

请注意，标准位置陪集（旋转 δ=0.125π）的点关于中心 (0,0) 对称，并且在圆周围等间距。 相比之下，对于双陪集（旋转 δ≠0.125π），这些点仅关于 (0,0) 对称。

我们现在将研究在标准位置陪集上插值（圆形 STARK 的迹域）的多项式。

圆上的多项式

在 STARK 的上下文中，计算迹被插值为指定域上的多项式。 对于传统 STARK， 此域是平滑加法/乘法子群的陪集， 并且生成的插值产生单变量多项式。 然而，在 Circle STARK 的情况下， 该域由圆曲线上的点（特别是标准位置陪集）构成。 这里，插值产生二元多项式，因为圆曲线上的点由两个变量表示：x 和 y。

设 F[x,y] 表示系数在 F 中的二元多项式环。 由于插值发生在圆曲线上的点上，因此生成的多项式属于多项式环 F[x,y] 的商 通过理想 (X2+Y2−1)。 这些二元多项式在总次数 ≤N/2 的圆曲线上构成的空间表示为 LN(F)。

LN(F)=F[X,Y]/(X2+Y2−1)

其中 (X2+Y2−1) 表示由多项式 X2+Y2−1 生成的理想，即

(X2+Y2−1)={p(X,Y)⋅(X2+Y2−1)∣p(X,Y)∈F[X,Y]}

现在让我们看看这些多项式的另一种表示形式。 对于任何 p(X,Y)∈LN(F)， 我们可以用圆的方程 Y2=1−X2 替换 Y 的所有高次项，并将 p(X,Y) 简化为以下形式，

p(X,Y)=p0(X)+Y⋅p1(X),

由于 p(X,Y) 的总次数 ≤N/2， 因此 p0 的次数 ≤N/2， p1 的次数 ≤N/2−1。 从上面的表示形式中，我们可以看到 LN(F) 空间由以下单项式基张成：

1,X,…,XN/2,Y,Y⋅X,…,Y⋅XN/2−1

LN(F) 的维度是单项式基元素的数量， 即 N+1。 现在我们将了解消失多项式， 它属于 LN(F) 空间。

消失多项式

消失多项式是在特定点集上求值为零的非零多项式。 在 STARK 中， 我们在计算迹上定义多项式约束。 当相应的多项式在迹域上的点上求值为零时，满足这些约束。 因此，约束多项式必须是消失在（或求值为零）迹域上的多项式的倍数。 因此，我们对迹域上的消失多项式特别感兴趣，迹域是双陪集（或标准位置陪集）。

在深入研究消失多项式之前， 让我们首先了解平方映射的一些属性， 这些属性将用于表达这些消失多项式。

平方映射 π 是一个 2 对 1 的映射，它将大小为 N 的双陪集（或标准位置陪集）D 缩减为大小为 N/2 的双陪集（或标准位置陪集）。 π 的这个属性 对于在圆形 FFT 期间将域减半至关重要。 平方映射对应于将单位圆上每个点的角度加倍， eiθ⋅eiθ=ei(2θ)

以下动画显示了平方映射一次应用于陪集中的每个点， 这等效于将每个点的角度加倍（由旋转表示）。 该过程从蓝点表示的陪集开始。 通过将每个点的角度加倍， 我们获得一个大小为一半的陪集，由红点表示。 类似地，将平方映射应用于橙点表示的陪集会产生一个大小为一半的陪集，由紫点表示。

因此，将平方映射一次应用于大小为 8 的双陪集（由蓝色和橙色点表示） 会产生大小为 4 的双陪集（由红色和紫色点表示）。 更一般地， 将平方映射 n−1 次应用于大小为 N=2n 的双陪集 D 会得到大小为 2 的双陪集，如下所示：

πn−1(D)={(XD,YD),(XD,−YD)}

如果我们将这些点投影到 x 轴上， 我们最终会得到它们的 x 坐标 XD。

πx∘πn−1(D)=XD

其中 πx 是到 x 轴的投影。 我们可以将双陪集 D 上的消失多项式表示为

vD(X,Y)=πx∘πn−1(D)−XD

该平方映射本身是一个多项式，由 π(x+iy)=(2x2−1)+i(2xy) 给出 因此，当它与自身和 x 投影迭代组合时，结果也是一个多项式： 消失多项式 vD(X,Y)。 请注意，vD(X,Y) 在双陪集 D 的所有点上求值为 0。

如前所述，应用于标准位置陪集的平方映射会给出大小减半后的标准位置陪集。 以下示例说明了应用于大小为 N=8 的标准位置陪集的平方映射。

但是，在标准位置陪集的情况下， 在将平方映射应用 n−1 次之后， 最终点位于 y 轴上， 即 XD=0。 因此，大小为 N=2n 的标准位置陪集 D 上的消失多项式是 vD(X,Y)=πx∘πn−1(D)

结论

在这篇文章中， 我们探索了圆形曲线， Circle STARK 中使用的迹域（即标准位置陪集，更一般的是双陪集） 以及在此域上插值的二元多项式。 在本系列的第三部分中， 我们将在此基础上构建这些概念， 并深入研究 圆形 FFT。

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