探索Circle STARKs

近年来，STARKs协议设计的趋势是转向使用较小的字段。最早期的STARKs实现使用256位字段,但这种设计效率较低。为解决这个问题,STARKs开始使用更小的字段,如Goldilocks、Mersenne31和BabyBear。

这种转变大幅提升了证明速度。例如,Starkware能在M3笔记本上每秒证明620,000个Poseidon2哈希值。这意味着只要信任Poseidon2作为哈希函数,就可以解决开发高效ZK-EVM的难题。

本文将探讨这些技术的工作原理,特别关注Circle STARKs这种与Mersenne31字段兼容的方案。

使用小字段的常见问题

在创建基于哈希的证明时,一个重要技巧是通过对多项式在随机点的评估来间接验证多项式的性质。这大大简化了证明过程。

为防止攻击,我们需要在攻击者提供多项式后再选择随机点。在大字段中,可以简单选择256位随机数。但在小字段中,可选值太少,容易被攻击者穷举。

有两种解决方案:

1. 进行多次随机检查
2. 扩展字段

多次检查简单有效,但效率较低。扩展字段类似复数,允许在有限域上进行更复杂的运算。这提高了安全性,同时保留了小字段的高效性。

Circle FRI

Circle STARKs的巧妙之处在于,给定质数p,可以找到大小为p的群,具有类似的二对一特性。这个群由满足特定条件的点组成,如x^2 mod p等于某值的点集。

这些点遵循一种加法规律: (x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1)

双倍形式是: 2 * (x,y) = (2x^2 - 1, 2xy)

Circle FRI将所有点收敛到一条直线上,然后进行随机线性组合,得到一维多项式P(x)。

从第二轮开始,映射变为: f0(2x^2-1) = (F(x) + F(-x)) / 2

这个映射每次将集合大小减半,将圆上两个相对点的x坐标转换为倍增后点的x坐标。

Circle FFTs

Circle group也支持FFT,构造方式与FRI类似。一个关键区别是,Circle FFT处理的不是严格意义上的多项式,而是Riemann-Roch空间。

作为开发者,几乎可以忽略这一点。STARKs只需将多项式作为评估值集合存储。唯一需要FFT的地方是进行低度扩展。

商运算

在STARK中,常见的操作是对特定点进行商运算。在circle group中,由于没有单一点的线性函数,需要采用不同技巧。

我们不得不在两个点上进行评估来证明,从而添加一个不需关注的虚拟点。

消失多项式

在circle STARK中,相应的消失多项式函数是:

Z1(x,y) = y Z2(x,y) = x
Zn+1(x,y) = (2 * Zn(x,y)^2) - 1

反向位序

Circle STARKs需要调整反向位序以反映其折叠结构。我们需要反转除最后一位外的每一位,用最后一位决定是否翻转其他位。

效率

Circle STARKs非常高效。一个被证明的计算通常涉及:

1. 用于业务逻辑的原生算术
2. 用于加密的原生算术
3. 查找参数

效率的关键是充分利用计算跟踪中的空间。Circle STARKs在2^31大小的字段中浪费的空间较少。

结论

Circle STARKs对开发者来说并不比常规STARKs复杂。虽然背后的数学很复杂,但这种复杂性被很好地隐藏了。

结合Mersenne31、BabyBear和Binius等技术,我们正接近STARKs基础层的效率极限。未来的优化方向可能包括:

• 最大化哈希函数等原语的效率
• 递归构造以提高并行性
• 算术化虚拟机以改善开发体验