Circle STARKs：第一部分，梅森素数 - ZKSECURITY

引言

在零知识证明系统中，我们（几乎）总是在一个有限域上进行运算，并且因为证明者通常需要进行大量的域运算来生成证明，所以我们自然希望我们的域运算尽可能地快。使用椭圆曲线密码学时，我们被限制在“密码学大小”的域中，例如，对于 128 位的安全性，大约为 256 位。然而，类似 STARK 的技术 (Reed-Solomon IOPs) 在安全参数和域大小之间没有这种直接的依赖关系。 因此，我们可以使用小得多的域。

通过这样做，我们可以使用具有非常高效算术的域，例如小的二元域或小的素数域（考虑 32 位或 64 位）。 一些最快的这种域是小的梅森素数域，它们具有非常简单的模约简。

不幸的是，直到最近，这些域的结构使得它们不适合 STARK，因为它们不能有效地容纳 FRI/STIR。 现在这种情况已经改变了。 这是由 Haböck, Levit 和 Papini 提出的 Circle STARKs 的四部分系列的开端，它使能够使用这些特定域，以更高的效率用于 STARK。 该系列将结构如下：

• 第一部分 – 介绍、背景和梅森素数域的动机（本文）。
• 第二部分 – 我们将探索单位圆作为一个群。
• 第三部分 – 实现圆形 FFT 并将这些技术应用于 FRI 中。
• 第四部分 – 我们将探索 Circle STARK 的算术化。

FRI 和 STARK 的先决条件

这篇文章的目的不是解释 FRI 的一般工作原理，为此，我推荐 这篇博文 或 这篇，尽管我们将在本系列的未来部分中介绍 Circle FRI 和 Circle STARK。 现在，只要知道要实例化 FRI（和 STARK），你需要：

1. 一个有限域 F。
2. 一个阶数为 |L0|=2k 的群 L0：一个在其上定义运算的光滑群 F：

它可以通过 F 上的（小次数）多项式/有理函数来计算。

3. 一系列 k 个群同态 ϕi:Li→Li+1，具有小的（2 阶）核。

每个都可以表示为 F 上的（小次数）多项式/有理函数。

同态定义了一个越来越小的光滑群序列 Li=ϕi(Li−1)：

L0L1=ϕ1(L0)L2=ϕ2(ϕ1(L0))⋮Lk=ϕk(ϕk−1(…ϕ1(L0)…))

以下是可能的 FRI 实例化的简要概述：

1) 光滑乘法子群

当 F 的乘法子群 F∗ 是光滑的时可用：2k||F∗|

• 适用于素数域 Fp，当 p−1=2k⋅n 对于某个 n。
• 子群是 L0=⟨ω⟩={ωi∣i∈[0,2k)} 其中 ω∈Fp∗ 的阶数为 2k。\
• 同态只是平方 ϕ:X↦X2。\
• 因此，较小的群 Li 是 Li=⟨ω2i⟩。\ \ 这是 Ben-Sasson、Bentov、Horesh 和 Riabzev 于 2018 年提出的原始构造。\ \ 2) 二元域的向量空间\ \ 当域是一个二元域 F2m 时可用。\ \
• 这种形式适用于被验证的计算是二元的应用程序。\ 例如，Keccak 的评估在二元域上表达效率最高。\ 此外，二元域在硬件中非常快。\ \
• 子群是一个线性子空间：我们将 F2m 看作一个 m 维的在 F2 上的向量空间\ 并取一个维度为 k 的子空间，换句话说，对于 F2 线性独立的向量 v1,…,vk∈F2m。\ L0=⟨v1→,…,vk→⟩={∑iλivi→∣λi∈F2}\ \
• 同态通过 L0 的一个子空间进行商：\ ϕi(X)=∏e→∈⟨vi→⟩(X−e→)\ 这是一个 F2 线性变换，\ 它对应于一个具有核空间 ⟨vi→⟩={vi→,0→} 的矩阵，即将由 vi→ 生成的某个一维子空间发送到零。\ \ \ 由 Ben-Sasson、Goldberg、Kopparty 和 Saraf 在 2019 年的 DEEP-FRI 论文 中介绍。\ \ 3) 光滑椭圆曲线 (ECFFT)\ \ 适用于任何大域 F。\ \
• 如果你需要一个特定的域，这将非常有用。 例如，如果你想验证 STARK 内部的 secp256k1 ECDSA 签名，\ 你可以使用 secp256k1 的基域作为 STARK 的域，从而可以有效地验证曲线运算。\ \
• 该技术实际上略微推广了我们上面概述的形式，评估域 L0 不是一个子群，而是一个子群的陪集。 该子群是 F 中具有点的某个椭圆曲线的光滑子群：\ E0(F)={(x,y)∣y2=x3+A⋅x+B}⊆F2G≤E0(F)阶数为2kL0=e+G⊆E0(F)\ 因此，陪集 L0 也具有阶数 2k。\ 使用陪集（代替 G）是因为我们最终希望在域元素而不是椭圆曲线点 (x,y) 处评估多项式，\ 这是通过将曲线点 (x,y) 映射到其 x 坐标来实现的，因此我们必须确保 L0 的每个元素都有一个唯一的 x 坐标——对于椭圆曲线的子群来说情况并非如此：该元素及其逆元素具有相同的 x 坐标。\ \
• 同态是椭圆曲线之间的一系列同源，每个同源都有一个大小为 2 的核：\ 将 Li⊆Ei(F) 映射到 Li+1⊆Ei+1(F)\ 其中 |Li+1|=|Li|/2。\ 由于椭圆曲线之间的同源是有理函数，因此同态是有理函数，而不是多项式。\ \ \
• 该实现将效率提高到与乘法子群情况相当的水平，\ 但显然使用大域（如椭圆曲线的基域）会使 STARK 速度变慢。\ 一个问题是该字段需要很大（ish），是域 L0 大小的二次方，以确保存在具有光滑子群的椭圆曲线：Hasse 定理指出椭圆曲线的阶数为 p+1±2p，其中 p 是域的大小，因此要有一个可被 2k 整除的阶数，我们需要 p≈(2k)2。\ \ 此构造于 2021 年推出，分为两篇论文 ECFFT 第一部分 和 ECFFT 第二部分，作者为 Ben-Sasson、Carmon、Kopparty 和 Levit。\ \ 4) 单位圆 (Circle STARK / Circle FRI)\ \ 适用于素数域 Fp 其中 2k∣p+1。 最值得注意的是梅森素数：p=2k−1。\ \
• 如果你需要一个基于素数域的快速 STARK，这将非常有用。\
• 子群是 Fp 上单位圆上的一组点。\
• 同态是圆上的点加倍（和复共轭）。\
• 与椭圆曲线情况不同，同态是一个多项式：因为复数乘法和共轭是多项式，与椭圆曲线上的加法/加倍不同。\
• 本质上是更强大的 ECFFT 技术的简化（亏格 0）特殊情况。\ \ 这项技术是由 Haböck、Levit 和 Papini 在今年 2024 年提出的\ \ 这将是本系列的重点。\ \

  梅森素数域\

  \ 前两组技术已被广泛部署，例如由以下团队：\ \

• Polygon Zero。 使用素数域 Fp，其中 p=264−232+1。\
• StarkWare。 使用素数域 Fp，其中 p=261+20⋅232+1。\
• Ulvetanna。 使用二元域 F2k。\ \ 选择这些域是因为它们可以实现快速算术，从而实现快速 STARK 证明。 对于素数域，最近引入的第四种技术 Circle STARK 将允许对一类素数域进行更快的 STARK：梅森素数域。\ \ Circle STARK 定义在域 F=Z/(2k−1)Z 上，其中 2k−1 是素数：整数模梅森素数 2k−1。\ 在二进制中，素数只是一个由 k 个 1 组成的字符串：\ \ 2k−1=1111…11112\ \ 事实证明，模约简就像与掩码进行 AND 运算一样简单，并将高位向下移动并添加，例如\ 对于 31 位梅森素数 231−1，该约简可以实现为：\ \

  
  #define MASK (0x7FFFFFFF) // 2^31 - 1 = 1111...1111

uint64_t reduce(uint64_t x) { return (x & MASK) + (x >> 31); }

\
这采用一个 64 位整数并生成一个部分简化的结果，应用两次约简会产生完全简化的结果。 要了解其工作原理，请注意，如果我们定义：\
\
low=x&MASK=xmod231high=x>>31=⌊x/231⌋\
\
我们可以将 x 表示为：\
\
x=low+231⋅high\
\
因此：\
\
x≡low+(231mod(231−1))⋅highmod231−1\
\
由于 231mod(231−1)=1，我们有：\
\
x≡low+highmod231−1\
\
这显然非常快：在任何现代 CPU 上只需要几个周期。 因为它是一个 31 位素数，所以任何域乘法未简化的结果最多为 62 位，因此适合 64 位整数。 使用例如 [VPMULUDQ](https://www.intel.com/content/www/us/en/docs/cpp-compiler/developer-guide-reference/2021-9/mm256-mul-epu32.html) 对其进行矢量化也非常简单。\
\
如果 31 位不够，你可以使用 61 位梅森素数 261−1，它是适合 64 位整数的最大梅森素数，并应用类似的技术。\
\
**要点**：我们希望将梅森素数域用于我们的 STARK，因为模约简非常快：实际上没有比这更好的了。\
\
## 梅森素数的问题\
\
通常，在设计 STARK 时，我们有许多可能的（素数）域 Fp 选择，并且**我们可以选择一个**具有光滑乘法子群的域。\
一种方法是选择某个 n，使得 p=2m+n⋅2k+1 是素数，则该域将具有一个阶数为 2k 的光滑子群，因为 2k∣p−1。\
例如，ethSTARK 素数\
p=261+20⋅232+1 具有 n=20，仅仅因为它使 p 成为素数的最小 n>0。\
\
梅森素数的问题是我们无法选择它们，\
只知道 51 个，并且它们增长得非常非常快。\
因此，与 ethSTARK 素数不同，我们不能只是“选择另一个”，不幸的是，它们没有光滑的乘法子群，\
例如，31 位梅森素数 p=231−1 的乘法群的阶数为：\
\|F231−1∗\|=231−1=2⋅32⋅7⋅11⋅31⋅151⋅331\
没有大的 2 的幂 :( \
\
我们将在本系列的第二部分中开始探索在梅森素数情况下可以利用的**替代群结构**，即**单位圆**。

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