Cryptology ePrint Archive: Report 2022/027

Speeding Dumbo: Pushing Asynchronous BFT Closer to Practice

Bingyong Guo and Yuan Lu and Zhenliang Lu and Qiang Tang and Jing Xu and Zhenfeng Zhang

Abstract: Asynchronous BFT consensus can implement robust mission-critical decentralized services in the unstable or even adversarial wide-area 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 particular, 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 he 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^3)$ message complexity incurred by $n$ RBCs to $O(n^2)$, 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 [32], 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.

Category / Keywords: cryptographic protocols / Asynchronous protocols, Byzantine-fault tolerance, Blockchain consensus, multi-valued validated agreement

Original Publication (with minor differences): NDSS 22

Date: received 9 Jan 2022, last revised 17 Jan 2022

Contact author: bingyong2017 at iscas ac cn, luyuan at iscas ac cn, zhlu9620 at uni sydney edu au, qiang tang at sydney edu au, xujing at iscas ac cn, zhenfeng at iscas ac cn

Available format(s): PDF | BibTeX Citation

Version: 20220117:062122 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]