探索Circle STARKs

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

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

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

使用小字段的常见问题

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

为防止攻击,我们需要在攻击者提供多项式后再选择随机点。在较小字段的STARKs中,可选的随机值只有约20亿个,对于坚定的攻击者来说是可行的。

解决方案有两个:

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

进行多次检查简单有效,但存在效率问题。扩展字段类似复数,但基于有限域。这样可以在有限域上进行更复杂的运算,提高安全性。

Regular FRI

FRI协议通过将证明多项式度数为d的问题简化为证明度数为d/2的问题,来简化验证过程。这个过程可以重复多次,每次将问题简化一半。

FRI的工作原理是重复这个简化过程。如果某个阶段的输出不是预期的多项式度数,那么这一轮的检查将失败。

为实现域的逐步减少,使用了二对一映射。这种映射允许将数据集大小减半,同时保留相同属性。

Circle FRI

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

这些点遵循一种加法规律。从第二轮开始,映射发生变化。这个映射每次都将集合大小减半。

Circle FFTs

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

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

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对开发者来说并不比STARKs复杂。主要区别在于上述三个问题。尽管背后数学复杂,但这种复杂性被很好地隐藏了。

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

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