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
We describe a procedure for quantum mining (Algorithm 2), formulate a corresponding Markov chain (Figure 1), and use this formulation to derive an expression for the expected fraction of blocks the quantum miner contributes to the blockchain (Theorem 2). This analysis accounts for the quantum miner using the “aggressive mining” techniques of [21]. In aggressive mining the quantum miner performs a measurement in response to a classical miner finding a proof-of-work, potentially forcing a tie in the race and yielding a reward to the quantum miner (with non-zero but low probability).
The expression for the expected fraction of blocks the quantum miner adds to the blockchain varies with the number Grover iterations the quantum miner applies before measuring. Still, the number of Grover iterations that maximizes this expression is unclear. As a solution, we make further simplifications justified by practical considerations.
Using this approximation we derive a closed-form expression for the expected fraction of blocks the quantum miner successfully mines (Eq. 44). We also show how this expression can be used to determine the effective hash rate (Eq. 59) and efficiency, or cost per block, (Eq. 61) of the quantum miner. By comparing the efficiency of the quantum miner with that of a classical miner, we derive conditions for quantum mining to be advantageous over classical miners (Eq. 63).
Our second simplification is to assume that only peaceful (i.e. non-aggressive) mining occurs, meaning, if a classical miner finds a block first, the quantum miner looses the race and does not mine a block. This assumption is accurate if the time to preform a measurement prohibits the quantum miner from quickly responding to a classical miner adding a block, if the quantum miner is not highly connected in the Bitcoin network, or if network protocols are adjusted to prevent aggressive mining (e.g. the countermeasures suggested in [21]). We show, for a peaceful quantum miner with small hash rate compared to the network, that the expected fraction of blocks the quantum miner adds to the blockchain is maximized if they apply Grover iterations for
If our optimal quantum mining procedure is used, we are able to derive a simple, easy to compute approximation for the expected fraction of blocks the quantum miner contributes to the blockchain (Eq. 68). This approximation yields that blocks are cheaper to mine with 3 a quantum computer than with a classical computer if
Our conditions for advantegous mining lay the foundation for understanding when the first quantum miners could arise. Doing so is important because quantum mining brings with it security risks and other disruptions to the Bitcoin protocol. The primary security risk associated with quantum mining is stale blocks arising from aggressive mining, a vulnerability first identified in [21]. Whereas our condition is both sufficient and necessary for advantageous peaceful mining, they are only sufficient for advantageous aggressive mining. Among the other disruptions quantum mining brings is that the assumptions that mining is “progress free” and that inter-block times obey an exponential distribution no longer hold in the presence of quantum miners, creating uncertainties in Bitcoin’s security.
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