探索Circle STARKs

Circle STARKs是一种新型的STARK证明系统,它利用了圆群的特殊性质来构建高效的证明。本文将探讨Circle STARKs的工作原理及其优势。

背景

近年来,STARKs协议设计趋向使用较小的数学字段,如Goldilocks、Mersenne31和BabyBear等。这种转变大大提升了证明速度,例如Starkware能在M3笔记本上每秒证明62万个Poseidon2哈希。

但使用小字段也带来了一些挑战,如何在有限的随机性空间内保证安全性。Circle STARKs通过巧妙的设计解决了这一问题。

Circle STARKs的核心原理

Circle STARKs的核心思想是利用圆群的二对一映射性质。给定一个质数p,我们可以找到一个大小为p的群,该群具有类似的二对一特性。这个群由所有满足x^2 + y^2 = 1 mod p的点(x,y)组成。

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

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

利用这种映射,我们可以构造出类似FRI的证明系统,但在更小的字段上工作。

Circle FFTs

Circle群还支持FFT运算,但处理的对象不是严格意义上的多项式,而是所谓的Riemann-Roch空间。这意味着我们将x^2 + y^2 - 1的任何倍数视为零。

这导致Circle FFT输出的系数不同于常规FFT,而是基于特定的基{1, y, x, xy, 2x^2 - 1, ...}。但作为开发者,我们几乎可以完全忽略这一点,只需将多项式作为评估值集合来处理即可。

Circle STARKs的特殊技巧

商运算

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

消失多项式

Circle STARKs中的消失多项式形式为:

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

反向位序

为了适应Circle STARKs的特殊折叠结构,我们需要调整反向位序。具体方法是反转除了最后一位的每一位,并用最后一位决定是否翻转其他位。

Circle STARKs的效率

Circle STARKs在31位素数字段上工作,比大字段STARKs更高效。它充分利用了字段空间,减少了空闲空间的浪费。虽然Binius等方案在某些方面更优,但Circle STARKs概念更简单。

结论

Circle STARKs为开发者提供了一种概念简单但高效的STARK变体。它很好地平衡了效率和易用性,是STARK技术发展的重要一步。未来STARK优化可能会集中在以下方向:

1. 最大化哈希函数等基础密码原语的算术化效率
2. 通过递归构造提高并行化
3. 改进虚拟机算术化以优化开发者体验

Circle STARKs的出现为我们提供了一个理解和探索更多特殊FFT技术的窗口,推动了STARK技术向更高效和实用的方向发展。