Beyond Optimal Fault-Tolerance

It is sometimes assumed in the literature (e.g. [26]) that, in the event of a consistency violation, an “administrator” will somehow (through out-of-protocol means) remove perpetrators from the system and co-ordinate an appropriate “reboot”. Our automated recovery procedure is “in-protocol,” and therefore has the significant benefits that it does not rely on a centralized entity, has no single point of failure, and formalizes a process by which one can guarantee bounded rollback (a principal focus of this paper).

In practical settings, partial synchrony may hold with respect to $\mathrm{\Delta }$ of the order of a few hundred milliseconds. It may also be reasonable to suppose that synchrony will hold with respect to some much larger bound ${\mathrm{\Delta }}^{\ast }$, but making direct use of this larger bound to run a synchronous protocol (and increase resilience beyond 1/3) would result in an impractically slow protocol. Our use of the two bounds $\mathrm{\Delta }$ and ${\mathrm{\Delta }}^{\ast }$ reflects our interest in considering protocols that give all the usual guarantees of protocols for partial synchrony (with no requirement that the larger bound ${\mathrm{\Delta }}^{\ast }$ should hold), but which also give recovery guarantees in the case that the larger bound for synchrony should hold.

We assume that processes communicate by point-to-point authenticated channels and that a public key infrastructure (PKI) is available for generating and validating signatures. For simplicity of presentation (e.g., to avoid the analysis of negligible error probabilities), we work with ideal versions of these primitives (i.e., we assume that faulty processes cannot forge signatures). We also assume that all processes have access to a random permutation of $\mathrm{\Pi }$, denoted ${\mathrm{\Pi }}^{\ast }:[1,n]\to \mathrm{\Pi }$, which is sampled after the adversary chooses which processes to corrupt.

We consider a discrete sequence of timeslots $t\in {\mathbb{N}}_{\ge 0}$. As discussed in the introduction, we consider protocols that operate in partial synchrony (with some parameter $\mathrm{\Delta }$, perhaps in the order of seconds or milliseconds) and satisfy additional recovery properties should synchrony hold (with some different parameter ${\mathrm{\Delta }}^{\ast }$, which may be set much larger than $\mathrm{\Delta }$) while running the “recovery procedure”.

Synchrony. In the synchronous setting, a message sent at time $t$ must arrive by time $t+{\mathrm{\Delta }}^{\ast }$, where ${\mathrm{\Delta }}^{\ast }$ is known to the protocol.

Partial synchrony. In the partially synchronous setting, a message sent at time $t$ must arrive by time $\max \{\text{GST},t\}+\mathrm{\Delta }$. While $\mathrm{\Delta }$ is known, the value of GST is unknown to the protocol. The adversary chooses GST and also message delivery times, subject to the constraints already specified.

In the partially synchronous setting, we suppose all correct processes begin the protocol execution before GST. When considering the synchronous setting, we suppose all correct processes begin the protocol execution by time ${\mathrm{\Delta }}^{\ast }$. A correct process begins the protocol execution with its local clock set to 0; thus, we do not suppose that the clocks of correct processes are synchronized. For simplicity, we assume that the clocks of correct processes all proceed in real time, meaning that 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$.⁴⁴4Using standard arguments, our protocol and analysis can easily be extended to the case in which there is a known upper bound on the difference between the clock speeds of correct processes.

We use the following notation when discussing any execution of a protocol:

• $\mathrm{■}$

  $M_i(t)$ denotes the set of messages received by process $p_i$ by timeslot $t$;

• $\mathrm{■}$

  $M_c(t)$ denotes the set of all messages received by any correct process by timeslot $t$;

• $\mathrm{■}$

  $M_c$ denotes the set of all messages received by any correct process during the execution.

Transactions are messages of a distinguished form, signed by the environment. Each timeslot, each process may receive some finite set of transactions directly from the environment.

A value is determined if it known to all processes, and is otherwise undetermined. For example, $\mathrm{\Delta }$, ${\mathrm{\Delta }}^{\ast }$ and $\mathrm{\Pi }$ are determined, while GST is undetermined.

Informally, a protocol for state machine replication (SMR) must cause correct processes to finalize logs (sequences of transactions) that are live and consistent with each other, and must also produce “certificates” of finalization that can be presented to clients who may not always be online and observing the protocol execution. Formally, if $\sigma$ and $\tau$ are sequences, we write $\sigma ⪯\tau$ to denote that $\sigma$ is a prefix of $\tau$. We say $\sigma$ and $\tau$ are compatible if $\sigma ⪯\tau$ or $\tau ⪯\sigma$. If two sequences 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$.

Fix a process set $\mathrm{\Pi }$ and genesis log, denoted ${\mathrm{𝚕𝚘𝚐}}_G$. If $𝒫$ is a protocol for SMR, then it must specify a function $ℱ$, which may depend on $\mathrm{\Pi }$ and ${\mathrm{𝚕𝚘𝚐}}_G$, that maps any set of messages to a sequence of transactions extending ${\mathrm{𝚕𝚘𝚐}}_G$. We require the following conditions to hold in every execution (for any $M_1,M_2,p_i,p_j$ and $\mathrm{𝚝𝚛}$):

Consistency. If $M_1\subseteq M_2\subseteq M_c$, then $ℱ(M_1)⪯ℱ(M_2)$.⁵⁵5This is equivalent to the seemingly stronger condition in which $M_c$ is replaced by the set of messages received by any process (correct or otherwise), as faulty processes always have the option of echoing any messages they receive to correct processes.

Liveness. If $p_i$ and $p_j$ are correct and if $p_i$ receives the transaction $\mathrm{𝚝𝚛}$ then, for some $t$, $\mathrm{𝚝𝚛}\in ℱ(M_j(t))$.

This definition of consistency ensures that correct processes never finalize incompatible logs: for any sets $M_1,M_2\subseteq M_c$ that two such processes might have received, $ℱ(M_1)⪯ℱ(M_1\cup M_2)$ and $ℱ(M_2)⪯ℱ(M_1\cup M_2)$. We say a set of messages $M$ is a certificate for a sequence of transactions $\sigma$ if $ℱ(M)⪰\sigma$: intuitively, any process can present the set of (potentially signed) messages $M$ to a “client” that has not been observing the protocol execution as proof that it has finalized a sequence of transactions extending $\sigma$. If we wish to make $ℱ$ explicit, we may also say that $M$ is an $ℱ$-certificate for $\sigma$.

