paint-brush
Probability of Success in Quantum Bitcoin Miningby@escholar

Probability of Success in Quantum Bitcoin Mining

by EScholar: Electronic Academic Papers for Scholars
EScholar: Electronic Academic Papers for Scholars HackerNoon profile picture

EScholar: Electronic Academic Papers for Scholars

@escholar

We publish the best academic work (that's too often lost...

January 14th, 2025
Read on Terminal Reader
Read this story in a terminal
Print this story
Read this story w/o Javascript
Read this story w/o Javascript
tldt arrow

Too Long; Didn't Read

This section examines the probabilities of quantum miners successfully adding blocks to the blockchain. It derives transition probabilities, explores optimal Grover iteration values for peaceful mining, and provides insights into the conditions for success in the small computational power regime.
featured image - Probability of Success in Quantum Bitcoin Mining
1x
Read by Dr. One voice-avatar

Listen to this story

EScholar: Electronic Academic Papers for Scholars HackerNoon profile picture
EScholar: Electronic Academic Papers for Scholars

EScholar: Electronic Academic Papers for Scholars

@escholar

We publish the best academic work (that's too often lost to peer reviews & the TA's desk) to the global tech community

About @escholar
LEARN MORE ABOUT @ESCHOLAR'S
EXPERTISE AND PLACE ON THE INTERNET.
0-item

STORY’S CREDIBILITY

Academic Research Paper

Academic Research Paper

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

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


image


image


image


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


image


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


image


image


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


image


The probability the quantum miner finds an additional block is then


image


by the law of total probability.


image


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


image


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


image


The value of w(n) for n even is


image


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


image


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


image


image


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


image


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


image


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


image


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


image


image


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.


image


Proof. We begin with the variable substitutions


image


These substitutions yield


image


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,


image


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


image


FIG. 2. Probability Plot

FIG. 2. Probability Plot


image


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.


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.


L O A D I N G
. . . comments & more!

About Author

EScholar: Electronic Academic Papers for Scholars HackerNoon profile picture
EScholar: Electronic Academic Papers for Scholars@escholar
We publish the best academic work (that's too often lost to peer reviews & the TA's desk) to the global tech community

TOPICS

THIS ARTICLE WAS FEATURED IN...

Permanent on Arweave
Read on Terminal Reader
Read this story in a terminal
 Terminal
Read this story w/o Javascript
Read this story w/o Javascript
 Lite
Also published here
Hackernoon
X
Bsky