探索Circle STARKs

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

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

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

使用小字段的常见问题

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

然而,在小字段上进行这种随机采样存在安全性问题。例如Mersenne31字段只有约20亿个可能的采样点,对于下定决心的攻击者来说是可行的。

有两种解决方案:

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

多次检查简单有效,但存在效率问题。扩展字段则可以提供更多的采样点选择,从而提高安全性。

常规FRI

FRI协议的第一步是将计算问题转化为多项式方程。然后证明提出的多项式解确实是合理的多项式,且具有一定的最大度数。

FRI通过逐步将证明多项式度数为d的问题简化为证明度数为d/2的问题来实现这一点。这个过程可以重复多次,每次将问题规模减半。

FRI的每一步都将多项式次数和点集规模减半。前者是FRI工作的关键,后者使算法运行速度极快。

Circle FRI

Circle STARKs的巧妙之处在于,它找到了一个大小为p的群,具有类似的二对一特性。这个群由满足特定条件的点组成。

从第二轮开始,映射发生变化:

f_0(2x^2-1) = (F(x) + F(-x))/2

这个映射每次都将点集大小减少一半。

Circle FFTs

Circle group也支持FFT,构造方式与FRI类似。但Circle FFT处理的对象并非严格的多项式,而是所谓的Riemann-Roch空间。

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

商运算

在Circle STARKs中,由于没有可以通过单点的线性函数,需要采用不同的技巧来替代传统的商运算方法。

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

消失多项式

在Circle STARKs中,消失多项式的形式为:

Z_1(x,y) = y Z_2(x,y) = x
Z_{n+1}(x,y) = (2 * Z_n(x,y)^2) - 1

逆位序

Circle STARKs中的逆位序需要调整以反映其特殊的折叠结构。具体来说,需要反转除最后一位外的每一位,并用最后一位决定是否翻转其他位。

效率

Circle STARKs非常高效。与大字段SNARKs相比,它们可以更充分地利用计算跟踪中的空间。

Binius在某些方面比Circle STARKs更好,但代价是概念更复杂。相比之下,Circle STARKs在概念上相对简单。

结论

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

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

1. 最大化哈希函数和签名的效率
2. 递归构造以提高并行性
3. 优化虚拟机以改善开发体验