Beyond One-third Faulty Replicas in
Byzantine Fault Tolerant Systems

We use the same replicated state machine model as presented in past work [6, 24]. The network is unreliable and may replicate, discard, and reorder messages with the one exception that it cannot indefinitely prevent two honest parties from communicating with each other.

The system consists of a number of clients and 3f + 1 replicated servers, where f is a predetermined parameter. Clients make requests for operations to servers. An operation is executed when servers accept it and apply it to their state. An operation is completed when its originating client accepts the reply. We use lower-case letters that appear early in the alphabet such as a, b, c to denote clients, and letters that appear late in the alphabet such as p, q, u, w to denote servers. We also use the term replicas and servers interchangeably. A node is either a client or server. Each node has a public/private key pair. Each server knows the public keys of all nodes and each client knows the public keys of all servers.

We assume a Byzantine failure model. A faulty node may either halt or deviate from correct behavior arbitrarily, even colluding with other faulty nodes. However, a faulty node cannot forge digital signatures of correct nodes or find collisions of a cryptographic hash function.

3. Fork consistency

Figure 2 shows the server-side interface between a state-machine replication system (such as PBFT) and the replicated service (e.g., an NFS file server). The service starts in a fully-specified initial state and provides a single function, Execute, that takes a request operation, op, as an argument, then deterministically updates its state and returns a result, res. In ordinary operation, clients submit requests through a client-side replication library. The server-side code communicates amongst replicas so as to invoke Execute with an identical sequence of requests on every replica, thereby producing identical results to send back to the client. The client side library returns the results from the matching replies to the client.

Of course, a compromised server need not behave as described above. It can fail to respond to messages. Worse yet, it may return arbitrary results to clients; it may subvert network routing to intercept and tamper with packets; it may even collude with other compromised servers and send carefully-crafted messages that subvert honest replicas and ultimately convince the client library to return incorrect or inconsistent results. We need techniques that allow honest clients and replicas to minimize the damage that may be caused by malicious replicas.

A significant part of the challenge is ensuring that malicious replicas do not corrupt the internal state of honest replicas. Because an honest replica's internal state is entirely determined by the sequence of all operations it has ever executed, we introduce a term for this history: We call the sequence L^all = op¹, op², ..., opⁿ ; of all operations executed by a replica the result list of its latest operation opⁿ. This result list entirely determines both the result returned by the Execute function for opⁿ and the state Sⁿ⁺¹ of the replica after executing opⁿ. Whenever possible, we would like to ensure that honest replicas all have the same result lists and that these lists contain only requests legitimately issued by users.

To defend against illegitimate requests, each operation may be signed by the key of its originating user. Without knowing a user's private key, a bad replica cannot forge requests. By verifying the signatures on requests, honest replicas can limit themselves to calling Execute only on operations legitimately requested by users. Should malicious replicas learn a compromised user's private key, they may be able to convince honest replicas to execute arbitrary operations with the privileges of the compromised user; effectively any well-formed operation by a compromised user is legitimate.

In an ideally consistent (well-behaved) system, every honest replica will have the same result list L^all = op¹, op², ..., opⁿ ; for operation opⁿ. Moreover, this list will preserve the temporal order of non-overlapping operations. Malicious replicas, of course, may behave as though opⁿ's result is not the outcome of executing L^all, but rather of some different result list L^bad. In fact, malicious server behavior may be incompatible with any possible sequence of legitimate requests; we therefore allow L^bad to contain illegal operations (such as “cause the next operation to return this particular result”).

When a system undergoes total failure (as in the case of PBFT with more than f faulty replicas), an operation's result list even at an honest replica might not contain all previously issued requests; malicious servers may have succeeded in concealing the existence of legitimately issued operations. Worse yet, it may be that different replica's result lists contain the same operations in different orders, and that this convinces the client libraries on different machines to return inconsistent results. To mitigate these problems, we previously defined a consistency model, fork consistency [16], that can be realized in the presence of entirely malicious servers. An important property of fork consistency is that it helps provide server accountability by allowing clients to detect any past consistency violations on the part of bad servers.

