A Fast and Practical Sector-Based BFT Consensus With Sublinear Communication Complexity

Byzantine fault-tolerant (BFT) consensus protocols are the core components of blockchain. In the process of improving the performance of BFT protocols, existing work faces the following three problems: 1) the binary dilemma between the leader’s performance bottleneck in star-based linear communication and compromised resilience in tree-based sublinear communication; 2) two- or three-round protocols restrict the phase number of one proposal, thereby limiting the number of concurrent proposals and causing high latency. 3) The fixed timeout makes the protocol sensitive to varying network delays. Therefore, this paper proposes Crackle, the first sector-based pipelined BFT protocol with a sublinear communication complexity, for a throughput improvement of consensus protocol with max resilience of (N -1)/3. We propose a sector-based communication mode to disseminate messages from the leader to a subset of replicas in each phase to accelerate consensus and split the traditional two-round protocol into 2κ phases to increase the basic pipeline scale. We refine the timer strategy so that the timeout Δ is adjusted with the proposal submission to cope with the changing network environment. We then address two technical challenges: 1) to ensure Quorum Certificate (QC) validation, we design a voteMap s field within each block, and verify QC by the signature aggregation of voteMap s in continuous κ phases; and 2) to achieve pipeline decoupling among shorter phases, we propose a vote-appending mechanism that relaxes the conditions for the leader to send new proposals. We provide comprehensive theoretical proof of the correctness of Crackle, including safety and liveness. Moreover, we implement Crackle based on a public BFT framework and deploy it on 64 cloud servers. Real experimental results reveal that our Crackle protocol achieves up to 10.36x higher throughput and can dynamically adapt to network delay compared with state-of-the-art BFT protocols such as Kauri and Hotstuff.