Paper 2020/851

Asynchronous Byzantine Agreement with Subquadratic Communication

Erica Blum, Jonathan Katz, Chen-Da Liu-Zhang, and Julian Loss


Understanding the communication complexity of Byzantine agreement (BA) is a fundamental problem in distributed computing. In particular, as protocols are run with a large number of parties (as, e.g., in the context of blockchain protocols), it is important to understand the dependence of the communication on the number of parties $n$. Although adaptively secure BA protocols with $o(n^2)$ communication are known in the synchronous and partially synchronous settings, no such protocols are known in the fully asynchronous case. We show here an asynchronous BA protocol with subquadratic communication tolerating an adaptive adversary who can corrupt $f<(1-\epsilon)n/3$ of the parties (for any $\epsilon>0$). One variant of our 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. 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).

Available format(s)
Publication info
Published by the IACR in TCC 2020
byzantine agreementsubquadratic communication
Contact author(s)
erblum @ cs umd edu
jkatz2 @ gmail com
lichen @ inf ethz ch
lossjulian @ gmail com
2020-10-06: last of 2 revisions
2020-07-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Erica Blum and Jonathan Katz and Chen-Da Liu-Zhang and Julian Loss},
      title = {Asynchronous Byzantine Agreement with Subquadratic Communication},
      howpublished = {Cryptology ePrint Archive, Paper 2020/851},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.