Chain Selection

Chain selection processes in blockchains are used for the purpose of selecting blocks to build on and finalize. It is important for these processes to be consistent among nodes and resilient to a maximum proportion of malicious nodes which do not obey the chain selection process.

The parachain host uses both a block authoring system and a finality gadget. The chain selection strategy of the parachain host involves two key components: a leaf-selection rule and a set of finality constraints. When it's a validator's turn to author on a block, they are expected to select the best block via the leaf-selection rule to build on top of. When a validator is participating in finality, there is a minimum block which can be voted on, which is usually the finalized block. The validator should select the best chain according to the leaf-selection rule and subsequently apply the finality constraints to arrive at the actual vote cast by that validator.

Before diving into the particularities of the leaf-selection rule and the finality constraints, it's important to discuss the goals that these components are meant to achieve. For this it is useful to create the definitions of viable and finalizable blocks.

Property Definitions

A block is considered viable when all of the following hold:

  1. It is or descends from the finalized block
  2. It is not stagnant
  3. It is not reverted.

A block is considered a viable leaf when all of the following hold:

  1. It is viable
  2. It has no viable descendant.

A block is considered stagnant when either:

  1. It is unfinalized, is not approved, and has not been approved within 2 minutes
  2. Its parent is stagnant.

A block is considered reverted when either:

  1. It is unfinalized and includes a candidate which has lost a dispute
  2. Its parent is reverted

A block is considered finalizable when all of the following hold:

  1. It is viable
  2. Its parent, if unfinalized, is finalizable.
  3. It is either finalized or approved.
  4. It is either finalized or includes no candidates which have unresolved disputes or have lost a dispute.

The leaf-selection rule

We assume that every block has an implicit weight or score which can be used to compare blocks. In BABE, this is determined by the number of primary slots included in the chain. In PoW, this is the chain with either the most work or GHOST weight.

The leaf-selection rule based on our definitions above is simple: we take the maximum-scoring viable leaf we are aware of. In the case of a tie we select the one with a lower lexicographical block hash.

The best-chain-containing rule

Finality gadgets, as mentioned above, will often impose an additional requirement to vote on a chain containing a specific block, known as the required block. Although this is typically the most recently finalized block, it is possible that it may be a block that is unfinalized. When receiving such a request:

  1. If the required block is the best finalized block, then select the best viable leaf.
  2. If the required block is unfinalized and non-viable, then select the required block and go no further. This is likely an indication that something bad will be finalized in the network, which will never happen when approvals & disputes are functioning correctly. Nevertheless we account for the case here.
  3. If the required block is unfinalized and viable, then iterate over the viable leaves in descending order by score and select the first one which contains the required block in its chain. Backwards iteration is a simple way to check this, but if unfinalized chains grow long then Merkle Mountain-Ranges will most likely be more efficient.

Once selecting a leaf, the chain should be constrained to the maximum of the required block or the highest finalizable ancestor.