探索Circle STARKs

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

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

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

使用较小数学字段的常见问题

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

为防止攻击,我们需要在攻击者提供多项式后再选择随机点。在较小字段的STARKs中,可选择的随机值数量有限,这给安全性带来挑战。

解决方案有两个:

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

扩展字段类似于复数,但基于有限域。通过引入新值α,我们创建了一个新的数学结构,能在有限域上进行更复杂的运算。这种扩展允许我们有更多的值选择,从而提高安全性。

Circle FRI

Circle STARKs的巧妙之处在于,给定质数p,可以找到大小为p的群体,具有类似二对一特性。这个群体由满足特定条件的点组成,遵循一种加法规律。

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

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

这个映射每次将集合大小减少一半。每个x代表两个点:(x,y)和(x,-y)。(x → 2x^2 - 1)就是点倍增法则。

Circle FFTs

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

作为开发者,您几乎可以完全忽略这一点。STARKs从不要求您了解系数。您只需将多项式作为在特定域上的一组评估值进行存储。

Quotienting

在circle group的STARK协议中,由于没有可以通过单一点的线性函数,需要采用不同技巧来替代传统的商运算方法。我们不得不通过在两个点上进行评估来证明,从而添加一个不需要关注的虚拟点。

Vanishing polynomials

在圆形STARK中,消失多项式函数是:

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

Reverse bit order

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

效率

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

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

效率的关键是充分利用计算跟踪中的整个空间进行有用工作。Circle STARKs在这方面表现良好。

结论

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

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

1. 对哈希函数和签名等进行最大化效率的算术化
2. 进行递归构造以启用更多并行化
3. 算术化虚拟机以改善开发者体验