  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 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?
  To answer these questions, we describe a formal framework for the analysis of
both permissioned and permissionless systems. 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 a number of
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 eight open questions.
