Maximum clique enumeration for attestation aggregation in op pool

[michaelsproul]

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

	// Greedily aggregate the attestation with all existing attestations.
	// NOTE: this is sub-optimal and in future we will remove this in favour of max-clique
	// aggregation.
	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;
	}
	}

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

[ankurdubey521]

I plan to participate in the 4th cohort of the Ethereum Protocol Fellowship and am highly interested in picking this up as my project for the cohort.

[michaelsproul]

I think @GeemoCandama was also interested in working on this, would you two be open to working together?

[GeemoCandama]

Yes, I am interested in working on this.

[ankurdubey521]

I think @GeemoCandama was also interested in working on this, would you two be open to working together?

Excited to work on this together @GeemoCandama !

[PatStiles]

I'm also participating in the cohort and was thinking about working on this @ankurdubey521 @GeemoCandama are you guys down to collaborate?

[GeemoCandama]

@PatStiles I don't think more people working on this would be beneficial. I think we would have a too many cooks in the kitchen type situation. If you have a different idea feel free to message me on Discord though: @geemo_candama.

[PatStiles]

No worries, @michaelsproul I Dm'd you regarding other projects.

[michaelsproul]

Hey @PatStiles I'm on leave for the next 2 weeks, please reach out to @paulhauner