Provably-Secure Proof-of-Stake Blockchains

Abstract: Bitcoin has ushered in a new era of interest in cryptocurrencies and distributed algorithms for consensus. While Bitcoin provides a spectacular solution in this space, it uses a "proof-of-work" mechanism that makes quite awesome resource demands: the protocol is projected to burn approximately 70TWh next year, as much as the country of Austria. Proof-of-stake is an alternative framework that has the potential to remove these energy demands. However, proof-of-stake protocols face numerous analytic challenges that do not exist in the proof-of-work setting.

We will begin with an overview of the Bitcoin system, focusing on the proof-of-work mechanism. We will then describe the constructions and analyses of the Ouroboros blockchains, the first blockchain protocols providing provable security in the proof-of-stake setting. These new blockchains are now deployed as a part of the Cardano/ADA cryptocurrency. The analysis shows off a number of new analytic features of interest and makes connections to coupled Markov chains, combinatorics, and the UC-model of protocol security.

This is joint work with Bernardo David, Aggelos Kiayias, Peter Gazi, and Roman Oliynikov.