The selection $ℱ$ of finalized transactions by a correct process depends only on the set of messages it has received, and not on the times at which these messages were received. The motivation for this restriction is to formalize the requirement of SMR [22] that “clients” wishing to verify the finality of transactions without observing the entire execution of the protocol should be able to do so (via a suitable certificate). As discussed in [25], this crucial distinction between SMR and Total-Order-Broadcast is sometimes overlooked in the literature: In the context of an honest majority, any report of finality by a majority of processes constitutes proof of finality, so a protocol for Total-Order-Broadcast directly gives a protocol for SMR. However, the distinction becomes non-trivial in the context of player reconfiguration, or if there is no guarantee of honest majority (such as in this paper). In partial synchrony, certificates are anyways required for guaranteed consistency and liveness [16], so our approach is general for the context considered here.

If there exists some fixed $\mathrm{\ell }$ that is a function of determined inputs⁶⁶6The requirement that $\mathrm{\ell }$ is not a function of ${\mathrm{\Delta }}^{\ast }$ (while ${\mathrm{\Delta }}^{\ast }$ is not necessarily $O(\mathrm{\Delta })$) means that having liveness parameter $\mathrm{\ell }$ may require finalization of transactions in time less than ${\mathrm{\Delta }}^{\ast }$ after GST. other than ${\mathrm{\Delta }}^{\ast }$ and such that the following holds in all executions of $𝒫$, we say $𝒫$ has liveness parameter $\mathrm{\ell }$: If $p_i$ and $p_j$ are correct and if $p_i$ receives the transaction $\mathrm{𝚝𝚛}$ at time $t$ then, for $t^{\prime }=\text{max}\{t,\text{GST}\}+\mathrm{\ell }$, $\mathrm{𝚝𝚛}\in ℱ(M_j(t^{\prime }))$.

Recall that $n=|\mathrm{\Pi }|$. When the protocol $𝒫$ is clear from context, we write ${\rho }_C$ to denote the consistency resilience of $𝒫$, which is the largest $\rho$ such that, for all $n$, the protocol satisfies consistency so long as the adversary is $\rho$-bounded. We write ${\rho }_L$ to denote the liveness resilience, which is the largest $\rho$ such that, for all $n$, the protocol satisfies liveness so long as the adversary is $\rho$-bounded. It is well known that ${\rho }_C+2{\rho }_L\le 1$ in the partially synchronous setting [14] and that ${\rho }_C+{\rho }_L\le 1$ in the synchronous setting [19].

When $ℱ$ is clear from context, we say the set of messages $M$ has $r$ consistency violations if there exist $M_0\subset M_1\subset \mathrm{\cdots }\subset M_r\subseteq M$ such that, for each $s\in \{0,1,\mathrm{\dots },r-1\}$, $ℱ(M_s)⋠ℱ(M_{s+1})$. We also say $M$ has a consistency violation (w.r.t. $ℱ$) if it has at least one consistency violation. An execution has $r$ consistency violations if $M_c$ has $r$ consistency violations.

Informally, a protocol is accountable if it produces proofs of guilt for some faulty processes in the event of a consistency violation. We cannot generally require proofs of guilt for a fraction $\lambda >{\rho }_C$ of processes, since consistency violations may occur when less than a fraction $\lambda$ of processes are faulty. On the other hand, all standard protocols that provide accountability produce proofs of guilt for a ${\rho }_C$ fraction of processes in the event of a consistency violation [24].

Consider an SMR protocol $𝒫$:

• $\mathrm{■}$

  We say the set of messages $M$ is a proof of guilt for $p\in \mathrm{\Pi }$ if there does not exist any execution of $𝒫$ in which $p$ is correct and for which $M\subseteq M_c$.⁷⁷7If we wish to make $𝒫$, ${\mathrm{𝚕𝚘𝚐}}_G$, and $\mathrm{\Pi }$ explicit, we may also say that $M$ is a $(𝒫,\mathrm{\Pi },{\mathrm{𝚕𝚘𝚐}}_G)$-proof of guilt.

• $\mathrm{■}$

  We say $𝒫$ is $\lambda$-accountable if the following holds at every timeslot $t$ of any execution of $𝒫$: if $M_c(t)$ has a consistency violation, then $M_c(t)$ is a proof of guilt for at least a $\lambda$ fraction of processes in $\mathrm{\Pi }$.

Given that all standard protocols that are $\lambda$-accountable for any $\lambda >0$ are also ${\rho }_C$-accountable, we will say that a protocol is accountable to mean that it is ${\rho }_C$-accountable. It is important to note that, while an accountable protocol ensures the existence of proofs of guilt for a ${\rho }_C$ fraction of processes in the event of a consistency violation, it does not automatically ensure consensus between correct processes as to a set of faulty processes for which a proof of guilt exists. One role of the recovery procedure (as specified in Section 5) will be to ensure such consensus.

In our recovery procedure, it will be convenient to assume that correct processes gossip all messages received. Then, if synchrony does hold with respect to ${\mathrm{\Delta }}^{\ast }$, any message received by correct $p$ at some timeslot $t$ is received by all correct processes by time $t+{\mathrm{\Delta }}^{\ast }$. It will not generally be necessary to gossip all messages; for example, for standard quorum-based protocols, it will suffice to gossip blocks that have received quorum certificates (QCs) along with those QCs.

Given an accountable SMR protocol $𝒫$ and a process set $\mathrm{\Pi }$, our wrapper will initiate a sequence of executions of $𝒫$, with process sets that are progressively smaller subsets of $\mathrm{\Pi }$. Of course, a PKI for $\mathrm{\Pi }$ suffices to provide a PKI for each subset of $\mathrm{\Pi }$ and a random permutation of $\mathrm{\Pi }$ naturally induces a random permutation of each subset. Moreover, the maximum number of executions of $𝒫$ initiated by the wrapper will be small and the size of the process set of each is known ahead of time. (For example, if ${\rho }_C=1/3$ and the adversary is $5/9$-bounded, the wrapper will initiate at most two executions of $𝒫$; if ${\rho }_C=1/3$ and the adversary is $2/3$-bounded, at most three.) Thus, for setup assumptions such as threshold signatures, one can simply run each required setup in advance, before executing the wrapper.

Is a protocol vulnerable to one consistency violation inexorably doomed to an unbounded number of them? Or could a protocol achieve strictly higher levels of resilience by tolerating (and recovering from) a bounded number of consistency violations? The following definitions generalize consistency and liveness resilience to account for the possibility of recovery from consistency violations.

• $\mathrm{■}$

  Recoverable consistency resilience. Consider a function $g:{\mathbb{N}}_{\ge 0}\to [0,1]$. We say a protocol $𝒫$ has recoverable consistency resilience $g$ if the following holds for each $r\in {\mathbb{N}}_{\ge 0}$: $g(r)$ is the largest $\rho$ such that, for all $n$, provided the adversary is $\rho$-bounded, executions of $𝒫$ have at most $r$ consistency violations.

