<- Last Update

The attestations aggreagtion problem can be broken down into two parts:

1. The aggregation stage, which takes existing attestations (unit and pre-aggregated) and produces the best possible aggregations subject to the constaints of BLS aggregation.
2. The packing stage, which selects
   $K$ aggreagates from the output of the first stage in-order to maximise the validator coverage. Here,
   $K=128$.

Me and Geemo agreed that the best way to split the tasks would be for him to handle the aggreagation stage, while I would be working on the packing stage. As I mentioned in my previous update, most of my research was targeted at the Aggregation Stage and the Bron-Kerbosh algorithm, so started afresh and began my research into the Packing Stage.

Existing Implementation

Most of the week was spent reading the code in the operation_pool folder, that deals with storing and processing attestations.
The existing implementation in lighthouse can be found here, which is an implementation of the Greedy Algorithm to the Max Coverage Problem. This approach guarantees the worst case outcome to be within

$1-{\displaystyle \frac{1}{e}}$ by ratio of the optimal solution, and has been working fairly well in practice so far.

Satalia's Solution

The solution presented by Satalia, is assuming a set

$A^{\ast }$ containing the maximal non-dominated attestations has been calculated by the Aggregation Stage, is to represent the Maximum Coverage problem as a Mixed Integer Problem, and then use a MIP solver (like CBC) to produce a solution. While this solution theoretically works, experimental results from Satalia showed that it many cases the solver might be too slow to be used in a production environment.

As suggested by the paper, one way to speed things up is to use a more sophisticated solver (like Gurobi), but these tend to be proprietary. This is something which might not be desirable, therfore this path is not explored.

The paper then explores two possibilities of speeding up this calculation.

1. The Decomposition Approach: On a high level, the paper describes a way to break down the main problem into a set of similar subproblems, and desribes a way to combine these subproblems' solutions to calculate the solution to the main problem, essentially Dynamic Programming. Since the MIP solver takes exponential time to calculate the solution, calculating the solutions to smaller sub-problems should theoretically result in saving a lot of time.
2. The Enumeration Approach: This describes a way to replace the MIP solver with a custom hand-tuned branch and bound solver.

Both of these approaches have not been experimentally tested yet, and this is what I plan to do in the upcoming weeks. The main challenge would be to come up with an implementation which can produce the optimal solution in a reasonable amount of time, in the best case on all systems but at the very least on higher end systems (through a flag).

-> Next Update