A New Theoretical Framework of Pyramid Markov Processes for Blockchain Selfish Mining

Abstract

In this paper, we provide a new theoretical framework of pyramid Markov processes to solve some open and fundamental problems of blockchain selfish mining under a rigorous mathematical setting. We first describe a more general model of blockchain selfish mining with both a two-block leading competitive criterion and a new economic incentive mechanism. Then we establish a pyramid Markov process and show that it is irreducible and positive recurrent, and its stationary probability vector is matrix-geometric with an explicitly representable rate matrix. Also, we use the stationary probability vector to study the influence of orphan blocks on the waste of computing resource. Next, we set up a pyramid Markov reward process to investigate the long-run average mining profits of the honest and dishonest mining pools, respectively. As a by-product, we build one-dimensional Markov reward processes and provide some new interesting interpretation on the Markov chain and the revenue analysis reported in the seminal work by Eyal and Sirer (2014). Note that the pyramid Markov (reward) processes can open up a new avenue in the study of blockchain selfish mining. Thus we hope that the methodology and results developed in this paper shed light on the blockchain selfish mining such that a series of promising research can be developed potentially.

Keywords

Blockchain / Proof of Work / selfish mining / main chain / pyramid Markov process / pyramid Markov reward process / phase-type distribution / Matrix-geometric solution

References

[1] Albrecher H, Goffard P O (2020). On the profitability of selfish blockchain mining under consideration of ruin. HAL Id: hal-02649025: 1–29.

[2] Awe K F, Malik Y, Zavarsky P, Jaafar F (2020). Validating BGP update using blockchain-based infrastructure. Decentralised Internet of Things: 151–165. Springer.

[3] Babich V, Hilary G. Distributed ledgers and operations: What operations management researchers should know about blockchain technology. Manufacturing & Service Operations Management, 2019, 22(2): 223-240.

[4] Bahack L (2013). Theoretical bitcoin attacks with less than half of the computing power (draft). arXiv preprint arXiv 1312.7013: 1–18.

[5] Bai Q, Zhou X, Wang X, Xu Y, Wang X, Kong Q (2019). A deep dive into blockchain selfish mining. International Conference on Communications: 1–6.

[6] Bano S, Sonnino A, Al-Bassam M, Azouvi S, McCorry P, Meiklejohn S, Danezis G (2019). SoK: Consensus in the age of blockchains. Proceedings of the 1st ACM Conference on Advances in Financial Technologies: 183–198.

[7] Bastiaan M (2015). Preventing the 51%-Attack: A stochastic analysis of two phase Proof-of-Work in bitcoin. The 22nd Twente Student Conference on IT: 1–10.

[8] Bissias G, Levine B N (2020). Bobtail: A Proof-of-Work target that minimizes blockchain mining variance. Network and Distributed Systems Security Symposium: 1–16.

[9] Bissias G, Levine B N, Ozisik A P, Andresen G (2016). An analysis of attacks on blockchain consensus. arXiv preprint arXiv 1610.07985: 1–19.

[10] Bright L, Taylor P G. Calculating the equilibrium distribution in level dependent quasi-birth-and-death processes. Stochastic Models, 1995, 11(3): 497-525.

[11] Bright, L, Taylor, P G (1997). Equilibrium distributions for level-dependent quasibirth-and-death processes. Matrix-Analytic Methods in Stochastic Models, Marcel Dekker: 359–375.

[12] Cachin C, Vukolic M (2017). Blockchain consensus protocols in the wild. The 31st International Symposium on Distributed Computing: 1–18.

[13] Carlsten M, Kalodner H A, Weinberg S M Narayanan A (2016). On the instability of bitcoin without the block reward. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security: 154–167.

[14] Chang D, Hasan M, Jain P (2019). Spy based analysis of selfish mining attack on multi-stage blockchain. IACR Cryptology ePrint Archive: 1–34.

[15] Chang S Y, Park Y, Wuthier S, Chen C W (2019). Uncle-block attack: Blockchain mining threat beyond block withholding for rational and uncooperative miners. International Conference on Applied Cryptography and Network Security: 241–258.

[16] Chicarino V, Albuquerque C, Jesus E, Rocha A. On the detection of selfish mining and stalker attacks in blockchain networks. Annals of Telecommunications, 2020, 75(3): 143-152.

[17] Choi S M, Park J Nguyen Q, Cronje A (2018). Fantom: A scalable framework for asynchronous distributed systems. arXiv preprint arXiv 1810.10360: 1–36.

[18] Courtois N T, Bahack L (2014). On subversive miner strategies and block withholding attack in bitcoin digital currency. arXiv preprint arXiv 1402.1718: 1–15.

[19] Davidson M, Diamond T (2020). On the profitability of selfish mining against multiple difficulty adjustment algorithms. IACR Cryptology ePrint Archive: 1–22.

[20] Decker C, Wattenhofer R (2013). Information propagation in the bitcoin network. IEEE Thirteenth International Conference on Peer-to-Peer Computing: 1–10.

[21] Dong X, Wu F, Faree A, Guo D, Shen Y, Ma J. Self-Holding: A combined attack model using selfish mining with block withholding attack. Computers & Security, 2019, 87(101584): 1-11.

[22] Eijkel D, Fehnker A (2019). A distributed blockchain model of selfish mining. The 1st Workshop on Formal Methods for Blockchains: 48–59.

[23] Eyal I, Gencer A E, Sirer E G, Van Renesse R (2016). Bitcoin-NG: A scalable blockchain protocol. The 13th USENIX Symposium on Networked Systems Design and Implementation: 45–59.

[24] Eyal I, Sirer E G. Majority is not enough: Bitcoin mining is vulnerable. Communications of the ACM, 2018, 61(7): 95-102.

[25] Fan C, Ghaemi S, Khazaei H, Musilek P. Performance evaluation of blockchain systems: A systematic survey. IEEE Access, 2020, 8: 126927-126950.

[26] Fullmer D, Morse A S (2018). Analysis of difficulty control in bitcoin and Proof-of-Work blockchains. The IEEE Conference on Decision and Control: 5988–5992.

[27] Gao S, Li Z, Peng Z, Xiao B (2019). Power adjusting and bribery racing: Novel mining attacks in the bitcoin System. Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security: 833–850.

[28] Garay J, Kiayias A, Leonardos N (2015). The bitcoin backbone protocol: Analysis and applications. Annual International Conference on the Theory and Applications of Cryptographic Techniques: 281–310.

[29] Garay J A, Kiayias A, Panagiotakos G (2017). Proofs-of-Work for blockchain protocols. IACR Cryptology ePrint Archive: 1–26.

[30] Garay J, Kiayias A, Ostrovsky R M, Panagiotakos G, Zikas V (2020). Resource-restricted cryptography: Revisiting MPC bounds in the Proof-of-Work era. Annual International Conference on the Theory and Applications of Cryptographic Techniques: 129–158.

[31] Gervais A, Karame G O, Wüst K, Glykantzis V, Ritzdorf H, Capkun S (2016). On the security and performance of Proof-of-Work blockchains. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security: 3–16.

[32] Gervais A, Ritzdorf H, Karame G O, Capkun S (2015).Tampering with the delivery of blocks and transactions in bitcoin. Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security: 692–705.

[33] Gőbel J, Keeler H P, Krzesinski A E, Taylor P G (2016). Bitcoin blockchain dynamics: The selfish-mine strategy in the presence of propagation delay. Performance Evaluation 104: 23–41.

[34] Grunspan C, Pérez-Marco, R (2018). On profitability of selfish mining. arXiv preprint arXiv 1805.08281: 1–20.

[35] Grunspan C, Pérez-Marco R (2018). On profitability of stubborn mining. arXiv preprint arXiv 1808.01041: 1–16.

