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

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

By admin