cover_image

Circle STARKs 系列（一）：梅森素域

Kurt Pan XPTY
2024年06月06日 16:03

原文：https://www.zksecurity.xyz/blog/posts/circle-starks-1/

译者：Kurt Pan

引言

在零知识证明系统中，我们（几乎）总是在有限域上进行操作，并且由于证明者通常必须进行大量的域操作来生成证明，因此我们自然希望我们的域操作要尽可能快。如果使用椭圆曲线密码学，我们被限制在“密码学大小”的域，比如大约 256 位可实现 128 位安全性。然而，类 STARK 的技术（里德-所罗门IOP）在安全参数和域大小之间并没有这种直接依赖性。因此，我们可以使用小得多的域。

通过这样做, 我们就可以使用具有非常高效算术的域, 例如小二进制域或小素域（想想 32 位或 64 位)。此类域中最快的是小梅森素域，其具有非常简单的模约简。

不幸的是, 直到最近, 这些域的结构使其并不适合 STARK, 因为它们无法有效地兼容 FRI/STIR。现在情况已经改变了。这是一个四部分系列的开始, 解释了 Haböck、Levit 和 Papini 最近被称为Circle STARK的构造，该结构使得 STARK 可以更高效地使用这些特定的域。本系列结构如下：

https://eprint.iacr.org/2024/278

  • 第一部分——梅森素域的介绍、背景和动机（这篇文章）。
  • 第二部分——我们把单位圆当作群来进行探索。
  • 第三部分 —— 实现circle FFT 并应用 FRI 中的技术。
  • 第四部分——我们探索 Circle STARK 的算术化。

FRI 和 STARK 的预备知识

这篇文章的目的不是解释 FRI 的一般工作原理，关于此我推荐下面两篇博文，尽管我们会在本系列的后续部分中介绍 Circle FRI 和 Circle STARK。

  • https://rot256.dev/post/fri/
  • https://aszepieniec.github.io/stark-anatomy/fri

现在只要知道要实例化 FRI（和 STARK）需要：

  1. 一个有限域 。
  2. 一个阶 的群 一个平滑群, 其操作定义在 上：即可以通过 上的（低次）多项式/有理函数来计算。
  3. 具有小（2 阶）核的 个群同态 序列。其中每个同态都可以表示为 上的（低次）多项式/有理函数。 同态定义了一系列越来越小的平滑群 :

以下是可能的 FRI 实例化情况的简要概述:

1) 平滑乘法子群

当 的乘法子群 平滑时可用:

  • 适合当 对某些 的素数域 。
  • 子群为 , 其中 的阶为 。
  • 同态 只是进行平方。
  • 因此较小的群 是 。 这是 Ben-Sasson、Bentov、Horesh 和 Riabzev 于在2018 年最初的构造。

https://eprint.iacr.org/2018/046

2) 二进制域的向量空间

当域是二进制域 时可用。

  • 这种风格对于所验证的计算是二进制的应用来说非常有用。例如, Keccak 的求值在二进制域上的表达最为高效。此外，二进制域在硬件中速度非常快。
  • 子群是一个线性子空间：我们将 视为上的 维向量空间，采用 维子空间，换句话说对 -线性独立向量
  • 子空间的同态商为:

这是一个 - 线性变换, 它对应于具有核空间 的矩阵, 即变换一维 生成的子空间到零。

由Ben-Sasson、Goldberg、Kopparty 和 Saraf 在 2019 年的 DEEP-FRI 论文中首次引入。

https://eprint.iacr.org/2019/336

3）平滑椭圆曲线（ECFFT）

适合任意大域 。

  • 当你需要特定域时很有用。例如, 如果你想在 STARK 内验证 secp256k1 ECDSA 签名，你可以使用 secp256k1 的基域作为 STARK 的域, 从而可以有效验证曲线操作。
  • 该技术实际上是稍稍泛化了我们上面描述的形式, 求值域 不是子群, 而是子群的陪集。这个子群是某个其点在 中的椭圆曲线的平滑子群,

