This Math Hack Could Let Miners Earn Extra on Blockchains | HackerNoon

Table of Links

Abstract and 1. Introduction

1.1 Related Work

2. Preliminaries

   2.1 System Model

   2.2 Selfish Mining Objective

   2.3 Markov Decision Processes

3. Selfish Mining Attack

   3.1 Overview

   3.2 Formal Model

   3.3 Formal Analysis

   3.4 Key Features and Limitations

4. Experimental Evaluation

5. Conclusion, Acknowledgments, and References

A. NAS Mining Objectives

B. Efficient Proof Systems

C. Proof of Theorem 3.1

5 CONCLUSION

We initiated the study of optimal selfish mining strategies for unpredictable blockchain protocols based on efficient proof systems. To this end, we considered a selfish mining objective corresponding to changes in chain quality and proposed a novel selfish mining attack that aims to maximize this objective. We formally modeled our attack as an MDP strategy and we presented a formal analysis procedure for computing an 𝜖-tight lower bound on the optimal expected relative revenue in the MDP and a strategy that achieves it for a specified precision 𝜖 > 0. The procedure is fully automated and provides formal guarantees on the correctness of the computed bound.

We believe that our work opens several exciting lines for future research. We highlight two particular directions. First, our formal analysis only allows us to compute lower bounds on the expected relative revenue that an adversary can achieve. A natural direction of future research would be to consider computing upper bounds on the optimal expected relative revenue for fixed resource amounts. Second, as discussed in Section 3.4, our formal analysis only computes 𝜖-tight lower bounds on the expected relative revenue by following a strategy in our MDP model. However, our model in Section 3.2 introduces assumptions such as growing private forks instead of trees and bounding the maximal length of each fork for tractability purposes. It would be interesting to study whether these assumptions could be relaxed while still providing formal correctness guarantees.

ACKNOWLEDGMENTS

This work was supported in part by the ERC-2020-CoG 863818 (FoRM-SMArt) grant and the MOE-T2EP20122-0014 (Data-Driven Distributed Algorithms) grant.

REFERENCES

[1] 2022. https://ethereum.org/en/roadmap/merge/.

[2] Adam Back. 1997. Hashcash. http://hashcash.org/.

[3] Vivek Kumar Bagaria, Amir Dembo, Sreeram Kannan, Sewoong Oh, David Tse, Pramod Viswanath, Xuechao Wang, and Ofer Zeitouni. 2022. Proof-of-Stake Longest Chain Protocols: Security vs Predictability. In Proceedings of the 2022 ACM Workshop on Developments in Consensus, ConsensusDay 2022, Los Angeles, CA, USA, 7 November 2022, Jorge M. Soares, Dawn Song, and Marko Vukolic (Eds.). ACM, 29–42. https://doi.org/10.1145/3560829.3563559

[4] Dan Boneh, Joseph Bonneau, Benedikt Bünz, and Ben Fisch. 2018. Verifiable Delay Functions. IACR Cryptol. ePrint Arch. (2018), 601. https://eprint.iacr.org/2018/601

[5] Jonah Brown-Cohen, Arvind Narayanan, Christos-Alexandros Psomas, and S. Matthew Weinberg. 2018. Formal Barriers to Longest-Chain Proof-of-Stake Protocols. CoRR abs/1809.06528 (2018). arXiv:1809.06528 http://arxiv.org/abs/ 1809.06528

[6] Jing Chen and Silvio Micali. 2019. Algorand: A secure and efficient distributed ledger. Theor. Comput. Sci. 777 (2019), 155–183.

[7] Bram Cohen and Krzysztof Pietrzak. 2019. The chia network blockchain. https://docs.chia.net/assets/files/Precursor-ChiaGreenPaper82cb50060c575f3f71444a4b7430fb9d.pdf

[8] Bram Cohen and Krzysztof Pietrzak. 2023. Chia Greenpaper. https://docs.chia. net/green-paper-abstract

[9] Bernardo Machado David, Peter Gazi, Aggelos Kiayias, and Alexander Russell. 2017. Ouroboros Praos: An adaptively-secure, semi-synchronous proof-of-stake protocol. IACR Cryptol. ePrint Arch. (2017), 573. http://eprint.iacr.org/2017/573

[10] Stefan Dziembowski, Sebastian Faust, Vladimir Kolmogorov, and Krzysztof Pietrzak. 2015. Proofs of Space. In Advances in Cryptology – CRYPTO 2015 – 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part II (Lecture Notes in Computer Science, Vol. 9216), Rosario Gennaro and Matthew Robshaw (Eds.). Springer, 585–605. https://doi.org/10.1007/978-3- 662-48000-7_29

[11] Ittay Eyal and Emin Gün Sirer. 2018. Majority is not enough: bitcoin mining is vulnerable. Commun. ACM 61, 7 (2018), 95–102. https://doi.org/10.1145/3212998

