深入探索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) = c,证明Q = (A - c)/(X - r)是一个多项式。

为防止攻击,需要在攻击者提供A之后再选择r。在大字段协议中,可以选择随机256位数字作为r。但在小字段STARKs中,只有约20亿种r值可选,攻击者可以尝试所有可能。

这个问题有两个解决方案:

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

多次随机检查简单有效,但存在效率问题。扩展字段类似复数,但基于有限域。引入新值α满足α^2=某个值,创建新的数学结构。这允许我们有更多值选择,提高安全性。

Regular FRI

FRI协议的第一步通常是算术化,将计算问题转化为方程P(X,Y,Z)=0,其中P是多项式,X、Y、Z是参数。解决方程对应解决原问题。

要证明解的正确性,需证明提出的值是合理的多项式且具有最大度数。使用随机线性组合技巧:

• 假设有多项式A的评估值,要证明其度数<2^20
• 考虑B(x^2) = A(x) + A(-x), C(x^2) = (A(x) - A(-x))/x
• D是B和C的随机线性组合:D = B + rC

本质上B隔离偶数系数,C隔离奇数系数。B和C可恢复A。如果A度数<2^20,B和C的度数分别为A的度数和A度数-1。D作为随机组合,其度数应为A的度数。

FRI重复这个简化过程,每次将问题简化一半。这种设计有效检测不符合要求的输入。

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)

我们专注于圆上奇数位置的点,将所有点收敛到一条直线上: f0(x) = (F(x,y) + F(x,-y))/2

然后进行随机线性组合,得到一维多项式P(x)。

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

作为开发者,可以基本忽略这点。STARKs只需将多项式存储为评估值集。FFT主要用于低度扩展:给定N个值,生成k*N个同一多项式上的值。

Quotienting

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

如果多项式P在x1处等于y1,在x2处等于y2,选择插值函数L在这两点相等。然后证明P-L在两点为零,通过L除以得到商Q是多项式。

Vanishing polynomials

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

这可从折叠函数推导:重复使用x → 2x^2 - 1。

Reverse bit order

Circle STARKs中的反向位序需调整:反转除最后一位的每一位,用最后一位决定是否翻转其他位。

16大小的折叠反向位序为: {0, 15, 8, 7, 4, 11, 12, 3, 2, 13, 10, 5, 6, 9, 14, 1}

效率

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

1. 业务逻辑的原生算术
2. 密码学的原生算术
3. 查找参数

效率关键在于充分利用计算跟踪空间。31位素数字段减少了浪费。Binius混合不同大小字段效率更高,但概念更复杂。

结论

Circle STARKs对开发者并不复杂。理解背后数学需时间,但复杂性被很好隐藏。它也是理解其他特殊FFTs的途径。

目前STARKs基础层效率接近极限。未来优化方向可能包括:

• 最大化哈希函数等基本密码原语的效率
• 递归构造以增加并行化
• 算术化虚拟机以改善开发体验