Skip to main content

We gratefully acknowledge support from
the Simons Foundation and member institutions.
arXiv.org > cs > arXiv:1805.03391
Help | Advanced Search
All fields
Title
Author
Abstract
Comments
Journal reference
ACM classification
MSC classification
Report number
arXiv identifier
DOI
ORCID
arXiv author ID
Help pages
Full text
Search
Computer Science > Distributed, Parallel, and Cluster Computing
[Submitted on 9 May 2018 (v1), last revised 15 Feb 2020 (this version, v4)]
Communication Complexity of Byzantine Agreement, Revisited
Ittai Abraham, T-H. Hubert Chan, Danny Dolev, Kartik Nayak, Rafael Pass, Ling Ren, Elaine Shi
As Byzantine Agreement (BA) protocols find application in large-scale decentralized cryptocurrencies, an increasingly important problem is to design BA protocols with improved communication complexity. A few existing works have shown how to achieve subquadratic BA under an {\it adaptive} adversary. Intriguingly, they all make a common relaxation about the adaptivity of the attacker, that is, if an honest node sends a message and then gets corrupted in some round, the adversary {\it cannot erase the message that was already sent} — henceforth we say that such an adversary cannot perform “after-the-fact removal”. By contrast, many (super-)quadratic BA protocols in the literature can tolerate after-the-fact removal. In this paper, we first prove that disallowing after-the-fact removal is necessary for achieving subquadratic-communication BA.
Next, we show new subquadratic binary BA constructions (of course, assuming no after-the-fact removal) that achieves near-optimal resilience and expected constant rounds under standard cryptographic assumptions and a public-key infrastructure (PKI) in both synchronous and partially synchronous settings. In comparison, all known subquadratic protocols make additional strong assumptions such as random oracles or the ability of honest nodes to erase secrets from memory, and even with these strong assumptions, no prior work can achieve the above properties. Lastly, we show that some setup assumption is necessary for achieving subquadratic multicast-based BA.
Comments:
The conference version of this paper appeared in PODC 2019
Subjects:
Distributed, Parallel, and Cluster Computing (cs.DC)
Cite as:
arXiv:1805.03391 [cs.DC]
(or arXiv:1805.03391v4 [cs.DC] for this version)
Submission history
From: T-H. Hubert Chan [view email]
[v1] Wed, 9 May 2018 07:17:31 UTC (105 KB)
[v2] Sat, 13 Oct 2018 03:21:14 UTC (103 KB)
[v3] Thu, 28 Feb 2019 07:12:03 UTC (55 KB)
[v4] Sat, 15 Feb 2020 11:16:39 UTC (76 KB)
Download:
• PDF
• Other formats
(license)
Current browse context:
cs.DC
< prev | next >
new | recent | 1805
Change to browse by:
cs
References & Citations
• NASA ADS
• Google Scholar
• Semantic Scholar
DBLP – CS Bibliography
listing | bibtex
T.-H. Hubert Chan
Rafael Pass
Elaine Shi
Export Bibtex Citation
Bookmark
   
Bibliographic Tools
Bibliographic and Citation Tools
Bibliographic Explorer Toggle
Bibliographic Explorer (What is the Explorer?)
Code
Related Papers
About arXivLabs
Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)
About
Help
contact arXivClick here to contact arXiv
Contact
subscribe to arXiv mailingsClick here to subscribe
Subscribe
Copyright
Privacy Policy
Web Accessibility Assistance
arXiv Operational Status
Get status notifications via email or slack