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

XPTY
更新于 2024-06-12 15:37
阅读 1300

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

>   
> 原文：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. 一个有限域  $\mathbb{F}$。

1. 一个阶 $|L_0|=2^k$ 的群 $L_0$ : 一个平滑群, 其操作定义在 $\mathbb{F}$ 上：即可以通过 $\mathbb{F}$ 上的（低次）多项式/有理函数来计算。

1. 具有小（2 阶）核的 $k$ 个群同态 $\phi_i:L_i \rightarrow L_{i+1}$ 序列。其中每个同态都可以表示为  $\mathbb{F}$ 上的（低次）多项式/有理函数。同态定义了一系列越来越小的平滑群 $L_i=\phi_i(L_{i-1})$ :
$$
\begin{aligned}
&L_0 \\
&L_1=\phi_1(L_0)\\
&L2=\phi_2(\phi_1(L_0))\\
& ... \\
&L_k=\phi_k(\phi_{k-1}(...\phi_i(L_0)...))
\end{aligned}
$$

以下是可能的 FRI 实例化情况的简要概述:  
### 1) 平滑乘法子群  
  
当 $\mathbb{F}$  的乘法子群 $\mathbb{F}^*$  平滑时可用:   $2^k ||\mathbb{F}^*|$

- 适合当 $p-1=2^k \cdot n$ 对某些 n 的素数域  。

- 子群为$L_0=\langle \omega \rangle = \{ \omega^i | i \in [ 0,2^k) \} $  , 其中 $\omega \in \mathbb{F}^*_p$ 的阶为 $2^k$ 。

- 同态 $\phi:X \mapsto X^2$ 只是进行平方。

- 因此较小的群 $L_i$ 是 $L_i=\langle \omega^{2^i}\rangle$ 。这是 Ben-Sasson、Bentov、Horesh 和 Riabzev 于在2018 年最初的构造。
  
>   
> https://eprint.iacr.org/2018/046  
  
### 2) 二进制域的向量空间  
  
当域是二进制域 $\mathbb{F}_{2^m}$ 时可用。

- 这种风格对于所验证的计算是二进制的应用来说非常有用。例如, Keccak 的求值在二进制域上的表达最为高效。此外，二进制域在硬件中速度非常快。

- 子群是一个线性子空间：我们将 $\mathbb{F}_{2^m}$ 视为 $\mathbb{F}$上的 m 维向量空间，采用 k 维子空间，换句话说对 $\mathbb{F}_2$-线性独立向量$v_1,...,v_k \in \mathbb{F}^{2^m}$ 。

$L_0=\langle \vec v_1,...,\vec v_k \rangle =\{\sum_i \lambda_i \vec v_i | \lambda_i \in \mathbb{F}_2\}$

- $L_0$子空间的同态商为:

$\phi_i(X)=\prod_{\vec e \in \langle \vec v_i \rangle} (X- \vec e)$

这是一个 $\mathbb{F}_2$ - 线性变换, 它对应于具有核空间 $\langle \vec v_i \rangle = \{ \vec v_i, \vec 0 \}$ 的矩阵, 即变换一维 $\vec v_i$生成的子空间到零。  
  
由Ben-Sasson、Goldberg、Kopparty 和 Saraf 在 2019 年的 DEEP-FRI 论文中首次引入。  
>   
> https://eprint.iacr.org/2019/336  
  
### 3）平滑椭圆曲线（ECFFT）  
  
适合任意大域 $\mathbb{F}$ 。

- 当你需要特定域时很有用。例如, 如果你想在 STARK 内验证 secp256k1 ECDSA 签名，你可以使用 secp256k1 的基域作为 STARK 的域, 从而可以有效验证曲线操作。

- 该技术实际上是稍稍泛化了我们上面描述的形式, 求值域 $L_0$ 不是子群, 而是子群的陪集。这个子群是某个其点在  $\mathbb{F}$ 中的椭圆曲线的平滑子群,

