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) in the blockchain, a proposer is selected by some proposing schedule (Hyperdrive comes with a simple round-robin schedule). The proposer must propose a valid block before the proposing timeout.

Every replica is waiting to receive the propose. If they see an invalid proposal, or they do not see a proposal before their proposing timeout, the replica will prevote for nil. Otherwise, they will prevote for the proposed block that they received.

After prevoting, replicas wait to receive prevotes from all of the other replicas. After receiving 2/3rds of prevotes, they start their prevoting timer. If they see 2/3rds+ prevotes for the same block, they will precommit to that block. Otherwise, when the timer runs out, 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 timer. If they see 2/3rds+ precommits for the same block, they will commit to that block and consensus is finished for this height. The height increases, and the process begins again. Otherwise, when the timer runs out, they will not commit to anything and instead increase the round and the process begins again.

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