因此陪集 也具有阶 。使用陪集（代替 ) 是因为我们最终想要求值域元素处的多项式，而不是椭圆曲线点 ，这是通过映射 到其 坐标来实现的, 因此我们必须确保 具有唯一的 坐标--椭圆曲线的子群并不符合这个条件：元素及其逆元都有相同的 坐标

  • 同态是椭圆曲线间同源的序列，每个同源核的大小为 2：将 映射到 ， 。由于椭圆曲线之间的同源是有理函数, 因此同态是有理函数，而不是多项式。
  • 实现可以使得效率与乘法子群情况相当, 但显然使用大域（如椭圆曲线的基域）会使 STARK 变慢。一个问题是域需要很大, 域的大小是求值域 的平方, 以确保具有平滑子群的椭圆曲线存在: Hasse定理指出椭圆曲线的阶为 , 其中 是域的大小, 因此要有一个能被 整除的阶, 我们需要 。

该结构于 2021 年引入, 分为 Ben-Sasson、Carmon、Kopparty 和 Levit 撰写的两篇论文 ECFFT Part I 和 ECFFT Part II。

  • https://arxiv.org/abs/2107.08473
  • https://www.math.toronto.edu/swastik/ECFFT2.pdf

4) 单位圆（Circle STARK / Circle FRI)

适用于素域 , 其中 。最著名的是梅森素数： 。

  • 如果你需要在素域上进行快速的 STARK, 这很有用。
  • 子群是 上单位圆上的一组点。
  • 同态是圆上的倍点（以及复共轭）。
  • 与椭圆曲线的情况不同，同态是多项式：因为复数乘法和共轭是多项式，与椭圆曲线上的加法/倍点不同。
  • 本质上是更强大的 ECFFT 技术的简化（genus 0）特例。

这项技术是由 Haböck、Levit 和 Papini 今年（2024 年）提出的。

https://eprint.iacr.org/2024/278

也将是本系列的关注重点。

梅森素域

前两组技术已被广泛部署, 例如由以下团队部署的例子:

  • Polygon Zero。使用素域 ， 。
  • StarkWare。使用素域 ， 。
  • Ulvetanna。使用二进制域 。

选择这些域是因为它们能够实现快速算术, 从而实现快速 STARK 证明生成。就素域而言, 最近推出的第四种技术 Circle STARK 可以在一类素域（梅森素域）上达到更快的 STARK。

Circle STARK 是在域 上定义的, 其中 是素数：即整数模一个梅森素数。在二进制中, 该素数只是一个由 个1组成的串:

事实证明, 模约简就像和掩码进行“与"操作, 然后加上右移的高位一样简单, 例如对于 31 位梅森素数 , 约简可以实现为:

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

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

该函数输入一个 64 位整数并生成部分约简结果, 应用约简两次会生成完全约简结果。要了解其原理，请看如果我们定义:

我们可以将 表示为:

因此:

因为 , 我们有:

这显然非常快：在任何现代 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 位梅森素数 , 它是适用 64 位整数的最大梅森素数, 并应用类似的技术。

要点：我们希望为 STARK 使用梅森素域，因为模约减非常快：没有比这更好的了。

梅森素数的问题

通常, 在设计 STARK 时, 我们有许多可能的（素数）域 可以选择, 并且我们可以选择一个具有平滑乘法子群的域。一种方法是选择 使得 为质数, 那么该域将具有阶为 的平滑子群，因为 。例如, ethSTARK 的素数 有 , 仅仅因为它是使 成为素数的最小的 。

梅森素数的问题是我们无法挑选它们, 已知的只有 51 个, 而且增长得非常非常快。因此, 与 ethSTARK 的素数不同, 我们不能只是简单地“选择另一个”，不幸的是它们没有平滑的乘法子群，例如，31 位梅森素数 具有乘法群的阶为：

看不到 2 的大幂:(

在本系列的第二部分中, 我们将开始探索可以在梅森素数情况下被使用的另一种群结构, 即单位圆。