In defining fork consistency, we make a distinction between operations issued by correct clients, which obey the protocol, and malicious or compromised clients that don't. We use the term result lists only for replies to operations issued by correct clients running our library, as it makes little sense to talk about the results seen by clients that do not implement the protocol or even necessarily use our software. However, we consider any result accepted by a correct client to have a result list. In the event that malicious servers completely break the system, they may induce clients to accept “impossible” results, in which case the corresponding result lists must have illegal operations.

---

// At server side:
(Sⁿ⁺¹, res) <- Execute(Sⁿ, op);

Figure 2: Pseudocode for replicated state machines.

---

Definition: A system is fork consistent if and only if it satisfies the following requirements:

• Legitimate-request Property: Every result accepted by a correct client has a result list L that contains only well-formed operations legitimately issued by clients.
• Self-consistency Property: Each honest client sees all past operations from itself: if the same client a issues an operation opⁱ before op^j, then opⁱ also appears in op^j's result list.

  This property ensures that a client has a consistent view with respect to its own operations. For example, in a file system, a client always reads the effect of its own writes.

• No-join Property: Every accepted result list that contains an operation op by an honest client is identical up to op.

One corollary of fork consistency is that when two clients see each others' recent operations, they have also seen all of each other's past operations in the same order. This makes it possible to audit the system; if we can collect all clients' current knowledge and check that all can see each others' latest operations, we can be sure that the system has never in the past violated ideal consistency. Another corollary is that every result list preserves the temporal order of non-concurrent operations by correct clients, since an accepted result list cannot contain operations that have not yet been issued.

We say two result lists are consistent if one is an improper prefix of the other. We say two result lists are forked if they are not consistent. For instance, result list op¹, op²; and result list op¹, op³; are forked, while op¹, op²; and op¹, op², op³; are not. If clients accept forked result lists, the system has failed to deliver ideal consistency.

We say servers are in different fork sets if they reflect forked result lists. A fork set consists of a set of servers who return the same set of consistent result lists to all clients, though in an asynchronous system, some results may not reach the client before an operation completes. Intuitively, a correct server cannot be in more than one fork set. A malicious server, however, can simultaneously be in multiple fork sets—pretending to be in different system states when talking to different nodes. An attacker who controls the network and enough replicas may cause the remaining honest replicas to enter different forks sets from one another, at which point with any practical protocol clients can no longer be assured of ideal consistency. ¹

---

Figure 3: An example of fork consistency. Since the server deceives client b about a's operation op2, client a's result list op1, op2;, and b's result list op1, op3; are only fork consistent, not ideally consistent. (Strictly speaking, client a still has ideal consistency at this moment, should op2 be ordered before op3. However, client a will miss ideal consistency hereafter.)

---

Figure 3 shows an example where fork consistency differs from ideal consistency. Initially, all clients have the same result list op¹;. Client a issues a request op², and gets back the result list op¹, op²; from fork set FS_α; after that, client b's operation op³ returns with the result list op¹, op³; from fork set FS_β. Here the server deceives b about a's completed operation op². Therefore, client a's result list and client b's are forked. At this moment, one can verify that the system has delivered fork consistency, but failed to provide ideal consistency. It is worth pointing out that if a protocol returned the entire result list with each reply to an operation, a client could compare result lists to detect the attack whenever it received replies from two different fork sets. The BFT2F protocol presented in Section 5 uses hashes to achieve a similar guarantee without the efficiency or privacy problems of shipping around result lists.

---

Figure 4: In a replicated state system, the intersection of two fork sets can only consist of provably malicious servers, which are denoted by shaded circles. The partition that excludes the intersection part might have honest servers and malicious ones that have not yet misbehaved.

---

Figure 4 shows a potential configuration that could produce the two fork sets in Figure 3. FS_α ∩FS_β must have only faulty servers that have already acted maliciously (e.g., p, q, o). FS_α − (FS_α ∩FS_β) and FS_β − (FS_α ∩FS_β) can include either honest servers (e.g., u, w, t), or malicious servers who have not misbehaved so far (e.g., r could be such a server), and so who are externally indistinguishable from honest servers, though they might later deviate from the protocol.

