Morpheus Consensus:
Excelling on Trails and Autobahns

While blockchains may often need to handle high throughputs, it is not the case that all blockchains need to deal with high throughput all of the time. For example, various “subnets” or “subchains” may only have to deal with high throughputs infrequently, and should ideally be optimised to deal also with periods of low throughput. The motivation for the present paper therefore stems from a real-world need for consensus protocols that deal efficiently with both high and low throughputs. Specifically, we are interested in a setting where:

1. 1.

   The processes/validators may be few, but could be up to a few hundred in number.

2. 2.

   The protocol should be able to handle periods of asynchrony, i.e. should operate efficiently in the partially synchronous setting.

3. 3.

   The protocol is required to have optimal resilience against Byzantine adversaries, i.e., should be live and consistent so long as less than 1/3 of processes display Byzantine faults, but should be optimised to deal with the “normal case” that processes are not carrying out Byzantine attacks and that faults are benign (crash or omission failures).

4. 4.

   There are expected to be some periods of high throughput, meaning that the protocol should ideally match the state-of-the-art during such periods.

5. 5.

   Often, however, throughput will be low. This means the protocol should also be optimised to give the lowest possible latency during periods of low throughput.

6. 6.

   Ideally, the protocol should be “leaderless” during periods of low throughput: the use of leaders is to be avoided if possible, since, even without malicious action, leaders who are offline/faulty may cause significant increases in latency.

7. 7.

   Ideally, the protocol should also be “quiescent”, i.e., there should be no need for the sending and storing of new messages when new transactions are not being produced.

8. 8.

   Transactions may come from clients (not belonging to the list of processes/validators), but will generally be produced by the processes themselves.

We introduce and analyse the Morpheus protocol, which is designed for the setting described above. The protocol is quiescent and has the following properties during periods of low throughput:

• $\mathrm{■}$

  It is leaderless, in the sense that transactions are finalized without the requirement for involvement by leaders.

• $\mathrm{■}$

  Transactions are finalized in time $3\delta$, where $\delta$ is the actual (and unknown) bound on message delays after GST.¹¹1The partially synchronous setting and associated notions such as GST are formally defined in Section 2. This more than halves the latency of existing DAG-based protocols and variants such as Autobahn [15] for the low throughput case, and even decreases latency by at least $\delta$ when compared with protocols such as PBFT (and even if we suppose leaders for those protocols are non-faulty), since the leaderless property of our protocol negates the need to send transactions to a leader before they can be included in a block.²²2See the online version of the paper at https://arxiv.org/abs/2502.08465 for a detailed analysis of latency and complexity considerations.

• $\mathrm{■}$

  A further advantage over protocols such as PBFT and Tendermint is that crash failures by leaders are not able to impact latency during periods of low throughput.

During periods of high throughput, Morpheus is very similar to Autobahn, and so inherits the benefits of that protocol. In particular:

• $\mathrm{■}$

  It has the same capability to deal with high throughput as DAG-based protocols and variants such as Autobahn, and has the same ability to recover quickly from periods of asynchrony (“seamless recover” in the language of Autobahn).

• $\mathrm{■}$

  It has the same latency as Autobahn during high throughput, matching the latency of Sailfish [24], which is the most competitive existing DAG-based protocol in terms of latency.

• $\mathrm{■}$

  Morpheus has the same advantages as Autobahn in terms of communication complexity when compared to DAG-based protocols such as Sailfish, DAG-Rider [17], Cordial Miners [19], Mysticeti [3] or Shoal [26].

Of course, much of the complexity in designing a protocol that operates efficiently in both low and high throughput settings is to ensure a smooth transition and consistency between the different modes of operation that the two settings necessitate.

In Section 3, we also formalise the task of Extractable SMR, as an attempt to make explicit certain implicit assumptions that are often made by papers in the area. While State-Machine-Replication (SMR) requires correct processes to finalize logs (sequences of transactions) in such a way that consistency and liveness are satisfied, it is well understood in the community that some papers describing protocols for SMR specify protocols that do not actually aim to explicitly ensure all correct processes receive all finalized blocks (required for liveness). Roughly, the protocol instructions suffice instead to ensure data availability (that each finalized block is received by at least one correct process), and then the protocol is required to establish a total ordering on transactions that can be extracted via further message exchange, given data availability. Liveness is therefore only achieved after further message exchange (and via some unspecified method), which (while a trivial addition if one does not consider communication complexity) is not generally taken into account when calculating message complexity.

In Hotstuff [29], for example, one of the principal aims is to ensure linear message complexity within views. Since this precludes all-to-all communication within views, a Byzantine leader may finalize a block of transactions in a given view without certain correct processes even receiving the block. Those correct processes must eventually receive the block for liveness to be satisfied, but the protocol instructions do not explicitly stipulate the mechanism by which this should be achieved. While ensuring that all correct processes receive the block is trivial if one is not concerned with communication complexity (e.g., just have each correct process broadcast each finalized block they observe, together with a quorum certificate verifying that the block is finalized), the messages required to do so are not counted when analyzing message complexity. The obvious methods of ensuring that the block is propagated to all correct processes will require more than linear communication complexity, which undermines the very point of the Hotstuff protocol.

