Machinations

I recently gave a talk at DISC on our paper Secure and Scalable Computation Among Strangers. Short abstract below:

“The last decade has seen substantial progress on designing Byzantine agreement algorithms that 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^2 message complexity, where n is the total number of nodes. In particular, the communication cost incurred by the honest nodes n^2, 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^2) is the number of bits sent by Byzantine nodes.”