Speeding Dumbo: Pushing Asynchronous BFT Closer to Practice

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

Abstract

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(n3) message complexity incurred by n RBCs to O(n2), 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.

Original languageEnglish (US)
Title of host publication29th Annual Network and Distributed System Security Symposium, NDSS 2022
PublisherThe Internet Society
ISBN (Electronic)1891562746, 9781891562747
DOIs
StatePublished - 2022
Externally publishedYes
Event29th Annual Network and Distributed System Security Symposium, NDSS 2022 - Hybrid, San Diego, United States
Duration: Apr 24 2022Apr 28 2022

Publication series

Name29th Annual Network and Distributed System Security Symposium, NDSS 2022

Conference

Conference29th Annual Network and Distributed System Security Symposium, NDSS 2022
Country/TerritoryUnited States
CityHybrid, San Diego
Period4/24/224/28/22

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Control and Systems Engineering
  • Safety, Risk, Reliability and Quality

Fingerprint

Dive into the research topics of 'Speeding Dumbo: Pushing Asynchronous BFT Closer to Practice'. Together they form a unique fingerprint.

Cite this