File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/3293611.3331629
- Scopus: eid_2-s2.0-85070940993
- WOS: WOS:000570442000046
Supplementary
- Citations:
- Appears in Collections:
Conference Paper: Communication Complexity of Byzantine Agreement, Revisited
Title | Communication Complexity of Byzantine Agreement, Revisited |
---|---|
Authors | |
Keywords | Adaptive Byzantine agreement Communication complexity Lower bound Multicast |
Issue Date | 2019 |
Publisher | Association for Computing Machinery. |
Citation | Proceedings of the 2019 ACM 38th Symposium on Principles of Distributed Computing (PODC '19), Toronto, ON, Canada, 29 July – 2 August 2019, p. 317-326 How to Cite? |
Abstract | 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 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 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 a new subquadratic binary BA construction (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 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. |
Persistent Identifier | http://hdl.handle.net/10722/290709 |
ISBN | |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Abraham, I | - |
dc.contributor.author | Chan, HTH | - |
dc.contributor.author | Dolev, D | - |
dc.contributor.author | Nayak, K | - |
dc.contributor.author | Pass, R | - |
dc.contributor.author | Ren, L | - |
dc.contributor.author | Shi, D | - |
dc.date.accessioned | 2020-11-02T05:46:00Z | - |
dc.date.available | 2020-11-02T05:46:00Z | - |
dc.date.issued | 2019 | - |
dc.identifier.citation | Proceedings of the 2019 ACM 38th Symposium on Principles of Distributed Computing (PODC '19), Toronto, ON, Canada, 29 July – 2 August 2019, p. 317-326 | - |
dc.identifier.isbn | 9781450362177 | - |
dc.identifier.uri | http://hdl.handle.net/10722/290709 | - |
dc.description.abstract | 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 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 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 a new subquadratic binary BA construction (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 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. | - |
dc.language | eng | - |
dc.publisher | Association for Computing Machinery. | - |
dc.relation.ispartof | Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC '19) | - |
dc.rights | Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC '19). Copyright © Association for Computing Machinery. | - |
dc.subject | Adaptive | - |
dc.subject | Byzantine agreement | - |
dc.subject | Communication complexity | - |
dc.subject | Lower bound | - |
dc.subject | Multicast | - |
dc.title | Communication Complexity of Byzantine Agreement, Revisited | - |
dc.type | Conference_Paper | - |
dc.identifier.email | Chan, HTH: hubert@cs.hku.hk | - |
dc.identifier.authority | Chan, HTH=rp01312 | - |
dc.identifier.doi | 10.1145/3293611.3331629 | - |
dc.identifier.scopus | eid_2-s2.0-85070940993 | - |
dc.identifier.hkuros | 318357 | - |
dc.identifier.spage | 317 | - |
dc.identifier.epage | 326 | - |
dc.identifier.isi | WOS:000570442000046 | - |
dc.publisher.place | New York, NY, USA | - |