# 递归 STARK

By [0xBai_](https://paragraph.com/@alpies) · 2023-11-22

---

**第一个通用计算的递归证明现已在以太坊主网上发布**
---------------------------

### **长话短说**

*   递归证明在主网上上线，通过单一证明扩展 StarkEx 应用程序和 StarkNet
    
*   它提高了规模，并在成本和延迟方面带来了好处（规模和延迟同时发生是一种罕见且令人兴奋的情况，而不是一种权衡）
    
*   它为 L3 和其他好处奠定了基础
    
*   [请阅读有关递归证明的](https://medium.com/@starkware/recursive-starks-78f8dd401025)博客文章 。这是很酷的东西😉
    

### **扩大！**

由开罗通用计算提供支持的递归证明现已投入生产。这标志着 STARK 的 L2 扩展能力得到了重大提升。它将通过单一证明写入以太坊的交易数量迅速增加数倍。

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

这种方法现已在许多基于开罗的应用程序的生产中使用：在 StarkEx（StarkWare 的 SaaS 扩展引擎）和 StarkNet（无需许可的汇总）上运行的应用程序。

### **到目前为止的故事**

自 2020 年 3 月在主网上首次证明以来，以下发展影响了 STARK 的使用方式。

#### **基于 STARK 的扩展**

2020 年 6 月，第一个基于 STARK 的扩展解决方案 [StarkEx](https://youtu.be/P-qoPVoneQA) 部署在以太坊主网上。StarkEx 有一个证明者，可以在链外执行大量计算，并为其正确性生成 STARK 证明，还有一个验证者，可以在链上验证此证明。首次部署的限制是 StarkWare 工程师“手写”的，从而极大地限制了 StarkEx 的功能速度。我们的结论是需要一种支持证明通用计算的编程语言——Cairo。

#### **开罗**

2020 年夏天，开罗 [首次出现在以太坊主网上](https://medium.com/starkware/hello-cairo-3cb43b13b209)。Cairo 代表 CPU 代数中间表示 (AIR)，并包含一个验证该“CPU”指令集的 AIR。它为更复杂的业务逻辑、任意计算语句以及以更快、更安全的方式进行编码证明打开了大门。Cairo 程序可以证明单个应用程序逻辑的执行。但开罗计划也可以是多个此类应用程序的串联——SHARP。

#### **锋利的**

SHARP——一种共享证明者——从多个独立的应用程序中获取交易，并在一个 STARK 证明中证明它们。应用程序合并其批次的交易，更快地填满 STARK 证明的容量。交易的处理速度和延迟均得到改善。下一个前沿：递归证明，但不仅适用于某些硬编码逻辑，而且适用于 **一般计算**。

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

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

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

证明极大的语句最终会受到可用计算资源（例如内存）的限制。在递归之前，这实际上是STARK 证明的限制[区块链可扩展性的障碍。](https://starkware.co/resource/redefining-blockchain-scalability/)

### **什么是递归证明？**

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

[Cairo](https://starkware.co/cairo/) 允许表达可以通过 STARK 证明证明并由相应 STARK 验证者验证的通用计算语句。

[这就是执行递归的](https://en.wikipedia.org/wiki/Recursion)机会  出现的地方：就像我们编写一个 Cairo 程序来证明数千笔交易的正确性一样，我们也可以编写一个 Cairo 程序来验证多个 STARK 证明。我们可以生成一个证明来证明多个“上游”证明的有效性。这就是我们所说的递归证明。

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

在实现递归时，SHARP 可以在语句到达时对其进行证明。他们的证明可以一遍又一遍地合并成各种模式的递归证明，直到在某个时刻，将所得的证明提交给链上验证者合约。典型模式如图 2 所示：

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

在此示例中，有四个语句被发送到 SHARP（可能来自四个不同的源）。这些陈述均被并行证明。然后，每对证明都通过递归验证器语句（验证 STARK 证明的 Cairo 程序）进行验证，并为其生成证明。该声明声称两个证据已被验证是正确的。接下来，通过递归验证器语句再次合并两个证明。这产生了一份证明所有四个原始陈述的证据。然后，该证明最终可以在链上提交，由 Solidity 验证者智能合约进行验证。

### **递归证明的直接好处**

#### **降低链上成本**

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

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

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

#### **减少延迟**

递归证明模式减少了证明大量语句的延迟。这是两个因素的结果：

1.  传入的语句可以并行证明 **（** 而不是证明一个非常大的组合语句）。
    
2.  无需等到火车中的最后一条语句到达才开始证明。相反，证据可以在新的陈述到达时与它们结合起来。这意味着加入火车的最后一条语句的延迟大致是证明最后一条语句所需的时间加上证明递归验证器语句（证明所有已经“加入”该列车的语句）所需的时间。特别是火车）。
    

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

#### **促进 L3**

开罗递归验证器声明的开发也开启了向 StarkNet 提交证明的可能性，因为该声明可以被纳入 StarkNet 智能合约中。 这允许在公共 StarkNet （L2 网络）[之上](https://medium.com/starkware/fractal-scaling-from-l2-to-l3-7fe238ecfb4f)构建 L3 部署。

递归模式也适用于 L3 证明的聚合，并由 L2 上的单个证明进行验证。因此，在那里也实现了超扩展。

### **更微妙的好处**

#### **应用递归**

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

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

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

图 3：应用递归示例

这里，语句1证明了从A到B的状态更新，语句2证明了从B到C的进一步更新。语句1和语句2的证明可以组合成第三个语句，证明从A到C的直接更新通过递归地应用类似的逻辑，可以非常显着地降低状态更新的成本，直至最终延迟要求。

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

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

#### **降低链上验证者的复杂性**

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

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

#### **减少计算占用空间**

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

有了递归，就不再需要证明如此巨大的陈述了。因此，可以使用更小、更便宜且更可用的计算实例（尽管与大型整体证明器相比可能需要更多的计算实例）。这允许在比以前更多的物理和虚拟环境中部署证明者实例。

### **概括**

一般计算的递归证明现在服务于多个生产系统，包括以太坊主网上的 StarkNet。

递归的好处将逐渐实现，因为它不断允许新的改进，并且很快将通过释放并行化的潜力来实现超大规模、降低汽油费并改善延迟。

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

**Gidi Kaempfer**，StarkWare 核心工程主管

---

*Originally published on [0xBai_](https://paragraph.com/@alpies/stark)*