TY - GEN
T1 - Dumbo-MVBA
T2 - 39th Symposium on Principles of Distributed Computing, PODC 2020
AU - Lu, Yuan
AU - Lu, Zhenliang
AU - Tang, Qiang
AU - Wang, Guiling
N1 - Publisher Copyright:
© 2020 ACM.
PY - 2020/7/31
Y1 - 2020/7/31
N2 - 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(ℓn2 + λn2 + n3) communication (where n is the number of parties, ℓ is the input length, and λ is the security parameter). Recently, Abraham et al. (PODC '19) removed the n3 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 ℓ ≥ λn, and thus the communication is dominated by the ℓn2 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(ℓn + λn2) communicated bits, which is optimal when ℓ ≥ λn. 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(n2) 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.
AB - 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(ℓn2 + λn2 + n3) communication (where n is the number of parties, ℓ is the input length, and λ is the security parameter). Recently, Abraham et al. (PODC '19) removed the n3 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 ℓ ≥ λn, and thus the communication is dominated by the ℓn2 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(ℓn + λn2) communicated bits, which is optimal when ℓ ≥ λn. 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(n2) 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.
UR - http://www.scopus.com/inward/record.url?scp=85090361471&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85090361471&partnerID=8YFLogxK
U2 - 10.1145/3382734.3405707
DO - 10.1145/3382734.3405707
M3 - Conference contribution
AN - SCOPUS:85090361471
T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
SP - 129
EP - 138
BT - PODC 2020 - Proceedings of the 39th Symposium on Principles of Distributed Computing
PB - Association for Computing Machinery
Y2 - 3 August 2020 through 7 August 2020
ER -