Understanding Attestation Packing Efficiencies

Studying the Attestation Packing Problem and estimating packing efficiencies of historical beacon blocks.

Before we Start

Hi all!

This will be a bit different from our normal posts and is largely targeted towards other core Proof-of-Stake consensus developers/contributers.

Because of this, this write-up will need fairly detailed knowledge of the Proof-of-Stake upgrade coming to the Ethereum network and a strong grasp on the Ethereum Proof-of-Stake specification.

Familiarity with the concept of attestation packing would also be useful, but it will be brought in in this write-up.

Glossary

Background

Even before genesis of the Proof-of-Stake-secured Beacon Chain in December 2020, client teams had been working hard to tighten the performance of their software.

One such performance metric is validator reward efficiency; how much of the maximum possible reward is obtained.

Validator rewards are dependent on multiple different factors:

Inclusion Delay

Disclaimer: Rewards for certain attestation-related duties will be tweaked in the upcoming Altair hard-fork.

The first is the concept of inclusion delay. The more delayed your attestation was in being contained into a block, the smaller your reward will be. The minimum possible delay is 1 slot. This gives you the full possible reward. For every extra slot of delay, you begin to lose reward. If your inclusion is delayed by 2 slots, you receive 1/2 the possible reward. A delay of 3 slots is 1/3rd of the possible reward, and so on. If your validator does not produce an attestation or it is not contained within 32 slots, you will receive no reward.

Attestation Accuracy

The second is attestation accuracy. When attestations are made, they make a vote for the source, target and head of the beacon chain. If your validator attests with the majority, you will receive a reward proportional to the percentage of the validator set who also attest in the majority. If your validator fails to attest, or does not attest with the majority, you are penalized.

For example, if 99% of the validator set attests to the same source, target and head, those validators will receive 99% of the possible accuracy reward. The 1% of validators who did not attest with the majority are penalized accordingly.

Block Reward

Finally, the block reward is the reward given to the block proposer and is proportional to the number of attestations covered in the block. While there is no penalty for not proposing a block, the validator scheduled to propose the block misses out on the reward.

Helpful Links

For more information about rewards and penalties and how they are worked out see the following resources:

• https://kb.beaconcha.in/rewards-and-penalties
• https://consensys.net/blog/codefi/rewards-and-penalties-on-ethereum-20-phase-0/
• https://pintail.xyz/posts/beacon-chain-validator-rewards/
• https://pintail.xyz/posts/validator-rewards-in-practice/

The Attestation Packing Problem

While there is a maximum number of attestations that are allowed to be covered in any given block, BLS cryptographyWhen these signatures are of the same attestation, we are able to aggregate all those individual attestations in tandem. , allows us to 'aggregate' many signatures into a single signature.

This dramatically cuts the impact of attestations on the block size without compromising on consensus security, and allows us to support hundreds of thousands of validators.

Certain validators are assigned to be 'aggregators', and are responsible for collecting individual attestations in the pool, aggregating them and propagating them around the network. While these 'aggregators' are assigned to the task, block proposers themselves are also able to aggregate any compatible attestations as needed.

We can even aggregate other aggregates, gave that they don't overlap, that is, a signature isn't aggregated twice.

Since there is an upper limit on the number of aggregates which can be contained, proposers, hence, are unable to simply include every valid individual attestation that they receive, but rather must decide which aggregates to include and which to ignore to maximize block rewards. This is known as attestation packing.

When block space is limited, it is possible that certain aggregates need to be excluded. This means that a scenario could exist where an attestation is valid and known, but due to limited block space, it is not covered since the proposer is only aware of it in a suboptimal overlapping aggregate.

For example, look at the following aggregates:

Here each box denotes a validator's attestation (or lack thereof) as part of an aggregate for a given committee. The red coloured attestations are unique to each aggregate.

When it comes time to pack blocks full of attestations, if there is enough space, these aggregates could both be covered and so all attestations are accounted for.

Even so, if there is limited block space, there could be situations where it is optimal to only include 1 (which means missing out on the 3 unique attestations in the other aggregate) so that a different, more optimal, aggregate could be covered (perhaps one with 4 new unique attestations).

Of course if the proposer had access to other aggregates which contained those missing attestations and didn't overlap, or the unaggregated attestations themselves, they could be aggregated jointly to solve the problem.

Inefficiencies arise when the proposer does not have access to those attestations or if block space is limited and the packing algorithm isn't able to correctly establish which set of aggregates to include to keep the densest possible packing.

