探索Circle STARKs

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

使用小字段可以大幅提升证明速度。例如Starkware能在M3笔记本上每秒证明62万个Poseidon2哈希。但小字段也带来了新的挑战,如何在有限的选择空间中保证安全性。

本文将探讨Circle STARKs,这是一种与Mersenne31字段兼容的新方案。Circle STARKs通过在圆上的点群上操作,解决了小字段带来的安全性问题。

Circle FRI

Circle FRI的核心思想是在圆上定义一个大小为p的点群,这个群具有二对一映射的性质。群中的点满足x^2 + y^2 = 1 (mod p)。

Circle FRI的映射过程如下:

1. 首先将所有点收敛到x轴上
2. 进行随机线性组合得到一维多项式P(x)
3. 从第二轮开始使用映射 f_0(2x^2-1) = (F(x) + F(-x))/2

这个过程每次将点集的大小减半,类似于常规FRI。

Circle FFTs

Circle群也支持FFT,其构造与Circle FRI类似。不同之处在于Circle FFT处理的不是严格意义上的多项式,而是Riemann-Roch空间。

Circle FFT的输出系数是特定于Circle FFT的基础:{1, y, x, xy, 2x^2 - 1, 2x^2y - y, ...}

作为开发者,可以忽略这些数学细节,只需将多项式存储为评估值集合即可。

其他技术细节

• Circle STARKs中的商运算需要在两个点上进行评估
• 消失多项式的构造方式不同
• 使用修改后的反向位序来适应Circle STARKs的折叠结构

效率

Circle STARKs在31位素数字段上非常高效:

• 充分利用了计算空间
• 适用于业务逻辑和加密计算
• 支持高效的查找表操作

相比之下,Binius方案在效率上略胜一筹,但概念更为复杂。

总结

Circle STARKs对开发者来说并不比常规STARKs复杂。它为小字段STARKs提供了一种优雅的解决方案,有望推动STARKs技术向更高效率发展。

未来STARKs的优化方向可能包括:

• 优化哈希函数等基础密码原语
• 使用递归构造提高并行性
• 改进虚拟机的算术化以提升开发体验