{'fraction_non_alphanumeric': 0.03560748527915652, 'fraction_numerical': 0.010111909239448777, 'mean_word_length': 4.823927224848884, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Reaching Consensus in the Byzantine Empire: A Comprehensive Review of BFT Consensus Algorithms

Byzantine fault-tolerant (BFT) consensus algorithms are at the core of providing safety and liveness guarantees for distributed systems that must operate in the presence of arbitrary failures. Recently, numerous new BFT algorithms have been proposed, not least due to the traction blockchain technologies have garnered in the search for consensus solutions that offer high throughput, low latency, and robust system designs. In this paper, we conduct a systematic survey of selected and distinguished BFT algorithms that have received extensive attention in academia and industry alike. We perform a qualitative comparison among all algorithms we review considering message and time complexities. Furthermore, we decompose each consensus algorithm into its constituent subprotocols for replication and view change backed by intuitive figures to illustrate the message-passing pattern. We also elaborate on the strengths and weaknesses of each algorithm as compared to the state-of-the-art approaches.


INTRODUCTION
Byzantine fault-tolerant (BFT) consensus algorithms, which coordinate server actions under Byzantine (arbitrary) failures, have been extensively studied due to the burgeoning development of blockchain applications [58,61]. Since BFT algorithms tolerate arbitrary faults (i.e., the behavior of faulty servers (processes) is not constrained [85]), they have long been used in safety critical systems (e.g., aircraft [90,96] and submarines [95]) where hardware may become unreliable in hostile environments (e.g., extreme weather and radiation). Recently, driven by the rising interest in blockchain technology, BFT algorithms are widely deployed in numerous blockchain platforms to provide decentralized solutions that engender trust without relying on a third party, supporting cryptocurrencies [73], supply chains [40,81], international trade platforms [25], and Internet of Things (IoT) [34]. In these applications, BFT algorithms are quintessential in providing correctness guarantees for consensus as malicious behaviour is becoming the norm [3,16,31,46,47,92].
Depending on whether a designated server is used as a primary (a.k.a. leader), BFT algorithms can be generally categorized into leader-based and leaderless classes. After PBFT [24] pioneered a practical solution for BFT consensus, numerous approaches have proposed extensions and optimizations to improve system performance. These optimizations often handle normal and worst cases separately, following the recommendation of Lampson's famous doctrine: "the normal case must be fast, and the worst case must make some progress [63]. " In particular, some efficient leaderbased BFT algorithms target performance in achieving high throughput and low latency in fail-free operations [17, 24, 44, 47, 49, 52, 55, 64-66, 69, 80, 98-100]. They select a primary to coordinate and conduct consensus for committing and executing client requests, avoiding conflicts and achieving consensus with low message and time complexities.
Moreover, robust leader-based BFT algorithms [2,5,27,94] focus on defending against various potential failures instead of achieving impressive performance in fail-free operations. Byzantine faulty servers can behave arbitrarily; for example, they may deliberately send erroneous messages, • It comprehensively describes each algorithm in terms of normal operation and failure cases with intuitive figures illustrating message-passing workflows and discusses the strengths and weaknesses.
The remainder of this paper is organized as follows: Section 2 summarizes commonly used concepts and system properties; Section 3 describes leader-based BFT algorithms that target efficiency and achieve high performance in failure-free operations; Section 4 surveys leader-based BFT algorithms that fortify robustness and improve system availability and reliability in the presence of failures; and Section 5 presents leaderless BFT algorithms with their replication schemes and conflict resolution mechanisms.

BACKGROUND AND SYSTEM MODELS
This section introduces commonly used system models and assumptions in BFT consensus algorithms, including state-machine replication, fault tolerance with quorum certificates, network assumptions, complexity measurement, and correctness specifications.

Consensus and state machine replication
The consensus discussion often relates to state machine replication (SMR) in distributed systems [67,75,76,85]. State machines model an array of server replicas operating coherently in providing one or more services to clients. These services are able to operate correctly even if some of their replicas are faulty. A state machine consists of state variables and commands, which represent states and state transitions, respectively [85].

Fault tolerance
In the context of SMR, Byzantine failures model the behaviour of servers to exhibit arbitrary behavior, including the collusion among servers [62], software bugs, and unintentional as well as intentional malicious behaviour. Specifically, Byzantine servers can arbitrarily change message content and new states [4]. This type of failure differs from fail-stop failures [84] (or benign failures [59,60,74]), where the message content is immutable and the change of the state of faulty servers is constrained and detectable.
In the presence of failures, consensus algorithms often rely on quorum certificates [42] to implement their replication protocols. A quorum certificate is a set of identical messages collected from different replicas (a.k.a. participants). The minimum quorum sizes to tolerate benign failures (e.g., Paxos [59] and Raft [74]) and Byzantine failures (e.g., PBFT [24] and HotStuff [98]) are + 1 and 2 + 1, respectively.
Pompe relies on its underlying consensus algorithm to achieve full consensus. We use X to represent the complexity of its underlying consensus algorithm.
‡ Aardvark invokes a view change if an incumbent leader fails to achieve the expected throughput; thus, Aardvark may undergo more than view changes ( > 1) under faulty leaders. * DBFT, HoneyBadgerBFT and BEAT family use the binary Byzantine protocol, the message complexity of which is denoted by | |.

Complexity measures
The message complexity of a consensus algorithm is the total number of messages sent. For example, in an -server cluster whose communication topology is a complete (fully connected) graph, if a server broadcasts a message for rounds, the message complexity is ( ); if every server broadcasts a message for rounds, the message complexity is ( 2 ). In addition to message complexity, time complexity is also commonly used to measure the efficiency of consensus algorithms. The time complexity for an execution of consensus is the number of message-passing rounds until the execution terminates [6]. For example, if server sends a message to server , and then replies to , the time complexity is 2. When the network is asynchronous, measuring time complexity requires a finite delay time for message transmission [78].
Reaching Consensus in the Byzantine Empire: A Comprehensive Review of BFT Consensus Algorithms 5

Service properties
Consensus algorithms coordinate server actions and provide correctness guarantees. In particular, an -resilient BFT consensus algorithm needs to meet three criteria: termination, agreement, and validity [62,77].
Termination. Every non-faulty server eventually decides on a value. Agreement. Non-faulty servers do not decide on conflicting values; i.e., no two non-faulty servers decide differently. Validity. If all servers have the same input, then any value decided by a non-faulty server must be that common input.
The correctness guarantee can also be interpreted by safety and liveness [57,83]. Safety. No two non-faulty replicas agree differently on a total order for the execution of requests despite failures. Liveness. An execution will terminate if its input is correct.
The safety property ensures that something will not happen: correct replicas agree on the same total order for the execution of requests in the presence of failures. The liveness property, however, guarantees that something must happen: an execution eventually terminates if its input is correct; in the context of SMR, clients eventually receive replies to their requests.

LEADER-BASED BFT ALGORITHMS: THE EFFICIENCY SQUAD
Leader-based BFT algorithms have been favored in backing permissioned blockchain platforms, such as HyperLedger [3], R3 Corda [16], CCF [87], and Diem [31], due to their efficient consensus processes. The consensus process operates through a succession of system configurations called views with a common pattern rendered in two protocols: the replication protocol and view-change protocol. When a view has a correct primary, the replication protocol coordinates all non-faulty replicas to agree on a total order for the execution of requests. If the primary fails, the system enters the view-change protocol to select a new primary from the remaining replicas. Then, the system resumes normal operation under the leadership of the primary in the new view.

PBFT: Practical Byzantine fault tolerance
3.1.1 System model and service properties. PBFT pioneered a practical solution that achieves consensus in the presence of Byzantine faults. PBFT guarantees safety when there are at most faulty replicas out of a total of = 3 + 1 replicas; the safety guarantee does not rely on any assumption of network synchrony; i.e., safety is provided in asynchronous networks. However, PBFT requires synchrony with bounded message delays to guarantee liveness. The replication protocol operates through a progression of views numbered with consecutive integers. The viewchange protocol first selects a replica as a primary in a view, and the other replicas assume a backup role. The parameters of all messages involved in the replication and view-change protocols are presented in Table 2. 3.1.2 The replication protocol. The consensus in replication consists of an array of linearizable consensus instances for each client request. In each consensus instance, replicas make predicates for the primary's instructions in each phase based on quorums that include votes from 2 + 1 different replicas. The replication also uses checkpoints to periodically confirm that the requests committed by terminated consensus instances have been successfully executed.
Specifically, a consensus stance starts when a client invokes an operation to a primary. As illustrated in Figure 1a, a client requests to invoke an operation (op) on the primary, which starts the first phase in replication, the request phase. This operation invokes a PBFT service, such as  an invocation to propose or query a value (i.e., a write or read), and each operation has a unique timestamp. After sending a reqest message, the client starts a timer, waiting for the completion of the requesting operation: if the client receives + 1 reply messages from different replicas, the client considers the operation to be completed and stops the timer. However, if the client cannot receive a sufficient number of replies before the timer expires, this implies that the invocation of the requesting operation may have failed. This failure can be caused by internal faults (e.g., the primary failed) and external faults (e.g., the request failed to be delivered to the primary). Clients cannot deal with the former faults and must simply wait for the system to recover. However, the latter faults can be handled by a different messaging scheme; if a client's timer expires, the client resends the request message by broadcasting it to all replicas. Replicas that receive such a request transmit it to the primary. Although this scheme increases the messaging complexity of the request phase from (1) to ( ), it allows the client to invoke operations when the link between the client and primary is not reliable.
After receiving a request, the primary starts to conduct consensus among replicas to commit the request. The consensus starts with the pre-prepare phase in which the primary assigns a unique sequence number to the request. The sequence number is chosen from the range of ℎ to ℎ + , where ℎ is the sequence number of the last stable checkpoint, and is a predefined value used to limit the growth of sequence numbers. The limited growth prevents a faulty primary from exhausting the space of the sequence numbers. Then, the primary assembles the current view number, sequence number, and digest of the request message into a pre-prepare message and signs it; the pre-prepare message also piggybacks the original request received from the client, and the primary sends the message to all backups.
Next, the process enters the prepare phase. After receiving the pre-prepare message, backups 1 ○ verify the signature, 2 ○ check that they are in the same view as the primary, 3 ○ confirm that the sequence number has not been assigned to other requests, and 4 ○ compute the digest of the piggybacked request to ensure the digests match. If the message is valid, backups proceed by broadcasting prepare messages to all replicas. Then, a backup collects prepare messages from the other backups. If the backup receives 2 prepare messages from different backups, the backup makes a predicate that the request is prepared. The predicate is supported by a quorum certificate consisting of 2 + 1 agreements (including itself) of the same order from different replicas. Since there are at most faulty replicas among the total of = 3 + 1 replicas, the combination of pre-prepare and prepare phases ensures that non-faulty replicas have reached an agreement on the order of the request in the same view.
After the prepared predicate is made, the replica informs the other replicas about the predicate in the commit phase by broadcasting a commit message. Similar to the previous phase, replicas make a predicate of the request as committed when 2 commit messages have been received from different replicas; the redundancy forms a quorum certificate that 2 + 1 replicas have committed the same request in the agreed order. The quorum certificate also guarantees a weak certificate, which supports a committed-local predicate that + 1 replicas have committed the request. By the end of the commit phase, the quorum certificate provides the safety property: no two correct replicas execute the request differently. Finally, when predicate committed is valid, a backup starts the reply phase and sends the client a reply message with a Boolean variable (resultOfOp=true), indicating that the consensus for committing the proposed request is reached. The client waits for a weak certificate to confirm the result; that is, it waits for + 1 replies with valid signatures from different replicas.
Once a request is committed, the execution of the request reflects a replica's state. The replica must show the correctness of its states when sharing them with other replicas. Instead of generating proofs for every execution, the algorithm periodically computes proofs for an array of executions, namely checkpoints, as a way to show states. To produce checkpoints, a replica broadcasts a checkpoint message. If 2 + 1 checkpoint messages are collected, the proof of the checkpoint is formed, and the checkpoint becomes a stable checkpoint. The sequence number of the stable checkpoint is denoted by ℎ as a low water mark. A high water mark is = ℎ + where is a sufficiently large predefined number. The low and high water marks bound the growth of sequence numbers, as introduced in the pre-prepare phase. After obtaining a stable checkpoint, the intermediate log entries for creating previous quorum certificates can be discarded. The incremental computation of checkpoints can clean log entries appended at a previous checkpoint. Thus, this progressive oblivation of stale log entries achieves garbage collection and reduces space overhead.

3.1.3
The view-change protocol. When a primary fails, the coordination of consensus is impeded, which puts liveness in jeopardy. PBFT handles primary failures by its view-change protocol, and the ability to progress in the succession of views underpins liveness. Specifically, if the primary of view fails, the algorithm proceeds to view + 1 and selects a new primary such that = ( + 1) mod . During a view change, replicas may have various replication states because replication works in an asynchronous premise; i.e., replicas may be not fully synchronized. Thus, this variety produces many tricky corner cases that are difficult to handle, bringing challenges to design and implementation. PBFT has different view-change protocols presented in the literature [22][23][24]. We summarize the version in [23], which improves the version presented in [24] but may require unbounded spaces.
A view change process has three phases (shown in Figure 1b). In view , initially, a backup starts a timer after receiving a valid request if the timer is not running at the moment. Then, the backup starts to wait for the request to be committed. The request can be received from the primary or clients. The backup stops its timer when the request is committed but restarts the timer if there are outstanding valid requests that have not been committed. If its timer expires, the backup considers the primary failed and prepares to enter view + 1 by starting the view-change phase. It broadcasts a view-change message, where newView = + 1 and the sequence number is the latest stable checkpoint; C, P, and Q are indicators of the replication progress in view : C contains the sequence number and digests of each checkpoint, and P and Q store information about requests that have prepared and pre-prepared between the low and high water marks, respectively.
After receiving a view-change message, a replica verifies the message such that P and Q are produced in views that are less than . Then, the replica sends a view-change-ack message to the primary of view + 1. The ack message contains the current replica ID, the digest and the sender of the received view-change message. The primary of view + 1 keeps collecting view-change and view-change-ack messages. After receiving 2 − 1 view-change-ack messages that acknowledge a backup 's view-change message, the primary adds this view-change message to a set S and thus a quorum certificate, called view-change certificate, is formed.
Next, the new primary pairs the replica ID and its view-change message in S to a set V and selects the highest checkpoint, ℎ, that is included in at least + 1 messages in S. The primary extracts requests whose sequence numbers are between ℎ and ℎ + and have been prepared in view or pre-prepared by a quorum certificate and adds these requests into a set X. Sets V and X allow requests that are uncommitted but seen by a quorum in the previous view to be processed in the new view.
Finally, backups check if the messages in V and X support the new primary's decision of choosing checkpoints and the continuance of uncommitted requests. If not, the replicas start a new view, moving to view + 2. Otherwise, the new primary's legitimacy is confirmed while the view-change protocol terminates and normal operation resumes.
3.1.4 Discussion. PBFT pioneered a practical solution for Byzantine fault tolerance in asynchronous networks and made a significant impact by starting an era of efficient BFT algorithms. The extended version of PBFT [23] also provided a proactive recovery approach to recover faulty replicas. PBFT was adopted by many permissioned blockchains, though it was not designed to cope with a large number of failures. Numerous works are inspired by PBFT to obtain higher throughput and lower latency consensus (e.g., BFT-SMaRt [13], SBFT [45], HotStuff [98], and Prosecutor [99]).
However, PBFT's quadratic messaging complexity hinders it from building applications at large scales [15,93]. Furthermore, the client interaction may lead the system to repeated view changes without making progress if faulty clients use an inconsistent authenticator on requests [27].

Zyzzyva: Speculative Byzantine fault tolerance
3.2.1 System model and service properties. Zyzzyva [52][53][54] is a leader-based BFT algorithm that uses speculative executions to reduce communication costs under normal operation. Similar to PBFT [24], Zyzzyva has a replication protocol and a view-change protocol and tolerates Byzantine faulty replicas with 3 + 1 servers in total. Chiefly, instead of reaching consensus among replicas before replying to clients, Zyzzyva allows clients to collect tentative results before consensus is reached. Clients can speculatively complete a request in a fast track if all replicas reply with matching/correct execution results. The speculative execution reduces message complexity from quadratic to linear in the fast track. Table 3 illustrates the messaging formats in Zyzzyva.

3.2.2
The replication protocol. Under normal operation, Zyzzyva's replication protocol operates in two phases: speculative execution and commit (shown in Figure 2a). A speculative execution starts when a client sends a reqest to the primary. The client starts a timer, waiting for specresponse messages from replicas. The primary then assigns a sequence number for the request and broadcasts an order-req message that contains a digest and a history of the request to other replicas. After receiving the order-req message, a replica speculatively executes the operation (op) in the request and directly replies with a spec-response message to the client with the execution   result. At the end of this phase, if 3 + 1 responses are collected, which means the request has been correctly executed in all servers, the client adopts a fast agreement without notifying replicas. In this case, replicas are not aware of the client's decision, and thus they must preserve the sequence number and the history of executed requests until the next view change. Moreover, if 2 + 1 responses cannot be collected before the timer expires, which suggests that the primary may have failed, the client resends the request to all replicas, and correct replicas then forward it to the primary. In addition, if some non-primary replicas are faulty, a client may receive 2 + 1 to 3 responses. In this case, a client starts a commit phase by setting a second timer and broadcasting a commit message that piggybacks a commit certificate containing all matching responses (i.e., 2 + 1 signed spec-response messages from different replicas). Replicas then store the certificate and send a local commit message to the client. If the client receives 2 + 1 local commit messages before its timer expires, the client completes the request. At this time, the commit certificate is stored in at least + 1 correct servers. If the client fails to collect sufficient local commits, it resends the request to other replicas so that a view change can be initiated when a request execution cannot be finished in time.

3.2.3
The view-change protocol. Since Zyzzyva introduces speculative execution to achieve fast agreements, compared with PBFT [24], Zyzzyva's view-change protocol is more fine-grained with a phase of no-confidence votes (Figure 2b). A view change can be triggered in two ways: a client can 1 ○ disclose a proof of misbehavior (POM) targeting the primary, or 2 ○ complain to other replicas triggering timeouts to detect the anomaly of the primary. A POM message consists of a view number and a pair of order-req messages received by the client; the order-req messages have the identical view number and digest of results but different sequence numbers or history.  Once a replica receives a POM message or its timer triggers a timeout, it initiates a view change and sends out a no-confidence vote (I-hate-the-primary message) to other replicas. Note that in PBFT, replicas remain silence after sending out a view-change message, but in Zyzzyva, replicas still participate in replication in the current view during the no-confidence vote phase until they have collected enough votes for this view change. This design guarantees that potential view changes will not stop replication when a primary failure has not yet been confirmed.

SBFT Normal operation
When a replica receives + 1 no-confidence votes, it starts a view-change phase by broadcasting a view-change message that contains the new view number ( + 1), the latest sequence number, C, CC and O, where C is the most recent commit certificate, CC is the proof of the last stable checkpoint including at least 2 + 1 checkpoint messages, and O is the history of the ordered requests after the last checkpoint.
Next, when the new primary of view + 1 collects 2 + 1 view-change messages, it sends out a new-view message to all replicas, where P is the set of the 2 + 1 collected view-change messages, and G is the set of the history of commit certificates and ordered requests computed by the new primary based on collected view-change messages.
Finally, a replica broadcasts a view-confirm message and expects to receive 2 +1 view-confirm messages (including its own) at the end of this phase. The confirmation indicates that the replica has received the new-view message and will operate in the next view. Note that this phase is not mandatory for guaranteeing safety; nevertheless, it indicates that all correct replicas have agreed on the history of the last view, which simplifies the safety proof.

Discussion.
Zyzzyva reduces the messaging cost in replication by using speculative executions. The fast-track and two-phase design of Zyzzyva inspired many linear-cost BFT protocols, such as 700BFT [44] and SBFT [45]. However, the correctness of the protocol is not formally proved, and later studies show that the safety property can be violated [1]: a Byzantine primary can provide inconsistent commit certificates during different view-change phases, which lead to conflicting logs among different views.

SBFT: A scalable and decentralized trust infrastructure
3.3.1 System model and service properties. SBFT [45] is a leader-based BFT consensus algorithm that tolerates Byzantine servers and crashed or straggler servers using 3 + 2 + 1 servers in total. Similar to Zyzzyva [52], SBFT enables a fast path for achieving consensus if no failure occurs and the network is synchronous. Otherwise, SBFT can seamlessly switch to a slow path, namely linear-PBFT, featuring a dual model without engaging view changes. Compared with PBFT [24], SBFT avoids the quadratic Byzantine broadcast (i.e., -to-messaging) by utilizing threshold signatures; threshold signatures can convert an array of signed messages into one threshold signed message where a threshold indicates the number of signers. By utilizing threshold signatures, under normal operation, SBFT achieves linear consensus with a message transmission cost of ( ).

The replication protocol.
SBFT uses different servers acting as "local" primaries in different phases, amortizing the coordination workload among a group of selected collectors. In particular, as shown in Figure 3a, SBFT delineates three key phases under normal operation; in each phase, messages are broadcast and collected by a single server. The fast path mode of SBFT, in which the network is synchronous and no servers fail, makes use of this messaging scheme to achieve fast consensus.
Fast path. First, in the pre-prepare phase, the primary manages the order of transactions proposed by clients and broadcasts instructions to all other servers. Then, after receiving the instruction from the primary, servers validate the primary's message and prepare a reply message; instead of replying to the primary, servers send the reply message to the commit collector (Ccollector). Next, in the full-commit-proof phase, the C-collector takes the primary responsibility by collecting signed replies, converting them into one threshold signed message, and broadcasting the message to all other servers. Finally, in the full-execute-proof phase, the leadership duty is assigned to the execution collector (E-collector). The E-collector collects replies, aggregates them into one threshold signed message, and disseminates them to the others including the proposing client. Compared with PBFT, whose clients confirm the commit of a proposed transaction based on + 1 messages, SBFT sends only one confirm message to a proposing client. linear-PBFT. In contrast to the fast path mode, under the presence of failures or partial synchrony, SBFT switches to the linear-PBFT mode. In this mode, regardless of , there are at most 2 collectors or all collector roles are aggregated to the primary. The reason this model is called linear-PBFT is that if SBFT uses only the primary as all "local" leaders in each phase, the workflow becomes similar to PBFT [24]. Nonetheless, the messaging complexity is reduced from ( 2 ) to ( ), as each server receives an (1) threshold signed message in the linear-PBFT mode. In a given view, SBFT selects a primary as based on the view number and chooses collectors based on the commit state index (sequence number) and the view number. SBFT suggests to randomly select a primary and collectors to increase robustness, though the design and implementation are unprovided. In the linear-PBFT mode, the primary is always chosen as the last collector. The transition of server roles is initiated by view changes, which select a new set of a primary and collectors when the current primary is faulty.

3.3.3
The view-change protocol. SBFT's view change mechanism has a message transmission complexity of ( 2 ). Figure 3b shows the workflow proceeding to a new view. A view change is initiated when a replica triggers a timeout or receives a proof that the primary is faulty ( + 1 replicas suspect the primary is faulty). This begins the view change trigger phase, and in the worst case, all servers trigger new views, resulting in an ( 2 ) message transmission. Then, in the view-change phase, each replica maintains the last stable sequence number, denoted by . Since the network can be partially synchronous, concurrent in-process consensus may lead to discrepant among servers; SBFT limits the number of outstanding blocks by a predefined parameter, denoted by ; thus, a sequence number lies between and + . The sequence number indicates a server's state, and the servers that have triggered a view change send the new primary a viewchange message consisting of and digests of corresponding states from to + . After the new primary solicits a set of 2 + 2 + 1 view-change messages, denoted by I, in the new-view phase, it initiates a new view and broadcasts I to all other servers. Then, in the accepting a new-view phase, servers accept the values indexed from slot to + or adopt a safe value, a symbol that the corresponding sequence number can be used for a future transaction as its index in the new view.   reduces client communication from ( + 1) to (1) since E-collectors aggregate server replies in the full-execute-proof phase. However, SBFT inherits some weaknesses from PBFT [27]. Faulty clients can trigger unnecessary view changes if they only partially communicate with + 1 replicas. In SBFT, a view change is triggered if + 1 replicas complain; faulty clients can take advantage of this feature by sending transactions to a set of + 1 replicas excluding the primary. After the + 1 replicas trigger timeout, a view change is initiated to replace to the correct primary, invoking unnecessary leadership changes.

HotStuff: BFT consensus in the lens of blockchain
3.4.1 System model and service properties. HotStuff [98] is a leader-based BFT consensus algorithm that tolerates up to Byzantine servers using a total of 3 + 1 servers. It assumes a partially synchronous network to achieve liveness, whereas safety does not rely on any assumption of network synchrony. HotStuff guarantees optimistic responsiveness; i.e., a consensus decision requires only the first 2 + 1 messages to make progress. Inspired by the design of rotating primaries (leaders) in permissionless BFT networks [18,38,43], HotStuff rotates primary servers for each consensus instance to ensure chain quality [41]. Similar to SBFT [45], HotStuff uses threshold signatures to obtain consensus linearity (i.e., ( ) messaging complexity) under normal operation, reducing the communication overhead of Byzantine broadcasts that reach consensus by -tomessaging in PBFT [24]. However, in the worst case of cascading failed primaries, HotStuff takes up to ( * ) rounds to reach consensus, on the order of ( 2 ).

The replication protocol.
A replication process starts when a client broadcasts a request to invoke an operation to all replicas (shown in Figure 4). Similar to PBFT [24], the client waits for replies from + 1 replicas to confirm that an invoked operation is executed. HotStuff does not further discuss the handling of client failures but references standard literature regarding handling numbering and de-duplication of client requests [13,24].
HotStuff operates in the succession of views. Under normal operation, a consensus process has four phases (shown in Figure 4). After receiving a client request, the primary broadcasts a prepare message to all replicas. A replica verifies the message based on two criteria: 1 ○ the message extends from a previously committed message (they are continuous with no other messages in between), and 2 ○ it has higher view number (viewNum) than the current view number. If the message is verified, the replica signs a prepare-vote message by its partial signature and sends the vote back to the primary. The primary waits for 2 + 1 votes to form a quorum certificate (QC) for the prepare phase, denoted by prepareQC. After a prepareQC is formed, the primary starts a pre-commit phase by broadcasting a message with the prepareQC. All replicas store a received prepareQC in this phase and send a commit-vote message signed by their partial signatures back to the primary. When the primary receives 2 + 1 votes, it forms a pre-commitQC for this pre-commit phase. Then, it starts a commit phase by broadcasting messages with pre-commitQC to all replicas. Replicas reply to the primary with a commit vote and update a local variable, denoted by lockedQC, that keeps counting the number of received QCs for a request. When the primary receives 2 + 1 commit votes, it broadcasts a decide message to all replicas. Replicas consider the consensus of the current client request to be reached and then execute the operation in the request. Replicas then increment the viewNum and send a new new-view message to the new primary. Replicas also send a confirmation to the proposing client, indicating that the request is locally executed. The client waits for + 1 messages to confirm that its proposed request is executed.
Throughout a consensus process, each replica stores three key variables to reach consensus for a client request: prepareQC, the highest locked prepare message that a replica knows; lockedQC, the highest locked commit message that a replica knows; and viewNum, the current round the replica is in, updated with each new-view.
Unlike PBFT [24] and other leader-based protocols that maintain a stable leadership [13,45,52,99], HotStuff rotates leadership for each consensus instance. Each consensus instance, identified by a monotonically increasing viewNum, begins with a new-view message with viewNum and references to the highest quorum certificate from the most recent prepare round, prepareQC. The primary for the next round collects 2 + 1 new-view messages to identify the highest preceding view that it extends from, based on collected prepareQCs. If the new primary cannot collect a new-view message from 2 + 1 in time, the other replicas will trigger timeouts and initiate a view change that rotates the primary role to the next server.

The view-change protocol.
With the motivation of ensuring chain quality [41] for blockchain applications, HotStuff enables frequent view changes compared to state-of-the-art leader-based protocols [24,45,52,99]. Each consensus instance starts with a new primary that conducts consensus by broadcasting coordination messages and collecting threshold signatures. As a result, the view change is engraved at the core of the HotStuff protocol. HotStuff adopts PBFT's leadership rotation scheme where a new primary in a view is decided such that = mod where is the number of total servers. In addition, a broad range of strategies could be used for rotating primaries in each phase, ranging from randomness to reputation-based selection. For instance, LibraBFT [10], HotStuff's implementation in the Libra blockchain, uses round-robin leadership selection among all replicas to choose a primary.
3.4.4 Discussion. By utilizing threshold signatures, HotStuff achieves linear message transmission for reaching consensus. In each phase, the primary collects votes and builds threshold signatures that can be pipelined; pipelining of decisions can further simplify the protocol for building chained HotStuff, similar to Casper [18], and reduces the time complexity in reaching consensus. Furthermore, HotStuff can be extended to permissionless blockchains using delay towers (e.g., [72]).
However, HotStuff's frequent leadership rotation becomes problematic in the presence of failures. Since each server conducts a consensus instance for client requests, under failed servers, HotStuff's throughput drops significantly because the failed servers cannot achieve consensus when they are assigned with primary duties [99].

Pompe: Byzantine ordered consensus without Byzantine oligarchy
Pompē [100] is an ordering protocol built on top of standard consensus algorithms (e.g., SBFT [45] and HotStuff [98]). It prevents Byzantine replicas from dictating the order of commands by democratically collecting preferred orders from a quorum of replicas. After an order of a command is decided, Pompē relies on an applied consensus algorithm to perform consensus for a batch of ordered commands in a periodic manner. 3.5.1 System model and service properties. Pompē tolerates faulty replicas out of a total of 3 + 1 replicas. It has a unique service property that can address the ordering of operations/commands since the ordering of operations can have significant financial implications [30]. In addition to the traditional specification of BFT SMR correctness (i.e., safety and liveness), Pompē introduces a new property: Byzantine ordered consensus. This property assigns each operation with an ordering indicator, which shows a replica's preference to order the operation. By coordinating indicators, Pompē avoids the ordering manipulation of operations against Byzantine replicas (i.e., Byzantine oligarchy) that disrespect the ordering indicators from correct replicas. For example, although it can ensure safety and liveness, a Byzantine primary can always deliberately put requests from client before requests from client when their requests invoke the same operation.

3.5.2
The replication protocol. Pompē has two phases in the replication protocol: 1 ○ the ordering phase and 2 ○ consensus phase. The ordering phase aims to secure a democratic order of a proposed request. Unlike traditional BFT algorithms, in which the order is single-handedly decided by the primary, in Pompē, the order is a selection among 2 + 1 preferred orders from different replicas. Specifically, as shown in Figure 5, the ordering phase has two steps: the propose order and lock order steps. In the first step, a replica (say replica ), acting as a proposer, broadcasts a ReqestTS message in the format of ⟨ReqestTS, ⟩ to solicit preferred timestamps, which are used as the ordering indicator, for command from all other replicas. Then, a replica (say replica ) replies to the proposer with ⟨ResponseTS, , ⟩ , where is its preferred timestamp. After the first step, the proposer collects ResponseTS messages to a set T until a quorum is formed. Then, the second step starts; the proposer picks the median timestamp, denoted by , from T , and assigns as the order of the command. Next, the proposer broadcasts the order in the format of ⟨Seqence, , , ⟩ . Finally, replica verifies and accepts the received order if the received order should be higher than any previously accepted orders. If the received order is accepted, replica replies to the proposer with an acknowledgement in the format of ⟨SeqenceResponce, , ℎ⟩ ; otherwise, it replies ⟨SeqenceResponce, , ℎ⟩ , where ℎ is the cryptographic hash of the received Seqence message from the proposer. At the end of the ordering phase, Pompē obtains an order for a specific command such that the order is not manipulated by Byzantine oligarchy. Since there are at most Byzantine replicas, in a quorum with a size of 2 + 1, the median is the both upper-and lower-bounded timestamps from correct replicas.
Pompē relies on an applied consensus algorithm to obtain consensus for ordered commands. For example, if Pompē uses HotStuff [98] as its consensus algorithm, it periodically executes consensus in a predefined interval. During an interval, Pompē packs ordered commands into a batch, and the consensus phase is used to periodically commit a batch of commands. With the ordering and consensus phases, Pompē achieves Byzantine ordered consensus, which adds ordering fairness to linearizability. 3.5.4 Discussion. Pompē extends the traditional correctness discussion of BFT SMR from focusing only on safety and liveness to the ordering of operations. This new property may have a significant impact when the BFT SMR service is used in financial applications [30]. In Pompē, the ordering of operations is democratically decided by a quorum of replicas instead of being determined by a single primary. Pompē separates consensus into two major phases as ordering and consensus and majorly discusses the ordering phase. Yet, Pompē does not design a specific consensus algorithm but uses any standard consensus algorithm to perform the second phase. However, since many consensus algorithms have meticulously designed view-change protocols, it is unclear how safety and/or liveness can be ensured when these consensus algorithms are applied to perform the ordering service. For example, PBFT's design allows valid cross-view requests to be committed; if PBFT applies to Pompē as a consensus algorithm, it may disable this feature because of potential safety violations.

LEADER-BASED BFT ALGORITHMS: THE ROBUSTNESS BAND
While efficient leader-based BFT algorithms are able to achieve high performance under normal operation, they may have sacrificed system robustness and become vulnerable under a diverse attack vector. This section introduces another category of leader-based consensus algorithms, namely robust BFT algorithms, that mark fault tolerance as the first priority, fortifying system robustness by defending diverse attacks under Byzantine failures. Each survey presents the robustness improvement in log replication and view changes such as performance monitoring [26], redundant executions [5], and misbehavior penalization [99]. Time and message complexities overhead are also discussed to show the cost of robustness improvements.

Aardvark: Making Byzantine fault tolerant systems tolerate Byzantine failures
Aardvark [26] aims to improve the robustness of BFT algorithms that achieve high performance in terms of throughput and latency when the system operates in gracious executions, such as PBFT [24], Zyzzyva [52], 700BFT [44], and Scrooge [86]. In gracious executions, the network is synchronous, and all clients and servers are correct. However, the aforementioned high-performance protocols are vulnerable during uncivil executions, in which the network latency is bounded and up to servers may become Byzantine faulty with unlimited Byzantine clients. In this case, a series of meticulously designed attacks can wreck the performance of these BFT algorithms, and the system availability decreases significantly (even down to zero). For example, when clients use an inconsistent authenticator on requests, PBFT [24] fails to make progress and can result in repeated view changes.

System model and service properties.
Aardvark uses the same fault-tolerance and network synchrony assumption as PBFT: it tolerates fault replicas out of a total of 3 + 1 replicas; it ensures safety in asynchrony but requires bounded message delay to obtain liveness. Aardvark argues that the first principle to design BFT algorithms should be the ability to tolerate Byzantine failures and defend malicious attacks; during uncivil executions, the performance degradation should remain at a reasonable degree. Aiming to improve BFT robustness, Aardvark's improvements are threefold: stronger message authentication (signed client requests), independent communication (resource isolation), and adaptive leadership rotation (regular view changes).

Robustness in log replication.
Aardvark requires clients to use digital signatures to authenticate their requests. Unlike the message format of PBFT in Table 2, a client request is specifically authenticated between the requesting client (denoted by ) and the receiving replica (denoted by ). It has the format of ⟨⟨reqest, , , ⟩ , ⟩ , , where the operation and timestamp are signed by signature ; the signed message is then authenticated by a MAC (message authentication code) , for recipient . In addition, Aardvark requires the communication among replicas to use separate network interface controllers (NICs) and wires (shown in Figure 6). This separation enables a more secure communication channel, reducing interference from faulty servers. Replicas also separate message queues for receiving requests from external clients and internal replicas. The isolation of message queues prevents replicas from being overwhelmed by a spike of client requests.
The workflow of the replication protocol of Aardvark is similar to that of PBFT. However, with signed client requests and resource isolation, Aardvark takes more steps to verify both client and replica messages, aiming to reduce the potential impairment from faulty clients and replicas. To verify a client message, a replica, in the request phase, checks that 1 ○ the client is not blacklisted; 2 ○ the authentication MAC ( , ) is valid; 3 ○ the timestamp is incremented by one as the previously received one; and 4 ○ the request has not been processed. Then, 5 ○ the replica verifies signature ; if is invalid, the replica blacklists this client. Finally, if the request is verified in a previous view but not processed, 6 ○ the replica continues the replication protocol, which allows the system to commit cross-view requests.
Messages circulated between two replicas also undergo a checklist process. In particular, when replica receives a message from replica , replica 1 ○ takes a volume check: if replica sends more messages than expected, replica blacklists replica . Then, replica 2 ○ picks received messages to process consensus in a round-robin manner and discards incoming messages if buffers are full. Next, replica 3 ○ verifies the message's MAC, 4 ○ processes the message according to its type, and 5 ○ adds it to the corresponding quorum. After a complete quorum (with a size of 2 + 1) is formed, the consensus process continues. If replica is not processing any messages for forming consensus (i.e., in the idle mode), replica 6 ○ starts to process catchup messages from other servers in the recovery mode.

Robustness in view changes.
In PBFT, a primary is considered to be correct if consensus can be achieved in time; i.e., backups commit a proposed request before their timers expire. This primary may stay in this position forever and dominate the replication phase. This scenario may result in low performance if the primary deliberately slows the process of leading the consensus or colludes with faulty clients. Although Aardvark utilizes the same view-change protocol as PBFT [24] (shown in Figure 1b), to prevent any replica from dictating the replication process, Aardvark imposes two expectations on a correct primary: 1 ○ sufficiently and timely issuing Pre-prepare messages and 2 ○ maintaining sustained throughput. If the primary fails either of the two expectations, Aardvark imposes view changes regardless of the primary's correctness. The former expectation requires the primary to timely and fairly process client requests. Aardvark manages Pre-prepare messages as heartbeats between the primary and backups. A backup starts a timer in a view, say view , and resets it upon receiving a valid Pre-prepare message from the primary; otherwise, the timer keeps counting down. Thus, if the primary cannot issue Pre-prepare messages in time, the backup's timer expires; the backup considers the primary to be faulty and invokes a view change to enter view + 1. In addition, backups require fairness of client request ordering. A backup monitors a client request if the request has not been pre-prepared and relays it to the primary. If the primary cannot issue Pre-prepare for this request after another two requests are pre-prepared, the backup considers the primary to be faulty as the primary's behavior is unfair, with a probability of trying to block requests from specific clients. Then, the backup initiates a view change to enter the next view.
The latter expectation is enforced by monitoring the primary's throughput over previous views. Aardvark uses periodic checkpoint messages to calculate a primary's averaged throughput. The primary of view is expected to maintain at least 90% of the maximum throughput achieved in its prior views. If the primary fails to accomplish this goal, backups consider the primary to be faulty and initiate a new view change to enter view + 1.

Discussion.
Aardvark addresses the robustness problem of PBFT-like consensus algorithms, especially focusing on tolerating faulty clients. The improvements made by Aardvark are generally focused on requiring signed client messages, isolating resources, and performing regular view changes; thus, compared with its baseline protocols, Aardvark obtains a lower throughput deduction during uncivil executions than during gracious executions. However, the strict expectations on a correct primary to maintain at least 90% of the throughput achieved in the last views may bring unnecessary burden on correct replicas and benefit a faulty primary [5]. When the workload increases, a faulty primary can block incoming client requests and select only 90% of them to process. This behavior may result in more severe performance degradation when the workload is dynamic. Additionally, since correct primaries can be mistakenly replaced with the system making no progress, Aardvark may impose unnecessary view changes, thereby impeding higher throughput performance.

Spin: Byzantine fault tolerance with a spinning primary
Spinning [94] addresses the problem of performance degradation in leader-based BFT algorithms under faulty leaders. PBFT [24] and its variants [13,26,52] use a stable primary to achieve consensus, and backups detect primary failures using timeouts. The primary remains unchanged as long as no failures are reported by backups. The timeout value is often set much larger than the expected completion time of a consensus instance (e.g., a timeout is set to 500 ms when consensus can be achieved within 50 ms). However, this stable leadership design is vulnerable to performance attacks where a faulty primary deliberately slows down transaction processing in a delay that does not trigger a backup timeout. To mitigate this problem, Spinning rotates primaries for each client request, which avoids leadership monopoly from specific replicas. Since faulty primaries can cause sustained performance degradation, it also uses a blacklist to prevent suspected faulty replicas from becoming a primary.

System model and service properties.
Spinning assumes a partially synchronous network for maintaining liveness while safety does not require network synchrony. Similar to the fault-tolerant model in PBFT [24], Spinning tolerates failures in a total of 3 + 1 replicas. In addition, standard public/private key encryption is used on messages.

Robustness in log replication.
Spinning's normal operation for a consensus instance follows PBFT's communication pattern that includes pre-prepare, prepare, and commit phases, with 2 + 1 commit messages needed for operation execution (shown in Figure 7a). Compared with PBFT, which changes a primary when it is suspected of being faulty, Spinning changes a primary whenever it defines the order of a batch of requests. For example, in Figure 7a, when a client broadcasts a request ( 1), replica 0 , the primary of view , starts a consensus instance for committing 1; when the client proposes another request ( 2), the consensus is conducted by the primary ( 1 ) of the next view, + 1. Since requests are handled in different views, Spinning does not need to assign sequence numbers to requests but uses the view number instead. After a client broadcasts a request, if a replica receives a pre-prepare message from the primary in view ′ > for current view , it buffers the message until view ′ becomes valid; is set when the replica receives at least + 1 prepare messages from distinct replicas with as the current view number. If a replica cannot receive enough prepare messages, it uses the last accepted view number . When the client receives + 1 replies from distinct replicas, it accepts the result in the reply.
Replicas use timeouts to limit the completion time of a consensus instance. If a replica cannot collect enough commit messages in time, it triggers a timeout and sends a merge message to all replicas. Unlike PBFT, the merge operation is not designed to change views; it aims to determine which requests from the previous view can be accepted and executed by merging information from all replicas and proceeding to a new view (shown in Figure 7b). The merge operation first begins when replicas trigger a timeout or have received + 1 merge messages from distinct replicas. A merge message contains a set, , that contains requests that a replica has received a pre-prepare message paired with 2 + 1 prepare messages. That is, set shows requests that have been prepared and can proceed with their commit operation in the next view. Next, after receiving 2 + 1 merge messages, the replica of the new view enters the pre-prepare merge phase ( 3 in Figure 7b). It broadcasts a pre-prepare-merge message that contains a vector of digests of requests received from valid sets. Finally, replicas change their state back to normal after a received pre-prepare-merge message is verified, and normal operation resumes.

Robustness in view changes.
Since leadership is rotated for each request, Spinning does not require an explicit view change protocol when a primary failure is detected. However, under faulty replicas in a total of = 3 +1 replicas, frequent leadership rotation can significantly decrease throughput, as no request can be committed under a faulty primary, with a drop in throughput of 33% in theory ( 3 +1 ). To mitigate this effect, Spinning uses a blacklist to exclude misbehaved replicas when assigning the primary role. The list has a maximum capacity of , where the oldest are removed if full, and is maintained by all correct replicas using pre-prepare-merge messages. When a faulty primary triggers a merge operation, the failure is confirmed when a pre-prepare-merge  message is sent in a view; replicas then put this faulty primary into the blacklist. Since a replica can be wrongly judged faulty because of network conditions, when the blacklist size exceeds , the oldest replica is removed in a FIFO manner. Replicas on the blacklist can still participate in consensus processes; they are excluded from the primary role only when leadership is rotated for handling new incoming client requests.

Conclusion.
Equipped with the leadership-rotation-per-request mechanism, compared with efficient BFT algorithms (in § 3), Spinning becomes more robust under malicious attacks targeting the primary replicas. Since it amortizes the coordination workload among all replicas, it also mitigates the performance bottleneck problem in algorithms that use only a single primary.
Nevertheless, leadership rotation incurs extra message-passing when failures do not occur on a primary. The merge operation has a message complexity of ( 2 ) and is triggered on every failed replica. This extra messaging cost has a negative impact on system performance whenever a replica fails in the system.

RBFT: Redundant Byzantine fault tolerance
4.3.1 System model and service properties. RBFT [5] suggests that some methods aiming to improve the robustness of fault tolerance, such as Prime, Aardvark, and Spin, leave the door open for performance degradation in numerous corner cases. These corner cases often target a primary, which may result in single points of failure, thereby reducing system performance. To tackle this challenge, RBFT introduces more redundancy in the consensus process: RBFT executes multiple instances of the PBFT protocol in parallel, and each replica plays the primary role in the corresponding instance. Among these parallelly executing instances, one instance assumes a master role and takes the primary duty to lead the consensus, whereas other instances assume a backup role to monitor the processing speed of the master, preventing the master from deliberately slowing down the consensus process. Similar to PBFT's failure assumption, RBFT tolerates faulty replicas out of a total of 3 + 1 replicas.

Robustness in replication.
The replication process has four major phases, the first of which is the request phase. In this phase, a client broadcasts a request to all replicas. In contrast to PBFT, RBFT requires clients to broadcast their requests to all replicas, even if the master replica is correct and responsive. After checking the signature of the request, replicas broadcast the request to all other replicas in the propagate phase. Since only out of 3 + 1 replicas are faulty, a correct replica is able to eventually receive at least + 1 propagate messages. Then, the replica starts its local instance of a PBFT consensus, which contains the pre-prepare, prepare, and commit subphases. Similar to the end of PBFT's commit phase, if 2 + 1 commit messages are collected from different replicas in the same instance, the replica in RBFT commits the request. Finally, the replica executes the request and sends a reply to the requesting client in the reply phase.
The redundancy of multiple concurrently running instances is used to monitor the master instance's processing speed to detect whether the master is faulty. Each instance sends periodic messages to inquire about the number of requests the other servers have processed and then calculates the average processing speed. If the master's processing speed falls below the average by a threshold (say ), the instance considers the master instance to be faulty and initiates instance changes (similar to view changes). Additionally, each instance tracks the processing time of each request's consensus and calculates the average latency for each client. If the processing time for some clients deviates from the average by a threshold (say ), the master instance is considered to be unfair in leading the consensus. Consequently, backup instances initiate instance changes to enter the next view.

Robustness in instance changes.
The instance-change protocol operates in a similar way as the view-change protocol in PBFT to replace a faulty primary. Each instance maintains a counter ; if the master instance does not satisfy the two thresholds (i.e., and ), a backup instance increments and broadcasts an instance-change message in the format of ⟨instance-change, , ⟩ , in which is the instance ID. After receiving this message, other instances check the currently monitored performance of the master instance if the received is not less than their own counters. If the performance does not satisfy the two threshold criteria, these instances support the instance change and broadcast their instance-change messages. Upon receiving 2 +1 instance-change messages with the same counter from different instances, a new master instance is selected, and the system enters the next view.

Discussion.
RBFT observes that some previously published robust BFT algorithms, such as Prime, Aardvark and Spin, have flaws in corner cases. These cases often target the primary and can result in dramatic throughput degradation. RBFT solves this problem by using multiple concurrently running instances to monitor the performance of the primary (master instance). However, RBFT introduces more operating costs owing to more redundancy; this imposes a massive additional messaging cost on the system compared with PBFT-like algorithms, the message complexity of which (in the order of ( 2 )) hinders them from being used in large-scale practical applications. Since each replica runs a PBFT-like instance after the propagate phase, to commit | | requests, the message complexity of RBFT is (| |( + 2 + ( + 2 + 2 ) + )) = (2| |( 3 + 2 + )). In addition, RBFT may still suffer from unnecessary view changes that mistakenly replace a correct master instance. In practice, especially in geo-distributed applications, the communication latency between clients and different replicas can be significantly different; when the difference causes a correct master to fail to meet the fairness requirement, backups replace the master by initiating unnecessary instance changes.  [99] assumes a partially synchronous network and tolerates Byzantine failures out of a total of 3 + 1 replicas. Compared with PBFT-like algorithms, Prosecutor has a different perspective on view changes: it allows server replicas to actively claim to be the new primary and transition to an intermediate state called candidate, as opposed to rotating leadership on a predefined schedule. To suppress Byzantine servers from being the primary, Prosecutor imposes computation penalties on candidates; the computation difficulty changes based on the candidate's past behavior. The more failures a candidate has exhibited, the greater computation penalty the candidate must incur for becoming the new primary.

The replication protocol.
Prosecutor efficiently replicates client requests, with a message complexity of ( ). Similar to HotStuff's replication protocol, Prosecutor utilizes threshold signatures to reduce the package size in primary-backup communication. Specifically, the replication process has five phases. First, the client broadcasts requests to all replicas. Then, the primary assigns an order to the request and sends it to all other replicas. Next, replicas verify the primary's message to ensure that the order has not been used for other requests. Then, replicas partially sign an endorsement and reply to the leader, indicating that they agree to commit the request in the assigned order. After collecting 2 + 1 replies from different replicas, the leader considers the request to be committed, announces to the client, and issues a commit instruction signed by its threshold signatures. Finally, replicas examine the commit instruction and announce to the client that the request has been locally committed.

The view-change protocol.
Prosecutor's view-change protocol, associated with computation penalties, is the most unique feature compared with those of other state-of-the-art BFT algorithms. Generally, a view-change process has two major steps: performing computations and voting (shown in Figure 9b). Specifically, if a backup's timer expires, the backup invokes an algorithm, similar to Proof-of-Work [73], to perform hash computations. 1 ○ The backup prepares a proof window that contains an array of values starting at the first uncommitted value and ending at the last committed value. Then, the backup combines its proof window with a randomly generated string called nonce. 2 ○ The backup computes the hash of the combination to obtain a hash result. Prosecutor imposes a threshold requirement for the result. The threshold is an integer that indicates the number of identical and consecutive bytes a hash result should prefix. 3 ○ If the hash result satisfies the threshold requirement, the algorithm terminates; otherwise, the backup repeatedly changes the nonce until obtaining a qualified result. After a qualified result is acquired, 4 ○ the backup becomes a candidate, broadcasts a VoteMe message including the new view number and hash result, starts a new timer, votes for itself, and waits for votes from the other replicas. If the candidate collects 2 votes before its timer expires, 5 ○ it becomes the new primary in the new view and broadcasts a New-View message including all collected votes, showing the legitimacy of becoming the new primary.
Replicas increment the threshold value of a requesting candidate after receiving its VoteMe message. Thus, the more requests a candidate has initiated, the more computation the candidate must perform for the next leadership competition. Moreover, replicas decrement a candidate's threshold if the candidate becomes the primary and successfully conducts consensus in a new view, where is a predefined parameter of the minimum number of expected transactions committed under correct leadership. Therefore, if a replica does not fulfil the primary duty after being elected, its threshold will not be decreased; this penalization regime entices replicas to operate correctly in order to avoid performing computation work.

Discussion.
Prosecutor penalizes suspected faulty replicas while achieving efficient consensus in terms of linear message complexity. If Byzantine servers launch attacks aiming to usurp correct leadership, they will be penalized and forced to perform exponentially growing computational work. Thus, Byzantine servers are gradually suppressed and marginalized from leadership competition. Compared with PBFT-like view change protocols, such as PBFT [24] and HotStuff [98], Prosecutor can avoid sustained performance degradation when faulty servers repeatedly launch attacks. However, the PoW-like penalization may become less efficient if faulty servers have a strong computation capability; in this case, Prosecutor may suffer from a long period without a correct leader before Byzantine servers exhaust their computation capability.

LEADERLESS BFT ALGORITHMS
Although leader-based algorithms operate efficiently under normal operation, they are vulnerable to single points of failure targeting the primary: the system must first detect a primary failure and then invoke a view-change protocol to select a new primary. In addition to this vulnerability, a primary server that interacts with both clients and servers often suffers from a heavy workload, which may become the system bottleneck. In contrast, this section discusses leaderless BFT algorithms that provide a different solution by amortizing the coordination workload among a group of or all server replicas. Compared with leader-based algorithms, leaderless algorithms can increase system availability and/or reliability, though the consensus process may involve a higher message complexity. Since leaderless consensus protocols are often less intuitive than leader-based protocols due to concurrent proposals and conflict resolution methods, each survey shows message-passing workflows and comprehensively describes the consensus process.

Preliminary fundamental models
Before delving into each algorithm, we introduce two fundamental building blocks that facilitate the design and implementation of leaderless BFT algorithms: the reliable broadcast (i.e., Bracha's RBC), introduced by Bracha et al. [14], and the binary Byzantine agreement (i.e., BA), introduced by Moustefaoui et al. [71].

Reliable broadcast.
This protocol is able to achieve agreement in asynchronous networks [14]. It contains four major steps (shown in Figure 10a).
(1) First, the primary (replica 2 ) proposes a value by broadcasting an initial message.
(2) When a replica (including the primary) receives the initial message, it broadcasts an echo message with . (3) A replica broadcasts a ready message with if it receives − echo messages with the same , or it receives + 1 ready messages with the same . (4) Finally, when a replica receives − ready messages with the same , it delivers .
In step 3, for a value , a replica broadcasts the ready message only once. For example, in 10b, after receiving three echo messages, replica 1 broadcasts a ready message; it does not broadcast twice at the ready phase. In contrast, 3 fails to collect − echo messages, so it must broadcast a ready message when it receives + 1 ready from the other replicas.
Bracha's RBC terminates at the end of its last phase. This guarantees that if the proposer is correct, then all correct processes deliverer 's proposed value, or if is faulty, then either all correct processes deliver the same value or none of them deliver 's proposed value.
5.1.2 Binary Byzantine agreement. Similar to the network assumption of Bracha's RBC, the binary Byzantine agreement protocol [71] operates in asynchronous networks despite failures. The protocol operates through a progression of rounds and terminates until a consensus is reached. Each round has three coordination phases aiming to deliver a value under the presence of Byzantine failures (shown in Figure 11a).   In Phase 1, each replica first increments its round number by one and then performs a two-step broadcast, denoted by BV-broadcast. Each replica first proposes an estimated value ( ), 0 or 1, and broadcasts the value with . Then, when a replica receives the same value as the current round number from + 1 replicas and this value has not yet been broadcast, the replica re-broadcasts the value (grey arrows in 11a). In this case, if a replica receives 2 + 1 messages with the same value , BV-broadcast considers this value to be delivered, and the replica stores this value to an array (i.e., bin_values in the original paper), where may contain multiple values.
In Phase 2, in order to commit values in , a replica broadcasts an aux message with if its is not empty. In addition, replicas can asynchronously execute this phase as long as is not empty, so an aux message can be broadcast before collects its final value.
In Phase 3, when a replica receives − aux messages, if (1) every message contains a single value and (2) ∈ (i.e., was delivered by BV-broadcast in Phase 1), the replica starts a coin-flip process to decide the final delivery of by the following three steps: (1) It uses a random number generator to obtain a coin-flip value ∈ 0, 1.
(2) If = , it delivers and sets = as an initial estimated value for the next round. (3) If ≠ , it sets the initial estimated value as the coin value; i.e., = for the next round.
Phase 3 does not involve message exchanges among replicas. Each replica decides the delivery (or abort) of the initial value of the current round and assigns the initial value for the next round. Figure 11b shows an example of replicas proposing conflicting values. In this case, replicas 1 and 2 propose value 0 (shown in solid lines), whereas 3 and 4 propose value 1 (in dash lines). After Phase 1, each replica receives three messages containing value 0 and three messages containing value 1 after the two steps of message passing. For instance, 1 receives two messages with = 1 24 G. Zhang et al.  (it receives two dash lines and thus re-broadcasts = 1) and another message with = 0 in the first step (one solid line). As a result, every replica has two values, 0 and 1, in its by the end of phase 1. After Phase 2, all aux messages of each replica contain two values; therefore, no replica can decide. They must flip their coins to calculate the values for a new round, so multiple rounds may be needed to reach a final agreement.
The BA protocol obtains validity and agreement; that is, a decided value is proposed by a correct replica (validity), and no two correct processes decide different values (agreement). Since each correct replica decides at most once, with randomized replicas reaching a common coin, BA obtains termination: with the growing number of round (i.e., → +∞), the probability of each correct replica deciding by round is 1.

DBFT: Efficient leaderless Byzantine consensus and its application to blockchains
5.2.1 System model and service properties. Democratic Byzantine fault tolerance (DBFT) is a leaderless BFT protocol that tolerates Byzantine replicas among at least 3 + 1 replicas [28,29]. DBFT runs on a partially synchronous network, and its messaging pattern combines RBC and a derived version of BA, namely Psync, which uses a weak coordinator to improve performance. DBFT has a time complexity of 6 (rounds) in the best case, given no faulty replicas and a synchronous network, and a message complexity of ( 3 ).

5.2.2
The binary Byzantine consensus, Psync. Psync is adapted from the BA protocol shown in Section 5.1.2. Psync made three major changes to the original protocol: (1) Psync adds timeout triggers in each phase to handle partial synchronous networks.
(2) Psync adds a weak coordinator in Phase 2 to resolve conflicts.
(3) Psync adds a termination condition in Phase 3. Figure 12a, Psync divides Phase 2 of the BA protocol into two steps. A weak coordinator is picked in a round-robin fashion such that = (( + 1) mod ) + 1, where is the round number and is the number of all replicas. In this example, replica 2 is the weak coordinator, and it broadcasts a coord message to the other replicas. When the weak coordinator has multiple values in its value set , it picks the value received from the smallest ID replica and then broadcasts a coord message with . As a result, Psync can resolve value conflicts to a great extent. Next, the weak coordinator and the other replicas that have received the coord message within a time delay threshold broadcast an aux message containing . At the end of this phase, replicas wait for − aux messages to start Phase 3.

As shown in
Since Psync works in partial synchrony, if a non-weak-coordinator replica does not receive any coord message in time, it still broadcasts the aux messages. Figure 12b shows an example where replicas 1 and 2 propose value 0 (solid lines), while 3 and 4 propose value 1 (dash lines). At the end of Phase 1, each replica receives three messages containing value 0 and three messages containing value 1 in two rounds. In this case, both values, 0 and 1, are included in each replica's value set . The weak coordinator 2 decides to propose value 0 because 0 is received from 1 , which has the smallest ID number. However, the coord messages sent from 2 have not reached to 3 and 4 in time. These two replicas must broadcast their aux messages containing both values 0 and 1. In Phase 3, no replica collects sufficient aux messages ( − = 4 − 1 = 3) with a single value . Consequently, no replica can deliver any value, and they must start the next round to resolve this conflict.
In Phase 3, if a replica has decided a value in round , it checks whether the current value set has more than one value; i.e., some other replica has not yet decided. If so, the replica starts the next round. Each replica halts after two rounds of its decision round; i.e., if a replica has decided in round , it terminates the current Psync instance in round + 2. Figure 13 shows the complete DBFT protocol, divided into two parts. The first part consists of Bracha's RBC [14] instances. Each instance corresponds to a proposed value. After this instance finishes, each replica checks the validity of the proposed data, denoted by , (e.g., the values proposed by all replicas). The second part consists of Psync instances (i.e., each replica contributes a Psync instance). This part assists all replicas in deciding on whether to accept . DBFT claims that these Psync instances can execute on different threads in parallel. For simplicity, we put those instances in sequential order in Figure 13. Each replica can operate those instances in two ways:

DBFT protocol based on Psync.
(1) Fast path. If a replica (say ) has RBC-delivered some data from replica , it joins , sets its Psync value set = 1 in , and directly starts its role in Phase 2 by skipping the double broadcast procedure in Phase 1. The fast path's functionality and correctness of Phase 1 in Psync are performed and ensured by the RBC protocol ( § 5.1.1). Replica keeps joining such RBC-delivered Psync instances until one of the Psync instances delivers a single value 1.
(2) Regluar Path. If a replica delivers value 1 in a Psync instance, it joins all other Psync instances.
It proposes value 0 and starts its role from Phase 1. In addition, if a replica never delivers any data through RBC, it joins each Psync instance and starts from Phase 1 with a proposed value 0.
After running Psync instances, when an instance (say ) delivers 1, each replica picks the smallest ID . Then, the data on replica are the decided data by this DBFT consensus instance.
The message complexity of each RBC or Psync instance is ( 2 ). Since multiple RBCs and Psync instances are needed, the total message complexity becomes ( 3 ). In the best case, data can be delivered with one RBC instance plus Psync instances starting from a fast path and run in parallel. In this case, the time complexity is 4 rounds (RBC) plus 2 rounds ( parallel Psync with fast path), which adds up to 6 rounds. If conflicts exist, DBFT needs at least one complete round of Psync, which incurs a delay of at least 4 extra rounds.

Discussion.
DBFT improves the BA protocol by assigning a conflict resolver (i.e., the week coordinator). Compared with BA, Psync can directly decide a binary value in the fast path by removing the last two rounds and the random coin-flip procedure. This improvement upgrades system performance in terms of throughput and latency, though it still requires ( ) delays when there are Byzantine replicas [100]. However, DBFT assumes a partially synchronous network to achieve consensus while some state-of-the-art leaderless protocols, such as HoenyBadgerBFT [70] and BEAT [36], are able to work in asynchronous networks.

System model and service properties.
HoneyBadgerBFT is a leaderless Byzantine fault-tolerant consensus protocol that tolerates Byzantine replicas in a total of 3 + 1 replicas [70]. Compared to DBFT [29], which operates in partially synchronous networks, it can operate in asynchronous networks. It argues that failure detection based on timeouts requires network synchrony and tuning timeouts is difficult in practice because the system may encounter arbitrary periods of asynchrony [70]. It uses threshold encryption in its protocol to defend against censorship attacks, where adversaries may refuse to broadcast or vote on certain data to prevent them from being processed. It has a time complexity of (log ) for replicas and a message complexity of (| | + | | 3 log ), where is the message set.

Efficient reliable broadcast for large messages.
HoneyBadgerBFT uses batching to improve the system's throughput. When multiple RBC instances run in parallel, large messages may overload the network bandwidth and cause significant performance degradation. To reduce messaging, Hon-eyBadgerBFT uses erasure coding in Bracha's RBC protocol and thus reduces the communication complexity from (| | 2 ) to (| | ), where | | is the message size of a data batch. Similar to Bracha's RBC, this protocol has four steps (shown in Figure 14). In Step 1, the sender uses ( − 2 , ) Reed-Solomon codes from [97] and disseminates a data batch into blocks of size | | −2 . Each block contains original transactions and parity data for decoding and recovery. The storage overhead is where | | is the ideal block size without any parity data. The erasure coding scheme brings two benefits: (1) It reduces the size of initial and echo messages by a factor of ( ), which further reduces the communication complexity from (| | 2 ) (in Bracha's RBC) to ( | | · 2 ) = (| | ).
(2) It requires − 2 > blocks to decode a complete batch. Thus, faulty replicas cannot produce enough blocks to pollute a correct replica's decoded data.
After encoding, the sender adds the Merkle tree information as a checksum of each encoded data block and then distributes each ⟨initial, , ⟩ to corresponding replica .
In Step 2, similar to Bracha's RBC, a replica broadcasts ⟨echo, , ⟩ after receiving the initial message. Each replica also checks the validity of the data block in each echo message with its Merkle-tree-based checksum and discards any faulty ones.
In Step 3, similar to Bracha's RBC, a replica broadcasts a ready message only once if one of the following conditions holds: 1 ○ it receives no less than − echo messages, or 2 ○ it receives + 1 ready messages with valid ℎ. The replica then recalculates the Merkle root ℎ from the checksums in the messages. Once the Merkle root ℎ is valid, it broadcasts a ⟨ready, ℎ⟩ message with the Merkle root ℎ to save bandwidth. In Step 4, when a replica receives − ready messages with valid ℎ, it waits for − 2 distinct echo messages to collect sufficient data blocks to decode ; after that, it delivers .

Binary
Byzantine agreement with cryptographic common coin. HoneyBadgerBFT also adapts the BA protocol [71] (introduced in § 5.1.2) with two modifications: (1) a more secure coin-flip process in Phase 3, and (2) an additional termination condition in Phase 3 to prevent BA from prolonged looping.
The former process uses an ( , ) threshold signature from Cachin et al. [20] to generate a common coin shared among = 3 + 1 replicas that tolerate up to adversaries. This process first assigns a trusted dealer to generate a common public key ( ) for all replicas and secret keys ( for replica ). Each replica computes a signature share for an input message by using their secret keys and then broadcasts the computed share. When + 1 shares from different replicas are collected, a replica combines these shares and produces a threshold signature, , that can be verified by the common public key, ; is valid if at least + 1 shares are correct. Then, the replica delivers as the output of this process. Note that cannot be verified by if some shares are faulty [88]. Thus, the messaging is safe with up to adversaries because polluting a delivered value requires at least + 1 faulty shares.
The latter modification aims to strengthen the termination of producing a common coin. Hon-eyBadgerBFT uses a round number ( ) in the BA protocol as an input message (i.e., = ) of the threshold signature process. Specifically, when a replica delivers a valid signature (where = ), it computes a coin bit such that = ( mod 2). Then, the replica checks if its agreement value set contains a value such that = . If so, it delivers the agreement set . This process requires a message complexity of ( 2 ) incurred by the broadcast of signature shares and a time complexity of (1) (rounds). The replica terminates the loop for obtaining a common coin (in § 5.1.2) when a new coin ( ′ ) is obtained in a round such that ′ = .

Asynchronous common subset.
HoneyBadgerBFT uses an asynchronous common subset (ACS) protocol from Ben-Or et al. [12] as the core building block. An ACS instance contains up to modified RBC instances (introduced in Section 5.3.2) and up to modified BA instances (introduced in Section 5.3.3) running in parallel. Each replica runs an ACS instance in two phases.
In Phase 1, a replica starts its instance when it proposes some data . All replicas participate in this instance if some from other servers starts as a proposer or a receiver. In Phase 2, a replica joins up to BA instances to decide whether to accept some replica(s)' proposal(s). Here, if a replica delivered some data from (proposed by replica ), it sets 1 as the input value for . All replicas then wait for at least − BA instances to deliver 1. After that, a replica sets 0 to the BA instances for which it has not yet set any value and waits for all BA instances to complete. HoneyBadgerBFT expects those instances to terminate after (log ) rounds [70]; i.e., the time complexity is (log ). Under HoneyBadgerBFT, some instance may run more slowly than its paired instances. Thus, at the end of Phase 2, each replica waits for a paired and = 1 to deliver their data to itself. Finally, each replica delivers a collection of the data blocks as a final decision.   The time complexity of an ACS instance is (log ) as it must wait for each BA to finish [12]. There are solutions with a time complexity of (1) [11], but HoneyBadgerBFT decides to use the current solution to achieve high throughput.

5.3.5
The complete protocol of HoneyBadgerBFT. The complete HoneyBadgerBFT runs in three epochs (shown in 15) that coordinate the pace of all replicas for achieving consensus. We now show the life-time of a transaction going through the three epochs.
In the first epoch, a replica randomly selects a batch of transactions from its buffer and uses a threshold encryption scheme from Baek and Zheng [8] to encrypt into encrypted data . This scheme works similarly to the threshold signature scheme described in § 5.3.3, where a trusted stakeholder generates a common public key and individual private keys distributed to each replica; each replica can encrypt data and produce a share and decrypt the share with + 1 decryption shares.
In the second epoch, a replica uses its encrypted data as the input of an ACS instance. After running instances and instances, the replica acquires a collection of encrypted data blocks { | ∈ {1... } ∧ = 1} delivered by this ACS instance. In the third epoch, a replica decrypts each acquired to obtain the original transaction set . Specifically, each replica broadcasts its decryption share of , denoted as ℎ ( , ), to the other replicas. Then, if a replica collects decryption shares of a data block from + 1 different replicas, it then retrieves the original data . Once a replica retrieves the original , it delivers transactions in and deletes them from its buffer.

Messaging complexity and batch sizes.
HoneyBadgerBFT utilizes many protocols to achieve consensus without a primary, which makes it tricky to calculate its messaging complexity. We analyze the messaging complexity of a consensus process that commits a set of transactions among replicas in the following three parts.
(1) The RBC. Each replica selects a sub-batch of = transactions as the input of their corresponding RBC instance. Note that each instance has a communication complexity of (| | ) (previously analyzed in Section 5.3.2), and there are RBC instances in total (shown in Figure 15). Therefore, the messaging complexity is ( · | | ) = (| | ).
(2) The BA. An instance of BA requires ( 2 ) messages for each round, and each instance requires (log ) rounds to guarantee termination. Assume the message size in this instance is | | (the relation of and is precisely discussed in the below paragraph), each instance has a messaging complexity of (| | 2 log ), and there are instances, which results in a total messaging complexity of (| | 3 log ). (3) The decryption share. Each replica sends its decryption share ℎ ( , ) of data blocks to every other replica, and it may receive blocks as a replica sends ( 2 ) decryption share messages. Assuming the share size is | |, a replica requires a messaging complexity of (| | 2 ). With a total of replicas, the messaging complexity becomes (| | 3 ).

Discussion.
HoneyBadgerBFT is able to achieve high throughput over tens of thousands of transactions per second among a hundred replicas. It claims to be the first practical solution that guarantees liveness in asynchronous networks. It also provides several encryption mechanisms to prevent censorship attacks.
However, HoneyBadgerBFT sacrifices latency to achieve high throughput, as shown in [36]. The latency is relatively high (> 10s) when > 48 [70], which is undesirable for applications that require low-latency consensus. The erasure coding library [97] of HoneyBadgerBFT also puts an upper bound of to 128 [36].

BEAT: Asynchronous BFT made practical
5.4.1 System model and service properties. BEAT [36] consists of five leaderless asynchronous BFT protocols (i.e., BEAT0 to BEAT4), with each of them addressing different goals such as throughput, latency, bandwidth usage, and BFT storage. These protocols draw inspiration from HoneyBad-gerBFT [70] and make improvements to achieve higher performance.
(1) It uses a labeled threshold encryption mechanism. All encrypted data blocks from a replica in an epoch are labeled as ( , ); duplicated messages with the label ( , ) are discarded. In addition, BEAT0 replaces HoneyBadgerBFT's pairing-based cryptography with TDH2 [89], which significantly reduces the encryption latency [36]. (2) It replaces HoneyBadgerBFT's common coin protocol by directly applying a threshold coin clipper method [20]; the new method can also reduce latency in obtaining a common coin. (3) It uses a more efficient erasure coding library called Jerasure 2.0 [79]; the new erasure coding approach has higher performance than the zfec [97] library used in HoneyBadgerBFT and is able to scale up the cluster size to more than 128 replicas.

BEAT1 and BEAT2
. BEAT0 inherits the erasure-coding-based reliable broadcast protocol used in HoneyBadgerBFT; however, this protocol incurs high latency when batch sizes are small. To improve their performance, BEAT1 and BEAT2 use the original Bracha's RBC [14] to obtain lower broadcast latency, and BEAT2 also moves the labeled threshold encryption from server ends to client ends. By doing so, faulty replicas cannot defer transaction processing to perform censorship attacks; however, they can target and suppress specific clients to censor client requests. To mitigate this problem, BEAT2 uses anonymous communication networks to hide clients' information so that correct clients are not exposed to adversaries. This improvement assists BEAT2 to achieve casual order preservation [19,35,82], a weaker consistency guarantee than linearizability [50].

BEAT3
. BEAT3 uses an erasure-code-based RBC protocol called AVID-FP [48] to replace Bracha's RBC used in BEAT2. AVID-FP follows a four-phase message-passing workflow (shown in Figure 16), similar to the RBC protocols introduced in § 5.  (1) A replica uses a ( , ) labeled threshold encryption to encode a data batch ( ) to a set of fragments ({ }) and a single global fingerprinted cross-checksum ( ). It then broadcasts initial messages in the form of ⟨initial, ,c⟩ to corresponding replicas where ∈ {1.. }.
(BEAT3 sets = + 2 where ≥ + 1 matches the threshold). (2) Each replica verifies the received fragment using cross-checksum . If is valid, stores with and then broadcasts an echo message piggybacking . (3) A replica broadcasts a ready message with (only once) when 1 ○ it has received + echo messages with , or 2 ○ it has received + 1 ready messages with . (4) After a replica receives 2 + 1 ready messages with the same cross-checksum , it delivers . Although Bracha's RBC, HoneyBadgerBFT's RBC, and AVID-FP have a similar message-passing workflow, the messaging formats are different: Bracha's RBC carries original data blocks in all messages until the protocol terminates, which involves a large message size, whereas HoneyBad-gerBFT's RBC carries fragmented data blocks by the end of the second phase. In contrast, AVID-FP broadcasts fragmented data blocks only in the first phase; the rest of the phases circulate only the global cross-checksum value. Since checksums are usually much smaller than data blocks, AVID-FP is able to reduce the usage of network bandwidth to (| |) + ( | |) = (| |) where (| |) for the first phase and ( | |) for the remaining phases.
The AVID-FP protocol does not guarantee that all correct replicas eventually receive the original data. Since the threshold of encryption is + 1, AVID-FP guarantees that + 1 correct replicas eventually receive + 1 erasure-encoded fragments of the original data, with one fragment on each replica, and all correct replicas deliver the global fingerprinted cross-checksum . Nonetheless, clients can reconstruct the original data from + 1 fragments and verify data integrity using the cross-checksum . Since a client encodes a data block and generates fragments with a checksum, the client can send a query quest to collect + 1 fragments paired with from + 1 correct replicas. Then, the client can decode received fragments to reconstruct the original data block .
By using AVID-FP, BEAT3 significantly reduces the usage of storage spaces, from ( | |) to (| |) where is the set of all messages proposed by clients. The evaluation results of BEAT [36] show that BEAT3 outperforms HoneyBadgerBFT under all performance metrics: throughput, latency, scalability, network bandwidth, and storage overhead.

BEAT4.
This protocol replaces AVID-FP used in BEAT3 with AVID-FP-Pyramid, which uses pyramid codes [51] to reduce data reconstruction costs for read operations. Compared with MDS [68], the conventional erasure code, pyramid codes require additional parity data but allow partial data reconstruction with less information; i.e., clients can recover specific data from tailored data fragments. This method enables a more efficient data recovery process with a lower Throughput Latency Bandwidth Scalability Storage 2x 2x 0.7-1.1x ↓↓ (| |) -(| |) + 10% Table 4. Qualitative comparison of BEAT and HoneybadgerBFT. Notations and represent low contention (small batch size) and high contention (large batch size (e.g., > 5000 transactions)), respectively; ↑ and ↓ represent slightly higher or lower values, and ↑↑ and ↓↓ represent significantly higher or lower values than the baseline; '-' means no data are presented in the paper; and is the set of all transactions that clients send.
bandwidth when clients need only partial data fragments. For example, in smart contract applications, clients often need only specific keywords to append or execute transactions; in video media services, clients may load partial fragments instead of the whole video.   Figure 17 shows an example of the pyramid code used in BEAT4 compared to conventional MDS codes where there are 6 data fragments. In this example, a (9, 6) MDS code [68] builds three redundant parity fragments ( 7 ... 9 ), whereas a (9 + 1, 6) = (10, 6) pyramid code equally divides data fragments and computes two group-level parity fragments, namely 7−1 for { 1 , 2 , 3 } and 7−2 for { 4 , 5 , 6 }, using a (4, 1) MDS code. Besides the two group-level parity fragments, the (10, 6) pyramid code maintains two global-level parity fragments ( 8 and 9 ). In this case, if a fragment is faulty (say 1 ), the pyramid code needs only 3 group-level fragments ( 2 , 3 and 7−1 ) to recover 1 as opposed to using 6 fragments in a (9, 6) MDS code.
By using AVID-FP-Pyramid, a client can directly request a specific data fragment from the corresponding replica and the checksum from + 1 replicas. If the fragment is faulty, the client can first try to collect group-level fragments from corresponding replicas and reconstruct the fragment. If the client fails to collect sufficient group-level fragments, it then broadcasts a request to collect global-level fragments from replicas outside the group. As a result, BEAT4 can save 50% of the bandwidth in read requests, with approximately 10% additional storage space [36,51]. However, BEAT4 requires more replicas to store pyramid codes, which incurs a higher latency when is small ( = 3 + 1). For example, in BEAT's evaluation, the latency is higher than that of HoneyBadgerBFT when = 1, but when > 1, BEAT4 outperforms HoneybadgerBFT under all performance metrics. 5.4.6 Discussion. We qualitatively compare BEATs and HoneyBadgerBFT in Table 4 in terms of throughput, latency, consumption of network bandwidth, scalability, and storage space. BEAT0, BEAT1, and BEAT2 can be applied to general state machine replication applications, while BEAT3 and BEAT4 are more suitable for BFT storage services.

CONCLUSIONS
This paper surveyed selected state-of-the-art Byzantine fault-tolerant (BFT) consensus algorithms that are prominent examples from academia and industry. These algorithms are categorized as efficient leader-based, robust leader-based, and leaderless BFT algorithms. We presented a qualitative comparison of all surveyed algorithms in terms of time and message complexities. Each survey intuitively shows message-passing workflows for reaching consensus by providing diagrams that depict the process of a complete consensus instance. To improve understandability, each survey decouples the complex design and mechanism of algorithms and describes their core components of consensus following the same structure, including normal operation (all three categories), view changes (efficient/robust leader-based BFT), robustness improvements, conflict resolutions (leaderless BFT), and a discussion of strengths and weaknesses.