Casper FFG in Eth2.0

Thanks to Danny Ryan for discussion & review

My last post discussed the basic Casper Friendly Finality Gadget. The first part of this post will focus on the high-level details of the Casper FFG mechanism implementation in the Beacon Chain. The second part of this post will discuss the fork choice rule and other liveness considerations.

This post explains things directly from the Eth2.0 specifications. Wherever possible, links have been included to the relevant parameters & functions in the specification. Following these links is not required for understanding this article – they have only been included for reference.

Part 1 – Casper FFG Mechanism

Slots, Epochs, & Attestations

Slots: Time is divided into slots, and one new block can be proposed every slot. The current duration of a slot is SECONDS_PER_SLOT = 12. For each slot, a validator is assigned to produce a new block.

Epochs: The Casper FFG mechanism does not operate on the complete block tree, and instead considers only blocks from certain slots for the purposes of voting. This reduces the overhead of checking too many source-target pairs when trying to detect finality by looking at votes. With enough spaces between these special slots, new votes from a large majority of the validators are expected to be seen every time FFG finality checks are run. Slots are grouped together into epochs, with the current parameter being SLOTS_PER_EPOCH = 32, leading to each epoch being 6.4 minutes long. Only blocks at the boundaries of these epoch periods (“checkpoints” or “epoch boundary blocks (EBBs)”) are considered by the FFG mechanism.

Slots & Epochs when SLOTS_PER_EPOCH = 3
Blocks A, D, and G are checkpoints

Attestations: Attestations are Casper FFG votes which contain information such as the source & target blocks, slot number when attestation was made, identifier for the validator, etc. Attestations are broadcasted by validators to the p2p network, and are eventually picked up by a block producer to be packaged into blocks.

Changes to Casper FFG Mechanism

There is a change in the definition of finalization from the one mentioned in my previous post.

Finalization: A block B_0 is finalized if:

  • it is the genesis block, or
  • the following two conditions hold:
    • there is a sequence of checkpoints in the increasing order of slot number [B_0, B_1, ... , B_n] with n >= 1 such that all these blocks are in the same chain and are justified, and
    • more than 2/3rd validators have made votes (B_0, B_n).

Blocks colored yellow are justified, and red are finalized

This change in the definition still preserves the outline of the Casper FFG safety proof from the previous post. A complete proof can be found in the “Safety” section in this paper.

Detecting Casper FFG Finality

The Beacon Chain has an on-chain FFG mechanism that processes blocks & attestations to detect finality. At each epoch boundary, this mechanism processes new attestations and updates its knowledge of justified and finalized blocks.

To lower the overhead of processing attestations between any possible source-target pair, only specific source-target pairs are considered by the on-chain FFG mechanism. Only attestations that are made in the current and previous epoch are processed (there are a few more conditions though!). This leads to the on-chain FFG mechanism not being able to detect all instances of finality! In short, the on-chain mechanism is sound but not complete.

A network synchrony assumption is also introduced because of only processing attestations from the last two epochs: attestations are broadcasted in the network within two epochs.

The specification of the on-chain FFG mechanism is quite simple:

  • The first step is to detect justification of blocks. The two most recent epoch boundary blocks are checked for being justified using the new attestations from the last two epochs.
  • The next step is to detect finalization of blocks, for which the last two epoch boundary blocks are checked. Only four source-target combinations are used for the finality check (for improving performance & specification simplicity):
Case Checking Finalization for Source Checkpoint Using Target Checkpoint
1a 2nd most recent 1st most recent
1b 3rd most recent 1st most recent
2a 3rd most recent 2nd most recent
2b 4th most recent 2nd most recent

Checkpoints involved in the finalization check
Blocks colored yellow are justified, and red are finalized

Part 2 – Fork Choice & Validator Schedule

While the Casper FFG Mechanism outlines the rules that guarantee the finalization of a block, it does not mention how liveness is achieved in practice (Note: this post does not attempt to prove liveness, but instead outline the processes that are expected to achieve liveness. For a rigorous analysis, refer to this paper). This part of the post will focus on two major liveness considerations:

  • The fork choice rule that validators execute to find the head of the chain
  • The schedule of producing blocks & attestations followed by validators

HLMD GHOST Fork Choice Rule

Validators who are to propose blocks must first find the local head of their chain, for which they use the Hybrid Latest Message Driven (HMLD) GHOST fork choice rule.

The specification of this fork choice is as follows:

  1. At the start of each epoch, identify the latest justified block in the current view of the validator. This variable is frozen for the period of that epoch, and is updated again at the start of the next epoch.
  2. Filter out any blocks that do not have the justified block from Step 1 as the latest justified block in that block’s chain.
  3. Descend through the block tree using the usual LMD GHOST rules until a leaf block is found.

For more information about the fork choice, check out the “Hybrid LMD GHOST” section from this paper.

Validator Schedule

Each validator has two main responsiblities towards the network: proposing new blocks, and attesting to the best block in their local view. A validator schedule is specified to prevent chaos and to streamline message passing in the network. This schedule is computed by each validator by obtaining randomness from the current Beacon Chain state, which prevents attackers from dictating the schedule to enable.

Proposal Schedule: For each slot in each epoch, a validator is assigned to be the proposer. The validator then finds the head of the chain using the fork choice on its local view of the block tree and produces a new child block for the head. Attestations that the validator has seen can be packaged into the block for rewards, and these serve as an input to the on-chain FFG mechanism when finality checks are to be run.

Attestation Schedule: Every validator is assigned to make an attestation in one slot per epoch. In practice, the entire validator set is randomly partitioned into SLOTS_PER_EPOCH number of equal sized committees for each epoch, and each committee is assigned a specific slot in the epoch to make attestations. When validator are making attestations, they are expected to put the source as the last justified block, and the target as the most recent checkpoint behind the head of the chain as per their local view.

For more information about the validator schedule, check out this validator guide from the Eth2.0 specs.

References & Additional Material

  1. Ethereum 2.0 Phase 0 Specification
  2. “Combining GHOST and Casper” paper

—Source link—

What do you think?

The Moneyness of Bitcoin and Ethereum

Ethereum’s upcoming derivative primitives