JUMBOJUMBO: Fully Asynchronous BFT Consensus Made Truly Scalable

Recent progresses in asynchronous Byzantine fault-tolerant (BFT) consensus, e.g. <tex-math notation="LaTeX">Dumbo-NG</tex-math> (CCS' 22) and <tex-math notation="LaTeX">Tusk</tex-math> (EuroSys' 22), show promising performance through decoupling transaction dissemination and block agreement. However, when executed with a larger number <tex-math notation="LaTeX">n</tex-math> 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 <tex-math notation="LaTeX">O(n)</tex-math> 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 <tex-math notation="LaTeX">FIN-NG</tex-math> 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 <tex-math notation="LaTeX">FIN-NG</tex-math> relies on our non-trivial redesign of FIN's multi-valued validated Byzantine agreement towards achieving optimal quality. <tex-math notation="LaTeX">FIN-NG</tex-math> greatly improves the performance of FIN and already outperforms <tex-math notation="LaTeX">Dumbo-NG</tex-math> in most deployment settings. To further overcome the scalability limit of <tex-math notation="LaTeX">FIN-NG</tex-math> due to <tex-math notation="LaTeX">O(n³)</tex-math> messages, we propose <tex-math notation="LaTeX">JUMBO</tex-math>, a scalable instantiation of <tex-math notation="LaTeX">Dumbo-NG</tex-math>, with only <tex-math notation="LaTeX">O(n²)</tex-math> complexities for both authenticators and messages. We use various aggregation and dispersal techniques for QCs to significantly reduce the authenticator complexity of original <tex-math notation="LaTeX">Dumbo-NG</tex-math> implementations by up to <tex-math notation="LaTeX">O(n²)</tex-math> orders. Finally, we implement our designs in Golang and experimentally demonstrated their enhanced scalability with hundreds of Amazon's AWS instances. <tex-math notation="LaTeX">JUMBO</tex-math> and FIN-NG significantly outperform the state-of-the-art in (nearly) all deployment settings. Especially, when <tex-math notation="LaTeX">n≥</tex-math>196, <tex-math notation="LaTeX">JUMBO</tex-math> can attain a throughput that is more than 4× that of FIN and <tex-math notation="LaTeX">Dumbo-NG</tex-math>.