以太坊 - 递归STARKs

递归 STARKs

首个通用计算的递归证明，现已在以太坊主网上线

TL;DR（太长不看版）

• 递归证明已在主网上线，通过单个证明扩展 StarkEx 应用以及 StarkNet
• 它提升了规模，并在成本和延迟方面带来了好处（规模和延迟同步移动，而非权衡取舍，这种情况罕见且令人兴奋）
• 它为 L3 和其他好处奠定了基础
• 去阅读关于递归证明的博文。它很酷 😉

扩大规模！

由 Cairo 的通用计算驱动的递归证明现已投入生产。这标志着 STARKs 的 L2 扩展能力得到了大幅提升。它将迅速成倍增加可以通过单个证明写入以太坊的交易数量。

到目前为止，STARK 扩展的工作原理是将成千上万甚至数十万笔交易“汇总”成一个证明，然后将其写入以太坊。通过递归，可以将多个这样的证明“汇总”成一个证明。

此方法现在已在众多基于 Cairo 的应用程序中投入生产：在 StarkEx（StarkWare 的 SaaS 扩展引擎）和 StarkNet（无需许可的 Rollup）上运行的应用程序。

故事到目前为止

自 2020 年 3 月在主网上进行首次证明以来，以下发展塑造了 STARKs 的使用方式。

基于 STARK 的扩展

2020 年 6 月，首个基于 STARK 的扩展解决方案——StarkEx——在以太坊主网上部署。StarkEx 有一个 Prover（证明者），可在链下执行大型计算并生成 STARK 证明以验证其正确性，还有一个 Verifier（验证者），可在链上验证此证明。此首次部署的约束由 StarkWare 的工程师“手动编写”，从而大大限制了 StarkEx 的功能速度。我们得出结论，需要一种编程语言来支持通用计算证明——Cairo。

Cairo

2020 年夏天，Cairo 首次在以太坊主网上亮相。Cairo 代表 CPU Algebraic Intermediate Representation (AIR)，其中包括一个 AIR，用于验证此“CPU”的指令集。它为编码更复杂的业务逻辑证明、任意计算语句以及以更快、更安全的方式这样做打开了大门。Cairo 程序可以证明单个应用程序逻辑的执行。但是 Cairo 程序也可以是多个此类应用程序的串联——SHARP。

SHARP

SHARP——一个共享证明器——从多个独立的应用程序获取交易，并在一个 STARK 证明中证明它们。应用程序将其批处理交易组合在一起，更快地填满 STARK 证明的容量。交易以更高的速率和更低的延迟处理。下一个前沿：递归证明，但不仅仅是针对某些硬编码逻辑，而是针对通用计算。

要了解递归证明的全部好处，值得更多地了解 SHARP 到目前为止是如何执行（非递归）证明的。图 1 描绘了一个典型的非递归流程：

图 1：典型的非递归证明流程

在此，语句随时间到达。当达到某个容量（或时间）阈值时，将生成一个大的组合语句（又名 Train）。仅当收到所有单独的语句后，才证明此组合语句。此证明需要很长时间才能证明（大致等于单独证明每个语句所花费的时间之和）。

证明非常大的语句最终会受到可用计算资源（如内存）的限制。在递归之前，这实际上是 STARK 证明的限制性可扩展性障碍。

什么是递归证明？

使用 STARK 证明，证明语句所需的时间与执行语句所需的时间大致呈线性关系。此外，如果证明一个语句花费 T 时间，则验证证明花费的时间约为 log(T) 时间，这通常称为“对数压缩”。换句话说，使用 STARKs，验证语句所花费的时间比计算语句所花费的时间要少得多。

Cairo 允许表达可由 STARK 证明证明并由相应的 STARK 验证器验证的通用计算语句。

这就是执行 递归 的机会发挥作用的地方：正如我们编写一个 Cairo 程序来证明数千笔交易的正确性一样，我们也可以编写一个 Cairo 程序来验证多个 STARK 证明。我们可以生成一个证明，证明多个“上游”证明的有效性。这就是我们所说的递归证明。

由于对数压缩和大致线性的证明时间，证明对 STARK 证明的验证所花费的时间相对较短（预计在不久的将来仅需几分钟）。

在实现递归时，SHARP 可以在语句到达时证明它们。它们的证明可以一遍又一遍地合并到各种模式的递归证明中，直到在某个时候，将生成的证明提交到链上验证器合约。一个典型的模式如图 2 所示：

图 2：典型的递归证明流程。

在此示例中，将四个语句发送到 SHARP（可能来自四个不同的来源）。这些语句各自并行证明。然后，每对证明都由递归验证器语句（一个验证 STARK 证明的 Cairo 程序）验证，并生成一个证明。此语句断言已验证两个证明是正确的。接下来，这两个证明再次由递归验证器语句合并。这将生成一个证明，证明所有四个原始语句。然后，可以最终将此证明提交到链上，由 Solidity 验证器智能合约验证。

递归证明的直接好处

降低链上成本

立即，我们实现了将多个证明“压缩”为一个证明，这意味着每次交易的链上验证成本更低（其中每个语句可能包括许多交易）。

通过递归，计算资源障碍（例如内存）现在限制了证明的大小，因为可以分别证明每个限制大小的语句。因此，当使用递归时，递归的有效 Train 大小几乎是无限的，并且每次交易的成本可以降低几个数量级。