$\mathbb{E}_0(\mathbb{F})=\{(x,y)|y^2=x^3+A\cdot x+B\} \subseteq \mathbb{F}^2$
$G \le \mathbb{E}_0 (\mathbb{F})\ of\ order\ 2^k$
$L_0=e+G \subseteq \mathbb{E}_0(F)$

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

- 同态是椭圆曲线间同源的序列，每个同源核的大小为 2：将 $L_i \subseteq \mathbb{E_i}(\mathbb{F})$ 映射到 $L_{i+1} \subseteq \mathbb{E_{i+1}}(\mathbb{F})$ ，$|L_{i+1}|=|L_i|/2$  。由于椭圆曲线之间的同源是有理函数, 因此同态是有理函数，而不是多项式。

- 实现可以使得效率与乘法子群情况相当, 但显然使用大域（如椭圆曲线的基域）会使 STARK 变慢。一个问题是域需要很大, 域的大小是求值域 $L_0$ 的平方, 以确保具有平滑子群的椭圆曲线存在: Hasse定理指出椭圆曲线的阶为 $p+1 \pm 2 \sqrt{p}$ , 其中 p 是域的大小, 因此要有一个能被 $2^k$ 整除的阶, 我们需要 $p \approx (2^k)^2$ 。

该结构于 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)  
  
适用于素域 $\mathbb{F_p}$ , 其中 $2^k |\ p+1$ 。最著名的是梅森素数： $p=2^k-1$ 。

- 如果你需要在素域上进行快速的 STARK, 这很有用。

- 子群是 $\mathbb{F_p}$上单位圆上的一组点。

- 同态是圆上的倍点（以及复共轭）。

- 与椭圆曲线的情况不同，同态是多项式：因为复数乘法和共轭是多项式，与椭圆曲线上的加法/倍点不同。

- 本质上是更强大的 ECFFT 技术的简化（genus 0）特例。

这项技术是由 Haböck、Levit 和 Papini 今年（2024 年）提出的。  
>   
> https://eprint.iacr.org/2024/278

也将是本系列的关注重点。  
## 梅森素域  
  
前两组技术已被广泛部署, 例如由以下团队部署的例子:

- **Polygon Zero** 。使用素域 $\mathbb{F_p}\ ,\ p=2^{64}-2^{32}+1$。

- **StarkWare** 。使用素域  $\mathbb{F_p}\ ,\ p=2^{61}+20\cdot 2^{32}+1$。

- **Ulvetanna** 。使用二进制域  $\mathbb{F_{2^k}}$。

选择这些域是因为它们能够实现快速算术, 从而实现快速 STARK 证明生成。就素域而言, 最近推出的第四种技术 Circle STARK 可以在一类素域（梅森素域）上达到更快的 STARK。  
  
Circle STARK 是在域 $\mathbb{F}=\mathbb{Z}/(2^k-1)\mathbb{Z}$ 上定义的, 其中 $2^k-1$ 是素数：即整数模一个梅森素数$2^k-1$。在二进制中, 该素数只是一个由 k 个1组成的串:

$2^k-1=1111...111_2$
  
事实证明, 模约简就像和掩码进行“与"操作, 然后加上右移的高位一样简单, 例如对于 31 位梅森素数 2^{31}-1, 约简可以实现为:

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

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

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

$low=x \& MASK =x \ mod \ 2^{31} $
$high=x>>31=\lfloor x/2^{31} \rfloor$
  
我们可以将  x 表示为:

$x=low \ + \ 2^{31} \cdot high$
  
因此:

$x \equiv low +(2^{31}\ mod\ (2^{31}-1)) \cdot high\ mod\ 2^{31}-1$
  
因为 $2^{31}\ mod\ (2^{31}-1)$ , 我们有:

$x \equiv low + high\ mod\ 2^{31}-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 位梅森素数$2^{61}-1$ , 它是适用 64 位整数的最大梅森素数, 并应用类似的技术。  
  
 **要点** ：我们希望为 STARK 使用梅森素域，因为模约减非常快：没有比这更好的了。