3.1. Fork consistency examples

For some applications, fork consistency may be nearly as good as ideal consistency. In the example of a card-swipe access control service, if two out four replicas are compromised and an attacker forks the system state, it is likely only a matter of hours or days before people notice something is wrong—for instance that new users' cards do not work on all doors. At that point, the administrators must repair the compromised replicas. In addition, they may need to merge access logs and replay all revocations executed in either fork set by the two honest replicas. Even without server compromises, adding and removing door access is often not instantaneous anyway, both because of bureaucracy and because people do not always report lost or stolen ID cards immediately.

On the other hand, in other settings fork consistency may lead to quantifiable damage compared to ideal consistency. Consider a bank that uses four machines to replicate the service that maintains account balances. An attacker who compromises two of the machines and forks the state can effectively duplicate his account balance. If the attacker has $1,000 in his account, he can go to one branch and withdraw $1,000, then go to a branch in a different fork set and withdraw $1,000 again.

Finally, of course, there are settings in which fork consistency on its own is nearly useless. For example, a rail signaling service split into two fork sets, each of which monitors only half the trains and controls half the signals, could easily cause a catastrophic collision. One way to mitigate such problems is to leverage fork consistency to get bounded inconsistency through heartbeats. A trusted heartbeat client could increment a counter every few seconds; trains that do not detect the counter being incremented could sound an alarm. The attacker would then need to compromise either another f replicas or the heartbeat box to suppress the alarms.

3.2. Impossibility of one-round fork consistency

Unfortunately, for a system to guarantee fork consistency when the fraction of honest replicas is too small for linearizability, clients must send at least two messages for every operation they perform. The most serious implication of this is that the system can no longer survive client failures—if a client fails between the first and second messages of an operation, the system may no longer be able to make progress. Another disadvantage is that slow clients can severely limit system throughput by leaving servers idle between the two messages. Finally, there are various implementation reasons why a one-round protocol is often simpler and more efficient, particularly if there is high latency between the client and servers.

Theorem: In an asynchronous system that provides liveness when up to f out of 3f+1 replicas fail, guaranteeing fork consistency in the face of more than f replica failures requires more than one round of client-server communication on each operation.

Proof Sketch: For simplicity, we consider the case of four replicas with f=1, though the same argument applies to any number of replicas. In a single-round protocol, a client sends a single message that eventually convinces honest replicas to alter their state by executing an operation. Consider the case when two clients, a and b, issue two requests, op_a and op_b, concurrently. Neither client could have known about the other's request when issuing its operation. Thus, either op_a or op_b is capable of being executed before the other.

If, for instance, the network delays op_a, op_b could execute before op_a arrives and vice versa. Moreover, because of liveness, request op_a must be capable of executing if both client b and replica w are unreachable, as long as the remaining three replicas respond to the protocol. Figure 5 illustrates this case, where the result list op_b, op_a; was eventually returned to client a.

---

Figure 5: Two malicious servers (p and q) wear different hats when talking to distinct honest servers (u or w) in the server-server agreement phase, during which all servers communicate with each other to achieve consensus on incoming requests. Meanwhile, they delay the communication between u and w. In this way, p and q, with u, return result list opb, opa; to client a; p and q, with w, return opa, opb; to client b.

---

The same reasoning also applies to client b, who might get result list op_a, op_b; when replica u is unreachable. These two out-of-order result lists reflect the (malicious) servers' ability to reorder concurrent requests at will, if a single message from a client is allowed to change the system state atomically. This clearly violates the no-join property of fork consistency.

3.3. A two-round protocol

---

Figure 6: A two-round protocol.

---

The problem with a one-round protocol is that at the time a client signs a request for operation op, there may be previous operations by other clients it does not know about. Therefore, there is nothing the client can include in its signed request message to prevent the two honest replicas (u and w) from believing op should execute in two different contexts.

