Limitless Scalability: A High-Throughput and Replica-Agnostic BFT Consensus

Traditional Byzantine Fault Tolerance (BFT) consensus protocols adopt a star topology with a leader to handle all message transmission, causing performance to degrade rapidly as replicas grow. Recently, many studies have sought to improve scalability by exploring multi-layer topology (e.g., tree structures) to reduce the leader's fanout. However, these approaches either depend on a polynomial fanout to preserve fault tolerance or are constrained by the impact of topology depth on throughput, ultimately leading to only modest scalability gains. To this end, we propose Tide, the first leader-based BFT protocol that maintains robust performance as replica count grows, which is enabled by our design of logarithmic-fanout topology and high-parallel pipelining. Tide utilizes redundant connections as a key insight in topology, reducing fanout without compromising resilience. Tide further introduces a novel pipelining where interlayer interactions dynamically determine the degree of proposal parallelism, thereby decoupling throughput from topology depth. Real-world experiments with 100 cloud servers demonstrate that as the replica count scales from 100 to 1,000, state-of-the-art protocols experience a 65% to 90% decrease in throughput and a 50× increase in latency. In contrast, Tide maintains a replicaagnostic high throughput of around 50ktps, over 5x higher than others, while its latency remains at 0.3s-0.4s.