Paper 2017/656

A Scalable Proof-of-Stake Blockchain in the Open Setting (or, How to Mimic Nakamoto's Design via Proof-of-Stake)

Lei Fan and Hong-Sheng Zhou

Abstract

Bitcoin and blockchain technologies have proven to be a phenomenal success. The underlying techniques hold huge promise to change the future of financial transactions, and eventually the way people and companies compute, collaborate, and interact. At the same time, the current Bitcoin-like proof-of-work based blockchain systems are facing many challenges. For example, a huge amount of energy/electricity is needed for maintaining the Bitcoin blockchain. We propose a new approach to constructing energy-efficient blockchain protocols. More concretely, we develop proof-of-stake based, scalable blockchain protocols in the open network setting. Our contributions are as follows: -- We for the first time identify a new security property called chain soundness, for proof-of-stake based protocols, which captures the intuition of ensuring new players to join the protocol execution securely. -- We for the first time formally investigate greedy strategies for proof-of-stake based protocols; via a greedy strategy, the protocol players may extend the best blockchain faster by attempting to extend multiple positions, instead of only the latest block, in the blockchain. We demonstrate a very useful upper bound of extending blockchain by greedy players, which enables us to give the first natural mimic of Bitcoin blockchain via proof-of-stake mechanism (without using any form of Byzantine fault tolerance). -- Our design is very simple, using only standard hash functions and unique digital signatures, which makes our design very appealing in practice. Our blockchain achieves important security properties including common prefix, chain quality, chain growth, and chain soundness, and is adaptively secure without assuming secure erasure.

Note: As of May 25, 2021: This result has been superseded by https://eprint.iacr.org/2021/660