Journal of Systems Research

This paper presents Mir-BFT, a robust Byzantine fault-tolerant (BFT) total order broadcast protocol aimed at maxi-mizing throughput on wide-area networks (WANs), targetingdeployments in decentralized networks, such as permissionedand Proof-of-Stake permissionless blockchain systems.

Mir-BFT is the first BFT protocol that allows multiple lead-ers to propose request batches independently (i.e., parallelleaders), while effectively precluding performance degrada-tion due to request duplication by rotating the assignmentof a partitioned request hash space to leaders. As this mech-anism removes the single-leader bandwidth bottleneck andexposes a computation bottleneck related to authenticatingclients even on a WAN, our protocol further boosts through-put using a client signature verification sharding optimization.Our evaluation shows that Mir-BFT outperforms state-of-the-art single-leader protocols and orders more than 60000 signedBitcoin-sized (500-byte) transactions per second on a widelydistributed setup (100 nodes, 1 Gbps WAN) with typical la-tencies of few seconds. Moreover, our evaluation exposesthe impact of duplicate requests on parallel leader protocolswhich Mir-BFT eliminates. We also evaluate Mir-BFT un-der different crash and Byzantine faults, demonstrating itsperformance robustness.

Mir-BFT relies on classical BFT protocol constructs, whichsimplifies reasoning about its correctness. Specifically, Mir-BFT is a generalization of the celebrated and scrutinizedPBFT protocol. In a nutshell, Mir-BFT follows PBFT “safety-wise”, with changes needed to accommodate novel featuresrestricted to PBFT liveness.