一文读懂StarkNet零知识递归证明：STARK

StarkNet零常识递归证明—STARK已上线，递归在本钱和推迟方面的优势异常明显，还会催生 L3 和运用递归等新时机。

原文：《Recursive STARKs》 byStarkWare 中心工程师 Gidi Kaempfer

翻译：「StarkNet 中文」社区

作者：技术最前沿

概要

递归证明上线主网，用一个证明来扩展 StarkEx 运用程序和 StarkNet

递归证明提高扩展性，下降本钱和推迟（鲜有的扩展性和推迟同步开展，而没有取舍）

递归证明为 L3 和其他妙用创造了条件

来看看递归证明的博文吧，超酷的

倍数扩展！

由 Cairo 通用核算供给支撑的递归证明现已投入生产。这标志着 STARK 对 L2 扩展才干的严重提高。单一证明写入以太坊的买卖数量可快速成倍增加。

迄今为止，STARK 证明经过将数万乃至数十万个买卖「汇总」成单一证明写入以太坊来完成扩展。经过递归，许多这样的证明能够「汇总」成一个单一证明。

这种方法现已运用于众多根据 Cairo 的运用程序：在 StarkWare 的 SaaS 扩展引擎 StarkEx 和无需答应的 Rollup StarkNet 上运转的运用程序 。

迄今开展进程

自 2020 年 3 月主网上线首个证明发生以来，STARK 证明至今阅历了不同开展阶段。

STARK 扩展

2020 年 6 月，第一个 STARK 扩展解决方案StarkEx在以太坊主网布置。StarkEx 有一个证冥具能够在链下履行大型核算，生成一个 STARK 证明表明买卖准确性，还有一个验证器在链上验证证明的准确性。第一次布置由 StarkWare 工程师从零开始亲身操刀，因而 StarkEx 的功用极大受限。终究咱们决定，需求一种支撑证明通用核算的编程言语。这样，Cairo 便应运而生。

Cairo 编程言语

2020 年夏天，Cairo初次亮相以太坊主网。Cairo 即 CPU 代数中间代码(CPU Algebraic Intermediate Representation [AIR])，内含一个用于验证相应「CPU」指令集的单一 AIR。Cairo 为更杂乱的事务逻辑、任意可核算出题(computational statements)打开了编码证明的大门，而且更快、更安全。一个 Cairo 程序能够证明相应运用程序的履行逻辑。但一个 Cairo 程序也能够调集多个此类运用程序，这便是 SHARP。

SHARP

SHARP 即同享证冥具 (SHARed ProSver)，能够聚合几个独立运用程序的买卖，并在一个单一的 STARK 证明中证明。运用程序能够组合不同批量买卖，更快填满 STARK 证明的容量。买卖处理速度和推迟都有所提高。递归证明是下一代前沿技术，不只适用于一些硬编码逻辑，而且适用于通用核算。

要了解递归证明的悉数优势，有必要进一步了解 SHARP 迄今为止是如何履行（非递归）证明的。图 1 描绘了一个典型的非递归流程：

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

在这个流程中，出题逐渐抵达。容量（或时刻）抵达必定阈值时，会生成一个大型组合出题 (Train)。只要在收到一切独自出题后，才干证明此组合出题。此证明需求很长时刻（大约是独自证明每个出题所需的时刻总和）。

证明极其巨大的出题终究会遭到内存等可用核算资源的约束。在递归之前，这实际上是约束 STARK 证明可扩展性的一大妨碍。

什么是递归证明？

经过 STARK 证明，证明出题所花费的时刻与履行出题所花费的时刻大致呈线性关系。此外，假如证明一个出题需求的时刻为 T，那么验证证明所需求的时刻大约为 log(T) ，这一般被称为「对数紧缩」。换句话说，运用 STARK 让用户在验证出题上的时刻要比核算出题的时刻少得多。

Cairo答应表达通用核算出题，这些出题能够经 STARK 证明所证明，再经相应的 STARK 验证器验证。

这便是履行递归的时机地点：就像能够写一个 Cairo 程序来证明不计其数的买卖正确性，也能够写一个 Cairo 程序来验证多个

STARK 证明。能够生成一个证明来验证多个「上游」证明的有用性。这便是咱们所说的递归证明。

因为对数紧缩和证明时刻大致呈线性关系，证明 STARK 证明所需的时刻相对较短（不久的将来估计只需求几分钟）。

在完成递归时，SHARP 能够一收到出题就能够对其进行验证。证明能够各种形式重复地合并成递归证明，直到在某个点上，发生的证明提交给链上验证者合约。图 2 便是典型的递归证明形式：

图 2：典型递归证明流程

在本例中，有四个出题发送给 SHARP（或许源自四个不同运用）。这些出题各自平行证明。然后，每一对证明都由一个递归验证器出题（验证 STARK 证明的 Cairo 程序）来验证，由此发生一个证明。这一出题证明有两个证明经过验证。接下来，经过递归验证器出题再次合并这两个证明。这就发生了一个证明，证明一切四个原始出题。此证明终究能够提交到链上，由 Solidity 验证器智能合约进行验证。

递归证明的直接优势

下降链上本钱

毫无疑问，咱们完成了将多个证明「紧缩」成一个，这意味着每笔买卖链上验证本钱会大幅更低（其中每个出题或许包含许多买卖）。

运用递归证明能够消除至今约束证明大小的核算资源妨碍（如内存），因为每个出题容量有限，都能够独自证明。因而当运用递归时，递归的有用组合出题 (Train) 的容量几乎是无限，每笔买卖本钱能够下降好几个数量级。

