EPF Update 9

This update will cover the current state of the new block packing methods for Lighthouse. With the assistance of Michael Sproul we have an optimality preserving aggregation strategy implemented. We are currently testing and optimizing it's performance. This comes as a pretty significant change to the block packing logic so we must ensure that everything functions correctly with good performance. Michael set an initial performance goal as attestation packing taking <50ms. To approach this we needed to profile the code to see what parts were taking the longest. I found that the Bron-Kerbosch algorithm was taking the longest followed by the greedy maximum coverage algorithm. After that efficiently removing aggregated attestations that have attester sets that are subsets of some other attestation in the set.

Given that information I began to look into how to optimize the implementation of the Bron-Kerbosch algorithm. I didn't find any great way to improve things. Thankfully the aggregation requirements ensure that no two attestations with different attestation data can be aggregated, so we are able to apply parallel computing techniques to improve performance. Using rayon's ParallelIterator primitive we were able to reduce the average packing time from about 89ms. Down to ~35ms. To use the primitive took resturcuring the code to facilitate parallel compute.

Also in the test repo I've implemented the "enumeration" approach which is an exact approach to the weighted maximum coverage problem. It uses a branch and bound algorithm. I'm sure some of it could be optimized but for now its quite slow. The structure of the algorithm lends itself to parallel compute so it should be able to improve things fairly significantly. However the current implentation is recursive making it less straightforward to employ rayon's primitives.
I also implemented an approximate algorithm for the weighted maximum coverage problem that leverages the "decomposition" approach plus the a k-greedy algorithm. It allows us to choose from combinations of attestations to avoid picking atttestations that have an attester set that collide with other attestations.

In conclusion, we are still figuring out the best approach to packing. We've implemented different approaches and are testing performance vs. reward. The exact approaches to me do not seem to be the best way to solve the problem given the tradeoffs.