[12] Lei Fan and Hong-Sheng Zhou. 2017. iChing: A Scalable Proof-of-Stake Blockchain in the Open Setting (or, How to Mimic Nakamoto’s Design via Proofof-Stake). IACR Cryptol. ePrint Arch. (2017), 656. http://eprint.iacr.org/2017/656

[13] Matheus V. X. Ferreira, Ye Lin Sally Hahn, S. Matthew Weinberg, and Catherine Yu. 2022. Optimal Strategic Mining Against Cryptographic Self-Selection in Proof-of-Stake. In EC. ACM, 89–114.

[14] Matheus V. X. Ferreira and S. Matthew Weinberg. 2021. Proof-of-Stake Mining Games with Perfect Randomness. In EC ’21: The 22nd ACM Conference on Economics and Computation, Budapest, Hungary, July 18-23, 2021, Péter Biró, Shuchi Chawla, and Federico Echenique (Eds.). ACM, 433–453. https: //doi.org/10.1145/3465456.3467636

[15] Jerzy Filar and Koos Vrieze. 2012. Competitive Markov decision processes. Springer Science & Business Media.

[16] Juan A. Garay, Aggelos Kiayias, and Nikos Leonardos. 2015. The Bitcoin Backbone Protocol: Analysis and Applications. In EUROCRYPT (2) (Lecture Notes in Computer Science, Vol. 9057). Springer, 281–310.

[17] Peter Gazi, Aggelos Kiayias, and Alexander Russell. 2020. Tight Consistency Bounds for Bitcoin. In CCS. ACM, 819–838.

[18] Christian Hensel, Sebastian Junges, Joost-Pieter Katoen, Tim Quatmann, and Matthias Volk. 2022. The probabilistic model checker Storm. Int. J. Softw. Tools Technol. Transf. 24, 4 (2022), 589–610. https://doi.org/10.1007/s10009-021-00633-z

[19] Charlie Hou, Mingxun Zhou, Yan Ji, Phil Daian, Florian Tramèr, Giulia Fanti, and Ari Juels. 2021. SquirRL: Automating Attack Analysis on Blockchain Incentive Mechanisms with Deep Reinforcement Learning. In NDSS. The Internet Society.

[20] Marta Z. Kwiatkowska, Gethin Norman, and David Parker. 2011. PRISM 4.0: Verification of Probabilistic Real-Time Systems. In CAV (Lecture Notes in Computer Science, Vol. 6806). Springer, 585–591.

[21] Satoshi Nakamoto. 2008. Bitcoin: A peer-to-peer electronic cash system. https: //bitcoin.org/bitcoin.pdf.

[22] James R Norris. 1998. Markov chains. Number 2. Cambridge university press.

[23] Sunoo Park, Albert Kwon, Georg Fuchsbauer, Peter Gazi, Joël Alwen, and Krzysztof Pietrzak. 2018. SpaceMint: A Cryptocurrency Based on Proofs of Space. In Financial Cryptography (Lecture Notes in Computer Science, Vol. 10957). Springer, 480–499.

[24] Rafael Pass, Lior Seeman, and Abhi Shelat. 2017. Analysis of the Blockchain Protocol in Asynchronous Networks. In EUROCRYPT (2) (Lecture Notes in Computer Science, Vol. 10211). 643–673.

[25] Krzysztof Pietrzak. 2019. Simple Verifiable Delay Functions. In ITCS (LIPIcs, Vol. 124). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 60:1–60:15.

[26] Martin L. Puterman. 1994. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley.

[27] Ayelet Sapirshtein, Yonatan Sompolinsky, and Aviv Zohar. 2016. Optimal Selfish Mining Strategies in Bitcoin. In Financial Cryptography (Lecture Notes in Computer Science, Vol. 9603). Springer, 515–532.

[28] Roozbeh Sarenche, Svetla Nikova, and Bart Preneel. 2024. Deep Selfish Proposing in Longest-Chain Proof-of-Stake Protocols. In Financial Cryptography and Data Security.

[29] Xuechao Wang, Govinda M. Kamath, Vivek Kumar Bagaria, Sreeram Kannan, Sewoong Oh, David Tse, and Pramod Viswanath. 2019. Proof-of-Stake Longest Chain Protocols Revisited. CoRR abs/1910.02218 (2019).

[30] Benjamin Wesolowski. 2018. Efficient verifiable delay functions. IACR Cryptol. ePrint Arch. (2018), 623. https://eprint.iacr.org/2018/623

[31] Roi Bar Zur, Ittay Eyal, and Aviv Tamar. 2020. Efficient MDP Analysis for SelfishMining in Blockchains. In AFT. ACM, 113–131.