Group BFT: Two-Round BFT Protocols Via Replica Grouping

This paper seeks to enhance the performance of large-scale leader-based Byzantine Fault Tolerant (BFT) systems by proposing a novel Group BFT scheme. The scheme utilizes a two-round message transmission process to distribute the load from a single leader across multiple replicas by dividing the entire consensus network into groups, each with an equal number of replicas. Each group has a leader to process the group's voting messages into a single aggregated voting message during the first round, which is then transmitted to the consensus leader in the second round (similar process for proposing). We establish a formal system framework for Group BFT protocols with a versatile set of base components and explicit definitions, addressing the challenges inherent in designing such a system. We further design and implement two highly efficient Group BFT protocols: one that supports inter-group member exchange and the other one that does not. We theoretically prove the safety, liveness, and responsiveness of the Group BFT protocols. We conduct a formal analysis of Group BFTs' tolerance and complexity. Experimental results show that the two Group BFT protocols significantly alleviate the processing bottlenecks of the leader and highly improve throughput in large-scale systems.