  Proof-of-Stake blockchains based on a longest-chain consensus protocol are an
attractive energy-friendly alternative to the Proof-of-Work paradigm. However,
formal barriers to "getting the incentives right" were recently discovered,
driven by the desire to use the blockchain itself as a source of
pseudorandomness \cite{brown2019formal}.
  We consider instead a longest-chain Proof-of-Stake protocol with perfect,
trusted, external randomness (e.g. a randomness beacon). We produce two main
results.
  First, we show that a strategic miner can strictly outperform an honest miner
with just $32.5\%$ of the total stake. Note that a miner of this size {\em
cannot} outperform an honest miner in the Proof-of-Work model. This establishes
that even with access to a perfect randomness beacon, incentives in
Proof-of-Work and Proof-of-Stake longest-chain protocols are fundamentally
different.
  Second, we prove that a strategic miner cannot outperform an honest miner
with $30.8\%$ of the total stake. This means that, while not quite as secure as
the Proof-of-Work regime, desirable incentive properties of Proof-of-Work
longest-chain protocols can be approximately recovered via Proof-of-Stake with
a perfect randomness beacon.
  The space of possible strategies in a Proof-of-Stake mining game is {\em
significantly} richer than in a Proof-of-Work game. Our main technical
contribution is a characterization of potentially optimal strategies for a
strategic miner, and in particular, a proof that the corresponding
infinite-state MDP admits an optimal strategy that is positive recurrent.