• $\mathrm{■}$

  Recoverable liveness resilience. Consider a function $g:{\mathbb{N}}_{\ge 0}\to [0,1]$. We say a protocol $𝒫$ has recoverable liveness resilience $g$ if the following holds for each $r\in {\mathbb{N}}_{\ge 0}$: $g(r)$ is the largest $\rho$ such that, for all $n$, provided the adversary is $\rho$-bounded, liveness holds in all executions with precisely $r$ consistency violations.⁸⁸8Prior to the $r$th consistency violation, a sufficiently large adversary may still be in a position to cause a liveness violation.

Suppose $𝒫$ has consistency resilience ${\rho }_C$ and recoverable consistency resilience $g$. Note that $g(0)={\rho }_C$. Also, $g$ is nondecreasing (i.e., $g(s)\ge g(r)$ for $s>r$): if executions of $𝒫$ have at most $r$ consistency violations when the adversary is $\rho$-bounded, then this is also true of all $s>r$. If $g(r+1)>g(r)$, the protocol effectively has increased consistency resilience after $r$ consistency violations.

Suppose $𝒫$ is accountable and has consistency resilience ${\rho }_C$ and liveness resilience ${\rho }_L$ for partial synchrony with ${\rho }_C+2{\rho }_L=1$. If we identify some fraction $x$ of the processes in $\mathrm{\Pi }$ as faulty and then run an execution of $𝒫$ using the remaining processes, there will be no consistency violation so long as less than a fraction $x+{\rho }_C(1-x)$ of the processes in $\mathrm{\Pi }$ are faulty. Given this, let us define a sequence ${\{x_r\}}_{r\in {\mathbb{N}}_{\ge 0}}$ by recursion:

Define:

Given $𝒫$ as input, our wrapper produces an SMR protocol with recoverable consistency resilience $g_1$ and recoverable liveness resilience $g_2$ as in (1). For example, if ${\rho }_C={\rho }_L=\frac{1}{3}$, then $g_1(0)=g_2(0)=\frac{1}{3}$, $g_1(1)=g_2(1)=\frac{5}{9}$, and $g_1(r)=g_2(r)=\frac{2}{3}$ for all $r\ge 2$.

Next, we provide a definition that captures the time required by a protocol to recover from consistency violations. Suppose $𝒫$ has recoverable liveness resilience $g$. We say $𝒫$ has recovery time $d$ with liveness parameter $\mathrm{\ell }$ if the following holds for all executions $ℰ$ of $𝒫$:

1. $\mathbf{(}{\mathbf{†}}_{𝒅\mathbf{,}\mathbf{\ell }}\mathbf{)}$

   If there exists $r$ such that $ℰ$ has precisely $r$ consistency violations, let $t$ be least such that $M_c(t)$ has $r$ consistency violations (otherwise set $t=\mathrm{\infty }$). If correct $p_i$ receives the transaction $\mathrm{𝚝𝚛}$ at any timeslot $t^{\prime }$ then, for every correct $p_j$ and for $t^{\prime \prime }=\text{max}\{t+d,\text{GST},t^{\prime }\}+\mathrm{\ell }$, $\mathrm{𝚝𝚛}\in {\mathrm{𝚕𝚘𝚐}}_j(t^{\prime \prime })$.

In the above, $d$ should be thought of as a “grace period” after consistency violations, after which liveness with parameter $\mathrm{\ell }$ must hold. In our construction, $d$ is governed by the length of time it takes to run our recovery procedure.

Our recovery procedure uses the random permutation ${\mathrm{\Pi }}^{\ast }$ – chosen after the adversary chooses which processes to corrupt – to select “leaders,” and as such it will run for a random duration. To analyze this, we allow the grace period parameter $d$ in the definition above to depend on an error probability $\epsilon \in [0,1]$ and sometimes write $d_{\epsilon }$ to emphasize this dependence. We then make the following definitions:

• $\mathrm{■}$

  We say that $({†}_{d,\mathrm{\ell }})$ is ensured with probability at least $p$ if, for every choice of corrupted processes (consistent with a static $\rho$-bounded adversary), with probability at least $p$ over the choice of ${\mathrm{\Pi }}^{\ast }$ (sampled from the uniform distribution), $({†}_{d,\mathrm{\ell }})$ holds in every execution consistent with these choices and with the setting.

• $\mathrm{■}$

  We say that $𝒫$ has probabilisitic recovery time $d_{\epsilon }$ with liveness parameter $\mathrm{\ell }$ if it holds for every $\epsilon \in [0,1]$ that $({†}_{d_{\epsilon },\mathrm{\ell }})$ is ensured with probability at least $1-\epsilon$.

Given $𝒫$ with liveness parameter $\mathrm{\ell }$ as input, our wrapper will produce an SMR protocol with (worst-case) recovery time $O({\mathrm{\Delta }}^{\ast }\cdot f_a)$, probabilisitic recovery time $O({\mathrm{\Delta }}^{\ast }\cdot \log \frac{1}{\epsilon })$, and liveness parameter $\mathrm{\ell }$, where $f_a$ denotes the actual (undetermined) number of faulty processes.

We say that a protocol has rollback bounded by $h$ if the following holds for every execution consistent with the setting and every correct $p_i,p_j\in \mathrm{\Pi }$: if there exists an interval $I=[t,t+h]$ such that $\sigma ⪯{\mathrm{𝚕𝚘𝚐}}_i(t^{\prime })$ for all $t^{\prime }\in I$, then $\sigma ⪯{\mathrm{𝚕𝚘𝚐}}_j(t^{\prime })$ for all sufficiently large $t^{\prime }$. That is, consistency violations can “unfinalize” only transactions that have been finalized recently, within the previous $h$ time steps. Here, $h$ can be any value that depends only on determined inputs.

Given an SMR protocol $𝒫$ with liveness resilience ${\rho }_L$ as input, our wrapper will produce an SMR protocol with rollback bounded by $h=2{\mathrm{\Delta }}^{\ast }$ so long as synchrony holds for ${\mathrm{\Delta }}^{\ast }$ and the adversary is $(1-{\rho }_L)$-bounded. In fact, while the recovery procedure described in Section 5 requires a common choice for ${\mathrm{\Delta }}^{\ast }$, rollback can be bounded on an individual basis, with each correct process making their own personal choice of message delay bound $\le {\mathrm{\Delta }}^{\ast }$. rollback will be bounded by twice their personal choice of bound, so long as that bound on message delay holds.⁹⁹9The requirement that the choice be $\le {\mathrm{\Delta }}^{\ast }$ stems from the fact that the recovery procedure requires delays to be bounded by ${\mathrm{\Delta }}^{\ast }$ to function correctly.

