Table of Links Abstract and I. Introduction A. Quantum Bitcoin Mining B. Our Contribution C. Comparison with Related Works D. Conventions II. Background A. Bitcoin Basics B. Bitcoin Security C. Grover’s Search Algorithm D. Quantum Attacks III. Approach A. Algorithm B. Markov Chain C. Assumptions and Approximations IV. Results A. Probability of Success B. Performance Measures C. Example Application V. Discussion, Acknowledgments, and References V. DISCUSSION We analyze the feasibility of quantum Bitcoin mining for the scenario in which a single quantum miner competes in an otherwise classical network. We give a closed-form expression for the quantum miner’s success when the quantum miner has small computational power compared to the network. We then describe an optimal mining protocol for when the quantum miner is also peaceful. We analyze the quantum miner’s efficiency and effective hash rate under these assumptions. Lastly, we give conditions for advantageous quantum mining which can be used to evaluate if a given quantum computer can provide an advantage over classical computers at mining. The computational problem of quantum Bitcoin mining contains an embedded time limit in that the quantum miner race to find a block before any other miner. This limit yields slightly non-intuitive dependencies on problem parameters. These dependencies are clear in the small computational power regime. Most noticeably, the probability of success for a peaceful quantum miner scales approximately linearly with problem difficulty D. This is the same scaling as classical mining and so runs counter to the usual intuition that quantum advantage increases with harder and harder problems. The reason quantum advantage does not increase with difficulty is the time limitation on mining which forces the quantum miner to apply only a fraction of the complete algorithm for Grover’s search. As problem difficulty increases, this fraction becomes smaller as the total number of Grover iterations applied for each block stays constant, but the number of iterations to required to complete Grover’s algorithm increases. The discrepancy comes from two places. First, we are interested in the regime in which the quantum miner has small computational power compared to the network. The r = 66.7MHz quantum computer satisfies this regime well. Under these assumptions the entirety of Grover’s algorithm can not be completed. Therefore less quadratic speed-up can be reaped from the quadratic scaling difference, and the quantum miner performs worse than they would if we assumed Grover’s algorithm was completed (as is assumed in [4]). Second, the effective hash rate calculation by Aggarwal et al. does not account for Grover iterations that are wasted because a classical miner finds a block before measurement is reached. Again, this approximation fits the regime they consider, as a quantum miner who is always able to complete Grover’s algorithm does not waste Grover iterations. ACKNOWLEDGEMENTS The authors thank Shahadat Hossain and Robert Benkoczi for helpful discussions throughout the development of this work and thank Barry Sanders for insightful comments on the manuscript. This work was supported by the Alberta Government We acknowledge the traditional owners of the land on which this work was undertaken at the University of Calgary and the University of Lethbridge: the Treaty 7 First Nations www.treaty7.org. [1] ASIC miner value. www.asicminervalue.com/ efficiency/sha-256. Accessed: 2021-09-28. [2] Network difficulty. www.blockchain.com/charts/ difficulty. Accessed: 2021-09-28. [3] FIPS Publication 180-2. National Institute of Standards and Technology, 2001. [4] D. Aggarwal, G. Brennen, T. Lee, M. Santha, and M. Tomamichel. Quantum attacks on Bitcoin, and how to protect against them. Ledger, 3, 2017. [5] A. Biryukov and D. Khovratovich. Equihash: Asymmetric proof-of-work based on the generalized birthday problem. Ledger, 2:1–30, 2016. [6] M. Boyer, G. Brassard, P. Høyer, and A. Tapp. Tight bounds on quantum searching. Fortschr. Phys., 46(4- 5):493–505, 1998. [7] A. Cojocaru, J. Garay, A. Kiayias, F. Song, and P. Wallden. Post-quantum security of the Bitcoin backbone and quantum multi-solution Bernoulli search. arXiv, 2012.15254, 2020. [8] I. Eyal and E. G. Sirer. Majority is not enough: Bitcoin mining is vulnerable. Commun. ACM, 61(7):95–102, June 2018. [9] A. Fedorov, E. O. Kiktenko, and A. Lvovsky. Quantum computers put blockchain security at risk. Nature, 563:465–467, 2018. [10] Y.-L. Gao, X. Chen, G. Xu, K. Yuan, W. Liu, and Y.- X. Yang. A novel quantum blockchain scheme base on quantum entanglement and DPoS. Quantum Inf. Process., 19:420, 2020. [11] Y.-L. Gao, X.-B. Chen, Y.-L. Chen, Y. Sun, X.-X. Niu, and Y.-X. Yang. A secure cryptocurrency scheme based on post-quantum blockchain. IEEE Access, 6:27205– 27213, 2018. [12] R. M. Gingrich, C. P. Williams, and N. J. Cerf. Generalized quantum search with parallelism. Phys. Rev. A, 61(5):052313, May 2000. [13] L. K. Grover. A fast quantum mechanical algorithm for database search. In STOC ’96, 1996. [14] K. Ikeda. qBitcoin: A peer-to-peer quantum cash system. Econometrics: Econometrics Stat. Methods - Spec. Top. eJournal, 2017. [15] D. Ilie, K. Karantias, and W. Knottenbelt. Bitcoin crypto - bounties for quantum capable adversaries. IACR Cryptol. ePrint Arch., page 186, 2020. [16] J. Jogenfors. Quantum Bitcoin: An anonymous, distributed, and secure currency secured by the no-cloning theorem of quantum mechanics. 2019 IEEE Int. Conf. Blockchain Cryptocurrency (ICBC), pages 245– 252, 2019. [17] T. Lee, M. Ray, and M. Santha. Strategies for Quantum Races. In A. Blum, editor, 10th Innov. Theor. Comput. Sci. Conf. (ITCS 2019), volume 124 of Leibniz International Proceedings in Informatics (LIPIcs), pages 51:1– 51:21, 2018. [18] S. Nakamoto. Bitcoin : A peer-to-peer electronic cash system. 2009. [19] M. Nielsen and I. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000. [20] D. Rajan and M. Visser. Quantum blockchain using entanglement in time. Quantum Rep., 1(1):3–11, 2019. [21] O. Sattath. On the insecurity of quantum Bitcoin mining. Int. J. Inf. Secur., 19, 06 2020. [22] M. C. Semmouni, A. Nitaj, and M. Belkasmi. Bitcoin security with post quantum cryptography. In Int. Conf. Networked Syst., 2019. [23] I. Stewart, D. Ilie, A. Zamyatin, S. M. Werner, M. F. Torshizi, and W. Knottenbelt. Committing to quantum resistance: a slow defence for Bitcoin against a fast quantum computing attack. R. Soc. Open Sci., 5, 2018. [24] P. Tasatanattakool and C. Techapanupreeda. Blockchain: Challenges and applications. In 2018 Int. Conf. Inf. Netw. (ICOIN), pages 473–475, 2018. [25] L. Tessler and T. Byrnes. Bitcoin and quantum computing. arXiv, 1711.04235, 2017. [26] Wolfram Research Inc. Wolfram alpha. Champaign, IL, 2021. [27] C. Zalka. Grover’s quantum searching algorithm is optimal. Phys. Rev. A, 60:2746–2751, 1999. Authors:
(1) Robert R. Nerem, Institute for Quantum Science and Technology, University of Calgary, Alberta T2N 1N4, Canada (riley.nerem@gmail.com);
(2) Daya R. Gaur, Department of Mathematics and Computer Science, University of Lethbridge, Alberta T1K 3M4, Canada. This paper is available on arxiv under CC BY 4.0 DEED license. Table of Links Abstract and I. Introduction Abstract and I. Introduction Abstract and I. Introduction A. Quantum Bitcoin Mining A. Quantum Bitcoin Mining B. Our Contribution B. Our Contribution C. Comparison with Related Works C. Comparison with Related Works D. Conventions D. Conventions II. Background II. Background A. Bitcoin Basics A. Bitcoin Basics B. Bitcoin Security B. Bitcoin Security C. Grover’s Search Algorithm C. Grover’s Search Algorithm D. Quantum Attacks D. Quantum Attacks III. Approach III. Approach III. Approach A. Algorithm A. Algorithm B. Markov Chain B. Markov Chain C. Assumptions and Approximations C. Assumptions and Approximations IV. Results IV. Results A. Probability of Success A. Probability of Success B. Performance Measures B. Performance Measures C. Example Application C. Example Application V. Discussion, Acknowledgments, and References V. Discussion, Acknowledgments, and References V. Discussion, Acknowledgments, and References V. DISCUSSION We analyze the feasibility of quantum Bitcoin mining for the scenario in which a single quantum miner competes in an otherwise classical network. We give a closed-form expression for the quantum miner’s success when the quantum miner has small computational power compared to the network. We then describe an optimal mining protocol for when the quantum miner is also peaceful. We analyze the quantum miner’s efficiency and effective hash rate under these assumptions. Lastly, we give conditions for advantageous quantum mining which can be used to evaluate if a given quantum computer can provide an advantage over classical computers at mining. The computational problem of quantum Bitcoin mining contains an embedded time limit in that the quantum miner race to find a block before any other miner. This limit yields slightly non-intuitive dependencies on problem parameters. These dependencies are clear in the small computational power regime. Most noticeably, the probability of success for a peaceful quantum miner scales approximately linearly with problem difficulty D. This is the same scaling as classical mining and so runs counter to the usual intuition that quantum advantage increases with harder and harder problems. The reason quantum advantage does not increase with difficulty is the time limitation on mining which forces the quantum miner to apply only a fraction of the complete algorithm for Grover’s search. As problem difficulty increases, this fraction becomes smaller as the total number of Grover iterations applied for each block stays constant, but the number of iterations to required to complete Grover’s algorithm increases. The discrepancy comes from two places. First, we are interested in the regime in which the quantum miner has small computational power compared to the network. The r = 66.7MHz quantum computer satisfies this regime well. Under these assumptions the entirety of Grover’s algorithm can not be completed. Therefore less quadratic speed-up can be reaped from the quadratic scaling difference, and the quantum miner performs worse than they would if we assumed Grover’s algorithm was completed (as is assumed in [4]). Second, the effective hash rate calculation by Aggarwal et al. does not account for Grover iterations that are wasted because a classical miner finds a block before measurement is reached. Again, this approximation fits the regime they consider, as a quantum miner who is always able to complete Grover’s algorithm does not waste Grover iterations. ACKNOWLEDGEMENTS The authors thank Shahadat Hossain and Robert Benkoczi for helpful discussions throughout the development of this work and thank Barry Sanders for insightful comments on the manuscript. This work was supported by the Alberta Government We acknowledge the traditional owners of the land on which this work was undertaken at the University of Calgary and the University of Lethbridge: the Treaty 7 First Nations www.treaty7.org. [1] ASIC miner value. www.asicminervalue.com/ efficiency/sha-256. Accessed: 2021-09-28. [2] Network difficulty. www.blockchain.com/charts/ difficulty. Accessed: 2021-09-28. [3] FIPS Publication 180-2. National Institute of Standards and Technology, 2001. [4] D. Aggarwal, G. Brennen, T. Lee, M. Santha, and M. Tomamichel. Quantum attacks on Bitcoin, and how to protect against them. Ledger, 3, 2017. [5] A. Biryukov and D. Khovratovich. Equihash: Asymmetric proof-of-work based on the generalized birthday problem. Ledger, 2:1–30, 2016. [6] M. Boyer, G. Brassard, P. Høyer, and A. Tapp. Tight bounds on quantum searching. Fortschr. Phys., 46(4- 5):493–505, 1998. [7] A. Cojocaru, J. Garay, A. Kiayias, F. Song, and P. Wallden. Post-quantum security of the Bitcoin backbone and quantum multi-solution Bernoulli search. arXiv, 2012.15254, 2020. [8] I. Eyal and E. G. Sirer. Majority is not enough: Bitcoin mining is vulnerable. Commun. ACM, 61(7):95–102, June 2018. [9] A. Fedorov, E. O. Kiktenko, and A. Lvovsky. Quantum computers put blockchain security at risk. Nature, 563:465–467, 2018. [10] Y.-L. Gao, X. Chen, G. Xu, K. Yuan, W. Liu, and Y.- X. Yang. A novel quantum blockchain scheme base on quantum entanglement and DPoS. Quantum Inf. Process., 19:420, 2020. [11] Y.-L. Gao, X.-B. Chen, Y.-L. Chen, Y. Sun, X.-X. Niu, and Y.-X. Yang. A secure cryptocurrency scheme based on post-quantum blockchain. IEEE Access, 6:27205– 27213, 2018. [12] R. M. Gingrich, C. P. Williams, and N. J. Cerf. Generalized quantum search with parallelism. Phys. Rev. A, 61(5):052313, May 2000. [13] L. K. Grover. A fast quantum mechanical algorithm for database search. In STOC ’96, 1996. [14] K. Ikeda. qBitcoin: A peer-to-peer quantum cash system. Econometrics: Econometrics Stat. Methods - Spec. Top. eJournal, 2017. [15] D. Ilie, K. Karantias, and W. Knottenbelt. Bitcoin crypto - bounties for quantum capable adversaries. IACR Cryptol. ePrint Arch., page 186, 2020. [16] J. Jogenfors. Quantum Bitcoin: An anonymous, distributed, and secure currency secured by the no-cloning theorem of quantum mechanics. 2019 IEEE Int. Conf. Blockchain Cryptocurrency (ICBC), pages 245– 252, 2019. [17] T. Lee, M. Ray, and M. Santha. Strategies for Quantum Races. In A. Blum, editor, 10th Innov. Theor. Comput. Sci. Conf. (ITCS 2019), volume 124 of Leibniz International Proceedings in Informatics (LIPIcs), pages 51:1– 51:21, 2018. [18] S. Nakamoto. Bitcoin : A peer-to-peer electronic cash system. 2009. [19] M. Nielsen and I. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000. [20] D. Rajan and M. Visser. Quantum blockchain using entanglement in time. Quantum Rep., 1(1):3–11, 2019. [21] O. Sattath. On the insecurity of quantum Bitcoin mining. Int. J. Inf. Secur., 19, 06 2020. [22] M. C. Semmouni, A. Nitaj, and M. Belkasmi. Bitcoin security with post quantum cryptography. In Int. Conf. Networked Syst., 2019. [23] I. Stewart, D. Ilie, A. Zamyatin, S. M. Werner, M. F. Torshizi, and W. Knottenbelt. Committing to quantum resistance: a slow defence for Bitcoin against a fast quantum computing attack. R. Soc. Open Sci., 5, 2018. [24] P. Tasatanattakool and C. Techapanupreeda. Blockchain: Challenges and applications. In 2018 Int. Conf. Inf. Netw. (ICOIN), pages 473–475, 2018. [25] L. Tessler and T. Byrnes. Bitcoin and quantum computing. arXiv, 1711.04235, 2017. [26] Wolfram Research Inc. Wolfram alpha. Champaign, IL, 2021. [27] C. Zalka. Grover’s quantum searching algorithm is optimal. Phys. Rev. A, 60:2746–2751, 1999. Authors: (1) Robert R. Nerem, Institute for Quantum Science and Technology, University of Calgary, Alberta T2N 1N4, Canada (riley.nerem@gmail.com); (2) Daya R. Gaur, Department of Mathematics and Computer Science, University of Lethbridge, Alberta T1K 3M4, Canada. Authors: Authors: (1) Robert R. Nerem, Institute for Quantum Science and Technology, University of Calgary, Alberta T2N 1N4, Canada (riley.nerem@gmail.com); (2) Daya R. Gaur, Department of Mathematics and Computer Science, University of Lethbridge, Alberta T1K 3M4, Canada. This paper is available on arxiv under CC BY 4.0 DEED license. This paper is available on arxiv under CC BY 4.0 DEED license. available on arxiv available on arxiv

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Conditions for Advantageous Quantum Bitcoin Mining: Discussion, Acknowledgments, and References

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

5 Ways to Measure Privacy Risks in Text Data

The Noonification: 2023 Was the Best Time to Accumulate Crypto (1/1/2024)

The Noonification: The Bitcoin Mining Writing Contest by GoMining (1/14/2024)

The Noonification: A Taxonomy of Inclusiveness (1/11/2024)

08/06/2018: Biggest Stories in the Cryptosphere

The Noonification: Much Ado About Bitcoin Halving (1/6/2024)

5 Ways to Measure Privacy Risks in Text Data

The Noonification: 2023 Was the Best Time to Accumulate Crypto (1/1/2024)

The Noonification: The Bitcoin Mining Writing Contest by GoMining (1/14/2024)

The Noonification: A Taxonomy of Inclusiveness (1/11/2024)

08/06/2018: Biggest Stories in the Cryptosphere

The Noonification: Much Ado About Bitcoin Halving (1/6/2024)

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps