Optimise unrealized FFG progression calculation

[paulhauner]

Description

When applying a block to fork choice (i.e., adding the block to our in-memory block-tree that we use to select the canonical head), we run a subset of per_epoch_processing code to determine the "unrealized" justified and finalized checkpoints (a.k.a unrealized FFG checkpoints):

lighthouse/consensus/fork_choice/src/fork_choice.rs

Lines 855 to 890 in 319cc61

	let (unrealized_justified_checkpoint, unrealized_finalized_checkpoint) =
	if let Some((parent_justified, parent_finalized)) = parent_checkpoints {
	(parent_justified, parent_finalized)
	} else {
	let justification_and_finalization_state = match block {
	BeaconBlockRef::Capella(_)
	| BeaconBlockRef::Merge(_)
	| BeaconBlockRef::Altair(_) => {
	let participation_cache =
	per_epoch_processing::altair::ParticipationCache::new(state, spec)
	.map_err(Error::ParticipationCacheBuild)?;
	per_epoch_processing::altair::process_justification_and_finalization(
	state,
	&participation_cache,
	)?
	}
	BeaconBlockRef::Base(_) => {
	let mut validator_statuses =
	per_epoch_processing::base::ValidatorStatuses::new(state, spec)
	.map_err(Error::ValidatorStatuses)?;
	validator_statuses
	.process_attestations(state)
	.map_err(Error::ValidatorStatuses)?;
	per_epoch_processing::base::process_justification_and_finalization(
	state,
	&validator_statuses.total_balances,
	spec,
	)?
	}
	};
	(
	justification_and_finalization_state.current_justified_checkpoint(),
	justification_and_finalization_state.finalized_checkpoint(),
	)
	};

Intermission for background info

FFG stands for "friendly finality gadget" and it's the method we use for determining finality on the beacon chain. A quick overview goes something like this when we're processing a block:

• A block has attestations inside it.
• When a block is applied to a state via process_block, we call process_attestation for each attestation.
• When we process an attestation we update either state.current_epoch_participation or state.previous_epoch_participation with some boolean values for each validator included in that attestation:
  • Did the attestation correctly attest to the "source" (see TIMELY_SOURCE_FLAG_INDEX)
  • Did the attestation correctly attest to the "target" (see TIMELY_TARGET_FLAG_INDEX)
  • Did the attestation correctly attest to the "head" (see TIMELY_HEAD_FLAG_INDEX)

Then, when at the end of each epoch we run process_epoch which, in turn calls process_justification_and_finalization which then goes through the state.current_epoch_participation and state.previous_epoch_participation lists and reduces them into three gwei balances:

• total_active_balance: the sum of the effective balances of all active validators.
• previous_target_balance: the subset of total_active_balance which received a TIMELY_TARGET_FLAG_INDEX for an attestation from the previous epoch.
• current_target_balance: the subset of total_active_balance which received a TIMELY_TARGET_FLAG_INDEX for an attestation from the current epoch.

Then, we put those three values into weigh_justification_and_finalization to determine if we have enough validator weight voting for the target that we can progress (i.e. increment) the state.current_justified_checkpoint or the state.finalized_checkpoint.

We call the state.current_justified_checkpoint and state.finalized_checkpoint the realized FFG checkpoints, because there also implicitly exists the unrealized FFG checkpoints. Let's look at those now.

Since we only need 2/3rds of validators voting to the target in the current epoch to increase the state.current_justified_checkpoint, it follows that we could accrue all those votes in the first ~2/3rd blocks of an epoch even if the rest of the blocks in the epoch were skipped. When we have processed enough blocks with enough attestations to increase our FFG checkpoints during process_epoch even if we never process another block, then we say that we have "unrealized" FFG progression.

It turns out that this unrealized FFG progression is quite important and if we're choosing between two blocks to be the head of the canonical chain and one of them has higher FFG progression than another, then we probably want to pick that one.

Back to the optimisation

So, what we're doing each time we apply a block to fork choice is converting the state.previous_epoch_participation and state.current_epoch_participation values into gwei values and then checking to see if they're enough to progress our FFG checkpoints.

This is wasteful since we're actually doing repeat iterations over the epoch participation arrays for each block we receive. What we could do is add a cache onto the BeaconState and then maintain an additional three gwei values to track the running total_active_balance, previous_target_balance and current_target_balance that we would usually compute at the end of the epoch. I believe we would update those running values when we're iterating through the attesting indices in process_attestation.

I see the main tasks with this implementation being:

1. Implementing the incremental balance calculation and testing it.
2. Figuring out how to neatly attach the cache to the BeaconState and make sure it's available for fork choice.
3. Handling the fact that if we decide to write this cache to disk, then any states that are already in the database won't have the cache.
   1. If we don't decide to write the cache to the DB, we'll have to handle the case where we load a mid-epoch state from disk which is cache-less.
4. Handling the cases when the cache isn't available to fork choice (we probably just revert back to the current method).

I believe that all the other clients (definitely Teku and Prysm) have this implemented, so perhaps reading their impls would be a good place to start.

[paulhauner]

I've run out of time to keep writing up this one, there might be some things I've missed but I think this is a good start!

CC @jimmygchen, who has showed interest ☺️

[int88]

@jimmygchen Have you started work on this?

If you have not and don't have enough time to do, I'd like to try :)

[jimmygchen]

Hi @int88 I haven't started work on this - please feel free to give it a try.
I'm hoping to spend some time understanding this in the next week, so let me know if you run into any issues!

[int88]

Update:

It seems that prysm has not done relevant optimiazation. BeaconState has no cache and still calculates based on Epoch Participation every time.

https://github.com/prysmaticlabs/prysm/blob/f6764fe62b9ca43d5777e3c476a9620c7207a940/beacon-chain/state/state-native/getters_participation.go#L44-L60

[potuz]

This seems to be false, the Beacon state is passed in memory to forlchoice and I've benchmarked the loop at 5ms last year for the merge. In addition we don't bother to compute this during the first 2/3 of the epoch and neither if the parent block already justified, so in practice this means that the loop is executed only once per epoch. This gives a cost of 5ms per Epoch which seems acceptable

[jimmygchen]

Hi @int88!

Just wanted to check if you're still interested in working on this one - no worries if you haven't started or busy with something else. I might take a look at this one soon, as it's kind of related to the issue @michaelsproul linked above, and we're looking to get this implemented soon. Thanks!

[int88]

As @potuz mentioned, it may not be a optimization point, so I didnt' further investigate it.

If it's urgent to fix this issue, please go ahead. I may not be able to implement it so quickly 😄 @jimmygchen

[jimmygchen]

As @potuz mentioned, it may not be a optimization point, so I didnt' further investigate it.

If it's urgent to fix this issue, please go ahead. I may not be able to implement it so quickly 😄 @jimmygchen

Thanks @int88 !