什么是递归？

递归最常用于数学、统计学和计算机科学领域，但它也广泛应用于其他一系列学科，包括语言学和逻辑学，以及人工智能和游戏的实际应用。

递归是指函数在循环中直接或间接调用自身。

递归可用于提高计算精度并减少所需的总体计算负载。通过将更大、更复杂的问题分解为更小的部分（也称为“分而治之”），递归可以更快、更可行地解决任务。一个关键特征是该函数连续重复调用自身以实现根据基本情况和递归步骤定义的递归。

基本情况是指具有计算输出的所有输入的问题的最简单实例。递归步骤调用相同的函数，但输入的大小和/或复杂性减小。

迭代算法和递归算法都将问题分解为更小的问题，但前者需要显式的控制逻辑来管理算法的顺序。递归函数的排序是由向量数据和递归函数的相互作用决定的。这为处理无法提前明确定义的数据结构提供了更大的灵活性。

递归如何应用于区块链技术？

递归是一种在区块链上生成证明的方法。它现在为以太坊主网上的多个生产系统提供服务。例如，Arbitrum 使用递归二分算法来解决争议，而 StarkWare 和 zkSync 都使用递归来实现增强的扩展能力。

如果没有递归技术，证明中可以容纳的交易存在上限，该上限由单个区块的计算能力决定。通过递归，可以从包含数十万个基础交易的多个经过验证的证明中生成单个证明。换句话说，我们现在可以在单个证明中处理更多交易，也称为递归扩展。

递归技术应用于零知识证明尤为重要，因为它被视为解决区块链可扩展性的关键解决方案。以 StarkWare 的 StarkNet（以太坊上领先的 zk-rollup 扩展解决方案之一）为例，SHARP（SHARed Prover）将来自 StarkNet 上单独应用程序的交易批量并压缩为一个 ZK-STARK 证明（或只是 STARK 证明）。然后证明者将证明传递给验证者，验证者的工作是在第 1 层验证和注册状态更改。根据所需的计算资源，谁可以成为证明者是有限制的。

现在让我们在图中添加递归。多个交易（或语句）被发送到 SHARP 并并行进行验证。然后每个证明都会由 STARK 验证者进行验证。一旦验证，它们就会通过递归验证器语句再次合并。这个过程可以重复进行，直到最终证明被提交到第 1 层以供 Solidity 验证者智能合约使用。因此，该证明证明了所有原始陈述，允许在单个证明中处理多个链上交易。理论上，递归循环可以无限重复，从而具有“超扩展”能力的潜力。

因此，递归进一步释放了汇总技术和第 2 层扩展的潜力。

递归的好处

有效性证明递归的好处包括由于将多个证明“压缩”为一个而降低了每笔交易的成本，从而降低了 Gas 成本。这允许更多交易在提交给 L1 的单个证明中拆分，从而分摊每笔交易的 Gas 成本。限制证明大小的计算资源障碍也不再是一种约束，因为不需要一次性证明非常大的语句。

它还可以减少延迟。语句（包含较小的交易）可以并行证明，而不必等待其他交易进入。证明者不再需要在链下执行大型计算，因此成为证明者的障碍已经降低，从而激励去中心化的证明者网络进一步提高网络的处理能力。

此外，用户还可以受益于 STARK 的“对数压缩”，其中证明一个陈述需要 T 时间，而验证证明大约需要 log(T) 时间。对数压缩很重要，因为验证包含两个正确执行证明的证明将需要 log(2log(T)) 步骤。换句话说，生成和验证递归证明的延迟呈对数减少。

通过递归，平台和应用程序有机会进一步扩展其成本和性能。

第 2 层之外的递归的用途

递归为第 3 层用例奠定了基础。到目前为止，重点是使用递归在第 2 层上生成最终在第 1 层上解决的证明。然而，新层还提供了从第 3 层向第 2 层提交交易证明的可能性，其中执行在顶层完成，最终在第 2 层验证证明，可以进一步释放性能优化和成本效益。第 3 层和第 2 层之间的交互类似于第 2 层和第 1 层，同时保留所有事务完整性和安全性。

具体来说，私有第 3 层网络是高度可定制的，因此协议能够设置自己的操作参数，例如设置交易批量大小以平衡交易成本和速度或实现隐私保护功能。第 3 层的定制质量可满足不同的用例，同时通过递归提高处理能力，从而实现定制的链体验，同时确保性能和成本优化工具随时可用。第 3 层的优点是超可扩展性，这是由于利用了递归证明、隐私性以及第 2 层和第 3 层之间改进的互操作性的乘法效应。

随着时间的推移，区块链开发中递归的更多用例和好处将被实现。通过解锁并行化过程，它将使超扩展成为可能，同时改善延迟并降低天然气费用。

作者

Jane Ma，zkLend 的联合创始人兼联合项目负责人，zkLend 是一个基于 StarkNet 构建的 L2 货币市场协议，将 zk-rollup 可扩展性、卓越的交易速度和成本节约与以太坊的安全性相结合。该协议提供了双重解决方案：为机构客户提供许可且注重合规性的解决方案，为 DeFi 用户提供无需许可的服务 - 所有这些都不会牺牲去中心化。