在实际操作中，下降本钱取决于可接受的推迟（以及买卖抵达的速度）。此外，因为每个证明一般也随同相应链上数据输出，因而与单个证明一起写入链上的数据量也会有限。虽然如此，将本钱下降一个数量级，乃至继续提高功能都能够轻松完成。

下降推迟

递归证明形式可下降证明大型组合出题推迟。有两个因素起到效果：

1. 接纳的出题能够并行证明（而不是证明巨大的组合出题）。

2. 无需比及 Train 中的终究一个出题抵达即可证明。相反，有新出题参加能够随时与证明结合。也便是说，参加 Train 的终究一个出题的推迟，大致上是证明终究一条出题所需的时刻加上证明递归验证器出题（证明一切已经「参加」这个特定 Train 的出题）所需的时刻。

咱们正在活跃开发和优化证明递归验证器出题的推迟问题。估计几个月内证明递归验证器出题会抵达几分钟的数量级。因而，一个高效的 SHARP 推迟可控制在几分钟到几小时，推迟长短取决于对每笔买卖链上本钱的取舍。这是对 SHARP 推迟的严重改进。

促进 L3 运用

用 Cairo 开发的递归验证器出题也开启了向 StarkNet 提交证明的或许性，因为该出题能够写入 StarkNet 智能合约。这答应在StarkNet L2 公共网络上布置 L3。

递归形式也适用于来自 L3 的聚合证明，由 L2 上的单个证明验证。因而，L3 也能够完成超大规模扩展。

更多妙用

运用递归

递归为希望进一步扩展其本钱和功能的渠道和运用程序拓荒了更多时机。

每个 STARK 证明证明运用于某些「公开输入」（或 Cairo 术语中的「程序输出」）的出题有用性。从概念上来说，STARK 递归将具有两个输入的两个证明紧缩为一个具有两个输入的证明。换句话说，虽然证明的数量削减，但输入数量未变。然后，输入一般由运用程序用以更新 L1 上的某些状况（例如，更新状况根或履行链上取款）。

假如递归出题能够在运用层感知，即辨认运用程序本身的语义，那么递归出题既能够将两个证明紧缩为一个，也能够将两个输入组合为一个。终究的出题证明根据运用程序语义的输入组合的有用性，这便是运用递归（Applicative Recursion，参见图 3 示例）。

图 3：运用递归示例

出题 1 证明从 A 到 B 的状况更新，而出题 2 验证从 B 到 C 的进一步更新。出题 1 和出题 2 的证明能够合并为第三个出题，直接证明从 A 到 C 的更新。经过运用相似的递归逻辑，能够十分明显地下降状况更新的本钱，抵达终究推迟要求。

运用递归的另一个重要示例是紧缩来自多个证明的汇总数据。例如，对于像 StarkNet 这样的有用性证明 Rollup，L2 每次存储更新也作为传输数据在 L1 更新，保证数据可用性。可是，不需求为同一个存储单元发送多次更新，因为只要经过证明验证过的买卖终究才干满足数据可用性。此优化已在单个StarkNet 区块中履行。可是，经过为每个区块生成证明，运用递归能够紧缩多个L2 区块汇总数据。这能够明显下降本钱，下降 L2 出块时刻，而不会献身 L1 更新的可扩展性。

值得注意的是：运用递归能够与前面描述的运用通用递归结合运用。但这两种优化互无关联。

下降链上验证器的杂乱性

STARK 验证器的杂乱性取决于用以验证的出题类型。特别是对于 Cairo 出题，验证器的杂乱性取决于 Cairo 言语中答应的特定要素，更具体地说，是支撑的内置项（假如把 Cairo 比喻成 CPU，那么内置项相当于 CPU 中的微电路：核算履行过分频频，所以需求优化本身核算）。

Cairo 言语不断开展并供给越来越多有用的内置项。另一方面，递归验证器只需求运用一小部分内置项。因而，递归 SHARP 能够经过支撑递归验证器中的完好言语来成功支撑 Cairo 中的任何出题。具体来说，L1 上的 Solidity 验证器只需求验证递归证明，因而验证器能够仅限于验证 Cairo 言语一个更安稳的子集：L1 验证器不需求随最新、最安稳的内置项更新。换句话说，出题不断演化，杂乱的验证就交由 L2 处理，L1 验证器只需求验证简单、安稳的出题。

削减核算足迹

在递归之前，聚合多个出题为一个证明遭到可用核算实例上能够证明的出题大小（以及生成此类证明所需的时刻）的约束。

有了递归，无需再证明如此巨大的出题。因为有了更多又小又便宜的核算实例可供运用（虽然核算实例或许要比运用大型单片证冥具时需求的更多）。这使得在更多的物理和虚拟环境中布置证冥具实例成为或许。

总结

通用核算的递归证明现已为包含 StarkNet 在内以太坊主网上的多个产品系统服务。

因为能够不断改进，递归的优势会逐渐显现。并行核算的潜力得以发挥后，Gas 费下降，推迟改进，超高扩展性终将完成。

递归在本钱和推迟方面的优势异常明显，还会催生 L3 和运用递归等新时机。递归验证器持续优化，功能和本钱效益也都会逐渐提高。

附录

原文：Recursive STARKs

https://medium.com/starkware/recursive-starks-78f8dd401025

原文：Youtube:StarkEx - How Does it Work?

https://www.youtube.com/watch?v=P-qoPVoneQA

原文：Hello, Cario!

https://medium.com/starkware/hello-cairo-3cb43b13b209

原文：Hello, Cario!

https://starkware.co/cairo/

原文：Wikipedia Entry: Recursion

https://en.wikipedia.org/wiki/Recursion

原文：《分形式扩容：从L2到L3》

https://mirror.xyz/starknet-zh.eth/-5oiKxwShIOzGUwuQJzIl070wopcPjqBcypVjRvyC1E