Listen to this story
We publish the best academic work (that's too often lost to peer reviews & the TA's desk) to the global tech community
Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.
C. Comparison with Related Works
II. Background
C. Assumptions and Approximations
IV. Results
V. Discussion, Acknowledgments, and References
In [4], Aggarwal et al. analyze the effect of quantum computation on the security of Bitcoin. As part of this analysis, they calculate the number of qubits and gate speed a quantum computer would need to dominate the Bitcoin network’s computing power and, as a result, be capable of a 51% attack. Using this analysis, they predict that “it will be some time before quantum computers out compete classical machines for this task and when they do, a single quantum computer will not have majority hashing power.” The analysis accounts for both parallelization of Grover’s search and the overhead from quantum error correction.
In [21], Sattath takes a different approach to the determining the implications of quantum computing to Bitcoin security. He shows that the properties of quantum Bitcoin mining lead to security risks even if no single miner dominates the networks computing power. This reduction in security comes from stale blocks. If a quantum miner receives a block midway through performing Grover’s search algorithm, they can perform a measurement of their quantum register, and with probability higher than random guessing, mine a block. This procedure is called aggressive mining, whereas peaceful mining refers to the procedure in which the quantum miner ends their search if they learn of another block. If many quantum miners follow an aggressive procedure, then with higher probability than classically, two blocks are found at nearly the same time by different miners, creating many stale blocks. This result is important because it shows quantum mining poses security risks simply because the process of quantum mining is different than classical mining, not because quantum mining is more effective.
Sattath conjectures that if quantum miners must commit to the number of Grover iterations they will apply before measuring, then the stale block rates are minimal. He proposes a change in the Bitcoin protocol that would force quantum miners to decide before they begin mining a block how many Grover iterations they will apply. This change in protocol is incompatible with proposed fixes for insecurities arising from selfish mining techniques [8].
Determining the rate of stale blocks with Sattath’s proposed change is a challenging game theory question. This question is addressed in [17], where Lee et al. analyze a class of games they call quantum races in which multiple quantum capable players compete to solve a computational problem first. In many cases, they confirm Sattath’s conjecture of low stale block rates.
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