  The Nakamoto longest chain protocol is remarkably simple and has been proven
to provide security against any adversary with less than 50% of the total
hashing power. Proof-of-stake (PoS) protocols are an energy efficient
alternative; however existing protocols adopting Nakamoto's longest chain
design achieve provable security only by allowing long-term predictability
(which have serious security implications). In this paper, we prove that a
natural longest chain PoS protocol with similar predictability as Nakamoto's
PoW protocol can achieve security against any adversary with less than 1/(1+e)
fraction of the total stake. Moreover we propose a new family of longest chain
PoS protocols that achieve security against a 50% adversary, while only
requiring short-term predictability. Our proofs present a new approach to
analyzing the formal security of blockchains, based on a notion of
adversary-proof convergence.
