---
abstract: |
    This paper presents (or, simply, ), a robust Byzantine fault-tolerant (BFT) total order broadcast protocol aimed at maximizing throughput on wide-area networks (WANs), targeting permissioned and Proof-of-Stake permissionless blockchains. 

    We show that achieves unprecedented throughput on WANs without sacrificing latency, robustness to malicious behavior, or even performance in clusters.  Our evaluation shows that orders more than 60000 signed Bitcoin-sized transactions per second on a widely distributed 100 nodes, 1 Gbps WAN setup, while preventing a range of attacks including request duplication performance attacks. 

    To achieve this, relies on a novel protocol mechanism that allows a set of leaders to propose request batches independently, in parallel, while rotating the assignment of a partitioned request hash space to leaders.  Several optimizations boost throughput even further, including partial replication through a novel abstraction we call *light total order (LTO)* broadcast.  Perhaps most importantly, relies on proven BFT protocol constructs, which simplifies reasoning about correctness.  Specifically, is a generalization of the celebrated and scrutinized PBFT protocol.  In a nutshell, follows PBFT “safety-wise”, with changes needed to accommodate novel features restricted to PBFT liveness. 
author:
- 'Paper \#32'
- |
    Chrysoula Stathakopoulou\
    IBM Research - Zurich
- |
    Tudor David\
    IBM Research - Zurich
- |
    Marko Vukolić\
    IBM Research - Zurich
title:
- '**: High-Throughput Robust BFT for Blockchains**'
- '**: High-Throughput BFT for Blockchains**'
---

Introduction
============

Blockchains are decentralized, globally-distributed, strongly consistent replicated systems that run across networks of mutually untrusting nodes.  Since the inception of Bitcoin’s decentralized cash application [@Bitcoin], modern blockchain systems have evolved the ability to run arbitrary distributed applications (e.g., [@EthereumURL; @AndroulakiBBCCC18]), with the promise of supporting entire decentralized economies [@AlgorandURL] and business ecosystems across industries [@HyperledgerURL]. 

Byzantine fault-tolerant (BFT) protocols, which tolerate arbitrary (Byzantine [@Lamport:1982:BGP:357172.357176]) behavior of a subset of nodes, have evolved to be the key technology to power blockchains and ensure their consistency [@Vukolic15; @CromanDEGJKMSSS16].  BFT protocols relevant to blockchain are consensus and state machine replication (SMR) protocols (e.g., [@Castro:2002:PBF]) or, even more specifically, total order (TO) broadcast protocols that establish the basis for SMR [@Schneider90].  Such BFT protocols have found their use in replacing (or, less often, complementing) energy-wasting and slow Proof-of-Work (PoW) consensus protocols used to power early blockchains including Bitcoin, which process between 7 and 60 transactions per second [@Vukolic15; @GervaisKWGRC16]. 

In general, current BFT protocols do not scale well with the number of nodes (replicas) and hence do not perform to the needs of blockchain use cases.  State-of-the-art BFT protocols are either very efficient on small scales in clusters (e.g., [@700; @Zyzzyva]) or exhibit modest performance on large scales (thousands or more nodes) across wide area networks (WAN) (e.g., [@Algorand]). 

However, BFT protocols which exhibit excellent performance on medium-size WAN networks (e.g., up to 100 nodes) remain largely unexplored.  We focus on this deployment setting as it is highly relevant to different types of blockchain networks.  On the one hand, *permissioned* blockchains, such as Hyperledger Fabric [@AndroulakiBBCCC18], are rarely deployed on scales above 100 nodes, yet use cases gathering dozens of organizations (e.g,.  banks) are very prominent [@CordaURL].  In such use cases, every organization represents a separate administrative domain, which defines boundaries of trust, and the requirement that each organization runs (or administers) at least one node is very common.  On the other hand, this setting is also highly relevant in the context of large scale *permissionless* blockchains, in which anyone can participate, that use weighted voting (based e.g., on Proof-of-Stake (PoS) [@CasperFFG; @Ouroboros], delegated PoS (DPoS) [@TendermintURL]), or committee-voting [@Algorand], to limit the number of nodes involved in the critical path of the consensus protocol.  With such weighted voting, the number of (relevant) nodes for PoS/DPoS consensus is typically in the order of a hundred ([@TendermintURL]) or sometimes even less (e.g., few dozens of nodes [@EOSBlockProducers]). 

This paper fills in the void and presents (or, simply, ), a novel total order (TO) BFT protocol that achieves the best throughput to date on public WAN networks, as confirmed by our measurements up to 100 nodes.  achieves this without compromising robustness to failures and malicious attacks, latency or performance on small scale and in clusters.  The following summarizes the main features of , as well as contributions of this paper:

**$\bullet$** [builds on the seminal leader-based PBFT protocol [@Castro:2002:PBF] by generalizing its “liveness” part.  In short, allows multiple concurrent leaders to propose batches of requests in parallel, in a sense multiplexing several PBFT instances into a single total order.  In doing so, leverages multiple secure connections (gRPC) across each pair of nodes, as opposed to state-of-the-art designs that use a single TCP/TLS connection between a pair of nodes, which is important in boosting throughput in small deployments of (e.g., up to 10 nodes). [ ^1] ]{} **$\newline\bullet$** [On the protocol level, the seemingly simple idea of using multiple leaders in parallel raises the issue of *request duplication* performance attacks which may be indistinguishable from normal request re-submissions needed to address the *request censoring* attacks by Byzantine leaders.  In short, with up to $n$ leaders, request duplication attacks may induce an $n$-fold duplication of every single request and bring the effective throughput to its knees, voiding the benefits of using multiple leaders.  As its main novelty in the context of BFT TO protocols, partitions the request hash space across replicas, preventing request duplication, while rotating this partitioning assigment across protocol configurations/epochs, adressing request censoring.]{} ** $\newline\bullet$** [While the base (“vanilla”) version of implements classical TO broadcast and disseminates every request to every correct node, this guarantee is unneccessarily strong for some blockchains.  To this end, we introduce the concept of a *light total order (LTO)* broadcast, which is identical to TO, except that it provides partial data availability guaranteeing the delivery of every request to *at least one* correct node.  Other correct nodes get and agree on the order of cryptographic hashes of requests, which is the basis for maintaining other TO properties.  LTO can potentially be used to boost vanilla throughput in blockchain systems that separate the execution of applications (smart contracts) from the agreement on the order of transactions (e.g., Hyperledger Fabric [@AndroulakiBBCCC18]).  Mir further uses *client signature verification sharding* optimization to offload CPU, which often becomes a bottleneck in . ]{} ** $\newline\bullet$** [ avoids “design-from-scratch”, which is known to be error-prone for BFT [@700].  is a generalization of the well-scrutinized PBFT protocol [^2], which closely follows “safety-wise” while introducing important generalizations to PBFT liveness (e.g., leader election).  Restricting changes to PBFT liveness simplifies the reasoning about correctness.]{} ** $\newline\bullet$** [Finally, we implement in Go and run it with up to 100 nodes in a WAN, as well as in clusters and under faults, for different transaction sizes, comparing it to state of the art BFT protocols.  We also evaluate the impact of multiple optimizations we propose.  Our results show that drastically outperforms state of the art, ordering more than 60000 signed Bitcoin-sized tps on a scale of 100 nodes on a WAN, with typical latencies of 1-2 sec. ]{} 

-   [builds on the seminal leader-based PBFT protocol [@Castro:2002:PBF] by generalizing its “liveness” part.  In short, allows multiple concurrent leaders to propose batches of requests in parallel, in a sense multiplexing several PBFT instances into a single total order.  In doing so, leverages multiple secure connections (gRPC) across each pair of nodes, as opposed to state-of-the-art designs that use a single TCP/TLS connection between a pair of nodes, which is important in boosting throughput in small deployments of (e.g., up to 10 nodes). [ ^3] ]{}

-   [On the protocol level, the seemingly simple idea of using multiple leaders in parallel raises the issue of *request duplication* performance attacks which may be indistinguishable from normal request re-submissions needed to address the *request censoring* attacks by Byzantine leaders.  In short, with up to $n$ leaders, request duplication attacks may induce an $n$-fold duplication of every single request and bring the effective throughput to its knees, voiding the benefits of using multiple leaders.  As its main novelty in the context of BFT TO protocols, partitions the request hash space across replicas, preventing request duplication, while rotating this partitioning assigment across protocol configurations/epochs, adressing request censoring.]{} 

-   [While the base (“vanilla”) version of implements classical TO broadcast and disseminates every request to every correct node, this guarantee is unneccessarily strong for some blockchains.  To this end, we introduce the concept of a *light total order (LTO)* broadcast, which is identical to TO, except that it provides partial data availability guaranteeing the delivery of every request to *at least one* correct node.  Other correct nodes get and agree on the order of cryptographic hashes of requests, which is the basis for maintaining other TO properties.  LTO can potentially be used to boost vanilla throughput in blockchain systems that separate the execution of applications (smart contracts) from the agreement on the order of transactions (e.g., Hyperledger Fabric [@AndroulakiBBCCC18]).  Mir further uses *client signature verification sharding* optimization to offload CPU, which often becomes a bottleneck in . ]{} 

-   [ avoids “design-from-scratch”, which is known to be error-prone for BFT [@700].  is a generalization of the well-scrutinized PBFT protocol [^4], which closely follows “safety-wise” while introducing important generalizations to PBFT liveness (e.g., leader election).  Restricting changes to PBFT liveness simplifies the reasoning about correctness.]{} 

