本文是关于 Circle STARKs 系列的第一篇文章,主要介绍了 Mersenne 素数域在 STARK 中的应用动机和背景。由于 Mersenne 素数域具有非常高效的模约简算法,但在传统 STARK 中无法有效支持 FRI/STIR,Circle STARKs 解决了这个问题,使得在这些特定域上使用 STARK 更高效。
在零知识证明系统中,我们(几乎)总是在一个有限域上进行运算,并且因为证明者通常需要进行大量的域运算来生成证明,所以我们自然希望我们的域运算尽可能地快。使用椭圆曲线密码学时,我们被限制在“密码学大小”的域中,例如,对于 128 位的安全性,大约为 256 位。然而,类似 STARK 的技术 (Reed-Solomon IOPs) 在安全参数和域大小之间没有这种直接的依赖关系。 因此,我们可以使用小得多的域。
通过这样做,我们可以使用具有非常高效算术的域,例如小的二元域或小的素数域(考虑 32 位或 64 位)。 一些最快的这种域是小的梅森素数域,它们具有非常简单的模约简。
不幸的是,直到最近,这些域的结构使得它们不适合 STARK,因为它们不能有效地容纳 FRI/STIR。 现在这种情况已经改变了。 这是由 Haböck, Levit 和 Papini 提出的 Circle STARKs 的四部分系列的开端,它使能够使用这些特定域,以更高的效率用于 STARK。 该系列将结构如下:
这篇文章的目的不是解释 FRI 的一般工作原理,为此,我推荐 这篇博文 或 这篇,尽管我们将在本系列的未来部分中介绍 Circle FRI 和 Circle STARK。 现在,只要知道要实例化 FRI(和 STARK),你需要:
它可以通过 F 上的(小次数)多项式/有理函数来计算。
每个都可以表示为 F 上的(小次数)多项式/有理函数。
同态定义了一个越来越小的光滑群序列 Li=ϕi(Li−1):
L0L1=ϕ1(L0)L2=ϕ2(ϕ1(L0))⋮Lk=ϕk(ϕk−1(…ϕ1(L0)…))
以下是可能的 FRI 实例化的简要概述:
1) 光滑乘法子群
当 F 的乘法子群 F∗ 是光滑的时可用:2k||F∗|
\ 前两组技术已被广泛部署,例如由以下团队:\ \
#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 助手,为大家转译优秀英文文章,如有翻译不通的地方,还请包涵~
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!