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 B. Markov Chain To determine probability of success, we represent the aggressive mining procedure using the state transition graph in Figure 1. If we take φ = 0, then this state transition graph describes the peaceful mining procedure. We define T := K/r where K is the number of Grover iterations and r is the speed of the quantum miner in Grover iterations per second. The executing events in the protocols are as follows. (1) → (2) Some classical miner announces a valid block before T. (2) → (6) The quantum miner discovers a valid block using aggressive mining before T. (2) → (5) The quantum miner fails at aggressive mining, and the classically mined block is accepted to the blockchain. (1) → (3) No classical miner finds a block before T. (3) → (4) The quantum miner discovers a valid block at time T. (3) → (1) The quantum miner’s measurement at time T fails to yield a valid block. (6) → (7) The classically mined block gets accepted and the quantum miner’s block becomes stale. (6) → (8) The quantum miner’s block gets accepted and the quantum miner’s block becomes stale. We model these events as independent, and their probabilities are in the KEY. Quantum miner generate a valid block in two situations. (4) No classical miner finds a block in time T (probability 1 − µ), and the quantum miner’s subsequent measurement succeeds, which occurs with probability ν. (8) Some classical miner generates a valid block before T with probability µ and announces the block to the network. The quantum miner receives this valid block, and in response, performs a measurement (aggressive mining) that succeeds with probability φ. Subsequent blocks are then added to on top of the quantum miner’s block, as opposed to the classical miner’s block resulting in acceptance of the quantum miner’s block(probability γ). KEY Initial state


Classical miner has found a block in time T (ln 5)


Classical miner did not find a block in time T (ln 19)


Quantum miner finds a block (ln 21)


In response to classical miner finding a block, the quantum miner measured and failed to find a block (ln 15)


In response to classical miner finding a block, the quantum miner measured and found a block (ln 11)


Classical miner’s block is accepted


Quantum miner’s block is accepted (ν) Probability the quantum miner’s measurement after T seconds of Grover iterations yields a block to the quantum miner (µ) Probability the classical miner finds a block before T (φ) Quantum miner finds a block in response to classical miner finding a block first (aggressive mining) (γ) Fraction of miners who mine on the quantum miner’s block when a fork occurs States (4), (5), (7), (8) contain self loops of weight 1 (not shown) FIG. 1. State transition graph for quantum Bitcoin mining. Our procedure assumes a K that is not changed between iterations. However, the constant K case always contains an optimal quantum mining procedure; as the state of the system directly after a failed quantum measurement is always identical, a value of K that maximizes the quantum miner’s future success following this measurement must also be the same as the initial choice for K. In short, as each time the quantum miner reaches (1), the state of the system is indistinguishable, the quantum miner can always make the same choice of K. 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 B. Markov Chain To determine probability of success, we represent the aggressive mining procedure using the state transition graph in Figure 1. If we take φ = 0, then this state transition graph describes the peaceful mining procedure. We define T := K/r where K is the number of Grover iterations and r is the speed of the quantum miner in Grover iterations per second. The executing events in the protocols are as follows. (1) → (2) Some classical miner announces a valid block before T. (2) → (6) The quantum miner discovers a valid block using aggressive mining before T. (2) → (5) The quantum miner fails at aggressive mining, and the classically mined block is accepted to the blockchain. (1) → (3) No classical miner finds a block before T. (3) → (4) The quantum miner discovers a valid block at time T. (3) → (1) The quantum miner’s measurement at time T fails to yield a valid block. (6) → (7) The classically mined block gets accepted and the quantum miner’s block becomes stale. (6) → (8) The quantum miner’s block gets accepted and the quantum miner’s block becomes stale. We model these events as independent, and their probabilities are in the KEY. Quantum miner generate a valid block in two situations. (4) No classical miner finds a block in time T (probability 1 − µ), and the quantum miner’s subsequent measurement succeeds, which occurs with probability ν. (8) Some classical miner generates a valid block before T with probability µ and announces the block to the network. The quantum miner receives this valid block, and in response, performs a measurement (aggressive mining) that succeeds with probability φ. Subsequent blocks are then added to on top of the quantum miner’s block, as opposed to the classical miner’s block resulting in acceptance of the quantum miner’s block(probability γ). KEY KEY Initial state Classical miner has found a block in time T (ln 5) Classical miner did not find a block in time T (ln 19) Quantum miner finds a block (ln 21) In response to classical miner finding a block, the quantum miner measured and failed to find a block (ln 15) In response to classical miner finding a block, the quantum miner measured and found a block (ln 11) Classical miner’s block is accepted Quantum miner’s block is accepted Initial state Initial state Classical miner has found a block in time T (ln 5) Classical miner has found a block in time T (ln 5) Classical miner did not find a block in time T (ln 19) Classical miner did not find a block in time T (ln 19) Quantum miner finds a block (ln 21) Quantum miner finds a block (ln 21) In response to classical miner finding a block, the quantum miner measured and failed to find a block (ln 15) In response to classical miner finding a block, the quantum miner measured and failed to find a block (ln 15) In response to classical miner finding a block, the quantum miner measured and found a block (ln 11) In response to classical miner finding a block, the quantum miner measured and found a block (ln 11) Classical miner’s block is accepted Classical miner’s block is accepted Quantum miner’s block is accepted Quantum miner’s block is accepted (ν) Probability the quantum miner’s measurement after T seconds of Grover iterations yields a block to the quantum miner (µ) Probability the classical miner finds a block before T (φ) Quantum miner finds a block in response to classical miner finding a block first (aggressive mining) (γ) Fraction of miners who mine on the quantum miner’s block when a fork occurs States (4), (5), (7), (8) contain self loops of weight 1 (not shown) FIG. 1. State transition graph for quantum Bitcoin mining. Our procedure assumes a K that is not changed between iterations. However, the constant K case always contains an optimal quantum mining procedure; as the state of the system directly after a failed quantum measurement is always identical, a value of K that maximizes the quantum miner’s future success following this measurement must also be the same as the initial choice for K. In short, as each time the quantum miner reaches (1), the state of the system is indistinguishable, the quantum miner can always make the same choice of K. 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.

A Markov Chain Approach to Quantum Bitcoin Mining

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