Skip to main content

Consensus

Definitions and notation

For the purpose of maintaining consensus, transactions are grouped into blocks. There is a single preconfigured block GG called genesis block. Every block except GG has a link pointing to the previous block prev(B)\operatorname{prev}(B), where BB is the block, and GG is reachable from every block by following those links (that is, there are no cycles).

The links between blocks give rise to a partial order: for blocks AA and BB, A<BA < B means that ABA \ne B and AA is reachable from BB by following links to previous blocks, and ABA \le B means that A<BA < B or A=BA = B. The relations >> and \ge are defined as the reflected versions of << and \le, respectively. Finally, ABA \sim B means that either A<BA < B, A=BA = B or A>BA > B, and ABA \nsim B means the opposite.

A chain chain(T)\operatorname{chain}(T) is a set of blocks reachable from block TT, which is called its tip. That is, chain(T)={BBT}\operatorname{chain}(T) = \{B \mid B \le T\}. For any blocks AA and BB, there is a chain that both AA and BB belong to iff ABA \sim B. In this case, AA and BB are said to be on the same chain.

Each block has an integer height h(B)\operatorname{h}(B). It is guaranteed that block heights are monotonic (that is, for any block BGB \ne G, h(B)>h(prev(B))\operatorname{h}(B) > \operatorname{h}(\operatorname{prev}(B))), but they need not be consecutive. Also, h(G)\operatorname{h}(G) may not be zero. Each node keeps track of a valid block with the largest height it knows about, which is called its head.

Blocks are grouped into epochs. In a chain, the set of blocks that belongs to some epoch forms a contiguous range: if blocks AA and BB such that A<BA < B belong to the same epoch, then every block XX such that A<X<BA < X < B also belongs to that epoch. Epochs can be identified by sequential indices: GG belongs to an epoch with index 00, and for every other block BB, the index of its epoch is either the same as that of prev(B)\operatorname{prev}(B), or one greater.

Each epoch is associated with a set of block producers that are validating blocks in that epoch, as well as an assignment of block heights to block producers that are responsible for producing a block at that height. A block producer responsible for producing a block at height hh is called block proposer at hh. This information (the set and the assignment) for an epoch with index i2i \ge 2 is determined by the last block of the epoch with index i2i-2. For epochs with indices 00 and 11, this information is preconfigured. Therefore, if two chains share the last block of some epoch, they will have the same set and the same assignment for the next two epochs, but not necessarily for any epoch after that.

