EPF Update #10

This update covers the process toward merging the optimality preserving atttestation aggregation process. It is slated to be included in the next update to Lighthouse v4.6.0.

One of the major things worked on during this period was including a new test to ensure that given a 'pairwise overlapping' set of attestations our packing strategy should result in 2 attestations that cover the attester set. By 'pairwise overlapping' we mean something like the following:

$$A=[[1,2,3,4],[3,4,5,6],[5,6,7,8],[7,8,9,10]]$$
Consider each set as an attestation with an attester set corresponding to the set. Allo of the attestations have the same AttestationData, so recall that the only other rule to determine if two attestations are able to be aggregated is: the attester sets must be disjoint. This turned out to be a very fruitful test because the number of cliques from a set generated in a similar way to the above is very large. Let's see why. Remember that our aggregation technique is graph based and enumerates all maximal cliques. So lets list the edges.

$$\begin{gathered} A=[a_1,a_2,...,a_i] \\ k=2^{i-1} \\ {a}_i=[k+1,k+2,k+3,k+4] \end{gathered}$$
Let's start with n = 5.

$$E=[(a_1,a_3),(a_1,a_4),(a_1,a_5),(a_2,a_4),(a_2,a_5),(a_3,a_5)]$$
Notice that this is a special type of graph namely a path complement graph. Therefore the number of cliques grows very fast. In particular we know the through a recursive formula the number of cliques in a graph a path complement graph with n vertices is:

$$numCliques(P_n^c)=numCliques(P_{n-2}^c)+numCliques(P_{n-3}^c)$$

To see this we take an equivalent view of the number of maximal independent sets(MISs) in the path graph. So consider a path graph with n vertices its clear that the path graph with n + 1 vertices will have at least as many as the one with n. There will be two types of MISs: MISs that include the new vertex and MISs that don't. We can see that the number of MISs that include the new vertex is just the number of MISs that don't include the previous vertex to the new one. We could say that's the number of MISs on

$P_{n-2}$. And the number of cliques that don't include the new vertex is from the same logic just pretend we the vertex previous the new one is the new one.

This is a special type of graph so we are able to answer the number of maximal cliques fairly simply however this is much harder for the general graph. So we can only give an upper bound of

$3^{n/3}$. As you can see this grows very fast and including the algorithm as is would be unacceptable. So we've decided to limit the number of vertices (attestations) that can be included in the algorithm. We chose to take only the best 16 attestations from each attestation data. By best we mean that they have the largest number of attesting indices set.

We don't expect that this will be an issue during normal operation because we very rarely have greater than 16 attestations for a particular attestation data.

Further we have made many optimizations to reduce the amount of allocation done. This effort has be spearheaded by Michael Sproul of Sigma Prime. As we prepare for things to be the aggregation techinque to be merged we have an average run time of about attestation packing time of about 30ms. One of the main changes was to use the persistent data strcture HashTrieSet. Additionally we implemented an optimization of the max cover algorithmm that only iterates a restricted set of attestations when updating the affective attester set.