Part 3: Annotated Specification

Fork Choice

Introduction

The beacon chain's fork choice is documented separately from the main state transition specification. Like the main specification, the fork choice spec is incremental, with later versions specifying only the changes since the previous version. When annotating the main spec I combined the incremental versions into a single up-to-date document. In the following, however, I will deal separately with the original Phase 0 fork choice and the incremental Bellatrix fork choice update as the latter mainly introduced one-off functionality specific to the Merge transition. There were no changes to fork choice in the Altair upgrade.

What's a fork choice?

As described in the introduction to consensus, a fork choice rule is the means by which a node decides, given the information available to it, which block is the "best" head of the chain. A good fork choice rule results in the network of nodes eventually converging on the same canonical chain: it is able to resolve forks consistently, even under a degree of faulty or adversarial behaviour.

Ethereum's proof of stake consensus introduces a Store object that contains all the data necessary for determining a best head. A node's Store is the "source of truth" for its fork choice rule. In classical consensus terms it is a node's local view: all the relevant information that a node has about the network state. The fork choice rule can be characterised as a function, GetHead(Store)HeadBlock\text{GetHead}(\text{Store}) \rightarrow \text{HeadBlock}.

During the Merge event, the beacon chain's fork choice was temporarily augmented to be able to consider blocks on the Eth1 chain, in order to agree which (of potentially multiple candidates) would become the terminal proof of work block.

Overview

Ethereum's fork choice comprises the LMD GHOST fork choice rule, modified by (constrained by) the Casper FFG fork choice rule. The Casper FFG rule modifies the LMD GHOST fork choice by only allowing blocks descended from the last finalised1 checkpoint to be candidates for the chain head. All earlier branches are effectively pruned out of a node's local view of the network state.

Diagram of a block tree showing that Casper FFG finalises the early chain up to a checkpoint and LMD GHOST handles fork choice after that

Casper FFG's role is to finalise a checkpoint. History prior to the finalised checkpoint is a linear chain of blocks with all branches pruned away. LMD GHOST is used to select the best head block at any time. LMD GHOST is constrained by Casper FFG in that it operates on the block tree only after the finalised checkpoint.

This combination has come to be known as "Gasper", and appears to be relatively simple at first sight. However, the emergence of various edge cases, and a relentless stream of potential attacks has led third party researchers to declare that "The Gasper protocol is complex". And that was said before implementing many of the fixes that we'll be reviewing in the following sections. Vitalik himself has written that

The "interface" between Casper FFG finalization and LMD GHOST fork choice is a source of significant complexity, leading to a number of attacks that have required fairly complicated patches to fix, with more weaknesses being regularly discovered.

Despite all this, we are happily running Ethereum on top of the Gasper protocol today. We continue to incrementally add defences against known attacks, and one day we may move on from Gasper entirely - perhaps to a single slot finality protocol, or to Casper CBC. Meanwhile, Gasper is proving to be "good enough" in practice.2

Scope and terminology

These fork choice specification documents don't cover the whole mechanism. They are largely concerned only with the LMD GHOST fork choice; the Casper FFG side of things (justification and finalisation) is dealt with in the main state-transition specification.

The terms attestation, vote, and message appear frequently. An attestation is a collection of three votes: a vote for a source checkpoint, a vote for a target checkpoint, and a vote for the a block. The source and target votes are used by Casper FFG, and the head vote is used by LMD GHOST. We will mostly be concerned with head votes in the following sections, except when stated otherwise. LMD GHOST head votes are also called messages, being the "M" in "LMD".

Where we discuss attestations, they can be a single attestation from one validator, or aggregate attestations containing the attestations of multiple validators that made the same set of votes. It will be clear from the context which of these applies.

History

Proof of Stake Ethereum has a long history that we shall review elsewhere. The following milestones are significant for the current Casper FFG plus LMD GHOST implementation.

Vitalik published the original mini-spec for the beacon chain's proof of stake consensus on July 31st 2018, shortly after we had abandoned prior designs for moving Ethereum to PoS. The initial design used IMD GHOST (Immediate Message Driven GHOST) in which attestations have a limited lifetime in the fork choice3. IMD GHOST was changed to LMD GHOST (Latest Message Driven GHOST) in November 2018 due to concerns about the convergence properties of IMD.

The initial fork choice spec was published to GitHub in April 2019, numbering a mere 96 lines. The current Phase 0 specification has 488 lines.

Various issues have caused the fork choice specification to balloon in complexity.

In August 2019, a "decoy flip-flop attack" on LMD GHOST was identified that could be used by an adversary to delay finalisation (for a limited period of time). The defence against this is to add a check that newly considered attestations are from either the current or previous epoch only. We'll cover this under validate_on_attestation().

In September 2019 a "bouncing attack" on Casper FFG was identified that could delay finalisation indefinitely. The suggested fix involves only allowing the fork choice's justified checkpoint to be updated during the early part of an epoch. This was implemented in the consensus specs in November, 2019. We'll be devoting a whole section to the bouncing attack.

In July 2021, an edge case was identified in which (if 1/3 of validators were prepared to be slashed) the invariant that the store's justified checkpoint must be a descendant of the finalised checkpoint could become violated. A fix to the on_tick() handler was implemented to maintain the invariant.

In November 2021, some overly complicated logic was identified in the on_block() handler that could lead to the Store retaining inconsistent finalised and justified checkpoints, which would in turn cause filter_block_tree() to fail. Over one third of validators would have had to be slashed to trigger the fault, but the resulting fix turned out to be a nice simplification in any case.

Proposer boost was also added in November 2021. This is a defence against potential balancing attacks on LMD GHOST that could prevent Casper FFG from finalising. We'll cover this in detail in the proposer boost section.

A new type of balancing attack was published in January 2022 that relies on the attacker's validators making equivocating attestations (multiple different attestations at the same slot). To counter this, a defence against equivocating indices was added in March 2022. We'll discuss this when we get to the on_attester_slashing() handler.

We will study each of these in more detail as we work through the fork choice specification in the following two sections.

Note that a substantial rewrite of the fork choice specification is in-flight. The rewrite removes the bouncing attack fix and introduces the "pulled tips" defence against a new attack, among other things. I will update the following sections when the changes have been released as part of the Capella upgrade.


  1. I'm simplifying here. LMD GHOST can only consider descendants of the last justified checkpoint at any one time. But the last justified checkpoint can change. LMD GHOST will never consider branches from before the last finalised checkpoint. More on this later.
  2. Appendix C.1 of the Goldfish, "No More Attacks on Proof-of-Stake Ethereum?" paper is a useful overview of known weaknesses of Gasper consensus.
  3. If I've understood correctly. Traces of IMD GHOST are difficult to find these days, and that's probably for the better.

Created by Ben Edgington. Licensed under CC BY-SA 4.0. Published 2023-05-22 09:59 UTC. Commit 9788c11.