I noted that Geemo and acidicHydrogen already started working on it.

What is attestation packing problem?

Attestation packing is the process by which Ethereum consensus clients choose attestations to include in blocks. The block proposer is only able to include a maximum of 128 attestations in a single block.

BLS cryptography allows to aggregate many signatures into a single one. When these signatures are of the same attestation, we are able to aggregate all those individual attestations together.

Every epoch certain validators are assigned to be aggregators. They have to gather all attestations they see that are compatible with its own attestation, aggregate them and propagating them to the network. Also the block proposer can further aggregate attestations he receives.

<aside> ⚙ We can even aggregate other aggregates, provided that they don't overlap, that is, a signature isn't aggregated twice.

</aside>

Since there is an upper limit on the number of attestations in a block (128), proposers have to decide which aggregates to include in order to maximize the reward.

This problem is known as attestation packing.

Possible Sources of Inefficiencies

⇒ a.k.a. why participation rate (# ETH that vote during an epoch) is not 100%

  1. Validators are offline.
  2. Network inefficiencies such as attestations being insufficiently propagated.
  3. The block proposer excludes the attestation during the packing process due to a lack of block space or inefficiencies in its block packing algorithm.

NP-hard Problem

Attestation packing is known to be a NP-hard problem.

Lighthouse uses a greedy approximation algorithm that runs in less than ~250ms on average hardware.

Teamed up with Satalia

Lighthouse teamed up with Satalia in order to find out: