你应该关注RC-STARKs的原因

为什么你应该关注 RC-STARKs

作者：[Omer Shlomovits](https://x.com/Omer Shlomovits)

本文友好地介绍了我们的新论文：“应用于 STARKs 的真正复杂代码”，作者是 @Yuval_Domb。

介绍：我阅读研究的秘密策略

十多年来，我一直在研究密码学研究论文。很长一段时间，我都有一个习惯：为了真正掌握一篇论文，我会读三遍。第一遍只是为了了解情况——浏览主要结果并理解结构。第二遍更彻底；我会深入研究引言，并确保我理解所有关键结构。第三次阅读是最耗时的——一切都关于学习证明技术、原语及其安全定义。

但总有例外。有些论文是杰作；有些仅仅是很酷。有些我甚至能背诵（向 L17 致敬）。但最近，我的注意力不如以前了。通常我只有时间快速浏览一下，然后才能决定任何行动项目。周末是我进行更深入研究的时间——第二遍和第三遍——但我选择的论文更多是为了精神食粮。我想我已经获得了足够的经验，可以专注于对我来说最重要的部分，并提取我需要的知识。

近年来，我为我的阅读习惯增加了一个新的转折，这使它变得更加有趣。每当我阅读一篇论文时，我都会尝试逆向工程作者的旅程：这篇论文是如何产生的？像思考一个神秘小说一样，我问自己这样的问题：这里真正的发现是什么？为什么以前没有人想到这一点——为什么是现在？为什么是这个特定的作者而不是其他人？为什么结果以这种特定方式呈现？缺少哪些结果？等等……

回答这些问题可以帮助我更轻松地浏览那些厚重的 40 页或 50 页的论文。通常，一篇论文的“核心”归结为一个非常具体的想法。通常，这个想法很简单，其余的工作是证明它，或者以一种提供更完整的系统或故事的方式来包装它。例如，一篇关于使用多方计算 (MPC) 运行零知识证明者的论文，可能归结为一个关于如何在两方之间高效地划分多标量乘法 (MSM) 原语的巧妙技巧。其余的大多是重复已知的结果，以确保完整的 ZK 协议可以在相同的 MPC 设置中运行。

进入作者的脑海是一门艺术，但当它奏效时，它会将一篇论文变成一个故事——反映了作者在完成作品的旅程中所经历的挣扎和胜利。我相信好的论文应该以这种叙事方式来撰写。

我对 Circle STARK 论文的理解

STARKs 非常强大。

具有 31 位的梅森素数，通常被称为 M31，具有使其特别有吸引力的独特属性。但是，使用 M31 作为 STARKs 的基域效率不高，因为 M31 的 2-adicity 低，这意味着我们不能直接使用快速傅里叶变换 (FFT)——而 FFT 对于 STARK 在低阶扩展 (LDE) 和 Reed-Solomon (RS) 代码评估等领域的表现至关重要。

Circle STARK 论文的作者试图解决这个问题。他们想要一种类似于 FFT 的变换，它从 M31 域获取元素，并输出相同域中的元素。他们的第一个关键观察是，虽然 M31 没有足够高的 2 阶，但它的第一个域扩展有。本文的其余部分致力于开发所需的类 FFT 变换。最终结果是一种新的变换，具有基本的 2:1 折叠属性，使 STARKs 能够在 M31 上工作并实现显着的效率提升。本文涉及一些非常复杂的数学运算来完成这一新颖的结果。

到目前为止，一切都好，那又如何

但问题是：新的变换类似于 FFT，但它不是我们所知和喜爱的 FFT。例如，我们还不知道是否有办法支持大于 2 的基数。当我们在硬件中实现 FFT 时，我们依赖于更高阶的基数，因为它们可以帮助我们节省内存——这是我们始终试图避免的 FFT 瓶颈。

Yuval 的论文讲述了一个不同的故事。Yuval 是我们关于 NTT 的教科书的主要作者，他的工作感觉就像直接从那本书中摘取了几页。他的论文没有提出一个新颖的想法；相反，它基于已经存在了几十年的概念构建了一个 FFT。本质上，本文提出了一个复数域上的 FFT。主要的突破是识别问题中的正确对称性，允许评估（或系数）来自实数——在这种情况下，是 M31 的元素。

这导致可以直接集成到 STARK 系统中，几乎一对一地替换 Circle STARK 变换。复杂度与 Circle STARK 方法大致相同，但现在我们可以立即利用现有的硬件优化来实现高效的内存管理，这要归功于过去 50 年来在 FFT 上投入的大量工作。

为了增加一些色彩，下表摘自论文，显示了 Circle STARK（左列）的乘法次数与我们的 FFT（最右列)的乘法次数相当。有关完整分析，请参阅论文中的第 6 节。

重要提示：我过于简化了从我们新的 RC 代码到像 Stwo 这样的全面生产就绪的 STARK 所需的过程。我也低估了 Yuval 作品中的天才之处。我的目标只是为了说明一个观点❤️。

结论

在他的书 《臭鼬工厂：个人回忆录》 中，本·里奇引用他的前辈凯利·约翰逊的话说，“外形美观的飞机飞起来也很漂亮。”这句话捕捉到一个深刻的真理：空气动力学服从物理定律。物理学描述自然，并通过数学编码。数学是优雅的，飞机也是如此。科学也是如此。想想麦克斯韦方程组的优雅性。FFT 是另一个例子——它通常是任何算法课程或书籍中教授的第一个算法。它具有一定的美感并且非常强大。 我们的工作并非开创性的，Circle STARK 才是。我们的工作是有效的：我们利用问题中的对称性，即使在 M31 引入的挑战下，也能保持 STARK 的优雅。

当我说这值得你关注时，我的意思是它以最完美的方式体现了我们在这里所做的事情：ZK。有效。

毋庸置疑，这项工作离不开 @StarkWareLtd 和 @StarknetFndn 的支持。

关注 Ingonyama

Twitter: https://twitter.com/Ingo_zk

YouTube: https://www.youtube.com/@ingo_zk

GitHub: https://github.com/ingonyama-zk

LinkedIn: https://www.linkedin.com/company/ingonyama

加入我们: https://www.ingonyama.com/career

• 原文链接： medium.com/@ingonyama/wh...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～