Fork-choice for parachains based on approvals and disputes

[rphmeier]

Problem Statement

One of the goals of parachain consensus is that we never finalize any parachain block which is not considered valid. That means that we have to monitor approval and dispute state and use that to determine not only which blocks we vote to finalize but also which blocks we choose to build on.

We need two rules, one for choosing which block to build on top of, and one for choosing which block to finalize.

Block Authoring Parent Rule:

1. Avoid blocks which contain candidates which have lost disputes
2. Avoid blocks which are not approved and are more than S slots old (S = 15 or 90 seconds with 6-second slot times)
3. Choose the best block out of all remaining by comparing BABE score

Finality Target Rule:

1. Choose the best block via the Block Authoring Parent Rule
2. Avoid blocks which contain candidates which have active disputes
3. Avoid blocks which have not been approved

These two rules, when used in conjunction with each other, will provide the following properties:

1. Nothing disputed will be finalized
2. Chains that are stagnant wil be abandoned
3. Chains that contain invalid candidates will be abandoned
4. Chains which are built as alternatives to abandoned chains will be ordered by BABE rules and can be finalized even when much shorter than the abandoned chain.

Revert Signals
We assume that chains which contain invalid candidates eventually issue digests indicating that they should be abandoned as disputes conclude on these chains. These signals take the form RevertSignal(BlockNumber), appearing in the block header, which indicates the ancestor of the signaling block which contains a bad candidate and should be reverted. A block may contain multiple revert signals targeting different ancestors.

---

Solution

Create a ForkChoiceSubsystem which wraps a database and implements the block authoring parent rule. This can be wrapped by a SelectChain implementation which will can be plugged into BABE and GRANDPA. The additional constraints on GRANDPA voting can be implemented via the approval voting and dispute coordinator subsystems.

---

Data structures:

struct LeafEntry {
    block_hash: BlockHash,
    babe_score: BabeScore,
}

struct Stagnant(bool);

struct ApprovalStatus {
    // None means approved
    approved: Option<Stagnant>,
    earliest_stagnant_ancestor: Option<BlockHash>,
}

struct RevertStatus {
   // Whether this block has been explicitly reverted by one of its descendants.
   explicitly_reverted: bool,
   // The hash of the earliest unfinalized ancestor which was explicitly reverted.
   earliest_reverted_ancestor: Option<BlockHash>,
}

struct BlockEntry {
    block_hash: BlockHash,
    parent_hash: BlockHash,
    import_time: Timestamp,
    children: Vec<BlockHash>,
    approval_status: ApprovalStatus,
    revert_status: RevertStatus,
    babe_score: BabeScore,
}

DB Schema:

// All unfinalized leaves. If empty, the finalized block is implicitly the fork-choice.
// Sorted descending by BABE score.
Leaves: Vec<LeafEntry>;
// Unfinalized number -> all known block hashes.
BlocksAtHeight: BlockNumber -> Vec<BlockHash>;
// Unfinalized block hash -> entry
BlocksByHash: BlockHash -> Vec<BlockEntry>;
// Import timestamp to block hashes which have not been checked for stagnation.
StagnantQueue: Timestamp -> Vec<BlockHash>;

---

Stagnation

Stagnation refers to blocks which go a long time without being approved. These are typically blocks which contain invalid candidates or the result of bugs in the approval voting subsystems.

A block is stagnant in the fork-choice rule if either

1. Its own approval status is Some(Stagnant(true)).
2. It has a stagnant ancestor

We assume that we have two constants:

// How often to check for stagnation. This should balance frequency with expense.
// When checks are infrequent, validators can have highly varying views of what is stagnant.
// When checks are too frequent, effort is wasted checking with no underlying change.
//
// recommend 5-10 seconds
const STAGNANT_CHECK_INTERVAL: Duration;
// How many slots old a block must be unapproved to be considered stagnant. Recommend 30 slots
const STAGNANT_THRESHOLD: Duration;

Reversion

A block is explicitly reverted if one of its descendants issues a revert signal targeting its block number.
A block is reverted if it is explicitly reverted or is the descendant of an unfinalized explicitly reverted block.

Blocks which contain candidates that have lost disputes are explicitly reverted by the runtime code handling the import of disputes. The descendants of those blocks are implicitly reverted.

Viable Leaf

A block is viable if:

1. It is not stagnant.
2. It is not reverted.

Note that a block can only be viable if all of its unfinalized ancestors are viable as well.

A block is a viable leaf if:

1. It is viable.
2. It has no descendants which are viable.