The question arises, “what precisely is the task being achieved by such protocols if they do not satisfy liveness without further message exchange (and so actually fail to achieve the task of SMR with the communication complexity computed)”. We assert that the task of Extractable SMR is an appropriate formalisation of the task being achieved, and hope that the introduction of this notion is a contribution of independent interest.

The paper structure is as follows: Section 2 describes the basic model and definitions; Section 3 formalises the task of Extractable SMR; Section 4 gives the intuition behind the Morpheus protocol; Section 5 gives the formal specification of the protocol; Appendix A formally establishes consistency and liveness; Appendix B discusses related work. See the online version of the paper at https://arxiv.org/abs/2502.08465 for a detailed analysis of latency and complexity considerations.

Our cryptographic assumptions are standard for papers in distributed computing. Processes communicate by point-to-point authenticated channels. We use a cryptographic signature scheme, a public key infrastructure (PKI) to validate signatures, a threshold signature scheme [6, 23], and a cryptographic hash function $H$. The threshold signature scheme is used to create a compact signature of $m$-of-$n$ processes, as in other consensus protocols [30]. In this paper, $m=n-f$ or $m=f+1$. The size of a threshold signature is $O(\kappa )$, where $\kappa$ is a security parameter, and does not depend on $m$ or $n$. We assume a computationally bounded adversary. Following a common standard in distributed computing and for simplicity of presentation (to avoid the analysis of negligible error probabilities), we assume these cryptographic schemes are perfect, i.e., we restrict attention to executions in which the adversary is unable to break these cryptographic schemes. Hash values are thus assumed to be unique.

We consider a discrete sequence of timeslots $t\in {\mathbb{N}}_{\ge 0}$ in the partially synchronous setting: for some known bound $\mathrm{\Delta }$ and unknown Global Stabilization Time (GST), a message sent at time $t$ must arrive by time $\max \{\text{GST},t\}+\mathrm{\Delta }$. The adversary chooses GST and also message delivery times, subject to the constraints already specified. We write $\delta$ to denote the actual (unknown) bound on message delays after GST, noting that $\delta$ may be significantly less than the known bound $\mathrm{\Delta }$.

We do not suppose that the clocks of correct processes are synchronized. For the sake of simplicity, however, we do suppose that the clocks of correct processes all proceed in real time, i.e. if $t^{\prime }>t$ then the local clock of correct $p$ at time $t^{\prime }$ is $t^{\prime }-t$ in advance of its value at time $t$. This assumption is made only for the sake of simplicity, and our arguments are easily adapted to deal with a setting in which there is a known upper bound on the difference between the clock speeds of correct processes after GST. We suppose all correct processes begin the protocol execution before GST. A correct process may begin the protocol execution with its local clock set to any value.

Transactions are messages of a distinguished form. For the sake of simplicity, we consider a setup in which each process produces their own transactions, but one could also adapt the presentation to a setup in which transactions are produced by clients who may pass transactions to multiple processes.

State-Machine-Replication (SMR) requires correct processes to finalize logs (sequences of transactions) in such a way that consistency and liveness are satisfied. As noted in Section 1, however, for many papers describing protocols for SMR, the explicit instructions of the protocol do not actually suffice to ensure liveness without further message exchange, potentially impacting calculations of message complexity and other measures. Roughly, the protocol instructions do not explicitly ensure that all correct processes receive all finalized blocks, but rather ensure data availability (that each finalized block is received by at least one correct process), and then the protocol is required to establish a total ordering on transactions that can be extracted via further message exchange, given data availability. Although it is clear that the protocol can be used to solve SMR given some (as yet unspecified) mechanism for message exchange, the protocol itself does not solve SMR. So, what exactly is the task that the protocol solves?

If $\sigma$ and $\tau$ are strings, we write $\sigma \subseteq \tau$ to denote that $\sigma$ is a prefix of $\tau$. We say $\sigma$ and $\tau$ are compatible if $\sigma \subseteq \tau$ or $\tau \subseteq \sigma$. If two strings are not compatible, they are incompatible. If $\sigma$ is a sequence of transactions, we write $\mathrm{𝚝𝚛}\in \sigma$ to denote that the transaction $\mathrm{𝚝𝚛}$ belongs to the sequence $\sigma$.

If $𝒫$ is a protocol for extractable SMR, then it must specify a function $ℱ$ that maps any set of messages to a sequence of transactions. Let $M^{\ast }$ be the set of all messages that are received by at least one (potentially Byzantine) process during the execution. For any timeslot $t$, let $M(t)$ be the set of all messages that are received by at least one correct process at a timeslot $\le t$. We require the following conditions to hold:

Consistency.

For any $M_1$ and $M_2$, if $M_1\subseteq M_2\subseteq M^{\ast }$, then $ℱ(M_1)\subseteq ℱ(M_2)$.

Liveness.

