  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)$.
