Lay Down the Common Metrics: Evaluating Proof-of-Work Consensus Protocols' Security

Following Bitcoin's Nakamoto Consensus protocol (NC), hundreds of cryptocurrencies utilize proofs of work (PoW) to maintain their ledgers. However, research shows that NC fails to achieve perfect chain quality, allowing malicious miners to alter the public ledger in order to launch several attacks, i.e., selfish mining, double-spending and feather-forking. Some later designs, represented by Ethereum, Bitcoin-NG, DECOR+, Byzcoin and Publish or Perish, aim to solve the problem by raising the chain quality; other designs, represented by Fruitchains, DECOR+ and Subchains, claim to successfully defend against the attacks in the absence of perfect chain quality. As their effectiveness remains self-claimed, the community is divided on whether a secure PoW protocol is possible. In order to resolve this ambiguity and to lay down the foundation of a common body of knowledge, this paper introduces a multi-metric evaluation framework to quantitatively analyze PoW protocols' chain quality and attack resistance. Subsequently we use this framework to evaluate the security of these improved designs through Markov decision processes. We conclude that to date, no PoW protocol achieves ideal chain quality or is resistant against all three attacks. We attribute existing PoW protocols' imperfect chain quality to their unrealistic security assumptions, and their unsatisfactory attack resistance to a dilemma between "rewarding the bad" and "punishing the good". Moreover, our analysis reveals various new protocol-specific attack strategies. Based on our analysis, we propose future directions toward more secure PoW protocols and indicate several common pitfalls in PoW security analyses.