If correct $p$ produces the transaction $\mathrm{𝚝𝚛}$, there must exist $t$ such that $\mathrm{𝚝𝚛}\in ℱ(M(t))$.

Note that consistency suffices to ensure that, for arbitrary $M_1,M_2\subseteq M^{\ast }$, $ℱ(M_1)$ and $ℱ(M_2)$ are compatible. To see this, note that, by consistency, $ℱ(M_1)\subseteq ℱ(M_1\cup M_2)$ and $ℱ(M_2)\subseteq ℱ(M_1\cup M_2)$.

In this paper, we focus on the task of Extractable SMR. One way to convert a protocol for Extractable SMR into a protocol for SMR is to assume the existence of a gossip network, in which each process has some (appropriately chosen) constant number of neighbors. Using standard results from graph theory ([5] Chapter 7), one can assume correct processes form a connected component: this assumption requires classifying some small number of disconnected processes that would otherwise be correct as Byzantine. If each correct process gossips each “relevant” protocol message, then all such messages will eventually be received by all correct processes. Overall, this induces an extra communication cost per message which is only linear in $n$. Of course, other approaches are also possible, and in this paper we will remain agnostic as to the precise process by which SMR is achieved from Extractable SMR.

Roughly, by the “low throughput mode”, we mean a setting in which processes produce blocks of transactions infrequently enough that correct processes agree on the order in which they are received, meaning that transaction blocks can be finalized individually upon arrival. Our aim is to describe a protocol that finalizes transaction blocks with low latency in this setting, and without the use of a leader: the use of leaders is to be avoided if possible, since leaders who are offline/faulty may cause significant increases in latency. The way in which Morpheus operates in this setting is simple:

1. 1.

   Upon having a new transaction block $b$ to issue, a process $p_i$ will send $b$ to all processes.

2. 2.

   If they have not seen any blocks conflicting with $b$, other processes then send a 1-vote for $b$ to all processes.

3. 3.

   Upon receiving $n-f$ 1-votes for $b$, and if they still have not seen any block conflicting with $b$, each correct process will send a 2-vote for $b$ to all others.

4. 4.

   Upon receiving $n-f$ 2-votes for $b$, a process regards $b$ as finalized.

Recall that $\delta$ is the actual (unknown) bound on message delays after GST. If the new transaction block $b$ is created at time $t>$GST, then the procedure above causes all correct processes to regard $b$ as finalized by time $t+3\delta$.

Which blocks should a new transaction block $b$ point to? For the sake of concreteness, let us specify that if there is a sole tip amongst the blocks received by $p_i$, i.e., if there exists a unique block $b^{\prime }$ amongst those received by $p_i$ which observes all other blocks received by $p_i$, then $p_i$ should have $b$ point to $b^{\prime }$. To integrate with our approach to the “high throughput mode”, we also require that $b$ should point to the last transaction block created by $p_i$. Generally, we will only require transaction blocks to point to at most two previous blocks. This avoids the downside of many DAG-based protocols that all blocks require $O(n)$ pointers to previous blocks.

When conflicting transaction blocks are produced, we need a method for ordering them. The approach we take is to use leaders, who produce a second type of block, called leader blocks. These leader blocks are used to specify the required total ordering.

Views. In more detail, the instructions for the protocol are divided into views, each with a distinct leader. If a particular view is operating in “low throughput” mode and conflicting blocks are produced, then some time may pass during which a new transaction block fails to be finalized. In this case, correct processes will complain, by sending messages indicating that they wish to move to the next view. Once processes enter the next view, the leader of that view will then continue to produce leader blocks so long as the protocol remains in high throughput mode. Each of these leader blocks will point to all tips (i.e. all blocks which are not observed by any others) seen by the leader, and will suffice to specify a total ordering on the blocks they observe.

The two phases of a view. Each view is thus of potentially unbounded length and consists of two phases. During the first phase, the protocol is in high throughput mode, and is essentially the same as Autobahn.³³3We note that Autobahn includes the option of various optimisations (with corresponding tradeoffs) that can be used to further reduce latency in certain “good” scenarios (where all processes act correctly, for example). For the sake of simplicity we do not include these optimisations in our formal description of Morpheus in Section 5, but the online version of this paper discusses those options. Processes produce transaction blocks, each of which just points to their last produced transaction block. Processes do not send 1 or 2-votes for transaction blocks during this phase, but rather vote for leader blocks, which, when finalized, suffice to specify the required total ordering on transactions. Leader blocks are finalized as in PBFT, after two rounds of voting. If a time is reached after which transaction blocks arrive infrequently enough that leader blocks are no longer required, then the view enters a second phase, during which processes vote on transaction blocks and attempt to finalize them without the use of a leader.

