Circle STARKs 系列(一):梅森素域

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

在零知识证明系统中,我们(几乎)总是在有限域上进行操作,并且由于证明者通常必须进行大量的域操作来生成证明,因此我们自然希望我们的域操作要尽可能快。如果使用椭圆曲线密码学,我们被限制在“密码学大小”的域,比如大约 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}$。

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

  3. 具有小(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 的大幂:(

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

点赞 1
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
XPTY
XPTY
江湖只有他的大名,没有他的介绍。