Validated Asynchronous Byzantine Agreement with Optimal Resilience and Asymptotically Optimal Time and Word Communication
share
We provide a new protocol for Validated Asynchronous Byzantine Agreement. 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 can withstand the optimal number f<n/3 of Byzantine failures and reaches agreement in the asymptotically optimal expected O(1) running time. Honest parties in our protocol send only an expected O(n^2) messages where each message contains a value and a constant number of signatures. Hence our total expected communication is O(n^2) 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(n^3) expected word communication. Our work addresses an open question of Cachin et al. from 2001 and improves the expected word communication from O(n^3) to the asymptotically optimal O(n^2).
READ FULL TEXT