探索Circle STARKs

近年来，STARKs协议设计趋势转向使用较小的字段。早期STARKs实现使用256位字段,与椭圆曲线签名兼容,但效率较低。为提升效率,STARKs开始使用更小的字段,如Goldilocks、Mersenne31和BabyBear。

这种转变显著提升了证明速度。例如Starkware能在M3笔记本上每秒证明62万个Poseidon2哈希。这意味着,只要信任Poseidon2作为哈希函数,就可以解决高效ZK-EVM的难题。本文将探讨这些技术的工作原理,特别关注Circle STARKs方案。

使用小字段的常见问题

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

例如,证明系统可能要求生成多项式A的承诺,满足A^3(x) + x - A(ωx) = x^N。协议可要求选择随机坐标r并证明A(r) + r - A(ωr) = r^N。

为防止攻击,需在攻击者提供A后再选择r。在256位字段中这很简单,但在小字段中只有约20亿种r可选,攻击者可能破解。

解决方案有两种:

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

多次检查简单有效,但可能需要增加轮数以提高安全性。扩展域类似复数,但基于有限域。通过引入新值α,创建更复杂的数学结构,提供更多选择。

Regular FRI

FRI协议的第一步是将计算问题转化为多项式方程P(X,Y,Z)=0。然后证明提出的值是合理的多项式,且度数有限。

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

Circle FRI

Circle STARKs的巧妙之处在于,对于质数p,可找到大小为p的群,具有类似二对一特性。这个群由满足特定条件的点组成,如x^2 mod p等于某值的点集。

这些点遵循加法规律:(x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1)

双倍形式为:2*(x,y) = (2x^2 - 1, 2xy)

Circle FRI的映射从第二轮开始变为: f0(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空间,而非严格多项式。

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

开发者几乎可以忽略这点,只需将多项式作为评估值集合存储。FFT主要用于低度扩展。

Quotienting

在circle group的STARK中,由于没有单点线性函数,需要采用不同技巧替代传统商运算。通常需要在两点上评估来证明,添加一个虚拟点。

Vanishing polynomials

Circle STARK中的消失多项式为: Z1(x,y) = y Z2(x,y) = x
Zn+1(x,y) = (2 * Zn(x,y)^2) - 1

Reverse bit order

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

效率

Circle STARKs非常高效,计算通常涉及:

1. 业务逻辑的原生算术
2. 密码学的原生算术(如Poseidon哈希)
3. 查找参数

2^31大小的字段减少了空间浪费。Binius在混合字段大小方面更优,但概念更复杂。

结论

Circle STARKs对开发者并不比STARKs复杂。理解其数学需要时间,但复杂性被很好地隐藏。

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

• 最大化哈希函数等的算术化效率
• 递归构造以提高并行化
• 算术化虚拟机以改善开发体验