Check justified checkpoint root in fork choice

[paulhauner]

Description

Credits to @hwwhww for bringing this to our attention.

In fork choice, Lighthouse checks checkpoint epochs:

lighthouse/consensus/proto_array/src/proto_array.rs

Lines 423 to 433 in fff01b2

	/// This is the equivalent to the `filter_block_tree` function in the eth2 spec:
	///
	/// https://github.com/ethereum/eth2.0-specs/blob/v0.10.0/specs/phase0/fork-choice.md#filter_block_tree
	///
	/// Any node that has a different finalized or justified epoch should not be viable for the
	/// head.
	fn node_is_viable_for_head(&self, node: &ProtoNode) -> bool {
	(node.justified_epoch == self.justified_epoch || self.justified_epoch == Epoch::new(0))
	&& (node.finalized_epoch == self.finalized_epoch
	|| self.finalized_epoch == Epoch::new(0))
	}

However, the specification declares:

    correct_justified = (
        store.justified_checkpoint.epoch == GENESIS_EPOCH
        or head_state.current_justified_checkpoint == store.justified_checkpoint
    )
    correct_finalized = (
        store.finalized_checkpoint.epoch == GENESIS_EPOCH
        or head_state.finalized_checkpoint == store.finalized_checkpoint
    )

We have to check "checkpoints" are equal. So Lighthouse needs to update to check both epoch and root, not just the epoch.

Steps to resolve

In order to support this, we need to add the root information to the ProtoNode:

lighthouse/consensus/proto_array/src/proto_array.rs

Line 31 in fff01b2

pub justified_epoch: Epoch,

... and also the ProtoArray:

lighthouse/consensus/proto_array/src/proto_array.rs

Line 45 in fff01b2

pub justified_epoch: Epoch,

This will require a database migration. I think it should be fairly simple to migrate the ProtoNode, the roots of all the justified ancestors should be in the ProtoArray, so we should just be able to find the roots by just iterating backwards until we find the first ancestor where ancestor.slot <= start_slot(node.justified_epoch).

For ProtoArray, I think we should be able to get the root for the justified checkpoint from the ForkChoiceStore, which is persisted alongside it. We'd need to do some more reading to ensure there's a 1:1 relationship between these values, though.

[paulhauner]

I think @realbigsean is interested in taking this.

[paulhauner]

I think it should be fairly simple to migrate the ProtoNode, the roots of all the justified ancestors should be in the ProtoArray, so we should just be able to find the roots by just iterating backwards until we find the first ancestor where ancestor.slot <= start_slot(node.justified_epoch).

I was wrong here, specifically with "the roots of all the justified ancestors should be in the ProtoArray". That's true for the head block, but not necessarily earlier blocks (e.g., the finalized block). Earlier blocks may reference finalized blocks as their justified roots, meaning they are no longer in the ProtoArray.

With the "fairly simple" method unavailable, I can see two broad ways to implement this migration:

1. Full migration: read BeaconStates from the store during the migration to fill in the justified roots.
2. Partial migration: make the justified_root field an Option<Hash256>. All new blocks added to the proto-array get Some(root). When we do the check, only check the root if justified_root.is_some(). This means the migration happens gradually and we're full migrated once we flush out the proto-array with new blocks (probably a few epochs).

(1) is nice because it's one clean migration that's contained in database code and the actual fork choice code knows nothing of it. However, it means we need to do some database work on startup that might be a little slow. It also makes the assumption that we have the states for any block that's in ProtoArray, which I think is fine, but mo assumptions == mo problems.

(2) is nice because the migration code is blindingly simple. However, it means we need to add complexity to the actual fork choice code to handle the Option. It also puts is in a weird "partially updated" state that might have side-effects.

I'm not quite sure which way to go right now, but I'm going to post this so @realbigsean can have a read whilst I think more 🤔