Leaderless Byzantine Fault Tolerant Consensus

Byzantine fault tolerant (BFT) consensus has recently gained much attention because of its intriguing connection with blockchains. Several state-of-the-art BFT consensus protocols have been proposed in the age of blockchains such as Tendermint [5], Pala [9], Streamlet [8], HotStuff [23], and Fast-HotStuff [17]. These protocols are all leader-based (i.e., protocols run in a series of views, and each view has a delegated node called the leader to coordinate all consensus decisions). To make progress, leader-based BFT protocols usually rely on view synchronization, which is an ad-hoc way of rotating the leader and synchronizing nodes to the same view with the leader for enough overlap time. However, many studies and system implementations show that existing methods of view synchronization are complicated and bug-prone [2], [15], [16], [19]. In this paper, we aim to design a leaderless Byzantine fault tolerant (LBFT) protocol, in which nodes simply compete to propose blocks (containing a batch of clients' requests) without the need of explicit coordination through view synchronization. LBFT also enjoys several other desirable features emphasized recently by the research community, such as the chain structure, pipelining techniques, and advanced cryptography [5], [6], [9], [17], [23]. With these efforts, LBFT can achieve both good performance (e.g., O(n)or O(nlog(n)) message complexity) and prominent simplicity.