Asymptotically Optimal Validated Asynchronous Byzantine Agreement

Abstract

We provide a new protocol for Validated Asynchronous Byzantine Agreement in the authenticated setting. Validated (multi-valued) Asynchronous Byzantine Agreement is a key building block in constructing Atomic Broadcast and fault-tolerant state machine replication in the asynchronous setting. Our protocol has optimal resilience of ƒ < n/3 Byzantine failures and asymptotically optimal expected O(1) running time to reach agreement. Honest parties in our protocol send only an expected O(n2) messages where each message contains a value and a constant number of signatures. Hence our total expected communication is O(n2) words. The best previous result of Cachin et al. from 2001 solves Validated Byzantine Agreement with optimal resilience and O(1) expected time but with O(n3) expected word communication. Our work addresses an open question of Cachin et al. from 2001 and improves the expected word communication from O(n3) to asymptotically optimal O(n2).