Welcome to the resource topic for 2021/660
Title:
A Permissionless Proof-of-Stake Blockchain with Best-Possible Unpredictability
Authors: Lei Fan, Jonathan Katz, Phuc Thai, 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.
ePrint: https://eprint.iacr.org/2021/660
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .