  Blockchain protocols typically aspire to run in the permissionless setting,
in which nodes are owned and operated by a large number of diverse and unknown
entities, with each node free to start or stop running the protocol at any
time. This setting is more challenging than the traditional permissioned
setting, in which the set of nodes that will be running the protocol is fixed
and known at the time of protocol deployment. The goal of this paper is to
provide a framework for reasoning about the rich design space of blockchain
protocols and their capabilities and limitations in the permissionless setting.
  We propose a hierarchy of settings with different "degrees of
permissionlessness", specified by the amount of knowledge that a protocol has
about the current participants: These are the fully permissionless, dynamically
available and quasi-permissionless settings.
  The paper also proves several results illustrating the utility of our
analysis framework for reasoning about blockchain protocols in these settings.
For example:
  (1) In the fully permissionless setting, even with synchronous communication
and with severe restrictions on the total size of the Byzantine players, every
deterministic protocol for Byzantine agreement has a non-terminating execution.
  (2) In the dynamically available and partially synchronous setting, no
protocol can solve the Byzantine agreement problem with high probability, even
if there are no Byzantine players at all.
  (3) In the quasi-permissionless and partially synchronous setting, by
contrast, assuming a bound on the total size of the Byzantine players, there is
a deterministic protocol solving state machine replication.
  (4) In the quasi-permissionless and synchronous setting, every proof-of-stake
state machine replication protocol that uses only time-malleable cryptographic
primitives is vulnerable to long-range attacks.
