Probability of Success in Quantum Bitcoin Mining

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

IV. RESULTS

A. Probability of Success

In this subsection we derive the expression for the quantum miner’s probability of successfully adding a block to the blockchain, or in other words, the expected fractions of blocks they add to the blockchain. Next, we develop a closed-form approximation for this success probability valid in the small computational power regime. Finally, we determine the value of K that optimizes this approximation in the case that the quantum miner is peaceful.

1. Expressions for Transition Probabilities

We begin our determination of success probability by considering the expression for ν. Using Theorem 1, the probability a measurement of a single register Ai at time T yields a marked header is

Finally, we find an expression for the probability φ that if a classical miner finds a block first, the quantum miner also finds a block via aggressive mining. If the quantum miner is following the peaceful protocol, then φ = 0, so here we address the aggressive case. Recall from the analysis of ν that the quantum miner’s measurement after applying k Grover iterations yields a marked header with probability

or, using the substitution t := k/r,

The probability the classical miner finds a block at time t, conditioned on t < T, is

The probability the quantum miner finds an additional block is then

by the law of total probability.

2. Total Probability of Success

Now that we have expressions for the transition probabilities in Figure 1, as well as approximations for these expressions in the √D>>K and K >>1 limit, we analyze the total probability that the quantum miner successfully adds a block to the blockchain. To start, we prove the following lemma

Lemma 1. Starting at state (1), after an infinite number of steps the probability the state is (4) is

Proof. As the only sequences of states which result in a final state of (4) are (1)(3)(4), (1)(3)(1)(3)(4), (1)(3)(1)(3)(1)(3)(4) and so on, we see that the state (4) can only be reached after an even number of steps. Let w(n) be the probability the state (4) is reached after n steps. Then, the total probability that the final state is (4) is given by

The value of w(n) for n even is

as the only way to arrive at (4) after n steps is to follow the sequence

Substituting Eq. 30 into Eq. 29 yields a geometric series:

We now derive the total probability that the quantum miner successfully mines a block.

Theorem 2. The probability P := p14 + p18 that the quantum miner successfully adds a block to the blockchain is

Proof. Examination of the state transition graph reveals that the state (2) is visited if and only if the final state (4) is not. Therefore if p12 is the probability that (2) is reached at any number of steps from (1) then

The state transition graph shows that the probability p18 that the final state is (8) is given by

Substituting this expression for p18 into P := p14 + p18 yields the statement of the theorem

3. Optimal Number of Grover Iterations

Now, we find the value of K which maximizes ˜p14. This value describes the optimal K for quantum mining when γ is small, or when the quantum miner uses only peaceful mining.

Proof. We begin with the variable substitutions

These substitutions yield

The variable x is a measure of the quantum computers power in relation to problem difficulty. As m, r, λ, D > 0, the value of x is always positive. The variable y determines the time at which the quantum miner should measure, as T = y/λ. Simplifying further,

To find the maximum, we take the derivative with respect to y and set this derivative equal to zero:

In other words, if the quantum miner plans to measure at 16 minutes, then there is approximately a 20% chance a classical miner does not find a block before they make this measurement.