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 A. Quantum Bitcoin Mining Bitcoin mining is the process through which blocks are added to the Bitcoin blockchain, a public ledger which records transactions. In Bitcoin mining, miners attempt for a given hash function f, they search for a string x such that f(x) is less than some threshold τ . A solution to this problem yields a proof-of-work which allows the miner to add a block to the blockchain and receive a subsequent Bitcoin reward. Partial inversion of a hash function is equivalent to searching for a marked item in an unordered list of items (unstructured search) if f is computationally inefficient to invert. Here, x such that f(x) < τ are the marked items. Bitcoin mining is therefore an obvious potential application of Grover’s quantum algorithm for unstructured search [13]. Whereas classical algorithms for unstructured search find a marked item in Θ(√D) queries to f, where D := N/M is the ratio of total items to marked items, Grover’s search can find a marked item in Θ(√ D) queries [6, 27]. We refer to queries to a hash function f by hashes. Quantum and classical search algorithms differ in another important way. The optimal classical algorithm for unstructured search is the simple brute-force method of guessing and checking through the search space in some random order. Contrarily, Grover’s algorithm consists of applying some number of quantum operations called Grover iterations followed by a measurement, where each Grover iteration contains two hashes. Unlike the classical brute-force algorithm, which can yield a marked item after any hash, Grover’s algorithm can only yield a marked item after the measurement step. Additionally, the more Grover iterations applied before measurement, the higher the probability that measurement yields a solution (assuming fewer than the optimal number of Grover iterations are applied). This difference between classical and quantum search algorithms has key consequences to Bitcoin’s proof-ofwork. What makes Bitcoin sensitive to this difference is that miners race to be the first to find a marked item. It is important to win the race, as only a single winner reaps the Bitcoin reward for each block added. Once a block is added, a new search problem begins rendering progress on the previous problem irrelevant. For a classical miner the race setting does not change the optimal procedure from brute-force search. However, the difficulty in evaluating the effectiveness of quantum mining is that, for a quantum miner, determining the optimal procedure in the race setting requires answering the following question first asked in [21]. Question 1. How many Grover iterations should a quantum Bitcoin miner apply before measuring? On one hand, the more Grover iterations the quantum miner applies before measuring, the more likely another miner is able to solve the problem before the measurement step is reached. On the other hand, the less Grover iterations the quantum miner applies before measuring, the less advantage they have over classical algorithms. What makes answering Question 1 challenging is that the optimal choice of when to measure depends on when other miners are expected to find a marked item. 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 A. Quantum Bitcoin Mining Bitcoin mining is the process through which blocks are added to the Bitcoin blockchain, a public ledger which records transactions. In Bitcoin mining, miners attempt for a given hash function f, they search for a string x such that f(x) is less than some threshold τ . A solution to this problem yields a proof-of-work which allows the miner to add a block to the blockchain and receive a subsequent Bitcoin reward. Partial inversion of a hash function is equivalent to searching for a marked item in an unordered list of items (unstructured search) if f is computationally inefficient to invert. Here, x such that f(x) < τ are the marked items. Bitcoin mining is therefore an obvious potential application of Grover’s quantum algorithm for unstructured search [13]. Whereas classical algorithms for unstructured search find a marked item in Θ(√D) queries to f, where D := N/M is the ratio of total items to marked items, Grover’s search can find a marked item in Θ(√ D) queries [6, 27]. We refer to queries to a hash function f by hashes. Quantum and classical search algorithms differ in another important way. The optimal classical algorithm for unstructured search is the simple brute-force method of guessing and checking through the search space in some random order. Contrarily, Grover’s algorithm consists of applying some number of quantum operations called Grover iterations followed by a measurement, where each Grover iteration contains two hashes. Unlike the classical brute-force algorithm, which can yield a marked item after any hash, Grover’s algorithm can only yield a marked item after the measurement step. Additionally, the more Grover iterations applied before measurement, the higher the probability that measurement yields a solution (assuming fewer than the optimal number of Grover iterations are applied). This difference between classical and quantum search algorithms has key consequences to Bitcoin’s proof-ofwork. What makes Bitcoin sensitive to this difference is that miners race to be the first to find a marked item. It is important to win the race, as only a single winner reaps the Bitcoin reward for each block added. Once a block is added, a new search problem begins rendering progress on the previous problem irrelevant. For a classical miner the race setting does not change the optimal procedure from brute-force search. However, the difficulty in evaluating the effectiveness of quantum mining is that, for a quantum miner, determining the optimal procedure in the race setting requires answering the following question first asked in [21]. Question 1 . How many Grover iterations should a quantum Bitcoin miner apply before measuring? Question 1 How many Grover iterations should a quantum Bitcoin miner apply before measuring? On one hand, the more Grover iterations the quantum miner applies before measuring, the more likely another miner is able to solve the problem before the measurement step is reached. On the other hand, the less Grover iterations the quantum miner applies before measuring, the less advantage they have over classical algorithms. What makes answering Question 1 challenging is that the optimal choice of when to measure depends on when other miners are expected to find a marked item. 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.

How Many Grover Iterations Should a Quantum Bitcoin Miner Apply?

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

15 Common Types of Unethical Behavior Found in Open-Source Projects

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)

15 Common Types of Unethical Behavior Found in Open-Source Projects

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

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps