I think there is an efficient way to solve the Aggregation Attestation problem (AAP) optimally, not just find a good approximation. The maximum-weight independent set (MWIS) problem (not to be confused with the maximal independent set):
(1) captures the disjoint requirement of AAP
(2) captures the fact that not all attestations are equal by virtue of the weight attribute which maps to the total number of signatures are there in an attestation
(3) is NP-hard but admits a polynomial-time dynamic programming algorithm (DPA) assuming reasonable bounds on the total number of attestations (indeed bounded in ETH2)
(4) its DPA is well suited for the way attestations find their way in the subnet, in that clients can keep updating the DPA table(s) and memoizing partial solutions while still listening for more attestations on the wire.
Reduction from AAP to MWIS:
-
Construct a graph by creating a vertex v_n for each attestation X_n =(x_1x_2...x_c), where c is the number of validators per committee (=
MAX_VALIDATORS_PER_COMMITTEEin ETH2 specs) and x_i\in \{0,1\} =1 if X contains a signature from validator i and 0 otherwise (i.e. x_i=1 \Rightarrow the i\text{-th} bit inaggregation_bitsis 1). The “n” is a counter local to each aggregating validator client, so e.g. X_{n+1} is the attestation a client received on the wire after X_n (note: there will be 16 designated aggregators perslotper committee). -
Label each vertex v_n with weight w_n where w_n=H(X_n) is the Hamming weight of attestation X_n, i.e. it’s the total number of signatures in the attestation.
-
Create an edge (v_n, v_m) \forall m > n iff H(X_n \wedge X_m) >0 for attestaions X_n and X_m, i.e. there’s an edge between any two attestations that have at least one BLS signature in common.
The graph is constructed incrementally, everytime an attestation arrives on the wire it is added as a vertex and then edges from older overlapping attestations are connected to it.
Example:
The following graph corresponds to the sample attestations A, B, and C in the OP above:
There is an edge from A \rightarrow C because they overlap on the 4th bit.
Suppose a new attestation D=(01100) arrives on the wire, then the graph becomes:
Thus far the DP algo has memoized these potential aggregations:
| Aggregation candidate(s) | Total weight |
|---|---|
| {A} | 1 |
| {B} | 1 |
| {C} | 2 |
| {D} | 2 |
| {A, D} | 3 |
If now is the time to BLS-aggregate (reaching the end of slot) the client would aggregates A and D as the optimal choice. If two solutions are equally optimal clearly pick the one with less total attestations (less crypto).
The efficiency gain provided by the DPA is by virtue of the fact that when a new vertex v_j is appended to a path (v_i, v_k, ...,v_p, v_s), then we know that either we get more weight by including v_j and excluding v_s or vice versa (can’t be both), and in doing so we need not re-compute the best trajectory up until v_p … the DPA memoized that and we’re now just reusing it.
Proof AAP is NP-hard:
The reduction above from AAP to MWIS does not prove the NP-hardness of the AAP. For that we need to do the reverse: reduce a known NP-hard problem into AAP in polynomial time and logarithmic space.
Here is a reduction from Exat Cover (EC) to AAP. Given the universe set X=\{x_1, x_2, .., x_n\} and the set of subsets S=\{S_1, S_2, ..., S_k\} of an EC instance, create a corresponding AAP instance as follows:
- initialize |S| attestations A_1, A_2, ... A_k each as a sequence of n 0’s
- set the i\text{-th} bit in attestation A_j to 1 if x_i\in S_j
- solve this AAP, if the solution is empty return “no”, otherwise return the indices of attestations in the optimal solution as indices to the susbets in S in the optimal solution to the EC instance \blacksquare.
Expected performance:
In ETH2 the number of attestations floating around in a subnet during a given slot is bounded and so the optimal solution can be found and no attestation should go to waste.
Rough back of the envelop calculations: if there are 128 validators in the committee each broadcasting 10 unique attestations to every other validator, then 10*128^2*480 bytes/attestation \rightarrow a DPA table of size ~75mb in RAM. That’s a conservative upper bound though, because most of the time there are lots of duplicate attestations and (I think) clients aren’t simply flooding the subnet [1, 2, 3] with attestations (b/c pubsub in the gossip protocol), so 128^2 is an exaggeration.