For protocols in which each block points to a single precedessor, the total ordering of transactions specified by a finalized block $b$ is clear: the ordering on transactions is just that inherited by the sequence of blocks below $b$ and the transactions they contain. In a context where each block may point to multiple others, however, we have extra work to do to specify the required total ordering on transactions. The approach we take is similar to many DAG-based protocols (e.g. [19]). Given any sequence of blocks $S$, we let $\mathrm{𝚃𝚛}(S)$ be the corresponding sequence of transactions, i.e. if $b_1,\mathrm{\dots },b_k$ is the subsequence of $S$ consisting of the transaction blocks in $S$, then $\mathrm{𝚃𝚛}(S)$ is $b_1.\text{Tr}\ast b_2.\text{Tr}\ast \mathrm{\cdots }\ast b_k.\text{Tr}$, where $\ast$ denotes concatenation, and where $b.\text{Tr}$ is the sequence of transactions in $b$. We suppose given ${\tau }^{†}$ such that, for any set of blocks $B$, ${\tau }^{†}(B)$ is a sequence of blocks that contains each block in $B$ precisely once, and which respects the observes relation: if $b,b^{\prime }\in B$ and $b^{\prime }$ observes $b$, then $b$ appears before $b^{\prime }$ in ${\tau }^{†}(B)$. Each transaction/leader block $b$ will contain $q$ which is a 1-Quorum-Certificate (1-QC), i.e., a threshold signature formed from $n-f$ 1-votes, for some previous block: this will be recorded as the value $b.\text{1-QC}=q$, while, if $q$ is a 1-QC for $b^{\prime }$, then we set $q.\text{b}=b^{\prime }$. QCs are ordered first by the view of the block to which they correspond, then by the type of the block (leader or transaction, with the latter being greater), and then by the height of the block. We then define $\tau (b)$ by recursion:

• $\mathrm{■}$

  $\tau (b_g)=b_g$.

• $\mathrm{■}$

  If $b\ne b_g$, then let $q=b.\text{1-QC}$ and set $b^{\prime }=q.\text{b}$. Then $\tau (b)=\tau (b^{\prime })\ast {\tau }^{†}([b]-[b^{\prime }])$.

Given any set of messages $M$, let $M^{\prime }$ be the largest set of blocks in $M$ that is downward closed, i.e. such that if $b\in M^{\prime }$ and $b$ observes $b^{\prime }$, then $b^{\prime }\in M^{\prime }$. Let $q$ be a maximal 2-QC in $M$ such that $q.\text{b}\in M^{\prime }$, and set $b=q.\text{b}$, or if there is no such 2-QC in $M$, set $b=b_g$. We define $ℱ(M)$ to be $\mathrm{𝚃𝚛}(\tau (b))$.

Consistency is formally established in Appendix A, and uses a combination of techniques from PBFT, Tendermint, and previous DAG-based protocols. Roughly, the argument is as follows. When the protocol moves to a new view, consistency will be maintained using the same technique as in PBFT. Upon entering the view, each process sends a “new-view” message to the leader, specifying the greatest 1-QC they have seen. Upon producing a first leader block $b$ for the view, the leader must then justify the choice of $b.\text{1-QC}$ by listing new-view messages signed by $n-f$ distinct processes in $\mathrm{\Pi }$. The value $b.\text{1-QC}$ must be greater than or equal to all 1-QCs specified in those new-view messages. If any previous block $b^{\prime }$ has received a 2-QC, then at least $f+1$ correct processes must have seen a 1-QC for $b^{\prime }$, meaning that $b.\text{1-QC}$ must be greater than or equal to that 1-QC. Subsequent leader blocks $b^{\prime \prime }$ for the view just set $b^{\prime \prime }.\text{1-QC}$ to be a 1-QC for the previous leader block.

To maintain consistency between finalized transaction blocks and between leader and transaction blocks within a single view, we also have each transaction block specify $q$ which is 1-QC for some previous block. Correct processes will not vote for the transaction block unless $q$ is greater than or equal to any 1-QC they have previously received.

Overall, the result of these considerations is that, if two blocks $b$ and $b^{\prime }$ receive 2-QCs $q$ and $q^{\prime }$ respectively, with $q$ greater than $q^{\prime }$, then the iteration specifying $\tau (b)$ (as detailed above) proceeds via $b^{\prime }$, so that $\tau (b)$ extends $\tau (b^{\prime })$.

While operating in low throughput, a 1-QC for a block $b$ suffices to ensure both data availability, i.e. that some correct process has received the block, and non-equivocation, i.e. two conflicting blocks cannot both receive 1-QCs. When operating in high throughput, however, transaction blocks will not receive 1 or 2-votes. In this context, we still wish to ensure data availability. It is also useful to ensure that each individual process does not produce transaction blocks that conflict with each other, so as to bound the number of tips that may be created. To this end, we make use of 0-votes, which may be regarded as weaker than standard votes for a block:

1. 1.

   Upon having a new transaction block $b$ to issue, a process $p_i$ will send $b$ to all processes.

2. 2.

   If the block is properly formed, and if other processes have not seen $p_i$ produce any transaction blocks conflicting with $b$, then they will send a 0-vote for $b$ back to $p_i$. Note that 0-votes are sent only to the block creator, rather than to all processes.