[36] Grunspan C, Pérez-Marco R (2018). On profitability of trailing mining. arXiv preprint arXiv 1811.09322: 1–19.

[37] Grunspan C, Pérez-Marco R (2019). Bitcoin selfish mining and dyck words. arXiv preprint arXiv 1902.01513: 1–5.

[38] Guerraoui R, Wang J (2018). On the unfairness of blockchain. The 6th International Conference on Networked Systems: 36–50.

[39] Gupta N (2020). Security and privacy issues of blockchain technology. Advanced Applications of Blockchain Technology: 207–226.

[40] Hofmann E, Strewe U M, Bosia N (2017). Supply Chain Finance and Blockchain Technology: The Case of Reverse Securitisation. Springer.

[41] Huang H, Kong W, Zhou S, Zheng Z, Guo S. A survey of state-of-the-art on blockchains: Theories, modelings, and tools. ACM Computing Surveys (CSUR), 2021, 54(2): 1-42.

[42] Jain P (2019). Revenue generation strategy through selfish mining focusing multiple mining pools. Bachelor Thesis for the Degree of B Tech in Computer Science & Applied Mathematics, Indraprastha Institute of Information Technology: 1–24, Delhi.

[43] Javarone M A, Wright C S (2018). Modeling a doublespending detection system for the bitcoin network. arXiv preprint arXiv 1809.07678: 1–14.

[44] Javier K, Fralix B. A further study of some Markovian Bitcoin models. Stochastic Models, 2020, 36(2): 223-250.

[45] Karakostas D, Kiayias A (2020). Securing Proof-of-Work ledgers via checkpointing. 2021 IEEE International Conference on Blockchain and Cryptocurrency (ICBC): 1–5.

[46] Karame G, Androulaki E, Capkun S (2012). Doublespending fast payments in bitcoin. Proceedings of the ACM Conference on Computer and Communications Security: 906–917.

[47] Kedziora M, Kozłowski P, Szczepanik M, Józawiak P (2020). Analysis of blockchain selfish mining attacks. Proceedings of 40th Anniversary International Conference on Information Systems Architecture and Technology: 231–240.

[48] Kiayias A, Lamprou N, Stouka A P (2016). Proofs of Proofs-of-Work with sublinear complexity. International Conference on Financial Cryptography and Data Security: 61–78.

[49] Kiayias A, Miller A, Zindros D. Non-interactive proofs of Proof-of-Work, 2018, Cham: Springer.

[50] Kiayias A, Panagiotakos G (2017). On trees, chains and fast transactions in the blockchain. International Conference on Cryptology and Information Security in Latin America. Springer.

[51] Kiayias A, Zindros D (2019). Proof-of-Work sidechains. International Conference on Financial Cryptography and Data Security: 21–34.

[52] Kraft D. Difficulty control for blockchain-based consensus systems. Peer-to-Peer Networking and Applications, 2016, 9(2): 397-413.

[53] Lee J (2018). The chain of antichains - box protocol: The dual-blockchain and a stablecoin. arXiv preprint arXiv 1810.11871: 1–29.

[54] Lee S, Kim S (2018). Pooled mining makes selfish mining tricky. IACR Cryptology ePrint Archive: 1–16.

[55] Lee S, Kim S (2019). Detective mining: Selfish mining becomes unrealistic under mining pool environment. IACR Cryptology ePrint Archive: 1–10.

[56] Leelavimolsilp T, Nguyen V H, Stein S, Tranthanh L (2019). Selfish mining in Proof-of-Work blockchain with multiple miners: An empirical evaluation. International Conference on Principles and Practice of Multi-Agent Systems: 219–234.

[57] Leelavimolsilp T, Tran-Thanh L, Stein S (2018). On the preliminary investigation of selfish mining strategy with multiple selfish miners. arXiv preprint arXiv 1802.02218: 1–20.

[58] Lewenberg Y, Sompolinsky Y, Zohar A (2015).Inclusive block chain protocols. International Conference on Financial Cryptography and Data Security: 528–547.

