本文深入探讨了Circle STARKs的代数基础,包括复数、单位圆的群性质,以及在有限域上的扩展。文章还讨论了单位圆的子群结构、余集,以及在Circle STARKs中用于计算轨迹的trace domain(标准位置陪集或更一般的双陪集)上的多项式插值和消失多项式。
在这篇文章中,我们将开始探索圆形 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 哪个简单地:
因为我们有 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。
旋转 Q: 将 G2 乘以 Q 对应于以角度 δ 逆时针旋转 G2。 这被可视化为表示 Q⋅G2 的旋转橙色点。
旋转 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 助手,为大家转译优秀英文文章,如有翻译不通的地方,还请包涵~
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!