In a two-round protocol, the client's first message can request knowledge about any previous operations, while the second message specifies both the operation and its execution order. Figure 6 shows such a protocol. A client sends an acquire request to acquire the system's latest state in the first round; a server replies with its current state. Disregarding efficiency, a straw-man protocol might represent this state as the previous operation's result list (i.e., the impractically long list of every operation ever executed). In the second round, the client commits its operation op by signing a message that ties op to its execution order. Again, in a straw-man, inefficient protocol, the client could append its new operation to the list of all previous operations and sign the whole list. Servers then sanity check the commit message, execute op, and send back the reply.

Note that servers are not allowed to abort an operation after replying to an acquire message—the acquire-ack is a commitment to execute the operation in a particular order given a signed commit. Otherwise, if servers could optionally abort operations, malicious replicas p and q could convince u and a that op_a aborted while convincing w to execute it, violating fork consistency. But of course a server cannot execute an operation until it sees the signed commit message, which is why clients can affect both liveness and throughput.

These problems can be overcome in application-specific ways. When it is known that an operation's result cannot depend on a previous operation's execution, it is safe to execute the later operation before the previous one commits. SUNDR performs this optimization at the granularity of files and directory entries, which mostly overcomes the performance bottleneck but can still lead to unavailable files after a client failure. Because SUNDR does whole-file overwrites, one can recover from mid-update client crashes by issuing a new write that either deletes or supersedes the contents of whatever file is generating I/O timeout errors.

HQ replication [8] similarly allows concurrent access to different objects. The technique could be used to improve performance of a two-round protocol. However, object semantics are general enough that there would be no way to recover from a client failure and still provide fork consistency with f+1 malicious replicas.

Figure 7 shows a two-round protocol in pseudocode. S_n^curr represents node n's latest knowledge of the system state. We say S_i^curr ≺ S_j^curr (meaning S_i^curr happens before S_j^curr) if one of node j's past system states is identical to S_i^curr—in other words, node j's current knowledge is consistent with and strictly fresher than i's. In our straw-man protocol, if S_n^curr is a list of all operations ever executed, then S_i^curr ≺ S_j^curr means S_i^curr is a prefix or S_j^curr.

---

//executed by server x upon receiving acquire.
Server_Round1(a, S_a^curr, op)
if next = null and S_a^curr ≺ S_x^curr
  Extract timestamp ts from op;
  Agree with other servers that current state is S_x^curr
   and next operation to execute is op from client a;
 next [a, op];
 send [acquire-ack, ts, S_x^curr] to client a;

//executed by client a to collect acquire-acks
//and generate commit.
Client_Check_Commit(op)
Decide on the system's current state S^curr based on
 2f+1 matching acquire-acks from servers;
S_a^curr <- S^curr;
send [commit, S_a^curr, op]_Ka⁻¹ to all servers;

//executed by server x upon receiving commit.
Server_Round2(a, S_a^curr, op)
if next = [a, op] and S_a^curr = S_x^curr
 (S_x^curr, res) <- ExecuteS_x^curr, op;
 send [reply, S_x^curr, res] to client a;
 next <- null;

Figure 7: Pseudocode for a two-round protocol.

---

4. Fork* consistency

Because of the performance and liveness problems of two-round protocols, this section defines a weaker consistency model, fork* consistency, that can be achieved in a single-round protocol. Intuitively, rather than have separate acquire and commit messages, our plan will be to have each request specify the precise order in which the same client's previous request was supposed to have executed. Thus, it may be possible for an honest replica to execute an operation out of order, but at least any future request from the same client will make the attack evident.

Turning back to the example in Figures 3 and 4, with a one-round protocol, after the system state has been forked, client c's operation op⁴ might be applied to servers in both fork sets if c has no clue that the system state has been forked when it issues op⁴. Then the honest servers in both FS_α and FS_β will update their system state, S_α or S_β, respectively, with op⁴, violating the no-join property of fork consistency. However, client c is only going to accept the reply from one of the fork sets, e.g., FS_α, and adopt its new state, S_α, as its freshest knowledge of the system state. If the protocol can prohibit any correct node that has seen state in one fork set, namely FS_α, from issuing any operations that execute in another (e.g., FS_β), then all future operations from client c can only be applied to servers in fork set FS_α (or subsequent forks of FS_α).

