JUMBO: Fully Asynchronous BFT Consensus Made Truly Scalable

Recent progresses in asynchronous Byzantine fault-tolerant (BFT) consensus, e.g., Dumbo-NG (CCS' 22) and Tusk (EuroSys' 22), show promising performance through decoupling transaction dissemination and block agreement. However, when executed with a larger number n of nodes, like several hundreds, they would suffer from significant degradation in performance. Their dominating scalability bottleneck is the huge authenticator complexity: each node has to multicast O(n) quorum certificates (QCs) and subsequently verify them for each block. This paper systematically investigates and resolves the above scalability issue. We first propose a signature-free asynchronous BFT consensus FIN-NG that adapts a recent signature-free asynchronous common subset protocol FIN (CCS' 23) into the state-of-the-art framework of concurrent broadcast and agreement. The liveness of FIN-NG relies on our non-trivial redesign of FIN's multi-valued validated Byzantine agreement towards achieving optimal quality. FIN-NG greatly improves the performance of FIN and already outperforms Dumbo-NG in most deployment settings. To further overcome the scalability limit of FIN-NG due to O(n³) messages, we propose JUMBO, a scalable instantiation of Dumbo-NG, with only O(n²) complexities for both authenticators and messages. We use various aggregation and dispersal techniques for QCs to significantly reduce the authenticator complexity of original Dumbo-NG implementations by up to O(n²) orders. Finally, we implement our designs in Golang and experimentally demonstrated their enhanced scalability with hundreds of Amazon's AWS instances. JUMBO and FIN-NG significantly outperform the state-of-the-art in (nearly) all deployment settings. Especially, when n ≥ 196, JUMBO can attain a throughput that is more than 4× that of FIN and Dumbo-NG. © 2004-2012 IEEE.