3. 3.

   Upon receiving $n-f$ 0-votes for $b$, $p_i$ will then form a 0-QC for $b$ and send this to all processes.

When a block $b^{\prime }$ wishes to point to $b$, it will include a $z$-QC for $b$ (for some $z\in \{0,1,2\}$). As a consequence, any process will be able to check that $b^{\prime }$ is valid/properly formed without actually receiving the blocks that $b^{\prime }$ points to: the existence of QCs for those blocks suffices to ensure that they are properly formed (and that at least one correct process has those blocks), and other requirements for the validity of $b^{\prime }$ can be checked by direct inspection. For this to work, votes (and QCs) must specify certain properties of the block beyond its hash, such as the height of the block and the block creator. The details are given in Section 5.

There exists a unique genesis block, denoted $b_g$. For any block $b$, $b.\text{type}$ specifies the type of the block $b$, $b.\text{view}$ is the view corresponding to the block, $b.\text{h}$ specifies the height of the block, $b.\text{auth}$ is the block creator, and $b.\text{slot}$ specifies the slot corresponding to the block. For $b_g$, we set:

• $\mathrm{■}$

  $b_g.\text{type}=\text{gen}$, $b_g.\text{view}=-1$, $b_g.\text{h}=0$, $b_g.\text{auth}=\perp$, $b_g.\text{slot}=0$.

For $z\in \{0,1,2\}$, a $z$-vote for the block $b$ is a message of the form $(z,b.\text{type},b.\text{view},$ $b.\text{h},b.\text{auth},b.\text{slot},H(b))$, signed by some process in $\mathrm{\Pi }$. The reason votes include more information than just the hash of the block is explained in Section 4. A $z$-quorum for $b$ is a set of $n-f$ $z$-votes for $b$, each signed by a different process in $\mathrm{\Pi }$. A $z$-QC for $b$ is the message $m=(z,b.\text{type},b.\text{view},$ $b.\text{h},b.\text{auth},b.\text{slot},H(b))$ together with a threshold signature for $m$, formed from a $z$-quorum for $b$ using the threshold signature scheme.

By a QC for the block $b$, we mean a $z$-QC for $b$, for some $z\in \{0,1,2\}$. If $q$ is a $z$-QC for $b$, then we set $q.\text{b}=b$, $q.\text{z}=z$, $q.\text{type}=b.\text{type}$, $q.\text{view}=b.\text{view},$ $q.\text{h}=b.\text{h}$, $q.\text{auth}=b.\text{auth}$, $q.\text{slot}=b.\text{slot}$. We define a preordering $\le$ on QCs as follows: QCs are preordered first by view, then by type with , and then by height.⁴⁴4For the sake of completeness, if $q.\text{view}=q^{\prime }.\text{view}$, $q.\text{type}=q^{\prime }.\text{type}$, and $q.\text{h}=q^{\prime }.\text{h}$, then we set $q\le q^{\prime }$ and $q^{\prime }\le q$. We will show that, in this case, $q.\text{b}=q^{\prime }.\text{b}$.

Each process $p_i$ maintains a local variable $M_i$, which is automatically updated and specifies the set of all received messages. Initially, $M_i$ contains $b_g$ and a 1-QC for $b_g$.

Each transaction block $b$ is entirely specified by the following values:

• $\mathrm{■}$

  $b.\text{type}=\text{Tr}$, $b.\text{view}=v\in {\mathbb{N}}_{\ge 0}$, $b.\text{h}=h\in {\mathbb{N}}_{>0}$, $b.\text{slot}=s\in {\mathbb{N}}_{\ge 0}$.

• $\mathrm{■}$

  $b.\text{auth}\in \mathrm{\Pi }$: the block creator.

• $\mathrm{■}$

  $b.\text{Tr}$: a sequence of transactions.

• $\mathrm{■}$

  $b.\text{prev}$: a non-empty set of QCs for blocks of height .

• $\mathrm{■}$

  $b.\text{1-QC}$: a 1-QC for a block of height .

If $b.\text{prev}$ contains a QC for $b^{\prime }$, then we say that $b$ points to $b^{\prime }$. For $b$ to be valid, we require that it is of the form above and:

1. 1.

   $b$ is signed by $b.\text{auth}$.

2. 2.

   If $s>0$, $b$ points to $b^{\prime }$ with $b^{\prime }.\text{type}=\text{Tr}$, $b^{\prime }.\text{auth}=b.\text{auth}$ and $b^{\prime }.\text{slot}=s-1$.

3. 3.

   If $b$ points to $b^{\prime }$, then $b^{\prime }.\text{view}\le b.\text{view}$.

4. 4.

   If $h^{\prime }=\text{max}\{b^{\prime }.\text{h}:b\text{ points to }{b}^{\prime }\}$, then $h=h^{\prime }+1$.

We suppose correct processes ignore transaction blocks that are not valid. In what follows we therefore adopt the convention that, by a “transaction block”, we mean a “valid transaction block”.

The genesis block observes only itself. Any other block $b$ observes itself and all those blocks observed by blocks that $b$ points to. If two blocks do not observe each other, then they conflict. We write $[b]$ to denote the set of all blocks observed by $b$.