The problem for the proposer so, is to select a subset of the whole attestation set (aggregate and unaggregated) they have access to, such that they maximize their block reward.

This problem is an example of an Optimization Problem with an NP-hard complexity. It is very comparable in structure to certain kinds of optimization problems such as the Maximum Coverage and Set Cover problems.

A key feature of these types of problems is that they are widely believed to be incapable of being solved in polynomial time (and some may not even be decidable). In practice this necessitates the use of approximation algorithms which run fast but do not guarantee an optimal solution, or exact algorithms which are guaranteed to run reasonably fast if the structure of the input is constrained.

Jacek Sieka from the Nimbus team has written a regarding attestation packing and how has implemented improvements in their own codebase.

A more detailed discussion of the attestation packing problem can be found in a write-up by Victor Farazdagi from Prysmatic Labs.

A formal examination of such can be found For those that are curious, the attestation packing algorithm applied by is a greedy implementation of a weighted covering algorithm. here. Meridian Client3 from NFT Bounty also .

Throughout this write-up, we will not set out to find a new algorithm which is more efficient than the ones that are employed right now, still we will attempt to find out how efficient the current Ethereum clients are at packing attestations into blocks, how they compare and how much efficiency there is to be gained.

Possible Sources of Inefficiency

In a 200,000 validator network with an average participation rate of 99%, (the equivalent balance of) 2000 validators miss an attestation every epoch. First we should weigh the possible reasons why an attestation was not contained into a block. This could be for 3 different reasons:

1. Validator is offline, either in the short term due to an outage, or in the long term, perhaps the operator lost their keys, forgot about their node, etc.
2. Network inefficiencies such as attestations being insufficiently propagated such that they are never visible to the block proposer or only visible in a suboptimal aggregate.
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.

In an ideal case, we would be able to minimize or eliminate completely the effects of (1.) and (2.) and leave us with an overall block packing efficiency.

Even so, distinguishing between these sources is difficult and so to start, we will take a measure of efficiency as simply the ratio of attestations that were contained into a given block and the attestations that should have been available assuming perfect network conditions.

Note: This will not be a true measure of packing efficiency since it does not distinguish between the other types of inefficiencies. It will still give us a starting point from which to compare different implementations of the algorithms applied by different clients since averaged over a large enough dataset, the effects from (1.) and (2.) should affect the different clients equally, but any algorithmic differences will keep.

Method

The method applied to compute the set of available attestations is as follows:

• Query historical blocks via the NFT Bounty Beacon Node API to get the committee data for each epoch.
• Parse this data per slot to extract a list of the validators which are needed to attest in each slot.
• Pull historical blocks and extract the list of attestations which were packed into prior blocks.
• Remove the attestations that were covered in earlier blocks up to 32 slots ago.

So for slot $n$:

\begin{equation} \label{eq1} A_n = \bigcup_{i={n - 32}}^{n - 1} C_i - I_i \end{equation}

Where:
$A_n$ = The set of available attestations for slot $n$.
$C_i$ = All attestations as defined by the committee selection at slot $i$.
$I_i$ = The attestations that were contained in the block at slot $i$.

The attestation packing efficiency $E_n$ can then be computed as:

\begin{equation} \label{eq2} E_n = \frac{|I_n|}{|A_n|} \end{equation}

Here, $A_n$ is an optimistic set of the available attestations for slot $n$. This assumes that all possible attestations were submitted and seen by the proposer.

As went through eariler, due to network inefficiencies and offline validators, the computed efficiencies will be lower than the true efficiency. Even so we will (naively) work on the assumption that since Mainnet's participation rate can be as high as 99.7% the error from these effects is small.

Via a NFT Bounty tool called lcli, we can work out the efficiencies of all the slots in a particular epoch range.

lcli etl-block-efficiency --output /path/to/output.csv --start-epoch 30000 --end-epoch 30999

For more info about lcli, see the .

This pulls the committee data and blocks from those epochs, calculates the available and covered attestations along with proposer info per slot and saves the data into output.csv.

Via graffiti examination, the results can be separated into their a range of client implementations and staking pools. The vast majority of the proposers will be unidentifiable, still this should still give a good baseline for which to compare efficiencies.

Since this examination isn't about comparing particular clients against each other, client and pool identities have been obfuscated.

Results

^{Table 1: The average attestation packing efficiencies* of Mainnet across the whole chain history.}

From these results we can see that the computed efficiencies are by a wide margin lower than the average participation of the network. Still, by taking an average of the full history of chain, we begin to lose valuable information. We cannot see how clients tightened over time, whether that be from client upgrades, a better packing algorithm, or from tightened network conditions. In addition, some staking pools were not operating at Genesis, so for them, a direct comparison doesn't make sense as they will have inflated efficiencies.

