A lightweight BFT consensus protocol for blockchains
Jan Hackfeld





A lightweight BFT consensus protocol for blockchains
    Jan Hackfeld 
 Lightcurve GmbH 
 
    December 30, 2023
====================================================




We present a general consensus framework that allows to easily introduce a customizable Byzantine fault tolerant consensus algorithm to an existing (Delegated) Proof-of-Stake blockchain. We prove the safety of the protocol under the assumption that less than 1/3 of the validators are Byzantine. The framework further allows for consensus participants to choose subjective decision thresholds in order to obtain safety even in the case of a larger proportion of Byzantine validators. Moreover, the liveness of the protocol is shown if less than 1/3 of the validators crash.

Based on the framework, we introduce , a Byzantine fault tolerant consensus algorithm for the Lisk ecosystem. integrates with the existing block proposal mechanism, requires only two additional integers in blocks and no additional messages. The protocol is simple and provides safety in the case of static validators if less than 1/3 of the validators are Byzantine. For the case of dynamically changing validators, we prove the safety of the protocol assuming a bound on the number of Byzantine validators and the number of honest validators that can change at one time.
We further show the liveness of the protocol for less than 1/3 crashing validators.




§ INTRODUCTION


The Paxos protocol introduced by Lamport in <cit.> is the basis for most consensus protocols solving the Byzantine agreement or more generally the state machine replication problem. Starting with <cit.>, there has been a multitude of different practical consensus protocols that adapt the basic Paxos protocol to improve various aspects such as the efficiency and the resistance against Byzantine faults. See <cit.> for a classification of different consensus protocols.

In this paper, we introduce , a Byzantine fault tolerant consensus algorithm for the Lisk blockchain that follows this line of research. We assume that there is a set of 
validators that can add blocks to a block tree via a given proposal mechanism (e.g. round-robin). 
Ideally, we would like the validators to propose one block after another always referencing the previously proposed block via a directed edge and hence forming a tree with only one growing branch, i.e., a blockchain. However, due to the latency of communication between the validators or deliberate attacks on the network, there can be multiple child blocks of the same parent block and separate growing branches. We therefore need a consensus protocol for validators to agree on one block at every height of the block tree.

We distinguish between honest validators that correctly follow the consensus protocol
and Byzantine validators that may behave arbitrarily. The consensus algorithm is
supposed to allow validators to decide for exactly one block at every height of the block tree such that the following properties are satisfied:


  * Safety. Two honest validators never decide for conflicting blocks, i.e., blocks that are not contained in one branch of the block tree. 

  * Liveness. An honest validator eventually decides for a block at any height.

  * Accountability. A validator can detect if a Byzantine validator violates the consensus protocol and can identify the Byzantine validator.


Note that the safety property implies that all decided blocks for an honest validator are in one branch of the block tree and for any height two honest validators never decide for distinct blocks.

In the case of Bitcoin <cit.>, consensus is reached by validators choosing the chain which required the most “work”. This rule does not satisfy both the safety and liveness property above because no matter how late a validator decides for a block B, there is no guarantee that the block B will be contained in the Bitcoin blockchain the Bitcoin network agrees on in the future. The reason is that there always can be a different branch of the Bitcoin block tree in the future with more “work” although for economic reasons it becomes increasingly unlikely the more blocks are added to the block tree as descendants of B.

Tendermint <cit.> is one of the first blockchain consensus protocols achieving the safety, liveness and accountability property above.  Namely, Tendermint guarantees that as long as <1/3 of the validators are Byzantine, both the safety and liveness property hold, which is optimal for the partially synchronous system model introduced in <cit.>. The Tendermint protocol proceeds in three distinct phases. Once the three phases are completed successfully, the validators decide for a block B  and proceed with proposing and deciding for a descendant of B. This way the block tree in Tendermint is simply a path as for every height the validators decide for a block before proceeding further. We call a consensus protocol with this property fork-free. In contrast to that, we refer to a consensus protocol as forkful if there is no requirement for validators to achieve consensus, i.e., decide for a block, before adding further blocks to the block tree. 

The protocol is a forkful protocol, where the block proposal can independently progress before consensus is reached on blocks. This idea of using speculative Byzantine fault tolerance in order to decrease the overhead has already been considered in <cit.> for the state machine replication problem. We also believe that a forkful protocol can achieve better performance in practice and significantly decrease the communication overhead as consensus
can be reached independent of the block proposal at any later point in time.
For a more detailed treatment of forkful versus fork-free consensus protocols and the message complexity involved, see <cit.>.
 



§ MODEL AND DEFINITIONS


In this section, we introduce the blockchain specific terminology as well as the underlying network model. We do not consider the general state machine replication problem, but instead assume that there is a block proposal mechanism, where time is divided into discrete slots and for every time slot there is a designated validator. We also change some of the state machine replication terminology to the blockchain specific context.

A block tree is a directed tree with a designated root vertex referred to as genesis block and a unique directed path from every vertex in the block tree to the genesis block. We refer to the vertices in the block tree as blocks. We assume that blocks can contain arbitrary data such as signatures or messages. Every block B has a corresponding height, denoted by h(B), which is the number of edges of the unique path from that block to the genesis block. Note that the genesis block has height 0. For a block B in the block tree, we call a block B' ancestor if B' is distinct from B and is on the directed path from B to the genesis block. Moreover, B' is called a descendant of B if B is an ancestor of B'. If there is a directed edge from a block B to a block B', then B' is called the parent of B and B a child of B'. We further refer to the subgraph induced by a path from a block without child to the genesis block as a branch or a chain. For a given chain, the unique block without child block is referred to as the tip or head of the chain. Two blocks are called conflicting if they are not contained in one branch of the block tree, i.e., none is a descendant of the other.

We assume that there is a set of validators  and a proposal mechanism for validators to add child blocks of existing blocks to the block tree. We distinguish between three types of validators: 
A validator is honest if it obeys the consensus protocol and actively participates by sending messages. 
A validator is further called offline or crashed if it stops participating in the consensus protocol from a certain point in time onwards, i.e., does not send any message more to the network, but all its messages obey the protocol rules. Moreover,  a Byzantine validator can behave arbitrarily, e.g., maliciously violate the consensus protocol or crash.  Classic Byzantine fault tolerance consensus protocols typically yield guarantees assuming certain upper bounds on the number of Byzantine validators. In the case of blockchain, in particular Proof-of-Stake, we would rather have guarantees in terms of the stake represented by a certain set of validators. We can model this by associating a weight ω_∈ [0,1] to every validator  such that ∑_∈ω_ = 1, where ω_ can be thought of as the relative stake in the case of a Proof-of-Stake blockchain. 
For the simplicity of exposition, we often do not use the validator weights explicitly but rather say that >ω (or <ω)  of the validators satisfy a property X if the set M of validators satisfying property X has overall weight larger (or smaller) than ω, i.e., ∑_∈ Mω_ >ω (∑_∈ Mω_ <ω). For instance, we regularly assume that <1/3 of the validators are Byzantine. 