The leader of view $v$, denoted $\mathrm{𝚕𝚎𝚊𝚍}(v)$, is process $p_i$, where $i=v\text{ mod }n$.

If process $p_i$ sees insufficient progress during view $v$, it may send an end-view $v$ message of the form $(v)$, signed by $p_i$. By a quorum of end-view $v$ messages, we mean a set of $f+1$ end-view $v$ messages, each signed by a different process in $\mathrm{\Pi }$. If $p_i$ receives a quorum of end-view $v$ messages before entering view $v+1$, it will combine them (using the threshold signature scheme) to form a $(v+1)$-certificate. Upon first seeing a $(v+1)$-certificate, $p_i$ will send this certificate to all processes and enter view $v+1$. This ensures that, if some correct process is the first to enter view $v+1$ after GST, all correct processes enter that view (or a later view) within time $\mathrm{\Delta }$.

When $p_i$ enters view $v$, it will send to $\mathrm{𝚕𝚎𝚊𝚍}(v)$ a view $v$ message of the form $(v,q)$, signed by $p_i$, where $q$ is a maximal amongst 1-QCs seen by $p_i$. We say that $q$ is the 1-QC corresponding to the view $v$ message $(v,q)$.

Each leader block $b$ is entirely specified by the following values:

• $\mathrm{■}$

  $b.\text{type}=\text{lead}$, $b.\text{view}=v\in {\mathbb{N}}_{\ge 0}$, $b.\text{h}=h\in {\mathbb{N}}_{>0}$, $b.\text{slot}=s\in {\mathbb{N}}_{\ge 0}$.

• $\mathrm{■}$

  $b.\text{auth}\in \mathrm{\Pi }$: the block creator.

• $\mathrm{■}$

  $b.\text{prev}$: a non-empty set of QCs for blocks of height .

• $\mathrm{■}$

  $b.\text{1-QC}$: a 1-QC for a block of height .

• $\mathrm{■}$

  $b.\text{just}$: a (possibly empty) set of view $v$ messages.

As for transaction blocks, if $b.\text{prev}$ contains a QC for $b^{\prime }$, then we say that $b$ points to $b^{\prime }$. For $b$ to be valid, we require that it is of the form described above and:

1. 1.

   $b$ is signed by $b.\text{auth}$ and $b.\text{auth}=\mathrm{𝚕𝚎𝚊𝚍}(v)$.

2. 2.

   If $b$ points to $b^{\prime }$, then $b^{\prime }.\text{view}\le b.\text{view}$.

3. 3.

   If $h^{\prime }=\text{max}\{b^{\prime }.\text{h}:b\text{ points to }{b}^{\prime }\}$, then $h=h^{\prime }+1$.

4. 4.

   If $s>0$, $b$ points to a unique $b^{\ast }$ with $b^{\ast }.\text{type}=\text{lead}$, $b^{\ast }.\text{auth}=b.\text{auth}$ and $b^{\ast }.\text{slot}=s-1$.

5. 5.

   If $s=0$ or , then $b.\text{just}$ contains $n-f$ view $v$ messages, each signed by a different process in $\mathrm{\Pi }$. This set of messages is called a justification for the block.

6. 6.

   If $s=0$ or , then $b.\text{1-QC}$ is greater than or equal to all 1-QCs corresponding to view $v$ messages in $b.\text{just}$.

7. 7.

   If $s>0$ and $b^{\ast }.\text{view}=v$, then $b.\text{1-QC}$ is a 1-QC for $b^{\ast }$.

As with transaction blocks, we suppose correct processes ignore leader blocks that are not valid. In what follows we therefore adopt the convention that, by a “leader block”, we mean a “valid leader block”.

Each process $p_i$ maintains a local variable $Q_i$, which is automatically updated and, for each $z\in \{0,1,2\}$, stores at most one $z$-QC for each block: For $z\in \{0,1,2\}$, if $p_i$ receives⁵⁵5Here, we include the possibility that $p_i$ receives the $z$-QC inside a message, such as in $b^{\prime }.\text{prev}$ for a received block $b^{\prime }$ a $z$-quorum or a $z$-QC for $b$, and if $Q_i$ does not contain a $z$-QC for $b$, then $p_i$ automatically enumerates a $z$-QC for $b$ into $Q_i$ (either the $z$-QC received, or one formed from the $z$-quorum received).

We define the “observes” relation $⪰$ on $Q_i$ to be the minimal preordering satisfying (transitivity and):

• $\mathrm{■}$

  If $q,q^{\prime }\in Q_i$, $q.\text{type}=q^{\prime }.\text{type}$, $q.\text{auth}=q^{\prime }.\text{auth}$ and $q.\text{slot}>q^{\prime }.\text{slot}$, then $q⪰q^{\prime }$.

