ZK-EVM提速：Circle STARKs核心技术解析

探索 Circle STARKs：构建高效 ZK-EVM 的基石

本文深入探讨了 Circle STARKs 的构造，并阐述了其在构建高效零知识以太坊虚拟机（ZK-EVM）中的应用。我们将解析密码学证明在多项式领域上的应用，并讨论圆形快速傅里叶变换（FFT）和哈希函数等关键技术，力求为读者带来对这一构造的深刻理解。

在开始之前，我们假设你已经熟悉 SNARK 和 STARK 的基本原理。如果你对此还不太了解，建议先阅读相关资料。特别感谢 Eli ben-Sasson、Shahar Papini、Avihu Levy 以及 Starkware 团队的其他成员，感谢他们提供的反馈和讨论。

• Vitalik 关于 Binius 的文章
• Karatsuba 算法
• Polygon Plonky2 的深入解析
• 零知识证明的小域应用

这种转变已经显著提升了证明速度。最引人注目的是，Starkware 能够在 M3 笔记本电脑上每秒证明 620,000 个 Poseidon2 哈希。这意味着，只要我们信任 Poseidon2 哈希函数，构建高效 ZK-EVM 的最困难部分之一就已经得到了有效解决。但是，这些技术是如何运作的？密码学证明（通常需要大整数来保证安全性）是如何在这些域上构建的？这些协议与更奇特的构造（例如 Binius）又该如何比较？本文将探讨其中的一些细微差别，特别关注一种称为 Circle STARKs 的构造（在 Starkware 的 stwo、Polygon 的 plonky3 和我自己的 Python 实现中都有实现），它具有一些独特的性质，旨在与高效的 Mersenne31 域兼容。

小域常见的问题

在进行基于哈希的证明（或实际上任何类型的证明）时，最重要的“技巧”之一是用证明有关多项式在随机点的求值来代替证明有关底层多项式的事情。

• Fiat-Shamir 启发法

这个问题有两个自然的解决方案：

• 执行多次随机检验
• 扩域

def multiply_complex(x, y, modulus): real_part = (x[0] * y[0] - x[1] * y[1]) % modulus imaginary_part = (x[0] * y[1] + x[1] * y[0]) % modulus return (real_part, imaginary_part)

这里实现不是最优的（可以用 Karatsuba 优化），只是展示原理。

常规 FRI

• FRI 协议

Circle FRI

• Eli Ben-Sasson 论 Circle STARK 的优势

这些点遵循加法律。如果你最近学过三角学或复数乘法，你可能会觉得这个定律很熟悉：

• 复数乘法的代数

从第二轮往后，映射改变：

Circle FFTs

• Vitalik 论 FFT
• 椭圆曲线快速傅里叶变换 (ECFFT)

从这里开始，让我们来了解一些更深奥的细节。对于实现 Circle STARK 的人来说，与常规 STARK 相比，这些细节会有所不同。

取商

• 商多项式

消失多项式

反转比特序

效率

因此，Circle STARK 实际上非常接近最优了！Binius 甚至更强大，因为它允许混合搭配不同大小的域，从而为所有东西给出更高效的位打包。Binius 还提供了执行 32 比特加法的选项，且无需产生查找表的开销。然而，这些收益是以（在我看来）显著更高的理论复杂性为代价的，而 Circle STARK（以及基于 BabyBear 的常规 STARK）在概念上是相当简单的。

结论：我对 Circle STARKs 怎么看？

与常规 STARK 相比，Circle STARK 并不会给开发者带来太多额外的复杂性。在实现的过程中，上述三个问题基本上就是我看到的与常规 FRI 相比的唯一区别。Circle FRI 所操作的“多项式”背后的数学原理是相当反直觉的，需要一段时间才能理解和领悟。但恰好这种复杂性被隐藏起来了，使得开发者不会看到太多。Circle 数学的复杂性是封装过的，而不是系统性的。

理解 Circle FRI 和 Circle FFT 还是理解其他“奇异 FFT”的良好智力途径：最值得注意的是二进制域 FFT，之前在 Binius 和 LibSTARK 中使用，还有更奇特的构造，如椭圆曲线 FFT，其使用几对一映射，可以很好地与椭圆曲线点运算配合使用。

通过结合 Mersenne31、BabyBear 和二进制域技术（比如 Binius），我们确实感觉得到正在接近 STARK“基础层”效率的极限。在这个时间点，我预计 STARK 优化的前沿将转向对哈希函数和签名等原语进行最高效的算术化（并为此目的优化这些原语本身）、进行递归构造以解锁更多并行化、对虚拟机进行算术化以提升开发者体验，以及其他上层任务。