22 February 2021 - Andrew Lewis-Pye

Speaker

Andrew Lewis-Pye

Title

Byzantine Generals in the Permissionless Setting

Abstract

In the distributed computing literature, consensus protocols have traditionally been studied in a setting where all participants are known to each other from the start of the protocol execution. In the parlance of the ‘blockchain’ literature, this is referred to as the permissioned setting. What differentiates the most prominent blockchain protocol Bitcoin from these previously studied protocols is that it operates in a permissionless setting, i.e. it is a protocol for establishing consensus over an unknown network of participants that anybody can join, with as many identities as they like in any role. The arrival of this new form of protocol brings with it many questions.  Beyond Bitcoin, what can we prove about permissionless protocols in a general sense?  How does recent work on permissionless protocols in the blockchain literature relate to the well-developed history of research on permissioned protocols in distributed computing?

I’ll talk about recent work with Tim Roughgarden in which we describe a formal framework for the analysis of both permissioned and permissionless systems (https://arxiv.org/pdf/2101.07095.pdf).  Our framework allows for  “apples-to-apples’” comparisons between different categories of protocols and, in turn, the development of theory to formally discuss their relative merits. A major benefit of the framework is that it facilitates the application of a rich history of proofs and techniques in distributed computing to problems in blockchain and the study of permissionless systems. Within our framework, we then address the questions above.  We consider the Byzantine Generals Problem as a formalisation of the problem of reaching consensus, and address a programme of research that asks, “Under what adversarial conditions, and for what types of permissionless protocol, is consensus possible?”  We prove several results for this programme, our main result being that deterministic consensus is not possible for decentralised permissionless protocols.  To close, we give a list of seven open questions. 

Bio

Andrew Lewis-Pye is a Professor in the Department of Mathematics at the London School of Economics. His research interests are in computability, algorithmic randomness, network science and cryptocurrencies. Prior to coming to LSE, he was a Royal Society University Research Fellow at the University of Leeds, and a Marie-Curie Fellow at the University of Siena.