• $\mathrm{■}$

  If $q,q^{\prime }\in Q_i$, $q.\text{type}=q^{\prime }.\text{type}$, $q.\text{auth}=q^{\prime }.\text{auth}$, $q.\text{slot}=q^{\prime }.\text{slot}$, and $q.\text{z}\ge q^{\prime }.\text{z}$, then $q⪰q^{\prime }$.

• $\mathrm{■}$

  If $q,q^{\prime }\in Q_i$, $q.\text{b}=b$, $q^{\prime }.\text{b}=b^{\prime }$, $b\in M_i$ and $b$ points to $b^{\prime }$, then $q⪰q^{\prime }$.

We note that the observes relation $⪰$ depends on $Q_i$ and $M_i$, and is stronger than the preordering $\ge$ we defined on $z$-QCs previously, in the following sense: if $q$ and $q^{\prime }$ are $z$-QCs with $q⪰q^{\prime }$, then $q\ge q^{\prime }$, while the converse may not hold. When we refer to the “greatest” QC in a given set, or a “maximal” QC in a given set, this is with reference to the $\ge$ preordering, unless explicitly stated otherwise. If $q.\text{type}=q^{\prime }.\text{type}$, $q.\text{auth}=q^{\prime }.\text{auth}$ and $q.\text{slot}=q^{\prime }.\text{slot}$, then it will follow that $q.\text{b}=q^{\prime }.\text{b}$.

The tips of $Q_i$ are those $q\in Q_i$ such that there does not exist $q^{\prime }\in Q_i$ with $q^{\prime }\succ q$ (i.e. $q^{\prime }⪰q$ and $q⋡q^{\prime }$). The protocol ensures that $Q_i$ never contains more than $2n$ tips: The factor 2 here comes from the fact that leader blocks produced by correct $p_i$ need not observe all transaction blocks produced by $p_i$ (and vice versa).

We say $q\in Q_i$ is a single tip of $Q_i$ if $q⪰q^{\prime }$ for all $q^{\prime }\in Q_i$. We say $b\in M_i$ is a single tip of $M_i$ if there exists $q$ which is a single tip of $Q_i$ and $b$ is the unique block in $M_i$ pointing to $q.\text{b}$.

For each $i,j,s$, $z\in \{0,1,2\}$ and $x\in \{\text{lead},\text{Tr}\}$, the value ${\mathrm{𝚟𝚘𝚝𝚎𝚍}}_i(z,x,s,p_j)$ is initially 0. When $p_i$ sends a $z$-vote for a block $b$ with $b.\text{type}=x$, $b.\text{auth}=p_j$, and $b.\text{slot}=s$, it sets ${\mathrm{𝚟𝚘𝚝𝚎𝚍}}_i(z,x,s,p_j):=1$. Once this value is set to 1, $p_i$ will not send a $z$-vote for any block $b^{\prime }$ with $b^{\prime }.\text{type}=x$, $b^{\prime }.\text{auth}=p_j$, and $b^{\prime }.\text{slot}=s$.

For each $i$ and $v$, the value ${\mathrm{𝚙𝚑𝚊𝚜𝚎}}_i(v)$ is initially 0. Once $p_i$ votes for a transaction block during view $v$, it will set ${\mathrm{𝚙𝚑𝚊𝚜𝚎}}_i(v):=1$, and will then not vote for leader blocks within view $v$.

Process $p_i$ regards $q\in Q_i$ (and $q.\text{b}$) as final if there exists $q^{\prime }\in Q_i$ such that $q^{\prime }⪰q$ and $q^{\prime }$ is a 2-QC (for any block).

This is defined exactly as specified in Section 4.

These record the present view and slot numbers for $p_i$.

We remain agnostic as to how frequently processes should produce transaction blocks, i.e. as to whether processes should produce transaction blocks immediately upon having new transactions to process, or wait until they have a set of new transactions of at least a certain size. We suppose simply that:

• $\mathrm{■}$

  Extraneous to the explicit instructions of the protocol, ${\mathrm{𝙿𝚊𝚢𝚕𝚘𝚊𝚍𝚁𝚎𝚊𝚍𝚢}}_i$ may be set to 1 at some timeslots of the execution.

• $\mathrm{■}$

  If ${\mathrm{𝙿𝚊𝚢𝚕𝚘𝚊𝚍𝚁𝚎𝚊𝚍𝚢}}_i=1$ and ${\mathrm{𝚜𝚕𝚘𝚝}}_i(\text{Tr})=s>0$, then there exists $q\in Q_i$ with $q.\text{auth}=p_i$, $q.\text{type}=\text{Tr}$ and $q.\text{slot}=s-1$.

When $p_i$ wishes to form a new transaction block $b$, it will run this procedure, by executing the following instructions:

1. 1.

   Set $b.\text{type}:=\text{Tr}$, $b.\text{auth}:=p_i$, $b.\text{view}:={\mathrm{𝚟𝚒𝚎𝚠}}_i$, $b.\text{slot}:={\mathrm{𝚜𝚕𝚘𝚝}}_i(\text{Tr})$.

