Paper 2021/660

A Permissionless Proof-of-Stake Blockchain with Best-Possible Unpredictability

Lei Fan, Jonathan Katz, Phuc Thai, and Hong-Sheng Zhou

Abstract

To eliminate the unnecessary waste of energy and computing power in Bitcoin, in this paper, we develop a novel proof-of-stake consensus in the permissionless setting. Among other features, our design achieves the ``best possible'' unpredictability for permissionless proof-of-stake protocols. As shown by Brown-Cohen et al~(EC 2019), unpredictability property is critical for proof-of-stake consensus in the rational setting; the flip side of unpredictability property, i.e., predictability can be abused by the attackers for launching strengthened version of multiple attacks such as selfish-mining and bribing, against proof-of-stake systems. We are inspired by Bitcoin's ``block-by-block'' design, and we show that a direct and natural mimic of Bitcoin's design via proof-of-stake is secure if the majority 73\% of stake is honest. Our result relies on an interesting upper bound of extending proof-of-stake blockchain we establish: players (who may extend all chains) can generate blockchain at most $2.72\times$ faster than playing the basic strategy of extending the longest chain. We introduce a novel strategy called ``D-distance-greedy'' strategy, which enables us to construct a class of secure proof-of-stake blockchain protocols, against an \textbf{arbitrary} adversary, even assuming much smaller (than 73\% of) stake is honest. To enable a thorough security analysis in the cryptographic setting, we develop several new techniques: for example, to show the chain growth property, we represent the chain extension process via a Markov chain, and then develop a random walk on the Markov chain; to prove the common prefix property, we introduce a new concept called ``virtual chains'', and then present a reduction from the regular version of common prefix to ``common prefix w.r.t. virtual chains''. Finally, we note that, ours is the first ``block-by-block'' style of proof-of-stake in the permissionless setting, naturally mimicking Bitcoin's design; it turns out that this feature, again allows us to achieve the ``best possible'' unpredictability property. Other existing provably secure permissionless proof-of-stake solutions are all in an ``epoch-by-epoch'' style, and thus cannot achieve the best possible unpredictability.

Note: This is a replacement of https://eprint.iacr.org/2017/656 and other earlier versions of the work.