[59] Li Q L (2010). Constructive Computation in Stochastic Models with Applications: The RG-Factorizations. Springer.

[60] Li Q L, Ma J Y, Chang Y X (2018). Blockchain queue theory. International Conference on Computational Social Networks: 25–40.

[61] Li Q L, Ma J Y, Chang Y X, Ma F Q, Yu H B. Markov processes in blockchain systems. Computational Social Networks, 2019, 6(1): 1-28.

[62] Liu H L, Li Q L, Chang Y X, Zhang C (2020). Block-structured double-ended queues and bilateral QBD processes. arXiv preprint arXiv 2001.00946: 1–43.

[63] Liu H, Ruan N, Du R, Jia W (2018). On the strategy and behavior of Bitcoin mining with N-attackers. Proceedings of Asia Conference on Computer and Communications Security: 357–368.

[64] Liu H, Ruan N, Liu J K (2019). Catfish effect between internal and external attackers: Semi-honest is helpful. arXiv preprint arXiv 1907.03720: 1–13.

[65] Liu Y, Hei Y, Xu T, Liu J. An evaluation of uncle block mechanism effect on ethereum selfish and stubborn mining combined with an eclipse attack. IEEE Access, 2020, 8: 17489-17499.

[66] Liu Z, Yang G, Yu X, Li F (2019). A security detection model for selfish mining attack. International Conference on Blockchain and Trustworthy Systems, Communications in Computer and Information Science Book Series (CCIS, volume 1156). Springer.

[67] Luu L, Velner Y, Teutsch J, Saxena P (2017). SmartPool: Practical decentralized pooled mining. Proceedings of the 26th USENIX Security Symposium: 1409–1426.

[68] Marmolejo-Cossío F J, Brigham E, Sela B, Katz J (2019). Competing (semi)-selfish miners in bitcoin. AFT’19, Zurich, Switzerland: 89–109.

[69] Miller A, Kosba A, Katz J, Shi E (2015). Nonoutsourceable scratch-off puzzles to discourage Bitcoin mining coalitions. Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security: 680–691.

[70] Morhaim L (2019). Blockchain and cryptocurrencies technologies and network structures: Applications, implications and beyond. HAL Id-02280279: 1–57.

[71] Moustapha B. The Markov chain resulting from the states of the bitcoin. International Journal of Computer Applications, 2018, 181(4): 1-7.

[72] Mulser S (2018). Simulation of different selfish mining strategies in bitcoin. Diplom-Ingenieur Thesis in Software Engineering & Internet Computing, Technische Universität Wien.

[73] Mwale M (2016). Modelling the dynamics of the bitcoin blockchain. Master Thesis, Department of Mathematical Sciences, Stellenbosch University.

[74] Nakamoto S (2008). Bitcoin: A peer-to-peer electronic cash system 1–9. http://bitcoin.org/bitcoin.pdf.

[75] Narayanan A, Bonneau J, Felten E, Miller A, Goldfeder S (2016). Bitcoin and Cryptocurrency Technologies: A Comprehensive Introduction. Princeton University Press.

[76] Natoli C, Yu J, Gramoli V, Esteves-Verissimo P (2019). Deconstructing blockchains: A comprehensive survey on consensus, membership and structure. arXiv preprint arXiv 1908.08316: 1–43.

[77] Nayak K, Kumar S, Miller A, Shi E (2016). Stubborn mining: Generalizing selfish mining and combining with an eclipse attack. IEEE European Symposium on Security and Privacy: 305–320.

[78] Neuts M F (1981). Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach. Johns Hopkins University Press.

[79] Nguyen G T, Kim K. A survey about consensus algorithms used in blockchain. Journal of Information Processing Systems, 2018, 14(1): 101-128.

[80] Niu J, Feng C (2019). Selfish mining in ethereum. 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS): 1306–1316.

[81] Ritz F, Zugenmaier A (2018). The impact of uncle rewards on selfish mining in ethereum. The 3rd IEEE European Symposium on Security and Privacy Workshops: 50–57.

[82] Rosenfeld, M (2014). Analysis of hashrate-based double spending. arXiv preprint arXiv 1402.2009: 1–13.

[83] Saad M, Njilla L, Kamhoua C, Mohaisen A (2019). Countering selfish mining in blockchains. The 2019 International Conference on Computing Networking and Communications: 1–5.

[84] Saad M, Spaulding J, Njilla L, Kamhoua C, Nyang D, Mohaisen A (2019). Overview of attack surfaces in Blockchain. Blockchain for Distributed System Security: 51–66.

[85] Sapirshtein A, Sompolinsky Y, Zohar A (2016). Optimal selfish mining strategies in bitcoin. The 20th International Conference on Financial Cryptography and Data Security: 515–532.

[86] Solat S, Potop-Butucaru M (2016a). Zeroblock: Timestamp-free prevention of block-withholding attack in bitcoin. arXiv preprint arXiv 1605.02435: 1–11.

[87] Solat S, Potop-Butucaru M (2016b). ZeroBlock: Preventing selfish mining in bitcoin. HAL Id: hal-01310088: 1–16.

[88] Sompolinsky Y, Lewenberg Y, Zohar A (2016). SPECTRE: A fast and scalable cryptocurrency protocol. IACR Cryptology ePrint Archive (1159): 1–71.

[89] Sompolinsky Y, Zohar A (2015). Secure high-rate transaction processing in bitcoin. The 19th International Conference on Financial Cryptography and Data Security: 507–527.

[90] Stifter N, Schindler P, Judmayer A, Zamyatin A, Kern A, Weippl E (2019). Echoes of the past: Recovering blockchain metrics from merged mining. International Conference on Financial Cryptography and Data Security: 527–549.

[91] Tromp J (2015). Cuckoo Cycle: A memory bound graph-theoretic Proof-of-Work. International Conference on Financial Cryptography and Data Security: 49–62.

[92] Velner Y, Teutsch J, Luu L (2017). Smart contracts make bitcoin mining pools vulnerable. International Conference on Financial Cryptography and Data Security: 298–316.

[93] Wang W, Hoang D T, Hu P, Xiong Z H, Niyato D, Wang P, Wen Y G, Dong IK. A survey on consensus mechanisms and mining strategy management in blockchain networks. IEEE Access, 2019, 7: 22328-22370.

[94] Wang Z, Liu J, Wu Q, Zhang Y, Zhou Z. An analytic evaluation for the impact of uncle blocks by selfish and stubborn mining in an imperfect ethereum network. Computers & Security, 2019, 87(101581): 1-10.

[95] Werner S M, Pritz P J, Zamyatin A, Knottenbelt W J (2019). Uncle traps: Harvesting rewards in a queue-based ethereum mining pool. Proceedings of the 12th EAI International Conference on Performance Evaluation Methodologies and Tools: 127–134.

[96] Wright C S (2017). The fallacy of selfish mining in bitcoin: A mathematical critique. SSRN-id3004026: 1–18.

[97] Wright C S, Savanah S (2017). The fallacy of the selfish miner in bitcoin: An economic critique. SSRN-id3151923: 1–6.

[98] Wüst K (2016). Security of blockchain technologies. Master Thesis, Department of Computer Science, ETH Zürich.

[99] Xiao Y, Zhang N, Lou W, Hou Y T. A survey of distributed consensus protocols for blockchain networks. IEEE Communications Surveys & Tutorials, 2019, 22(2): 1432-1465.

[100] Zhang R (2015). Broadcasting intermediate blocks as a defense mechanism against selfish-mine in bitcoin. IACR Cryptology ePrint Archive: 1–19.

[101] Zhang R, Preneel B. Publish or perish: A backward-compatible defense against selfish mining in bitcoin, 2017, Cham: Springer.