You are looking at a specific version 20200712:144344 of this paper. See the latest version.

Paper 2020/841

Dumbo: Faster Asynchronous BFT Protocols

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

Abstract

HoneyBadgerBFT, proposed by Miller et al. [32] 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 $k$ (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 [32] 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. will appear at ACM CCS 2020
Keywords
Dumboatomic broadcastasynchronousprotocol
Contact author(s)
guobingyong @ tca iscas ac cn,zl425 @ njit edu,qiang @ njit edu,xujing @ tca iscas ac cn,zfzhang @ tca iscas ac cn
History
2020-08-15: last of 2 revisions
2020-07-12: received
See all versions
Short URL
https://ia.cr/2020/841
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.