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 C. Comparison with Related Works In [17], Lee et al. consider Question 1 in the setting in which all miners are quantum. They do this by formulating a game called a quantum race. Lee et al. characterize the Nash equilibrium of quantum races that yield no payout in a tie, and therefore correspond with peaceful mining. This equilibrium is then be used to find an approximate Nash equilibrium for the general case in which a tie could payout. Aggarwal et al. [4] give a detailed analysis of the security risks quantum poses to Bitcoin, including mining attacks and attacks on Bitcoins digital signature scheme. They estimate the resources a quantum computer would need to attack Bitcoin by dominating the computing power of the network. To do so, they calculate the rate at which a quantum miner mines blocks as one divided by the time for a quantum miner to complete Grover’s algorithm. Their method is useful for determining if a quantum miner has large computing power compared to the network and Aggarwal et al. infer that the quantum computers are not powerful enough dominate the Bitcoin network at current speeds. However, in the small computational power regime we analyze, their method is less effective. We find that a quantum miner with small computational power would have a substantially lower effective hash rate than suggested by [4]. The discrepancy arises in part because the quantum miner does not have enough time to complete the entirety of Grover’s algorithm if their computational power is small compared to the Bitcoin network. Therefore, the quantum miner can not reap the full √D benefits of the quantum speed-up. A short analysis of the feasibility of quantum Bitcoin mining is given in [25] as part of a larger discussion on the effects of quantum on Bitcoin. In [7] Cojocaru et al. show that many of the same security assumptions that rely on the dynamics of classical mining hold in the presence of quantum adversaries. They proceed by formulating generalizations of unstructured search which arise in quantum mining, and lower bounding the queries a quantum adversary would need to solve these problems. In particular, the lower bounds they develop rely on the idea that a quantum query is worth at most O(√D) classical queries. Contrary to our focus on mining, a variety of works have investigated the security risks Shor’s quantum algorithm for factoring poses to the Bitcoin signature scheme and possible ways to address these risks [4, 9, 11, 15, 22, 23]. Another researched intersection of quantum and Bitcoin is quantum schemes for blockchains in which some portion of the a blockchain protocol is made quantum [10, 14, 16, 20]. For a more technical description of [4, 17, 21] and their relation Bitcoin security, to see Section II D. 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 C. Comparison with Related Works In [17], Lee et al. consider Question 1 in the setting in which all miners are quantum. They do this by formulating a game called a quantum race. Lee et al. characterize the Nash equilibrium of quantum races that yield no payout in a tie, and therefore correspond with peaceful mining. This equilibrium is then be used to find an approximate Nash equilibrium for the general case in which a tie could payout. Aggarwal et al. [4] give a detailed analysis of the security risks quantum poses to Bitcoin, including mining attacks and attacks on Bitcoins digital signature scheme. They estimate the resources a quantum computer would need to attack Bitcoin by dominating the computing power of the network. To do so, they calculate the rate at which a quantum miner mines blocks as one divided by the time for a quantum miner to complete Grover’s algorithm. Their method is useful for determining if a quantum miner has large computing power compared to the network and Aggarwal et al. infer that the quantum computers are not powerful enough dominate the Bitcoin network at current speeds. However, in the small computational power regime we analyze, their method is less effective. We find that a quantum miner with small computational power would have a substantially lower effective hash rate than suggested by [4]. The discrepancy arises in part because the quantum miner does not have enough time to complete the entirety of Grover’s algorithm if their computational power is small compared to the Bitcoin network. Therefore, the quantum miner can not reap the full √D benefits of the quantum speed-up. A short analysis of the feasibility of quantum Bitcoin mining is given in [25] as part of a larger discussion on the effects of quantum on Bitcoin. In [7] Cojocaru et al. show that many of the same security assumptions that rely on the dynamics of classical mining hold in the presence of quantum adversaries. They proceed by formulating generalizations of unstructured search which arise in quantum mining, and lower bounding the queries a quantum adversary would need to solve these problems. In particular, the lower bounds they develop rely on the idea that a quantum query is worth at most O(√D) classical queries. Contrary to our focus on mining, a variety of works have investigated the security risks Shor’s quantum algorithm for factoring poses to the Bitcoin signature scheme and possible ways to address these risks [4, 9, 11, 15, 22, 23]. Another researched intersection of quantum and Bitcoin is quantum schemes for blockchains in which some portion of the a blockchain protocol is made quantum [10, 14, 16, 20]. For a more technical description of [4, 17, 21] and their relation Bitcoin security, to see Section II D. 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.

Can Quantum Computers Compete with Bitcoin Miners? Here’s What New Research Says

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