We further assume that the validators communicate by exchanging messages via the underlying network. We model the network using the partially synchronous system model introduced in <cit.>. The basic assumption of this model is that in general the network can behave arbitrarily badly, i.e., messages are lost or have a huge delay, but eventually, from a time  onward, the network behaves nicely, i.e., all messages arrive reliably and with a delay of at most Δ.
The parameter  is called the global stabilization time. Messages are further always signed so that a validator can not be impersonated by another validator. The validators are not required to know any bound on  or Δ. 
Note that the eventually synchronous network is only necessary to show the liveness of the consensus algorithm, but not for the safety. In fact, this assumption on the underlying network is stronger than needed for our consensus to work in practice and our results can easily be extended to a network model with regular long enough good time periods, where the messages arrive reliably and within Δ time. These good periods only need to be long enough for validators to send enough messages to decide for blocks. For the ease of exposition, however, we use the partially synchronous system model.

Note that due to the impossibility results of Fischer et al. <cit.>, stating that consensus is impossible without randomization in an asynchronous message-passing system with at least one Byzantine or crashing node, the partially synchronous system model is one of the weakest models where consensus without randomization is possible. 
Known consensus algorithms for asynchronous systems using randomization have worse guarantees in terms of maximum number of Byzantine validators, require a large number of local computations or a larger number of messages <cit.>. 




§ GENERAL CONSENSUS ALGORITHM FRAMEWORK

In this section, we define a general consensus protocol with two types of messages, which
is later used as the basis for the protocol.



 §.§ Protocol rules

We now describe the protocol rules of the general consensus framework. A validator  can send two types of messages, 
(B,T,) and (B,T,), where B and T are blocks in the block tree such that T=B or T is a descendant of B (T is typically the tip of the current chain of ). In an implementation, B and T can be block hashes and  the public key and signature of the validator . 
We assume that both types of messages are added to the blocks so that we can refer to the prevotes and precommits included in the blockchain from the genesis block up to the tip T. 
Moreover, we shortly write that a validator prevotes for B if  sends a (B,T,) message and equivalently that  precommits for B if it sends a message (B,T,) for a block T.
Next, we describe the protocol rules that must be satisfied when sending prevote and precommit messages and the conditions for validators to decide for blocks.