The consensus protocol defines a notion of finality. Informally, if a block BB is final, any future final blocks may only be built on top of BB. Therefore, transactions in BB and preceding blocks are never going to be reversed. Finality is not a function of a block itself, rather, a block may be final or not final in some chain it is a member of. Specifically, final(B,T)\operatorname{final}(B, T), where BTB \le T, means that BB is final in chain(T)\operatorname{chain}(T). A block that is final in a chain is final in all of its extensions: specifically, if final(B,T)\operatorname{final}(B, T) is true, then final(B,T)\operatorname{final}(B, T') is also true for all TTT' \ge T.

Data structures

The fields in the Block header relevant to the consensus process are:

struct BlockHeader {
...
prev_hash: BlockHash,
height: BlockHeight,
epoch_id: EpochId,
last_final_block_hash: BlockHash,
approvals: Vec<Option<Signature>>
...
}

Block producers in the particular epoch exchange many kinds of messages. The two kinds that are relevant to the consensus are Blocks and Approvals. The approval contains the following fields:

enum ApprovalInner {
Endorsement(BlockHash),
Skip(BlockHeight),
}

struct Approval {
inner: ApprovalInner,
target_height: BlockHeight,
signature: Signature,
account_id: AccountId
}

Where the parameter of the Endorsement is the hash of the approved block, the parameter of the Skip is the height of the approved block, target_height is the specific height at which the approval can be used (an approval with a particular target_height can be only included in the approvals of a block that has height = target_height), account_id is the account of the block producer who created the approval, and signature is their signature on the tuple (inner, target_height).

Approvals Requirements

Every block BB except the genesis block must logically contain approvals of a form described in the next paragraph from block producers whose cumulative stake exceeds 2 ⁣/3^2\!/_3 of the total stake in the current epoch, and in specific conditions described in section epoch switches also the approvals of the same form from block producers whose cumulative stake exceeds 2 ⁣/3^2\!/_3 of the total stake in the next epoch.

The approvals logically included in the block must be an Endorsement with the hash of prev(B)\operatorname{prev}(B) if and only if h(B)=h(prev(B))+1\operatorname{h}(B) = \operatorname{h}(\operatorname{prev}(B))+1, otherwise it must be a Skip with the height of prev(B)\operatorname{prev}(B). See this section below for details on why the endorsements must contain the hash of the previous block, and skips must contain the height.

Note that since each approval that is logically stored in the block is the same for each block producer (except for the account_id of the sender and the signature), it is redundant to store the full approvals. Instead physically we only store the signatures of the approvals. The specific way they are stored is the following: we first fetch the ordered set of block producers from the current epoch. If the block is on the epoch boundary and also needs to include approvals from the next epoch (see epoch switches), we add new accounts from the new epoch

def get_accounts_for_block_ordered(h, prev_block):
cur_epoch = get_next_block_epoch(prev_block)
next_epoch = get_next_block_next_epoch(prev_block)

account_ids = get_epoch_block_producers_ordered(cur_epoch)
if next_block_needs_approvals_from_next_epoch(prev_block):
for account_id in get_epoch_block_producers_ordered(next_epoch):
if account_id not in account_ids:
account_ids.append(account_id)

return account_ids

The block then contains a vector of optional signatures of the same or smaller size than the resulting set of account_ids, with each element being None if the approval for such account is absent, or the signature on the approval message if it is present. It's easy to show that the actual approvals that were signed by the block producers can easily be reconstructed from the information available in the block, and thus the signatures can be verified. If the vector of signatures is shorter than the length of account_ids, the remaining signatures are assumed to be None.

Messages

On receipt of the approval message the participant just stores it in the collection of approval messages.

def on_approval(self, approval):
self.approvals.append(approval)

Whenever a participant receives a block, the operations relevant to the consensus include updating the head and initiating a timer to start sending the approvals on the block to the block producers at the consecutive target_heights. The timer delays depend on the height of the last final block, so that information is also persisted.

def on_block(self, block):
header = block.header

if header.height <= self.head_height:
return

last_final_block = store.get_block(header.last_final_block_hash)

self.head_height = header.height
self.head_hash = block.hash()
self.largest_final_height = last_final_block.height

self.timer_height = self.head_height + 1
self.timer_started = time.time()

self.endorsement_pending = True

The timer needs to be checked periodically, and contain the following logic:

def get_delay(n):
min(MAX_DELAY, MIN_DELAY + DELAY_STEP * (n-2))

def process_timer(self):
now = time.time()

skip_delay = get_delay(self.timer_height - self.largest_final_height)

if self.endorsement_pending and now > self.timer_started + ENDORSEMENT_DELAY:

if self.head_height >= self.largest_target_height:
self.largest_target_height = self.head_height + 1
self.send_approval(head_height + 1)

self.endorsement_pending = False

if now > self.timer_started + skip_delay:
assert not self.endorsement_pending

self.largest_target_height = max(self.largest_target_height, self.timer_height + 1)
self.send_approval(self.timer_height + 1)

self.timer_started = now
self.timer_height += 1

def send_approval(self, target_height):
if target_height == self.head_height + 1:
inner = Endorsement(self.head_hash)
else:
inner = Skip(self.head_height)

approval = Approval(inner, target_height)
send(approval, to_whom = get_block_proposer(self.head_hash, target_height))

Where get_block_proposer returns the next block proposer given the previous block and the height of the next block.

It is also necessary that ENDORSEMENT_DELAY < MIN_DELAY. Moreover, while not necessary for correctness, we require that ENDORSEMENT_DELAY * 2 <= MIN_DELAY.

Block Production

We first define a convenience function to fetch approvals that can be included in a block at particular height:

def get_approvals(self, target_height):
return [approval for approval
in self.approvals
if approval.target_height == target_height and
(isinstance(approval.inner, Skip) and approval.prev_height == self.head_height or
isinstance(approval.inner, Endorsement) and approval.prev_hash == self.head_hash)]

A block producer assigned for a particular height produces a block at that height whenever they have get_approvals return approvals from block producers whose stake collectively exceeds 2/3 of the total stake.

Finality condition

A block BB is final in chain(T)\operatorname{chain}(T), where TBT \ge B, when either B=GB = G or there is a block XTX \le T such that B=prev(prev(X))B = \operatorname{prev}(\operatorname{prev}(X)) and h(X)=h(prev(X))+1=h(B)+2\operatorname{h}(X) = \operatorname{h}(\operatorname{prev}(X))+1 = \operatorname{h}(B)+2. That is, either BB is the genesis block, or chain(T)\operatorname{chain}(T) includes at least two blocks on top of BB, and these three blocks (BB and the two following blocks) have consecutive heights.

Epoch switches

There's a parameter epoch_length3\operatorname{epoch\_ length} \ge 3 that defines the minimum length of an epoch. Suppose that a particular epoch ecure_{cur} started at height hh, and say the next epoch will be enexte_{next}. Say BP(e)\operatorname{BP}(e) is a set of block producers in epoch ee. Say last_final(T)\operatorname{last\_ final}(T) is the highest final block in chain(T)\operatorname{chain}(T). The following are the rules of what blocks contain approvals from what block producers, and belong to what epoch.

  • Any block BB with h(prev(B))<h+epoch_length3\operatorname{h}(\operatorname{prev}(B)) < h+\operatorname{epoch\_ length}-3 is in the epoch ecure_{cur} and must have approvals from more than 2 ⁣/3^2\!/_3 of BP(ecur)\operatorname{BP}(e_{cur}) (stake-weighted).
  • Any block BB with h(prev(B))h+epoch_length3\operatorname{h}(\operatorname{prev}(B)) \ge h+\operatorname{epoch\_ length}-3 for which h(last_final(prev(B)))<h+epoch_length3\operatorname{h}(\operatorname{last\_ final}(\operatorname{prev}(B))) < h+\operatorname{epoch\_ length}-3 is in the epoch ecure_{cur} and must logically include approvals from both more than 2 ⁣/3^2\!/_3 of BP(ecur)\operatorname{BP}(e_{cur}) and more than 2 ⁣/3^2\!/_3 of BP(enext)\operatorname{BP}(e_{next}) (both stake-weighted).
  • The first block BB with h(last_final(prev(B)))>=h+epoch_length3\operatorname{h}(\operatorname{last\_ final}(\operatorname{prev}(B))) >= h+\operatorname{epoch\_ length}-3 is in the epoch enexte_{next} and must logically include approvals from more than 2 ⁣/3^2\!/_3 of BP(enext)\operatorname{BP}(e_{next}) (stake-weighted).

(see the definition of logically including approvals in approval requirements)

Safety

Note that with the implementation above a honest block producer can never produce two endorsements with the same prev_height (call this condition conflicting endorsements), neither can they produce a skip message s and an endorsement e such that s.prev_height < e.prev_height and s.target_height >= e.target_height (call this condition conflicting skip and endorsement).

Theorem Suppose that there are blocks B1B_1, B2B_2, T1T_1 and T2T_2 such that B1B2B_1 \nsim B_2, final(B1,T1)\operatorname{final}(B_1, T_1) and final(B2,T2)\operatorname{final}(B_2, T_2). Then, more than 1 ⁣/3^1\!/_3 of the block producer in some epoch must have signed either conflicting endorsements or conflicting skip and endorsement.

Proof Without loss of generality, we can assume that these blocks are chosen such that their heights are smallest possible. Specifically, we can assume that h(T1)=h(B1)+2\operatorname{h}(T_1) = \operatorname{h}(B_1)+2 and h(T2)=h(B2)+2\operatorname{h}(T_2) = \operatorname{h}(B_2)+2. Also, letting BcB_c be the highest block that is an ancestor of both B1B_1 and B2B_2, we can assume that there is no block XX such that final(X,T1)\operatorname{final}(X, T_1) and Bc<X<B1B_c < X < B_1 or final(X,T2)\operatorname{final}(X, T_2) and Bc<X<B2B_c < X < B_2.

Lemma There is such an epoch EE that all blocks XX such that Bc<XT1B_c < X \le T_1 or Bc<XT2B_c < X \le T_2 include approvals from more than 2 ⁣/3^2\!/_3 of the block producers in EE.

Proof There are two cases.

Case 1: Blocks BcB_c, T1T_1 and T2T_2 are all in the same epoch. Because the set of blocks in a given epoch in a given chain is a contiguous range, all blocks between them (specifically, all blocks XX such that Bc<X<T1B_c < X < T_1 or Bc<X<T2B_c < X < T_2) are also in the same epoch, so all those blocks include approvals from more than 2 ⁣/3^2\!/_3 of the block producers in that epoch.

Case 2: Blocks BcB_c, T1T_1 and T2T_2 are not all in the same epoch. Suppose that BcB_c and T1T_1 are in different epochs. Let EE be the epoch of T1T_1 and EpE_p be the preceding epoch (T1T_1 cannot be in the same epoch as the genesis block). Let RR and SS be the first and the last block of EpE_p in chain(T1)\operatorname{chain}(T_1). Then, there must exist a block FF in epoch EpE_p such that h(F)+2=h(S)<h(T1)\operatorname{h}(F)+2 = \operatorname{h}(S) < \operatorname{h}(T_1). Because h(F)<h(T1)2\operatorname{h}(F) < \operatorname{h}(T_1)-2, we have F<B1F < B_1, and since there are no final blocks XX such that Bc<X<B1B_c < X < B_1, we conclude that FBcF \le B_c. Because there are no epochs between EE and EpE_p, we conclude that BcB_c is in epoch EpE_p. Also, h(Bc)h(F)h(R)+epoch_length3\operatorname{h}(B_c) \ge \operatorname{h}(F) \ge \operatorname{h}(R)+\operatorname{epoch\_ length}-3. Thus, any block after BcB_c and until the end of EE must include approvals from more than 2 ⁣/3^2\!/_3 of the block producers in EE. Applying the same argument to chain(T2)\operatorname{chain}(T_2), we can determine that T2T_2 is either in EE or EpE_p, and in both cases all blocks XX such that Bc<XT2B_c < X \le T_2 include approvals from more than 2 ⁣/3^2\!/_3 of block producers in EE (the set of block producers in EE is the same in chain(T1)\operatorname{chain}(T_1) and chain(T2)\operatorname{chain}(T_2) because the last block of the epoch preceding EpE_p, if any, is before BcB_c and thus is shared by both chains). The case where BcB_c and T1T_1 are in the same epoch, but BcB_c and T2T_2 are in different epochs is handled similarly. Thus, the lemma is proven.

Now back to the theorem. Without loss of generality, assume that h(B1)h(B2)\operatorname{h}(B_1) \le \operatorname{h}(B_2). On the one hand, if chain(T2)\operatorname{chain}(T_2) doesn't include a block at height h(B1)\operatorname{h}(B_1), then the first block at height greater than h(B1)\operatorname{h}(B_1) must include skips from more than 2 ⁣/3^2\!/_3 of the block producers in EE which conflict with endorsements in prev(T1)\operatorname{prev}(T_1), therefore, more than 1 ⁣/3^1\!/_3 of the block producers in EE must have signed conflicting skip and endorsement. Similarly, if chain(T2)\operatorname{chain}(T_2) doesn't include a block at height h(B1)+1\operatorname{h}(B_1)+1, more than 1 ⁣/3^1\!/_3 of the block producers in EE signed both an endorsement in T1T_1 and a skip in the first block in chain(T2)\operatorname{chain}(T_2) at height greater than h(T1)\operatorname{h}(T_1). On the other hand, if chain(T2)\operatorname{chain}(T_2) includes both a block at height h(B1)\operatorname{h}(B_1) and a block at height h(B1)+1\operatorname{h}(B_1)+1, the latter must include endorsements for the former, which conflict with endorsements for B1B_1. Therefore, more than 1 ⁣/3^1\!/_3 of the block producers in EE must have signed conflicting endorsements. Thus, the theorem is proven.

Liveness

See the proof of liveness in Doomslug Whitepaper and the recent Nightshade sharding protocol.

The consensus in this section differs in that it requires two consecutive blocks with endorsements. The proof in the linked paper trivially extends, by observing that once the delay is sufficiently long for a honest block producer to collect enough endorsements, the next block producer ought to have enough time to collect all the endorsements too.

Approval condition

The approval condition above

Any valid block must logically include approvals from block producers whose cumulative stake exceeds 2/3 of the total stake in the epoch. For a block B and its previous block B' each approval in B must be an Endorsement with the hash of B' if and only if B.height == B'.height + 1, otherwise it must be a Skip with the height of B'

Is more complex that desired, and it is tempting to unify the two conditions. Unfortunately, they cannot be unified.

It is critical that for endorsements each approval has the prev_hash equal to the hash of the previous block, because otherwise the safety proof above doesn't work, in the second case the endorsements in B1 and Bx can be the very same approvals.

It is critical that for the skip messages we do not require the hashes in the approvals to match the hash of the previous block, because otherwise a malicious actor can create two blocks at the same height, and distribute them such that half of the block producers have one as their head, and the other half has the other. The two halves of the block producers will be sending skip messages with different prev_hash but the same prev_height to the future block producers, and if there's a requirement that the prev_hash in the skip matches exactly the prev_hash of the block, no block producer will be able to create their blocks.