Fork* consistency therefore relaxes the no-join property in fork consistency to a join-at-most-once property: two forked result lists can be joined by at most one operation from the same correct client.

• Join-at-most-once Property: If two result lists accepted by correct clients contain operations op' and op from the same correct client, then both result lists will have the operations in the same order. If op' precedes op, then both result lists are identical up to op'.

The join-at-most-once property is still useful for system auditing. We can periodically collect all clients' current knowledge to check that all have seen each others' latest operations. Suppose each client issues an operation for this purpose at times t¹, t² ... tⁿ, where tⁿ is the time of the latest check. The join-at-most-once property guarantees that if the checks succeed, then the system has never violated ideal consistency up to time tⁿ⁻¹.

In the example above, for client a, the new result list is op¹, op², op⁴;, and for b, it is op¹, op³, op⁴;. Yet, the system still delivers fork* consistency at this moment, just not fork consistency or ideal consistency. However, fork* consistency forces malicious servers to choose between showing c's future operations to a or b, but not both.

4.1 Fork* consistency examples

In the card-swipe example, fork* consistency has effectively the same consequences as fork consistency. It delays revocation and complicates recovery. The only difference is that after the attack one operation from each client may appear in both fork sets, so, for example, one user may get access to a new door in both fork sets, but no one else will.

In the case of the bank, fork* consistency increases the potential loss. For example, the attacker can go to one branch, withdraw $1,000, then go to the other branch and deposit the $1,000. The attacker can ensure this deposit shows up in both fork sets—allowing him to withdraw an additional $1,000 from the first branch, as well as the $2,000 he can get from the branch at which he made the deposit.

In the case of a heart-beat server used to sound an alarm, fork* consistency doubles the amount of time required to detect a problem, since one increment of the counter may show up in both fork sets.

5. BFT2F Algorithm

In this section, we present BFT2F, an extension of the original PBFT protocol [6] that guarantees fork* consistency when more than f but not more than 2f out of 3f+1 servers fail in an asynchronous system.

Like PBFT, BFT2F has replicas proceed through a succession of numbered configurations called views, and uses a three-phase commit protocol [22] to execute operations within views. The three phases are pre-prepare, prepare, and commit. In view number view, replica number viewmod 3f+1 is designated the primary and has responsibility for assigning a new sequence number to each client operation.

5.1. BFT2F Variables

Below, we describe major new variables and message fields introduced in BFT2F. We use superscripts to denote sequence number, e.g., msgⁿ refers to the message with sequence number n. We use subscripts to distinguish variables kept at different nodes.

Hash Chain Digest (HCD):

A HCD encodes all the operations a replica has committed and the commit order. A replica updates its current HCD to be HCDⁿ = D (D(msgⁿ) ∘ HCDⁿ⁻¹) upon committing msgⁿ, where D is a cryptographic hash function and ∘ is a concatenation function. Replicas and clients use HCDs to verify if they have the same knowledge of the current system state.

Hash Chain Digest History:

To check if a replica's current knowledge of the system state is strictly fresher than another replica's and not forked, each replica keeps a history of past HCDs. We denote replica p's history entry for msgⁿ as T_p[n].

Version Vector:

Every node i represents its knowledge of the system state in a version vector V_i. The version vector has 3f+1 entries, one for each replica. Each entry has the form r, view, n, HCDⁿ;_Kr⁻¹, where r is the replica number, view is the view number, n is the highest sequence number that node i knows replica r has committed, and HCDⁿ is r's HCD after n operations. The entry is signed by r's private key K_r⁻¹. We denote replica r's entry in V_i by V_i[r], and use C structure notation to denote fields—i.e., V_i[r].view, V_i[r].n, and V_i[r].HCD.

We define several relations and operations on these data structures:

