2020/02/06 by Elette Boyle, Boyle, Elette, Ran Cohen +3
Computer Science · #Algorithms and Data Compression #Cryptography and Data Security #Cryptography and Security (cs.CR) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2002.02516
openalex publication_date 2020/02/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 O(1) bits per party, but some parties must send Ω(n) bits. In best known balanced protocols, the overall communication is sub-optimal, with each party communicating O(√(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 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 O(1) balanced communication, offering a tradeoff between setup and cryptographic assumptions, and answering an open question presented by King and Saia (DISC'09).