The prevotes and precommits send by a validator ∈ must obey the following rules:


  * For any two distinct messages (B,T,) and (B',T',), it holds that h(B)≠ h(B'). 


  * For any message (B,T,), the blockchain up to block T must include both 


  * one (B,·,) message and

  * (B,·,·) messages by >2/3 of the validators.


  * For any two messages  (B,T,) and  (B',T',) with h(B)<h(B') at least one of the following conditions is satisfied: 


  * B' is a descendant of B. 

  * The blockchain up to T' contains a block B̅ at height h(B̅)≥ h(B) and (B̅,·,·) messages by >2/3 of the validators.


Let τ_∈ (13,1] denote the decision threshold of a validator . Once validator  receives (B,·, ·) messages by >τ_ of the validators, validator  decides for block B or finalizes block B. This implies that  also decides for all ancestors of B.


The basic intuition behind the protocol rules is that prevotes must not contradict, so validators can cast only one prevote for every height by <ref>. Moreover, in order to send a precommit for a block, a validator has to have send a prevote for that block and received prevotes  by >2/3 of the validators for it due to <ref>. Finally, the intuition behind <ref> is that a validator cannot change to a different chain without a justification, i.e., after a precommit for block B, all prevotes of larger height must be for descendants of B or, as a justification, there is a block B̅ at height h(B̅)≥ h(B) with >2/3 prevotes that allows the validator to start sending prevotes on a different chain.

In the next subsection, we show how the decision threshold relates to the safety property of the protocol. Intuitively, the higher the decision threshold of the validators, the more validators can be Byzantine without losing the safety property. On the other hand, for the liveness property, the decision threshold cannot be too high as otherwise a validator may never decide on a block. 



 §.§ Safety


In this section, we show that the safety property is fulfilled for the general consensus protocol assuming a bound on the overall weight of Byzantine validators that depends on the decision thresholds of the validators.


If the weight of Byzantine validators is <(τ -1/3) for τ∈ (1/3, 1], then any two honest validators with decision threshold at least τ never decide for conflicting blocks. 



Assume, for the sake of contradiction, that there are two conflicting blocks B_1 and B_2 
as well as an honest validator _1 with decision threshold τ_1 deciding for B_1 and an honest validator _2 with decision threshold τ_2 deciding for B_2. Without loss of generality let h(B_1) ≤ h(B_2). Note that by assumption we have τ≤τ_1 and τ≤τ_2.

If _1 decides for B_1, it must have received a (B_1,·, ·) messages by >τ_1 of the validators by definition. 
By assumption, τ_1 ≥τ and <(τ -1/3) of the validators are Byzantine so that there is a set of >1/3 honest or crashing validators _1 that must have sent a (B_1,·, ·) message. 
Note that crashing validators obey the protocol rules, but may stop sending messages from some point onwards.
In particular, by property <ref>, no validator ∈_1 sends a (B,·, ) message for a distinct block B at height h(B_1) and hence no distinct block B at height h(B_1) can receive >2/3 prevotes.
This also implies that we cannot have h(B_1)=h(B_2) as there can only be ≤ 2/3 prevotes for B_2 and hence no validator  obeying the protocol rules would send a (B_2,·,) message by <ref>. Thus, the threshold of τ_2 precommit messages for block B_2 cannot be reached and we must have h(B_1)<h(B_2).



By <ref>, every validator ∈_1 only sends a prevote message for a block that is not a descendant of B_1 if there is a block B̅ at height h(B̅)≥ h(B_1) with (B̅,·,·) messages by >2/3 of the validators. 
As all validators in _1 follow the protocol, there have to be >2/3 prevotes for such a block B̅ by validators not in _1. 
This is a contradiction, as _1 is a set of >1/3 validators by assumption. 
Hence, no block that is not a descendant of B_1 can obtain >2/3 prevotes and thus no validator following the protocol sends a precommit for B_2. 
This means that the decision threshold of τ_2 precommit messages for block B_2 cannot be reached contradicting that the honest validator _2 decided for B_2.



Note that for ≥ 1/3 Byzantine validators a consensus protocol that guarantees both safety and liveness  in the partially synchronous system model is impossible as shown in <cit.>. This is also the case for the consensus framework above because Byzantine validators can for example not send any prevotes  and thus prevent any decision for a block as the threshold of >2/3 prevotes is not reached. In order to have both the liveness and safety property, we hence cannot have ≥ 1/3 Byzantine validators.
The purpose of the flexible subjective decision threshold is to allow for optimistic participants (those assuming a small fraction of Byzantine validators) to decide for blocks earlier by only requiring a small decision threshold τ_. On the other hand, pessimistic participants can decide for a block only with a very high decision threshold (with the risk of never making a decision if too many validators are Byzantine or offline) with the guarantee that ≥τ_ -1/3 must violate the protocol rules for a conflicting block to be decided. In particular, in the case that slashing conditions are added to punish Byzantine validators by burning their deposits, this allows to choose a decision threshold
depending on the desired safety guarantee in terms of deposit at stake.




 §.§ Liveness


For proving the liveness condition of the consensus framework from Definition <ref>, we rely on the partially synchronous system model. Recall that the basic assumption is that after the global stabilization time of , all messages arrive reliably with a delay of at most Δ. We assume that the time slots for validators to add blocks to the block tree have a duration of at least 2 Δ. This way the underlying network is fast enough for the message about a new block to reach every validator and all validators to send new prevote and precommit messages that reach every other validator before the next block is proposed. This way, all prevotes and precommits can be included in the next block and validators at regular times have the same information about the block tree (we assume that blocks, prevote and precommit messages that were lost before time  are simply rebroadcast).

Additionally, for the liveness property to hold, validators need to follow the same fork choice rule, i.e., a rule that defines how the validators choose one branch of the block tree as their current chain. More precisely, a fork choice rule is a function f that, given the block tree 𝒯_ of validator  (i.e., the block tree containing all blocks received by validator ) and the arrival times of all blocks as input, returns one branch of the block tree 𝒯_. We refer to this branch as the canonical chain of 𝒯_. We say that a validator  follows a fork choice rule f if it adds new proposed blocks to the canonical chain and only sends prevote and precommit messages for blocks in the canonical chain. For the liveness proof, we use the fork choice rule defined below. 


Let 𝒯_ be the current block tree of validator  and h̅ be the largest height of a block in 𝒯_ with prevotes by >2/3 of the validators included in one branch of 𝒯_.  
Then the fork choice rule returns the longest branch that contains a block B̅ at height h̅ and (B̅,·,·) messages by >2/3 of the validators. Ties are broken in favor of the complete chain received first.


The essential property that the fork choice rule needs to satisfy is that the branch returned always contains a block B̅ of largest height with prevote messages by >2/3 of the validators. The reason is that by <ref>, once a validator casts a precommit for B̅, it can only prevote and precommit for blocks on the same branch as B̅ (unless there is a block of height at least h(B̅) with >2/3 prevotes). Thus, by requiring the canonical chain to include B̅, the validators automatically satisfy <ref> when casting prevotes and precommits. In general, other fork choice rules that satisfy that the canonical chain always contains B̅ are possible and yield the liveness property. An example is Immediate message-driven GHOST proposed for Ethereum <cit.>.

If <1/3 of the validators are Byzantine, there can be at most one block at a given height with >2/3 prevotes by the the validators by <ref>. Thus, in this case B̅ in the definition above is unique.
Further, note that the tie-breaking in favor of the chain seen first is rather arbitrary and
also block hashes, i.e., identifiers associated with every block, can be used. The main point of the tie-breaking is to have a rule that quickly makes the block tree change to a state (by the new proposed blocks) where there are no more ties.

In the following theorem, we show liveness assuming a bound on the weight of crashed validators. The reason for not considering
Byzantine validators is that this would require to make stronger assumptions on the block proposal mechanism. Furthermore, for a concrete application of the general consensus framework it is usually necessary to show liveness again for the concrete block proposal mechanism and additional rules how validators send prevote and precommit messages.


Assume all validators obey the general consensus protocol and fork choice rule and   <1/3 of the validators crash. Then for any l ∈ℕ, an honest validator  with decision threshold τ_∈ (1/3,2/3] will eventually decide on a block at height l.



Consider an arbitrary set of blocks proposed and prevotes as well as precommits cast by all validators according to the consensus protocol from Definition <ref>. 
Assume that we have reached time +2Δ.
This means that all messages arrive  reliably within time Δ and all previously lost messages have been broadcast again and received by all validators.
In particular, the block tree 𝒯_ at the beginning of every block proposal time slot is the same for every 
validator . Note that due to lost or delayed messages before time , there can initially be multiple chains of the same length
that contain a block of largest height with prevotes by >2/3 of the validators. Because of different arrival
times of blocks, validators could decide for different canonical chains. However, after the first block is 
proposed, these ties are broken and the rule yields the same canonical chain for every honest validator. 

Let l∈ℕ and h_max be the largest height that any honest validator cast a prevote for. 
We show that an honest validator  with decision threshold τ_∈ (1/3,2/3] will eventually decide on a block at height l.
The canonical chain of all honest validators continues growing until there are two consecutive blocks B_1
and B_2 added to the chain with h(B_i)>max{l, h_max} for i=1,2.

We first show that any honest validator  can send a (B_1,·, ) message.
Assume  previously cast a precommit message for a block B'. We show that the precommit for B' does not prevent  to prevote for B_1. By assumption, B_1 was added to the chain that contains the block of largest height B̅ for which >2/3 of the validators cast prevotes (at the time when B_1 is added to the chain).
If B' is on a branch not containing B̅, then by <ref> validator  can prevote for B_1 because we have h(B')< h(B̅) as B' must have >2/3 prevotes and B is the block of largest height with >2/3 prevotes. Note that there can be at most one block at every height with >2/3 prevotes because of <ref> and the fact that >2/3 of the validators honestly follow the protocol.
If B' is on the same branch as B, then by the choice of B either B'=B or B' is an an ancestor of B. In both cases, the precommit for B' allows  to prevote for any descendants of B', in particular, for B_1. Thus,  can prevote for B_1.

Therefore, all >2/3 honest validators can send (B_1,·,·) messages and these messages reach all validators before the next block is proposed because we assume that the block proposal time slots have duration >2 Δ. This means that the honest validator of B_2 can include these prevote messages for B_1 into the block B_2. After receiving B_2,
all honest validators can now send a (B_1,·,·) messages. Hence, B_1 receives precommits by >2/3 of the validators and any validator with decision threshold τ∈ (1/3,2/3] will decide for B_1 and all ancestors of B_1.
In particular, any honest validator will decide for a block at height l since h(B_1)>l. This shows the claim.




 §.§ Accountability


We assume that all messages (B,T,) and (B,T,) are signed by the validator .
Using the current chain up to block T, any validator can verify if the messages sent by a validator  satisfy the consensus protocol rules <ref>–<ref>.
Note that we assume that it is impossible that a validator sends a message exclusively to one honest validator without all other validators eventually being able to learn about it, as the underlying peer-to-peer network will gossip the messages to all validators. 




 §.§ Lightweight consensus messages


In this section, we describe how multiple prevote and precommit messages can be concisely expressed via a single message, which we call an approve  message. An (k,p,T,) message contains a block T, two integers k,p ∈ℕ with k < h(T) and p < h(T) as well as the validator  sending the message. In an implementation, T can be the hash of the block T and  the public key and signature of the message by validator .
Moreover, for the message (k,p,T,) to be valid, p must be the height of the block B̅ of largest height that is an ancestor of T and the chain up to T includes prevotes
by >2/3 of the validators for B̅. As a convention, we assume that the genesis block has prevotes by all validators. The height p can be viewed as redundant information that can be derived from the chain up to block T. However, it is essential for a simple expression of the protocol rules and short proofs of any violation of the protocol rules.
We now state the rules that validators must satisfy when sending approve messages.


The approve messages by a validator  satisfy the if for any two distinct approve messages (k,p,T,) and (k',p',T',) with k≤ k' the following conditions are satisfied:


  * It holds that h(T)≤ k'. 

  * We have p≤ p'.



Let B_0,B_1,…, B_l be the current chain of validator  and T=B_r for r ∈{0,1,…, l}. Then the intuition behind an (k,p,T,) message is that  approves the blocks B_k+1,B_k+1,…, B_r.
We require that k < h(T) holds, such that a non-empty set of blocks up to block T is approved. 
Now, condition <ref> of the requires two  approve messages to be for blocks with disjoint sets of heights.
Note that, in particular, we cannot have k=k' for two distinct messages as otherwise we would obtain h(T)>k=k'.
Moreover,  <ref> ensures that a validator only switches to another chain extending a different block with >2/3 prevotes if that block has no smaller height. 

We now describe how an approve message translates to prevote and precommit messages.  


Let B_0,B_1,…, B_l be one branch of the block tree of validator . 
Then an ( k, p, B_r, ) message with r∈{k+1,…, l} implies the following prevotes and precommits: 


  *  casts a (A, B_r,) for every block A ∈{B_k+1,B_k+2, …, B_r}. 

  * Considering the prevotes and precommits included in the chain C=B_0,B_1,…, B_r (given via  approve  messages), let 

    j_1     :=max( {0 ≤ s ≤ r |∃ (B_s,·, )  in chain  C }∪{-1}) 
    
    j_2    :=max( {0 ≤  s ≤ k |∄  (B_s,·, )  in chain  C}∪{-1}) 
    
    j     :=max {j_1, j_2}+1.

Then  casts a (A,B_r,) for every block A in the set {B_j,…, B_r} that has (implied) prevotes by >2/3 of the validators included in the chain C. 




The idea is that the validator approves the blocks B_k+1,B_k+2, …, B_r by prevoting for them. Moreover, validator  sends a maximum number of precommits for blocks starting from its previous precommit while satisfying protocol rule <ref>. Note that for the precommits in <ref>, it is important that only the prevotes in the chain C and not those cast in <ref> are taken into account, so that for any (A,B_r,) we have h(A)≤ p. This property is needed in the proof of Lemma <ref>.

Next, we show that if a validator satisfies the for the approve messages, then the implied prevote and precommit messages satisfy the protocol rules from Definition <ref>.  


If the approve messages by a validator  satisfies the and  sends no additional prevote or precommit messages, then the prevotes and precommits implied by the transformation in Definition <ref> satisfy the protocol rules <ref>–<ref>.



Consider two messages (k,p,T,) and (k',p',T',) with k≤ k'. Because of condition <ref> of the , we have h(T) ≤ k' and thus

    {k+1,k+2, …, h(T)}∩{k'+1,k'+2, …, h(T')} = ∅.

Therefore all prevotes are cast for blocks at distinct heights, i.e., <ref> is satisfied. 

Next, consider an arbitrary (A,B_r,) that is cast according to the transformation of an (k,p,B_r,) message, where we use the notation from Definition <ref>. 
We then have A∈{B_j,B_j+1,…, B_r}, where j=max{j_1,j_2}+1. As j_2< j, validator  must have cast a prevote for A and by definition of the transformation there are (A,·, ·) messages by >2/3 of the validators included in the chain up to B_r.
Hence, <ref> is satisfied for all precommit messages.

Finally, consider a (A,T,) message and a (A',T',) message with h(A)<h(A'). If A' is a descendant of A, then <ref> is satisfied. Otherwise, we must show that <ref> is satisfied, i.e.,  there exists a
block B̅ at height h(B̅)≥ h(A) with (B̅,·, ·) messages by >2/3 of the validators
contained in the blockchain up to T'.

From now on, assume that <ref>  does not hold. Then both (A,T,) and (A',T',)  cannot be implied by the same message (k,p,T,), as otherwise A' is a descendant of A. Thus, there have to be two distinct messages (k,p,T,) and (k',p',T',) such that the first implies the message (A,T,) and the second implies the message  (A',T',). As (A',T',) is implied by (k',p',T',), we must have k'<h(A')≤ h(T'). 
For the sake of contradiction, let us assume that k≥ k'. Then the branch up to T cannot contain any implied prevote by  for a block at height h(A'), because we assume that this branch does not contain A' (otherwise again A' is a descendant of A),  already send a  (A',T',) message on a different branch and <ref> is satisfied. 
Using the notation from Definition <ref>, this implies that j_2≥ h(A') for the chain C up to T. 
Therefore any precommit implied by the message (k,p,T,) must be for blocks at height larger than h(A'). This would mean h(A)>h(A'), a contradiction. Hence, we must have k<k'. 

As k<k' holds, we must have p≤ p' by condition <ref> of the .
Note that we must have h(A)≤ p as p is the largest height of a block with prevotes by >2/3 of the validators included in the chain up to T. Let B̅ be the block at height p' that is an ancestor of T'. We have h(A)≤ p≤ p'=h(B̅) and there are  (B̅,·, ·) messages by >2/3 of the validators contained in the blockchain up to T'. Thus, <ref> is also satisfied. 


By Lemma <ref>, the protocol rules <ref>–<ref> are satisfied when validators cast prevotes and precommits implicitly via approve messages. This means that also Theorem <ref> holds for the case that
validators only use approve messages for the consensus algorithm.


Assume for the consensus algorithm validators only use approve messages that are transformed according to Definition <ref> and for any honest or crashing validator the approve messages satisfy the .
If the weight of Byzantine validators is <(τ -1/3) for τ∈ (1/3, 1], then any two honest validators with decision threshold at least τ never decide for conflicting blocks. 




 §.§ Dynamic set of validators


So far, we only considered a static set of validators . In blockchains networks, however, this set is typically changing over time as validators may want to stop participating in Proof-of-Stake and withdraw their deposit or different delegates get voted in the top ranks in a Delegated Proof-of-Stake system. 
The interesting question is what the implications of a  dynamically changing set of validators are for the safety and liveness guarantees from the last sections. 

In this section, we consider the approach that a change of validators (e.g., because of withdrawals, deposits or votes) is always possible and comes into effect without requiring finality, i.e., without requiring that the block or a descendant of the block containing the information of the change of validators receives precommits by a certain threshold of validators. 
Note that if the set of  validators changes over time, there can now be blocks at the same height which assume a different set of validators. 
For instance, one chain may contain the information regarding a change of validators, whereas another chain does not. 
Thus, we now associate a unique set of active validators _B to every block B of the block tree, which are the active consensus participant for that block. 
For one branch B_0,B_1,B_2… of the block tree, the active validators for a block B_l in that branch must be given by the information in the ancestor blocks in that branch, i.e., blocks B_0,B_1,…,B_l-1. 
In particular, the genesis block B_0 defines _B_1, the active validators for block B_1. 
The active validators  associated to a block B always contain the validator forging B and every validator that can cast prevotes and precommits for the block B. 
We further say that a validator  is active at block B if ∈_B. 

Furthermore, apart from a change in validators, it can happen that the weight ω_ associated with a validator  changes (e.g., due to a change in stake). For the following results, we need to distinguish between the changed and unchanged weights of validators. Hence, we model an increase of weight of validator  from ω_ to ω_' by assuming that a new validator ' with weight ω_'-ω_ is added to the new set of validators. Similarly, for a decrease of weight from ω_ to ω_', we assume that the original set of validators contains two validators  and ' with weights ω_' and ω_-ω_', respectively. The change of weight in this case is then modeled by ' leaving the set of validators. This allows us to only consider a change in the set of validators and not additionally consider changes of weights. Note that for any active set of validators _B for a block B the weights always need to satisfy ∑_∈_Bω_=1.

Moreover, if validators cast prevotes and precommits implicitly via approve messages, then for a ( k, p, B_r, )  message to be valid, we require  to be active at the blocks B_k+1,…, B_r. 
This way any implied (A, B_r,) cast according to Definition <ref> is for a block A where  is active. As a precommit is only implied if  previously made an implicit prevote, it holds that also all implied precommits are for blocks where  is active. 

We now show sufficient conditions for the safety and liveness property for the case of validators that change according to the mechanism described above.


Let ℬ be the set of blocks of the block tree. Then the following properties hold:


  * If ⋂_B∈ℬ_B contains >(4/3-τ) validators following the consensus protocol, then two honest validator in ⋃_B∈ℬ_B with decision threshold at least τ∈ (1/3,1] never decide for conflicting blocks (Safety).

  * Assume all active validators in the block tree follow the general consensus protocol and fork choice rule and <1/3 of the validators in any active validator set crash. 
If after the global stabilization time is reached, there is regularly an unchanged validator set for two consecutive blocks, then for any l ∈ℕ, an honest validator  with decision threshold τ_∈ (1/3,2/3] will eventually decide on a block at height l (Liveness).




The proof of the first part of the claim is similar to the proof of Theorem <ref>.
Assume, for the sake of contradiction, that there are two conflicting blocks B_1 and B_2 
as well as an honest validator _1 ∈⋃_B∈ℬ_B with decision threshold τ_1 deciding for B_1 and an honest validators _2∈⋃_B∈ℬ_B with decision threshold τ_2 deciding for B_2. 
By assumption, we have τ≤τ_1 and τ≤τ_2. Hence, there must be (B_1,·, ·) 
messages cast by >τ of the validators in _B_1 and also (B_2,·, ·) 
messages cast by >τ of the validators in _B_2.

Let  be the set of >(4/3-τ) validators obeying the protocol that is contained in ⋂_B∈ℬ_B by assumption. 
Note that  can contain both honest as well as crashing validators.
In particular, we have ⊆_B_1∩_B_2.
The set of validators _B_1∖ has weight <1-(4/3-τ)= τ -1/3, but there are  (B_1,·, ·) 
messages cast by >τ of the validators in _B_1. Hence, there are >1/3 validators in  that sent a (B_1,·, ·) message. Analogously,
there are also >1/3 validators in  that must have sent a (B_2,·, ·) message. 
 
Without loss of generality, we assume h(B_1) ≤ h(B_2).  
Let _1 ⊆ be the subset 
of >1/3 validators that send a precommit for B_1. By <ref>, every validator ∈_1 
must have also cast a  (B_1,·, ) message. Thus, by <ref>, no validator in ∈_1 
sends a prevote for any other block at height h(B_1). We must therefore have h(B_1)<h(B_2) as otherwise B_2 cannot obtain >2/3 prevotes
because _1 is contained in every active set of validators.

By <ref>, every validator ∈_1 only sends a prevote message for a block that is not a descendant of B_1 if there is a block B̅ at height h(B̅)≥ h(B_1) with (B̅,·,·) messages by >2/3 of the validators. As all validators in _1 obey the protocol, there have to be >2/3 prevotes for such a block B̅ by validators not in _1. This is a contradiction, as _1 is a set of >1/3 validators
that is contained in any active set of validators. Hence, no block that is not a descendant of B_1 can obtain >2/3 prevotes and thus no validator obeying the protocol sends a precommit for B_2. This means that the decision threshold of τ_2 precommit messages for block B_2 cannot be reached contradicting that the honest validator _2 decided for B_2.

The liveness property follows from Theorem <ref>, as the proof only requires an unchanged set of honest validators with weight >2/3 for two consecutive blocks.


The above theorem shows that the safety guarantee is only slightly weaker if only a small fraction of the validators change. However, several changes of a small fraction of validators over time could amount to almost all validators changing. The following result shows that as long as the validators finalize blocks in between these changes of validators, we can improve the safety guarantee above.



Let α∈ (0,1/3) and τ∈ (1/3+2 α, 1]. 
Let B, B' be two blocks in one branch such that B' is the descendant of B with minimal height such that the chain up to B' contains >τ precommits for B or a descendant of B. 
We assume that between all such pairs of blocks B and B' in the block tree <α of the validators obeying the protocol change. 
If any active validator set contains >4/3-τ+2 α validators obeying the protocol, then two honest validators with decision threshold at least τ never decide for conflicting blocks.



Let us assume, for the sake of contradiction, that there are two conflicting blocks B_1 and B_2 such that an honest validator _1 with decision threshold τ_1 decides for B_1 and another honest validators _2 with decision threshold τ_2 decides for B_2. 
Let A_0 be the block of largest height that is a common ancestor of B_1 and B_2. 
Moreover, let A_1 be the first descendant of A_0 on the branch containing B_1 such that the branch contains >τ precommits for A_1. 
Similarly, let A_2 be the first descendant of A_0 on the branch containing B_2 such that the branch contains >τ precommits for A_2. 
The setting is shown in Figure <ref>. As τ_1≥τ, there must be at least τ precommits for B_1 contained in the branch containing B_1 and therefore we must have A_1=B_1 or A_1 is an ancestor of B_1. 
The same holds for A_2 and B_2.
Without loss of generality let h(A_1) ≤ h(A_2). 

Let _0 be the subset of all validators in _A_0 that obey the protocol. 
The weight of all validators in _0 is >4/3-τ+2 α by assumption.
We also know by assumption that <α of the validators obeying the protocol change before a block on a branch receives >τ precommit. 
This means that the weight of validators in _0∖_A_i is <α for i ∈{1,2}.
Hence, :=_0 ∩_A_1∩_A_2 is a set of validators of weight >4/3 -τ that obey the protocol. 
The validator set  is further contained in the active set of validators associated to any block on the path from A_0 to A_1 or the path from A_0 to A_2. 

The set of validators _A_1∖ has weight <1-(4/3-τ)= τ -1/3, but there are (A_1,·,·) by >τ of the validators in the chain containing B_1.
Hence, there must be a subset _1⊆ of >1/3 validators that cast a precommit for A_1. 
This also implies that we cannot have h(A_1)=h(A_2) as there can only be ≤ 2/3 prevotes for A_2 and hence no validator ∈_A_2 obeying the protocol would cast a (A_2,·,) by <ref>. Thus, the threshold of τ precommits for block A_2 cannot be reached in this case and we must have h(A_1)<h(A_2).



By <ref>, every validator ∈_1 only sends a prevote message for a block that is not a descendant of A_1 if there is a block B̅ at height h(B̅)≥ h(A_1) with (B̅,·,·) messages by >2/3 of the validators. 
As all validators in _1 obey the protocol, there have to be >2/3 prevotes for such a block B̅ by validators not in _1. 
This is a contradiction, as _1 is a set of >1/3 validators that is contained in the active set of validators associated with every block on the path from A_0 to A_2.  
Hence, block A_2 cannot obtain >2/3 prevotes and thus no validators obeying the protocol sends a precommit for A_2. 
This means that the threshold of τ precommits for block A_2 cannot be reached, which is a contradiction.



Theorem <ref> outlines a way how we can maintain close to optimal safety guarantees while allowing dynamic validators. Assume that we only allow a change of validators with overall weight <1/100 at a time, i.e., after a change of validators from  to ' we require the new set of validators ' to finalize a block before another change of validators can occur. If we assume that we always have >2/3+2/100 validators following the protocol at any given time, then Theorem <ref> yields that the safety property is satisfied. 

Allowing an arbitrary large change of validators at a given time while preserving the safety property under the assumption that at any time >2/3 of the obey the protocol, requires a much more complex mechanism of two set of validators, i.e., both  and ', to vote on the same blocks.
For the Casper the Friendly Finality Gadget consensus algorithm this approach is sketched in <cit.>.





§ WEIGHTED CONSENSUS PROTOCOL


We now describe , a consensus protocol for the Lisk ecosystem,  which is based on the general consensus framework from the last section. 
The consensus protocol is flexible enough to work with different configurations of the Delegated Proof-of-Stake validator selection mechanism in the Lisk ecosystem. 

In the Delegated Proof-of-Stake system in Lisk Mainnet, in every round of 103 consecutive blocks there are 103 distinct delegates that can propose a block. 
The 103 delegates include the 101 delegates with largest vote weight and two randomly selected additional delegates. 
Only the 101 delegates with largest vote weight are supposed to participate in the consensus protocol and cast prevotes and precommits, whereas the two additional delegates only propose blocks. 
This is modeled by setting the active set of validators to the 103 forging delegates for each block of the round, assigning uniform weights of  ω_=1/101 to each of the 101 delegates with largest vote weight and weight ω_=0 to the two additional forging delegates. .
In particular, we then have ∑_∈_Bω_ = 1 for every block B with with active validator set _B. 
For different numbers of forging delegates per round and delegates participating in the  consensus protocol the weights can be assigned analogously such that  ∑_∈_Bω_ = 1 holds for every block.

Instead of using separate consensus messages, in all prevotes and precommits are implied by two additional integers added to blocks using
the same idea as the lightweight consensus messages introduced in the last section. 
Hence, the additional two integers in the blocks are the only overhead of the consensus protocol.


Let τ∈ (1/3, 1] and ρ∈ℕ be two protocol parameters. 
Let C:=B_0,B_1,…, B_l-1 be the current chain of validator  and h_0∈{0,1,…, l} be the height of the first block in the current chain since when  has been continuously in the active validator set.


  * When  proposes block B_l as a child of B_l-1, it adds the following information to the block: 


  h_previous The largest height of a block that  previously proposed (on any branch) and 0 if  has not proposed any block.

  h_prevoted The height of the block of largest height with >2/3 prevotes in the current chain B_0,B_1,…, B_l-1.

In general, for a block B we use the notation h_previous(B) and h_prevoted(B) to refer to the values above.

  * If h_previous(B_l)<h(B_l) holds, then the information in block B_l implies prevotes and precommits for blocks in the following order: 


  * Let k:=max{h_previous(B_l), h_0-1, l - ρ}. 
Then the block implies a (A, B_l,) cast for every block A ∈{B_k+1,B_k+2, …, B_l}. 

  * Considering the implied prevotes and precommits included in the chain C (via the additional information in the block), let 


    j_1     :=max(  {0 ≤ s < l |∃ (B_s,·, )  in chain  C }∪{-1}) 
    
    j_2    :=max(  {0 ≤  s ≤ h_previous(B_l) |∄  (B_s,·, )   in chain  C}∪{-1}) 
    
    j     :=max {j_1, j_2, h_0-1, l - ρ}+1.

Then the block implies a (A,B_l,) for every block A in the set {B_j,…, B_l} that has prevotes by >2/3 validators included in the chain C. 



  * A block B and all ancestors of B are finalized if there are precommits for B by >τ validators included in the chain C.

  * Validators follow the rule, where the block of largest height with >2/3 prevotes in a chain A_0,A_1,…, A_s is computed taking only the prevotes implied by blocks A_0,A_1,…, A_s-1, and not those implied by A_s, into account. 

  * We assume that the block proposal mechanisms assign block slots to the active validators in a round-robin fashion. 
That is, if a validator set  is first active for a block B, then the block slot for block B and the next ||-1 blocks slots are each assigned to one distinct validator in . 
We further require that ρ≥ 3 · |_B| holds for any block B in the block tree.

 

The protocol is an application of the general consensus framework from the last section,
where validators only cast prevotes and precommits via the two additional integers contained in blocks.
The values h_previous and h_prevoted in block B_l correspond to the validator  first proposing block B_l and afterwards sending the message  (h_previous,h_prevoted,B_l,). 
However, the transformation of the two integers in blocks to prevote and precommit messages above contains two modifications compared to the transformation for approve messages in Definition <ref>. 
First of all, we have k=max{h_previous, h_0-1, l - ρ} instead of k=h_previous. 
The reason for enforcing k≥ h_0-1 is to ensure that the implied prevotes are only for blocks at heights where validator  was active. 
We further require that k≥  l - ρ holds for performance reasons so that it is sufficient to consider the previous ρ-1 blocks in the chain when updating the number of prevotes for blocks. 
Note that we require that ρ≥ 3 · |_B| holds for any block B in the block tree so that ρ is large enough such that a block can be finalized after ρ-1 additional blocks are added on top, i.e., the prevotes and precommits implied by ρ-1 subsequent blocks are sufficient such that a block can reach >τ precommits, see the proof of the liveness condition in Theorem <ref> for details.
Secondly, we have j =max {j_1, j_2, h_0-1, l - ρ}+1 instead of j :=max {j_1, j_2}+1. Again, this ensures that all implied precommits are for blocks where  was active and also for performance reasons all precommits are only for a subset of the previous ρ-1 blocks.
Overall, it is important to note that the prevotes and precommits implied by the transformation above are a subset of the prevotes and precommits implied
according to Definition <ref> when instead sending the message (h_previous,h_prevoted,B_l,).

A subtlety of the transformation <ref> above is that we consider only the prevotes implied by all blocks up to B_l-1 and not the prevotes implied by <ref>. This is analogous to the transformation for approve messages in Definition <ref>.

We establish some basic properties of the protocol in the following lemma. 


Let B_1 and B_2 be two distinct blocks proposed by a validator  obeying the protocol. Then the following properties hold: 


  * The rule implies that a branch with tip B is chosen over a branch with tip A, if the following conditions are satisfied: 

    h_prevoted(B)> h_prevoted(A)    or   (h_prevoted(B)= h_prevoted(A)  and  h(B)>h(A)).


  * If B_1 is proposed before B_2, then the following inequalities hold:

    h_previous(B_1) ≤ h_previous(B_2),    
    h_prevoted(B_1) ≤ h_prevoted(B_2),    
    h(B_1) ≤ h_previous(B_2).


  * If B_1 is proposed before B_2 and h_prevoted(B_1)=h_prevoted(B_2) holds, then we must have h(B_1)<h(B_2).

  * Block B_1 is proposed before B_2 if and only if 

    (h_previous(B_1),h_prevoted(B_1),h(B_1))<_lex (h_previous(B_2),h_prevoted(B_2),h(B_2)),

where <_lex is the lexicographical ordering.

  * If any two blocks by validator  satisfy the inequalities in <ref>, then the implied prevotes and precommits according to the protocol satisfy the conditions of the general consensus framework in Definition <ref>. 






  * According to the rule, the first deciding factor is the largest height of a block with >2/3 prevotes contained in some branch of the block tree. For a chain with tip A, the largest height of a block with >2/3 prevotes is given by h_prevoted(A)  because the prevotes implied by block A are not taken into account. If there are multiple chains that contain a block with >2/3 prevotes of the same height, then the longer chain containing these prevotes has priority according to the rule. This immediately yields the condition in the claim.


  * As B_2 is proposed after B_1 and the largest height of a block previously proposed is non-decreasing, we must have h_previous(B_1)≤ h_previous(B_2). As validator  follows the  rule, the tips of the canonical chain of  satisfy that h_prevoted(·) is non-decreasing by claim  <ref>. Thus, we must have h_prevoted(B_1)≤ h_prevoted(B_2).
Moreover, when proposing B_2, the largest height of a block previously proposed must be at least h(B_1). This implies h(B_1)≤ h_previous(B_2).


  * By claim <ref>, every time validator  switches to a different chain, either h_prevoted(·) is strictly increasing or it remains unchanged and the height of the tip strictly increases.
The same holds every time a new child is added to the tip of the chain of validator  (either proposed by  or another validator).
Thus, if h_prevoted(B_1)=h_prevoted(B_2) holds, then we must have h(B_1)<h(B_2).


  * Assume B_1 is proposed before B_2. By claim <ref>, we must have h_previous(B_1) ≤ h_previous(B_2) and h_prevoted(B_1) ≤ h_prevoted(B_2). Moreover, by <ref>, we have h(B_1)<h(B_2) if h_prevoted(B_1) = h_prevoted(B_2). Thus, Inequality (<ref>) must hold.
The other direction follows by contraposition.


  * We need to show that the implied prevotes and precommits according to the transformation in Definition <ref> satisfy the protocol rules
<ref>–<ref> of the general consensus framework. The proof works analogous to the proof of Lemma <ref>.

Let T and T' be two distinct blocks proposed by a validator , where T' is proposed after T. By claim <ref>, we have h(T)≤ h_previous(T'). Any (A,T,) implied by T satisfies
h(A)≤ h(T) and any  (A',T',) implied by T' satisfies h(A')> h_previous(T')≥ h(T). This means that all implied prevotes are for distinct heights, i.e., <ref> is satisfied. 

Next, consider some (A,B_l,) implied by a block B_l, where we use the notation from Definition <ref>. We then have h(A)> j_2
and hence  must have cast a prevote for A (implied by <ref> or a previous block by  in the current chain). By the definition of the transformation there are >2/3 prevotes for A in the chain up to B_l-1.
Hence, <ref> is satisfied for all precommit messages.

Finally, for showing <ref>, consider a (A,T,) and a (A',T',)  with h(A)<h(A') implied by two blocks T and T'. If A' is a descendant of A, then <ref> is satisfied. Otherwise, we must show that there exists a
block B̅ at height h(B̅)≥ h(A) with (B̅,·, ·) by >2/3 of the validators contained in the chain up to block T'.

We first show that T' must be proposed after T. Assume, for the sake of contradiction, that T' is proposed before T. By claim <ref>, we then have h(T')≤ h_previous(T)< h(T) and, 
in particular, h(A')≤ h(T') < h(T).
By our assumption, A' is not a descendant of A so
A' cannot be on the branch containing A and T. But then the branch containing A and T does not contain any prevote for a block at height h(A') because <ref> is satisfied. This means that any precommit implied by T must be for blocks at height at least h(A')+1, which contradicts h(A)<h(A') and that (A,T,) is implied by T.
Hence, T' must be proposed after T. 

By claim <ref>, we then obtain h_prevoted(T) ≤ h_prevoted(T'). We further have h(A) ≤ h_prevoted(T) because h_prevoted(T) is the largest height of a block with prevotes by >2/3 of the validators included in the chain up to T. Let B̅ be the block at height h_prevoted(T') that is an ancestor of T'. We have 
h(A)≤ h_prevoted(T) ≤ h_prevoted(T')=h(B̅)
and there are (B̅,·, ·) by >2/3 validators contained in the blockchain up to T'. Thus, <ref> is also satisfied. 


Let A and B be two distinct blocks proposed by a validator . Using Lemma <ref> <ref>, we can derive which of the blocks was proposed first assuming that validator  follows the protocol. We call the blocks A and B contradicting if, assuming this proposal order, they do not satisfy one of the inequalities in Lemma <ref> <ref> or the condition of Lemma <ref> <ref>.

Lemma <ref> directly yields the following two properties: 
The blocks proposed by a validator obeying  the protocol are never contradicting. Secondly, if none of the blocks of a validator are contradicting, then the implied prevotes and precommits satisfy the conditions of the general consensus framework in Definition <ref> due to Lemma <ref> <ref>. Hence, in order to detect whether the implied prevotes and precommits of a validator violate the general consensus framework, it is sufficient to check whether any pair of blocks by that validator is contradicting.

Note that we obtain all properties in the above paragraph if we only require blocks to satisfy all inequalities in Lemma <ref> <ref>. A violation of Lemma <ref> <ref> only implies a violation of the fork choice rule, but not that the prevotes and precommits violate the general consensus framework. For the liveness property, it is, however, important that validators choose one chain according to the fork choice rule and, in particular, do not forge multiple blocks with the same height and the same h_prevoted on different chains because this causes a tie in the fork choice rule if the blocks are at the tip of the chains.

The next lemma allows to reduce the number of checks to ensure that the blocks of a validator are not contradicting. Instead of checking the inequalities in Lemma <ref> <ref> and the condition of Lemma <ref> <ref> for any pair of blocks by the same validator, it is sufficient to only check pairs of successive blocks by the same validator in one chain.


Let C := B_0, B_1, …, B_l be a chain of blocks and B_i, B_j, B_k blocks forged by validator  such that 0 ≤ i <j <k≤ l. If the pairs of blocks (B_i,B_j) and (B_j,B_k) are not contradicting, then the pair of blocks (B_i, B_k) is also not contradicting.



By assumption, we have h_previous(B_i) ≤ h_previous(B_j) and h_previous(B_j) ≤ h_previous(B_k). 
We therefore obtain h_previous(B_i) ≤ h_previous(B_k). The same argument shows  h_prevoted(B_i) ≤ h_prevoted(B_k). We further have h(B_i)  ≤ h_previous(B_j)≤ h_previous(B_k) and therefore (B_i,B_k) satisfies all three inequalities in Lemma <ref> <ref>. 

Moreover, if h_prevoted(B_i) = h_prevoted(B_k) holds, then we must have both h_prevoted(B_i) = h_prevoted(B_j) and
h_prevoted(B_j) = h_prevoted(B_k).
This implies h(B_i)<h(B_j) and h(B_j)<h(B_k) by assumption. Hence, we also have h(B_i)<h(B_k) implying that B_i and B_k are not contradicting.


Using Lemma <ref>, we now show the desired safety, liveness and accountability properties of the protocol.
Note that for showing the liveness property we assume that <1/3 of the validators are offline, i.e., not forging any blocks, and we do not consider Byzantine validators. As validators cast prevotes and precommits together with the block proposal in the protocol, Byzantine validators could intentionally create competing branches in the block tree so that the prevotes and precommits of some honest validators are not considered as their block is not eventually included in the canonical chain. Such an attack would only be successful if a substantial number of Byzantine validators coordinate the creation of competing branches and at regular times multiple Byzantine validators can consecutive propose blocks so that the competing chain becomes longer than the chain previously forged by the honest validators. We believe that such an attack is rather unlikely as it requires a lot of coordination and a favorable validator ordering for the attackers. Further, it only effects the liveness property, but not the safety property.



The protocol with parameters  τ∈ (1/3, 1] and ρ∈ℕ has the following properties:


  * Let ℬ be the set of blocks of the block tree.
If ⋂_B∈ℬ_B contains >(4/3-τ) obeying the protocol, then two honest validator in ⋃_B∈ℬ_B with decision threshold at least τ never finalize conflicting blocks.


  * Assume that for any branch in the block tree <α among the validators obeying the protocol change without a block obtaining >τ precommits. 
If any active validator set contains >4/3-τ+2 α validators obeying the protocol, then two honest validators with decision threshold at least τ never decide for conflicting blocks.


  * Assume all active validators in the block tree follow the general consensus protocol and fork choice rule and <1/3 of the validators in any active validator set crash. 
If after the global stabilization time is reached, there is regularly an unchanged validator set for ρ consecutive blocks, then for any l ∈ℕ, an honest validator  with decision threshold τ_∈ (1/3,2/3] will eventually decide on a block at height l.

  * If a Byzantine validator forges blocks such that the implied prevotes and precommits violate the general consensus framework, then this protocol violation can be detected and the Byzantine validator can be identified. 





By Lemma <ref>, the implied prevotes and precommits in the protocol satisfy the protocol rules <ref>–<ref>. Then the first claim follows directly from Theorem <ref> and the second claim from Theorem <ref>.

For the liveness property in the third claim, consider an arbitrary state of the block tree and an arbitrary set of blocks proposed according
to the protocol. 
Moreover, we assume that we have reached the global stabilization time  so that all messages arrive reliably within time Δ. 
Let further l ∈ℕ and h_max be the largest height that any validator proposed a block for.
We show that an honest validator with decision threshold τ_∈ (1/3,2/3] eventually finalizes a block at height l.

After time +Δ, all honest validators are aware of all competing chains. There could be multiple competing chains for which h_previous(·) and h(·) of the tip of the chain is the same, but one block proposed by an honest validator always breaks these ties. Afterwards, in every proposal slot, there is one unique block A such that for every other block A' either h_prevoted(A)> h_prevoted(A') or h_prevoted(A)= h_prevoted(A') and h(A)>h(A') holds. This means A is the tip of the canonical chain of every honest validator. 

This canonical chain for all honest validators will continue growing until its tip has height >max{l, h_max}. 
By assumption, there will be ρ consecutive blocks B^(1), …,B^(ρ) appended to the canonical chain such that B^(1)>max{l, h_max} and ⋂_i ∈{1,…,ρ}_B^(i) contains an honest set of validators _H of weight >2/3. 
We show that B^(1) will be considered final by any honest validator  with decision threshold τ_∈ (1/3,2/3].

The  protocol assumes that the block proposal mechanism assigns block slots in a round-robin fashion and that  3 |_B^(i) | ≤ρ for i ∈{1,…,ρ}. 
In particular, this implies that there is j ∈{1,…,ρ} such that every validator in 
_H forges at least one of the blocks in B^(1), …,B^(j) and at least one of the blocks in B^(j+1), …,B^(ρ). 
The first block B^(i) in B^(1), …,B^(j) proposed by an honest validator ∈_H satisfies h_previous(B^(i))<B^(1) as we assume there is only one growing canonical chain and hence  did not forge any block at height ≥ h(B^(1)) already. 
By the transformation in Definition <ref>, B^(i) implies a prevote for B^(1) as  was active at height B^(1) and B^(i)-B^(1)≤ρ -1. 
Hence, after B^(j) is added to the chain, every validator in _H has cast a prevote for B^(1), i.e., B^(1) has prevotes by >2/3 of the validators included in the chain up to B^(j).
If a validator ∈_H has not already cast a precommit for B^(1), then the first subsequent block B^(i) with i ≥ j+1 by  implies a precommit by  for B^(1), because the following holds for the transformation in Definition <ref>:


  * j_2<B^(1), as all honest validators add blocks to the same canonical chain extending B^(1),

  * j_1<B^(1), because otherwise  already made a precommit for B^(1),

  * h_0 ≤B^(1), since all validators in _H are continuously active, 

  * B^(i)-B^(1)≤ρ -1.    

Hence, after B^(ρ) is added to the chain, there are precommits for B^(1) by every validator in _H in the current chain as each of them forges at least one block in B^(j+1), …,B^(ρ) by assumption. 
As the weight of validators in  _H is larger than 2/3, the chain up to block B^(ρ) therefore contains precommits by >2/3 precommits for B^(1). Thus, any honest validator  with decision threshold τ_∈ (1/3,2/3] can decide for B^(1) and all ancestors of B^(1). 
In particular, any honest validator finalizes a block at height l as B^(1)>l.

For the last claim, note that Lemma <ref>
<ref> states the conditions that must hold if a validator follows the protocol. By Lemma <ref> <ref>, these are also
sufficient for the implied prevotes and precommits to satisfy <ref>–<ref> of the general consensus framework. In order to determine whether the implied prevotes and precommits of blocks forged by a validator  obey the protocol rules <ref>–<ref>, it is therefore sufficient to consider every pair of blocks B_1 and B_2 proposed by ,
determine which one was proposed first according to Lemma <ref> <ref>, and then check if the inequalities given in Lemma <ref> 
<ref> hold.




§ CONCLUSION


We introduced a general consensus framework for blockchains which allows to prove safety and liveness depending on the number of Byzantine validators. As a concrete application of the consensus framework we defined the protocol, which allows to obtain strong guarantees with respect to safety and liveness while requiring no additional messages for the consensus as the necessary information is efficiently
encoded in the blocks.

Another interesting possible application of the general consensus framework could be to combine it together with a
suitable aggregate signature scheme. For instance, validators could send a (h(B_l)-1,·,B_l,) message
for the block they believe to be the correct block at height l. Using an aggregate signature scheme, these messages could be efficiently aggregated in the network and only added to any child block of B_l by the next validator. Applying the properties of the general consensus framework analogous to the case of the protocol, it is possible to show that a block can be finalized already after two additional blocks are added as descendants.