Let's take Client 1 and separate the averages for every 10,000 epochs. This will showcase how Client 1's performance has raised over time.

^{Table 2: The average attestation packing efficiencies* of Client 1 across the whole chain history in 10,000 epoch intervals.}

Clearly significant improvements have been made since Genesis. Still these improvements could be on the network level or on the client level.

So rather than 10,000 epoch intervals, a better way to visualize the improvements over time is by fitting a LOWESS-smoothed trendline to the full data set.

^{Figure 1: Trends of the attestation packing efficiency* for each of the 4 major clients across the full chain history.}

Likewise for some major staking pools:

^{Figure 2: Trends of the attestation packing efficiency* for some major staking pools across the full chain history.}

From these results above, we do see a general trend upwards from all clients. The reasons are likely two fold:

1. As client teams push new releases, the overall performance of the software tightens and any changes to the packing algorithm, or related parts of the stack, tighten efficiency.
2. As clients run better on the network the overall network conditions tighten allowing for better attestation visibility and thus more efficient packing.

Even so, despite the improvements, the efficiency values are still far below what we want to be achieving in the best case.

Long-Standing Offline Validators

*As some of you may have realized, the participation rate is actually going to have a significant effect on the way we are right now calculating packing efficiencies.

The reason for this, is because offline validators have a disproportionate effect on the number of available attestations.

Look at the following example: there are 50,000 active validators on a network and 500 of the validators are perpetually offline. Assume attestations from online validators are being correctly submitted and propagated.

Via the above computations from equation \ref{eq1}, one might expect a maximum possible attestation packing efficiency of 99%. Even so, while blocks occur every slot, validators only attest once per epoch.

So at each slot there is only 1/32 of the total active validator set (in this example ~1563 validators) available to make new attestations in that slot. Still, all attestations that haven't been contained in a block and have been submitted within 32 slots are also available to be contained. This means the missing attestations from all 500 offline validators are 'available' in every slot and so take up a larger share of the available attestation set.

For the above example, assuming perfect attestation inclusion efficiency (discounting the offline validators), we'd expect computed efficiencies equal to:

$E \approx \frac{Covered}{Committees + Offline} \approx \frac{1563 * 0.99}{1563 + (\frac{31}{32} * 500)} \approx 76\%$

More as a rule:

\begin{equation} \label{eq3} E_P \approx \frac{\frac{1}{32} * P}{\frac{1}{32} + (\frac{31}{32} * (1-P))} \end{equation}

Where:
$E_P$ = Estimate of Computed Efficiency for P.
$P$ = Participation Rate.

Note: Here we are via participation rate as an estimate for the number of offline validators for a given epoch. In practice, other effects also impact participation rate, still offline validators are the largest.

Running the numbers for Mainnet, via a participation rate of 99.7%:

$E_P \approx \frac{\frac{1}{32} * 0.997}{\frac{1}{32} + (\frac{31}{32} * (1-0.997))} \approx 91.2\%$

For a testnet such as Pyrmont, which in most cases has a lower participation rate of around 89% at the time of writing we get:

$E_P \approx \frac{\frac{1}{32} * 0.89}{\frac{1}{32} + (\frac{31}{32} * (1-0.89))} \approx 20.2\%$

We can plot all the worked out block efficiencies for a small section of Pyrmont which allows us to get a clearer view (be sure to note the axes values):

^{Figure 4: Attestation packing efficiencies for a small section of Pyrmont.}

Note that the three bands (1st at ~20%, 2nd at ~32%, 3rd at ~42%) are due to skipped slots. If one slot is skipped, the next proposer is able to include further attestations and thus the proportion of 'available' attestations made up of offline validators is cut and the worked out 'efficiency' grows. The same takes place in the case of double skipped slots.

Likewise for Mainnet:

^{Figure 5: Attestation packing efficiencies for a small section of Mainnet.}

No distinct bands exist here because there are much fewer skip slots on Mainnet compared to Pyrmont.

Clearly offline validators are having a very large impact on the computed efficiencies. Still, remember that these computed efficiencies do not stand for a true measure of the attestation packing efficiency since the method does not differentiate between different sources of inefficiency. Further, when it comes to calculating packing efficiencies, it makes sense to only include attestations that the proposer actually had access to.

Over a large enough dataset, the results here are still valid for direct comparisons, still this data gives no indication of how well different attestation packing algorithms carry out.

