探索Circle STARKs

近年来，STARKs协议设计趋向使用较小的字段。最早期的STARKs实现使用256位字段,与基于椭圆曲线的签名兼容。但这种设计效率较低,处理大数字会浪费算力。为解决这个问题,STARKs开始转向使用更小的字段:首先是Goldilocks,然后是Mersenne31和BabyBear。

这种转变提升了证明速度。例如Starkware能在M3笔记本上每秒证明620,000个Poseidon2哈希值。只要我们信任Poseidon2作为哈希函数,就可以解决开发高效ZK-EVM的难题。那么这些技术如何工作?这些证明如何在较小字段上建立?本文将探讨这些细节,特别关注Circle STARKs方案。

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

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

例如,假设要求生成多项式A的commitment,必须满足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位数。但在较小字段的STARKs中,只有约20亿个r值可选,攻击者可能通过穷举破解。

解决方案有两个:

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

多次随机检查简单有效,但存在效率问题。扩展域类似复数,但基于有限域。引入新值α,声明α^2=某值。这样可在有限域上进行更复杂运算。扩展域仅在FRI协议等场景中使用,大部分数学运算仍在基础字段进行。

常规FRI

构建SNARK或STARK时,第一步是算术化,将计算问题转化为多项式方程。要证明有解,需证明所提出值是合理的多项式且具有最大度数。为此使用逐步应用的随机线性组合技巧:

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

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

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

为实现域的逐步减少,使用二对一映射。这种映射允许将数据集大小减少一半,且是可重复的。从乘法子群开始,对集合S进行平方操作,新集合S^2保留同样属性。这允许持续减少数据集大小,直到最终只剩一个值。

BabyBear模数使其最大乘法子群包含所有非零值,子群大小为2k-1。可选择2^k大小的子群,然后应用FRI方法将多项式度数逐步减少到15。Mersenne31模数使乘法子群大小为2^31-1,只能被除以2一次,之后无法使用上述技术。

Mersenne31域适合32位CPU/GPU运算。其模数特性使许多运算可利用高效位操作完成。在Mersenne31域中,算术运算比BabyBear域快约1.3倍。如果能在Mersenne31域实现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空间:多项式模圆(x^2 + y^2 - 1 = 0)。

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

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

商运算

在STARK协议中,常见操作是对特定点进行商运算。例如,证明P(x)=y:

1. 计算商Q = (P - y)/(X - x)
2. 证明Q是多项式而非分数

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

如果多项式P在x1处等于y1,在x2处等于y2,选择插值函数L在x1处等于y1,在x2处等于y2: L = ((y2 - y1)/(x2 - x1)) * (x - x1) + y1

然后证明P - L在这两点为零,通过L除以L来证明商Q是多项式。

消失多项式

在STARK中,多项式方程通常形如C(P(x), P(next(x))) = Z(x) · H(x),Z(x)在整个评估域上为零。

在圆形STARK中,相应函数是: Z1(x,y) = y Z2(x,y) = x Zn+1(x,y) = (2 * Zn(x,y)^2) - 1

消失多项式可从折叠函数推导:常规STARK重复使用x → x^2,圆形STARK重复使用x → 2x^2 - 1。

反向位序

STARKs中,多项式评估通常按反向位序排列。例如n=16时: {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}

这种排序使FRI评估过程中早期分组的值在排序中相邻,节省空间。

在circle STARKs中,折叠结构略有不同。调整反向位序以反映这种结构,需反转除最后一位的每一位,用最后一位决定是否翻转其他位。

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

效率

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

1. 原生算术:用于业务逻辑
2. 原生算术:用于加密学
3. 查找参数:通用高效计算方法

效率关键在于充分利用计算跟踪空间。Circle STARKs字段大小为2^31,浪费空间较少。

Binius比Circle STARKs更好,允许混合不同大小字段,实现更高效位打包。但代价是概念更复杂,Circle STARKs概念相对简单。

结论

Circle STARKs对开发者并不比STARKs复杂。理解Circle FRI和Circle FFTs可作为理解其他特殊FFTs的途径。

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

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