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

2022-08-17 17:39:22· 稿源：网络整理

图 2：典型递归证明流程

图 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?

原文：Hello, Cario!