Lighthouse 的 Attestation 聚合与打包优化项目

eth-protocol-fellows
发布于 2023-08-17 11:29
阅读 17

Lighthouse 客户端的 Attestation 打包优化项目旨在提高区块提议者的奖励。该项目将实现一个最优的 Attestation 打包算法，通过 Bron-Kerbosch 算法进行聚合，并采用改进的最大覆盖算法进行打包，最终目标是在生产环境中默认运行最优的 Attestation 打包实现，或者为高性能机器提供可通过命令行开启的优化方案，并为计算能力受限的设备提供更好的解决方案。

## Lighthouse 的证明聚合与打包优化项目

Lighthouse 中的最佳证明打包

### 动机

证明打包是以太坊共识客户端选择要包含在区块中的证明的过程。 即使在合并之前，客户端团队也在这方面做了大量工作，因为区块提议者的奖励直接受到打包的证明与规范链的匹配程度的影响。 目前，Lighthouse 采用贪婪策略来决定提议者在区块中包含哪些证明。 这在很多情况下会产生接近最优的解决方案，但也有一些异常值，其质量没有已知的下限。 例如，在测试期间，Lighthouse 团队和 Satalia 发现了一个实例，其中贪婪策略的性能约为最佳解决方案的 60%。 在为期 8 天的数据收集期间，贪婪算法的证明打包奖励比最佳奖励低约 0.26 ETH。 我们的项目旨在通过实施最优的证明打包算法来补救这种情况，该算法至少可以在更强大的机器上在生产环境中运行。

### 项目描述

在 Sigma Prime 和 Satalia 在该主题上的合作取得巨大成果之后，我们建议实施他们用于证明聚合的最大团枚举解决方案，以及一种改进的最大覆盖算法，该算法利用了问题的结构。

### 规范

我们将分两个阶段实施我们的解决方案：

##### 聚合
对于聚合阶段，我们将把 Satalia 的 Bron-Kerbosch 算法的纯 Rust 实现移植到 Lighthouse 代码库中。 我们将删除当前在插入到操作池时发生的贪婪聚合步骤。 当被要求构造区块时，我们将在操作池中对一组有效的聚合证明使用 Bron-Kerbosch 算法，以创建一个限制性的证明集，该集合可保持最优性。 然后，我们将把可以聚合到结果集中的每个聚合的未聚合证明进行聚合。 并添加由未聚合证明形成的聚合证明，这些证明未由聚合证明集表示。 最后，我们将使用此集合作为最大覆盖算法的输入来进行打包。

##### 打包
打包阶段是加权最大覆盖问题 (WMCP) 的一个实例，已知该问题是 NP 难题。 为了解决这个问题，Satalia 的论文提出了一种解决方案，其中该问题被定义为混合整数问题 (MIP)。 然后，可以通过两种方法计算解决方案，一种是使用众所周知的免费 MIP 求解器（例如：CBC、SCIP），另一种是使用基于分支定界算法的自定义求解器。 前一种方法被 Satalia 称为“分解方法”，后一种方法称为“枚举方法”。 这些论文还提出了一些优化每种方法性能的策略。 我们计划在该项目的过程中实施这两种方法，尽我们所能优化每种方法，并最终选择性能更好的方法。
最终的实现还将允许用户在可用的方法之间进行选择——现有的贪婪实现和两种新方法。

### 路线图

第 1-2 周：\
将初始算法从 SigP 和 Satalia 仓库移植到 Lighthouse 中。
**聚合**：实现第一次通过。\
**打包**：实现第一次通过。

第 3-4 周：\
**聚合**：设置一些节点，以便在每个插槽中生成区块，以测试验证器奖励和性能。 根据需要实施更改。
**打包**：通过将问题分解为更小的子问题（每个子问题都可以在指数时间内解决），然后将子问题的解决方案组合起来以获得原始问题的解决方案（在线性时间内），从而实现分解方法。

第 5 周：\
**聚合**：尽可能清理代码并进行更多测试。 然后，如果测试结果良好，我们希望可以合并。 这将结束证明聚合部分。
**打包**：探索分解方法的优化。 这些包括并行计算动态规划算法的状态，尝试不同的 MIP 求解器（CBC 与 SCIP）等。

第 6-7 周：\
**打包**：通过使用分支定界算法枚举问题的所有可能解决方案来实现枚举方法。

第 8-10 周
**打包**：对两种方法进行基准测试，找出瓶颈并尽可能优化代码。 然后，如果测试结果良好，我们希望可以合并。

### 可能的挑战

主要挑战是最大覆盖算法的性能，因为它是一个已知的 NP 难题。 要编写一个在生产环境中表现良好的实现，考虑到证明打包的小窗口，将需要耐心和迭代。 我们希望编写一个即使对于规范设备也有效的实现，因此我们将需要进行大量测试。

### 项目目标

该项目的完全成功将是一个最佳的证明打包实现，该实现默认在 Lighthouse 中运行。 稍微不成功的最终结果是，对于强大的机器，可以通过命令行标志打开最佳解决方案，而对于计算受限的设备，则可以采用更好（但不一定是最优的）的证明打包解决方案。

### 合作者

