Options
A Fully-Distributed Scalable Peer-to-Peer Protocol for Byzantine-Resilient Distributed Hash Tables
Date Issued
11-07-2022
Author(s)
Abstract
Performing computation in the presence of faulty and malicious nodes is a central problem in distributed computing. Over 35 years ago, Dwork, Peleg, Pippenger, and Upfal [STOC 1986, SICOMP 1988] studied the fundamental Byzantine agreement problem in sparse, bounded degree networks and presented the first protocol that achieved almost-everywhere agreement among good nodes. However, this protocol and several subsequent protocols including that of King, Saia, Sanwalani, and Vee [FOCS 2006] had the drawback that they were not fully-distributed - in those protocols, nodes are required to have initial knowledge of the entire network topology. This drawback makes such protocols not applicable to real-world communication networks such as peer-to-peer (P2P) networks, which are typically sparse and bounded degree and where nodes initially have only local knowledge of themselves and of their neighbors. In thiswork,we present the first scalable, fully-distributed Byzantine protocol for sparse, bounded degree, P2P networks that can tolerate a large number of Byzantine nodes. We assume that the Byzantine nodes can behave arbitrarily and maliciously, have unlimited computational power, and may collude among themselves. However, they are oblivious to (direct) communication between good nodes, i.e., we assume the existence of private channels, but make no cryptographic assumptions. In particular, Byzantine nodes do have knowledge of the messages sent by good nodes if those messages go through a Byzantine node. As is standard in P2P networks, we assume that nodes can communicate with each other if they know their identities. Our main contribution is a (randomized) fully-distributed protocol that guarantees with high probability the construction of an addressable P2P network that can be used to build a distributed hash table (DHT) that enables efficient, robust, and reliable storage and search of data even in the presence of up to n/polylog n number of Byzantine nodes (where n is the total number of nodes). Furthermore, our protocol is scalable, in the sense that it incurs only polylog n overhead - only polylog n bits need to be processed and sent by each node per round and any node's computation cost per round is also polylog n and the protocol takes polylog n rounds. To the best of our knowledge, this is the first-known, fullydistributed P2P protocol in sparse networks that guarantees construction of an efficiently addressable DHT that can operate under a large number of Byzantine nodes.