## 梅森素数的问题  
  
通常, 在设计 STARK 时, 我们有许多可能的（素数）域  $\mathbb{F}$ 可以选择, 并且我们可以选择一个具有平滑乘法子群的域。一种方法是选择 n 使得  $p=2^m+n \cdot 2^k+1$为质数, 那么该域将具有阶为 $2^k$的平滑子群，因为 $2^k|p-1$ 。例如, ethSTARK 的素数 $p=2^{61}+20 \cdot 2^{32}+1$ 有n=20 , 仅仅因为它是使 p 成为素数的最小的 n>0 。  
  
梅森素数的问题是我们无法挑选它们, 已知的只有 51 个, 而且增长得非常非常快。因此, 与 ethSTARK 的素数不同, 我们不能只是简单地“选择另一个”，不幸的是它们没有平滑的乘法子群，例如，31 位梅森素数 $p=2^{31}-1$ 具有乘法群的阶为：

$| \mathbb{F}^*_{2^{31}-1}| = 2^{31}-1=2 \cdot 3^2 \cdot 7 \cdot 11 \cdot 31 \cdot 151 \cdot 331$
  
看不到 2 的大幂:(  
  
在本系列的第二部分中, 我们将开始探索可以在梅森素数情况下被使用的另一种群结构, 即单位圆。

原文：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）需要：

一个有限域 $\mathbb{F}$。
一个阶 $|L_0|=2^k$ 的群 $L_0$ : 一个平滑群, 其操作定义在 $\mathbb{F}$ 上：即可以通过 $\mathbb{F}$ 上的（低次）多项式/有理函数来计算。
具有小（2 阶）核的 $k$ 个群同态 $\phi_i:Li \rightarrow L{i+1}$ 序列。其中每个同态都可以表示为 $\mathbb{F}$ 上的（低次）多项式/有理函数。同态定义了一系列越来越小的平滑群 $L_i=\phii(L{i-1})$ : $$ \begin{aligned} &L_0 \ &L_1=\phi_1(L_0)\ &L2=\phi_2(\phi_1(L_0))\ & ... \ &L_k=\phik(\phi{k-1}(...\phi_i(L_0)...)) \end{aligned} $$

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

1) 平滑乘法子群

当 $\mathbb{F}$ 的乘法子群 $\mathbb{F}^$ 平滑时可用: $2^k ||\mathbb{F}^|$

适合当 $p-1=2^k \cdot n$ 对某些 n 的素数域。
子群为$L_0=\langle \omega \rangle = { \omega^i | i \in [ 0,2^k) } $ , 其中 $\omega \in \mathbb{F}^*_p$ 的阶为 $2^k$ 。
同态 $\phi:X \mapsto X^2$ 只是进行平方。
因此较小的群 $L_i$ 是 $L_i=\langle \omega^{2^i}\rangle$ 。这是 Ben-Sasson、Bentov、Horesh 和 Riabzev 于在2018 年最初的构造。

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

2) 二进制域的向量空间

当域是二进制域 $\mathbb{F}_{2^m}$ 时可用。

这种风格对于所验证的计算是二进制的应用来说非常有用。例如, Keccak 的求值在二进制域上的表达最为高效。此外，二进制域在硬件中速度非常快。
子群是一个线性子空间：我们将 $\mathbb{F}_{2^m}$ 视为 $\mathbb{F}$上的 m 维向量空间，采用 k 维子空间，换句话说对 $\mathbb{F}_2$-线性独立向量$v_1,...,v_k \in \mathbb{F}^{2^m}$ 。

$L_0=\langle \vec v_1,...,\vec v_k \rangle ={\sum_i \lambda_i \vec v_i | \lambda_i \in \mathbb{F}_2}$

$L_0$子空间的同态商为:

$\phii(X)=\prod{\vec e \in \langle \vec v_i \rangle} (X- \vec e)$

