Crackle: A Fast Sector-based BFT Consensus with Sublinear Communication Complexity

Abstract

Blockchain systems widely employ Byzantine fault-tolerant (BFT) protocols to ensure consistency. Improving BFT protocols’ throughput is crucial for large-scale blockchain systems. Frontier protocols face crucial problems: (i) the binary dilemma between leader bottleneck in star-based linear communication and compromised resilience in tree-based sublinear communication; and (ii) 2- or 3-round protocols restrict the phase number of one proposal, thereby limiting the scalability and parallelism of the pipeline. To overcome the above problems, 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. When implementing Crackle, we address two technical challenges: (i) to ensure Quorum Certificate (QC) validation during continuous κ phases, we design a voteMap field within each block, and verify QC by the aggregation of continuous κ voteMaps; and (ii) to achieve pipeline decoupling among shorter phases, we propose a vote-appending mechanism that accelerates the leader’s transition to the next phase. 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 Crackle achieves up to 10.36x higher throughput compared with state-of-the-art BFT protocols such as Kauri and Hotstuff.