CryptoDB
Breaking the $O(\sqrt{n})$-Bit Barrier: Byzantine Agreement with Polylog Bits Per Party
| Authors: | |
|---|---|
| Download: | |
| Abstract: | 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 BA protocols with the best overall communication, the demands of the parties are highly unbalanced : the amortized cost is $${\tilde{O}}(1)$$ O ~ ( 1 ) bits per party, but some parties must send $$\Omega (n)$$ Ω ( n ) bits. In best known balanced protocols, the overall communication is sub-optimal, with each party communicating $${\tilde{O}}(\sqrt{n})$$ O ~ ( 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)$$ O ~ ( 1 ) bits? Our contributions in this line are as follows: We define a cryptographic primitive— succinctly reconstructed distributed signatures (SRDS)—that suffices for constructing $${\tilde{O}}(1)$$ O ~ ( 1 ) balanced BA. We provide two constructions of SRDS from different cryptographic and public-key infrastructure (PKI) assumptions. 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. 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, toward minimizing per-party communication of BA. In particular, we construct the first two BA protocols with $${\tilde{O}}(1)$$ O ~ ( 1 ) balanced communication, offering a trade-off between setup and cryptographic assumptions and answering an open question presented by King and Saia (DISC’09). |
BibTeX
@article{jofc-2023-33820,
title={Breaking the $$O(\sqrt{n})$$-Bit Barrier: Byzantine Agreement with Polylog Bits Per Party},
journal={Journal of Cryptology},
publisher={Springer},
volume={37},
doi={10.1007/s00145-023-09484-0},
author={Elette Boyle and Ran Cohen and Aarushi Goel},
year=2023
}