Consensus

Consensus follows the algorithm described by "the latest gossip on BFT consensus". It includes two modifications: fast forwarding and rebasing.

The algorithm described by "the latest gossip on BFT consensus" assumes that process will eventually see all messages. This allows the algorithm to restrict its cases to messages that are bound for the H_p (the current of the honest process). However, this is not true in practice, since honest processes may find themselves crashing unexpectedly, or on the wrong side of a network partition.

For example, an honest process could become unavailable at height H_p and not become available again until H_p+N. At this point, none of the cases described by "the latest gossip on BFT consensus" will be triggered. Ideally, such an honest process is able to fast forward to H_p + N without relying on other honest processes relaying all missing messages.

We introduce the case:

upon (PROPOSAL, H, Round, V, *) and 2F+1 (PRECOMMIT, H, Round, id(V)) while H > H_p do
  if valid(V) then
    Decision_p [H_p] = V
    H_p = H + 1
    reset LockedRound_p, LockedValue_p, ValidRound_p, and ValidValue_p to initial values and empty message log
    startRound 0

In practice, the (PROPOSAL, H, Round, V, *) and (PRECOMMIT, H, Round, id(V)) messages required to trigger this case are optionally sent as part of a new (PROPOSAL, H + N, *, *, *) message.

Rebasing is used to change the signatories that are responsible for maintaining consensus.

Block kinds

There are three kinds of blocks: standard blocks, rebase blocks, and base blocks. All block headers must reference the latest base block, and the genesis block must be a base block.

Standard blocks do not define signatories in their headers. They contain transactions, the previous state, and an execution plan. The parent block of a standard block must not be a rebase block.

Rebase blocks define signatories in their headers. These signatories are considered proposals for who should become responsible for maintaining consensus. They contain transactions, the previous state, and an execution plan. The parent block of a rebase block must be standard block.

Base blocks define the same signatories in their headers as the previous rebase block. Base block finalise the signatories proposed by the previous rebase block and, after commitment, the new signatories become responsible for maintaining consensus on all future blocks up to, and including, the next base block. The parent block of a base block must be a rebase block (with the exception of the genesis block).

Rules

The genesis block:

• is always finalised,
• must be a base block,
• must have an empty list of transactions, an empty plan, and an empty state,
• must have a set of 3F+1 signatories in its header,
• must reference 0x0000000000000000000000000000000000000000000000000000000000000000 as the parent block hash, and
• must reference 0x0000000000000000000000000000000000000000000000000000000000000000 as the base block hash.

The N-th base block:

• must be a base block,
• must have an empty list of transactions, and an empty plan,
• must have the set of 3F+1 signatories in its header identical to its parent block,
• must reference a rebase block as the parent block hash, and
• must reference the N-1th base block as the base block hash.

The M-th rebase block:

• must be a rebase block,
• must have the set of 3F+1 signatories in its header, and
• must reference a standard block as the parent block hash.