以太坊 - 递归 STARKs

递归 STARKs

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

TL;DR

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

规模化！

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

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

这种方法现在已在大量基于 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)，并且包含一个验证此“CPU”指令集的单个 AIR。它为编码更复杂的业务逻辑证明、任意计算语句以及以更快、更安全的方式进行证明打开了大门。Cairo 程序可以证明单个应用程序逻辑的执行。但是 Cairo 程序也可以是多个此类应用程序的串联 — SHARP。

SHARP

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

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

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

这里，语句随时间推移而到达。当达到某个容量（或时间）阈值时，会生成一个大的组合语句（又名 Train）。只有在收到所有单独的语句后，才会证明此组合语句。这个证明需要很长时间才能完成（大约是单独证明每个语句所需时间的总和）。

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

什么是递归证明？

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

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

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

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

在你的收件箱中获取 StarkWare 的故事

免费加入 Medium，即可获取这位作者的更新。

在实施递归时，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 上的某些状态（例如，更新状态根或执行链上提款）。

如果允许递归语句是应用程序感知的，即识别应用程序本身的语义，则它可以将两个证明压缩为一个以及将两个输入组合为一个。生成的语句证明基于应用程序语义的输入组合的有效性，因此称为应用递归（有关示例，请参见图 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 验证器则验证更简单和更稳定的语句。

减少计算足迹

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

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

总结

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

递归的好处将逐渐实现，因为它将继续允许新的改进，并且它将很快通过释放并行化的潜力来提供超大规模、降低 gas 费用和提高延迟。

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

Gidi Kaempfer，StarkWare 核心工程主管

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