Paper 2020/842
Dumbo-MVBA: Optimal Multi-valued Validated Asynchronous Byzantine Agreement, Revisited
Yuan Lu, Zhenliang Lu, Qiang Tang, and Guiling Wang
Abstract
Multi-valued validated asynchronous Byzantine agreement (MVBA), proposed in the elegant work of Cachin et al. (CRYPTO '01), is fundamental for critical fault-tolerant services such as atomic broadcast in the asynchronous network. It was left as an open problem to asymptotically reduce the $O(ln^2+n^2*lambda+n^3)$ communication (where $n$ is the number of parties, $l$ is the input length, and $lambda$ is the security parameter). Recently, Abraham et al. (PODC '19) removed the $n^3$ term to partially answer the question when input is small. However, in other typical cases, e.g., building atomic broadcast through MVBA, the input length $l >= n*lambda$, and thus the communication is dominated by the $ln^2$ term and the problem raised by Cachin et al. remains open. We fill the gap and answer the remaining part of the above open problem. In particular, we present two MVBA protocols with $O(ln+n^2*lambda)$ communicated bits, which is optimal when $l >= n*lambda$. We also maintain other benefits including optimal resilience to tolerate up to $n/3$ adaptive Byzantine corruptions, optimal expected constant running time, and optimal $O(n^2)$ messages. At the core of our design, we propose asynchronous provable dispersal broadcast (APDB) in which each input can be split and dispersed to every party and later recovered in an efficient way. Leveraging APDB and asynchronous binary agreement, we design an optimal MVBA protocol, Dumbo-MVBA; we also present a general self-bootstrap framework Dumbo-MVBA* to reduce the communication of any existing MVBA protocols.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. MINOR revision.ACM PODC 2020
- DOI
- 10.1145/3382734.3405707
- Keywords
- Byzantine agreementexternal validityasynchronous networkoptimal protocol
- Contact author(s)
-
yl768 @ njit edu
zl425 @ njit edu
qiang @ njit edu
gwang @ njit edu - History
- 2020-08-20: last of 3 revisions
- 2020-07-12: received
- See all versions
- Short URL
- https://ia.cr/2020/842
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/842, author = {Yuan Lu and Zhenliang Lu and Qiang Tang and Guiling Wang}, title = {Dumbo-MVBA: Optimal Multi-valued Validated Asynchronous Byzantine Agreement, Revisited}, howpublished = {Cryptology ePrint Archive, Paper 2020/842}, year = {2020}, doi = {10.1145/3382734.3405707}, note = {\url{https://eprint.iacr.org/2020/842}}, url = {https://eprint.iacr.org/2020/842} }