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