• Let V be a version vector. We define a cur function to represent the current state of the system in V as follows: If at least 2f+1 entries in V have the same n and HCD values, cur(V) is one of these entries (e.g., the one with the lowest replica number). Otherwise, cur(V)=none.
• Let h and g be two version vector entries signed by the same replica. We say h dominates g iff h.view ≥ g.view and either the two entries have identical n and HCD fields or h.n>g.n.
• We say h dominates g with respect to hash chain digest history T iff h dominates g and the two entries' HCD fields appear at the appropriate places in T—i.e., h.HCD = T[h.n] and g.HCD = T[g.n]. In other words, this means that g appears in the history T that leads up to h.

Whenever a client a sees a version vector entry h signed by replica p, it always updates its own version vector V_a by setting V_a[p]← h if h dominates the old value of V_a[p]. A server r similarly updates V_r[p]← h if h is recent (e.g., not older than the beginning of T_r) and dominates the old V_r[p] with respect to T_r.

5.2. BFT2F Node Behavior

Client Request Behavior

A client a multicasts a request for an operation request, op, ts, a, cur(V_a);_Ka⁻¹ to all the replicas, where ts is a monotonically increasing timestamp, cur(V_a) is a's last known state of the system, and the message is authenticated by a's signature key, K_a⁻¹.

We note that while PBFT uses more efficient MAC vectors to authenticate requests from clients, BFT2F requires public-key signatures. The reason is that faulty clients may interfere with the replicas' operation by issuing requests in which some MAC vector entries are valid and some are invalid. Such a partially correct MAC vector causes some replicas to accept the request and some to reject it. PBFT can recover from such a situation if f+1 replicas attest to the validity of their MAC vector entries. However, in BFT2F, we want to avoid executing illegitimate operations even with >f faulty replicas, which means it is still not safe to execute an operation under such circumstances.

Server Behavior

Every server keeps a replay cache containing the last reply it has sent to each client. Upon receiving a request request, op, ts, a, cur(V_a);_Ka⁻¹ from client a, a server first checks the signature, then checks that the request is not a replay. Clients execute one operation at a time, so if ts is older than the last operation, the server ignores the request. If ts matches the last operation, the server just re-sends its last reply. Otherwise, the server checks that cur(V_a).HCD matches the HCD in the last reply the server sent to the client. If it does not, the client may be in a different fork set, or may be malicious and colluding with a malicious server. Either way, the server ignores this request. Once a message has been validated and checked against the replay cache, processing continues differently on the primary and other servers.

The primary replica, p, assigns the request a sequence number n and multicasts a pre-prepare message pre-prepare, p, view, n, D(msgⁿ);_σp to all other replicas. Here σ_p is either a MAC vector or a signature with p's private key, K_p⁻¹.

Upon receiving a pre-prepare message matching an accepted request, replica q first checks that it has not accepted the same sequence number n for a different message msg'ⁿ in the same view view. It also ensures n is not too far out of sequence to prevent a malicious primary from exhausting the sequence number space. Replica q then multicasts a prepare message prepare, q, view, n, D(msgⁿ);_σq to all other replicas.

A replica u tries to collect 2f matching prepare messages (including one from itself) with the same sequence number n as that in the original pre-prepare message. When it succeeds, we say replica u has prepared the request message msgⁿ. Unlike PBFT, u does not commit out of order, i.e., it enters the commit phase only after having prepared the message and committed all requests with lower sequence numbers.

To start committing, replica u computes HCDⁿ ← D(msgⁿ ∘ HCDⁿ⁻¹) and sets T_u[n]← HCDⁿ, updates V_u[u] to u, view, n, HCDⁿ;_Ku⁻¹, and multicasts a commit message commit, u, view, n, HCDⁿ;_Ku⁻¹; to all other replicas.

When replica w receives a commit message from u with a valid signature and HCDⁿ, it updates the entry for u in its current version vector, V_w[u], to u, view, n, HCDⁿ;_Ku⁻¹. Replica w commits msgⁿ when it receives 2f+1 matching commit messages (usually including its own) for the same sequence number n and the same HCD (HCDⁿ).

