  The security of most existing cryptocurrencies is based on a concept called
Proof-of-Work, in which users must solve a computationally hard cryptopuzzle to
authorize transactions (`one unit of computation, one vote'). This leads to
enormous expenditure on hardware and electricity in order to collect the
rewards associated with transaction authorization. Proof-of-Stake is an
alternative concept that instead selects users to authorize transactions
proportional to their wealth (`one coin, one vote'). Some aspects of the two
paradigms are the same. For instance, obtaining voting power in Proof-of-Stake
has a monetary cost just as in Proof-of-Work: a coin cannot be freely
duplicated any more easily than a unit of computation. However some aspects are
fundamentally different. In particular, exactly because Proof-of-Stake is
wasteless, there is no inherent resource cost to deviating (commonly referred
to as the `Nothing-at-Stake' problem).
  In contrast to prior work, we focus on incentive-driven deviations (any
participant will deviate if doing so yields higher revenue) instead of
adversarial corruption (an adversary may take over a significant fraction of
the network, but the remaining players follow the protocol). The main results
of this paper are several formal barriers to designing incentive-compatible
proof-of-stake cryptocurrencies (that don't apply to proof-of-work).
