  Blockchain protocols come with a variety of security guarantees. For example,
BFT-inspired protocols such as Algorand tend to be secure in the partially
synchronous setting, while longest chain protocols like Bitcoin will normally
require stronger synchronicity to be secure. Another fundamental distinction,
directly relevant to scalability solutions such as sharding, is whether or not
a single untrusted user is able to point to *certificates*, which provide
incontrovertible proof of block confirmation. Algorand produces such
certificates, while Bitcoin does not. Are these properties accidental? Or are
they inherent consequences of the paradigm of protocol design? Our aim in this
paper is to understand what, fundamentally, governs the nature of security for
permissionless blockchain protocols. Using the framework developed in
(Lewis-Pye and Roughgarden, 2021), we prove general results showing that these
questions relate directly to properties of the user selection process, i.e.,
the method (such as proof-of-work or proof-of-stake) which is used to select
users with the task of updating state. Our results suffice to establish, for
example, that the production of certificates is impossible for proof-of-work
protocols, but is automatic for standard forms of proof-of-stake protocols. As
a byproduct of our work, we also define a number of security notions and
identify the equivalences and inequivalences among them.
