$\mathsf {JUMBO}$JUMBO: Fully Asynchronous BFT Consensus Made Truly Scalable
Hao Cheng, Yuan Lu, Zhenliang Lu, Qiang Tang, Yuxuan Zhang, Zhenfeng Zhang · IEEE Transactions on Dependable and Secure Computing · 2025
Recent progresses in asynchronous Byzantine fault-tolerant (BFT) consensus, e.g.$\mathsf {Dumbo}\textrm {-}\mathsf {NG}$(CCS' 22) and$\mathsf {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$\mathcal {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$\mathsf {FIN}\textrm {-}\mathsf {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$\mathsf {FIN}\textrm {-}\mathsf {NG}$relies on our non-trivial redesign of FIN's multi-valued validated Byzantine agreement towards achieving optimal quality.$\mathsf {FIN}\textrm {-}\mathsf {NG}$greatly improves the performance of FIN and already outperforms$\mathsf {Dumbo}\textrm {-}\mathsf {NG}$in most deployment settings. To further overcome the scalability limit of$\mathsf {FIN}\textrm {-}\mathsf {NG}$due to$\mathcal {O}(n^{3})$messages, we propose$\mathsf {JUMBO}$, a scalable instantiation of$\mathsf {Dumbo}\textrm {-}\mathsf {NG}$, with only$\mathcal {O}(n^{2})$complexities for both authenticators and messages. We use various aggregation and dispersal techniques for QCs to significantly reduce the authenticator complexity of original$\mathsf {Dumbo}\textrm {-}\mathsf {NG}$implementations by up to$\mathcal {O}(n^{2})$orders. Finally, we implement our designs in Golang and experimentally demonstrated their enhanced scalability with hundreds of Amazon's AWS instances.$\mathsf {JUMBO}$and FIN-NG significantly outperform the state-of-the-art in (nearly) all deployment settings. Especially, when$n\ge$196,$\mathsf {JUMBO}$can attain a throughput that is more than 4× that of FIN and$\mathsf {Dumbo}\textrm {-}\mathsf {NG}$.