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 ([email protected]);
(2) Daya R. Gaur, Department of Mathematics and Computer Science, University of Lethbridge, Alberta T1K 3M4, Canada.