Replica w executes the operation after it has committed the corresponding request message msgⁿ. It sends a reply message to the client containing the result of the computation as well as its current version vector entry V_w[w]. Since w has collected 2f+1 matching commit messages, we know that these 2f+1 replicas are in the same fork set up to sequence number n.

Behavior of Client Receiving Replies

A reply from replica w has the format, reply, a, ts, res, w, view, n, HCDⁿ;_Kw⁻¹;_σw, where view is the current view number, ts is the original request's timestamp, and res is the result of executing the requested operation. A client considers an operation completed after accepting at least 2f+1 matching replies each of which contains the same ts, res, n, and HCDⁿ. (Recall by comparison that PBFT only requires f+1 matching replies.) This check ensures the client only accepts a system state agreed upon by at least 2f+1 replicas. Therefore, if no more than 2f replicas fail, the accepted system state reflects that of at least one correct replica. Client a also updates its V_a[w] to w, view, n, HCDⁿ;_Kw⁻¹ for each w of the 2f+1 replies, ensuring that HCDⁿ becomes the new value of cur(V_a).HCD.

To deal with unreliable communication, client a starts a timer after issuing a request and retransmits if it does not receive the required 2f+1 replies before the timer expires. Replicas discard any duplicate messages and can also fetch missing requests from each other in case the client crashes.

5.3. Garbage Collection

If a replica r has been partitioned from the network, it may have missed some number of successfully executed operations and need to learn them from other replicas. For small numbers of missed operations, the replica can just download the logged operations and commits and execute any operation that has 2f+1 commit messages with appropriate HCDs. However, if other replicas have truncated their logs, r may not be able to download all missing operations individually. It may instead need to do a bulk transfer of the entire state of the service from other replicas. The question then becomes how to authenticate the state in such a transfer.

In PBFT, r validates the state using stable checkpoints gathered every I operations (e.g., I=128). A stable checkpoint is a collection of signed messages from 2f+1 replicas attesting that the service had hash D(stateⁿ) at sequence n. r can then believe stateⁿ. In BFT2F, the signed messages must additionally vouch that stateⁿ is in the same fork set as r and allow r to bring its replay cache up to date. Our implementation accomplishes this by having each replica keep state back to n_low, the lowest version number in its version vector. This state may be required for application-specific recovery from fork attacks anyway. However, it requires unbounded storage while any replica is unavailable, which may be undesirable, so here we outline a way to achieve fork* consistency with bounded storage.

When replica u signs a checkpoint for sequence n, it includes its version vector V_u in the message. If no w has V_u[w].n≤ n−2I, then no honest replica will ever ask to be updated from a state n−2I or older. If, however, there is a V_u[w]≤ n−2I, then, for each such w, u includes in the checkpoint one of its own old version vector entries h that dominates V_u[w] with respect to T_u. Furthermore, it keeps enough commit messages around to roll w's state forward from V_u[w].HCD to h.HCD, so that w can be assured it is in the same fork set as h. To ensure w does not progress beyond h.n, replicas execute no more than 2I operations beyond the last stable checkpoint that shows them up to date.

In detail, u's signed checkpoint has the form checkpoint, r, n, D(stateⁿ), D(rcacheⁿ), V_u, E;_Ku⁻¹. Here rcacheⁿ is u's replay cache at sequence n (without the signatures or replica numbers, to make it identical at all unforked replicas). V is u's current version vector. E is a set of older values of V_u[u] computed as follows. For each w in which V_u[w].n ≤ n−2I, E contains u's signed version vector entry from the next multiple of I after V_u[w].n + I. A stable checkpoint consists of checkpoint messages signed by 2f+1 different replicas with the same n, D(stateⁿ), D(rcacheⁿ), and E (modulo the replica IDs and signatures in E). Given a stable checkpoint, u can delete log state except for operations more recent than n−2I and the 2I operations leading up to each element of E.

