Speeding Dumbo: Pushing Asynchronous BFT Closer to Practice

Asynchronous BFT consensus can implement robust mission-critical decentralized services network without relying on any form of timing assumption. Starting from the work of HoneyBadgerBFT (CCS 2016), several studies tried to push asynchronous BFT towards practice. In a recent work of Dumbo (CCS 2020), they redesigned the protocol backbone and used one multi-valued validated Byzantine agreement (MVBA) to replace n concurrent asynchronous binary agreement (ABA) protocols and dramatically improved the performance. Despite those efforts, asynchronous BFT protocols remain to be slow, and in particular, the latency is still quite large. There are two reasons contributing to the inferior performance: (1) the reliable broadcast (RBC) protocols still incur substantial costs; (2) the MVBA protocols are quite complicated and heavy, and all existing constructions need dozens of rounds and take the majority of the overall latency.

We first present a new construction of asynchronous BFT that replaces RBC instance with a cheaper broadcast component. It not only reduces the O (n³) message complexity incurred by n RBCs to O (n²), but also saves up to 67% communications (in the presence of a fair network scheduler). Moreover, our technical core is a new MVBA protocol, Speeding MVBA, which is concretely more efficient than all existing MVBAs. It requires only 6 rounds in the best case and expected 12 rounds in the worst case (by contrast, several dozens of rounds in the MVBA from Cachin et al. [12] and the recent Dumbo-MVBA [33], and around 20 rounds in the MVBA from Abraham et al. [4]). Our new technique of the construction might be of independent interests.

We implemented Speeding Dumbo and did extensive tests among up to 150 EC2 t2.medium instances evenly allocated in 15 AWS regions across the globe. The experimental results show that Speeding Dumbo reduces the latency to about a half of Dumbo's, and also doubles the throughput of Dumbo, through all system scales from 4 nodes to 150 nodes. We also did tests to benchmark individual components such as the broadcasts and the MVBA protocols, which may be of interests for future improvements.

© 2022 29th Annual Network and Distributed System Security Symposium, NDSS 2022. All Rights Reserved.