Skip to content

Consensus

Jump to bottom
Loong edited this page Jan 9, 2020 · 35 revisions

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

Proposals, Prevotes, and Precommits

Tendermint consensus algorithm

At every height (and every round in that height), a proposer is selected by an agreed proposers schedule (Hyperdrive comes with a simple round-robin schedule). The selected proposer must propose a valid block before the proposing timeout.

Every replica waits to receive the propose. If they see a proposal for a valid block, before their proposing timeout, they will prevote for the proposed block. Otherwise, the replica will prevote for nil.

After prevoting, replicas wait to receive prevotes from all of the other replicas. After receiving 2/3rds of prevotes, they begin their prevoting timeout. If they see 2/3rd+ prevotes for the same block, before their prevoting timeout, they will precommit to that block. Otherwise, they will precommit for nil.

After precommitting, replicas wait to receive precommits from all of the other replicas. After receiving 2/3rds of precommits, they start their precommitting timeout. If they see 2/3rd+ precommits for the same block, before their precommitting timeout, they will commit to that block and consensus is finished for this height and the process begins again for the next height. Otherwise, they will not commit to anything, increase the round, and the process begins again for the same height.

Fast Forwarding

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

Rebasing is used to change the signatories that are responsible for maintaining consensus. This is done by introducing special blocks that suggest new signatories. The existing signatories approve this suggestion by committing these special blocks in the usual way. After commitment, the new signatories become responsible.

Base blocks

Base blocks define the signatories that are responsible for proposing, prevoting, and precommitting blocks up to, and including, the next base block. All blocks must reference the most recently committed base block. Base blocks themselves reference the previously committed base block. This makes it easy to lookup which signatories should be proposing, prevoting, and precommitting at any given height.

  • Base blocks must reference a rebase block as their parent,
  • must define the same set of signatories in their header (as defined in the header of their parent),
  • must include the previous state,
  • must not include transactions, and
  • must not include an execution plan.

The genesis block is a base block with no reference to a parent block, no reference to a previously committed base block, and it is assumed to be finalised.

Rebase blocks

Rebase blocks are used to suggest that the blockchain rebases to a new set of signatories. Committing the rebase block implies that all of the current signatories approve of the suggestion, and the next block will be a base block. The existence of the base block is required to finalise any new state produced by the rebase block.

  • Rebase blocks must reference a standard block as their parent,
  • must define some set of signatories in their header,
  • must include the previous state,
  • can include transactions, and
  • can include an execution plan.

Standard blocks

  • Standard blocks must not define a set of signatories in their header,
  • must include the previous state,
  • can include transactions, and
  • can include an execution plan.

Clone this wiki locally