While the formal definition of SMR in Section 2 requires us to specify the finalization rule $ℱ$ (from which the transactions ${\mathrm{𝚕𝚘𝚐}}_i(t)$ finalized by $p_i$ can then be defined as $ℱ(M_i(t))$), it will be more natural when defining our wrapper to specify ${\mathrm{𝚕𝚘𝚐}}_i(t)$ directly, and then later to define $ℱ$ such that ${\mathrm{𝚕𝚘𝚐}}_i(t)=ℱ(M_i(t))$. Recall that the given protocol $𝒫$ satisfies consistency and liveness with respect to a function that may depend on the process set and the genesis log. We write $ℱ(\mathrm{\Pi },{\mathrm{𝚕𝚘𝚐}}_G)$ to denote this function.

In Section 4.1, we describe the intuition behind a feature of the wrapper which allows us to ensure rollback bounded by $2{\mathrm{\Delta }}^{\ast }$. We stress that bounding rollback is non-trivial: this is the requirement on the recovery procedure that requires the most delicate analysis. Section 4.2 then describes the intuition behind the recovery procedure.

In what follows, we use the variable $ℰ$ to denote an execution of the wrapper (with process set $\mathrm{\Pi }$ and ${\mathrm{𝚕𝚘𝚐}}_G$ as the genesis log), which initiates successive executions ${ℰ}_1,{ℰ}_2,\mathrm{\dots }$ of $𝒫$, where ${ℰ}_r$ has process set ${\mathrm{\Pi }}_r$ and ${\mathrm{𝚕𝚘𝚐}}_{G_r}$ as the genesis log. Process $p_i$ maintains local variables ${𝙼}_i$ and ${𝙼}_{i,r}$ for each $r\ge 1$.¹¹¹¹11We use ${𝙼}_i$ when specifying the pseudocode, rather than $M_i(t)$, since $p_i$ only has access to its local clock and does not know the “global” value of $t$. The former records all messages so far received in execution $ℰ$, while the latter records all messages so far received in execution ${ℰ}_r$. We suppose messages have tags identifying the execution in which they are sent, and that ${𝙼}_{i,r}\subseteq {𝙼}_i$ at every timeslot, for all correct $p_i$ and all $r$.

The wrapper takes as input an SMR protocol $𝒫$, a process set $\mathrm{\Pi }$, a random permutation ${\mathrm{\Pi }}^{\ast }$ of $\mathrm{\Pi }$, a value ${\mathrm{𝚕𝚘𝚐}}_G$, and message delay bounds ${\mathrm{\Delta }}^{\ast }$ and $\mathrm{\Delta }$. The consistency resilience ${\rho }_C$ of $𝒫$ is also given as input. Recall that the given protocol $𝒫$ satisfies consistency and liveness with respect to a finalization function that may depend on the process set ${\mathrm{\Pi }}^{\prime }$ and the value ${\mathrm{𝚕𝚘𝚐}}_G^{\prime }$ for the genesis log. (For example, signatures from a certain fraction of the processes in ${\mathrm{\Pi }}^{\prime }$ may be required for transaction finalization.) We write $ℱ({\mathrm{\Pi }}^{\prime },{\mathrm{𝚕𝚘𝚐}}_G^{\prime })$ to denote this function, and suppose also that this function is known to the protocol.

Process $p_i$ maintains a variable ${\mathrm{\Pi }}_r$ for each $r\in {\mathbb{N}}_{\ge 1}$. ${\mathrm{\Pi }}_1$ is initially set to $\mathrm{\Pi }$, while each ${\mathrm{\Pi }}_r$ for $r>1$ is initially undefined.¹²¹²12We write $x\uparrow$ to indicate that the variable $x$ is undefined, and $x\downarrow$ to indicate that $x$ is defined. Once ${\mathrm{\Pi }}_r$ is defined, ${\mathrm{\Pi }}_r^{\ast }$ is the permutation of ${\mathrm{\Pi }}_r$ induced by ${\mathrm{\Pi }}^{\ast }$.

Views are indexed by ordered pairs and ordered lexicographically: one should think of view $(r,v)$ as the $v^{\text{th}}$ view in the $r^{\text{th}}$ execution of the recovery procedure. For $r,v\in {\mathbb{N}}_{\ge 1}$, we set $\mathrm{𝚕𝚎𝚊𝚍}(r,v)=p_i$, where $p_i={\mathrm{\Pi }}_r^{\ast }(v)$; this function is used to specify the leader of each view.¹³¹³13We can write $p_i={\mathrm{\Pi }}_r^{\ast }(v)$ because the number of views in the $r^{\text{th}}$ execution of the recovery procedure will be bounded by $|{\mathrm{\Pi }}_r|$.

We let ${𝙼}_i$ be a local variable that specifies the set of all messages so far received by $p_i$. The wrapper will also initiate executions ${ℰ}_1,{ℰ}_2,\mathrm{\dots }$ of $𝒫$: for each $r\ge 1$, ${𝙼}_{i,r}$ specifies all messages so far received by $p_i$ in execution ${ℰ}_r$. We suppose that messages have tags identifying the execution in which they are sent, and that all messages received by $p_i$ in ${ℰ}_r$ are also received by $p_i$ in the present execution of the wrapper, so that ${𝙼}_{i,r}\subseteq {𝙼}_i$ for all $r$.

Process $p_i$ maintains a variable ${\mathrm{𝚕𝚘𝚐}}_{G_r}$ for each $r\in {\mathbb{N}}_{\ge 1}$. Initially, ${\mathrm{𝚕𝚘𝚐}}_{G_1}$ is set to ${\mathrm{𝚕𝚘𝚐}}_G$, while each ${\mathrm{𝚕𝚘𝚐}}_{G_r}$ for $r>1$ is undefined. If the execution ${ℰ}_r$ of $𝒫$ is initiated by the wrapper, then this will be an execution with ${\mathrm{𝚕𝚘𝚐}}_{G_r}$ as the genesis log and with process set ${\mathrm{\Pi }}_r$.

Process $p_i$ maintains two variables ${\mathrm{𝚕𝚘𝚐}}_i$ and ${\mathrm{𝚕𝚘𝚐}}_i^{\ast }$. The former should be thought of as the sequence of transactions that $p_i$ has finalized, while the latter is the sequence that $p_i$ has strongly finalized.

We write $m_{p_i}$ to denote the message $m$ signed by $p_i$.

An $r$-genesis message is a message of the form ${(\text{gen},\sigma ,r)}_{p_j}$, where $\sigma$ is a sequence of transactions and $p_j\in \mathrm{\Pi }$. These are used during the $r^{\text{th}}$ execution of the recovery procedure to help reach consensus on an appropriate value for ${\mathrm{𝚕𝚘𝚐}}_{G_{r+1}}$. We say ${\sigma }^{\prime }$ is extended by the $r$-genesis message ${(\text{gen},\sigma ,r)}_{p_j}$ if ${\sigma }^{\prime }⪯\sigma$.

