License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2020.31
URN: urn:nbn:de:0030-drops-131093
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13109/
Augustine, John ;
King, Valerie ;
Molla, Anisur Rahaman ;
Pandurangan, Gopal ;
Saia, Jared
Scalable and Secure Computation Among Strangers: Message-Competitive Byzantine Protocols
Abstract
The last decade has seen substantial progress on designing Byzantine agreement algorithms which do not require all-to-all communication. However, these protocols do require each node to play a particular role determined by its ID. Motivated by the rise of permissionless systems such as Bitcoin, where nodes can join and leave at will, we extend this research to a more practical model where initially, each node does not know the identity of its neighbors. In particular, a node can send to new destinations only by sending to random (or arbitrary) nodes, or responding to messages received from those destinations. We assume a synchronous and fully-connected network, with a full-information, but static Byzantine adversary. A major drawback of existing Byzantine protocols in this setting is that they have at least Ω(n²) message complexity, where n is the total number of nodes. In particular, the communication cost incurred by the honest nodes is Ω(n²), even when Byzantine node send no messages. In this paper, we design protocols for fundamental problems which are message-competitive, i.e., the total number of bits sent by honest nodes is not significantly more than the total sent by Byzantine nodes.
We describe a message-competitive algorithm to solve Byzantine agreement, leader election, and committee election. Our algorithm sends an expected O((T+n)log n) bits and has latency O(polylog(n)) (even in the CONGEST model), where T = O(n²) is the number of bits sent by Byzantine nodes. The algorithm is resilient to (1/4-ε)n Byzantine nodes for any fixed ε > 0, and succeeds with high probability. Our message bounds are essentially optimal up to polylagarithmic factors, for algorithms that run in polylogarithmic rounds in the CONGEST model.
We also show lower bounds for message-competitive Byzantine agreement regardless of rounds. We prove that, in general, one cannot hope to design Byzantine protocols that have communication cost that is significantly smaller than the cost of the Byzantine adversary.
BibTeX - Entry
@InProceedings{augustine_et_al:LIPIcs:2020:13109,
author = {John Augustine and Valerie King and Anisur Rahaman Molla and Gopal Pandurangan and Jared Saia},
title = {{Scalable and Secure Computation Among Strangers: Message-Competitive Byzantine Protocols}},
booktitle = {34th International Symposium on Distributed Computing (DISC 2020)},
pages = {31:1--31:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-168-9},
ISSN = {1868-8969},
year = {2020},
volume = {179},
editor = {Hagit Attiya},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13109},
URN = {urn:nbn:de:0030-drops-131093},
doi = {10.4230/LIPIcs.DISC.2020.31},
annote = {Keywords: Byzantine protocols, Byzantine agreement, Leader election, Committee election, Message-competitive protocol, Randomized protocol}
}
|
Keywords: |
|
Byzantine protocols, Byzantine agreement, Leader election, Committee election, Message-competitive protocol, Randomized protocol |
|
Collection: |
|
34th International Symposium on Distributed Computing (DISC 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
07.10.2020 |
