This week I continued researching the attestation aggregation and packing problem (AAPP). The difference between this week and the last is that I began digging into the implementation details of both the current greedy approach and the proposed maximum clique enumeration approach. Additionally, I've started integrating the new approach into the Lighthouse consensus client: https://github.com/sigp/lighthouse/pull/4507. The PR so far is really just porting over code from the nightly Rust compiler to the stable one. Most of the work will be making Lighthouse's data structures to play nice with the Bron-Kerbosch algorithm implementation and then testing to ensure there is no regression in block rewards and other metrics. Note that this is just phase 1 of the problem after aggregation is solved we (Ankur and I) are going to tackle the max coverage problem. We got the greenlight from the SigP crew to work towards it! So I'm focusing on aggregation then will move to packing once it's complete.

Here's an outline of what needs to be done. Michael Sproul provided the following overview:

1. Add the Bron-Kerbosch alg in its own crate
2. Modify the naive aggregation pool so that it retains the unaggregated attestations. Or, modify unaggregated attestation processing so that unaggregated attestations also get sent immediately to the op pool.
3. Rework the attestation storage in the op pool so that it can do max-clique enumeration on the stored attestations. Use the output of max-clique enumeration (on a per-attestation-data basis) as the input to max coverage.
4. Set up some nodes on mainnet and/or testnets to produce blocks every slot using blockdreamer. We can measure the profitability of these blocks to see if we can outcompete stable Lighthouse, as well as benchmark the time it takes to produce each block.

Since 1 was already accomplished I moved on to step 2. The naive aggregation pool in Lighthouse is a field of the BeaconChain struct which takes in unaggregated attestations. On insertion, attestations with AttestationData that has not been seen before but is valid will be added as another entry in the pool. Otherwise, assuming they are valid, they are aggregated immediately with the member of the pool that shares the same AttestationData. This process I assume is why it's called the 'naive' aggregation pool but I don't think that is explicitly said anywhere. This process can make it so the aggregated attestation in the pool cannot be aggregated with some other attestation if they share even one signer. This definitely has nice properties though and works really well in practice. As number 2 presents two options, I investigated them. I think the second option is preferable but I haven't ran that by anyone else. So instead of maintaining the unaggregated attestations int the naive_aggregation_pool we will just send them to the operation pool after processing them for validity.

One thing that I noticed about the way lighthouse handles their attestations currently is that it makes great use of incremental processess. Their greedy approach to aggregation allows them to spread out the computation over time whenever they receive a new aggregated attestation or unaggregated attestation. I am interested to see how the Bron-Kerbosch approach will fare comparatively, since it works on static graphs. I did find this paper on incremental maintenance of maximal cliqes in a dynamic graph: https://link.springer.com/article/10.1007/s00778-019-00540-5. [Warning: I only read the abstract]. It's not clear to me whether something like that would be beneficial but it's pretty interesting.

The greedy aggregation approach is pretty much fully described in the following few lines of code:

    pub fn insert(&mut self, attestation: Attestation<T>, attesting_indices: Vec<u64>) {
        let SplitAttestation {
            checkpoint,
            data,
            indexed,
        } = SplitAttestation::new(attestation, attesting_indices);

        let attestation_map = self
            .checkpoint_map
            .entry(checkpoint)
            .or_insert_with(AttestationDataMap::default);
        let attestations = attestation_map
            .attestations
            .entry(data)
            .or_insert_with(Vec::new);

        let mut aggregated = false;
        for existing_attestation in attestations.iter_mut() {
            if existing_attestation.signers_disjoint_from(&indexed) {
                existing_attestation.aggregate(&indexed);
                aggregated = true;
            } else if *existing_attestation == indexed {
                aggregated = true;
            }
        }

        if !aggregated {
            attestations.push(indexed);
        }
    }

Whenever a new attestation is to be inserted in to the operation pool the function above runs. It basically says aggregate the new attestation with all existing attestations that are compatible. If it has no compatable existing attestations then add the attestation directly to the pool.

In conclusion I started to understand the technical requirements to integrate the maximum clique enumeration approach to aggregation and decided on the current work split with my collaborator. Note that my project exploration was done in Week 0 so that I could take care of some IRL stuff this week.

Week 2 I will try to work through step 3. At which point code review will ensue. Thanks for reading.