An $r$-proposal is a tuple $P=(F,\sigma ,M,r)$, where $F\subset \mathrm{\Pi }$, $\sigma$ is a sequence of transactions, $M$ is a set of $r$-genesis messages, and $r\in {\mathbb{N}}_{\ge 1}$. The last entry $r$ indicates that this is a proposal corresponding to the $r^{\text{th}}$ execution of the recovery procedure. One should think of $F$ as a suggestion for ${\mathrm{\Pi }}_r-{\mathrm{\Pi }}_{r+1}$, while $\sigma$ is a suggestion for ${\mathrm{𝚕𝚘𝚐}}_{G_{r+1}}$ and $M$ is a justification for $\sigma$.

An $(r,v)$-proposal is a message of the form $R={(P,v,Q)}_{p_j}$, where $P$ is an $r$-proposal, $p_j\in \mathrm{\Pi }$, and either $Q=\perp$ or else $Q$ is a QC (as specified below) for some $(r,v^{\prime })$-proposal with .

A vote for the $(r,v)$-proposal $R={(P,v,Q)}_{p_j}$, where $P=(F,\sigma ,M,r)$, is a message of the form $V=R_{p_k}$, where $p_k\in \mathrm{\Pi }$. We also say $V$ is a vote by $p_k$. At timeslot $t$, $p_i$ will regard $V$ as valid if it is signed by one of the processes that, from $p_i$’s perspective, remains in the active process set – i.e., if ${\mathrm{\Pi }}_r$ is defined and $p_k\in {\mathrm{\Pi }}_r-F$.

A QC for an $(r,v)$-proposal $R={(P,v,Q^{\prime })}_{p_j}$, where $P=(F,\sigma ,M,r)$, is a set $Q$ of votes for $R$. At timeslot $t$, $p_i$ will regard $Q$ as valid if every vote in $Q$ is valid and $Q$ contains more than $\frac{1}{2}|{\mathrm{\Pi }}_r-F|$ votes, each by a different process. If $Q$ is a QC for an $(r,v)$-proposal $R={(P,v,Q^{\prime })}_{p_j}$, we set $\mathrm{𝚟𝚒𝚎𝚠}(Q)=(r,v)$ and $𝙿(Q)=P$, and we may also just refer to $Q$ as a QC.

Each process $p_i$ maintains a value $Q_i^{+}$, which is initially undefined. This variable should be thought of as playing the same role as locks in Tendermint. The variable $Q_i^{+}$ may be set to a valid QC for an $(r,v)$-proposal during view $(r,v)$.

Process $p_i$ maintains a local variable $P_i(r)$ for each $r\ge 1$, initially undefined. Upon halting execution ${ℰ}_r$ and entering the recovery procedure at timeslot $t$ (according to its local clock), $p_i$ will set $t_0:=t$, wait $2{\mathrm{\Delta }}^{\ast }$, and then set $P_i(r)$ to be the set of processes in ${\mathrm{\Pi }}_r$ from which it has received signed $r$-genesis messages.

Each view is of length $8{\mathrm{\Delta }}^{\ast }$. Having set $t_0$ upon halting execution ${ℰ}_r$ and entering the recovery procedure, $p_i$ will start view $(r,v)$ (for $v\ge 1$) at time $t_0+2{\mathrm{\Delta }}^{\ast }+8(v-1){\mathrm{\Delta }}^{\ast }$.

At timeslot $t$, we say $p_i$ detects equivocation in view $(r,v)$ if ${𝙼}_i$ contains at least two distinct $(r,v)$-proposals signed by $\mathrm{𝚕𝚎𝚊𝚍}(r,v)$.¹⁴¹⁴14If ${𝙼}_i$ contains a vote for an $(r,v)$-proposal, we consider it as also containing that $(r,v)$-proposal.

Consider an $(r,v)$-proposal $R={(P,v,Q)}_{p_j}$, where $P=(F,\sigma ,M,r)$. At timeslot $t$ (according to $p_i$’s local clock), process $p_i$ will regard $R$ as valid if:

1. (i)

   ${\mathrm{\Pi }}_r$ and ${\mathrm{𝚕𝚘𝚐}}_{G_r}$ are defined;

2. (ii)

   $F\subset {\mathrm{\Pi }}_r$, and $|F|\ge {\rho }_C|{\mathrm{\Pi }}_r|$;

3. (iii)

   ${𝙼}_i$ is a $(𝒫,{\mathrm{\Pi }}_r,{\mathrm{𝚕𝚘𝚐}}_{G_r})$-proof of guilt for every process in $F$;

4. (iv)

   $M$ is a set of $r$-genesis messages, each signed by a different process in ${\mathrm{\Pi }}_r-F$;

5. (v)

   For each $p_k\in P_i(r)$, there exists an $r$-genesis message signed by $p_k$ in $M$;

6. (vi)

   $\sigma$ is the longest sequence extended by more than $\frac{1}{2}|{\mathrm{\Pi }}_r-F|$ elements of $M$;

7. (vii)

   $p_j=\mathrm{𝚕𝚎𝚊𝚍}(r,v)$;

8. (viii)

   $Q_i^{+}$ is undefined, or $Q$ is a valid QC with (a) $\mathrm{𝚟𝚒𝚎𝚠}(Q)\ge \mathrm{𝚟𝚒𝚎𝚠}(Q_i^{+})$, and (b) $𝙿(Q)=P$, and;

9. (ix)

   $p_i$ does not detect equivocation in view $(r,v)$.

For each $(r,v)$, $\mathrm{𝚟𝚘𝚝𝚎𝚍}(r,v)$ and $\mathrm{𝚕𝚘𝚌𝚔𝚜𝚎𝚝}(r,v)$ are initially set to 0. These values are used to indicate whether $p_i$ has yet voted or set its lock during view $(r,v)$.

An $r$-finish vote for $P$ is a message of the form $P_{p_j}$, where $P=(F,\sigma ,M,r)$ is an $r$-proposal and $p_j\in \mathrm{\Pi }$. At timeslot $t$, $p_i$ will regard the $r$-finish vote as valid if ${\mathrm{\Pi }}_r$ is defined and $p_j\in {\mathrm{\Pi }}_r-F$. A valid finish-QC for $P$ is a set of more than $\frac{1}{2}|{\mathrm{\Pi }}_r-F|$ valid $r$-finish votes for $P$, each signed by a different process.