这是一个 $\mathbb{F}_2$ - 线性变换, 它对应于具有核空间 $\langle \vec v_i \rangle = { \vec v_i, \vec 0 }$ 的矩阵, 即变换一维 $\vec v_i$生成的子空间到零。

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

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

3）平滑椭圆曲线（ECFFT）

适合任意大域 $\mathbb{F}$ 。

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

$\mathbb{E}_0(\mathbb{F})={(x,y)|y^2=x^3+A\cdot x+B} \subseteq \mathbb{F}^2$ $G \le \mathbb{E}_0 (\mathbb{F})\ of\ order\ 2^k$ $L_0=e+G \subseteq \mathbb{E}_0(F)$

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

同态是椭圆曲线间同源的序列，每个同源核的大小为 2：将 $L_i \subseteq \mathbb{Ei}(\mathbb{F})$ 映射到 $L{i+1} \subseteq \mathbb{E{i+1}}(\mathbb{F})$ ，$|L{i+1}|=|L_i|/2$ 。由于椭圆曲线之间的同源是有理函数, 因此同态是有理函数，而不是多项式。
实现可以使得效率与乘法子群情况相当, 但显然使用大域（如椭圆曲线的基域）会使 STARK 变慢。一个问题是域需要很大, 域的大小是求值域 $L_0$ 的平方, 以确保具有平滑子群的椭圆曲线存在: Hasse定理指出椭圆曲线的阶为 $p+1 \pm 2 \sqrt{p}$ , 其中 p 是域的大小, 因此要有一个能被 $2^k$ 整除的阶, 我们需要 $p \approx (2^k)^2$ 。

该结构于 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)

适用于素域 $\mathbb{F_p}$ , 其中 $2^k |\ p+1$ 。最著名的是梅森素数： $p=2^k-1$ 。

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

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

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

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

梅森素域

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

Polygon Zero 。使用素域 $\mathbb{F_p}\ ,\ p=2^{64}-2^{32}+1$。
StarkWare 。使用素域 $\mathbb{F_p}\ ,\ p=2^{61}+20\cdot 2^{32}+1$。
Ulvetanna 。使用二进制域 $\mathbb{F_{2^k}}$。

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

Circle STARK 是在域 $\mathbb{F}=\mathbb{Z}/(2^k-1)\mathbb{Z}$ 上定义的, 其中 $2^k-1$ 是素数：即整数模一个梅森素数$2^k-1$。在二进制中, 该素数只是一个由 k 个1组成的串:

$2^k-1=1111...111_2$

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

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

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

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

$low=x \& MASK =x \ mod \ 2^{31} $ $high=x>>31=\lfloor x/2^{31} \rfloor$

我们可以将 x 表示为:

$x=low \ + \ 2^{31} \cdot high$

因此:

$x \equiv low +(2^{31}\ mod\ (2^{31}-1)) \cdot high\ mod\ 2^{31}-1$

因为 $2^{31}\ mod\ (2^{31}-1)$ , 我们有:

$x \equiv low + high\ mod\ 2^{31}-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 位梅森素数$2^{61}-1$ , 它是适用 64 位整数的最大梅森素数, 并应用类似的技术。

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

梅森素数的问题

通常, 在设计 STARK 时, 我们有许多可能的（素数）域 $\mathbb{F}$ 可以选择, 并且我们可以选择一个具有平滑乘法子群的域。一种方法是选择 n 使得 $p=2^m+n \cdot 2^k+1$为质数, 那么该域将具有阶为 $2^k$的平滑子群，因为 $2^k|p-1$ 。例如, ethSTARK 的素数 $p=2^{61}+20 \cdot 2^{32}+1$ 有n=20 , 仅仅因为它是使 p 成为素数的最小的 n>0 。

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

$| \mathbb{F}^*_{2^{31}-1}| = 2^{31}-1=2 \cdot 3^2 \cdot 7 \cdot 11 \cdot 31 \cdot 151 \cdot 331$

看不到 2 的大幂:(

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