深入探索Circle STARKs

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

使用小字段可以大幅提升证明速度。例如,Starkware能在M3笔记本上每秒证明62万个Poseidon2哈希。这意味着只要信任Poseidon2作为哈希函数,就可以解决高效ZK-EVM的难题。

但使用小字段也带来了一些挑战,如何在有限的字段大小下保证安全性。Circle STARKs方案提供了一种创新的解决方案,它利用了圆群的特殊性质来构造高效安全的证明系统。

本文将深入探讨Circle STARKs的原理和实现细节,包括:

• 小字段STARKs面临的主要挑战
• Circle FRI的基本原理
• Circle FFTs的实现
• Circle STARKs中的商运算和消失多项式
• 反向位序的调整
• Circle STARKs的效率分析

通过这些技术细节的讨论,我们可以更好地理解Circle STARKs的创新之处,以及它在提升STARKs效率方面的重要贡献。

使用小字段的挑战

在基于椭圆曲线的协议中,我们可以选择一个随机的256位数作为验证参数。但在小字段STARKs中,可选择的参数范围大大缩小,容易被攻击者穷举。

有两种解决方案:

1. 进行多次随机检查:在多个随机坐标上重复验证。这种方法简单有效,但会降低效率。

2. 扩展字段:引入新的数学结构来扩大可选值的范围。例如在Mersenne31字段上,我们可以定义α使得α^2=某个特定值,从而构造出更大的字段。

扩展字段主要用于FRI协议等需要随机线性组合的场景。大部分运算仍在基础字段上进行,保留了小字段的高效性。

Circle FRI的原理

Circle STARKs的核心创新在于Circle FRI。给定一个素数p,我们可以构造一个大小为p的群,该群具有类似二对一映射的特性。

这个群由满足x^2 mod p等于某个特定值的点集组成。这些点遵循一种特殊的加法规则:

(x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1)

双倍点公式为:

2 * (x,y) = (2x^2 - 1, 2xy)

Circle FRI首先将所有点收敛到一条直线上:

f0(x) = (F(x,y) + F(x,-y))/2

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

从第二轮开始,映射变为:

f0(2x^2-1) = (F(x) + F(-x))/2

这个映射每次都将点集大小减半,实现了类似常规FRI的效果。

Circle FFTs

Circle群也支持FFT操作,构造方式与Circle FRI类似。一个关键区别是Circle FFT处理的不是严格意义上的多项式,而是所谓的Riemann-Roch空间。

这意味着Circle FFT的输出系数并不像常规FFT那样是单项式,而是特定于Circle FFT的基函数。

作为开发者,我们可以忽略这些数学细节。只需将多项式存储为一组评估值,使用FFT进行低度扩展即可。

商运算和消失多项式

在Circle STARKs中,由于没有单一点的线性函数,需要采用不同的商运算技巧。我们通过在两个点上进行评估来证明,添加一个虚拟点。

消失多项式也需要相应调整。在Circle STARKs中,消失多项式的形式为:

Z1(x,y) = y Z2(x,y) = x
Zn+1(x,y) = (2 * Zn(x,y)^2) - 1

反向位序的调整

为了适应Circle FRI的折叠结构,需要调整反向位序。基本思路是反转除最后一位外的每一位,用最后一位决定是否翻转其他位。

效率分析

Circle STARKs在31位素数字段上非常高效。它充分利用了字段空间,减少了浪费。相比大字段SNARKs,Circle STARKs在业务逻辑和查找表方面更有优势。

Binius等方案通过混合不同大小的字段实现了更高的效率,但增加了复杂度。Circle STARKs在概念上更简单。

结论

Circle STARKs为开发者提供了一种高效且相对简单的STARKs实现方案。它巧妙地利用了圆群的特性,在保持安全性的同时显著提升了效率。

未来STARKs的优化方向可能包括:

• 最大化哈希函数等基础密码原语的效率
• 通过递归构造实现更多并行化
• 改进虚拟机的算术化以提升开发体验

总的来说,Circle STARKs是STARKs技术发展中的一个重要里程碑,为构建更高效的零知识证明系统提供了新的思路。