-   [Finally, we implement in Go and run it with up to 100 nodes in a WAN, as well as in clusters and under faults, for different transaction sizes, comparing it to state of the art BFT protocols.  We also evaluate the impact of multiple optimizations we propose.  Our results show that drastically outperforms state of the art, ordering more than 60000 signed Bitcoin-sized tps on a scale of 100 nodes on a WAN, with typical latencies of 1-2 sec. ]{} 

To put this into perspective, ’s 60000+ tps on 100 nodes on WAN are enough to 3x multiplex the advertised peak throughputs of the top 20 blockchain networks per market cap (less than 20k tps in total [@CapacityTop20URL] for more than \$260B USD total market capitalization).  It is 2.5x the alleged peak capacity of VISA (24k tps [@CapacityTop20URL]) and more than 30x faster than the actual average VISA transaction rate (about 2k tps [@Vukolic15]).  We expect that such a performance will open the door for new blockchain use cases. 

The rest of the paper is organized as follows.  In Section \[sec:model\], we define system model and in Section \[ssec:PBFT\] we briefly present PBFT (for completeness).  In Section \[sec:overview\], we give an overview of and changes it introduces to PBFT.  We then explain implementation details in Section \[sec:details\].  We present optimizations, including LTO, in Section \[sec:optimizations\].  Section \[sec:evaluation\] gives evaluation details.  Finally, Section \[sec:relwork\] discusses related work.  correctness arguments are postponed to Appendix \[sec:correctness\], while discussion of less novel protocol details (including state transfer, reconfiguration and durability) is in Appendix \[sec:otherthings\]. 

![ image](pbft.png){width="\textwidth"}

System Model {#sec:model}
============

We assume an eventually synchronous network [@Dwork:1988:CPP:42282.42283] in which the communication among correct processes can be fully asynchronous before some time $GST$, unknown to nodes, after which it is assumed to be synchronous.  Processes are split into a set of $n$ *nodes* (the set of all nodes is denoted by $Nodes$) and a set of *clients*.  We assume a public key infrastructure in which processes are identified by their public keys; we further assume node identities are lexicographically ordered and mapped by a bijection to the set $[0\ldots n-1]$ which we use to reason about node identities.  At any point in time, at most $\faults$ nodes can simultaneously be *Byzantine* faulty (i.e., crash or deviate from the protocol in an arbitrary way), such that $n\ge 3\faults+1$. Any number of clients can be Byzantine. 

We assume an adversary that can control Byzantine faulty nodes but cannot break the cryptographic primitives we use, such as PKI and cryptographic hashes.  $H(data)$ denotes a cryptographic hash of $data$, while $data_{\sigma_p}$ denotes $data$ signed by process $p$ (client or node).  Processes communicate through authenticated point-to-point channels (our implementation uses gRPC [@gRPCURL]). 

Nodes implement a BFT total order (atomic) broadcast service to clients.  To broadcast request $r$, a client invokes $\bcast(r)$, with nodes eventually outputting $\deliver(sn,r)$, such that the following properties hold:

1.   **Validity:** If a correct node delivers $r$ then some client broadcasted $r$.

2.   **Total Order:** If two correct nodes deliver requests $r$ and $r'$ with sequence number $sn$, then $r=r'$.

3.   **No duplication:** If a correct node delivers request $r$ with sequence numbers $sn$ and $sn'$, then $sn = sn'$.

4.   **Liveness:** If a correct client broadcasts request $r$, then every correct node eventually delivers $r$.

Crash Course on PBFT {#ssec:PBFT}
====================

We depict the PBFT communication pattern in Figure \[fig:pbft\].  PBFT proceeds in rounds called *views* which are led by the *primary*.  The primary sequences and *proposes* client’s request in a message — on WANs this step is typically a network bottleneck.  Upon reception of the , other nodes validate the request, which involves, at least, verifying the authenticity of a client’s request (we say a node *pre-prepares* the request).  This is followed by two rounds of all-to-all communication (and messages), which are not bottlenecks as they leverage $n$ links in parallel and contain metadata (request hash) only.  A node *prepares* a request and sends a message if it gets a message from a quorum ($2\faults+1$ nodes) that matches a .  Finally, nodes *commit* the request in total order, if they get a quorum of matching messages. 

The primary is changed only if it is faulty or if asynchrony breaks the availability of a quorum.  In this case, nodes timeout and initiate a *view-change*.  View-change involves a communication among nodes in which the information about the latest *pre-prepared* and *prepared* requests is exchanged, such that the new primary, which is selected in round robin fashion, must re-propose a potentially committed request under the same sequence number within a <span style="font-variant:small-caps;">new-view</span> message (see [@Castro:2002:PBF] for details).  The view-change pattern can be simplified using signatures [@Castro:1999:PBF:296806.296824]. 

After the primary is changed, the system enters the new view and common-case operation resumes.  PBFT complements this main common-case/view-change protocols with *checkpointing* (log and state compaction) and state transfer subprotocols [@Castro:2002:PBF]. 

Overview {#sec:overview}
========

is based on PBFT [@Castro:2002:PBF] (Sec.  \[ssec:PBFT\]) — major differences are summarized in Table \[table:diff\].  In this section we elaborate on these differences, giving a high-level overview of . 

[***Request Authentication.***]{} 

#### Request Authentication. 

While PBFT authenticates clients’ requests with a vector of MACs, uses signatures for request authentication as most blockchains do (e.g., to prevent any number of colluding nodes from spending client’s assets), as well as to avoid concerns associated with “big-MAC” attacks related to the MAC authenticators PBFT uses [@Clement:2009:MBF:1558977.1558988].  This change is hence required for robustness, however, it hampers throughput, as per-request verification of clients’ signatures requires more CPU than that of MACs. 

[***Batching and Watermarks.***]{} 

#### Batching and Watermarks. 

processes requests in *batches*, a standard throughput improvement of PBFT (see e.g., [@Zyzzyva; @700]).  However, it also retains request/batch *watermarks*, used by PBFT to boost throughput.  In PBFT, request watermarks, low and high, represent the range of request sequence numbers which the primary/leader can propose concurrently.  While many successor BFT protocols eliminated watermarks in favor of batching (e.g, [@Zyzzyva; @BessaniSA14; @700]), reuses watermarks to facilitate concurrent proposals of batches by *multiple leaders*. [*** Protocol Round Structure.*** ]{} 

#### Protocol Round Structure. 

proceeds in *epochs* which correspond to *views* in PBFT.  Like PBFT views, each epoch has the *primary*, which is a node deterministically defined by the epoch number, by round-robin rotation across all the participating nodes of the protocol. 

Each epoch $e$ has a set of *epoch leaders* (denoted by $\eplead(e)$), which we define as nodes that can propose batches in a given epoch (in contrast, in PBFT only the primary is the leader).  Within an epoch, deterministically partitions batch sequence numbers across epoch leaders, such that all leaders can propose their batches simultaneously, without conflicts.  Unlike in PBFT, some epochs have limited duration in terms of the maximum number of batches that can be ordered in an epoch.  Such epochs are called *ephemeral*.  An *ephemeral* epoch that orders the maximum number of batches transitions to the next epoch via *gracious epoch-change* protocol, which is a much more lightweight reconfiguration protocol compared to PBFT view change. 

We call an epoch **, i.e., with no bound on number of batches it can order, if and only if the number of epoch leaders is greater or equal to the configuration parameter $StableLeaders$. In this paper, we set $StableLeaders=n$ (i.e., a stable epoch has all nodes as leaders), and configure to start from a stable epoch.  From a epoch, moves to the next epoch only in case of failures or asynchrony (we talk about *ungracious epoch-change*). 

reduces to PBFT with $StableLeaders=1$, which makes every epoch stable, every view-change ungracious, and makes the primary the only leader. 

[***Selecting Epoch Leaders.***]{} 

#### Selecting Epoch Leaders. 

In this paper, we use a very simple approach to selecting the set of epoch leaders.[^5] Namely, the epoch $e$ primary chooses and reliably broadcasts the set of epoch leaders $EL(e)$ to all nodes, subject to the following constraints: 1) if $e$ starts graciously, the leader set does not reduce in size compared to previous epoch $e-1$ and it grows if the primary believes that more than $|\eplead(e-1)|$ nodes are correct and $|\eplead(e-1)|<StableLeaders$, 2) if $e$ starts ungraciously, the leader set reduces in size (if it contained more than one leader), and 3) the primary is always in the leader set.  In our evaluation, we used the policy in which the leader set grows and reduces in size by exactly one node, although different policies are easy to implement. 

[***Request Duplication and Request Censoring Attacks.***]{} 

#### Request Duplication and Request Censoring Attacks. 

Moving from the single-leader PBFT to the multi-leader poses the challenge of request duplication.  Namely, a simplistic approach to multiple leaders would be to allow any leader to add any request into a batch (as done in e.g., [@BFT-Mencius; @RedBelly; @Hashgraph]), either in the common case, or in the case of client request retransmission.  The simplistic approach, combined with a client sending a request to exactly one node, allows no duplication with good throughput only in the best case, i.e., with no Byzantine clients/leaders and with no asynchrony. 

However, this approach is not robust [@Clement:2009:MBF:1558977.1558988] outside the best case, in particular with Byzantine clients sending identical request to multiple nodes, performing the *request duplication* performance attack.  Moreover, a client cannot be naively declared as Byzantine and blacklisted if it sends a request to multiple nodes.  Indeed, as Byzantine leaders can drop requests selectively (we talk about request *censoring*), a client needs to send the request to at least $\faults+1$ nodes (i.e., to $O(n)$ nodes, when $n=3f+1$) in the worst case in *any* BFT protocol.[^6] Therefore, a simplistic approach to parallel request processing with multiple leaders [@BFT-Mencius; @RedBelly; @Hashgraph] faces attacks that can reduce throughput by factor of $O(n)$, nullifying the effects of using multiple leaders.  We demonstrate the effects of these attacks in Section \[sec:evalfaults\]. 

To cope with these attacks, partitions the request hash space into buckets which are then assigned to leaders (preventing request duplication) and rotates the bucket assignment across epochs and within stable epochs (addressing request censoring). 

[***Buckets and Request Partitioning.***]{} 

#### Buckets and Request Partitioning. 

partitions the hash space into $m*n$ non-intersecting *buckets* of (approximately) equal size, where $m$ is a configuration parameter.  Each leader of epoch $e$ is assigned at least $\lfloor\frac{m*n}{|\eplead(e)|}\rfloor$ buckets; in case of remaining buckets, the primary and subsequent epoch leaders per lexicographic order, are assigned $1$ additional bucket each. 

At any point in time, a leader can include in its batch only requests from its *active* buckets.  Figure \[fig:buckets\] illustrates the mapping of requests to (active) buckets in a stable epoch with $n=4$ ($m=1$). 

![ Request mapping in a epoch with $n=4$: Solid lines represent the active buckets.  Hash(Req.  1) is mapped to the first bucket, active in node $1$. Hash(Req.  2) is mapped to the third bucket, active in node $3$. Rotation shifts bucket assignment across leaders.[]{data-label="fig:buckets"}](RequestSharding.png){width="0.8\columnwidth"}

[***Rotating Bucket Assignment.***]{} 

#### Rotating Active Bucket Assignment. 

In a epoch (see details in Sec.  \[sec:rotation\]), leaders periodically (i.e., after a number of ordered batches) rotate the assignment of buckets, such that leader $i$ gets assigned active buckets that previously were active at leader $i+1$, per modulo $n$ arithmetics.  This is also illustrated in Figure \[fig:buckets\], for $n=4$. A similar active bucket rotation is done across epochs (Sec.  \[sec:gracious\]).  For simplicity, and since epochs are short-lived, the active bucket assignment within an epoch is fixed. 

#### Parallelism. 

The implementation (detailed in Sec.  \[sec:implementation\]) is highly parallelized, with every *worker* thread responsible for one batch.  In addition, uses multiple gRPC connections among each pair of nodes which proves to be critical in boosting throughput in a WAN especially with a small number of nodes. 

#### Generalization of PBFT and Emulation of Other BFT Protocols. 

reduces to PBFT by setting $StableLeaders=1$. This makes every epoch stable, hides bucket rotation (primary is the single leader) and makes every epoch change ungracious.  can also approximate protocols such as Tendermint [@Buchman16] and Spinning [@Spinning] by setting $StableLeaders>1$, and fixing the maximum number of batches and leaders in every epoch to 1, making every epoch an epoch and rotating leader/primary with every batch. 