If $p_i=\mathrm{𝚕𝚎𝚊𝚍}(r,v)$, then it will run this procedure during view $(r,v)$. To carry out the procedure, $p_i$ checks to see whether there exists some greatest such that it has received a valid QC, $Q$ say, with $\mathrm{𝚟𝚒𝚎𝚠}(Q)=(r,v^{\prime })$. If so, then $p_i$ sends the $(r,v)$-proposal $R={(𝙿(Q),v,Q)}_{p_i}$ to all processes. If not, then it sets $F$ to be the set of all processes $p_j\in {\mathrm{\Pi }}_r$ such that ${𝙼}_i$ is a $(𝒫,{\mathrm{\Pi }}_r,{\mathrm{𝚕𝚘𝚐}}_{G_r})$-proof of guilt for $p_j$. Let $M$ be the set of $r$-genesis messages that $p_i$ has received and which are signed by processes in ${\mathrm{\Pi }}_r-F$, and let $M^{\prime }$ be a maximal subset of $M$ that contains at most one message signed by each process. Process $p_i$ then sets $\sigma$ to be the longest sequence extended by more than $\frac{1}{2}|{\mathrm{\Pi }}_r-F|$ elements of $M^{\prime }$ and sends to all processes the $(r,v)$-proposal $R={(P,v,\perp )}_{p_i}$, where $P=(F,\sigma ,M^{\prime },r)$.

We adopt the message gossiping conventions described in Section 2.

While the function $ℱ$ is not explicitly used in the pseudocode, we will show in Section 7 that, at every $t$, ${\mathrm{𝚕𝚘𝚐}}_i=ℱ({𝙼}_i)$ (where ${\mathrm{𝚕𝚘𝚐}}_i$ and ${𝙼}_i$ are as locally defined for $p_i$ at $t$). The function $ℱ$ is specified in Algorithm 2.

The pseudocode appears in Algorithm 1. Below, we summarise the function of each section of code.

This line starts the execution of the wrapper by initiating ${ℰ}_1$, the first execution of $𝒫$, which has process set ${\mathrm{\Pi }}_1=\mathrm{\Pi }$ and ${\mathrm{𝚕𝚘𝚐}}_{G_1}={\mathrm{𝚕𝚘𝚐}}_G$ as the genesis log.

During the $r^{\text{th}}$ execution of $𝒫$, these lines check whether the recovery procedure should be triggered. If so, then $p_i$ disseminates an $r$-genesis message, temporarily resets its log, and starts the recovery procedure.

During the $r^{\text{th}}$ execution of $𝒫$, these lines check whether $p_i$ should extend its finalized and strongly finalized logs.

These lines initialize the $r^{\text{th}}$ execution of the recovery procedure by setting $t_0$ and $P_i(r)$.

These lines specify the instructions for view $(r,v)$. Initially, the leader waits $2{\mathrm{\Delta }}^{\ast }$ and then makes an $(r,v)$-proposal. Processes vote upon receiving a first valid $(r,v)$-proposal. Upon receiving a first valid QC for an $(r,v)$-proposal, $Q$ say, $p_i$ sets its lock to $Q$ and then waits $2{\mathrm{\Delta }}^{\ast }$. If, at this time, it still does not detect equivocation in view $(r,v)$, then it sends a finish vote for $𝙿(Q)$.

These lines determine when $p_i$ stops carrying out the $r^{\text{th}}$ execution of the recovery procedure. This happens when $p_i$ receives a valid finish-QC for some $r$-proposal $P$. The $r$-proposal $P$ then specifies ${\mathrm{\Pi }}_{r+1}$ and ${\mathrm{𝚕𝚘𝚐}}_{G_{r+1}}$.

To establish that at most one $r$-proposal can receive a valid finish-QC, suppose that some correct $p_i$ sends a finish vote for the $r$-proposal $P$ during view $(r,v)$. In this case, $p_i$ must set its lock to some valid QC, $Q$ say, at some timeslot $t$ while in view $v$. Suppose that $Q$ is a QC for the $(r,v)$-proposal $R$, and note that $𝙿(Q)=P$. We will observe that:

1. 1.

   All correct processes set their locks to some valid QC for $R$ while in view $v$.

2. 2.

   No $(r,v)$-proposal other than $R$ can receive a QC that is regarded as valid by any correct process.

From (1) and (2) it will be easy to argue by induction on $v^{\prime }>v$ that no correct process votes for any proposal $R^{\prime }={(P^{\prime },v^{\prime },Q^{\prime })}_{p_j}$ such that $P^{\prime }\ne P$, since their locks will forever prevent voting for such proposals. It follows that if any correct $p_k$ sends a finish vote for an $r$-proposal $P^{\prime }$ during some view $v^{\prime }\ge v$, then $P=P^{\prime }$. We conclude that, assuming (1) and (2), at most one $r$-proposal can receive a valid finish-QC.

To see that (1) holds, note that all correct processes will be in view $(r,v)$ at $t+{\mathrm{\Delta }}^{\ast }$ and will have received $Q$ by this time. They will therefore set their lock to be some QC for $R$, unless they have already received a valid QC for some $(r,v)$-proposal $R^{\prime }\ne R$. The latter case is not possible, since then $p_i$ would detect equivocation in view $(r,v)$ by $t+2{\mathrm{\Delta }}^{\ast }$, and so would not send the finish vote for $P$.

To see that (2) holds, the argument is similar. All correct processes will be in view $(r,v)$ at $t+{\mathrm{\Delta }}^{\ast }$ and will have received $R$ by this time. Item (ix) in the validity conditions for $(r,v)$-proposals prevents correct processes from voting for $(r,v)$-proposals $R^{\prime }\ne R$ at later timeslots, and correct processes cannot vote for such proposals at any timeslot $\le t+{\mathrm{\Delta }}^{\ast }$ because $p_i$ would detect equivocation in view $(r,v)$ in this case.

Having established that at most one $r$-proposal can receive a valid finish-QC, suppose now, towards a contradiction, that no $r$-proposal ever receives a valid finish-QC. Let $v$ be the least such that $\mathrm{𝚕𝚎𝚊𝚍}(r,v)$ is correct and let $i$ be such that $p_i=\mathrm{𝚕𝚎𝚊𝚍}(r,v)$. Since $p_i$ waits $2{\mathrm{\Delta }}^{\ast }$, until some timeslot $t$ say, before disseminating an $(r,v)$-proposal $R={(P,v,Q)}_{p_i}$, it will have seen all locks held by correct processes by this time, and will have received $r$-genesis messages from all processes in any set $P_j(r)$ for correct $p_j$. At $t$, $p_i$ will disseminate an $(r,v)$-proposal which all correct processes regard as valid by timeslot $t+{\mathrm{\Delta }}^{\ast }$. All correct processes will therefore vote for the proposal by this time and will receive a valid QC for the proposal by time $t+2{\mathrm{\Delta }}^{\ast }$. All correct processes will then set their locks. They will still be in view $(r,v)$ by time $t+4{\mathrm{\Delta }}^{\ast }$ (since they enter the view within time ${\mathrm{\Delta }}^{\ast }$ of each other) and will send $r$-finish votes for $P$ by this time.

We make the following definitions:

• $\mathrm{■}$

  Process $p_i$ begins the $r^{\text{th}}$ execution of the recovery procedure at the first timeslot at which $𝚛=r$ and $\mathrm{𝚛𝚎𝚌}=1$ (where those values are as locally defined for $p_i$).

• $\mathrm{■}$

  The $r^{\text{th}}$ execution of the recovery procedure begins at the first timeslot at which some correct process begins the $r^{\text{th}}$ execution of the recovery procedure.

• $\mathrm{■}$

  Execution ${ℰ}_r$ begins at the first timeslot at which some correct process begins execution ${ℰ}_r$. If $r>1$, then the ${(r-1)}^{\text{th}}$ execution of the recovery procedure also ends at this timeslot.

• $\mathrm{■}$

  If a QC/finish-QC is regarded as valid by all correct processes, we refer to it as a valid QC/finish-QC.

The proof of Lemma 5 is given in the full online version of the paper.

Given statement (iv) of Lemma 5, each value ${\mathrm{\Pi }}_r$ or ${\mathrm{𝚕𝚘𝚐}}_{G_r}$ is either undefined at all timeslots for all correct processes, or else is eventually defined and takes the same value for each correct process. We may therefore write ${\mathrm{\Pi }}_r$ and ${\mathrm{𝚕𝚘𝚐}}_{G_r}$ to denote these globally agreed values.

Let $\mathrm{𝚛𝚎𝚌}$, $𝚛$, ${𝙼}_i$, ${𝙼}_{i,r}$ and ${\mathrm{𝚕𝚘𝚐}}_i$ be as locally defined for $p_i$. Consider first the case that $\mathrm{𝚛𝚎𝚌}=0$ at the end of timeslot $t$. In this case, ${𝙼}_i$ has a consistency violation with respect to $ℱ({\mathrm{\Pi }}_r,{\mathrm{𝚕𝚘𝚐}}_{G_r})$ for each but does not have a consistency violation with respect to $ℱ({\mathrm{\Pi }}_{𝚛},{\mathrm{𝚕𝚘𝚐}}_{G_{𝚛}})$. Also, ${𝙼}_i$ contains a valid finish-QC for some $r$-proposal for each , which must be unique by Lemma 5. At the end of timeslot $t$, ${\mathrm{𝚕𝚘𝚐}}_i$ is the longest string $\sigma$ such that ${𝙼}_i$ (and ${𝙼}_{i,𝚛}$) is an $ℱ({\mathrm{\Pi }}_{𝚛},{\mathrm{𝚕𝚘𝚐}}_{G_{𝚛}})$-certificate for $\sigma$. The iteration defining $ℱ$ in Algorithm 2 will not return a value until it has defined all values ${\mathrm{\Pi }}_r$ and ${\mathrm{𝚕𝚘𝚐}}_{G_r}$ for $r\le 𝚛$. Upon discovering that ${𝙼}_i$ does not have a consistency violation with respect to $ℱ({\mathrm{\Pi }}_{𝚛},{\mathrm{𝚕𝚘𝚐}}_{G_{𝚛}})$, it will return the same value $\sigma$, as the longest string for which ${𝙼}_i$ is an $ℱ({\mathrm{\Pi }}_{𝚛},{\mathrm{𝚕𝚘𝚐}}_{G_{𝚛}})$-certificate.

Next, consider the case that $\mathrm{𝚛𝚎𝚌}=1$ at the end of timeslot $t$. In this case, ${𝙼}_i$ has a consistency violation with respect to $ℱ({\mathrm{\Pi }}_r,{\mathrm{𝚕𝚘𝚐}}_{G_r})$ for each $r\le 𝚛$, and also contains a valid finish-QC for some $r$-proposal for each , which must be unique by Lemma 5. However, ${𝙼}_i$ does not contain a valid finish-QC for any $𝚛$-proposal. At the end of timeslot $t$, ${\mathrm{𝚕𝚘𝚐}}_i={\mathrm{𝚕𝚘𝚐}}_{G_{𝚛}}$. The iteration defining $ℱ$ will not return a value until it has defined all values ${\mathrm{\Pi }}_r$ and ${\mathrm{𝚕𝚘𝚐}}_{G_r}$ for $r\le 𝚛$, and will then also return ${\mathrm{𝚕𝚘𝚐}}_{G_{𝚛}}$. $◀$

We say $p_i$ finalizes $\sigma$ if it sets ${\mathrm{𝚕𝚘𝚐}}_i$ to extend $\sigma$ and that $p_i$ strongly finalizes $\sigma$ if it sets ${\mathrm{𝚕𝚘𝚐}}_i^{\ast }$ to extend $\sigma$. Suppose $p_i$ finalizes $\sigma$ while running ${ℰ}_r$ at $t$ because there exists $M\subseteq {𝙼}_{i,r}$ which is an $ℱ({\mathrm{\Pi }}_r,{\mathrm{𝚕𝚘𝚐}}_{G_r})$-certificate for $\sigma$. By (iv) of Lemma 5, every correct process $p_j$ will begin ${ℰ}_r$ by $t+{\mathrm{\Delta }}^{\ast }$, and will receive the messages in $M$ by that time. This means $p_j$ will finalize $\sigma$, never to subsequently finalize any sequence incompatible with $\sigma$ while running ${ℰ}_r$, unless ${𝙼}_{j,r}$ has a consistency violation w.r.t. $ℱ({\mathrm{\Pi }}_r,{\mathrm{𝚕𝚘𝚐}}_{G_r})$ by $t+{\mathrm{\Delta }}^{\ast }$. In the latter case, $p_i$ will begin the recovery procedure by timeslot $t+2{\mathrm{\Delta }}^{\ast }$ and will not strongly finalize $\sigma$ at that time. We conclude that, if $p_i$ strongly finalizes $\sigma$ while running ${ℰ}_r$, then all correct processes finalize $\sigma$ while running ${ℰ}_r$.

If $p_i$ strongly finalizes $\sigma$ while running ${ℰ}_r$ and if the $r^{\text{th}}$ execution of the recovery procedure does not begin at any timeslot, it follows that, for all correct $p_j$, $\sigma ⪯{\mathrm{𝚕𝚘𝚐}}_j$ thereafter. So, suppose that the $r^{\text{th}}$ execution of the recovery procedure begins at some timeslot $t_0$. Note that, if $p_j$ is correct, then it waits $2{\mathrm{\Delta }}^{\ast }$ after beginning the $r^{\text{th}}$ execution of the recovery procedure before defining $P_j(r)$. By Lemma 5, all correct processes begin the $r^{\text{th}}$ execution of the recovery procedure within time ${\mathrm{\Delta }}^{\ast }$ of each other. Since correct processes send $r$-genesis messages immediately upon beginning the recovery procedure, it follows that $P_j(r)$ includes all correct processes.

