EPF Update 7

During the past couple of weeks I have pivoted to focusing on the enumeration approach as well as the decomposition approach. In my previous update I outlined these approaches at a high level. Here I will go in more detail. The majority of the work I did recently focused on learning more about dynamic programming, branch and bound algorithms, implementing decomposition in the test repository, and fixing an annoying bug in the attestation aggregation branch.

The dynamic programming approach to the attestation packing problem separates the problem into a main problem and sub-problems. The sub-problems will be very similar to ones you know if you have kept up with these updates. The synopsis being given some data

$d_k$ and a set maximum number of attestations

$n$ the function

$g(d_k,n)$ computes the weighted maximum coverage over the set of maximally aggregated attestations for the particular data. In practice the set of maximally aggregated attestations for the data is small. With an average around 2, maximum (over a small data set) of 13, and a minimum of 1. From here you can choose any exact method to solve this NP-hard subproblem. In the enumeration approach we chose to employ a branch and bound algorithm. This is currently unimplemented, but I believe this will be an improvement to the MIP solver approach in terms of performance because we can use a greedy approach to calculate an initial value to bound the tree search procedure. The greedy approach will often be the optimal result from what we have seen in practice from testing Lighthouse’s current block proposer rewards. This will allow us to use an approximation of the value of the remaining leaves to reduce the size of the tree and hence decrease the runtime.

The main problem is where the dynamic programming comes in to play. Satalia defined the approach as follows:
Let

$k$ be a non-negative integer and

$m$ be the maximum number of attestations that can be included in the block. Then the function f(k, m) computes the optimal reward given that the first k data have been taken into account. The function

$f$ is defined recursively with the base case being when k is zero.

Base case:

​​​​f(0,m) = {} the empty set
​​​​R(f(0,m)) = 0

Non-base case:

​f(k, m) = argmax (q \in {0, …, min(m, |g(k, m)|)}} R(f(k-1, m-q) \union g(d_k, q))$

In other words, the optimal packing for k data is the best packing for k – 1 data with the capacity decreased by q in union with the subproblem solved with a capacity of q. We choose q such that the reward is maximized.

Conclusion

I’ve implemented the decomposition approach while using the the MIP solver to solve the subproblem. I still need to test the algorithm. During testing the attestation aggregation branch we saw a degrading of proposer rewards with reference to the greedy aggregation approach. I believe I have since found the issue. We will do another sequence of testing to see if the problem has bee solved correctly. Then I will continue implementing the enumeration approach on top rhe decomposition work I’ve already done.