探索Circle STARKs

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

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

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

使用小字段的常见问题

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

为防止攻击,我们需要在攻击者提供多项式后再选择随机点。在较小字段的STARKs中,可选的随机点只有约20亿个,对下定决心的攻击者来说并不安全。

解决方案有两个:

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

多次检查简单有效,但存在效率问题。扩展字段类似于复数,但基于有限域。这允许我们在更大的域中操作,提高安全性。

Regular FRI

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

FRI使用二对一映射将数据集大小减半。这种映射是可重复的,允许我们持续减少数据集大小。

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只要求将多项式作为评估值存储。唯一需要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. 查找参数

关键是充分利用计算跟踪中的空间。2^31大小的字段减少了浪费空间。

结论

Circle STARKs对开发者来说并不比常规STARKs复杂。其背后的数学虽然复杂,但对开发者来说基本是隐藏的。

理解Circle FRI和FFTs可以作为理解其他特殊FFTs的途径。

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

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