HackMD
Introduction:
Hi, I’m Geemo. During the last EPF cohort, I worked on implementing some of the light client networking for the consensus client Lighthouse. I’m excited for cohort 4 to get started to continue learning and contributing! This time around my goal for each update is that the reader is able to understand my progress on topics discussed without significant domain knowledge. However, I will assume a basic understanding of Ethereum node related terminology and I’ll lean on other explanations for some in depth topics and I’ll only provide a high level commentary. This approach should make the updates a bit longer, but hopefully they’ll read better than what I did last time around.
Exploring Projects
The initial task for the program is to explore current protocol development topics and decide what to work on. The mentors of the program provided a list of projects here: https://github.com/eth-protocol-fellows/cohort-four/blob/master/projects/project-ideas.md. After looking over the list of projects two stood out:
- ePBS Design and Prototyping (By Potuz and Terrence of Prysm)
- Optimising Attestation Packing (By Michael Sproul of Lighthouse)
Proposer Builder Separation (PBS) has been a rich topic of research and development since the Merge. The out-of-protocol solution by Flashbots, MEV-boost, has been adopted by most of the validators on the network resulting in about 90% of blocks being built using the software. It allows block proposers to capture Maximal Extractable Value by outsourcing block building to a network of specialized entities that build highly profitable blocks. These blocks often include some form of arbitrage and their profitability is derived from ordering the transactions in the block. There has been much scrutiny around proposer builder separation after a vulnerability in MEV-boost was exploited to steal around $20 million from MEV bots. Additionally, the implementation hinges on centralized entities that have censored transaction in accordance with the list of OFAC sanctioned addresses. This weakens some of the core values of Ethereum of decentralization and censorship resistance.
Enshrined Proposer Builder Separation (ePBS) proposes to move the implementation of Proposer Builder Separation into the core protocol. Of course with any proposed expansion of the protocol, there is always a question of where the edge of the protocol should lie. PBS is clearly too well incentivized for validators to deny, yet it has serious implications for maintaining the usefulness of Ethereum. I think this is too sensitive an issue to rely on out-of-protocol solutions. The protocol has built up great specification tools and has valuable client diversity which keeps bugs localized to client. This article goes in depth on issues with relying on out-of-protocol solutions and proposes a path forward towards ePBS: https://ethresear.ch/t/why-enshrine-proposer-builder-separation-a-viable-path-to-epbs/15710. As it says, there is no expectation that MEV will be fully eliminated, so even if it can be limited it would still be useful for the protocol to have an approach to PBS.
This topic is intellectually very stimulating and I’d love to work on it at some point, but I’m not sure what value I can provide at the moment. Especially since the project is in Go, a programming language I have zero experience with.
On the other hand, implementing optimal attestation packing for the Lighthouse client is an interesting problem I feel I can tackle. The implementation touches on some optimization and graph theoretic topics that I’m excited to take on. Much of the research on the topic has already been done during a collaboration between Sigma Prime and Satalia. Not everything is mapped out however, because the solution provided runs too slow for production. I’m interested in finding ways to make the implementation practical while keeping it usable on low-resource devices. Since I plan on working on this I’ll go into more detail.
Optimizing Attestation Packing
Time in Ethereum is broken up into units of 12 seconds called slots. An epoch is 32 slots, or 384 seconds. Each slot one validator is selected as the block proposer. Each epoch, validators are broken into groups, called committees, with an associated slot to share an attestation. It represents the validator’s vote for what the correct chain is. This alone decreases the network usage at a given slot since not all validators attest at once. But there is a further reduction of network usage realized by a subset of the committee known as aggregators. Their role is to collect all the attestations from the committee and aggregate them, then broadcast the aggregated attestations on the network. The proposer of the next block then looks at these and decides which ones to store in the block. Each attestation has an associated reward for inclusion in the block. The goal of the Attestation Aggregation and Packing Problem (AAPP) is to select the attestations which result in the maximum reward. Satalia and Sigma Prime do a great job of formally describing AAPP in: https://lighthouse-blog.sigmaprime.io/docs/satalia-01-problem-definition.pdf.
Currently Lighthouse uses a greedy approximation algorithm, which on their 51097 test instances produces a solution within 5% of optimal for nearly all (99.97%) instances. This shows that the current approach is already quite good, but there is room to improve. And with financial reward on the line I think all validators would appreciate an optimal solution if possible within the time constraints. Especially the unlucky few that propose blocks around 40% off optimal with the current approach. Sigma Prime and Satalia analyze their greedy approach vs. the optimal solution in depth here: https://lighthouse-blog.sigmaprime.io/docs/satalia-03-results.pdf.
They outline an optimal solution for the problem in: https://lighthouse-blog.sigmaprime.io/docs/satalia-02-exact-approaches.pdf. The algorithm’s performance is analyzed in the paper comparing it against the greedy approach. The following is a brief description of their results in both.
The MIP Approach
This approach relies on breaking AAPP into two problems: an aggregation problem then a packing problem. The aggregation problem’s goal is to compute the set of attestations that are maximal with respect to the attester coverage. The approach used to compute the set uses a variation of the Bron-Kerbosch algorithm for enumerating maximal cliques in a graph. The graph we operate on takes all attestations available to the proposer as vertices and has an edge between two vertices if they are compatible for aggregation. Enumerating maximal cliques here is equivalent to computing the set of maximally aggregated attestations. But this a superset of our desired set. To see this, assume that the proposer’s set of available attestations include two aggregated attestations that are already maximally aggregated but they have the same attestation data and they have the same set of attesters except for one additional attester for one of them. They are both 1-vertex maximal cliques in the graph yet one has better attester coverage. They do not have an edge between them since their attester sets aren’t disjoint. We eliminate the sets with worse attester coverage to arrive at the desired set.
Now begins the packing problem, which seeks to optimize the reward the proposer receives by selectively picking elements of the previously constructed set. We cant select all of them in general since there is a limit on the number of attestations the proposer can include of 128. They formulate the optimization problem as a mixed integer program, because of the wide availability of MIP solvers. Solving directly in this way is not fast enough to be performed within the time constraints for some cases, but there are still options. There is some structure in the problem that can be used to reduce the size of the weighted maximum coverage problem. There is a lot of technical details that I am glossing over here so do read the paper I linked above if you are interested. The idea is to solve part of the problem using dynamic programming techniques while still using the MIP approach for the other parts. Their analysis of the solution showed that solving the aggregation problem is fast but the packing problem solution is relatively slow. The MIP approach can take more than 6 seconds to arrive at the optimal solution. This is not viable for direct use in production. Plus, relying on an MIP solver would add a dependency to Lighthouse. It remains to be seen if we can implement an optimal solution that can be used in the client.
Conclusion
I explored a couple of topics for the upcoming EPF program and I’ve started to look more deeply into the Attestation Aggregating and Packing Problem. Sigma Prime and Satalia wrote great documents and an implementation of their solution that will guide the project. We hope to bridge the gap between the offline implementation and a production ready one. I’m excited for the program to officially kick off and to meet the other contributors. Feedback of all kinds is welcome. Let me know if this is a good style for updates. The length will obvously vary.