To get a clearer picture of the actual effect of the algorithms applied in attestation packing, we need to minimize the effect of these offline validators.

Finding a Better Way

To correct for the presence of these offline validators, we can put in place a 'best-effort' attempt at detecting them which will allow us to remove them from the available attestation set.

By maintaining a list of validators which have had attestations contained in a window spanning the last 3 epochs, we can create an estimate for the number of long-standing offline validators at epoch $e$: $O_e$.

This allows us to work out a new normalized efficiency $N_n$ where:

\begin{equation} \label{eq4} N_n = \frac{|I_n|}{|A_n - O_e|} \end{equation}

To make sense of why a 3 epoch window was selected, look at the effect of changing the window size. As the window size decreases (say to 1 epoch), the size of $O_e$ increases, $|A_n - O_e|$ approaches $|I_n|$ and thus the normalized efficiencies would converge to 100%. Likewise, as the window raises to infinity, |$O_e$| approaches 0 and thus the normalized efficiencies would converge onto the original computed efficiencies. A window of 3 epochs was chosen as a reasonable middle ground.

Note that this will not be correct for nodes that go briefly offline for less than 3 epochs since that behaviour is indistinguishable from random network inefficiency (which also can't be corrected for via this method).

After normalizing for long-standing offline validators:

^{Figure 6: Normalized attestation packing efficiencies for a small section of Pyrmont.}

Further, the 3 distinct bands no longer exist which further supports this hypothesis. Compared to the original computed efficiencies, the shape is maintained, but efficiencies have risen by a wide margin indicating the majority of the effect was indeed from offline validators.

^{Figure 7: Normalized attestation packing efficiencies for a small section of Mainnet.}

Mainnet stays comparable, just with higher efficiencies. The trends below indicate the same effect, with normalized efficiencies being higher than the efficiencies originally computed.

^{Figure 8: Trends of the normalized attestation packing efficiency for each of the 4 major clients across the whole chain history.}

^{Figure 9: Trends of the normalized attestation packing efficiency for some major staking pools across the whole chain history.}

Findings

In this write-up, we covered the attestation packing problem and designed a naive method for estimating the packing efficiency of any given block. We found that this method was heavily impacted by offline validators, so much so that our computations were reporting an efficiency of ~20% for an average participation rate of ~89%.

We attempted to correct for this error by removing long-standing offline validators from the available attestation set. We found that by doing so, we largely decoupled our results from the participation rate as our worked out efficiencies jumped to ~95%.

Our data will still be affected by other types of inefficiency such as briefly offline validators and network latency, since these are not being corrected for as they are very difficult to distinguish. Because of this, it is likely the true packing efficiencies are even higher than what's being reported here.

What the data does show is that attestation packing efficiencies are in general quite high, at least >90% on average with some efficiencies reaching in excess of 97%.

Attestation Packing Efficiencies per Client

Certain clients seem consistently above the pack, indicating they could be via a different algorithm, or other extra optimizations to maximize their attestation coverage. As seen from the several figures presented in this write-up, all clients and pools maintain comparable levels of efficiency, all being within a few percentage points.

Overall though, from the data, there does not appear to be a significant discrepancy in attestation packing efficiencies between different clients.

The Limitations of Participation Rate

Another detail that these results show is the limitations of with Participation Rate as a network health metric.

Participation rate in it's simplest form, is just a count of the voting ETH across an epoch and is often employed as a metric for network health.

Participation rate (when worked out this way) is only interested in whether attestations were covered at all in a given epoch. This means for any given participation rate, a spectrum of scenarios exists between two extremes:

1. Attestations are covered as soon as possible ($delay = 1$)
   • In this case, the efficiencies of blocks are unaffected by late attestations.
2. Attestations are contained, but at the latest possible time ($delay \le 32$)
   • In this case, the efficiencies of every block has been impacted by late attestations.

In both cases, the participation rate is the same, since all those attestations are still being covered. Yet the health of the network is suffering due to late attestations.

Certainly, participation rate is a useful and consequential metric, even so care should be taken when with it to make inferences about the overall health of the network.

The Future of Attestation Packing

At present, most blocks are not full of attestations. This greatly simplifies the process of packing blocks since there are fewer instances where certain aggregates need to be excluded.

It stays to be seen whether the current efficiencies we are achieving are sustainable as the number of attestations called for to pack into a block raise.

Thank you!

If you made it this far, thank you for reading and I hope it was striking.

If you have any questions, feel free to reach out on the .

Happy Staking!