Note that it is possible to determine whether a block is viable by inspecting its entry and only its entry. Furthermore, it is possible to determine parent viability from a child's entry. All iteration is done during updates to the state, while queries to the state are cheap. This is designed to reflect the access patterns: the selection of a block to build upon or finalize should be quick and should not involve any expensive iteration.

---

Operations

1. Import Block:

Import the entire unknown ancestry of the block, extracting relevant info. Blocks are imported in ascending order. The initial approval state for new blocks should be Some(not_stagnant), with earliest_stagnant_ancestor fetched from the parent and None if the parent is not in the database. The initial reversion state for new blocks should be explicitly_reverted = false and earliest_reverted_ancestor based on the parent.

Add children to any blocks that already exist.

For each revert signal in any new block, iterate backwards to the referenced ancestor, ignoring if finalized, and set explicitly_reverted = true. If necessary, iterate forwards from the ancestor into all descendants and update the earliest_reverted_ancestor.

Add each imported block to the StagnantQueue map with the slot number at which it will become stagnant - slot + STAGNANT_THRESHOLD

Update the set of active leaves:

• Replace any non-reverted leaves which have been superseded by children
• Remove any reverted leaves and search recursively starting from the parent of the explicitly reverted blocks.

---

2. Finalize Block:

Remove all block entries with number older than the finalized block number.
Remove all block entries with the same number as the finalized block but with different hash, and all of their children.

No entries from StagnantQueue are pruned here. They will remain stale but will be cleaned up later by the stagnant detection task.

Remove the finalized block’s entry:

If stagnant, iterate recursively through all descendants and update the earliest_stagnant_ancestor as necessary and correct for each block.
If explicitly reverted, iterate recursively through all descendants and update the earliest_reverted_ancestor as necessary and correct for each block.

Update the set of active leaves:

• Remove all leaves from orphaned blocks and the finalized block.
• If the finalized block was not viable, then the leaves set must be empty as it can only contain descendants of the finalized block.
• Therefore: if the active leaves set is not empty, then the finalized block must have been viable. These leaves are still the correct leaves, as no new blocks have been imported, and nothing unfinalized has lost viability.
• Corollary: If the active leaves set is empty, then the finalized block was non-viable and the set should be filled with any viable leaves descending from the finalized block.

It’s also worth noting that the only way a non-viable block can be finalized is if our view in the network vastly differs from the majority due to the slow spread of information, and that typically the finalized block is viable and finalization does not require iteration.

---

3. Approve Block:

We assume that the approval voting subsystem sends signals about each approved block, including blocks which are instantaneously approved by virtue of including no candidates or similar protocol constraints.

The approved block should be loaded and its approval status should change to None. If the approved block was stagnant and the earliest_stagnant_ancestor of the approved block is None, then descendants should be visited recursively and have their earliest_stagnant_ancestor updated accordingly.

Update the set of active leaves:

• If the approved block was not stagnant, then no block has changed in viability and no change in the viable leaves should be made.
• If the approved block's parent was not viable then no block has changed in viability and no change in the viable leaves should be made.
• If the approved block's parent was viable and the approved block has now become viable, then its parent should be removed from the viable leaves set, and the approved block and its descendants should be searched for viable leaves. This can be combined with the earliest_stagnant_ancestor update of descendants.

---

4. Detect Stagnant:

This is invoked every STAGNANT_CHECK_INTERVAL time. Iterate and drain in ascending order every entry in StagnantQueue up to the current timestamp.

For each block hash there are 3 possibilities:

1. There is no entry for the block. Continue; this is an orphaned block.
2. There is an entry for the block and it is approved. Continue; there is no change to be made
3. There is an entry for the block and it is not approved. Mark as stagnant. If earliest_stagnant_ancestor is None, iterate all descendants and set earliest_stagnant_ancestor.

Update the set of active leaves:

• If the block was viable and is now non-viable, then any leaves that were encountered while updating earliest_stagnant_ancestor should be removed, and the parent of the block should, if unfinalized, be added to the active leaves set.
• If the block has not changed in viability, then no leaf has changed in viability.
• Generally, since we are starting with earlier blocks as opposed to later ones, that only the first set of stagnant blocks should involve any significant change to the active leaves set.

[burdges]

Yup, the children field looks like what we discussed. And StagnantQueue improves thing. :)

[rphmeier]

Ok, now that it's been reviewed, I'll take the following implementation steps:

• Write a guide page on the high-level goals of fork-choice for parachains
• Write a guide page for the subsystem based on this issue, avoiding low-level implementation details
• Extract the import-all-unknown logic from approval-voting to a general utility (extract determine_new_blocks into a separate utility #3261)
• Implement the fork-choice subsystem