2. 2.

   Let $s:={\mathrm{𝚜𝚕𝚘𝚝}}_i(\text{Tr})$. If $s>0$, then let $q_1\in Q_i$ be such that $q_1.\text{auth}=p_i$, $q_1.\text{type}=\text{Tr}$ and $q_1.\text{slot}=s-1$. If $s=0$, let $q_1$ be a 1-QC for $b_g$. Initially, set $b.\text{prev}:=\{q_1\}$.

3. 3.

   If there exists $q_2\in Q_i$ which is a single tip of $Q_i$, then enumerate $q_2$ into $b.\text{prev}$.

4. 4.

   If $h^{\prime }=\text{max}\{q.\text{h}:q\in b.\text{prev}\}$, then set $b.\text{h}:=h^{\prime }+1$.

5. 5.

   Let $q$ be the greatest 1-QC in $Q_i$. Set $b.\text{1-QC}:=q$.

6. 6.

   Sign $b$ with the values specified above, and send this block to all processes.

7. 7.

   Set ${\mathrm{𝚜𝚕𝚘𝚝}}_i(\text{Tr}):={\mathrm{𝚜𝚕𝚘𝚝}}_i(\text{Tr})+1$;

At any time, this boolean is equal to 1 iff either of the following conditions are satisfied, setting $v={\mathrm{𝚟𝚒𝚎𝚠}}_i$:

1. 1.

   Process $p_i$ has not yet produced a block $b$ with $b.\text{view}=v$ and $b.\text{type}=\text{lead}$, and both:

   1. (a)

      Process $p_i$ has received view $v$ messages signed by at least $n-f$ processes in $\mathrm{\Pi }$.

   2. (b)

      ${\mathrm{𝚜𝚕𝚘𝚝}}_i(\text{lead})=0$ or $Q_i$ contains $q$ with $q.\text{auth}=p_i$, $q.\text{type}=\text{lead}$, $q.\text{slot}={\mathrm{𝚜𝚕𝚘𝚝}}_i(\text{lead})-1$.

2. 2.

   Process $p_i$ has previously produced a block $b$ with $b.\text{view}=v$ and $b.\text{type}=\text{lead}$, and $Q_i$ contains a 1-QC for $b^{\prime }$ with $b^{\prime }.\text{auth}=p_i$, $b^{\prime }.\text{type}=\text{lead}$, $b^{\prime }.\text{slot}={\mathrm{𝚜𝚕𝚘𝚝}}_i(\text{lead})-1$.

When $p_i$ wishes to form a new leader block $b$, it will run this procedure, by executing the following instructions:

1. 1.

   Set $b.\text{type}:=\text{lead}$, $b.\text{auth}:=p_i$, $b.\text{view}:={\mathrm{𝚟𝚒𝚎𝚠}}_i$, $b.\text{slot}:={\mathrm{𝚜𝚕𝚘𝚝}}_i(\text{lead})$.

2. 2.

   Initially, set $b.\text{prev}$ to be the tips of $Q_i$.

3. 3.

   Set $s:={\mathrm{𝚜𝚕𝚘𝚝}}_i(\text{Tr})$ and $v:={\mathrm{𝚟𝚒𝚎𝚠}}_i$. If $s>0$, then let $q\in Q_i$ be such that $q.\text{auth}=p_i$, $q.\text{type}=\text{lead}$ and $q.\text{slot}=s-1$. If $b.\text{prev}$ does not already contain $q$, add $q$ to this set.

4. 4.

   If $h^{\prime }=\text{max}\{q.\text{h}:q\in b.\text{prev}\}$, then set $b.\text{h}:=h^{\prime }+1$.

5. 5.

   If $p_i$ has not yet produced a block $b$ with $b.\text{view}={\mathrm{𝚟𝚒𝚎𝚠}}_i$ and $b.\text{type}=\text{lead}$ then:

   1. (a)

      Set $b.\text{just}$ to be a set of view $v$ messages signed by $n-f$ processes in $\mathrm{\Pi }$.

   2. (b)

      Set $b.\text{1-QC}$ to be a 1-QC in $Q_i$ greater than or equal to all 1-QCs corresponding to messages in $b.\text{just}$.

6. 6.

   If $p_i$ has previously produced a block $b$ with $b.\text{view}={\mathrm{𝚟𝚒𝚎𝚠}}_i$ and $b.\text{type}=\text{lead}$ then let $q^{\prime }\in Q_i$ be a 1-QC with $q^{\prime }.\text{auth}=p_i$, $q^{\prime }.\text{type}=\text{lead}$ and $q^{\prime }.\text{slot}=s-1$. Set $b.\text{1-QC}:=q^{\prime }$ and set $b.\text{just}$ to be the empty set.

7. 7.

   Sign $b$ with the values specified above, and send this block to all processes.

8. 8.

   Set ${\mathrm{𝚜𝚕𝚘𝚝}}_i(\text{lead}):={\mathrm{𝚜𝚕𝚘𝚝}}_i(\text{lead})+1$;

The pseudocode appears in Algorithm 1 (with local variables described first, and the main code appearing later). Section 5.1 gives a “pseudocode walk-through”.