实际上，减少量取决于可接受的延迟（以及交易到达的速率）。此外，由于每个证明通常还伴随一些输出（例如链上数据），因此可以与单个证明一起写入链上的数据量存在限制。然而，轻松实现降低一个数量级甚至更好的成本。

降低延迟

递归证明模式降低了证明大型 Train 语句的延迟。这是两个因素的结果：

1. 传入语句可以并行证明（而不是证明一个非常大的组合语句）。
2. 无需等到 Train 中的最后一个语句到达才开始证明。相反，证明可以随着新语句的到达而与新语句组合。这意味着加入 Train 的最后一个语句的延迟大致等于证明该最后一个语句加上证明递归验证器语句（证明所有已“加入”此特定 Train 的语句）所需的时间。

我们正在积极开发和优化证明递归验证器语句的延迟。我们预计在几个月内这将达到几分钟的数量级。因此，高效的 SHARP 可以提供从几分钟到几小时的延迟，具体取决于与每次交易的链上成本的权衡。这代表了对 SHARP 延迟的有意义的改进。

促进 L3

在 Cairo 中开发递归验证器语句也开启了将证明提交到 StarkNet 的可能性，因为该语句可以嵌入到 StarkNet 智能合约中。这允许在公共 StarkNet（L2 网络）之上构建 L3 部署。

递归模式也适用于 L3 证明的聚合，这些证明将由 L2 上的单个证明验证。因此，超扩展也在此处实现。

更微妙的好处

应用递归

递归为希望进一步扩展其成本和性能的平台和应用程序开辟了更多机会。

每个 STARK 证明都证明应用于某个输入的语句的有效性，该输入称为“公共输入”（或 Cairo 中的“程序输出”）。从概念上讲，STARK 递归将具有两个输入的两个证明压缩为具有两个输入的一个证明。换句话说，虽然证明的数量减少了，但输入的数量保持不变。然后，这些输入通常被应用程序用于更新 L1 上的某些状态（例如，更新状态根或执行链上提款）。

如果允许递归语句是应用程序感知的，即识别应用程序本身的语义，则它既可以将两个证明压缩为一个证明，也可以将两个输入组合为一个输入。生成的语句证明基于应用程序语义的输入组合的有效性，因此得名 Applicative Recursion（应用递归）（有关示例，请参见图 3）。

图 3：应用递归示例

在此，语句 1 证明从 A 到 B 的状态更新，语句 2 证明从 B 到 C 的进一步更新。语句 1 和语句 2 的证明可以组合成第三个语句，证明从 A 到 C 的直接更新。通过以递归方式应用类似的逻辑，可以显着降低状态更新的成本，直至达到最终确定性延迟要求。

应用递归的另一个重要示例是压缩来自多个证明的 Rollup 数据。例如，对于诸如 StarkNet 之类的有效性 Rollup，L2 上的每个存储更新也作为传输数据包含在 L1 上，以确保数据可用性。但是，无需为同一存储元素发送多个更新，因为对于数据可用性，只需要证明所证明的交易的最终值。此优化已在单个 StarkNet 块中执行。但是，通过为每个块生成一个证明，应用递归可以跨多个 L2 块压缩此 Rollup 数据。这可以显着降低成本，从而在 L2 上实现更短的块间隔，而不会牺牲 L1 更新的可扩展性。

值得注意的是：应用递归可以与前面描述的与应用程序无关的递归相结合。这两个优化是独立的。

降低链上验证器的复杂性

STARK 验证器的复杂性取决于它旨在验证的语句类型。特别是，对于 Cairo 语句，验证器的复杂性取决于 Cairo 语言中允许的特定元素，更具体地说，取决于支持的内置函数（如果我们将 CPU 比喻为 Cairo，则内置函数相当于 CPU 中的微电路：执行得非常频繁的计算，以至于它们需要自己的优化计算）。

Cairo 语言不断发展，并提供越来越多的有用内置函数。另一方面，递归验证器仅需要使用这些内置函数的一个小子集。因此，递归 SHARP 可以通过在递归验证器中支持完整语言来成功支持 Cairo 中的任何语句。具体来说，L1 Solidity 验证器只需要验证递归证明，因此可以限制为 Cairo 语言的更稳定的子集：L1 验证器无需跟上最新和最强大的内置函数。换句话说，不断发展的复杂语句的验证被降级到 L2，而让 L1 验证器验证更简单和更稳定的语句。

减少计算占用空间

在递归之前，将多个语句聚合到一个证明中的能力受到可在可用计算实例上证明的最大语句大小（以及生成此类证明可能花费的时间）的限制。

通过递归，不再需要证明如此大的语句。因此，可以使用更小、更便宜且更可用的计算实例（尽管可能需要比大型单片证明器更多的实例）。这允许在比以前更多的物理和虚拟环境中部署证明器实例。

总结

通用计算的递归证明现在为包括 StarkNet 在内的多个生产系统提供服务，这些系统位于 Mainnet Ethereum 上。

随着递归不断允许新的改进，递归的好处将逐步实现，并且它将通过释放并行化的潜力来很快提供超大规模、削减 Gas 费和提高延迟。

它将带来显着的成本和延迟优势，以及 L3 和应用递归等新机会。递归验证器的进一步优化正在进行中，预计随着时间的推移将提供更好的性能和成本效益。

Gidi Kaempfer，StarkWare 核心工程主管

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