We are pleased to share the results of a joint collaboration on attestation packing with optimisation scientists from Satalia.
Attestation packing is the process by which Ethereum consensus clients choose attestations to include in blocks. We have written about it before on this blog, and it's something that we've spent a lot of time thinking about.
Background
We've known for a long time that attestation packing is an NP-hard optimisation problem. Attestations pay different rewards to the block proposer depending on how well they match the canonical chain, and the block proposer is only able to include a finite number of them (128).
One of the first projects I worked on when I started at Lighthouse was our implementation of attestation packing. In order to balance speed against profitability I settled on a greedy approximation algorithm which seemed to produce good blocks while running in less than ~250ms on consumer hardware. However, I never experimented with actually building optimal solutions, and the quality of the approximate solutions was not guaranteed by any theoretical lower bound due to the complication of aggregation. Enter Satalia.
Project Goals
In teaming up with Satalia our goal was to address unanswered questions about attestation packing:
- Is it possible to solve instances of the attestation packing problem optimally in a reasonable amount of time? Say, <500ms on consumer hardware?
- How close to optimal are the solutions produced by Lighthouse's greedy algorithm?
We were motivated to research these questions not just to improve Lighthouse's block profitability, but also to head off systemic risks. If it were possible to produce vastly better blocks by expending more compute, then large staking providers would have an advantage over smaller stakers and the resulting economy of scale would trend towards centralisation. Similarly if block producers were incentivised to spend more time building their blocks then this could lead to block propagation delays which hurt the network.
Results
Satalia produced three beautiful reports on these questions, with engineering input from us.
The first report is a formal description of the problem in mathematical language, abstracting over the Ethereum-specific details. We hope this will be beneficial to other researchers.
The second report is a description of two algorithms for solving the Attestation Aggregation and Packing Problem (AAPP) optimally.
Finally, the third report contains the answers to our original research questions as well as discussions for future exploration:
We got a positive result in answer to our first research question – it is possible to solve most instances optimally in <500ms! The runtime of Satalia's MIP algorithm was less than 500ms for the majority of instances, and less than 1 second for 98.6% of instances. See Section 3.2, Figure 1 in the report for details.
We also got a result in favour of Lighthouse's current greedy algorithm. The greedy algorithm produced an optimal solution for 52.3% of the instances tested, and produced a solution within 5% of optimal for 99.97% of instances tested. See Section 3.1 in the report.
Interestingly, the worst solution produced by the greedy algorithm fell short of the theoretical lower bound for the Weighted Maximum Coverage Problem (WMCP), with quality 56.54% of optimal. The lower bound for WMCP is $1 - 1/e \approx 63.2\%$, so this is a significant difference. We believe that this is due to the aggregation phase of our algorithm, which determines the input to the approximation algorithm we use for WMCP. Our current aggregation algorithm opportunistically aggregates attestations as they are added to the pool and does not have a proven lower bound for its approximation ratio.
In the cases where the greedy algorithm fell significantly short of optimal, the exact solver's runtime also increased sharply, hitting 2.6 seconds for the instance on which the greedy algorithm performed most poorly. The greatest runtime measured for the MIP algorithm was 6.1 seconds. For production use, Satalia have outlined two improvements over the MIP algorithm which would likely have better runtime performance. One is a problem decomposition, exploiting the fact that attestations from different committees can be packed separately. The other is a specialised branch & bound algorithm to replace the MIP solver. We think one or both of these approaches would yield an exact approach suitable for production, the implementation of which would be a matter of engineering work on our part.
For the full data on all of the 51097 instances solved, see:
- 04. Satalia Block Packing Results (Google Sheets)
Conclusion
Given the near-optimal performance of the greedy algorithm in the majority of cases, we do not believe that attestation packing represents a significant centralisation risk for Ethereum. A block proposer in possession of a fast exact solver stands to produce blocks that are only marginally better than those produced by the greedy algorithm, and will only see benefits greater than 5% in a minute number of cases (0.03%).
For this reason we have decided not to push ahead with an exact algorithm in production in the immediate future. The engineering effort required to build a consistently fast exact implementation is substantial, and not something we can devote resources to right now. Instead we've decided to pursue several related efforts which we believe will have greater impact:
- Improving the speed of our existing greedy algorithm: sigp/lighthouse#3312.
- Improving Lighthouse's interaction with builders, making MEV more accessible and censorship-resistant: sigp/lighthouse#builder-API.
- Adopting the improvements to aggregation to improve the greedy algorithm's worst-case performance up to the lower bound for WMCP: sigp/lighthouse#3733.
- Increasing the transparency surrounding block rewards by standardising and implementing new APIs: sigp/lighthouse#3661.
This isn't to say that we won't revisit optimal attestation packing at some point. Undertaking this work provided us with immensely useful knowledge about the problem space which will be relevant whenever this problem is revisited.
We are immensely grateful to Satalia for a robust and intellectually stimulating collaboration. Specifically we'd like to thank Judita Maslauskaitė, Tommaso Urli, Benedikt Posch and Stanislovas Kujalis. Their work helped us achieve a breakthrough on a difficult problem that has existed since the genesis of the Ethereum beacon chain.
We now feel confident knowing that our existing software is already close to optimal, and that there are no systemic risks lurking in the shadows.