探索Circle STARKs

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

这种转变提升了证明速度。例如Starkware能在M3笔记本上每秒证明620,000个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位字段中很简单:选择随机256位数字即可。但在小字段中,可选的r值只有约20亿种,攻击者虽然工作量很大但仍可能尝试所有可能。

有两个解决方案:

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

多次检查简单有效,但存在效率问题。扩展字段类似复数,但基于有限域。引入新值α满足某关系,如α^2=某值。这创建了新的数学结构,可在有限域上进行更复杂运算。扩展域仅在需要随机线性组合时使用,大部分运算仍在基础字段进行。

常规FRI

构建SNARK或STARK的第一步是将计算问题转化为多项式方程P(X,Y,Z)=0。解决方案需证明提出的值是合理的多项式,且度数有限。这通过逐步应用随机线性组合实现:

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隔离A的偶数系数,C隔离奇数系数。给定B和C可恢复A:A(x) = B(x^2) + xC(x^2)。如果A度数<2^20,B和C的度数分别为A的度数和A度数-1。D作为随机组合,度数应为A的度数。

FRI通过将证明多项式度数为d简化为证明度数为d/2来简化验证。这个过程可重复多次,每次将问题简化一半。如果某阶段输出不符合预期度数,那一轮检查将失败。

FRI每步将多项式次数和点集规模减半。前者是FRI工作的关键,后者使算法运行极快:总计算成本是O(N)而非O(N*log(N))。

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

BabyBear的模数使其最大乘法子群包含所有非零值,大小为2^k-1。这非常适合上述技术,可通过重复映射有效减少多项式度数。Mersenne31的乘法子群大小为2^31-1,只能除以2一次,之后无法使用该技术。

Mersenne31域非常适合32位CPU/GPU运算。其模数特性(如2^31-1)使许多运算可利用高效位操作:超过模数的结果可通过位移减小。乘法可用特定CPU指令高效处理。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)是点倍增法则。我们将圆上两个相对点的x坐标转换为倍增后点的x坐标。

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中,由于没有通过单点的线性函数,需要不同技巧。可以构造切线函数,但它在点上具有重数2。因此必须在两点上评估来证明。

如果P在x1处等于y1,在x2处等于y2,我们选择插值函数L在这两点相等。然后证明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

反向位序

STARKs中多项式评估通常按反向位序排列。在circle STARKs中,折叠结构略有不同:

• 第一步:(x,y)与(x,-y)配对
• 第二步:x与-x配对
• 后续步骤:p与q配对,使Q^i(p) = -Q^i(q)

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

效率

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

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

效率关键在于充分利用计算跟踪空间。这里字段大小为2^31,浪费空间不大。Poseidon等哈希在任何字段中都充分利用每个数字的每一位。

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

结论

Circle STARKs对开发者而言并不比STARKs复杂。实现中与常规FRI的主要区别在于上述三个问题。尽管背后数学复杂,但这种复杂性被很好地隐藏。

理解Circle FRI和FFTs可以成为理解其他特殊FFTs的途径,如二进制域FFTs和椭圆曲线FFTs。

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

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