Asynchronous byzantine agreement with subquadratic communication

Understanding the communication complexity of Byzantine agreement (BA) is a fundamental problem in distributed computing. In particular, for protocols involving a large number of parties (as in, e.g., the context of blockchain protocols), it is important to understand the dependence of the communication on the number of parties \(n\). Prior to our work, adaptively secure BA protocols with \(o(n^2)\) communication were known in the synchronous and partially synchronous settings, but no such protocols were known in the fully asynchronous case.

We show asynchronous BA protocols with (expected) subquadratic communication complexity tolerating an adaptive adversary who can corrupt \(f<(1-\epsilon)n/3\) of the parties (for any \(epsilon\)). One protocol assumes initial setup done by a trusted dealer, after which an unbounded number of BA executions can be run; alternately, we can achieve subquadratic amortized communication with no prior setup. We also show that some form of setup is needed for (non-amortized) subquadratic BA tolerating \(\Theta(n)\) corrupted parties. (In concurrent work, Cohen, Keidar, and Spigelman also present a protocol for adaptively secure subquadratic BA. Their work makes use of different assumptions: they consider a non-standard network model that places a mild restriction on the adversary’s ability to reorder messages, but on the other hand are able to forgo the stronger computational assumptions and trusted dealer used by our approach.)

As a contribution of independent interest, we show a secure-computation protocol in the same threat model that has \(o(n^2)\) communication when computing no-input functionalities with short output (e.g., coin tossing).