When computing a stable checkpoint, it may be that replicas do not initially agree on E. However, each replica updates its version vector using any recent signed entry with a valid HCD in any other replica's checkpoint message and multicasts a new checkpoint message upon doing so. (To ensure the receiving replica can check the HCD, replicas ignore commit and checkpoint messages before the last stable checkpoint, so that once marked stale in a stable checkpoint, a replica can only change to being completely up-to-date.) Note that even after a stable checkpoint exists, a replica that was previously shown as out of date can cause a second stable checkpoint to be generated for the same sequence number by multicasting a checkpoint message with its up-to-date version vector.

5.4. Server View Change

In BFT2F, a replica r experiencing a timeout sends a view-change message view-change, view+1, V_r[r], P;_Kr⁻¹ to all other replicas. Here V_r[r] is the version vector entry for r's last committed operation, while P is a set of sets P_m for each prepared message m with sequence number higher than n. Each P_m contains the pre-prepare message for m and 2f corresponding matching prepare messages.

The primary p in the new view view+1 checks all signatures (but not MACs) and validates the V_r[r].HCD value in view-change messages it receives. If V_p[p] dominates V_r[r] with respect to T_p, then V_r[r] is valid. Otherwise, if V_r[r] dominates V_p[p], then p requests from r an operation and 2f+1 matching commits with appropriate HCDs for every sequence number between V_p[p].n and V_r[r].n. p then executes these operations, bringing T_p up to date so that V_p[p] dominates V_r[r] with respect to T_p. If p cannot download the missing operations from r, it does a bulk state transfer.

We say two view-change messages conflict if their P fields include different operations for the same sequence number. This may happen if honest replicas are forked because of more than f failures, or if the σ authenticators on pre-prepare and prepare messages have corrupted MAC vectors and malicious replicas claim to have prepared messages for which they didn't actually receive a pre-prepare and 2f+1 matching prepares. As long as there are 2f+1 honest replicas (without which we cannot guarantee liveness), we will be in the latter case and p will eventually receive 2f+1 valid and non-conflicting view-change messages (including one from itself), at which point it multicasts a new-view message new-view, view+1, V, O;_Kp⁻¹. Here V is the set of 2f+1 valid, non-conflicting view-change messages. O is a set of pre-prepare messages constructed as below:

1. p determines min-s as the lowest sequence number of any version vector entry (V_r[r]) in an element of V. p then determines max-s as the highest sequence number of any of the P_m sets in elements of V.
2. For each sequence number n from min-s through max-s, p either (1) constructs a pre-prepare message in the new view, if a P_m in one of the view-change messages has a valid request for sequence number n, or (2) constructs a special null request pre-prepare, p, view+1, n, D(null);_Kp⁻¹, null; to fill in the sequence number gap.

A backup replica u in the new view validates the new-view message as follows. u checks the version vector in each element of V using the same checks p performed upon receiving the view-change messages. If u is too far out of date, it may need to do a state transfer. u also verifies that O is properly constructed by executing the same procedure as the primary. If u accepts the new-view message as valid, it sends a prepare message for each message in O and proceeds normally in the new view.

When there are no more than f faulty replicas, the above algorithm is essentially the same as PBFT with hash chain digests replacing the state hashes in PBFT's checkpoint messages. When more than f but no more than 2f replicas fail, there may be concurrent view changes in different fork sets. In the worst case when 2f replicas fail, up to f+1 view changes may succeed concurrently, leading to f+1 fork sets.

However, with no more than 2f failures, each fork set is guaranteed to contain at least one honest replica, r, which ensures fork* consistency. To see this, we consider two cases. First, suppose r does not do a state transfer. Its hash chain digests are then simply the result of processing a sequence of operations in turn. Because r checks the cur(V_a) in a client's request against the last reply to that client, r will never accept a request from an honest client that has executed an operation in another fork set. At worst, r may execute the first request a client executes in a different fork set—hence achieving the join at most once property.

On the other hand, if r does a state transfer, this requires 2f+1 other replicas to vouch for r's new state. At least one of those 2f+1 replicas—call it u—must also be honest and in r's fork set. Since u is honest, it ensures that any operations r skips executing because of the state transfer do not violate fork* consistency.

5.5. An Example