Analyzing and Improving Proof-of-Work Consensus Protocols
The last decade witnessed the rise of permissionless blockchains. Requiring no prior knowledge of the participants' identities, these decentralized systems are advocated as a promising solution to many real-world problems. Unfortunately, the security of deployed permissionless blockchains is inferior to their permissioned peers, where the participants' identities are public and verified. Neither is their performance comparable with centralized competitors, where transactions are processed by server farms rather than scattered volunteers.
A considerable amount of new designs appeared in recent years, each declaring to have overcome the limitations of existing blockchains. However, most security and performance improvements claimed by the designers are not widely recognized as solid progress. For systems claiming to strengthen security, the analyses provided by the designers vary in scope and quality. Even some of the most influential designs provide no analysis or only show their resistance against one attack strategy targeting a previous design. As for systems claiming higher performance, most of them sacrifice certain aspects of security or usability. Moreover, it is difficult to compare their performance gains given that their results are simulated in different environments.
This thesis aims to demystify and evaluate these contributions and propose new designs to further advance this discipline. Our study focuses on proof-of-work (PoW) consensus protocols, which is the dominant choice in existing digital currencies. We extend a powerful method based on Markov decision processes to multiple utility functions, in order to get a more comprehensive picture of the security of these protocols. With proper simplification and formal modeling, this method can not only discover new attack strategies but also quantify the resistance against designated attacks. The extended method is applied to the most influential and representative protocols, leading to the discovery of several protocol-specific vulnerabilities and general insights relevant to all PoW protocols.
Guided by our insights, we design two new protocols with stronger attack resistance. Publish or Perish is a selfish-mining defense outperforming the previous best design. It is compatible with the current Bitcoin implementation and can be deployed without splitting the network. NC-Max modifies Bitcoin's Nakamoto Consensus (NC) so that selfish mining is not profitable. Moreover, NC-Max eliminates NC's current performance bottleneck and raises the protocol's throughput without compromising security.
Our future work includes the following studies. First, we will evaluate the performance of blockDAG and sharding protocols within the same environment. Second, we plan to design more secure and flexible protocols based on our discovered insights. Third, we want to develop more advanced security evaluation techniques and to apply them to recent and more complicated PoW protocols.
We hope that our results help establish a solid foundation for the discipline by confirming and contributing to substantive innovations, while exposing the most common flaws. Only with such a foundation can blockchain technology truly benefit the digital society.