Abstract

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

Mir-BFT is the first BFT protocol that allows multiple leaders to propose request batches independently (i.e., parallel leaders), while effectively precluding performance degradation due to request duplication by rotating the assignment of a partitioned request hash space to leaders. As this mechanism removes the single-leader bandwidth bottleneck and exposes a computation bottleneck related to authenticating clients 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 signed Bitcoin-sized (500-byte) transactions per second on a widely distributed setup (100 nodes, 1 Gbps WAN) with typical latencies of few seconds. Moreover, our evaluation exposes the impact of duplicate requests on parallel leader protocols which Mir-BFT eliminates. We also evaluate Mir-BFT un-der different crash and Byzantine faults, demonstrating its performance robustness.

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