文章基本信息

标题：Scalable and Secure Computation Among Strangers: Message-Competitive Byzantine Protocols
本地全文：下载
作者：John Augustine ; Valerie King ; Anisur Rahaman Molla 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：179
页码：1-19
DOI：10.4230/LIPIcs.DISC.2020.31
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Byzantine protocols; Byzantine agreement; Leader election; Committee election; Message-competitive protocol; Randomized protocol