Paper 2020/130

Breaking the $O(\sqrt n)$-Bit Barrier: Byzantine Agreement with Polylog Bits Per Party

Elette Boyle, Reichman University and NTT Research
Ran Cohen, Reichman University
Aarushi Goel, NTT Research

Byzantine agreement (BA), the task of $n$ parties to agree on one of their input bits in the face of malicious agents, is a powerful primitive that lies at the core of a vast range of distributed protocols. Interestingly, in protocols with the best overall communication, the demands of the parties are highly unbalanced: the amortized cost is $\tilde O(1)$ bits per party, but some parties must send $\Omega(n)$ bits. In best known balanced protocols, the overall communication is sub-optimal, with each party communicating $\tilde O(\sqrt{n})$. In this work, we ask whether asymmetry is inherent for optimizing total communication. In particular, is BA possible where each party communicates only $\tilde O(1)$ bits? Our contributions in this line are as follows: 1) We define a cryptographic primitive---succinctly reconstructed distributed signatures (SRDS)---that suffices for constructing $\tilde O(1)$ balanced BA. We provide two constructions of SRDS from different cryptographic and Public-Key Infrastructure (PKI) assumptions. 2) The SRDS-based BA follows a paradigm of boosting from "almost-everywhere" agreement to full agreement, and does so in a single round. Complementarily, we prove that PKI setup and cryptographic assumptions are necessary for such protocols in which every party sends $o(n)$ messages. 3) We further explore connections between a natural approach toward attaining SRDS and average-case succinct non-interactive argument systems (SNARGs) for a particular type of NP-Complete problems (generalizing Subset-Sum and Subset-Product). Our results provide new approaches forward, as well as limitations and barriers, towards minimizing per-party communication of BA. In particular, we construct the first two BA protocols with $\tilde O(1)$ balanced communication, offering a tradeoff between setup and cryptographic assumptions, and answering an open question presented by King and Saia (DISC'09).

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. PODC 2021
Byzantine agreementcommunication complexity
Contact author(s)
elette boyle @ runi ac il
cohenran @ runi ac il
aarushi goel @ ntt-research com
2023-10-20: last of 6 revisions
2020-02-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Elette Boyle and Ran Cohen and Aarushi Goel},
      title = {Breaking the $O(\sqrt n)$-Bit Barrier: Byzantine Agreement with Polylog Bits Per Party},
      howpublished = {Cryptology ePrint Archive, Paper 2020/130},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.