Maximum clique enumeration for attestation aggregation in op pool #3733
Description
Description
Presently Lighthouse uses an opportunistic strategy for aggregating attestations added to the op pool. Any new attestation which can be aggregated with an existing one will be aggregated here:
lighthouse/beacon_node/operation_pool/src/attestation_storage.rs
Lines 163 to 174 in 6d5a2b5
In our collaboration with Satalia they prototyped a maximum clique enumeration algorithm for doing optimal aggregation. This issue is about adopting that optimal aggregation algorithm, while keeping our greedy algorithm for max coverage.
If you're interested in working on this issue DM me and I can provide a copy of the code written by Satalia. They wrote a pure Rust implementation of the Bron-Kerbosch algorithm which showed good performance during testing.
We would need to overhaul how we handle unaggregated attestations in the naive_aggregation_pool so that we keep single attestations unaggregated. This might be somewhat delicate.
Version
Lighthouse v3.2.1