[Ankur Dubey](https://github.com/ankurdubey521) 和 [Geemo Candama](https://github.com/GeemoCandama)

#### 研究员

[Ankur Dubey](https://github.com/ankurdubey521) 和 [Geemo Candama](https://github.com/GeemoCandama)

#### 导师

[Michael Sproul](https://github.com/michaelsproul) 和 [Paul Hauner](https://github.com/paulhauner)

### 资源
演讲：[优化证明聚合与打包](https://docs.google.com/presentation/d/1uigrSd6j57fhsTWpcQX2cYnSTgUwWP6z6RLy0UH9xYQ/edit?usp=sharing)
```
Aggregation: https://github.com/sigp/lighthouse/pull/4507
Packing: https://github.com/sigp/lighthouse/pull/4542
Previous Work: 
https://lighthouse-blog.sigmaprime.io/docs/satalia-01-problem-definition.pdf
https://lighthouse-blog.sigmaprime.io/docs/satalia-02-exact-approaches.pdf
https://lighthouse-blog.sigmaprime.io/docs/satalia-03-results.pdf
https://github.com/michaelsproul/optimising-attestation-packing-satalia
```

>- 原文链接： [github.com/eth-protocol-...](https://github.com/eth-protocol-fellows/cohort-four/blob/master/projects/attestation-aggregation-and-packing-optimisation-lighthouse.md)
>- 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～

Lighthouse 的证明聚合与打包优化项目

Lighthouse 中的最佳证明打包

动机

证明打包是以太坊共识客户端选择要包含在区块中的证明的过程。即使在合并之前，客户端团队也在这方面做了大量工作，因为区块提议者的奖励直接受到打包的证明与规范链的匹配程度的影响。目前，Lighthouse 采用贪婪策略来决定提议者在区块中包含哪些证明。这在很多情况下会产生接近最优的解决方案，但也有一些异常值，其质量没有已知的下限。例如，在测试期间，Lighthouse 团队和 Satalia 发现了一个实例，其中贪婪策略的性能约为最佳解决方案的 60%。在为期 8 天的数据收集期间，贪婪算法的证明打包奖励比最佳奖励低约 0.26 ETH。我们的项目旨在通过实施最优的证明打包算法来补救这种情况，该算法至少可以在更强大的机器上在生产环境中运行。

项目描述

规范

我们将分两个阶段实施我们的解决方案：

聚合

对于聚合阶段，我们将把 Satalia 的 Bron-Kerbosch 算法的纯 Rust 实现移植到 Lighthouse 代码库中。我们将删除当前在插入到操作池时发生的贪婪聚合步骤。当被要求构造区块时，我们将在操作池中对一组有效的聚合证明使用 Bron-Kerbosch 算法，以创建一个限制性的证明集，该集合可保持最优性。然后，我们将把可以聚合到结果集中的每个聚合的未聚合证明进行聚合。并添加由未聚合证明形成的聚合证明，这些证明未由聚合证明集表示。最后，我们将使用此集合作为最大覆盖算法的输入来进行打包。

打包

打包阶段是加权最大覆盖问题 (WMCP) 的一个实例，已知该问题是 NP 难题。为了解决这个问题，Satalia 的论文提出了一种解决方案，其中该问题被定义为混合整数问题 (MIP)。然后，可以通过两种方法计算解决方案，一种是使用众所周知的免费 MIP 求解器（例如：CBC、SCIP），另一种是使用基于分支定界算法的自定义求解器。前一种方法被 Satalia 称为“分解方法”，后一种方法称为“枚举方法”。这些论文还提出了一些优化每种方法性能的策略。我们计划在该项目的过程中实施这两种方法，尽我们所能优化每种方法，并最终选择性能更好的方法。最终的实现还将允许用户在可用的方法之间进行选择——现有的贪婪实现和两种新方法。

路线图

第 1-2 周：\ 将初始算法从 SigP 和 Satalia 仓库移植到 Lighthouse 中。聚合：实现第一次通过。\ 打包：实现第一次通过。

第 3-4 周：\ 聚合：设置一些节点，以便在每个插槽中生成区块，以测试验证器奖励和性能。根据需要实施更改。打包：通过将问题分解为更小的子问题（每个子问题都可以在指数时间内解决），然后将子问题的解决方案组合起来以获得原始问题的解决方案（在线性时间内），从而实现分解方法。

第 5 周：\ 聚合：尽可能清理代码并进行更多测试。然后，如果测试结果良好，我们希望可以合并。这将结束证明聚合部分。打包：探索分解方法的优化。这些包括并行计算动态规划算法的状态，尝试不同的 MIP 求解器（CBC 与 SCIP）等。

第 6-7 周：\ 打包：通过使用分支定界算法枚举问题的所有可能解决方案来实现枚举方法。

第 8-10 周 打包：对两种方法进行基准测试，找出瓶颈并尽可能优化代码。然后，如果测试结果良好，我们希望可以合并。

可能的挑战

主要挑战是最大覆盖算法的性能，因为它是一个已知的 NP 难题。要编写一个在生产环境中表现良好的实现，考虑到证明打包的小窗口，将需要耐心和迭代。我们希望编写一个即使对于规范设备也有效的实现，因此我们将需要进行大量测试。

项目目标

该项目的完全成功将是一个最佳的证明打包实现，该实现默认在 Lighthouse 中运行。稍微不成功的最终结果是，对于强大的机器，可以通过命令行标志打开最佳解决方案，而对于计算受限的设备，则可以采用更好（但不一定是最优的）的证明打包解决方案。

Aggregation: https://github.com/sigp/lighthouse/pull/4507
Packing: https://github.com/sigp/lighthouse/pull/4542
Previous Work: 
https://lighthouse-blog.sigmaprime.io/docs/satalia-01-problem-definition.pdf
https://lighthouse-blog.sigmaprime.io/docs/satalia-02-exact-approaches.pdf
https://lighthouse-blog.sigmaprime.io/docs/satalia-03-results.pdf
https://github.com/michaelsproul/optimising-attestation-packing-satalia