paint-brush
Can Quantum Computers Compete with Bitcoin Miners? Here’s What New Research Saysby@escholar

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

tldt arrow

Too Long; Didn't Read

This section compares various studies on quantum Bitcoin mining, highlighting discrepancies in computational power estimates, security risks, and the impact of quantum computing on Bitcoin's signature scheme and protocol.
featured image - Can Quantum Computers Compete with Bitcoin Miners? Here’s What New Research Says
EScholar: Electronic Academic Papers for Scholars HackerNoon profile picture
0-item

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

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.