Stwo：基于Circle STARK和M31的下一代STARK证明系统

1. 引言

StarkWare团队和Polygon Labs团队，历时数月，构造了基于Mersenne素数域M31的Circle STARK协议，通过使用M31 over a circle，可基于任意有限域构造高效STARKs，具体见2024年2月19日论文《Circle STARKs》。

基于Circle STARK协议，StarkWare团队开发了超快的证明系统：Stwo，大幅改进了现有Stone prover（见Stone Prover：StarkWare的STARK Prover）。

Stwo开源代码见：

• https://github.com/starkware-libs/stwo（Rust）

BabyBear域背景知识见：

• RISC Zero的Babybear域 及其 扩域
• 技术探秘：在RISC Zero中验证FHE——RISC Zero应用的DevOps（2）

Mersenne素数域M31背景知识见：

• Plonky3 Mersenne素数域的Reed-Solomon codes设计
• 基于circle group的Reed-Solomon codes

传统STARKs协议，其组成步骤要求代数结构：

• 需要一个素数域$p$，其$p-1$可被2的大幂整除。

即传统STARKs，其所使用的域内要有一个smooth order的cyclic group。
原因在于STARKs协议中有2大核心：

• FFT：使用FFT算法来高效插值点，并编写包含相邻行的约束。
• FRI

这就排除了许多尺寸较小的域，尽管这些域非常适合高效计算。如，Mersenne素数域M31，其$p=2^{31}-1$，而$p-1=2(2^{30}-1)$甚至不能被$4$整除。从而陷入僵局：

• 传统STARKs协议无法与M31结合使用

数年前，曾希望让STARKs协议适用于2种主流加密曲线：secp256k1 和 secp256r1。但这2条曲线也不满足上面的要求。为此，还研究出了Elliptic Curve Fast Fourier Transform (ECFFT) Part I: Fast Polynomial Algorithms over all Finite Fields论文，其使用椭圆曲线为FFT和FRI提供了替代的结构源，在该论文中，详细介绍了将STARKs用于任意域的机制——使用某椭圆曲线的cyclic group。

为能让M31与STARKs结合使用，StarkWare团队和Polygon Labs团队合作，最终有了Circle STARKs：

• 一种紧凑、优雅的协议，避免了ECFFT论文的重型机制。
• 简而言之：当$p+1$可被2的大幂整除时（如M31），基于该素数域的circle curve（$x^2+y^2=1$）提供了适于FFT和FRI所需的结构。

2. Stwo：基于Circle STARK和M31的下一代STARK证明系统

Stwo：

• 利用 Circle STARK 和各种其他优化来带来前所未有的证明性能。

Stone（为St-one）为一代，而Stwo（S-two）为二代。已基于Stone系统构建的应用链和Starknet，都不受影响，高级Cairo将与Stwo完全兼容。当时机到来时，Stwo 已准备好推出，Starknet 生态系统（即用户和开发人员）将受益于 Stwo 的下一级别的扩展，而无需执行任何操作！Stwo 将与编写合约的高级Cairo代码兼容，也与Sierra兼容。当前基于Stone的Starknet prover(s)，未来将使用Stwo。用户/构建者/dapp 也将在延迟和费用方面受益。

3. 性能对比

在《Circle STARKs》论文中，对基于M31的Circle STARKs，和，基于Babybear域的传统STARK（使用的Babybear代码为https://github.com/Plonky3/Plonky3/commit/86d13ddf269427c4788cdd41f413308a6050f9f3）做了性能对比，要快约1.4倍：

参考资料

[1] StarkWare 2024年3月博客 Stwo Prover: the next-gen of STARK scaling is here
[2] 2024年2月21日 Circle STARKs