(block, epoch)-fork choice

[adiasg]

This PR contains a security fix for the finality delay attack outlined in this paper.

Finality Delay Attack

The execution of the attack involves temporary block withholding by the first few proposers in the epoch. At the end of the last withholding proposer's slot, all blocks are released. During slots in which blocks were withheld, honest attesters make FFG target votes for the last block of the previous epoch (which is "pulled up" to serve as the FFG checkpoint for the current epoch). After the blocks have been released, honest attesters make FFG target votes for the first block of the current epoch. During each slot, 1 / SLOTS_PER_EPOCH (= 3.125%) fraction of stake is attesting. So a 25% attacker needs to control the first 3 slots (= ceil((33.33 - 25) / 3.125)) of an epoch to successfully delay finality at the end of that epoch.

A brief description from the original paper:

The attack is possible because the fork choice allows for updating the head block, without any reorgs, in the following situation:

• the old head block points to an FFG target inconsistent with the one pointed to by the new head block, and
• there is more support for the old head block's FFG target than the new head block's FFG target.

This happens because the fork choice only calculates the LMD GHOST winner based on the support for each individual block. This PR prevents the attack by changing the block tree structure, and by also taking into account the support for the FFG target pointed to by each block.

For example, the below block hierarchy will be transformed into a block tree in the following manner:

Summary of Changes

• Block Tree Structure
  • Changed block tree graph so that nodes that point to inconsistent FFG targets are in separate branches. (Refer: BlockTreeNode & add_block_tree_node)
• LatestMessage Accounting
  • To calculate support for nodes in the block tree, LMD GHOST fork choice now interprets LatestMessage in the spirit of the attack fix. (Refer: get_latest_attesting_balance)
• Fork Choice Store & Functions
  • Updated the fork choice store & all functions for compatibility with the new block tree structure.
  • Added block tree updates to the on_block & on_attestation functions.
• Testing
  • Added tests for the finality delay attack.
  • Updated existing tests that use internal fork choice functions.

[adiasg]

Note: First merge PR #2301 into dev, then merge this into dev