Implementation Details {#sec:details}
======================

The Client {#sec:client}
----------

Upon $\bcast(o)$, broadcasting operation $o$, client $c$ creates a message $\langle\requestmsg,o,t,c\rangle_{\sigma_c}$. The message includes the client’s timestamp $t$, a monotonically increasing sequence number, that must be in a sliding window between the low and high *client watermark* $t_{c_L}<t\le t_{c_H}$. Client watermarks in allow multiple requests originating from the same client to be “in-flight”, while allowing them to be processed by different leaders in parallel.  The low and high watermarks of the client’s timestamp sliding window are periodically advanced with the checkpoint mechanism described in Section \[sec:checkpoint\]. 

In this section, we assume that the client sends the to all nodes.  We however implemented a lightweight heuristic allowing clients to submit requests to a single node, estimating the right leader based on the load a client sends and on the bucket rotation period. 

Common-case operation {#sec:stable}
---------------------

Within an epoch $e$, the leadership in proposing batches is partitioned across epoch leaders.  Epoch primary proposes the first batch in the epoch; after that, the leaders take turn in leading batches in a deterministic, lexicographic order.  We say that a leader *leads* batch $B_{sn}$ when the leader is assigned broadcasting a for the batch with sequence number $sn$. Batches are proposed in parallel by all epoch leaders and are processed like in PBFT.  Recall that batch watermarking allows the PBFT primary to propose multiple batches in parallel; in , we simply extend this to multiple leaders (see Fig.  \[fig:preprepare\]). 

![ sending in epoch: All nodes are epoch leaders, balancing the proposal load.[]{data-label="fig:preprepare"}](NormalCase.png){width="\columnwidth"}

In epoch $0$, we assign buckets to leaders sequentially, starting from the buckets with the lowest hash values which we assign to primary $0$, and so on.  When $e>0$, the primary picks a set of consecutive buckets for itself, starting from the bucket which contains the *oldest* request it received; this is key to ensuring Liveness (P4, Sec.  \[sec:model\]).  The other leaders are then deterministically and sequentially assigned the following buckets. 

With such an assignment, the protocol proceeds as follows.  Upon receiving $\langle\requestmsg,o,t,c\rangle_{\sigma_c}$ from a client, an epoch leader first verifies that the request timestamp is in the client’s current window $t_{C_L}<t\le t_{C_H}$ and maps the request to the respective bucket by hashing the request payload along with the client timestamp and identifier $h_r = H(o||t||c)$. If the request falls into the leader’s active bucket, the leader also verifies the client’s signature on .  Malformed signatures result in a node locally blacklisting the client for a period of time. 

The request is discarded if $h_r$ is already in the logs of the node, either because it has already been preprepared or because it is already pending in a bucket. 

Each bucket is implemented as a FIFO queue.  Once enough requests are gathered in the current active bucket of the leader, or if timer $T_{batch}$ expires (since the last batch was proposed by $i$), leader $i$ adds the requests from the current active bucket in a batch, assigns to the batch its next available sequence number $sn$ (provided $sn$ is within batch watermarks) and sends a message.  If $T_{batch}$ time has elapsed and no requests are available, leader $i$ broadcasts a special message with an empty batch.  This guarantees the progress of the protocol with low load. 

Each node $j$ accepts a (we say *preprepares* the batch and the requests it contains), with sequence number $sn$ for epoch $e$ from leader $i$ provided that: (1) the epoch number matches the local epoch number and $j$ did not preprepare another batch with the same $e$ and $sn$, (2) node $i$ is in the $\eplead(e)$ set, (3) leader $i$ leads $sn$, (4) the sequence number $sn$ of the batch in the is between a low watermark and high watermark: $w<sn\leq W$, (5) every request in the batch has a timestamp within the current client’s watermarks, (6) none of the requests in the batch have already been *preprepared*, (7) each request in the batch belongs to one of $i$’s active buckets, and (8) every request in the batch was submitted by a client authorized to write and the request signature is valid. 

Condition (8) effectively enforces access control, which helps protect against flooding denial-of-service (DoS) and helps ensure Validity (Property P1, Sec.  \[sec:model\]).  As this step may reveal to be a CPU bottleneck in if performed by all nodes (e.g., in a case where all nodes need to perform a relatively expensive cryptographic task such as signature verification per transaction), we use signature sharding as an optimization (see Sec.  \[sec:sharding\]). 

If validation succeeds, node $j$ then sends a and the protocol proceeds exactly as PBFT.  Upon committing a batch with sequence number $k$ from leader $i$, node $j$ removes from its buckets any request that is already in batch $k$.

Active bucket rotation (epoch) {#sec:rotation}
------------------------------

introduces a bucket rotation mechanism to prevent request censoring, as we motivated in Section \[sec:overview\]. 

Bucket rotation in epoch relies on leader-to-leader *bucket handover*, which works as follows.  Every $BR(e)$ batches (a configuration parameter), leaders rotate the assignment of buckets, such that leader $i$ gets assigned buckets previously led by leader $i+1$ (in modulo $n$ arithmetics).  To prevent request duplication, leader $i$ waits to commit locally all batches pertaining to buckets $i$ gets assigned to (in particular those lead by $i+1$), before starting proposing own batches.  Other nodes also do the same before they pre-prepare batches in these buckets that are proposed by $i$. Referring to the example shown in Figure \[fig:buckets\], with $n=4$ and $4$ buckets in total, after $BR(e)$ batches, node $0$ gets assigned the red bucket (which was assigned to node $1$), yet node $0$ starts proposing batches only after it locally commits all batches pertaining to the red bucket that were previously committed — informally, node $1$ *hands over* the red bucket to node $0$.

Epoch-change
------------

distinguishes two variants of epoch-change, *gracious* and *ungracious* epoch change. 

### Gracious epoch-change {#sec:gracious}

A gracious epoch change occurs when the protocol delivers the maximal number of batches in an epoch.  Its goal is to implement a lightweight mechanism for potentially growing the set of leaders towards a epoch, and to implement a variant of the bucket rotation to ensure Liveness across epochs. 

After the primary of epoch $e+1$ ($\epprim(e+1)$) delivers all batches in an epoch $e$ (or, as an optimization, shortly before), $\epprim(e+1)$ *reliably broadcast* the *configuration* of epoch $e+1$. To this end, we use the classical 3-phase Bracha reliable broadcast [@Bracha:1985:ACB:4221.214134]. 

The epoch configuration information, which the primary reliably broadcasts, contains: 1) the set of epoch leaders for the new epoch, 2) identifiers of buckets that the primary picked for itself, derived from the oldest requests pending at the primary.  Recall that, if $e$ ends graciously, the leader set cannot reduce in size and it grows if the primary of epoch $e+1$ believes that more than $|\eplead(e)|$ nodes are correct.  In this case, the primary proposes $min(StableLeaders,\eplead(e)+1)$ nodes, chosen by the primary.  In case the primary of epoch $e+1$ estimates that no more than $|\eplead(e)|$ nodes are correct, it is allowed to maintain the same set of leaders as in the previous epoch — this avoids frequent oscillations between gracious and ungracious epoch changes, e.g.,in case few nodes are crash-faulty. 

Finally, similar to bucket handover (Sec.  \[sec:rotation\]), leader $i$ in epoch $e+1$ starts proposing batches, as soon as it delivers all batches from $e$ from nodes that were assigned the buckets now assigned to $i$.

### Ungracious epoch-change {#sec:untimely}

*Ungracious* epoch-changes in are caused by epoch timeouts due to asynchrony or failures and generalize PBFT view-changes.  Similar to PBFT, after delivering batch $sn$ in epoch $e$, a node resets and triggers an epoch-change timer $ecTimer$. supports adaptive timeouts.  To set $ecTimer$, a node locally estimates the average commit rate and sets the timeout proportional to the median commit time of a batch.  If an $ecTimer$ expires, a node enters the epoch-change subprotocol to move from epoch $e$ to epoch $e+1$. In this case, a node sends an <span style="font-variant:small-caps;">EPOCH-CHANGE</span> message to the primary of epoch $e+1$. <span style="font-variant:small-caps;">EPOCH-CHANGE</span> message follows the structure of PBFT <span style="font-variant:small-caps;">VIEW-CHANGE</span> message (page 411, [@Castro:2002:PBF]) with the difference that it is signed and that there are no <span style="font-variant:small-caps;">VIEW-CHANGE-ACK</span> messages exchanged (to streamline and simplify the implementation similarly to [@Castro:1999:ABF]).  The construction of the <span style="font-variant:small-caps;">NEW-EPOCH</span> message then proceeds in the same way as the PBFT construction of the <span style="font-variant:small-caps;">NEW-VIEW</span> message. 

Before triggering the PBFT-inherited processing of <span style="font-variant:small-caps;">NEW-EPOCH</span> message, nodes wait to reliably deliver configuration information pertaining to the new epoch, which the primary reliably broadcasts, just like in gracious epoch change (Sec.  \[sec:gracious\]).  The difference is that in an ungracious epoch change the epoch primary must select a *smaller number* of epoch leaders than in the previous epoch.  Concretely, in the configuration for new epoch $e$, the epoch primary picks the number of leaders in the last epoch $e'$ for which it has the configuration, and proposes at most $max(1,|\eplead(e')-e+e'|$ leaders.  Note that the epoch primary must always be in the epoch leader set. 

Finally, to counter the possibility of losing requests due to an epoch change, a node *resurrects* potentially pre-prepared but uncommitted requests from previous views that are not reflected in the <span style="font-variant:small-caps;">NEW-EPOCH</span> message.  Indeed, when an epoch change occurs, not all batches that were created and potentially preprepared before this event are delivered when installing the new epoch.  To prevent the requests in these batches from being lost (due to condition (6) in pre-preparing a batch — Sec.  \[sec:stable\]), before resuming normal operation after an ungracious epoch change, each correct node ensures that (1) the requests in such batches are returned to node’s pending buckets, and (2) these requests are removed from the logs of the node where they were marked as preprepared.  Thus, these requests are ready to be proposed again.  Together with the requirement that clients ensure that a correct replica eventually receives their request, this guarantees Liveness (P4), i.e., that client requests are eventually delivered, even in the face of view changes. 

Checkpointing (Garbage Collection) {#sec:checkpoint}
----------------------------------

Similarly to PBFT, uses a checkpoint mechanism to prune the message logs.  After each node $i$ has delivered a batch with sequence number $sn_C$ divisible by configuration parameter $C$ (which means that all batches with sequence numbers lower than $sn_C$ have been locally committed at $i$) node $i$ broadcasts a $\langle\checkpointmsg,sn_C,H(sn_C')\rangle\sigma_i$, where $sn_C'$ the last checkpoint and $H(sn_C')$ is the hash digest of the batches with sequence numbers $sn$ in range $sn_C'\le sn <sn_C$. Each node collects checkpoint messages until it has $2\faults+1$, including its own, and persists a *checkpoint certificate*.  At this point, the checkpoint is *stable* and the node can discard the common-case messages from its log for sequence numbers lower than $sn$.

advances batch watermarks at checkpoints like PBFT does.  Clients’ watermarks are also possibly advanced at checkpoints, as the state related to previously delivered requests is discarded.  For each client $c$, the low watermark $t_{c_L}$ advances to the highest timestamp $t$ in a request submitted by $c$ that has been delivered, such that all requests with timestamp $t'<t$ have also been delivered.  The high watermark advances to $t_{c_H}=w_c+t_{c_L}$, where $w_c$ the length of the sliding window. 

Note that node $i$ does not discard the validated requests that are pending in the bucket queues.  These are removed from the pending queue either when it proposes the request in a message or when the request is committed, as explained in section \[sec:stable\]. 

Implementation Architecture {#sec:implementation}
---------------------------

We implemented in Go.  Our implementation is multi-threaded and inspired by *consensus-oriented parallelism* (COP) architecture previously applied to PBFT to maximize its throughput on multicore machines [@BehlDK15].  Specifically, in our implementation, a separate thread is dedicated to managing each batch during the common case operation, which simplifies code structure and helps maximize performance.  We further parallelize computation-intensive tasks whenever possible (e.g., signature verifications, hash computations).  The only communication in common case between threads pertains to request duplication prevention – the shared data structures for duplication prevention are hash tables, with per-bucket locks; instances that handle requests corresponding to different leaders do not access the same buckets.  The only exception to the multi-threaded operation of is during an ungracious epoch-change, where a designated thread (Manager) is responsible for stopping worker common-case threads and taking the protocol from one epoch to the next.  This manager thread is also responsible for sequential batch delivery and for checkpointing, which however does not block the common-case threads managing batches. 

Our implementation also parallelizes network access.  We use a configurable number of independent network connections between each pair of servers, which results in several gRPC connections between each pair of servers (the number of gRPC connections between a pair of servers is, however, considerably smaller than the number of threads).  This proves to be critical in boosting performance beyond seeming bandwidth limitations in a WAN that stem from using a single TCP/TLS connection.  In addition to multiple internode connections, we use an independent connection for handling client requests.  As a result, the receipt of requests is independent of the rest of the protocol – we can safely continue to receive client requests even if the protocol is undergoing an epoch change.  Our implementation can hence seamlessly use, where possible, separate NICs for client’s requests and intranode communication to address DoS attacks [@Clement:2009:MBF:1558977.1558988]. 

Finally, cleaning-up duplication prevention-related data structures at checkpoint is a relatively expensive operation; yet because the watermark distance is larger than the checkpoint period, BFT instances can still proceed even when handling a checkpoint — therefore, this does not significantly affect throughput. 

Optimizations {#sec:optimizations}
=============

Lightweight Total Order (LTO) {#sec:LTO}
-----------------------------

When the system is network-bound (e.g., with large requests and/or on a WAN) the maximum throughput is driven by the amount of data each leader can broadcast in a message.  However, data, i.e., request payload, is not critical for total order, as the nodes can establish total order on request hashes.  While in many blockchains all nodes need data [@BitcoinURL; @EthereumURL], in some others [@AndroulakiBBCCC18], ordering is separated from request execution and full replication across ordering nodes is an overkill. 

For such blockchains, optionally boosts throughput using what we call *Light Total Order (LTO)* broadcast.  LTO is defined in the same way as TO broadcast (Sec.  \[sec:model\]) except that LTO requires property $P4$ to hold for hash of the request $H(r)$ instead for request $r$ and adds the following property:

P5 **Partial Replication:** If a correct client broadcasts $r$, then *at least one correct node* eventually delivers $r$.

1.   **Partial Replication:** If a correct client broadcasts request $r$, then *at least one correct node* eventually delivers $r$.

LTO optimization for modifies the protocol as follows.  Each leader broadcasts a full message only to a set of $\faults+1$ (a leader is always in of its own batch).  To the rest of the nodes, let us call them , the leader broadcasts a lightweight message which contains only metadata about the requests.  This metadata contains: (a) the hash of the request (b) the identifier of the client who submitted the request and (c) the request timestamp.  The request hash is necessary so that each node can remove committed requests from their pending queues.  The client identifier and request timestamp are necessary to guarantee that all nodes advance the watermarks per client in consistently. 

Upon receiving a (Sec.  \[sec:stable\]), must only verify: (a) condition $(1)$: the epoch number of the batch is correct and no other batch has been proposed in the same epoch with the same sequence number and (b) condition $(6)$ to guarantee no duplication.  Conditions (2)-(5) and (7)-(8) ensure that the batch is valid and it is sufficient that one correct node has verified them.  Such a correct verifier will always exist among the set of $2\faults+1$ senders of the messages that each node expects before sending a message. 

Besides LTO, we also evaluated (Sec.  \[sec:evaluation\]) *highly available* LTO (haLTO) variant of , with partial replication to $2\faults+1$ nodes, making data available at at least $\faults+1$ correct nodes. 

Signature Verification Sharding {#sec:sharding}
-------------------------------

As the multi-leader approach addresses network bottlenecks, it often exposes a CPU bottleneck due to relatively costly client signature verification.  To offload CPU, we enable the signature verification sharding optimization.  In short, in a epoch we require that the signatures in each batch are verified by only $\faults+1$ nodes instead of requiring each node to perform a signature verification, while in a epoch, the number of verifiers is $2\faults+1$. In detail, let $\verifiers(sn,e)$ be the set of nodes that are responsible for verifying the transaction signatures of the batch with sequence number $sn$ in epoch $e$. The leader that proposes the batch is always in $\verifiers(sn,e)$. For the other nodes in $\verifiers(sn,e)$ we use a partitioning mechanism similar to the one we introduced for partitioning requests into buckets.  Each *batch* is hashed to a value and the value is mapped to a .  However, unlike with request sharding, where each bucket is assigned to exactly one leader, each is assigned to $\faults+1$ (resp.,  $2f+1$) nodes in a stable (resp., )  epoch. 

A node $i$ upon receiving $\langle\prepreparemsg, sn, e\rangle$ verifies the clients’ signatures in a batch if $i\in\verifiers(sn,e)$ before broadcasting $\langle\preparemsg, sn, e\rangle$. Otherwise, if $i\notin\verifiers(sn,e)$, node $i$ will check only conditions (1)-(7) (see section \[sec:stable\]).  Each node $j$ broadcasts $\langle\commitmsg, sn, e\rangle$ upon receiving $\langle\prepreparemsg, sn, e\rangle$. In a stable epoch, a node waits for $\langle\preparemsg, sn, e\rangle$ from all $\faults+1$ nodes in $\verifiers(sn,e)$ and $\faults$ more messages. 

![ image](WAN500.pdf){width="\linewidth"}

![ image](WAN3500.pdf){width="\linewidth"}

Evaluation {#sec:evaluation}
==========

In this section, we report on experiments we conducted in scope of performance evaluation.  Our evaluation aims at answering the following questions: (1) how does scale on a WAN? ( 2) how does perform in clusters? ( 3) what is the impact of optimizations? ( 4) what is the impact of duplication prevention mechanism?  and (5) how does perform under faults and performance attacks? 

![ image](MirLAN500.pdf){width="\linewidth"}

![ image](MirLAN3500.pdf){width="\linewidth"}

#### Experimental setup. 

Our evaluation consists of microbenchmarks of 2 request payload sizes: (1) *small*, 500 byte requests, which correspond to average Bitcoin tx size [@BitcoinTXSizeURL], and (2) *large*, 3500 byte requests, typical in Hyperledger Fabric [@AndroulakiBBCCC18]. 

We compare to a state-of-the-art PBFT implementation optimized for multi-cores [@BehlDK15].  For fair comparison, we use the codebase tuned to closely follow the PBFT implementation of [@BehlDK15] hardened to implement Aardvark [@Clement:2009:MBF:1558977.1558988].  As another baseline, we compare the common case performance of Chain, an optimistic subprotocol of the Aliph BFT protocol [@700] with linear message complexity, which is known to be near throughput-optimal in clusters, although it is not robust and needs to be abandoned in case of faults [@700].  PBFT and Chain are always given best possible setups, i.e., PBFT leader is always placed in a node that has most effective bandwidth and Chain spans the path with the smallest latency.  We also compare with Honeybadger [@MillerXCSS16] using the open source implementation[^7] which was also used in the performance evaluation in [@MillerXCSS16].  We only compare Honeybadger with for *small* requests, since the default payload in the open source implementation is fixed to 250 byte requests.  We do not compare to other protocols because they are either unavailable (e.g., Hashgraph [@Hashgraph], Red Belly [@RedBelly]), unmaintained (BFT-Mencius [@BFT-Mencius]), faithfully approximated by PBFT (e.g., BFT-SMaRt [@BessaniSA14], Spinning [@Spinning], Tendermint [@TendermintURL], HotStuff [@hotstuff]), or report considerably worse performance than Mir (e.g., Algorand [@Algorand]). 

We use VMs on a leading cloud provider, with 32 x 2.0 GHz VCPUs and 32GB RAM, equipped with 1Gbps networking .and limited to that value for experiment repeatability, due to non-uniform bandwidth overprovisioning we sometimes experienced.  Table \[table:config\] shows configuration parameters we used.  Unless mentioned differently, uses LTO and signature sharding optimizations. 

Common-case experiments
-----------------------

#### Scalability on WANs. 

To evaluate scalability, we ran it with up to $n=100$ nodes on a WAN setup which spans 16 distinct datacenters across the world (beyond $n=16$, we collocate nodes across already used datacenters).  Figure \[fig:WAN\] depicts the common-case stable epoch performance of , compared to that of PBFT and Chain (for both small and large requests) and Honeybadger (for small requests). 

Client requests are generated by increasing the client instances and request rate per client instance until the throughput is saturated and we report the throughput just below saturation.  Client machines are also uniformly distributed across the 16 datacenters.  The client instances estimate which node $i$ has an active bucket for each of their requests and broadcast each request to nodes $i-1, \cdots, i+k$, where $k\leq f-1$, so at most to $f+1$ nodes. 

We observe that PBFT throughput decays rapidly, following an $O(1/n)$ function and scales very poorly.  Chain scales better and even improves with up to $n=16$ nodes, sustaining 20k (resp.,  3k) tps for small (resp.,  large) requests, but is limited by the bandwidth of the thinner network connection.  Compared to Honeybadger, retains much higher throughput, even though: (i) Honeybadger request size is smaller (250 bytes vs 500 bytes), and (ii) Honeybadger batches are significantly larger (up to 500K requests in our evaluation).  This is due to the fact that Honeybadger is computationally bound by $O(n^2)$ threshold signatures verification and on top of that the verification of the signatures is done sequentially.  Honeybadger’s throughput also suffers from request duplication (on average $1/3$ duplicate requests per batch), since the nodes choose the requests they add in their batches at random.  Moreover, we report on Honeybadger latency, which is in the order of minutes (partly due to the large number of requests per batch and partly due to heavy computation), significantly higher than that of Mir.  In our evaluation we could not increase the batch size as much as in the evaluation in [@MillerXCSS16], especially with increasing the number of nodes beyond $16$, due to memory exhaustion issues.  Finally, in our evaluation PBFT outperforms Honeybadger (unlike in [@MillerXCSS16]), as our implementation of PBFT leverages the parallelism of codebase. 

dominates other protocols delivering 56.4k (resp.,  28.3k) tps with small (resp.,  large) requests with $n=4$ nodes which peaks at 66.3k tps at $n=33$ nodes for small and 36.5k tps at $n=16$ nodes for large requests, due to more effective payload and signature sharding as the number of nodes increases.  With $n=100$, maintains more than 60k tps for small transactions, as for this payload size CPU is the main bottleneck at 100 nodes.  For large requests, where network bandwidth is the bottleneck, throughput reduces to 16.3k with 100 nodes, a drop which we attribute in part to the heterogeneity of VMs across datacenters (despite the identical specifications) and most importantly to the non-uniform partition of the available uplink bandwidth.  Nevertheless, delivers the best performance of all protocols to date with 100 nodes on a WAN, even compared to very optimistic protocols such as Chain. 

#### Performance in a single datacenter. 

Figure \[fig:LAN\] depicts fault-free performance in a single datacenter with up to $n=100$ nodes.  For small requests, Chain dominates delivering roughly 1.6x the peak throughput (130k tps vs 83k tps).  This difference is due to signature verification in (Chain uses vectors of MACs to authenticate a request to $\faults+1$ replicas).  Indeed, as soon as we add clients’ signatures to Chain (ChainSigs in Fig.  \[fig:LAN\]), Chain’s throughput drops below that of .  maintains more than 80k tps throughput for small requests, significantly outperforming PBFT.  For large requests delivers 28.9k tps on $n=100$ nodes, as in a cluster the uplink bandwidth is more uniformly distributed. 

#### Impact of optimizations and bucket rotation. 

In this experiment (see Fig.  \[fig:LT\]) we fix $n=16$ and run detailed fault-free latency-throughput experiments on a WAN for and its variants.  We also show the performance of Chain and PBFT as a reference.  Nodes are distributed over $16$ distinct datacenters across the world. 

robust bucket rotation (Sec.  \[sec:rotation\], “Mir (vanilla)” in Fig.  \[fig:LT\]) saturates at roughly 42.8k (resp.,  21.1k) tps for small (resp.,  large) requests, an approximate overhead of 3.9% (resp.,  4.8%) compared to an idealized non-robust vanilla (“Mir-NoRotation”) which involves no bucket rotation.  This is more than compensated by optimizations (Sec.  \[sec:optimizations\]).  With signature sharding and LTO (“Mir-LTO”), achieves a peak throughput of 36.7k tps for large transactions (delivering 1Gbps goodput), while with highly available LTO (“Mir-haLTO”) achieves 26.3k tps.  For small transactions, LTO does not considerably improve performance at this scale because bandwidth is not the bottleneck (hence not shown), but signature sharding boosts up to 62.9k tps. 

All variants of maintain roughly 1s (low load) to 2s (high load) end-to-end latency.  PBFT latency is lower at 600-800 ms, yet PBFT saturates under very low load in terms. 

![ image](LatencyThroughput-WAN-n16-500.pdf){width="\linewidth"}

![ image](LatencyThroughput-WAN-n16-3500.pdf){width="\linewidth"}

![ The impact of duplication prevention on 16 nodes on WAN for 500B requests.[]{data-label="fig:duplicates500"}](figures/LatencyGoodput-WAN-n16-500.pdf){width="\columnwidth"}

Impact of duplication prevention
--------------------------------

In this section we examine the impact of duplicate transactions to *goodput*, i.e., throughput of unique transactions.  In Fig.  \[fig:duplicates500\] we compare the performance of Mir (vanilla), to a version of the protocol where the leaders do not partition requests in buckets, but rather add in batches all their available requests (similarly to Hashgraph [@Hashgraph] and Red Belly [@RedBelly]).  We examine the impact of duplicates in an optimistic scenario, where the clients submit their transactions to only $f+1$ nodes, as well as in a scenario where the clients sent their requests to all.  The impact is a heavy penalty of 65% and 85%, respectively, for Bitcoin size requests and is similar for large requests. 

Performance under faults {#sec:evalfaults}
------------------------

![ image](figures/test_faults.pdf){width="85.00000%"}

#### Performance under standard crash faults. 

We now describe the behavior of when leader crashes occur.  Figure \[fig:faults\] presents the evolution of throughput as a function of time when one and two leaders fail simultaneously.  We run this experiment in a WAN setting with 16 nodes, and trigger a view change if an expected batch is not delivered within 20 seconds.  When there is one leader failure, a view change is triggered and the system immediately transitions to a configuration with 15 leaders, and a virtually optimal throughput.  When two failures occur simultaneously, the first view changes takes the system to a configuration with 15 leaders.  The first few batches are delivered in this configuration, but, since one of the 15 leaders has failed, a second view change is triggered that takes the system to a configuration with 14 leaders, from which execution can continue.  In this scenario, the figure also depicts the evolution of the leader set in case the failed nodes return online: within three epochs, the system is in a stable state with 16 leaders again. 

We can observe that *gracious* epoch changes are seamless in (these occur from second 141 onwards in the experiment with 2 faults, and are described in Sec.  \[sec:gracious\]), whereas *ungracious* epoch changes (when throughput drops to $0$ due to actual faults, see Sec.  \[sec:untimely\]) last in the order of epoch change timeouts. 

![ Mean and tail latencies (99%) for increasing number of Byzantine leaders that drop 20% of their transactions.[]{data-label="fig:censoring500"}](figures/censorship_resistance500.pdf){width="\columnwidth"}

#### Resistance to request censoring (Byzantine leaders).  

In this experiment we emulated Byzantine behavior by having an increasing number (from $0$ to $f=5$) of Byzantine leaders dropping (censoring) requests, in a deployment of $n=16$ nodes in our WAN setup.  The Byzantine nodes drop $20\%$ of the transactions they receive.  Fig.  \[fig:censoring500\] shows that mean latency remains below 2.2s (resp.,  2.7s) when clients submit to $3f+1$ (resp.,  $f+1$) nodes, while tail latencies (99th percentile) remain below 11s (resp.,  12).  The trade-off in throughput, as discussed in Sec.  \[sec:optimizations\], due to bucket rotation is minimal. 

#### Resistance to delays (Byzantine leaders). 

A common performance attack discussed in BFT literature is when Byzantine leaders reduce the throughput by delaying proposing batches marginally less than the view-change timeout [@Clement:2009:MBF:1558977.1558988].  Rotating leader protocols partially address this, since the Byzantine nodes can delay batches only once over $n$ rounds.  Similarly, in each leader is responsible only for a fraction of the requests, reducing vulnerability to this attack. 

Adaptive timeouts (Sec.  \[sec:untimely\]) allow to detect fast such Byzantine leaders and remove them from the leaderset.  A Byzantine node can delay the protocol only once every $n$ epochs, at which point it becomes epoch primary and adds itself back to the leaderset.  With non-adaptive, conservative, timeouts (30s), for 3500B requests, we evaluate that throughput drops from 20k tps to 10k tps, while with adaptive timeouts throughput drops to 14k tps.  The performance can be further improved by increasing epoch length with a trade-off on increasing tail latencies. 

Related Work {#sec:relwork}
============

The seminal PBFT [@Castro:2002:PBF] protocol started intensive research on practically feasible BFT protocols.  Performance-wise, PBFT has a single-leader bottleneck and does not scale with the number of nodes.  generalizes PBFT and removes this bottleneck with a multi-leader approach enforcing a robust request duplication prevention.  Request duplication elimination is simple in PBFT and other single-leader protocols, which require the leader to enforce it. 

Aardvark [@Clement:2009:MBF:1558977.1558988] was the one the first BFT protocols, along with [@Spinning; @Prime; @RBFT], to point out the importance of BFT protocol *robustness*, i.e., sustainable liveness in presence of active denial of service and performance attacks.  In practice, Aardvark is a hardened PBFT protocol, and uses clients’ signatures, regular periodic view-changes (rotating primary) and resource isolation using separate NICs for separating client-node from node-node traffic.  implements all of these and is robust in Aardvark sense.  Beyond Aardvark-like features, is the first protocol that combines robustness with multiple leaders, preventing request duplication performance attacks, paving the way for ’s excellent performance. 

The first replication protocol to point out the importance of multiple leaders was Mencius [@Mencius] in the context of crash-failures.  Mencius is a Paxos-style [@Lamport:1998:PP:279227.279229] protocol which leverages multiple leaders to reduce the latency of replication on WANs, the approach which was later followed by other crash-tolerant protocols (e.g., EPaxos [@Moraru:2013:MCE:2517349.2517350]).  The approach was extended to the BFT context by BFT-Mencius [@BFT-Mencius].  Mencius and BFT-Mencius are geared towards optimizing latency and shard clients’ requests by mapping a client to a closest node.  However, as a node can censor the request, a client is forced, in the worst case, to re-transmit the request to other nodes which creates a vulnerability to request duplication attacks which BFT-Mencius does not handle. ,  instead, maps clients’ requests to buckets which are then assigned to nodes, not unlike consistent hashing [@Karger:1997:CHR:258533.258660].  further rotates bucket assignment in time to enforce robustness to request duplication.  Unlike Mencius, EPaxos and BFT-Mencius, does not optimize for latency, paying a small price as it does not assign clients to the closest nodes — however, our experiments show that this impact is acceptable, in particular given that the blockchain is not the most latency-sensitive application. 

Recent BFT protocols, proposed in the blockchain context [@RedBelly; @Hashgraph], that exhibit multi-leader flavor, also do not address request duplication.  Furthermore, unlike , these proposals invent new BFT protocols from scratch which is a highly error-prone and tedious process [@700].  In contrast, follows an evolutionary rather then revolutionary design approach to a multi-leader protocol, building upon proven PBFT/Aardvark algorithmic and systems’ constructs, which considerably simplifies the reasoning about correctness. 

HotStuff [@hotstuff] is a BFT protocol which requires linear numbers of messages both during normal case operation and during view change.  However, as we observed in this work, at the scale targeted by , message complexity is not an issue in practice.  As a trade-off for linear message complexity, normal case operation in HotStuff requires an additional phase of communication.  Additionally, HotStuff uses a pipelined design with rotating leaders, leading to a slight improvement in throughput when compared to PBFT.  Nevertheless, HotStuff does not escape the fundamental downside of PBFT we address in this paper, i.e., sequential (albeit from different leaders) broadcasts of proposals, and therefore follows a similar, infavorable scalability trend as PBFT. 

*Optimistic* BFT protocols [@700; @Zyzzyva] have been showed to be very efficient on a small-scale in clusters.  In particular Aliph [@700], is a combination of Chain crash-tolerant replication [@Chain] ported to BFT and backed by PBFT/Aardvark outside the optimistic case, in which all nodes are correct.  We demonstrated that holds its ground with BFT Chain in clusters and it considerably outperforms it in WANs.  Nevertheless, remains compatible with the modular approach to building the optimistic BFT protocols of [@700], where can be used as a robust and high-performance backup protocol.  Zyzzyva [@Zyzzyva] is an optimistic leader-based protocol that optimizes for latency.  While we opted to implement based on PBFT, variants based on Zyzzyva latency-efficient communication pattern are conceivable with our approach. 

Eventually synchronous BFT protocols, to which belongs, circumvent the FLP consensus impossibility result [@FLP] by assuming eventual synchrony.  These protocols, included, guarantee safety despite asynchrony but rely on eventual synchrony to provide liveness.  Alternatively, probabilistic BFT protocols such as Honeybadger [@MillerXCSS16] provide both safety and liveness (except with negligible probability) in purely asynchronous networks.  By comparing Honeybadger and , we showed that this comes as a tradeoff, as significantly outperforms Honeybadger, even though both protocols target the same deployment setting (up to 100 nodes in a WAN). 

As blockchains brought an arms-race to BFT protocol scalability [@Vukolic15], many proposals focus on large, Bitcoin-like scale, with thousands or tens of thousands of nodes [@Algorand; @Bitcoin-NG].  In particular, Algorand [@Algorand] is a recent BFT protocol that deals with BFT agreement in populations of thousands of nodes, by relying on a verifiable random function to select a committee in the order of hundred(s) of node.  Algorand then runs a smaller scale agreement protocol inside a committee.  We foresee being a candidate for this “in-committee” protocol inside a system such as Algorand as well as in other blockchains that effectively restrict voting to a smaller group of nodes, as is the case in e.g., Proof of Stake proposals [@CasperFFG].  In addition, is particularly interesting to permissioned blockchains, such as Hyperledger Fabric [@AndroulakiBBCCC18].  Stellar[@stellar] uses SCP, a Byzantine agreement protocol which uses assymetric quorums and trust assumptions targetting payment networks, at similar scales as .  However, assymmetric quorums weaken both the trust assumptions and the liveness guarantees of traditional BFT protocols.  In this paper, we show it is possible to obtain high throughput and low latencies while maintaining the strong guarantees of BFT protocols with symmetric quorums. 

Finally, another class of protocols [@elastico; @omniledger] partition transaction verification into independent shards.  is complementary to such protocols, as they either require ordering within a shard, or total ordering of the shards.  The committees that perform this ordering are similar in size to the ones targeted by .  Additionally, sharding protocols either require knowledge of the application to ensure conflicting transactions cannot belong to different shards [@omniledger], or conflicts among already verified transactions need to be detected at ordering [@elastico]. 

[10]{}

Algorand.  <http://www.algorand.com>. 

Bitcoin.  <http://bitcoin.org>. 

The [C]{}orda [P]{}latform.  <https://www.r3.com/corda-platform/>. 

Ethereum.  <http://ethereum.org>. 

.  <http://grpc.io>. 

Hyperledger.  <http://www.hyperledger.org>. 

Tendermint.  <http://tendermint.com>. 

Daily hodl: Cryptocurrency transaction speeds: The complete review.  <https://dailyhodl.com/2018/04/27/cryptocurrency-transaction-speeds-the-complete-review/>, 2018. 

Bitcoin visuals: Transaction sizes.  <https://bitcoinvisuals.com/chain-tx-size>, 2019. 

anada: What is the role of a block producer?  <https://www.eoscanada.com/en/what-is-the-role-of-a-block-producer>, 2019. 

A. S. Aiyer, L. Alvisi, A. Clement, M. Dahlin, J.-P. Martin, and C. Porth.  Bar fault tolerance for cooperative services. ,  39(5):45–58, Oct. 2005. 

Y. Amir, Y. Amir, B. Coan, J. Kirsch, and J. Lane.  Byzantine replication under attack.  In [*Proceedings of the Conference on Dependable Systems and Networks ([DSN]{})*]{}, 2008. 

E. Androulaki, A. Barger, V. Bortnikov, C. Cachin, K. Christidis, A. D. Caro, D. Enyeart, C. Ferris, G. Laventman, Y. Manevich, S. Muralidharan, C. Murthy, B. Nguyen, M. Sethi, G. Singh, K. Smith, A. Sorniotti, C. Stathakopoulou, M. Vukolic, S. W. Cocco, and J. Yellick.  Hyperledger fabric: a distributed operating system for permissioned blockchains.  In [*Proceedings of the Thirteenth EuroSys Conference, EuroSys 2018, Porto, Portugal, April 23-26, 2018*]{}, pages 30:1–30:15, 2018. 

P. Aublin, S. B. Mokhtar, and V. Qu[é]{}ma.  redundant [B]{}yzantine fault tolerance.  In [*[IEEE]{} 33rd International Conference on Distributed Computing Systems, [ICDCS]{} 2013, 8-11 July, 2013, Philadelphia, Pennsylvania, [USA]{}*]{}, pages 297–306, 2013. 

P.-L. Aublin, R. Guerraoui, N. Knežević, V. Qu[é]{}ma, and M. Vukolić.  The next 700 [BFT]{} protocols. ,  32(4):12:1–12:45, Jan. 2015. 

J. Behl, T. Distler, and R. Kapitza.  Consensus-oriented parallelization: How to earn your first million.  In [*Proceedings of the 16th Annual Middleware Conference, Vancouver, BC, Canada, December 07 - 11, 2015*]{}, pages 173–184, 2015. 

A. N. Bessani, J. Sousa, and E. A. P. Alchieri.  State machine replication for the masses with [BFT-SMART]{}.  In [*International Conference on Dependable Systems and Networks (DSN)*]{}, pages 355–362, 2014. 

G. Bracha and S. Toueg.  Asynchronous consensus and broadcast protocols. ,  32:824–840, October 1985. 

E. Buchman.  Tendermint: [Byzantine]{} fault tolerance in the age of blockchains.  M.Sc.  Thesis, University of Guelph, Canada, June 2016. 

V. Buterin and V. Griffith.  Casper the friendly finality gadget. ,  abs/1710.09437, 2017. 

M. Castro and B. Liskov.  Authenticated [B]{}yzantine fault tolerance without public-key cryptography.  Technical Report MIT/LCS/TM-589, MIT Laboratory for Computer Science, 1999. 

M. Castro and B. Liskov.  Practical byzantine fault tolerance.  In [*Proceedings of the Third Symposium on Operating Systems Design and Implementation*]{}, OSDI ’99, pages 173–186, Berkeley, CA, USA, 1999.  USENIX Association. 

M. Castro and B. Liskov.  Practical [B]{}yzantine fault tolerance and proactive recovery. ,  20(4):398–461, Nov. 2002. 

A. Clement, E. L. Wong, L. Alvisi, M. Dahlin, and M. Marchetti.  Making byzantine fault tolerant systems tolerate byzantine faults.  In [*Proceedings of the 6th [USENIX]{} Symposium on Networked Systems Design and Implementation, [NSDI]{} 2009*]{}, pages 153–168, 2009. 

T. Crain, C. Natoli, and V. Gramoli.  Evaluating the [R]{}ed [B]{}elly blockchain. ,  abs/1812.11747, 2018. 

K. Croman, C. Decker, I. Eyal, A. E. Gencer, A. Juels, A. E. Kosba, A. Miller, P. Saxena, E. Shi, E. G. Sirer, D. Song, and R. Wattenhofer.  On scaling decentralized blockchains - [(A]{} position paper).  In [*Financial Cryptography and Data Security - [FC]{} 2016 International Workshops, BITCOIN, VOTING, and WAHC, Christ Church, Barbados, February 26, 2016, Revised Selected Papers*]{}, pages 106–125, 2016. 

C. Dwork, N. Lynch, and L. Stockmeyer.  Consensus in the presence of partial synchrony. ,  35(2):288–323, Apr. 1988. 

I. Eyal, A. E. Gencer, E. G. Sirer, and R. V. Renesse.  Bitcoin-ng: A scalable blockchain protocol.  In [*13th [USENIX]{} Symposium on Networked Systems Design and Implementation ([NSDI]{} 16)*]{}, pages 45–59, Santa Clara, CA, 2016. 

M. J. Fischer, N. A. Lynch, and M. S. Paterson.  Impossibility of distributed consensus with one faulty process. ,  32(2):374–382, Apr. 1985. 

A. Gervais, G. O. Karame, K. W[ü]{}st, V. Glykantzis, H. Ritzdorf, and S. Capkun.  On the security and performance of proof of work blockchains.  In [*Proceedings of the 2016 [ACM]{} [SIGSAC]{} Conference on Computer and Communications Security, Vienna, Austria, October 24-28, 2016*]{}, pages 3–16, 2016. 

Y. Gilad, R. Hemo, S. Micali, G. Vlachos, and N. Zeldovich.  Algorand: Scaling [B]{}yzantine agreements for cryptocurrencies.  In [*Proceedings of the 26th Symposium on Operating Systems Principles*]{}, pages 51–68.  ACM, 2017. 

D. Karger, E. Lehman, T. Leighton, R. Panigrahy, M. Levine, and D. Lewin.  Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the world wide web.  In [*Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing*]{}, STOC ’97, pages 654–663, 1997. 

A. Kiayias, A. Russell, B. David, and R. Oliynykov.  Ouroboros: A provably secure proof-of-stake blockchain protocol.  In J. Katz and H. Shacham, editors, [*Advances in Cryptology – CRYPTO 2017*]{}, pages 357–388, Cham, 2017.  Springer International Publishing. 

E. Kokoris[-]{}Kogias, P. Jovanovic, L. Gasser, N. Gailly, E. Syta, and B. Ford.  Omniledger: [A]{} secure, scale-out, decentralized ledger via sharding.  In [*2018 [IEEE]{} Symposium on Security and Privacy, [SP]{} 2018, Proceedings, 21-23 May 2018, San Francisco, California, [USA]{}*]{}, pages 583–598, 2018. 

R. Kotla, L. Alvisi, M. Dahlin, A. Clement, and E. Wong.  Zyzzyva: speculative [B]{}yzantine fault tolerance.  In [*Proceedings of the [S]{}ymposium on [O]{}perating [S]{}ystems [P]{}rinciples (SOSP)*]{}.  ACM, 2007. 

.  The [S]{}wirlds [H]{}ashgraph consensus algorithm: Fair, fast, [B]{}yzantine fault tolerance.  <https://www.swirlds.com/downloads/SWIRLDS-TR-2016-01.pdf>, 2016. 

L. Lamport.  The part-time parliament. ,  16:133–169, May 1998. 

L. Lamport, R. Shostak, and M. Pease.  The [Byzantine]{} generals problem. ,  4:382–401, July 1982. 

L. Luu, V. Narayanan, C. Zheng, K. Baweja, S. Gilbert, and P. Saxena.  A secure sharding protocol for open blockchains.  In [*Proceedings of the 2016 [ACM]{} [SIGSAC]{} Conference on Computer and Communications Security, Vienna, Austria, October 24-28, 2016*]{}, pages 17–30, 2016. 

Y. Mao, F. P. Junqueira, and K. Marzullo.  Mencius: Building efficient replicated state machines for wans.  In [*Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation*]{}, OSDI’08, pages 369–384, Berkeley, CA, USA, 2008.  USENIX Association. 

D. Maziéres.  The [S]{}tellar consensus protocol: A federated model for internet-level consensus.  https://www.stellar.org/papers/stellar-consensus-protocol.pdf, November 2015. 

A. Miller, Y. Xia, K. Croman, E. Shi, and D. Song.  The honey badger of [BFT]{} protocols.  In [*Proceedings of the 2016 [ACM]{} [SIGSAC]{} Conference on Computer and Communications Security, Vienna, Austria, October 24-28, 2016*]{}, pages 31–42, 2016. 

Z. Milosevic, M. Biely, and A. Schiper.  Bounded delay in byzantine-tolerant state machine replication.  In [*[IEEE]{} 32nd Symposium on Reliable Distributed Systems, [SRDS]{} 2013, Braga, Portugal, 1-3 October 2013*]{}, pages 61–70, 2013. 

I. Moraru, D. G. Andersen, and M. Kaminsky.  There is more consensus in egalitarian parliaments.  In [*Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles*]{}, SOSP ’13, pages 358–372, New York, NY, USA, 2013.  ACM. 

.  Bitcoin: A peer-to-peer electronic cash system. 

F. B. Schneider.  Implementing fault-tolerant services using the state machine approach: A tutorial. ,  22(4):299–319, 1990. 

R. van Renesse and F. B. Schneider.  Chain replication for supporting high throughput and availability.  In [*Proceedings of the Symposium on Operating Systems Design and Implementation (OSDI)*]{}, 2004. 

G. S. Veronese, M. Correia, A. N. Bessani, and L. C. Lung.  Spin one’s wheels? [ B]{}yzantine [F]{}ault [T]{}olerance with a spinning primary.  In [*Proceedings of International [S]{}ymposium on Reliable Distributed Systems (SRDS)*]{}.  IEEE Computer Society, 2009. 

M. Vukolić.  The quest for scalable blockchain fabric: Proof-of-work vs. [BFT]{} replication.  In [*International Workshop on Open Problems in Network Security (iNetSec)*]{}, pages 112–125, 2015. 

G. Wood.  Ethereum: A secure decentralised generalised transaction ledger.  <http://gavwood.com/paper.pdf>, 2016. 

M. Yin, D. Malkhi, M. K. Reiter, G. Golan[-]{}Gueta, and I. Abraham.  Hotstuff: [BFT]{} consensus with linearity and responsiveness.  In [*Proceedings of the 2019 [ACM]{} Symposium on Principles of Distributed Computing, [PODC]{} 2019, Toronto, ON, Canada, July 29 - August 2, 2019.*]{},  pages 347–356, 2019. 

Correctness Arguments {#sec:correctness}
=====================

In this section we sketch correctness arguments, focusing on TO properties, as defined in Section \[sec:model\], discussing also the impact of optimizations (Sec.  \[sec:optimizations\]). 

*Validity* (P1) relies on clients’ signatures which uses to authenticate the requests.  Without signature sharding, every signature is verified by at least $2\faults+1$ nodes, out of which $\faults+1$ are correct.  With signature sharding, clients’ signatures are verified by at least $\faults+1$ nodes, out of which at least one is correct — guaranteeing Validity. 

*Agreement* (P2) is best shown by contradiction and reduction to PBFT Agreement, which we outline here.  Suppose that Agreement does not hold in ; in this case, because of the structure which generalizes PBFT, there exists an execution of PBFT similar to that of , in which: 1) all requests proposed in a epoch are proposed in the respective PBFT view by the primary, 2) every gracious epoch change in is replaced by view-change in PBFT due to timeouts, and 3) there is an Agreement violation in PBFT.  A contradiction. 

*No-duplication* (P3) stems from the way prevents duplicate pre-prepares (rule (6) in accepting , Sec/ \[sec:stable\]).  The exception to this rule, in form of batch/request resurrection during ungracious epoch change (Sec.  \[sec:untimely\]), does not impact P3, as only requests from uncommitted batches as resurrected. 

*Liveness* (P4) can be shown by contradiction as follows.  Assume a correct client sends a request to all nodes, which is received by at least one correct node $i$. Fix $req$ to be the oldest request received by $i$ for which liveness is broken.  Consider time after $GST$. It is easy to show that in , either (1) $i$ becomes an epoch primary infinitely often, or (2) there is the *last* epoch $e$, a stable epoch that runs infinitely long.  In case (1), let $e$ be an epoch in which $req$ is the oldest request pending at node $i$ and $i$ is the primary (such an epoch exists due to the choice of $req$ and the resurrection of uncommitted but pre-prepared requests (Sec.  \[sec:untimely\])).  In case (2), $i$ gets to be the leader infinitely often in $e$ including being the leader of a bucket $req$ belongs to.  In both cases, $req$ gets proposed by $i$ and is committed (system runs after $GST$), a contradiction. 

Signature sharding (Sec.  \[sec:sharding\]) optimization does not compromise Validity/Agreement.  In case of a epoch, we expect all the nodes to be alive, since all nodes are in set.  Therefore, we expect that all $\faults+1$ messages from nodes that verify siggnatures will arrive.  If they do not, the batch timer will expire and enters an epoch.  In case of an epoch, $2\faults+1$ nodes will verify every client’s request.  As the set of $2\faults+1$ nodes that sent and messages intersect with the set of verifiers in at least $f+1$ nodes in an epoch, at least one of these will be a correct node. 

Similarly, it is easy to see that LTO optimization (Sec.  \[sec:LTO\]) yields Liveness (P4) on hashes and ensures Partial Replication (P5, Sec.  \[sec:LTO\]) on request payloads. 

State Transfer, Reconfiguration and Durability {#sec:otherthings}
==============================================

State transfer {#sec:statetransfer}
--------------

Nodes can temporarily become unavailable, either due to asynchrony, or due to transient failures.  Upon recovery/reconnection, replicas must obtain several pieces of information before being able to actively participate in the protocol again.  To achieve this, replicas need to obtain current epoch configuration information, the latest stable checkpoint (which occurred at the round having sequence $h$), as well as information concerning proposals having sequence numbers between $h+1$ and the current round $n$.

The state must, in particular, contain two pieces of information: (1) the current epoch configuration, which is necessary to determine the leaders from which the replica should accept proposals, and (2) client timestamps at the latest checkpoint, which are necessary to prevent including client requests that have already been proposed in future batches. 

A reconnecting replica $i$ obtains this information by broadcasting a $\langle HELLO, ne_i, c_i, b_i\rangle$ message, where $ne_i$ is the latest NEW-EPOCH message received by the replica, $c_i$ is the replica’s last stable checkpoint, and $b_i$ is the last batch $i$ delivered.  Upon receipt of a $HELLO$ message, another replica $j$ replies with its own $HELLO$ message, as well as with any missing state from the last stable checkpoint and up to the current round $n$.

We perform further optimizations in order to reduce the amount of data that needs to be exchanged in case of a reconnection.  First, upon reconnecting, replicas announce their presence but wait for the next stable checkpoint after reconnection before actively participating in the protocol again.  This enables us to avoid transferring the entire state related to requests following the preceding stable checkpoint.  Second, the amount of data related to client timestamps that needs to be transmitted can be reduced through only exchanging the root of the Merkle tree containing the client timestamps, with the precise timestamps being fetched on a per-need basis. 

Membership reconfiguration
--------------------------

While details of membership reconfiguration are outside of the scope of this paper, we briefly describe how deals with adding/removing clients and nodes.  Such requests, called *configuration* requests are totally ordered like other requests, but are tagged to be interpretable/executed by nodes (hence they are not subject to the LTO optimization, Sec.  \[sec:LTO\]).  As processes requests out of order (just like PBFT), configuration requests cannot be executed right after committing a request as the timing of commitment might diverge across nodes resulting in non-determinism.  Instead, configuration requests are taken into account only at checkpoints and more specifically all configuration requests ordered between checkpoints $k-1$ and $k$, take effect only after checkpoint $k+1$.

Durability (persisting state)
-----------------------------

By default, implementation does not persist state or message logs to stable storage.  Hence, a node that crashes might recover in a compromised state — however such a node does not participate in the protocol until the next stable checkpoint which effectively restores the correct state.  While we opted for this approach assuming that for few dozens of nodes simultaneous faults of up to a third of them will be rare, for small number of nodes the probability of such faults grows and with some probability might exceed threshold $\faults$. Therefore, we optionally persist state pertaining to *sent* messages in , which is sufficient for a node to recover to a correct state after a crash. 

We also evaluated the impact of durability with $4$ nodes, in a LAN setting, where it is mostly relevant due to small number of nodes and potentially collocated failures, using small transactions.  We find that durability has no impact on total throughput, mainly due to the fact that persisted messages are amortized due to batching, parallel architecture and the computation-intensive workload.  However, average request latency increases by roughly 300ms. 

[^1]: Here, relies on the original PBFT UDP-oriented logic to deal with potential re-ordering that stems from using multiple connections. 

[^2]: variants based on other BFT protocols can be derived as well. 

[^3]: Here, relies on the original PBFT UDP-oriented logic to deal with potential re-ordering that stems from using multiple connections. 

[^4]: variants based on other BFT protocols can be derived as well. 

[^5]: More elaborate leader set choices, which are outside the scope of this paper, can take into account execution history, fault patterns, weighted voting, distributed randomness, or blockchain stake. 

[^6]: Incentives, e.g., transaction fees [@Bitcoin; @EthereumYellowPaper], could help with request censoring in case of a rational adversary [@Aiyer:2005:BFT:1095809.1095816], potentially simplifying .  Here, we focus on the more challenging (“irrational”) adversary. 

[^7]: <https://github.com/initc3/HoneyBadgerBFT-Python>
