优化证明打包

sigmaprime
发布于 2022-11-30 22:36
阅读 8

Sigma Prime 与 Satalia 合作，研究以太坊 2.0 中 Attestation Packing 问题。研究表明，Lighthouse 客户端使用的贪婪算法在大多数情况下接近最优，且在可接受的时间内可以找到最优解。因此短期内不会在生产环境中采用精确算法，而是关注提高现有贪婪算法的速度和改进与其他构建器的交互。

我们很高兴与大家分享与 [Satalia](https://www.satalia.com/) 的优化科学家们合作进行的关于 **证明打包（attestation packing）** 的成果。

证明打包是 Ethereum 共识客户端选择包含在区块中的证明的过程。我们之前在这篇博客上 [写过关于它的文章](https://blog.sigmaprime.io/attestation-packing.html)，并且我们花了很多时间思考这个问题。

## 背景

我们早就知道证明打包是一个 NP 困难的优化问题。证明会根据其与规范链的匹配程度向区块提议者支付不同的奖励，并且区块提议者只能包含有限数量的证明（128 个）。

当我刚开始在 Lighthouse 工作时，我参与的第一个项目就是我们对证明打包的实现。为了平衡速度和盈利能力，我选择了一种贪婪近似算法，该算法似乎可以生成良好的区块，同时在消费级硬件上以小于约 250 毫秒的速度运行。但是，我从未尝试过 **真正** 构建最佳解决方案，并且由于 **聚合（aggregation）** 的复杂性，近似解决方案的质量没有任何理论上的下限保证。于是，[Satalia](https://www.satalia.com/) 登场了。

## 项目目标

通过与 [Satalia](https://www.satalia.com/) 合作，我们的目标是解决关于证明打包的未解决的问题：

1. 是否有可能在合理的时间内 **最优地** 解决证明打包问题的实例？比如，在消费级硬件上 <500 毫秒？
2. Lighthouse 的贪婪算法产生的解决方案与最优解的接近程度如何？

我们研究这些问题的动机不仅仅是为了提高 Lighthouse 的区块盈利能力，也是为了避免系统性风险。如果通过花费更多的计算资源来产生更好的区块是可能的，那么大型 staking 提供商将比小型 staker 具有优势，并且由此产生的 **规模经济（economy of scale）** 将趋向于中心化。同样，如果区块生产者被激励花费更多时间来构建他们的区块，那么这可能会导致区块传播延迟，从而损害网络。

## 结果

[Satalia](https://www.satalia.com/) 撰写了三份关于这些问题的精美报告，并得到了我们的工程投入。

第一份报告是用数学语言对问题进行正式描述，抽象了 Ethereum 特有的细节。我们希望这对其他研究人员有所帮助。

- [01\. 证明聚合和打包问题](https://blog.sigmaprime.io/docs/satalia-01-problem-definition.pdf) (PDF)

第二份报告描述了用于最优地解决证明聚合和打包问题 (AAPP) 的两种算法。

- [02\. 证明聚合和打包问题的精确方法](https://blog.sigmaprime.io/docs/satalia-02-exact-approaches.pdf) (PDF)

最后，第三份报告包含我们最初的研究问题的答案以及对未来探索的讨论：

- [03\. Lighthouse 贪婪方法在证明打包中的有效质量](https://blog.sigmaprime.io/docs/satalia-03-results.pdf) (PDF)

我们得到了一个 **积极的** 结果来回答我们的第一个研究问题——在 <500 毫秒内最优地解决大多数实例是可能的！Satalia 的 MIP 算法的运行时对于大多数实例小于 500 毫秒，对于 98.6% 的实例小于 1 秒。有关详细信息，请参见报告中的 **第 3.2 节，图 1**。

我们还得到了一个有利于 Lighthouse 当前贪婪算法的结果。对于 52.3% 的测试实例，贪婪算法产生了最优解，对于 99.97% 的测试实例，产生了在最优解的 5% 以内的解。参见报告中的 **第 3.1 节**。

有趣的是，贪婪算法产生的 **最差** 解决方案低于 [加权最大覆盖问题](https://en.wikipedia.org/wiki/Maximum_coverage_problem) (WMCP) 的理论下限，质量为最优解的 56.54%。WMCP 的下限为 1−1/e≈63.2%，因此这是一个显着差异。我们认为这是由于我们算法的聚合阶段，该阶段确定了我们用于 WMCP 的近似算法的输入。我们当前的聚合算法机会主义地聚合添加到池中的证明，并且其近似比率没有经过验证的下限。

在贪婪算法明显低于最优解的情况下，精确求解器的运行时也急剧增加，对于贪婪算法表现最差的实例，达到了 2.6 秒。MIP 算法测得的最大运行时为 6.1 秒。对于生产用途，Satalia 概述了对 MIP 算法的两项改进，这些改进可能会有更好的运行时性能。一种是问题分解，利用了来自不同委员会的证明可以单独打包的事实。另一种是专门的分支定界算法来代替 MIP 求解器。我们认为其中一种或两种方法都将产生适合生产的精确方法，其实现将是我们方面的一项工程工作。

有关已解决的所有 51097 个实例的完整数据，请参见：

- [04\. Satalia 区块打包结果](https://docs.google.com/spreadsheets/d/1PWxGFGtS8V5UE97bNIg_icu6Gr1CE3zCA4DUAFMN8X0) (Google Sheets)

## 结论

鉴于贪婪算法在大多数情况下都具有接近最优的性能，我们不认为证明打包对 Ethereum 构成重大的中心化风险。拥有快速精确求解器的区块提议者产生的区块仅比贪婪算法产生的区块略好，并且仅在极少数情况下 (0.03%) 才能看到大于 5% 的收益。

因此，我们已决定在不久的将来不推进在生产中使用精确算法。构建一致快速的精确实现所需的工程工作量很大，这不是我们现在可以投入资源的事情。相反，我们已决定追求几个相关的努力，我们认为这些努力将产生更大的影响：

- 提高我们现有贪婪算法的速度：
```
sigp/lighthouse#3312
```
- 改善 Lighthouse 与构建者的交互，使 MEV 更易于访问且具有抗审查性：
```
sigp/lighthouse#builder-API
```
- 采用对聚合的改进，以将贪婪算法的最坏情况性能提高到 WMCP 的下限：
```
sigp/lighthouse#3733
```
- 通过标准化和实施新的 API 来提高区块奖励的透明度：
```
sigp/lighthouse#3661
```

这并不是说我们不会在某个时候重新审视最佳证明打包。进行这项工作为我们提供了关于问题空间的极其有用的知识，这些知识将在重新审视这个问题时具有相关性。

我们非常感谢 [Satalia](https://www.satalia.com/) 进行的强大且具有智力刺激性的合作。 特别是，我们要感谢 Judita Maslauskaitė、Tommaso Urli、Benedikt Posch 和 Stanislovas Kujalis。 他们的工作帮助我们突破了自 Ethereum 信标链诞生以来就一直存在的难题。

我们现在有信心知道我们现有的软件已经接近最优，并且没有潜伏在阴影中的系统性风险。

>- 原文链接： [blog.sigmaprime.io/optim...](https://blog.sigmaprime.io/optimising-attestation-packing.html)
>- 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～

我们很高兴与大家分享与 Satalia 的优化科学家们合作进行的关于 证明打包（attestation packing） 的成果。

证明打包是 Ethereum 共识客户端选择包含在区块中的证明的过程。我们之前在这篇博客上写过关于它的文章，并且我们花了很多时间思考这个问题。

背景

当我刚开始在 Lighthouse 工作时，我参与的第一个项目就是我们对证明打包的实现。为了平衡速度和盈利能力，我选择了一种贪婪近似算法，该算法似乎可以生成良好的区块，同时在消费级硬件上以小于约 250 毫秒的速度运行。但是，我从未尝试过真正构建最佳解决方案，并且由于 聚合（aggregation） 的复杂性，近似解决方案的质量没有任何理论上的下限保证。于是，Satalia 登场了。

项目目标

通过与 Satalia 合作，我们的目标是解决关于证明打包的未解决的问题：

是否有可能在合理的时间内 最优地 解决证明打包问题的实例？比如，在消费级硬件上 <500 毫秒？
Lighthouse 的贪婪算法产生的解决方案与最优解的接近程度如何？

我们研究这些问题的动机不仅仅是为了提高 Lighthouse 的区块盈利能力，也是为了避免系统性风险。如果通过花费更多的计算资源来产生更好的区块是可能的，那么大型 staking 提供商将比小型 staker 具有优势，并且由此产生的 规模经济（economy of scale） 将趋向于中心化。同样，如果区块生产者被激励花费更多时间来构建他们的区块，那么这可能会导致区块传播延迟，从而损害网络。

结果

Satalia 撰写了三份关于这些问题的精美报告，并得到了我们的工程投入。

第一份报告是用数学语言对问题进行正式描述，抽象了 Ethereum 特有的细节。我们希望这对其他研究人员有所帮助。

01. 证明聚合和打包问题 (PDF)

第二份报告描述了用于最优地解决证明聚合和打包问题 (AAPP) 的两种算法。

02. 证明聚合和打包问题的精确方法 (PDF)

最后，第三份报告包含我们最初的研究问题的答案以及对未来探索的讨论：

03. Lighthouse 贪婪方法在证明打包中的有效质量 (PDF)

我们得到了一个 积极的 结果来回答我们的第一个研究问题——在 <500 毫秒内最优地解决大多数实例是可能的！Satalia 的 MIP 算法的运行时对于大多数实例小于 500 毫秒，对于 98.6% 的实例小于 1 秒。有关详细信息，请参见报告中的 第 3.2 节，图 1。

我们还得到了一个有利于 Lighthouse 当前贪婪算法的结果。对于 52.3% 的测试实例，贪婪算法产生了最优解，对于 99.97% 的测试实例，产生了在最优解的 5% 以内的解。参见报告中的 第 3.1 节。

有趣的是，贪婪算法产生的最差解决方案低于加权最大覆盖问题 (WMCP) 的理论下限，质量为最优解的 56.54%。WMCP 的下限为 1−1/e≈63.2%，因此这是一个显着差异。我们认为这是由于我们算法的聚合阶段，该阶段确定了我们用于 WMCP 的近似算法的输入。我们当前的聚合算法机会主义地聚合添加到池中的证明，并且其近似比率没有经过验证的下限。

有关已解决的所有 51097 个实例的完整数据，请参见：

04. Satalia 区块打包结果 (Google Sheets)

结论

提高我们现有贪婪算法的速度：
```
sigp/lighthouse#3312
```
改善 Lighthouse 与构建者的交互，使 MEV 更易于访问且具有抗审查性：
```
sigp/lighthouse#builder-API
```
采用对聚合的改进，以将贪婪算法的最坏情况性能提高到 WMCP 的下限：
```
sigp/lighthouse#3733
```
通过标准化和实施新的 API 来提高区块奖励的透明度：
```
sigp/lighthouse#3661
```

我们非常感谢 Satalia 进行的强大且具有智力刺激性的合作。特别是，我们要感谢 Judita Maslauskaitė、Tommaso Urli、Benedikt Posch 和 Stanislovas Kujalis。他们的工作帮助我们突破了自 Ethereum 信标链诞生以来就一直存在的难题。

我们现在有信心知道我们现有的软件已经接近最优，并且没有潜伏在阴影中的系统性风险。