Dumbo: Faster Asynchronous BFT Protocols

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

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

113 Scopus citations


HoneyBadgerBFT, proposed by Miller et al. [34] as the first practical asynchronous atomic broadcast protocol, demonstrated impressive performance. The core of HoneyBadgerBFT (HB-BFT) is to achieve batching consensus using asynchronous common subset protocol (ACS) of Ben-Or et al., constituted with n reliable broadcast protocol (RBC) to have each node propose its input, followed by n asynchronous binary agreement protocol (ABA) to make a decision for each proposed value (n is the total number of nodes). In this paper, we propose two new atomic broadcast protocols (called Dumbo1, Dumbo2) both of which have asymptotically and practically better efficiency. In particular, the ACS of Dumbo1 only runs a small ? (independent of n) instances of ABA, while that of Dumbo2 further reduces it to constant! At the core of our techniques are two major observations: (1) reducing the number of ABA instances significantly improves efficiency; and (2) using multi-valued validated Byzantine agreement (MVBA) which was considered sub-optimal for ACS in [34] in a more careful way could actually lead to a much more efficient ACS. We implement both Dumbo1, Dumbo2 and deploy them as well as HB-BFT on 100 Amazon EC2 t2.medium instances uniformly distributed throughout 10 different regions across the globe, and run extensive experiments in the same environments. The experimental results show that our protocols achieve multi-fold improvements over HoneyBadgerBFT on both latency and throughput, especially when the system scale becomes moderately large.

Original languageEnglish (US)
Title of host publicationCCS 2020 - Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security
PublisherAssociation for Computing Machinery
Number of pages16
ISBN (Electronic)9781450370899
StatePublished - Oct 30 2020
Event27th ACM SIGSAC Conference on Computer and Communications Security, CCS 2020 - Virtual, Online, United States
Duration: Nov 9 2020Nov 13 2020

Publication series

NameProceedings of the ACM Conference on Computer and Communications Security
ISSN (Print)1543-7221


Conference27th ACM SIGSAC Conference on Computer and Communications Security, CCS 2020
Country/TerritoryUnited States
CityVirtual, Online

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Networks and Communications


  • asynchronous network
  • atomic broadcast
  • byzantine fault tolerance


Dive into the research topics of 'Dumbo: Faster Asynchronous BFT Protocols'. Together they form a unique fingerprint.

Cite this