By Lemma 5, there exists a unique $r$-proposal, $P=(F,{\sigma }^{\prime },M^{\prime },r)$ say, that receives a valid finish-QC. For this to occur, there must exist $v$ and an $(r,v)$-proposal $R=(P,v,\perp )$ (signed by $\mathrm{𝚕𝚎𝚊𝚍}(r,v)$) which receives a valid QC. This QC must include at least one vote by a correct process, $p_j$ say. It follows that $M^{\prime }$ must contain $r$-genesis messages from every member of $P_j(r)$, and so from every correct process. As we noted previously, if $p_i$ strongly finalizes $\sigma$ while running ${ℰ}_r$, then every correct process must finalize $\sigma$ before beginning the $r^{\text{th}}$ execution of the recovery procedure. So, for each $r$-genesis message $(\text{gen},{\sigma }^{\prime \prime },r)$ sent by a correct process, ${\sigma }^{\prime \prime }$ must extend $\sigma$, and also extends ${\mathrm{𝚕𝚘𝚐}}_{G_r}$. It therefore holds that $\sigma$ (and ${\mathrm{𝚕𝚘𝚐}}_{G_r}$) is extended by more than $\frac{1}{2}|{\mathrm{\Pi }}_r-F|$ elements of $M^{\prime }$. Recall that ${\sigma }^{\prime }$ is as specified by $P$. No correct process will vote for $R$ unless ${\sigma }^{\prime }$ is the longest sequence extended by more than $\frac{1}{2}|{\mathrm{\Pi }}_r-F|$ elements of $M$, meaning that ${\sigma }^{\prime }$ must extend $\sigma$ and ${\mathrm{𝚕𝚘𝚐}}_{G_r}$. So far, we conclude that ${\mathrm{𝚕𝚘𝚐}}_{G_{r+1}}$ extends $\sigma$ and ${\mathrm{𝚕𝚘𝚐}}_{G_r}$. Since it follows by the same argument that ${\mathrm{𝚕𝚘𝚐}}_{G_s}$ extends $\sigma$ for all $s>r$, the claim of the lemma holds. $◀$

The proof of Lemma 8 is given in the full online version of the paper.

Recall that, in Section 3, we set $x_0=0$ and $x_{r+1}=x_r+{\rho }_C(1-x_r)$, and then defined:

Note that $x_r$ lower bounds the fraction of the processes removed to form ${\mathrm{\Pi }}_{r+1}$, i.e. $|\mathrm{\Pi }-{\mathrm{\Pi }}_{r+1}|\ge x_{r}n$. By Lemma, 8, if there exist $r$ consistency violations, then the $r^{\text{th}}$ execution of the recovery procedure must end at some timeslot. If the adversary is $g_2(k)$-bounded, and since $𝒫$ has liveness resilience ${\rho }_L$, it follows that liveness must hold. If the adversary is $g_1(r)$-bounded, then since $𝒫$ has consistency resilience ${\rho }_C$, the ${(r+1)}^{\text{th}}$ execution of the recovery procedure cannot begin at any timeslot. From Lemma 8, it follows that there are at most $r$ consistency violations. $◀$

The fact that the wrapper has recovery time $O(f_a{\mathrm{\Delta }}^{\ast })$ with liveness parameter $\mathrm{\ell }$ follows directly from (iii) of Lemma 5, since views are of length $O({\mathrm{\Delta }}^{\ast })$. To establish the claim regarding probabilistic recovery time, note that we required ${\rho }_C>0$ in the definition of optimal resilience. Some finite power of $(1-{\rho }_C)$ is therefore less than ${\rho }_L$, so there exists $r$ such that any execution in which the adversary is $1-{\rho }_L$-bounded can have most $r$ consistency violations. If the adversary is $\rho$-bounded, then the probability that, for one of the (at most $r$) executions of the recovery procedure, the first $d$ views all have faulty leaders is $O(r{\rho }^d)=O({\rho }^d)$ for fixed ${\rho }_C$. Since each view is of length $O({\mathrm{\Delta }}^{\ast })$, it follows from (iii) of Lemma 5 that the wrapper therefore has probabilistic recovery time $O({\mathrm{\Delta }}^{\ast }\text{log}\frac{1}{\epsilon })$ with liveness parameter $\mathrm{\ell }$, as claimed. $◀$

A sequence of papers, including Buterin and Griffith [7], Civit et al. [10], and Shamis et al. [23], describe protocols that satisfy accountability. Sheng et al. [24] analyze accountability for well-known permissioned protocols such as HotStuff [29], PBFT [8], Tendermint [4, 5], and Algorand [9]. Civit et al. [12, 11] describe generic transformations that take any permissioned protocol designed for the partially synchronous setting and provide a corresponding accountable version. These papers do not describe how to reach consensus on which guilty parties to remove in the event of a consistency violation (i.e. how to achieve “recovery”), and thus fall short of our goals here. One exception to this point is the ZLB protocol of Ranchal-Pedrosa and Gramoli [21], but the ZLB protocol only achieves recovery if the adversary controls less than a $5/9$ fraction of participants, and does not achieve bounded rollback. Freitas de Souza et al. [13] also describe a process for removing guilty parties in a protocol for lattice agreement (this abstraction is weaker than SMR/consensus and can be implemented in an asynchronous system), but their protocol assumes an honest majority and the paper does not consider bounded rollback. Sridhar et al. [26] specify a “gadget” that can be applied to blockchain protocols operating in the synchronous setting to reboot and maintain consistency after an attack, but they do not describe how to implement recovery and assume that an honest majority is somehow reestablished out-of-protocol.

Budish et al. [6] consider “slashing” in proof-of-stake protocols in the “quasi-permissionless” setting. Their main positive result is a protocol that, in the same timing model considered in this paper (with additional guarantees provided pre-GST message delays are bounded by a known parameter ${\mathrm{\Delta }}^{\ast }$), guarantees what they call the “EAAC property” – honest players never have their stake slashed, and some Byzantine stake is guaranteed to be slashed following a consistency violation. Budish et al. [6] do not contemplate repeated consistency violations, a prerequisite to the notions of recoverable consistency and liveness that are central to this paper. To the extent that it makes sense to compare their “recovery procedure” with our “wrapper,” our protocol is superior in several respects, with worst-case recovery time $O(n{\mathrm{\Delta }}^{\ast })$ (as opposed to $O(n^2{\mathrm{\Delta }}^{\ast })$); probabilistic recovery time $O({\mathrm{\Delta }}^{\ast }\text{log}\frac{1}{\epsilon })$, where $\epsilon$ is an error-probability bound (as opposed to $O(n{\mathrm{\Delta }}^{\ast }\text{log}\frac{1}{\epsilon })$); and rollback $2{\mathrm{\Delta }}^{\ast }$ (as opposed to unbounded rollback).