Dumbo-MVBA: Optimal Multi-Valued Validated Asynchronous Byzantine Agreement, RevisitedsMulti-Valued Validated Asynchronous Byzantine Agreement • August 20th, 2020
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(ln2 + λn2 + n3) communication (where n is the number of parties, l 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 l ≥ λn, and thus the communication is dominated by the ln2 term and the problem raised by Cachin et al. remains open.
