Strategies for quantum-enabled Bitcoin miners Zach Manson and Barry C. Sanders Institute for Quantum Science and Technology, University of Calgary, Alberta, Canada T2N 1N4 We study the impact that two miners equipped with quantum computers purpose-built for quantum Bitcoin mining will have on the 51% attack threshold of the Bitcoin network, given that the miners are playing a competitive game against each other to be the first to mine a block. We extend an existing game-theoretic framework for Bitcoin mining and compute the resultant payoff matrices. From these payoff matrices, we determine optimal quantum mining strategies for two non-colluding and aggressive quantum miners with multiple opportunities at finding a valid block in an otherwise classical Bitcoin network. We show that these optimal quantum mining strategies have a negligible effect on the 51% attack threshold. The novelty of our work is the inclusion of the Aggressive Quantum Mining Strategy and the realistic approach of allowing the quantum miners to restart their search if their measurements do not yield a valid block when determining the optimal quantum mining strategies. Our result is important for evaluating quantum-mining threats on cryptocurrencies based on Proof-of-Work, e.g. Bitcoin.
arXiv:2607.23952v1 [quant-ph] 27 Jul 2026
CONTENTS
I. Introduction
2
II. Background A. Bitcoin protocol 1. Structure of the blockchain 2. Proof of work 3. Temporary forks and the 51% attack B. Quantum mining 1. Grover’s algorithm 2. Applying the FQS algorithm to Bitcoin mining 3. Aggressive and peaceful quantum mining C. Quantum races 1. Preliminaries on game theory 2. Computing a Nash equilibrium 3. Two-player quantum races
6 6 6 9 12 14 14 17 19 20 20 23 24
III. Approach A. Model 1. Model foundations 2. Alice and Bob 3. Adversarial model B. Mathematics 1. Pure strategies 2. Payoff matrices 3. AQMS C. Methods 1. Computing payoff matrices 2. Optimal quantum mining strategy computation 3. Quantum mining simulation
26 26 26 26 27 28 28 30 32 33 34 34 35
IV. Results A. Payoff matrices for quantum miners 1. Payoff matrices for multiple measurements 2. Payoff entries with Sattath’s AQMS B. Optimal quantum mining strategies 1. Two measurements 2. Three and four measurements
36 36 36 37 39 39 40
2 3. One measurement and expected payoffs C. Decrease of 51% attack threshold
40 47
V. Discussion
47
VI. Conclusions
50
VII. Acknowledgments
51
References
52 I.
INTRODUCTION
Bitcoin is a decentralized digital currency whose security relies on the assumption that it is prohibitively expensive for a consortium to control the majority of the Bitcoin network’s computational power in a “51% attack” [1]. However, if quantum computers are built to scale, this assumption will no longer hold, as Grover’s algorithm could be used to reduce the cost of executing a 51% attack [2]. Prior works have studied this threat, but only under narrow and simplistic adversarial models [2, 3]. These works show that, in theory, Grover’s algorithm could significantly lower the cost of executing a 51% attack, but the magnitude of this threat within a more practical setting remains unknown. We study this same threat in a broader and more realistic adversarial model and quantify the impact that Grover’s algorithm has on the cost of executing a 51% attack. First we define a quantum miner and then state the problem we address. Definition 1 (Quantum miner). A quantum miner is a Bitcoin miner with access to a quantum computer. Remark 1. Prior work restricts a quantum miner to undertaking a peaceful mining strategy and just one quantum computation per race [3], whereas we permit Sattath’s aggressive quantum mining strategy [2] and up to c quantum computations and up to an arbitrary κ Grover iterations over all quantum computations, compared to prior work for which c = 1, κ = kopt
(1.1)
for kopt the optimal number of Grover iterations that maximizes the success probability of Grover’s algorithm for partially inverting the SHA-256 hash function to yield a valid proof-of-work (PoW). Specifically, we solve the following problem. Problem 1. Given two quantum miners in the Bitcoin network, determine their optimal quantum mining strategies and the resulting threshold for the 51% attack. A quantum mining strategy is the number of Grover iterations performed by the quantum miners for each of their measurements. Bitcoin’s (capital “B” referring to the network/protocol) security against 51% attacks relies on network-wide consensus [1]. To achieve this consensus, Bitcoin relies on the consensus mechanism of PoW, where participants, called miners, compete to solve a computational problem based on unstructured search, with the winning miner earning the right to extend the blockchain and receiving bitcoins (lowercase “b” referring to the currency) as a reward. As a large number of miners participate in this competition, and because the difficulty of the underlying computational problem is adjusted periodically based on the total computational power of the network, it is prohibitively expensive for a consortium to dominate the mining process and execute a 51% attack. However, if quantum computers are built to scale, miners could use Grover’s algorithm to solve the Bitcoin mining problem with a theoretical quadratic advantage over classical methods [4]. Furthermore, quantum Bitcoin miners (quantum miners) may adopt a quantum-specific technique called the aggressive quantum mining strategy [2], which increases the rate at which temporary forks in the blockchain occur. Classically, this is a known security issue, as a higher fork rate decreases the cost to successfully execute a 51% attack [2]. Whereas prior work concerns the theoretical possibility of the threat arising from quantum miners decreasing the cost of successfully executing a 51% attack [2, 3], practically the threat level to the Bitcoin network is unknown. The quantum threat to Bitcoin in general has been studied from several different angles. Kiktenko et al. [5] study the quantum threats to both Bitcoin’s digital signature scheme and the hash function used in Bitcoin mining, and propose a quantum key distribution-based replacement for Proof-of-Work. More recently, Babbush et al. [6] show that Shor’s algorithm can break Bitcoin’s digital signature scheme with substantially fewer resources than previously estimated,
3 and Dallaire-Demers and BTQ Technologies [7] show that quantum Bitcoin mining requires an extraordinary amount of power. No existing work, however, studies the effect of quantum miners on Bitcoin’s stale rate under a realistic adversarial model. In this work, we fill in this gap by extending an existing game-theoretic model of quantum Bitcoin mining to incorporate behaviour that more accurately reflects how quantum mining would be performed in practice. Our model accounts for the quantum miners’ ability to perform multiple quantum measurements between successive blocks, as well as their use of the aggressive quantum mining strategy. We determine the optimal quantum mining strategies for the quantum miners under these conditions, and analyze their effect on the 51% attack threshold. In this work, we consider a setting where two quantum miners, Alice and Bob, are hidden within an otherwise classical Bitcoin network. We extend the game-theoretic approach of Lee et al. [3] to determine optimal quantum mining strategies for quantum miners who perform multiple quantum measurements between consecutive blocks and use the aggressive quantum mining strategy. These optimal quantum mining strategies correspond to Nash equilibria, which are strategies for which no quantum miner can increase their expected payoff alone. These Nash equilibria are computed via the Lemke-Howson algorithm, which computes an exact Nash equilibrium for two-player games [8]. We simulate the employment of these optimal quantum mining strategies within the Bitcoin network to determine their effect on the 51% attack threshold, and finally determine the conditions for which executing a 51% attack becomes feasible in the presence of quantum miners. Our research is structured as follows. Here we provide a table of symbols and abbreviations for the reader’s convenience. In §II, we provide information on the background of our system. In §III, we present our extended model, the mathematics which describes our model, and the methods used to determine our results. §IV details our key results, which are discussed in §V. Finally, we present our conclusions in §VI.
4 TABLE I. Symbols and abbreviations. Symbol / Abbreviation UTXO BTC TXID PoW ASIC DAG FQS PQMS AQMS S2QR TFNP PPAD V hash SHA-2562 (s) M T R H P t τ N t̄11 t̄ S(X) fR ftt̄, t11 τ̃ D γ γS λ pstale q qc
Definition Unspent transaction output Bitcoin currency Transaction ID Proof-of-Work Application-Specific Integrated Circuit Directed Acyclic Graph Finite-Budget Quantum Search Peaceful Quantum Mining Strategy Aggressive Quantum Mining Strategy Symmetric Two-Player Quantum Races Total Function Nondeterministic Polynomial Polynomial Parity Arguments on Directed Graphs Bitcoin protocol version Cryptographic hash function Double-application of SHA-256 on input s Mempool Set of all valid but unconfirmed transactions Merkle root Block header Previous block hash Timestamp Difficulty target Nonce Median timestamp of the last 11 blocks Network-adjusted time Set of all subsets whose elements follow the partial ordering of X Merkle root computation oracle Timestamp validation oracle Uncompressed difficulty target Network difficulty Propagation parameter Sattath’s propagation parameter Block arrival rate Stale rate Hash rate of the Bitcoin network Fractional hash rate
5 TABLE II. Symbols and abbreviations (continued). Symbol / Abbreviation f M H uni(H ) her(H ) Uf H U0 G x mea [x] [x]0 p(k) kopt 32 kopt ℘ n℘ Si σi supp(σ) Σi s∗ σ∗ ui u v U (σ ∗ ) A B D0 c κ S0 S0c k(j) α/β i XA , XBi Ai /Bi Ameas /Bimeas i AQMS Ai /BiAQMS Ai /Bi ℓA /ℓB S0′ nq (S0c )′ ns bi fi P95 /P99 P>1/3 Pdet qi FAi /FBi
Definition 32-bit Boolean oracle Subset of marked inputs Hilbert space Set of unitary operators on H Set of Hermitian operators on H 32-qubit quantum phase oracle Single-qubit Hadamard gate 32-qubit Householder reflection 32-qubit Grover iterate Label in computational basis returned by the FQS algorithm Quantum measurement {1, 2, . . . , x} {0, 1, 2, . . . , x} Success probability for the FQS algorithm after k iterations Optimal number of Grover iterations Optimal number of Grover iterations for 32-bit search Finite set of players Number of players Set of actions for player i Mixed strategy for player i Support of mixed strategy σ Set of mixed strategies for player i Pure strategy profile Mixed strategy profile Payoff function for player i Alice’s payoff function Bob’s payoff function Expected payoff for mixed strategy profile σ ∗ Alice’s payoff matrix Bob’s payoff matrix Network difficulty threshold for at least one expected solution to the Bounded PoW problem Number of quantum-state opportunities for Alice and Bob Grover iteration budget Alice’s and Bob’s pure strategy set for a single quantum measurement Alice’s and Bob’s pure strategy set jth pure strategy of S0c in lexicographic ordering Row and column indices of Alice’s and Bob’s payoff matrices Outcome of Alice’s / Bob’s ith Grover state measurement Alice’s / Bob’s payoff matrix for their ith quantum measurement Payoff matrix for Alice’s/Bob’s ith quantum measurement alone Payoff matrix for Alice’s/Bob’s ith quantum measurement from Sattath’s AQMS Cumulative Grover iterations performed by Alice / Bob Index of Alice’s / Bob’s most recent measurement before the other’s ith Sampled subset of S0 used for computation Number of sampled Grover iteration counts from S0 Reduced pure strategy set of Alice and Bob Number of simulated days Number of blocks mined on simulated day i Number of forks observed on simulated day i 95th/99th percentiles Empirical probability of pstale > 1/3 on any given day Empirical detection probability p-value for simulated day i under null hypothesis that no quantum miners are present Cumulative probability that Alice / Bob fails their first i measurements
6 II.
BACKGROUND
In this section, we provide the essential background to frame the context of our research. We begin with an explanation of Bitcoin mining: detailing what Bitcoin is, how the Bitcoin network operates, and the mechanics of mining Bitcoin. Then we discuss quantum mining: detailing how Grover’s algorithm could be utilized to mine Bitcoin, the implications of quantum Bitcoin mining over the classical case, and introducing the aggressive quantum mining strategy. Finally, we discuss quantum races: summarizing the notion of quantum races [3] and explaining the relevant game-theoretic concepts. A.
Bitcoin protocol
Here we give an overview of the Bitcoin protocol. We begin by describing how the Bitcoin network operates by detailing how “blocks” store transactions and how the block headers are linked to form the blockchain. Then we describe what Proof-of-Work is and how it is quintessential to the mining process. Finally, we discuss temporary forks in the blockchain and their relation to the 51% attack. 1.
Structure of the blockchain
We describe the structure of the blockchain. We begin with a brief overview of the Bitcoin network. Then, we explain cryptographic hash functions, which play an important role in the Bitcoin protocol. We then move on to a discussion on what a bitcoin is, and how the ownership of bitcoin is recorded. Next, we discuss how the chain of ownership is recorded in transactions, and then explain how these transactions are aggregated into a data structure called a block, discussing all components. Finally, we discuss how the block headers link to form a digital ledger called the blockchain. We begin by providing a brief overview of the network that Bitcoin operates on. Bitcoin (capital “B” referring to the network/protocol) is structured as a decentralized peer-to-peer network [1]. In this network, the computers that participate, called nodes, are peers to each other and interconnect to form a mesh network, meaning that each node connects to multiple others with no hierarchy. These nodes communicate and synchronize with each other by following the current Bitcoin protocol labeled V , which is the system of rules that governs how the Bitcoin network operates. Whereas all nodes share the responsibility of routing information and data, some nodes can take on additional responsibilities. Nodes that take on all possible responsibilities are called “full nodes”. A user interacts with the Bitcoin network to send and receive bitcoin currency through a wallet application. Now we give an overview of cryptographic hash functions. Cryptographic hash functions are an essential component to Bitcoin, used for secure identification and ensuring the integrity of data [1, 9]. Definition 2 (Hash function [10] ). The m-bit hash of a bit string of arbitrary size (with ∗ for wildcard notation) is the uniformly distributed mapping hash : {0, 1}∗ → {0, 1}m : s 7→ hash(s).
(2.1)
Remark 2 (Approved hash function [10] ). An approved hash function such as SHA-2562 is efficiently computable, one-way (computationally difficult to invert), and collision-resistant (computationally difficult to find two inputs that map to the same output). We define the partial inversion of a hash function as follows. Definition 3 (Partial inversion of a hash function ). Given an m-bit hash function and a threshold Θ ∈ {0, 1}m , the partial inversion of the hash is a bit string s ∈ {0, 1}∗ such that hash(s) < Θ.
(2.2)
In the Bitcoin protocol, the accepted hash function SHA-256 is double applied SHA-2562 (s) := SHA-256(SHA-256(s))
(2.3)
when hashing [1, 11]. Now we discuss what a bitcoin is from a conceptual standpoint. At its core, a bitcoin (lowercase “b” referring to the currency) is not a physical or digital entity but a unit of account (an economic term for quantifying the value
7 of goods or services) recorded on a public, decentralized ledger [9]. The ownership of bitcoin is defined by the right to control a collection of Unspent Transaction Outputs (UTXOs), which can conceptually be thought of as discrete, indivisible quantities of bitcoin that are recognized by the entire network as valid [1]. The term “indivisible” means that a UTXO must be spent in full, and cannot be divided or partially spent [1]. Definition 4 (UTXO [1]). A UTXO is a 2-tuple of an integer representing an amount of bitcoin denominated in satoshis (1 satoshi = 10−8 BTC) and a byte stream (a sequence of bytes) of variable size called the locking script, which sets the conditions for that amount of bitcoin to be spent and also includes the length of the script itself. The conditions of the locking script are written in a simple Turing-incomplete scripting language, allowing for a plethora of requirements to be set for spending a UTXO [1]. However, the most common conditions involve requiring proof of ownership through cryptographic keys [1]. Definition 5 (Private key [9]). A private key is a 256-bit integer chosen uniformly at random. Definition 6 (Public key [1]). A public key is derived from the private key using a cryptographic one-way function. Currently, the one-way function used by the Bitcoin protocol is elliptic curve cryptography on the secp256k1 curve [1]. Definition 7 (Address [1]). An address is a human-readable string derived from a public key, specifying the destination for receiving bitcoin. Thus, ownership of bitcoin is conferred by controlling private-public key pairs and fulfilling the conditions of the locking scripts [1]. When bitcoin is exchanged or transacted, UTXOs are spent by the sender, and new UTXOs are created, for which only the receiver can unlock with their key pair(s). Here we explain the purpose and structure of Bitcoin transactions. Transactions record the creation and consumption of UTXOs, and also record the proof of ownership of bitcoin [1]. Each transaction consumes existing UTXOs as input, and creates new UTXOs as outputs. Each input references a UTXO to be spent and includes the transaction ID txid := SHA-2562 (bytes(x))
(2.4)
where bytes(x) is the byte representation of a transaction x, the output index (specifying which UTXO from that transaction is being referenced), an unlocking script (satisfying the conditions for spending that UTXO), and a sequence number (for relative time-locks and enabling additional features) [1]. We now define a Bitcoin transaction formally in a way that differs slightly from Antonopoulos’s definition [1] but is congruent. Definition 8 (Bitcoin Transaction ). A Bitcoin transaction is a 2-tuple comprising a list of inputs and a list of outputs, with each input being a 4-tuple referencing a specific UTXO and comprising a 256-bit transaction identification ( txid), a 32-bit index pointing to a specific output from a previous transaction, a variable-size (up to 10 000 bytes) unlocking script ( scriptSig) that provides the necessary information for the locking script, and a 32-bit sequence number ( nSequence) for establishing complex time locks and to set flags to enable additional transaction features, and each output being a new UTXO created by the transaction. If the total value of the UTXOs being spent exceeds the amount being sent to the recipient(s), then a new UTXO is created in the output sending the change back to the sender [1]. Although the change is sent back to the sender, the value of the input UTXOs is typically not equal to the value of the output UTXOs; the difference represents the transaction fee that the sender agrees to pay as a rule of the protocol [1]. Transactions are grouped and stored in a decentralized and distributed digital ledger, which is a digitally-maintained record of transactions that is shared, replicated, and synchronized across multiple network nodes [1, 9]. All full nodes in the network maintain a set of all unspent outputs from all transactions to construct transaction inputs quickly and to efficiently validate transactions to ensure immutability [1]. Similarly, all nodes except those running a lightweight version of the Bitcoin protocol maintain a partially-ordered set (poset) of unconfirmed transactions known as mempool, which we now define [1].
8
FIG. 1. The structure of a block. Blocks are depicted as squares that are partitioned into two rectangles. The upper rectangle is labeled Hi , which is the block header of the ith block, and the lower rectangle is the Merkle tree with root R. Within the Merkle tree, a triangle (△) represents the hash of an individual transaction. A square (□) represents the application of a hash function whose inputs are the contents inside the square, and || denotes concatenation. The Merkle tree construction is shown for an even number of transactions. For an odd number of transactions, the last transaction is duplicated to make the number of transactions even. The arrows between blocks represent the hash of the previous block’s header. Definition 9 (Mempool). The mempool M := (T, ≺)
(2.5)
is a poset where T is the set of all valid but unconfirmed Bitcoin transactions and ≺ is a binary relation on T such that for x, y ∈ T , x ≺ y iff (if and only if ) the bitstring corresponding to the txid of x is in the inputs of y. Now we explain how blocks are structured and the nature of their components. Bitcoin transactions are permanently recorded in a digital ledger by first grouping them into container data structures called blocks [1, 12], which are illustrated in Fig. 1. In this figure, the Merkle tree is a binary tree where individual transactions are hashed at the leaves, arranged in an arbitrary order. Parent nodes are formed by recursively hashing the concatenation of each pair of children until a single hash remains, called the Merkle root R [1]. Definition 10 (Block [1] ). A block is a container data structure comprising a block header H := (V, P, R, t, τ, N ) ∈ {0, 1}32 × {0, 1}256 × {0, 1}256 × {0, 1}32 × {0, 1}32 × {0, 1}32
(2.6)
which is an 80-byte sextuple containing metadata and a list of transactions aggregated into a Merkle tree for efficient verification of membership and summarization of the included transactions. The elements of the block header are a Bitcoin protocol version V ∈ {0, 1}32 , the double SHA-256 hash P ∈ {0, 1}256 of the preceding block’s header H, a Merkle root R ∈ {0, 1}256 , a timestamp t ∈ {0, 1}32 that records the approximate Unix time when the block was created, a difficulty target τ ∈ {0, 1}32 encoding a threshold that H must satisfy to be considered valid (see Def. 15), and an arbitrary nonce N ∈ {0, 1}32 set by the block’s creator. Remark 3 (Compression of the difficulty target τ [1] ). To reduce the size of the block header, the difficulty target τ is stored as a 4-byte compressed encoding of a 256-bit string τ̃ . Let b0,1,2,3 ∈ {0, 1}8 be the bytes of τ in big-endian order. The full 256-bit difficulty target is computed via τ̃ := 28(b0 −3) 216 b1 + 28 b2 + b3 .
(2.7)
(2.8)
9
FIG. 2. The blockchain depicted as a back-linked list of blocks. Each block is shown as a square divided into two rectangles. The upper rectangle represents the block header H of the ith block, and the lower rectangle contains the Merkle tree of transactions, depicted as a tree structure. Back-links are depicted by arrows between block headers, representing the previous block hash stored in each block’s header. The ellipses denote further preceding and succeeding blocks in the blockchain, and the block with header labeled G represents the genesis block, which has no predecessor. The value of τ̃ is updated every 2016 blocks according to the recurrence relation τ̃i+1 ←
t2016 τ̃i , 20160 min
(2.9)
where t2016 is the time to mine the last 2016 blocks. The Merkle root R is stored in the block header to summarize the transactions included and enable efficient verification of membership, requiring only O(log2 nT ) computations for nT transactions [1]. The previous block hash P in each block’s header uniquely and unambiguously identifies the previous block, and serves as a back link in a linked-list structure, linking all blocks chronologically. Now we explain what the blockchain is. The blockchain is structured as an ordered back-linked list of blocks that extends all the way to the first block, which is known as the genesis block [1]. The genesis block does not have a predecessor, and contains a trivial hash in its header. This structure is illustrated in Fig. 2. Any alteration to a previous block would change its hash, invalidating the block hash of all subsequent blocks. Correcting this invalidation requires significant computational effort, making the blockchain resistant to tampering [1]. Every node in the network maintains a local copy of the blockchain and individually verifies it against the copies held by other nodes to ensure consistency and maintain integrity [1]. In cases where nodes have blockchains that conflict with each other, each node independently determines which blockchain to consider authoritative by choosing the blockchain with the largest block height (longest length) [1]. Definition 11 (Block height [9]). The block height is the number of blocks between a given block and the genesis block, which has a block height of 0. As a result, this structure forms a decentralized and immutable digital ledger that records all Bitcoin transactions. 2.
Proof of work
Here we describe the mechanics of Proof-of-Work. We begin by discussing consensus in the context of blockchains and the importance of achieving consensus among the decentralized network. Then, we explain the specifics of Proofof-Work and how it functions to achieve consensus. Afterwards, we describe the process of mining Bitcoin and how it relates to Proof-of-Work. Finally, we describe the role of the coinbase transaction and discuss how its structure is exploited when mining. We explain the concept of consensus in the Bitcoin network and how it emerges from the protocol. In general, consensus refers to a general agreement among a group. We start by giving an accepted definition that describes how consensus is achieved in the Bitcoin network [1], which we refer to as operational consensus because it focuses on the mechanism rather than the concept of a general agreement itself. Definition 12 (Operational consensus ). Operational consensus is achieved when a majority of nodes in the network have the same blocks in the blockchain that they each validate as requiring the most total hashes. While this definition captures the mechanism by which consensus emerges, we also offer a definition that aligns more directly with the conceptual meaning of a general agreement.
10 Definition 13 (Consensus agreement ). A consensus agreement is a general agreement that all nodes in the network accept operational consensus. In the Bitcoin network, consensus emerges through a mechanism called Proof-of-Work (PoW) [1], which enables nodes to achieve a consensus agreement without a fixed election period or central coordination. PoW enforces the rules of the Bitcoin protocol that determine which blockchain is most authoritative and which blocks can be appended to it. At the same time, PoW also provides the necessary incentives for nodes to participate in maintaining and extending the blockchain. Now we discuss the technical details of PoW. PoW is a consensus mechanism that performs two functions [1]. One function is to establish the eligibility of blocks to be appended to the blockchain. The second function is to enforce the verification of blocks and transactions by nodes. To determine which blocks can be appended, participating nodes compete to solve a cryptographic problem based on the partial inversion of the SHA-256 hash function. As part of this process, the timestamp included in each block’s header must satisfy a validity condition [1], which we now define. Definition 14 (Valid timestamp ). A valid timestamp t satisfies t̄11 < t < t̄ + 2 hours
(2.10)
where t̄11 is the median timestamp of the last 11 blocks, and t̄ is the network-adjusted time, which is the median of a node’s local system time and the times reported by all connected peers. Definition 15 (PoW condition ). The PoW condition is SHA-2562 (V ∥ P ∥ R ∥ t ∥ τ ∥ N ) < τ̃ ,
(2.11)
where ∥ denotes concatenation, R is a valid Merkle root computed from the ordered transactions included in the block, t is a valid timestamp, and τ ∈ {0, 1}32 is the difficulty target. A block may be appended to the blockchain iff it satisfies the PoW condition. The problem of finding a block header that satisfies the PoW condition is now formalized as a computational problem. Given any set X, the power set 2X is the set containing all subsets of X. If X is a poset, we define S(X) as the set of all subsets whose elements are partially ordered according to the partial ordering of X. Problem 2 (PoW problem ). Given a version V , a previous block hash P , a difficulty target τ , a mempool of valid transactions M, a Merkle root computation oracle fR : S(M) → {0, 1}256
(2.12)
the network-adjusted time t̄, the median timestamp of the last 11 blocks t̄11 , and a timestamp validation oracle ftt̄,t̄11 : {0, 1}32 → {0, 1},
(2.13)
find a timestamp t, a sequence of transactions Tx ∈ S(M), and a nonce N such that the resultant block header H satisfies the PoW condition. Definition 16 (Network difficulty [9] ). The network difficulty function 256
D(τ̃ ) := 2 /τ̃
(2.14)
represents the expected number of hashes required to find a block header satisfying the PoW condition, where τ̃ is the full 256-bit difficulty target. Remark 4 (Rationale for D). As the 2256 outputs of SHA-256 are uniformly distributed (Definition 2), the probability that an output of SHA-256 is less than a given τ̃ is τ̃/2256 . Thus, the expected number of hashes computed before finding a header that satisfies the PoW condition is the network difficulty function (2.14). Although we define the network difficulty D as a function of τ̃ , we refer to the evaluated value D(τ̃ ) simply as D. In practice, solving Problem 2 by iterating over all 2320 possible values of the bitstrings (fR (Tx ), t, N ) is infeasible due to the overhead required for recomputing the Merkle root and validating the timestamp. Instead of solving Problem 2 all at once, nodes fix all bitstrings except the nonce and execute a brute-force search over the 232 possible nonce values. This process is repeated over multiple instances of this bounded problem until a solution to Problem 3 is found.
11
FIG. 3. A visualization of finding a proof-of-work for (a) the PoW problem and (b) the bounded PoW problem. The concatenated block header is represented by six rectangles. A rectangle represents a specific bitstring in the concatenation of the block header. Each rectangle is labeled above by the symbol of the element in the block header. The length of the bitstring for each label is indicated below the rectangle. A filled rectangle represents a bitstring whose value remains constant. An empty rectangle denotes a bitstring whose value is computed by the node finding a proof-of-work. In (a), for the Merkle Root R, the mempool M and the oracle fR are inputs, as are t̄, t̄11 , and ftt̄,t̄11 for the timestamp t. In (b), only the nonce N is computed. The nonce is represented as an empty rectangle in both figures, as it does not require any inputs. Problem 3 (Bounded PoW problem ). Given a version V , a previous block hash P , a Merkle root R, a valid timestamp t, and a difficulty target τ , find a nonce N such that the resultant H satisfies the PoW condition. The probability that a valid nonce exists within a search space of size 232 is approximately 232/D = τ̃/2224 .
(2.15)
The solution to Problems 2 and 3 is called the proof-of-work (lowercase). Whereas Antonopoulos uses “Proof-of-Work” to refer to both the mechanism and any solution to Problem 2 [1], we adopt the lower case to distinguish a solution from the consensus mechanism. A proof-of-work demonstrates that a node has expended sufficient computational effort based on the PoW condition. Satisfying the PoW condition grants that node the right to append a block to the blockchain [1]. In return, the node receives a reward for its efforts, which encourages other nodes to participate in the competition. We describe the process of mining Bitcoin and outline the responsibilities of nodes that participate as miners. Bitcoin mining refers to the process of extending the blockchain by constructing candidate blocks and searching for a proof-of-work [1]. Bitcoin miners, the nodes that participate in this process, are responsible for [1] validating new blocks and transactions when they are received by broadcast, placing validated transactions into their mempool, constructing the coinbase transaction, which pays the reward to the miner, selecting transactions from their mempool and constructing a Merkle tree with root R, which includes the coinbase transaction, constructing a candidate block with values for V , P , and τ using both public sources of information and local data, solving Problem 2 to find a proof-of-work and form a valid block header, and broadcasting the newly-mined block to the network. As a reward for extending the blockchain, a miner receives the transaction fees of all included transactions, and a fixed amount of newly minted bitcoins, with this fixed amount being halved approximately every four years [1, 12]. As a result, miners choose transactions from their mempool commencing with the highest transaction fee available when forming a candidate block [9]. Additionally, miners are responsible for independently updating the value of τ every 2016 blocks (2.9). As all miners compute the value of τ based on the publicly available blockchain, all miners will compute the same result, and any block with an incorrect value of τ in its header is considered invalid [1].
12
FIG. 4. The blockchain represented as a DAG during a temporary fork. A vertex (□) represents a block, each labeled with its block height. Directed edges represent the block hash of preceding blocks. A blue square (□) indicates a block that has become part of the longest blockchain. A red square (□) indicates a block that is not part of the longest blockchain. Each vertex (except the genesis block with height 0) has one outgoing edge to a preceding block, but can have multiple incoming edges from succeeding blocks during a temporary fork. This figure represents a temporary fork because not all nodes have the same symbol. Remark 5 (Average blocks per day [1]). On average, the Bitcoin blockchain produces 144 blocks per day. We describe the role and structure of the coinbase transaction. The mining reward is paid to the miner by what is known as the coinbase transaction [1]. The coinbase transaction is the first transaction in a block and is constructed by a miner as part of the mining process. Unlike other transactions, the coinbase transaction does not consume any UTXO as input. Instead, the coinbase transaction includes trivial data in place of the transaction input, and the transaction output is constructed by the miner so that the funds go to that miner’s wallet. Importantly, the unlocking script is replaced by coinbase data, which is a field containing arbitrary data that must contain between 2 and 100 bytes. For blocks with version 2 or greater, the first few bytes of this field are reserved to contain the block height [1]. We describe how miners exploit the structure of the coinbase transaction to extend their search space when mining. The 32-bit nonce within the block header allows miners to quickly generate up to 232 distinct block headers for each candidate block [1]. However, because the network computes hashes at an extremely high rate (primarily due to specialized mining devices called Application-Specific Integrated Circuits, or ASICs), the mining difficulty has been adjusted such that this limited nonce space is often exhausted before a proof-of-work is found. Rather than waiting for another miner to succeed and then reset the competition, miners require a way to seed new search spaces once the standard range of nonces is exhausted. Although adjusting the timestamp or reordering the transactions in the Merkle tree can alter the block header, these methods have limitations: only a small range of timestamps are considered valid, and reordering transactions requires a full recomputation of the Merkle tree. The practical solution has been to exploit the structure of the coinbase transaction. Miners utilize the 2 to 100 bytes of arbitrary data permitted in the coinbase field to seed new search spaces in a technique called extraNonce. This technique requires recomputing the left-most branch of the Merkle tree for each iteration of the extraNonce. Although extraNonce is not part of the Bitcoin protocol, it is widely adopted by miners in practice. 3.
Temporary forks and the 51% attack
Now we discuss what temporary forks are and how they relate to the 51% attack. We begin with an explanation of what a temporary fork is, and how they occur both naturally and intentionally. Then, we introduce the so-called “propagation parameter”, and discuss how it can be used for modelling forks in the blockchain. Finally, we discuss the 51% attack and how it relates to the rate at which forks appear in the blockchain. We explain what temporary forks are and how they arise in the blockchain. In the blockchain, temporary forks occasionally occur when multiple blocks are mined nearly simultaneously [1]. These blocks are broadcast through the network, and miners will mine atop of the block they receive first, causing the network to temporarily lose consensus. In this situation, the temporary forks form a directed acyclic graph (DAG), which is illustrated in Fig. 4. Eventually, one branch of the temporary fork will achieve more cumulative proof-of-work than the others, becoming the authoritative branch of the blockchain [1]. Blocks in the losing branches become “stale”. Definition 17 (Stale block [1] ). A stale block is a block that was successfully mined but has not been included in the longest branch of the blockchain. Miners who have mined blocks that become stale do not receive any mining rewards [9]. Temporary forks can occur naturally as a result of network effects [1] as depicted in Fig. 5. However, temporary forks can also be created deliberately by a consortium of miners (a singlet or a collection of miners exercising control over a cumulative mining
13
FIG. 5. A temporary fork occurring due to near-simultaneous block discovery. A vertex (⃝) represents a node in the Bitcoin network. A red vertex (⃝) represents a node that has just mined a new block. Each vertex contains either a star (⋆), representing the state of the network before the fork, or a triangle (△) or a square (□) representing one of the new branches created by the temporary fork. An arrow within an edge indicates the broadcast of a new block to a peer. An edge without an arrow represents a peer-to-peer connection where no new block is being broadcast. power) who could adopt a strategy to increase their expected revenue. One such strategy is known as the selfish mining strategy, where a consortium temporarily withholds the broadcast of newly-mined blocks to gain an advantage [13]. Now we discuss the propagation parameter. To capture the complexities that determine the outcome of temporary forks, we introduce the propagation parameter γ. Definition 18 (Propagation parameter [13, 14]). The propagation parameter γ is the fraction of honest miners who will mine on top of a given miner’s block in the event of a temporary fork. This parameter abstracts the plethora of factors that influences the resolution of a temporary fork such as the propagation time, network architecture, and unique strategies employed by miners that influence block announcements [2, 13, 14]. However, our use of γ differs from the prior definition (Def. 18), as we adopt Sattath’s definition [2]. Definition 19 (Sattath’s propagation parameter [2]). Sattath’s propagation parameter γS is the probability that a designated miner will successfully extend their branch of the blockchain first. We describe the 51% attack [1, 2] formally and explain the 51% attack threshold and the relative hash rate, which quantifies the authority of a consortium of miners. Definition 20 (Hash rate [9] ). The hash rate q is the number of hashes that can be computed per second by a consortium comprising all miners in the network, and the fractional hash rate qc is the proportion of the hash rate that can be performed by a given consortium. Remark 6 (Block arrival times [15] ). The block arrival times in Bitcoin are modelled as a Poisson process, meaning that they follow exponential distribution with a rate parameter of λ = 1/600 seconds. However, this model is only valid if the hash rate and network difficulty remain constant over the period being modelled. In practice, the hash rate and network difficulty evolve as functions of time, as miners are constantly joining and leaving the Bitcoin network and the technology for mining Bitcoin improves. Thus, the block arrival times are more accurately modelled as a nonhomogeneous Poisson process with a rate parameter λ that is proportional to the ratio of hash rate to the network difficulty.
14 Definition 21 (The 51% attack [2] ). The 51% attack means that some consortium controls over 50% of the hash rate of the network, enabling the consortium to double-spend coins, reverse transactions, or create their own branch of the blockchain with a high probability of success. Remark 7 (Duration of a 51% attack [1]). Executing a 51% attack is not instantaneous, as the consortium must mine many consecutive blocks faster than the rest of the Bitcoin network. In other words, the conditions enabling a 51% attack must hold for an extended period, rather than at a single moment. Although the terminology is 51% attack, any percentage above 50% suffices for this attack [1]. In fact, such an attack can be attempted with a smaller percentage of the hash rate, but the probability of success is reduced as other honest miners control the generation of some blocks with their relative hash rate. The 51% threshold is simply the level at which the probability of success approaches certainty. Consortiums with a larger fractional hash rate can deliberately create longer temporary forks, meaning that they can control and invalidate more blocks than smaller consortiums. The only known instance of a consortium reaching this threshold occurred in 2014, when the GHash.io consortium temporarily breached a fractional hash rate of 50%, causing widespread panic among the Bitcoin community [16]. In response, GHash.io established a reduced fractional hash rate of qc = 40%,
(2.16)
and committed to maintaining their fractional hash rate below this level. We explain what the stale rate of the network is and discuss how it relates to the 51% attack [2]. The 51% attack threshold is not static and depends on a key property of the network known as the stale rate. Definition 22 (Stale rate [2]). The stale rate pstale is the ratio of the number of blocks outside the longest blockchain to the total number of blocks in all branches of the blockchain. Remark 8 (Binomial distribution of stale blocks [1]). Since block arrivals follow a Poisson process (Remark 6), block events are both memoryless and independent of each other. Therefore, each block independently results in a stale block with probability pstale . Thus, the number of stale blocks out of any fixed number of blocks is approximately binomially distributed. Importantly, the value of the stale rate of the network directly impacts the effective threshold for a 51% attack. A consortium of miners with a fractional hash rate qc could execute a 51% attack with certain probability if [2] qc >
1 − pstale 2 − pstale
(2.17)
with the right hand side being effective threshold to execute a 51% attack with certain probability. Classically, the 51% attack is not an important security concern as it is infeasible. A study in 2018 estimated a network stale rate of pstale ≈ 0.24% [17], corresponding to approximately zero forks per day on average and meaning that a consortium will execute a 51% attack if qc ⪆ 0.499. However, the risk to Bitcoin’s security would become far more potent if factors arise that significantly increase the stale rate of the network [2]. B.
Quantum mining
Now we describe how quantum mining works. First, we discuss the nature of Grover’s algorithm and its generalization to multiple marked elements and how it could be applied to mining Bitcoin. Then we explore the contrasts between classical and quantum bitcoin mining. Finally, we discuss aggressive versus peaceful quantum mining strategies. 1.
Grover’s algorithm
Now we discuss how Grover’s algorithm and its generalization could be employed to mine Bitcoin. We begin by defining what an algorithm is. Then, we explain the problem that Grover’s algorithm solves, namely, the probabilistic unstructured search problem, and then describe the algorithm. Next, we show how the problem of finding a proof-ofwork reduces to an instance of this problem, allowing the use of Grover’s algorithm for mining Bitcoin. Finally, we discuss the feasibility of employing Grover’s algorithm to mine Bitcoin. We first define what an algorithm is both in the classical and quantum settings. An algorithm is the means by which a computer solves a computational problem and comprises three parts: an input, an output, and a procedure
15 that transforms the input into the output [18]. A procedure is a finite set of formally defined instructions interpretable by a computer. A quantum algorithm is an algorithm whose procedure uses quantum logic. We now turn to a specific computational problem known as probabilistic unstructured search. This problem formalizes the task of finding a “marked” item in a large unsorted dataset for which no underlying structure can be exploited. Since we ultimately wish to relate this problem to mining Bitcoin, we assume that the dataset has size 232 [1, 19]. The condition that identifies a marked item is defined using a function that returns 1 for a single input and 0 otherwise. We formally define the 32-bit Boolean oracle inspired by seminal work on the exact quantum lower bound for Grover’s problem [20]. Definition 23 (32-bit Boolean oracle). A 32-bit Boolean oracle is ( 1 32 f : {0, 1} → {0, 1} : x 7→ 0
if x ∈ M else
(2.18)
for some subset {0, 1}32 ⊇ M := {x0 : f (x0 ) = 1}
(2.19)
being the subset of marked inputs, i.e., all x0 that map to 1 under the action of f (2.18). Remark 9. As we undertake a search for multiple marked elements (2.19), Grover’s algorithm, which technically is designed for finding the only marked element, is not the appropriate name for the generalization of Grover’s algorithm to multiple marked elements. Building on Grover’s and Shor’s algorithm, Brassard, Høyer, Mosca and Tapp presented an algorithm [21] for a quantum search for multiple marked elements. In both cases, the budget, i.e., the number of iterations in the search loop, is unbounded, whereas we explicitly treat the finite-budget case as the quantum miners have limited time to execute the search. We refer to our variant of quantum search as a finite-budget quantum search (FQS). Problem 4. [Probabilistic unstructured search problem [21]] Given probability p and a 32-bit Boolean oracle f (2.18), and a promise of an unstructured search (each input is equally likely to yield 1 at the output), determine, with probability p, an input x0 ∈ M that is mapped to 1 by f . Problem 4 can be solved by the brute-force search algorithm, which is guaranteed to succeed within 232 calls to the Boolean oracle [21]. We now explain our FQS algorithm, which solves Problem 4 with no more than k jπp 232 /|M | (2.20) 4 queries to a quantum-phase oracle [22]. We define the 32-qubit quantum-phase oracle. We consider a Hilbert space H := H232 ,
(2.21)
where the subscript denotes the dimension of the space, equipped with an orthonormal computational basis {|x⟩ : x ∈ {0, 1}32 }. We denote uni(H ) and her(H ) as the set of unitary and hermitian operators on H , respectively. Definition 24 (32-qubit quantum-phase oracle [22]). Given a 32-bit Boolean oracle f , the corresponding 32-qubit quantum-phase oracle is X X uni (H ) ∋ Uf : H → H : αx |x⟩ 7→ αx (−1)f (x) |x⟩ . (2.22) x
x
The phase flip introduced by the quantum-phase oracle “marks” the solution by flipping the sign of the probability amplitude associated with the corresponding basis state [22]. The FQS algorithm exploits this marking by iteratively amplifying the probability amplitude of the basis states corresponding to solutions. This amplitude amplification is achieved by iteratively applying a quantum operator known as a Grover iterate. We first define the quantum operators that serve as the components of the Grover iterate and then define the Grover iterate itself. Definition 25 (32-qubit Hadamard gate [22]). The 32-qubit Hadamard gate H⊗32 is the tensor product of 32 singlequbit Hadamard gates 1 1 1 √ H= ∈ uni (H2 ) ∩ her (H) . (2.23) 2 1 −1
16 Definition 26 (32-qubit Householder reflection [23]). The 32-qubit Householder reflection is uni(H ) ∩ her(H ) ∋ U0 := 2 (|0⟩ ⟨0|)
⊗32
− 1,
(2.24)
which maps |0⟩
⊗32
⊗32
7→ |0⟩
, |x⟩ 7→ − |x⟩ ∀x ̸= 0.
(2.25)
Definition 27 (32-qubit Grover iterate [22]). The 32-qubit Grover iterate is uni(H ) ∋ G := H⊗32 U0 H⊗32 Uf .
(2.26)
We now outline the FQS algorithm (Remark 9) for the 32-qubit multi-solution case, utilizing the Grover iterate. Definition 28 (Quantum measurement). A quantum measurement is the destructive mapping mea : H → {0, 1}32 :
32 2X −1
⟨x|ψ⟩ |x⟩ 7→ x
(2.27)
x=0
|
{z
|ψ⟩
} 2
in the computational basis, where each label x ∈ {0, 1}32 is an outcome with probability |⟨x|ψ⟩| . Remark 10 (Measurement timing). We treat measurement as instantaneous. We now introduce the 32-qubit version of the FQS algorithm. Henceforth, we use the notation [x] := {1, . . . , x}, [x]0 := {0} ∪ [x]
(2.28)
being all natural numbers from 1 (or 0, respectively) up to x inclusive. Now we present Alg. 1, which formalizes the mapping that yields ⊗32 x ← mea Gk H⊗32 |0⟩ (2.29) with x being a marked input x0 (2.19) to the Boolean oracle (2.18) with probability that depends on the number of Grover iterations k performed before the quantum measurement (Def. 28). Algorithm 1 FQS algorithm (32-qubit) [19, 21, 22] Input: G ∈ uni(H ) k ∈ [51471]0 Output: x ∈ {0, 1}32 1: Procedure 2: H ∋ |ψ⟩ ← Gk H⊗32 |0⟩⊗32 3: return x ← mea(|ψ⟩) 4: end Procedure
▷ 32-qubit Grover iterate ▷ The number of Grover iterations ▷ Measured bitstring ▷ Apply Grover operator k times on superposition of basis states ▷ Measure the resultant state and return the basis state label with probability | ⟨x|ψ⟩ |2
Definition 29. The optimal number kopt of Grover iterations for the 32-qubit FQS algorithm is the least number of Grover iterations that maximizes the success probability; i.e., the maximum probability for which the returned label is correctly the inverse of 1 for the marked element. The FQS algorithm returns a valid solution with a probability h p i |M |/232 p(k, |M |) := sin2 2(k + 1/2) arcsin ,
(2.30)
that scales with the number of Grover iterations k performed before measurement and the number of marked elements |M | [21, 24]. In the context of mining Bitcoin, Eq. (2.30) is rewritten in terms of the network difficulty D by substituting 32
D = 2 /|M |,
(2.31)
17 giving h p i 1/D , p(k) = p(k, D) := sin2 2(k + 1/2) arcsin
(2.32)
where we adopt the shorthand notation p(k), as D remains fixed for the values considered in this work. Similarly, the optimal number of Grover iterations to perform, jπ√ k kopt (D) := D , (2.33) 4 is also a function of the network difficulty D in the context of Bitcoin. Since each Grover iteration queries the quantum-phase oracle (Def. 24) exactly once, this is also the optimal number of queries to perform. However, for simplicity, we refer to the evaluated value kopt (D) simply as kopt and specify the value of D when necessary. Remark 11 (Zero Grover iterations). The optimal number of Grover iterations is zero if s π2 π 232 32 9 |M | > × 2 ≈ 2.65 × 10 ⇐= < 1. 16 4 |M |
(2.34)
The case in which zero Grover iterations are performed is equivalent to selecting a 32-bit string uniformly at random. Remark 12 (Maximum number of Grover iterations). As the quantum-phase oracle encodes only the 32-bit nonce N , for D > 232 , the success probability p(k) (2.32) is maximized after performing jπ√ k 32 232 = 51471 kopt := (2.35) 4 Grover iterations. In contrast, kopt (2.33) only applies for D ≤ 232 or in the setting where the quantum-phase oracle encodes the entire block header. Now we present essential considerations for implementing the FQS algorithm in a realistic setting. The FQS algorithm offers a quadratic speedup in solving Problem 4, requiring only q 232/|M | (2.36) O queries to the quantum-phase oracle Uf compared to the 32 O 2 /|M |
(2.37)
oracle queries required by classical methods [22]. In this respect, the standard analyses of quantum search algorithms are often focused on minimizing the number of quantum oracle queries, treating it as a black box without consideration of the complexity of the quantum oracle itself. If the complexities of all operations are considered, then the overall complexity of the FQS algorithm depends on the number of oracle queries, the cost of implementing an oracle query, and the computational overhead of all non-query operations such as state preparation, measurement, and error correction. Furthermore, if the construction of a quantum oracle is considered in the overall speedup offered by the FQS algorithm, then an efficient and reversible quantum circuit implementing the quantum oracle must be constructed, which can be hard depending on the problem being solved. Therefore, while the FQS algorithm offers a quadratic speedup in the number of oracle calls, the overall advantage could be diminished if the overhead incurred by querying the oracle or non-query operations is too large. 2.
Applying the FQS algorithm to Bitcoin mining
Now we discuss how the FQS algorithm can be applied to mining Bitcoin. We begin by demonstrating the theoretical possibility of utilizing the FQS algorithm to mine Bitcoin by showing that the problem of finding a proof of work reduces to the probabilistic unstructured search problem. Then, we discuss the key differences between quantum and classical Bitcoin mining. Finally, we discuss a particular competition that arises between miners in the quantum setting. We prove that the FQS algorithm could theoretically be applied to the Bitcoin mining problem. We begin by establishing that Problem 3 reduces to Problem 4.
18
FIG. 6. A visualization of the reduction from the bounded PoW problem to probabilistic unstructured search. A square (□) represents an input or output of the respective problem, while a red square (□) represents a task that must be completed during the reduction step. A black arrow indicates the mapping between components in the reduction. The blue arrow represents the mapping between the input to the transformed output for the bounded PoW problem. The dashed line indicates an intermediate step. For the bounded PoW problem, N represents the 32-bit nonce and τ̃ is the 256-bit difficulty target. The Boolean oracle f takes N as input and is constructed for a particular instance of the bounded PoW problem with success probability p. Finally, x0 represents a nonce such that the resultant block header is a proof-of-work.
Lemma 1 (Reduction to probabilistic unstructured search ). The bounded PoW problem can be reduced to the probabilistic unstructured search problem. To prove this reduction, we first construct a Boolean oracle that encodes the PoW condition for a specific instance of the bounded PoW problem. Our Boolean oracle is used as input into Problem 4. Thus, solving this instance of Problem 4 yields a solution to an instance of Problem 3. Proof. Let f be the 32-bit Boolean oracle ( 32
f : {0, 1}
→ {0, 1} : N 7→
1 SHA-2562 (V ∥ P ∥ R ∥ t ∥ τ ∥ N ) < τ̃ 0 else.
(2.38)
The constant bitstrings V, P, R, t, and τ defining an instance of the bounded PoW problem determine the construction of f . Let M (2.19) be the set of nonces that satisfy the PoW condition. As the outputs of SHA-256 are uniformly distributed (Definition 2), the probability that at least one nonce in the 32-bit space satisfies the PoW condition (i.e., the probability that M ̸= ∅) is 232
p = 1 − (1 − τ̃/2256 )
.
(2.39)
By Remark 2, f is computable in polynomial time. Thus, solving the bounded PoW problem reduces to solving an instance of the probabilistic unstructured search problem with a 32-bit Boolean oracle f and probability p. Any algorithm that solves the probabilistic unstructured search problem can therefore be used to solve the bounded PoW problem using the constructed Boolean oracle f .
19 Remark 13 (Assuming at least one solution). For typical values of the network difficulty function D(τ̃ ), the probability that at least one valid nonce exists within a 32-bit space is small. If no valid nonce exists (|M | = 0), the FQS algorithm cannot yield a valid proof-of-work with any number of Grover iterations (2.32). In this case, a quantum miner would opt out of the quantum search entirely. However, we employ the procedure for the case that a valid nonce exists to study the advantage offered by the FQS algorithm when a valid nonce is present in the 32-bit search space. If an efficient and reversible quantum circuit capable of computing the SHA-256 hash function existed, then by building on Lemma 1 and Remark 2, an efficient quantum circuit implementing the quantum oracle for mining Bitcoin could be constructed [4, 24]. Now we discuss the key differences between mining Bitcoin in the classical and quantum settings. Applying the FQS algorithm to Bitcoin mining introduces new techniques that are not present in classical mining. Classically, miners check block headers sequentially and immediately determine whether a given header satisfies the PoW condition (Def. 15). In contrast, quantum miners must commit a specific amount of quantum information processing time before making a measurement [2, 3]. As a result, quantum miners cannot continually verify block headers; instead, they only learn of the outcome of the search after measurement. This fundamental difference leads to a unique competition between the miners that is only present in the quantum setting. Now we discuss a unique behaviour among miners that only arises when employing quantum mining techniques. Quantum miners must commit time to quantum information processing, aiming to perform as many Grover iterations as they can, or as close to the optimal number of Grover iterations as possible, to maximize their success probability. However, the quantum miners want to measure before each other to be the first to claim the mining reward [3]. If only one quantum miner is in the network, they would focus on performing kopt Grover iterations before measuring [25]. However, if multiple quantum miners in the network are present, determining when to measure is much more complicated. For example, a quantum adversary could perform a quantum measurement (Def. 28) after performing fewer than kopt Grover iterations, thereby reducing their success probability but gaining a temporal advantage and a higher chance of being the first to broadcast a valid block to the network [2, 3]. Therefore, quantum miners must strike a balance between maximizing their success probability and measuring before their adversaries.
3.
Aggressive and peaceful quantum mining
Now we explore the difference between aggressive and peaceful quantum mining following Sattath’s explanation [2]. We begin by discussing the choice that quantum miners are faced with when they learn of a new block. Then we explain what the peaceful quantum mining strategy is. Finally, we explain the aggressive mining strategy and its consequences on the Bitcoin network. We now turn to the decision that quantum miners must make when they learn of a newly-mined block while performing a Grover search. Upon receiving a broadcast of a new block, quantum miners face a crucial decision: either discard their search and begin a new one for the next block, or halt the search and immediately measure the resulting quantum state in hopes of producing a valid block. The first option is known as the peaceful quantum mining strategy and mirrors the classical approach of abandoning a block once a new block is found. The second is called the aggressive quantum mining strategy, which is an opportunistic approach unique to quantum miners that minimizes the waste of computational resources already invested in solving Problem 2. We discuss the peaceful quantum mining strategy (PQMS). In the PQMS, the quantum miners discard their current Grover search entirely and start anew upon receiving a broadcast of a newly-mined block. This behaviour mirrors classical Bitcoin miners, who immediately begin mining on top of newly-mined blocks as soon as they receive a broadcast of them. By discarding their Grover search, quantum miners employing the PQMS avoid intentionally forking the blockchain. However, unlike in the classical setting, discarding a Grover search wastes significant computational resources already invested in executing the FQS algorithm. Next, we turn to the aggressive quantum mining strategy (AQMS), as proposed by Sattath [2]. In his strategy, quantum miners halt their search and measure upon receiving a broadcast of a newly-mined block, attempting to maximize their chances of temporarily forking the blockchain. By employing Sattath’s AQMS, quantum miners avoid wasting the computational effort already invested in executing the FQS algorithm. If the quantum measurement (Def. 28) is successful, the quantum miner will attempt to temporarily fork the blockchain. If all quantum miners in the network employ Sattath’s AQMS, the quantum miners will halt and measure their quantum states nearly simultaneously when they receive a broadcast of a newly-mined block. As a result, the times at which quantum miners perform measurements and the times at which blocks are found become highly correlated. This correlation, which only occurs in the quantum setting due to Sattath’s AQMS, leads to an increased stale rate pstale in Def. 22 compared to the classical setting.
20 Remark 14. Sattath’s AQMS increases the Bitcoin network’s stale rate pstale . As a consequence, the effective threshold for a 51% attack (2.17) decreases, meaning that a consortium with fractional hash rate qc less than one half would be able to execute a 51% attack. Remark 15 (Regulation of peaceful mining). As a network regulation that all quantum miners be peaceful is not enforceable, aggressive mining should be the default assumption.
FIG. 7. Blockchain forking due to Sattath’s AQMS. A circle (⃝) represents a node in the Bitcoin network, with a dashed circle representing a quantum miner employing Sattath’s AQMS. The red circle (⃝) represents a classical mining node that has just mined a new block. Each vertex contains either a star (⋆), which represents the blockchain state before the new block was discovered, or a triangle (△), square (□), or diamond (♢), representing the new branches of the blockchain during a temporary fork. An arrow within an edge indicates the broadcast of a new block to a peer. An edge without an arrow represents a peer-to-peer connection where no new block is being broadcast. This figure represents a temporary fork because all of the nodes do not have the same symbol.
C.
Quantum races
We explain the quantum races model and its underlying game-theoretic foundation. We begin with some preliminary game-theoretic concepts that are essential to understanding the quantum races model. Next, we describe some methods used for computing a Nash equilibrium and discuss the computational complexity of this problem. Finally, we introduce the quantum races model and focus on the case of two players. 1.
Preliminaries on game theory
We discuss essential game theory concepts for understanding the quantum races model. We begin with a top-down explanation of what a strategic game is, noting the essential assumptions about the participants. Then, we explain what strategies are in strategic games. Next, we discuss what payoff functions are and how they quantify the players’ preferences over the outcomes of the game. Finally, we explain what a Nash equilibrium is and discuss how its existence is guaranteed. We begin with a top-down explanation of what a strategic game is, introducing each of its essential components. A strategic game is a mathematical model of interactive decision making, where each participant chooses a plan of action simultaneously and once and for all [26]. Formally, a strategic game is defined as follows.
21 Definition 30 (Strategic game [27]). A strategic game is a 3-tuple comprising a set of players ℘ that is finite: |℘| =: n℘ , a set of strategies for each player Si , and a set of payoff functions for each player that give a payoff value for each combination of the players’ chosen strategies. Although several different types of games exist [27, 28], we focus exclusively on strategic games in this work. In the standard framework of strategic games, players are assumed to be both rational and intelligent. Definition 31 (Rational player [27]). A rational player chooses their action to maximize their payoff consistent with their beliefs of what is going on in the game. Definition 32 (Intelligent player [27]). An intelligent player possesses complete knowledge about a game, including the actions available to themselves and their opponents, the possible outcomes of the game, and the preferences of all players. These assumptions, along with the structure of the game itself, are assumed to be common knowledge [27]. Now we explain the notion of strategies in the context of strategic games. Each player i ∈ ℘ is associated with a set of actions Si permitted by the rules of the game. If this set of actions is finite, then the game is called finite [28]. A strategy is an action chosen from Si deterministically (pure), or a probability distribution over Si (mixed). Definition 33 (Pure strategy [26]). A pure strategy is a single action si ∈ Si that a player i ∈ ℘ selects deterministically. Definition 34 (Mixed strategy [28]). A mixed strategy σi for player i ∈ ℘ is a probability distribution over Si . Definition 35 (Support of mixed strategy [28]). The support of a mixed strategy supp(σi ) := {si ∈ Si : σi (si ) > 0}
(2.40)
is the set of pure strategies that are played with positive probability by a mixed strategy σi . The set of mixed strategies for player i is [28] ( Σi :=
)
σi : Si → [0, 1] :
X
σi (si ) = 1 .
(2.41)
si ∈Si
A pure strategy can also be considered a mixed strategy with a degenerate distribution that selects a single element of Si with probability 1 [27]. Definition 36 (Pure strategy profile [27]). A pure strategy profile is an n℘ -tuple s∗ = (s1 , s2 , . . . , sn℘ ),
(2.42)
where each si ∈ Si is the pure strategy chosen by player i ∈ ℘. The set of all pure strategy profiles is denoted S ∗ . A mixed strategy profile σ ∗ is defined analogously, where each σi is the mixed strategy chosen by player i ∈ ℘ [27]. Remark 16 (Concise strategy profile notation [27]). A pure strategy profile is s∗ := (si , s∗−i ),
(2.43)
where s∗−i is the (n℘ − 1)-tuple denoting the strategies chosen by all players except player i. Similarly, a mixed strategy ∗ profile is denoted as σ ∗ = (σi , σ−i ). We note that Sattath’s AQMS [2] does not correspond to a strategy in the formal game-theoretic sense, and only specifies how a quantum miner will react to receiving a broadcast of a newly-mined block. Now we discuss how a player’s preferences are quantified in payoff. In a strategic game (Def. 30), each player i ∈ ℘ is associated with a payoff function that assigns a real number to every possible strategy chosen by all players [27]. The output of the payoff function is called the payoff, and represents the player’s preference over the game’s outcome that has been determined by the strategies played by all players.
22 Definition 37 (Payoff function [28]). A payoff function ui : S ∗ → R represents player i’s preference on the outcome of a game led to by the strategies chosen in the pure strategy profile s∗ ∈ S ∗ . We adopt a definition of a payoff matrix based on standard textbooks on game theory [28, 29]. Definition 38 (Payoff matrix). For two-player finite strategic games with S1,2 the sets of actions available to the players, the payoff functions ui : S1 × S2 → R : (s1 , s2 ) 7→ ui (s1 , s2 )
(2.44)
A ∈ R|S1 |×|S2 | , B ∈ R|S2 |×|S1 | ,
(2.45)
(s1 , s2 ) 7→ u1 (s1 , s2 ), (s1 , s2 ) 7→ u2 (s1 , s2 ),
(2.46)
determine a pair of payoff matrices,
with payoff-matrix entries
respectively. Remark 17. For two player games, we adopt the notation u := u1 v := u2
(2.47)
As1 s2 = u(s1 , s2 )
(2.48)
as the payoff functions for both players. Thus, the payoff matrix entries are
and similarly for B. Remark 18 (Expected payoff for mixed strategies [28]). For a mixed strategy profile σ ∗ , the expected payoff is given by X Y U (σ ∗ ) := Eσ∗ [u(σ ∗ )] = u(s∗ ) σi (si ). (2.49) s∗ ∈S ∗
i∈℘
Note that payoff is an ordinal construct. The value of payoff itself has no meaning and is used to order the desirability of alternatives [27]. Importantly, the payoff function is used to define a best-response. Definition 39 (Best response [27]). The strategy σi ∈ Σi is player i’s best response to their opponents’ strategies σ−i ∈ Σ−i if ∗ ∗ ui (σi , σ−i ) ≥ ui (σi′ , σ−i ) ∀σi′ ∈ Σi .
(2.50)
Definition 40 (Strictly dominated strategy [28]). A strategy si ∈ Si of player i ∈ ℘ is strictly dominated if ∃s′i ∈ Si : ui (si , s∗−i ) < ui (s′i , s∗−i )∀s−i ∈ S−i .
(2.51)
A rational player will not play a strictly dominated strategy. In two-player finite strategic games (Def. 30), the payoff functions are represented as payoff matrices [27]. Each player’s payoff matrix lists their payoff for each combination of pure strategies played by both players: rows correspond to their own actions, and columns correspond to the actions of their opponent. Definition 41 (Symmetric game [28]). A game is symmetric if the players share the same pure strategy set Si = Sj ∀i, j ∈ ℘,
(2.52)
σ ∗ = (σ1 , σ2 , . . . , σn℘ ),
(2.53)
and if, for any mixed-strategy profile
23 then, for any permutation π:℘→℘
(2.54)
ui (σ ∗ ) = uπ(i) (π(σ ∗ )),
(2.55)
π(σ ∗ ) := σπ(1) , σπ(2) , . . . , σπ(n℘ ) .
(2.56)
of the players i ∈ ℘,
where
Remark 19 (Payoff for symmetric two-player strategic games [28]). In a two-player symmetric strategic game (Def. 30), each player’s payoff matrix is the transpose of the other’s. Here we describe what a Nash equilibrium is. A Nash equilibrium is a strategy profile where each player plays a best response to the strategies of all other players, and no player has an incentive to unilaterally deviate [27]. Definition 42 (Nash equilibrium [27]). A strategy profile σ ∗ = (σ1 , σ2 , . . . , σn ) is a Nash equilibrium if ∗ ∗ ui (σi , σ−i ) ≥ ui (σi′ , σ−i ) ∀σi′ ∈ Σi , ∀i ∈ ℘.
(2.57)
As pure strategies are a degenerate case of mixed strategies, this definition of the Nash equilibrium applies to both pure and mixed strategies. In non-cooperative strategic games where all players are rational and intelligent, the Nash equilibrium is self-enforcing because all players know that deviating from their equilibrium strategy will result in a lower expected payoff [27]. Importantly, the existence of a mixed-strategy Nash equilibrium is guaranteed by Nash’s theorem. Theorem 2 (Nash’s existence theorem [27, 30]). Any n℘ -player finite strategic game has at least one mixed-strategy Nash equilibrium. Theorem 3 (Nash’s existence theorem for symmetric games [30]). Any finite symmetric game has at least one symmetric Nash equilibrium. Whereas a game can have multiple Nash equilibria, the existence of additional equilibria is not guaranteed. If multiple Nash equilibria exist, some can result in a better expected payoff for the players than others. 2.
Computing a Nash equilibrium
We discuss the problem of computing a Nash equilibrium in finite strategic games. We begin by giving an overview of different methods used to compute a Nash equilibrium. Then, we focus on the Lemke-Howson algorithm, a standard method for computing an exact Nash equilibrium in two-player games. Finally, we discuss the computational complexity of computing a Nash equilibrium. We begin by giving an overview of methods used for computing a Nash equilibrium. The method used to find a Nash equilibrium depends on several properties of the game, including, but not limited to, the number of players, whether the game is symmetric, whether players make decisions sequentially or in turns, and whether the goal is to find an exact or ϵ-approximate Nash equilibrium [29]. As a result, a wide range of methods have been developed for computing a Nash equilibrium, including analytical approaches, graphical techniques [31], and algorithmic approaches based on linear programming [8]. No single technique exists that is universally applicable to all types and properties of games. Now we discuss the Lemke-Howson algorithm. The Lemke-Howson algorithm is a well-established and standard method for finding an exact Nash equilibrium in two-player, finite, strategic games [8, 29]. As input, the LemkeHowson algorithm requires the payoff matrices of both players, along with an integer specifying the initial direction of the search [8]. The Lemke-Howson algorithm outputs a mixed-strategy profile corresponding to an exact Nash equilibrium (Def. 42). This algorithm works by traversing through the edges of a pair of polytopes representing the strategy sets of both players, using a method called complementary pivoting, until a pair of vertices corresponding to a Nash equilibrium is found [8, 29]. Note that the Lemke-Howson algorithm finds only a single Nash equilibrium, though additional Nash equilibria can be found by enumerating through different initial directions to search. All Nash equilibria found by Lemke-Howson must lie within the polytopes representing the strategy sets of both players. We discuss the complexity of computing a Nash equilibrium. The complexity of computing a Nash equilibrium is essential for understanding the limitations of the Lemke-Howson algorithm. The problem of computing a Nash
24 equilibrium for mixed-strategy games, denoted Nash, is heavily studied in computational complexity theory [32]. Formally, Nash is a function problem, which means the task is to evaluate a function that returns a Nash equilibrium for each game [33]. Since a solution to Nash is always guaranteed to exist by Nash’s theorem (Theorem 2), Nash belongs to the complexity class called Total Function Nondeterministic Polynomial (TFNP) [29]. More specifically, in 2006, it was shown that Nash is complete for the Polynomial Parity Arguments on Directed Graphs (PPAD) complexity class, which is a subclass of TFNP [32]. Although being PPAD-complete does not prove that Nash is intractable, it does provide strong evidence of intractability [34]. This is because any efficient algorithm that solves a PPAD-complete problem like Nash would yield efficient algorithms for all PPAD-complete problems, including computing Brouwer fixed points, which has been resilient to efficient solutions for decades [35]. Thus, although the Lemke-Howson algorithm computes an exact Nash equilibrium, it has worst-case exponential runtime, reflecting that Nash is PPAD-complete [32]. Additionally, many variants of Nash are known to be NP-complete, such as computing a second Nash equilibrium given a first, or computing a Nash equilibrium that uses particular strategies. 3.
Two-player quantum races
We follow the 2019 Lee-Ray-Santha approach (LRS19) [3] and describe the quantum races model in the case where there are two players, Alice and Bob. We begin with a description of the quantum races model, noting its purpose and its components. Then, we discuss the pure strategies for the players and the associated success probabilities. Next, we specialize to the case where there are only two players, Alice and Bob, and discuss their payoff and the structure of their payoff matrices. Finally, we explain how the quantum races model can be applied to Bitcoin. We explain the quantum races model with a model comprising descriptions of the players and their resources, the protocols they follow, the actions they are allowed, and the payoffs associated with those actions. We formally define a quantum race based on the description by LRS19 [3]. Definition 43 (Quantum race). A quantum race is a competition between two or more players, each equipped with a quantum computer, who are racing to be the first to solve the same computational problem. The quantum races model is introduced as a means to study such competitions using a game-theoretic approach. The purpose of the quantum races model is to determine the optimal strategies for the players. Before beginning a quantum race, each player i ∈ ℘ chooses the times at which they will measure their respective quantum states from the set Si := {1, 2, . . . , K},
(2.58)
which is the set of pure strategies available to player i, and K is the maximum allowed measurement time. The quantum races model assumes that each player performs exactly one quantum measurement for each quantum race. Remark 20 (Weak players). The assumption that each player performs exactly one quantum measurement per quantum race makes the players “weak”, as if both players’ quantum measurements do not yield a solution, then there is no winner. In contrast, a “strong” player would maximize their resources by performing multiple quantum measurements until either quantum miner succeeds. The set of pure strategies for each player is associated with a success probability that increases with the measurement time. For each time t′ ∈ Si , each player has a quantum algorithm that they can run for time t′ with an associated success probability p(t′ ). It is assumed that these probabilities form an increasing sequence 0 < p(1) < p(2) < · · · < p(K) ≤ 1.
(2.59)
Whereas LRS19 refer to these actions as “times”, we clarify that they can also represent the number of computational steps. The quantum races model applies to any quantum algorithm whose success probability can be characterized by an increasing sequence of probabilities at discrete points in its execution. Each quantum race is fully specified by an increasing sequence of probabilities (2.59) for each player, as well as their respective payoff functions, which we describe next. Remark 21 (Two players). LRS19 first considered a setting with two players, although they did not justify this choice. Presumably, the two-player case was analyzed first because the quantum race is fully represented by a pair of payoff matrices. A quantum race involving three or more players requires a higher-dimensional tensor, which makes the analysis much more difficult. We now follow LRS19 and specialize to the symmetric two-player quantum races model (Remark 21), which we refer to as the S2QR model for short, with Alice and Bob as the players.
25 Definition 44 (S2QR). A symmetric two-player quantum race is a quantum race (Def. 43) consisting of two players that is symmetric (Def. 41). In an S2QR, both players possess identical quantum and classical resources [3]. Thus, an S2QR is fully specified by an increasing sequence of probabilities associated with both players (2.59), and a pair of K × K payoff matrices, A and B. The player who succeeds first in solving the computational problem receives a payoff of 1, whereas the other player receives a payoff of 0. In the case of a tie, the payoff is split evenly between them. If the payoff is not split in the case of a tie, then the S2QR is called stingy. We describe the structure of Alice’s and Bob’s payoff matrices in a symmetric two-player quantum race. The (a, b) element of Alice’s payoff matrix A is her payoff in the case where Alice measures after a units of time or computational steps and Bob measures after b units of time or computational steps. The payoff is determined by the conditional probabilities of each player’s success and failure, depending on when each player measures relative to the other. If Alice measures before Bob (a < b), her payoff corresponds to the probability p(a) that she succeeds whereas Bob has not yet measured. In contrast, if Bob measures first (a > b), Alice’s payoff is p(a)(1 − p(b)),
(2.60)
the joint probability that Alice’s measurement is successful and Bob’s fails. If Alice and Bob measure at the same time (a = b), the term 1 p(a)2 2
(2.61)
is added to Alice’s payoff, representing the scenario where both Alice’s and Bob’s quantum measurements yield a valid proof-of-work and the reward is split. Alice’s payoff matrix is thus conveniently expressed as a<b p(a), A : [kopt ] × [kopt ] → [0, 1] : (a, b) 7→ p(a)(1 − p(b)) + 12 p(a)2 , a = b p(a)(1 − p(b)), a > b,
(2.62)
with (a, b) being (s1 , s2 ) and the right hand side being u1 (s1 , s2 ) (Def. 38). As the game is symmetric, Bob’s payoff matrix is B = A⊺ . An extension to the S2QR model, studying the case where each player performs two quantum measurements between successive blocks, is presented in Maharshi Ray’s PhD thesis [36]. Now we discuss how the S2QR model is applied to the context of mining Bitcoin. In this setting, Alice and Bob each represents a quantum miner, who are each equipped with identical quantum computers, and compete to solve Problem 3 before each other. The set of pure strategies available to each quantum miner is the set of Grover iterations that can be performed before measurement Si = {1, 2, . . . , kopt },
(2.63)
where kopt (2.33) is the optimal number of Grover iterations to perform for a given network difficulty D, and i is the index representing each player. In this quantum race, Alice and Bob each independently execute Alg. 1 with their own choice of k ∈ Si Grover iterations, obtaining a nonce x as a result of the quantum measurement (2.27). Alice or Bob win the quantum race if their own x satisfies the PoW condition (Def. 15). As both Alice and Bob have identical resources in this setting, the success probability (2.32) for each pure strategy si ∈ Si is the probability that the FQS algorithm returns a nonce constituting a valid proof-of-work given a number of Grover iterations and network difficulty D. These probabilities form an increasing sequence p(1) < p(2) < · · · < p(kopt ) ≤ 1,
(2.64)
reflecting the quadratically increasing likelihood of success as the number of Grover iterations increases. The quantum miner who first finds a valid block header receives a payoff of 1, representing the mining reward, whereas all other quantum miners receive a payoff of 0. The S2QR model for Bitcoin is based on the assumption that the quantum miners employ the PQMS. LRS19 model Bitcoin mining as a non-stingy quantum race, where the payoff is split in the case of a tie (2.62). However, the bulk of their analysis considers the stingy variant, which is more tractable. In contrast, our work permits the use of Sattath’s AQMS, so that in the case of a tie, Alice’s block wins with probability γS (Def. 19).
26 III.
APPROACH
Now we discuss our approach for determining the impact that quantum miners would have on Bitcoin’s security. We begin by discussing our model, where we consider two quantum miners in the Bitcoin network who compete against each other while mining. Next, we explain the mathematics for our model, paying special attention to the strategies available to the quantum miners and the construction of their payoff matrices. Finally, we describe the methods used to compute optimal quantum mining strategies and simulate their impact on Bitcoin’s security by estimating the resulting stale rate of the Bitcoin network. A.
Model
We present our model as a concept with the mathematics relegated to the next subsection. We begin by laying the foundations of our model, specifying our extensions to the S2QR model for Bitcoin, as well as the relevant parameters of the Bitcoin network. Then, we discuss the agents in our model, Alice and Bob. Finally, we build up the adversarial model we use to study how the agents affect Bitcoin’s security. 1.
Model foundations
We first lay the necessary foundations of our model. We begin by giving an overview of our extensions to the S2QR model for Bitcoin and explain the connection between our model and Problem 1. Then, we list the key Bitcoin network parameters that parameterize our model. Finally, we explain the regimes for the network difficulty our model considers. Following the LRS19 approach to restrict to two quantum miners (Remark 21), we extend the S2QR model for Bitcoin in two ways. First, we consider a setting where the quantum miners perform multiple quantum measurements (Def. 28) between successive blocks, rather than perform a single quantum measurement. This choice is motivated by the idea that in a practical setting, quantum miners would likely perform multiple quantum measurements until one of the quantum miners wins (Remark 20). Second, we consider quantum miners who employ Sattath’s AQMS [2], which is motivated by the fact that a regulation that all quantum miners in the network must be peaceful is not enforceable (Remark 15). These extensions to the S2QR model for Bitcoin capture quantum mining behaviour that closer reflects how quantum mining would be performed in reality. Our goal is to determine the optimal strategies for the quantum miners in this new setting, and study how these optimal strategies affect Bitcoin’s security against a 51% attack. We discuss the key parameters of the Bitcoin network that we employ in our model. Our model accepts the network difficulty D, which influences the success probability for the FQS algorithm (2.32) and the optimal number of Grover iterations to perform kopt (2.33). Furthermore, we observe how the stale rate pstale changes as a result of the optimal strategies for the quantum miners. Finally, we assume that the hash rate q of the Bitcoin network is constant for a given network difficulty D, so that the block arrival times are modelled as a homogeneous Poisson process. We consider three regimes for the network difficulty in our model. Recognising that D0 = 232 ,
(3.1)
for which Problem 3 has at least one expected solution, we now define the difficulty regimes for the network. Definition 45 (Network difficulty regimes). The three difficulty regimes for the Bitcoin network are low if D ≤ D0 , high if D > D0 , and ideal if D > D0 with a perfect quantum-phase oracle (Def. 24) encoding the entire block header. In the ideal regime, the quantum-phase oracle is replaced with a 640-qubit analogue that encodes all the necessary logic required for block validation including Merkle root computation, transaction reordering, extraNonce, timestamp verification, and difficulty target updates. By studying this ideal regime, we can model an upper bound on the capabilities of the quantum miners and the theoretical limits of quantum Bitcoin mining. 2.
Alice and Bob
Now we discuss Alice and Bob, the quantum miners in our model. We begin by discussing the roles Alice and Bob play in our model, highlighting their goals. Then, we go over the resources available to Alice and Bob. Finally, we lay out and justify some fundamental assumptions about Alice’s and Bob’s behaviour in our model.
27 We conceptually explain the roles of Alice and Bob in our model. Alice and Bob are rational and intelligent quantum miners who are competing in a quantum race [3] with the goal of successfully mining a block before each other. For each quantum race, Alice and Bob execute the FQS algorithm over the space of possible nonces for a block using a quantum-phase oracle (Def. 24) encoding the PoW condition (2.11). After performing the quantum measurement (Def. 28), if the returned nonce satisfies the PoW condition, then that quantum miner wins the quantum race. Alice and Bob operate within an otherwise classical Bitcoin network that is unaware of their quantum capabilities. To maximize their individual rewards, Alice and Bob employ Sattath’s AQMS [2] while competing in this quantum race. Alice and Bob neither cooperate nor communicate with each other. To avoid a situation where the quantum miners repeatedly undermine each other’s chosen strategy si ∈ Si (2.63), Alice and Bob compute and employ the same Nash equilibrium σ ∗ satisfying condition (2.57) for the two-player game representing their quantum race using publicly available information. We refer to the Nash equilibrium σ ∗ for competing quantum miners in a two-player game as an optimal quantum mining strategy. A full mathematical description of Alice’s and Bob’s quantum race is deferred to §III B. We discuss the resources available to Alice and Bob. Alice and Bob are each equipped with an identical quantum computer that is purpose-built for executing the FQS algorithm for mining Bitcoin. For each of Alice’s and Bob’s candidate blocks, they are provided with the corresponding Grover iterate (Def. 27), so that the cost of operating the quantum-phase oracle is reduced to queries. For each candidate block, Alice and Bob execute the FQS algorithm exactly c∈N
(3.2)
times each in search of a valid block header. The cumulative number of Grover iterations that each quantum miner could perform over all measurements is bounded above by the Grover iteration budget 32 κ := min kopt , kopt , (3.3) 32 where kopt (2.33) is the optimal number of Grover iterations to perform for network difficulty D, and kopt (2.35) is the optimal number of Grover iterations to perform for a 32-qubit quantum-phase oracle (Def. 24). This choice of κ is motivated by the fact that the 32-qubit quantum-phase oracle constrains the number of Grover iterations performed for D > 232 (Remark 12). Furthermore, κ is selected such that the problem of how Alice and Bob should optimally allocate their resources over c quantum measurements is nontrivial. A resource budget that is too low would concentrate all resources into a single quantum measurement, whereas a resource budget that is too high would 32 into each of their c quantum measurements independently. The propagation parameter allocate kopt
γ ∈ [0, 1]
(3.4)
represents the probability that Alice’s block is included in the longest blockchain in the event of a temporary fork, and 1 − γ represents this same probability for Bob. Finally, we assume that the cost of all non-query operations, such as state preparation, measurement, and constructing the relevant quantum-phase oracle is negligible. We make the following assumption about Alice’s and Bob’s behaviour in our model. Although employing Sattath’s AQMS decreases the effective threshold for a 51% attack (Remark 14), we assume that this does not influence Alice’s and Bob’s actions. Instead, we model Alice and Bob as being only interested in beating the other in the quantum race. A more complete problem would be to model the interaction between the quantum miners and the Bitcoin network using a game-theoretic framework. However, such an analysis would require modelling the full state of the Bitcoin network, which includes the behaviour of all nodes, adjustments in the network difficulty, and the many factors that affect block propagation times. Thus, we model the direct competition between the quantum miners to study their strategic interactions, which serves as a step towards understanding the full problem. Furthermore, as the number of pure strategies for Alice and Bob grows combinatorially with c, the evaluation of Alice’s and Bob’s payoff matrices is computationally expensive. Therefore, we introduce a heuristic to reduce the cardinality of their pure strategy spaces, which we formalize in §III B and outline in §III C. 3.
Adversarial model
We formalize the adversarial model used in our study. We first define what a Bitcoin adversary is, as we use this definition to form the foundation of our adversary model. Then, we specify the condition under which we consider the Bitcoin network to have failed. Finally, we identify the adversaries in our model and explain how they affect Bitcoin’s security. To formalize our adversarial model, we first define what a Bitcoin adversary is in the context of our model. Whereas standard textbooks define an adversary in general as an agent that generates worst-case inputs to maximize the cost
28 of executing an algorithm [37], this definition does not capture how an agent might cause the Bitcoin network to fail on a task it was designed to perform. Thus, we define a Bitcoin adversary as follows. Definition 46 (Bitcoin Adversary ). A Bitcoin adversary is an agent who forces the Bitcoin network to fail on some task. We use this definition of a Bitcoin adversary as the foundation for our adversarial model, clarifying the specific task we consider, what it means for the Bitcoin network to fail on performing that task, and how an agent can force such failure. We identify the task performed on the Bitcoin network relevant to our adversarial model and the conditions for deeming this task to have failed. The specific task that we consider is the prevention of a 51% attack. We consider the Bitcoin network to be vulnerable to a 51% attack if the effective threshold for a 51% attack decreases to 40% (2.16) or below. This threshold corresponds to a stale rate satisfying (2.17) pstale ≥ 1/3,
(3.5)
which addresses the GHash.io incident [16]. We identify the adversaries in our model and assess how they affect Bitcoin’s security. The adversaries in our model are Alice and Bob, the quantum miners. Although Alice and Bob are rational and intelligent quantum miners who are competing in a quantum race (Def. 43), the optimal quantum mining strategies they employ increase the Bitcoin network’s stale rate via Sattath’s AQMS. This is not a deliberate attack by Alice and Bob, but is an emergent effect of their optimal quantum mining strategies. We formalize Alice’s and Bob’s impact on the Bitcoin network with the following proposition. Proposition 4. Given the Grover iteration budget κ (3.3), two rational and intelligent quantum miners in the Bitcoin network employing optimal quantum mining strategies cannot increase pstale to satisfy (3.5) pstale ≥ 1/3
(3.6)
over the duration of a 51% attack. We prove this proposition in §IV. B.
Mathematics
We discuss the mathematics required to describe our model within a game-theoretic framework. We begin by discussing the pure strategies available to Alice and Bob and how these pure strategies label Alice’s and Bob’s payoff matrices. Then, we provide the mathematics required to derive Alice’s and Bob’s payoff matrices in the case where they each perform multiple quantum measurements between successive blocks. Finally, we explain the mathematics required to include the terms related to Sattath’s AQMS into Alice’s and Bob’s payoff matrices. 1.
Pure strategies
We discuss the pure strategies available to the quantum miners in our model. We begin by outlining the set of actions available to the quantum miners for a single quantum measurement. Then, we explain how Alice’s and Bob’s pure strategies are derived from the single quantum measurement case. Next, we show how Alice’s and Bob’s pure strategies label their payoff matrices. We discuss Alice’s and Bob’s pure strategies for a single quantum measurement. Alice and Bob perform c quantum measurements (Def. 28) for each instance of the quantum race they are participating in. For each of these measurements, the set of actions available to Alice and Bob, 32 S0 := kopt , (3.7) comprises all possible numbers of Grover iterations that can be performed before the quantum measurement. Note that this set differs from Eq. (2.63) by including 0, which corresponds to the action of doing nothing, i.e., performing zero Grover iterations. Each action label k ∈ S0 has an associated probability p(k) (2.32), which is the probability that measuring the quantum state after performing k ∈ S0 Grover iterations is successful. These probabilities form an increasing sequence 32 p(0) < p(1) < · · · < p kopt , (3.8)
29 which is a requirement of the quantum algorithms studied by the quantum races model [3]. Now we derive Alice’s and Bob’s pure strategies based on the set of available actions for a single quantum measurement (3.7). Both Alice and Bob perform c quantum measurements for each instance of the quantum race they are competing in. For each quantum race and given the number of quantum measurements c (3.2), the set of pure strategies is c o n X 32 c S0c := k ∈ kopt : 1 · k ≤ κ , 1 · k := ki ,
(3.9)
i=1
which represents all c-tuples of numbers of Grover iterations that could be performed by Alice and Bob across all c quantum measurements, where κ is the cumulative Grover-iteration limitation (3.3). As both Alice and Bob have identical resources, they share the same set of pure strategies S0c . Now we express a special case of the standard stars-and-bars result [38] as a lemma for clarity, noting that this lemma is quite straightforward to prove. Lemma 5 (Cardinality of S0c ). The cardinality of S0c is |S0c | =
κ+c . c
(3.10)
Proof. Our proof proceeds by the following combinatorial argument. For kc+1 := κ −
c X
ki , kc+1 ≥ 0,
(3.11)
i=1
a slack variable, c X
ki ≤ κ
(3.12)
ki = κ.
(3.13)
i=1
is replaced by the equality c+1 X i=1
Each c-tuple k satisfying Eq. (3.12) corresponds to a unique (c + 1)-tuple satisfying Eq. (3.13). The number of such (c + 1)-tuples is κ+c+1−1 κ+c |S0c | = = , (3.14) c+1−1 c which follows from the standard stars-and-bars result [38]. We now explain how we manage the computational cost imposed from the combinatorial growth of |S0c | (3.14). As |S0c | (3.14) determines the dimension of Alice’s and Bob’s payoff matrices, this combinatorial growth renders the evaluation of Alice’s and Bob’s payoff matrices computationally expensive. To address this issue, we introduce a heuristic in §III C that restricts the dimension of Alice’s and Bob’s payoff matrices. The motivation for this heuristic comes from the success probability p(k) (2.32) of the FQS algorithm. Since p(k) grows quadratically with k and is maximized with κ Grover iterations, performing a quantum measurement after executing the FQS algorithm with k ≪ κ Grover iterations produces p(k) ≪ 1. This low success probability suggests that if a quantum miner measures early (k < κ) to gain a temporal advantage, then that quantum miner will still perform close to k ≲ κ Grover iterations. Motivated by this, we restrict our attention to a subset of pure strategies for Alice and Bob such that the dimension is bounded by nq + 1 + c ′ (S0c ) ≤ < |S0c | , (3.15) c which remains combinatorial in c but is substantially smaller for nq ≪ κ. This heuristic significantly lowers the computational cost of evaluating Alice’s and Bob’s payoff matrices when computing optimal quantum mining strategies.
30 Now we explain how Alice’s and Bob’s pure strategies label their payoff matrices. Each pure strategy k = (k1 , k2 , . . . , kc ) ∈ S0c
(3.16)
labels the rows and columns of Alice’s and Bob’s payoff matrices. This labelling implies that Alice’s and Bob’s payoff matrices take the form of a higher-dimensional tensor. As the Lemke-Howson algorithm [8] requires payoff matrices as input, we label the rows and columns of Alice’s and Bob’s payoff matrices in the following way to preserve the matrix structure. Let n o c S0c = k(1) , k(2) , . . . , k|S0 | (3.17) be the elements of S0c (3.9) in lexicographic ordering, with k(j)
(3.18)
being the jth pure strategy (3.16) of S0c in this ordering. We index the rows and columns of Alice’s and Bob’s payoff matrices by α, β ∈ [|S0c |] , α 7→ k(α) , β 7→ k(β)
(3.19)
A(α, β) = A k(α) , k(β)
(3.20)
so that
is the payoff Alice receives when she plays strategy k(α) and Bob plays k(β) . Alice is the row player in her own payoff matrix, and Bob is the column player. Conversely, in Bob’s payoff matrix, he is the row player, and Alice is the column player. As the elements of S0c label the rows and columns of Alice’s and Bob’s payoff matrices, both Alice’s and Bob’s payoff matrices have dimension |S0c | × |S0c | (3.10). 2.
Payoff matrices
We describe the structure of Alice’s and Bob’s payoff matrices for our model. We start by discussing how we express Alice’s and Bob’s total payoff matrices as the sum of payoff matrices corresponding to each of their c quantum measurements. Next, we derive the structure of Alice’s and Bob’s payoff matrices for a single quantum measurement. Then, we extend this logic to derive the structure of Alice’s and Bob’s payoff matrices for c quantum measurements. Now we describe the structure of Alice’s and Bob’s payoff matrices based on their c quantum measurements. We first describe this structure at a high level and then later specify the payoff functions that determine the payoff matrix entries. First consider that Alice and Bob play the strategies (a1 , a2 , . . . , ac ), (b1 , b2 , . . . , bc ), {z } | {z } | a
(3.21)
b
respectively, meaning that Alice executes Alg. 1 with a1 Grover iterations and gets x1 (2.27), then runs Alg. 1 again for a2 Grover iterations to get x2 and so on, until the cth quantum measurement. For that final measurement, she gets xc . Thus, she obtains the string of measurement outcomes c A A A xA (3.22) i (a) i=1 := x1 (a), x2 (a), . . . , xc (a) with xi (a) the ith measurement outcome depending on action ai of strategy a (3.21). Similarly, Bob executes Alg. 1 under his strategy b (3.21) to obtain the string of measurement outcomes c B B B xB (3.23) i (b) i=1 := x1 (b), x2 (b), . . . , xc (b) , which is a tuple of the same length as Eq. (3.22). Here, we refer to the ith quantum measurement as Alice and Bob executing ai ∈ a and bi ∈ b Grover iterations, B respectively, and obtaining xA i and xi for i ∈ [c] (2.28). For each i ∈ [c], ( ( 1 xA 1 xB A B i (a) ∈ M i (b) ∈ M Xi (a) := , Xi (b) := , (3.24) 0 otherwise 0 otherwise
31 are random variables indicating whether Alice’s or Bob’s ith quantum measurement yields a valid proof-of-work. In our model, Alice’s quantum measurements are independent of each other, and the same is true for Bob. That is, XiA (a) ⊥ ⊥ XjA (a), XiB (b) ⊥⊥ XjB (b) for i ̸= j,
(3.25)
where ⊥ ⊥ denotes probabilistic independence. In general, Alice’s and Bob’s measurements are not independent of each other; i.e., XiA (a) ̸⊥⊥ XjB (b), XiB (b) ̸⊥⊥ XjA (a),
(3.26)
as the outcomes of Alice’s and Bob’s quantum measurements can be correlated through Sattath’s AQMS. We now describe how Alice’s and Bob’s payoff matrices are expressed as sums of payoff matrices corresponding to each of their c quantum measurements. Example 1 (Additive structure of payoff matrices). Suppose that for c = 2 Alice and Bob play the strategies a = (10, 20) b = (15, 25)
(3.27)
respectively. Excluding Sattath’s AQMS, Alice’s payoff is determined from two disjoint events. Alice either succeeds after executing 10 Grover iterations, or she fails after 10 but succeeds after 20 whereas Bob fails after 15. These two events represent Alice’s first and second quantum measurements, respectively, and the payoff Alice receives from each contributes to her total payoff for the given strategy profile (a, b). Thus, Alice’s total payoff can be expressed as a sum of the payoffs she receives from each quantum measurement. Given that Alice’s quantum measurements are independent of each other, and the same is true for Bob, we associate to each quantum measurement i ∈ [c] (2.28) a pair of payoff matrices (Def. 38), Ai and Bi , that give Alice’s and Bob’s respective payoffs for their ith quantum measurement. In other words, we express Alice’s and Bob’s total payoff matrices as A :=
c X
Ai , B :=
c X
i=1
Bi .
(3.28)
i=1
Furthermore, we express each Ai as Ai := Ameas + AAQMS , Bi := Bimeas + BiAQMS , i i
(3.29)
Ameas , Bimeas i
(3.30)
where
are the payoff matrices encoding Alice’s and Bob’s payoffs from their ith quantum measurements alone, and AAQMS , BiAQMS i
(3.31)
are the payoff matrices encoding Alice’s and Bob’s payoffs from their deployment of Sattath’s AQMS [2] on their ith quantum measurement. Consequently, the payoff functions u(a, b), v(a, b) (Remark 17) that determine the entries of A and B (Def. 38) have the same additive structure. That is, u(a, b; D, γS ) :=
c X i=1
ui (a, b; D, γS ), v(a, b; D, γS ) :=
c X
vi (a, b; D, γS ),
(3.32)
i=1
with ui (a, b; D, γS ) := umeas (a, b; D) + uAQMS (a, b; D, γS ), vi (a, b; D, γS ) := vimeas (a, b; D) + viAQMS (a, b; D, γS ), i i
(3.33)
giving Alice’s and Bob’s payoffs from their ith quantum measurement and from the deployment of Sattath’s AQMS, respectively, for the strategy profile (a, b) (3.21). We discuss the mathematics of incorporating Alice’s and Bob’s c quantum measurements into their payoff matrices. To formulate the payoff matrices for Alice and Bob in this setting, we extend the framework for a single quantum measurement established for S2QR (Def. 44) [3]. For a single quantum measurement, Alice’s and Bob’s payoffs depend
32 on the number of Grover iterations performed by each quantum miner. For example, if Alice performs fewer Grover iterations than Bob, her payoff is simply the probability that her quantum measurement is successful P (XA = 1),
(3.34)
P (X)
(3.35)
with
denoting the probability that event X occurs. In the context of the FQS algorithm, this probability is p(k) (2.32), which we remind is implicitly dependent on D. Conversely, if Bob performs the same number of Grover iterations as Alice or fewer, then Alice’s payoff is the joint probability that her measurement is successful whereas Bob’s measurement failed, P (XiA (a) = 1, XiB (b) = 0) = P (XiA (a) = 1)P (XiB (b) = 0),
(3.36)
where we factorise the probabilities because Sattath’s AQMS does not contribute to these terms. We note that as these probabilities are dependent on the value of the network difficulty D (2.32), umeas (a, b), uAQMS (a, b), vimeas (a, b), i i AQMS (a, b) are functions of D too. and vi For multiple quantum measurements, we extend the logic of a single quantum measurement to account for all possible outcomes. For Alice playing strategy a and Bob playing strategy b (3.21), we consider the entries of Ameas i and Bimeas to determine Ameas and B meas (3.30). The cumulative number of Grover iterations performed by Alice and Bob up to their ith quantum measurement is Ai :=
i X
aj , Bi :=
j=1
i X
bj , A0 := 0, B0 := 0,
(3.37)
j=1
respectively. Furthermore, [c]0 ∋ ℓA (a, b) := max{j ∈ [c]0 : Aj < Bi }, [c]0 ∋ ℓB (a, b) := max{j ∈ [c]0 : Bj < Ai }
(3.38)
are the indices in Alice’s and Bob’s strategies (3.21) that indicate the last quantum measurement performed by Alice or Bob before the other’s ith quantum measurement. For Alice’s ith quantum measurement, the entry of Ameas i corresponding to the strategy profile (a, b) (3.21) is ℓ (a,b)
Y BY i−1 A A P X (a) = 0 P XrB (b) = 0 umeas (a, b; D) := P X (a) = 1 r i i r=1
(3.39)
r=1
with ℓB dependent on b (3.38) and P implicitly dependent on D. The entry of Ameas (3.39) is the joint probability that Alice’s ith quantum measurement is successful, but failed her i first i − 1 quantum measurements, and Bob failed his first ℓB quantum measurements. The analogous entry of Bimeas , ℓ (a,b)
Y AY i−1 P XrB (b) = 0 P XrA (a) = 0 , vimeas (a, b; D) := P XiB (b) = 1
(3.40)
r=1
r=1
reflects the same logic applied to Bob’s ith quantum measurement. Thus, our formulation captures the cumulative nature of our model and extends the S2QR framework [3] to multiple quantum measurements. 3.
AQMS
Now we discuss the mathematics required to describe the entries AAQMS and BiAQMS . We first explain how Sattath’s i AQMS affects Alice’s and Bob’s payoffs based on the timings of Alice’s and Bob’s most recent quantum measurements relative to each other. Next, we consider the special case where Alice and Bob perform a quantum measurement at the same time. Then, we discuss additional AQMS terms and provide our justification for their omission from Alice’s and Bob’s total payoff. Now we explain the mathematics required to describe the entries of AAQMS and BiAQMS (3.29). When a quantum i miner employs Sattath’s AQMS, they perform a quantum measurement with fewer Grover iterations k than in their chosen strategy.
33 Fact 1. As Alice and Bob perform only c quantum measurements per our model, Bob cannot respond to Alice with Sattath’s AQMS if he has exhausted all c quantum measurements, so ℓB < c. For Alice’s ith quantum measurement, the entry of AAQMS corresponding to the strategy profile (a, b) i uAQMS (a, b; γS ) := γS P i
XiA (a) = 1
i−1 Y
! ℓB (a,b) Y B (b) = 1 , P XrB (b) = 0 P XAQMS P XrA (a) = 0
(3.41)
r=1
r=1
for γS Sattath’s propagation parameter (Def. 19), is the joint probability that Alice succeeds on her ith quantum measurement after failing all previous i − 1 quantum measurements, whereas Bob fails his first ℓB quantum measurements but then adopts Sattath’s AQMS and succeeds after performing Ai − BℓB Grover iterations. Here, B XAQMS (b)
(3.42)
is a random variable denoting the outcome of Bob’s measurement after employing Sattath’s AQMS. We consider now the special case for which Alice and Bob perform a measurement at the same time as a result of their chosen strategies. In other words, Ai = Bj , so uAQMS (a, b, γS ) = γS P i
XiA (a) = 1
P
XjB (b) = 1
i Y
! P (XrA (a) = 0)
r=1
j Y
! P (XrB (b) = 0)
(3.43)
r=1
is the entry of AAQMS corresponding to the strategy pair (a, b) in this case. The entries of BiAQMS are derived i analogously by swapping the roles of Alice and Bob (3.41, 3.43) and replacing γS with 1 − γS . We explain why certain payoffs related to Sattath’s AQMS are omitted in our model. We note that, in theory, the entries of AAQMS (3.41) should also include the payoff Alice receives after employing Sattath’s AQMS [2] when Bob i yields a proof-of-work. This additional payoff, ! ℓA (a,b) i−1 Y Y A γS P XiB (b) = 1 P (XrB (b) = 0) P (XrA (a) = 0) P (XAQMS (a) = 1), (3.44) r=1
r=1
is structurally identical to Eq. (3.41) but with the labels for Alice and Bob reversed. However, incorporating this payoff into the entries of AAQMS (and similarly for BiAQMS ) would require knowing the total ordering of Alice’s and i Bob’s quantum measurements. This knowledge is required because the number of Grover iterations Alice performs when deploying Sattath’s AQMS depends on the timing of Bob’s quantum measurements relative to all of Alice’s. The structure of Alice’s and Bob’s payoff matrices (3.28) either encodes the relative timings of Alice’s quantum measurements with respect to Bob’s in Alice’s payoff matrix, or vice versa for Bob, but not both. As the total number of c-tuple orderings grows as 2c for each of Alice and Bob, a closed-form expression for Alice’s and Bob’s payoff c matrices is complicated and unnecessary, so we instead focus on a numerical solution. We now discuss the impact of omitting these additional payoffs from Alice’s and Bob’s payoff matrices on our results. Omitting these payoffs alters the specific optimal quantum mining strategies we compute. The entries of AAQMS and BiAQMS account for Bob deploying Sattath’s AQMS in Alice’s payoff matrix, and Alice deploying i Sattath’s AQMS in Bob’s payoff matrix, but not the reverse in either case. We expect these additional payoffs to be higher-order corrections, and, although we have not formally studied their impact, their exclusion allows us to write a compact closed-form expression for Alice’s and Bob’s payoff matrices. We leave an analysis including all terms in Alice’s and Bob’s payoff matrices for future work.
C.
Methods
We outline the methods used to compute optimal mining strategies for Alice and Bob and the subsequent 51% threshold. We begin by discussing how the entries of Alice’s and Bob’s payoff matrices are computed and how we manage the computationally prohibitive dimension of these matrices. Next, we explain how the optimal quantum mining strategies are computed. Then, we describe the simulations used to estimate how the employment of these optimal quantum mining strategies affect Bitcoin’s security.
34 1.
Computing payoff matrices
We describe how we compute Alice’s and Bob’s payoff matrices. We begin by explaining how the individual entries of each matrix are computed. Next, we describe the heuristic used to sample Alice’s and Bob’s pure strategies. Finally, we explain how Alice’s and Bob’s payoff matrices are computed based on sampling. We first describe how we compute the individual entries of Alice’s and Bob’s payoff matrices. Each entry of Alice’s payoff matrix corresponds to a strategy profile (a, b) ∈ S0c × S0c (3.9) and is computed by evaluating a function fA : S0c × S0c × R+ × [0, 1] → R : (a, b, D, γS ) 7→
c X
umeas (a, b; D) + uAQMS (a, b; D, γS ) i i
(3.45)
i=1
that returns a 64-bit float representing Alice’s payoff for the corresponding strategy profile (a, b) given network difficulty D and Sattath’s propagation parameter γS . The corresponding entry for Bob’s payoff matrix is computed by evaluating fA (b, a, D, 1 − γS ). Now we discuss how we sample Alice’s and Bob’s pure strategies when evaluating their payoff matrices. As the dimension of Alice’s and Bob’s payoff matrices grows combinatorially with c (Lemma 5), evaluating Alice’s and Bob’s payoff matrices in their entirety is computationally expensive. To reduce their dimensionality, we apply a heuristic to the set of pure strategies for Alice and Bob (3.9). Specifically, we construct a subset of Grover iteration counts from S0 (3.7) using a quadratic spacing, % ) ($ 2 i 32 ′ kopt : i ∈ [nq ]0 ⊆ S0 , (3.46) S0 := 1− 1− nq with nq being the number of Grover iteration counts sampled from S0 . With this, Alice’s and Bob’s reduced pure strategies, (S0c )′ := {k ∈ (S0′ )c : 1 · k ≤ κ} ⊆ S0c ,
(3.47)
are the subset of c-tuples of Grover iterations drawn from S0′ (3.46) that are permitted under the cumulative Grover iteration budget κ. To further reduce the dimensionality of Alice’s and Bob’s payoff matrices, we also exclude pure strategies that are strictly dominated (Def. 40), as a rational player will not play them. Now we describe how the sampled pure strategy spaces are used to compute Alice’s and Bob’s payoff matrices. Using the sampled pure strategy spaces, we evaluate fA (a, b; D, γS ) for each strategy profile (a, b) ∈ (S0c )′ × (S0c )′ ,
(3.48)
and similarly for Bob. We note that we decrease the number of sampled Grover iteration counts nq as c increases to ensure that evaluating Alice’s and Bob’s payoff matrices is computationally manageable. The resulting payoff matrices have dimensions that are small enough such that the payoff matrices can be stored entirely in memory (requiring only a few gigabytes), further allowing the Lemke-Howson algorithm [8, 29] to finish executing within a practical amount of time (on the order of hours). 2.
Optimal quantum mining strategy computation
We explain how the optimal quantum mining strategies are computed using Alice’s and Bob’s payoff matrices. We start by describing how the Lemke-Howson algorithm is implemented using the Gambit library. Next, we discuss the specific parameters used for computing optimal quantum mining strategies via this algorithm. Then, we explain how we improve the precision of the computed Nash equilibria via Gambit’s Rational class. We discuss how the Lemke-Howson algorithm is implemented in our code. To compute the optimal quantum mining strategies for Alice and Bob, we use the Lemke Howson algorithm implemented as the gambit-lcp method in the pygambit library [39]. We use Alice’s and Bob’s payoff matrices as input into this method. Due to the exponential worst-case runtime of the Lemke-Howson algorithm [8], we limit the number of Nash equilibria computed with the stop after parameter and compute only one exact Nash equilibrium for each value of c. We now describe the parameters used in computing the optimal quantum mining strategies. We restrict ourselves to c ≤ 4, since for larger values, the runtime of the Lemke-Howson algorithm becomes prohibitively long, often taking days to compute a single Nash equilibrium. For computing the optimal quantum mining strategies, the number of sampled Grover iteration counts nq (3.46) was chosen so that Alice’s and Bob’s payoff matrices had similar dimensions
35 for c ∈ [2, 3, 4]. A smaller dimension was used for c = 1, which was sufficient for comparing optimal quantum mining strategies to this base case. Computing Nash equilibria for c > 4 requires decreasing the value of nq to a degree such that S0′ (3.46) is no longer representative of the full pure strategy space. We compute Nash equilibria for the simplest case for c = 1 to serve as a baseline for comparison with the multiple-measurement cases. For the low-difficulty regime, we assign D ← 3 651 011.631,
(3.49)
which is the value of the network difficulty from 26 February 2013 [40]. For the high-difficulty and ideal regimes, we assign D ← 119 116 256 505 723.5,
(3.50)
which is the value from 9 May 2025 [40]. We note that it is expected that the network difficulty will continue to increase beyond this value due to technological advancements in mining hardware [1]. For all computed Nash equilibria, we assign γS ← 0.5,
(3.51)
meaning that Alice and Bob have equal probability of their blocks being appended to the longest branch of the blockchain during a temporary fork. This choice is motivated by the fact that Alice and Bob have identical resources. We explain how Gambit’s Rational class is used to reduce floating-point error in Nash equilibria computation. To improve the precision of the computed Nash equilibria, we set the parameter rational=True in the gambit-lcp solver, enabling the solver to use Gambit’s built-in Rational class in the computation [39]. Gambit’s Rational class implements an exact representation of rational floating-point numbers by storing them as numerator-denominator pairs, eliminating the rounding errors inherent to their binary representations. Although using the Rational class increases the execution time of the Lemke-Howson algorithm, it significantly improves the precision of the computed Nash equilibria. 3.
Quantum mining simulation
We discuss the quantum mining simulation used to determine how the optimal quantum mining strategies affect Bitcoin’s security against a 51% attack. We begin by giving an overview of the simulation and its parameters. Then, we discuss how the simulation handles the timings of quantum measurement and classical block-arrival events. Finally, we discuss our method for studying how the network difficulty affects pstale under the deployment of optimal quantum mining strategies. We explain how we simulate the effect of Alice’s and Bob’s optimal quantum mining strategies on pstale . We perform a Monte Carlo simulation parameterized by a Nash equilibrium computed by the Lemke-Howson algorithm, as well as γS and D. The simulation begins at time zero and draws the next classical block arrival time from an exponential distribution with rate λ = 1/600 seconds (Remark 6). While searching for a valid block, the number of Grover iterations performed by Alice and Bob for each of their c quantum measurements is sampled from their respective mixed strategies in the Nash equilibrium. We record the timing of quantum measurements, which occur either according to Alice’s and Bob’s chosen strategies or as a result of Sattath’s AQMS, along with the classical block arrival times. For every new block that is appended to the blockchain, we repeat the process of simulating the mining of the next block by resampling Alice’s and Bob’s strategies from the Nash equilibrium and generating the next classical block arrival time. This cycle of simulating the next block in the blockchain is repeated until 86400 simulation seconds (1 day) have elapsed. We simulate ns = 1 000 000 days. For each simulated day i ∈ [ns ] (2.28), let bi denote the number of blocks mined on day i, fi denote the number of forks observed on day i, and pistale := fi/bi
(3.52)
the stale rate on day i. From the empirically-observed distribution of pistale , we compute the 95th and 99th percentiles, P95 , P99 ,
(3.53)
and the empirical probability n
P>1/3 :=
s 1 X 1 i 1 ns i=1 pstale > /3
(3.54)
36 that any pistale exceeds the 1/3 benchmark, with 1C being the indicator function for condition C. Furthermore, we also compute the empirical probability n
Pdet :=
s 1 X 1q <0.05 , ns i=1 i
(3.55)
of detecting the presence of quantum mining, where qi := P (X ≥ fi ) , X ∼ Binomial(bi , 0.0024)
(3.56)
is the p-value for day i under the null hypothesis that no quantum miners are present, with 0.0024 being the classical stale rate [17] and X ∼ Binomial(bi , 0.0024) following from block arrival times forming a Poisson process (Remark 8). We describe how we handle the timing of quantum measurements and classical block arrival events in the Monte Carlo simulation. Alice’s and Bob’s chosen strategies are converted into quantum measurement times by assuming that each Grover iteration takes 600/κ seconds to execute. We assume that the time required for state preparation, measurement, and constructing the relevant quantum-phase oracle is negligible and that Alice and Bob begin executing the FQS algorithm again immediately after a failed measurement. The quantum measurement times and the classical block arrival times are sorted to form a sequence of events. We record which events belong to Alice, Bob, or the classical network, and handle each event accordingly. If a quantum miner measures and is successful, Sattath’s AQMS is triggered for the other quantum miner who is forced to measure with the Grover iterations they have accumulated up to that point. If Sattath’s AQMS results in a successful measurement, then a fork is recorded. If the event is a classical block arrival, a block is appended to the blockchain unconditionally, and both quantum miners independently employ Sattath’s AQMS. To further study the impact that optimal quantum mining strategies would have on pstale , we also plot how different values of D (2.14) affect pstale for the values of c considered. For each value of D ∈ {230 , 231 , . . . , 245 } =: 2[30,45] ,
(3.57)
and for each value of c ∈ [4], we compute an optimal quantum mining strategy via the Lemke-Howson algorithm and then simulate the deployment of this strategy within the Bitcoin network. Here, we simulate the deployment of the optimal quantum mining strategies over 50 000 days to reduce the overall computation time, and report both P95 (3.53) and Pdet (3.55). We plot P95 as a function of D to study the pstale that is exceeded on 5% of the worst days of quantum mining, and Pdet as a function of D to study how the network difficulty affects the probability of detecting quantum mining. IV.
RESULTS
Now we present our results for how Alice and Bob should play the game including examples and show how this game affects Bitcoin’s security against a 51% attack. First we construct closed-form expressions for Alice’s and Bob’s payoff matrices. Next, we present examples of optimal quantum mining strategies for Alice and Bob, which correspond to Nash equilibria. Finally, we report the implications for Bitcoin’s security if Alice and Bob employ an optimal strategy for each quantum race. A.
Payoff matrices for quantum miners
Now we obtain the closed-form expressions for the payoff matrices used by Alice and Bob. First, for didactic reasons, we derive the expressions for Alice’s and Bob’s payoff matrices using only the terms that account for their c quantum measurements and excluding the terms from Sattath’s AQMS. Then, we extend these expressions to incorporate the terms corresponding to Sattath’s AQMS and derive expressions for Alice’s and Bob’s payoff matrices in our model. 1.
Payoff matrices for multiple measurements
Having developed the mathematical machinery in §III B, we now derive the expressions giving the entries of Ameas i and Bimeas (3.30) and present an example. We first discuss preliminaries explaining how we use the mathematics introduced in §III B to obtain these two matrices. Then, we derive a closed form of these payoff matrices. Finally, for didactic reasons, we illustrate an example of these entries for c = 2.
37 First, as a preliminary, we briefly clarify how the mathematics introduced in §III B relates to the general form and Bimeas (3.30). The rows and columns of Alice’s and Bob’s payoff matrices are inof the entries of Ameas i meas (3.30) is given by evaluating the dexed by α and β (3.19). β) entry Ameas i and Bi payoff func Thus, the (α, (α) (β) (α) (β) meas meas k , k ; D (3.40) for the strategy profile k(α) , k(β) corresponding k , k ; D (3.39) and vi tions ui to (α, β) (3.19). Furthermore, as we enumerate all possible quantum measurement orderings from the strategy profile (a, b), the values of ℓA (a, b) and ℓB (a, b) (3.38) are determined by the quantum measurement ordering being considered. We now derive a closed-form expression for the entries of Alice’s and Bob’s payoff matrices that correspond to their ith quantum measurements, Ameas and Bimeas (3.29). The (α, β) (3.20) entry is i Ameas : [|S0c |] × [|S0c |] → [0, 1] : (α, β) 7→ Ameas (α, β) , i i
(4.1)
α 7→ k(α) = (a1 , a2 , . . . , ac ), β 7→ k(β) = (b1 , b2 , . . . , bc ),
(4.2)
with the integers
mapping to a pair of pure strategies (3.19), and
Ameas (α, β) = i
1 Ai < b1 (1 − p(b1 )) b1 ≤ Ai < b1 + b2 ! i−1 (1 − p(b1 ))(1 − p(b2 )) b1 + b2 ≤ Ai < b1 + b2 + b3 Y p(ai ) (1 − p(ar )) .. . r=1 Qc−1 (1 − p(br )) Bc−1 ≤ Ai < Bc Qr=1 c Ai ≥ Bc . r=1 (1 − p(br ))
(4.3)
Here, we remind that Ai and Bi (3.37) are the cumulative number of Grover iterations performed by Alice and Bob up to their ith quantum measurement, respectively. As Alice and Bob have identical quantum and classical resources, the quantum race is symmetric (Def. 44). Consequently, Bimeas = (Ameas )⊺ i
(4.4)
is Bob’s payoff matrix from his ith quantum measurement alone. We illustrate the terms contributing to Alice’s and Bob’s payoff from their c quantum measurements (Ameas , B meas ) by examining the case where each quantum miner performs two quantum measurements. In this setting, Alice’s and Bob’s pure strategies are elements of S02 (3.9), which are 2-tuples (a1 , a2 ) and (b1 , b2 ). Here, Ameas = Ameas + Ameas , B meas = B1meas + B2meas 1 2
(4.5)
are the components contributing to Alice’s and Bob’s payoff matrix from their first and second quantum measurements, respectively. Focusing on Alice’s payoff matrix, a1 < b1 p(a1 ) meas A1 (α, β) = p(a1 )(1 − p(b1 )) (4.6) b1 ≤ a1 < b1 + b2 p(a )(1 − p(b ))(1 − p(b )) a ≥ b + b , 1 1 2 1 1 2 is the (α, β) element of Ameas , whereas 1 a1 + a2 < b1 p(a2 )(1 − p(a1 )) meas A2 (α, β) = p(a2 )(1 − p(a1 ))(1 − p(b1 )) b1 ≤ a1 + a2 < b1 + b2 p(a )(1 − p(a ))(1 − p(b ))(1 − p(b )) a + a ≥ b + b . 2 1 1 2 1 2 1 2
(4.7)
is the (α, β) element of Ameas . As the quantum race is symmetric, the terms contributing to Bob’s payoff are computed 2 by taking the transpose of Alice’s terms (4.4). 2.
Payoff entries with Sattath’s AQMS
We build on the previous result (4.3) by including Sattath’s AQMS, which gives Alice and Bob another chance to win the quantum race in the event that their opponent wins first. We first derive the expressions for Alice’s and Bob’s payoff matrices in this case. Then, we show how the example is modified by choosing a particular value of c.
38 As a preliminary, we describe how we build on the previous result to derive the general form of the entries of Alice’s and Bob’s payoff matrices. The (α, β) entry of Ai (3.29) is obtained by evaluating the payoff func(α, β; D, γS ) (3.41,3.43) with γS being Sattath’s propagation parameter (Def. 19) (α, β; D) (3.39) and uAQMS tions umeas i i for the strategy profile (k(a) , k(b) ) corresponding to (α, β) (4.2) for each i ∈ [c] (2.28) and then computing the full entry of A (3.28). The entries of B are computed analogously. We now present the general form of Alice’s and Bob’s payoff matrices. We incorporate Sattath’s AQMS (3.41) into (4.3) and Bimeas (4.4) to obtain the full payoff matrices A and B. Focusing on Alice, the (α, β) the entries of Ameas i entry (3.19) of Ai takes the form Ai : [|S0c |] × [|S0c |] → [0, 1 + γS ] : (α, β) 7→ Ai (α, β; γS ) ,
(4.8)
where p(ai )FAi−1 + γS p(ai )FAi−1 p(Ai ) p(ai )FAi−1 FB1 + γS p(ai )FAi−1 p(b1 ) i−1 1 i−1 1 p(ai )FA FB + γS p(ai )FA FB p(Ai − b1 ) i−1 2 p(ai )F FB + γS p(ai )F i−1 FB1 p(b2 ) A A Ai (α, β; γS ) = . . . i−1 c−1 i−1 c−1 p(ai )FA FB + γS p(ai )FA FB p(Ai − Bc−1 ) i−1 c−1 i−1 c p(ai )FA FB + γS p(ai )FA FB p(bc ) i−1 c p(ai )FA FB
Ai < b1 Ai = b1 b1 < Ai < b1 + b2 Ai = b1 + b2
(4.9)
Bc−1 < Ai < Bc Ai = Bc Ai > Bc
and FAi :=
i Y
(1 − p(ak )), FBi :=
k=1
i Y
(1 − p(bk ))
(4.10)
k=1
denotes the probabilities that Alice and Bob fail their first i quantum measurements, respectively. As the game is symmetric (Remark 19), Bob’s ith payoff is Bi = A⊺i ,
(4.11)
with γS replaced by 1 − γS . We note that, for c = 1, Alice’s and Bob’s payoff matrices reduce to those of the S2QR model for Bitcoin (2.62) [3]. Assigning γS ← 0 recovers the stingy variant [3], whereas assigning γS ← 1/2 recovers the non-stingy variant (2.62). Continuing the example with c = 2, we illustrate the general structure of Alice’s and Bob’s payoff matrices. We incorporate the terms from Sattath’s AQMS (3.41, 3.43) into Ameas (4.6, 4.7) and Bimeas in this example. Focusing i on Alice’s payoff matrix again, p(a1 ) + γS p(a1 )p(a1 ), a1 < b1 a1 = b1 p(a1 )(1 − p(b1 )) + γS p(a1 )p(b1 ) (4.12) A1 (α, β; γS ) = p(a1 )(1 − p(b1 )) + γS p(a1 )(1 − p(b1 ))p(a1 − b1 ) b1 < a1 < b1 + b2 p(a1 )(1 − p(b1 ))(1 − p(b2 )) + γS p(a1 )(1 − p(b1 ))p(b2 ) a1 = b1 + b2 p(a1 )(1 − p(b1 ))(1 − p(b2 )) a1 > b1 + b2 , is the (α, β) element of A1 , while p(a2 )(1 − p(a1 )) + γS p(a2 )(1 − p(a1 ))p(a1 + a2 ) a1 + a2 < b1 a1 + a2 = b1 p(a2 )(1 − p(a1 ))(1 − p(b1 )) + γS p(a2 )(1 − p(a1 ))p(b1 ) A2 (α, β; γS ) = p(a2 )(1 − p(a1 ))(1 − p(b1 )) + γS p(a2 )(1 − p(a1 ))(1 − p(b1 ))p(a1 + a2 − b1 ) b1 < a1 + a2 < b1 + b2 p(a2 )(1 − p(a1 ))(1 − p(b1 ))(1 − p(b2 )) + γS p(a2 )(1 − p(a1 ))(1 − p(b1 ))p(b2 ) a1 + a2 = b1 + b2 p(a2 )(1 − p(a1 ))(1 − p(b1 ))(1 − p(b2 )) a1 + a2 > b1 + b2 , (4.13) is the (α, β) element of A2 , with A = A1 + A2 being Alice’s full payoff matrix for our model in this setting.
(4.14)
39 B.
Optimal quantum mining strategies
We compute examples of optimal quantum mining strategies. Solving these examples is achieved by assigning numerical values to c and D, evaluating Alice’s and Bob’s payoff matrices, and computing an optimal quantum mining strategy via the Lemke-Howson algorithm [8]. We choose enough examples to illustrate our results, and the values of c and D are chosen such that the computations remain feasible for our computational resources. We first present optimal quantum mining strategies for the c = 2 case. Then, we consider the cases for c = 3, c = 4,
(4.15)
to understand how Alice and Bob allocate their resources for higher-order measurements. Next, we consider the c = 1 case to establish a baseline used to compare with the multiple measurement cases. Finally, we report the expected payoffs of all computed optimal quantum mining strategies. 1.
Two measurements
Now we turn to optimal quantum mining strategies for c = 2. We first list the parameters used in the computation. Then, we report the optimal quantum mining strategies computed in this case. We compute optimal quantum mining strategies for c = 2 using the parameters outlined in §III C. Specifically, we use γS ← 0.5
(4.16)
with the values of the network difficulty given in Eqs. (3.49) and (3.50) for the low- and high-difficulty regimes, respectively. For the ideal regime, we use the same value of D as the high-difficulty regime. Finally, we assign nq ← 45
(4.17)
for this computation. We present examples of optimal quantum mining strategies for all three network difficulty regimes in the c = 2 case. Figure 8 shows a Nash equilibrium for the low-difficulty regime, whereas Fig. 9 displays a Nash equilibrium for the ideal regime. For the high-difficulty regime, we find that the only optimal quantum mining strategy for Alice and Bob is to allocate all of their resources into their final quantum measurements. κ
1
i 2
0
0.18
0.11
0.08
0.08
0.08
0.07
0.06
0.06
0.04
0.04
0.03
0.03
0.02
0.02
0.02
0.02
0.02
0.02
0.01
<0.01
<0.01
σA (k)
(a)
κ
1
i 2
0
0.18
0.11
0.08
0.08
0.08
0.07
0.06
0.06
0.04
0.04
0.03
0.03
0.02
0.02
0.02
0.02
0.02
0.02
0.01
<0.01
<0.01
σB (k)
(b)
FIG. 8. The support of the mixed strategies for (a) Alice and (b) Bob in the Nash equilibrium for c = 2 in the low-difficulty regime. Each column corresponds to a pure strategy k in the support of the corresponding mixed strategy for Alice or Bob, σA,B (k), with the probability of playing each strategy shown on the abscissa with the probabilities adding to one. Each row corresponds to the measurement index i of the pure strategies, shown on the ordinate. The shade of each cell indicates the number of Grover iterations to perform for the specific measurement index and pure strategy combination, where white represents 0 Grover iterations and black represents κ Grover iterations.
40 κ
1
i 2
0
0.19
0.11
0.10
0.09
0.08
0.06
0.05
0.05
0.04
0.04
0.03
0.03
0.03
0.02
0.02
0.02
0.02
0.02
0.01
<0.01
<0.01
σA (k)
(a)
κ
1
i 2
0
0.19
0.11
0.10
0.09
0.08
0.06
0.05
0.05
0.04
0.04
0.03
0.03
0.03
0.02
0.02
0.02
0.02
0.02
0.01
<0.01
<0.01
σB (k)
(b)
FIG. 9. The support of the mixed strategies for (a) Alice and (b) Bob in the Nash equilibrium for c = 2 in the ideal regime, shown in the same format as Fig. 8.
2.
Three and four measurements
We present optimal quantum mining strategies for the case where both quantum miners perform c ∈ {3, 4} (4.15) quantum measurements between successive blocks. We first report the parameters used in this computation. Then, we present the optimal quantum mining strategies. Finally, we illustrate that these optimal quantum mining strategies are not unique by providing an example of a second optimal strategy computed in the low-difficulty regime for c = 3. For these computations, we use the same parameters as the computation for c = 2. However, we assign nq ← 21
(4.18)
nq ← 35
(4.19)
nq ← 25
(4.20)
for the c = 3 low-difficulty regime,
for c = 3 in the ideal and high-difficulty regimes, and
for c = 4. Now we present the computed optimal quantum mining strategies for c = 3 and c = 4 (4.15). Figures 10 and 11 display an optimal quantum mining strategy for the low-difficulty regime for c = 3 and c = 4, respectively, while Figs. 12 and 13 display an optimal quantum mining strategy for the ideal regime for c = 3 and c = 4, respectively. Similar to the c = 2 case, we find that for the high-difficulty regime, the only optimal quantum mining strategy for Alice and Bob is to allocate all of their resources into their final quantum measurements. To illustrate that the optimal quantum mining strategies are not unique, we compute an additional Nash equilibrium for c = 3 in the low-difficulty regime. This strategy is displayed in Fig. 14.
3.
One measurement and expected payoffs
Now we turn to the c = 1 case, which serves as a baseline used to compare how the quantum miners should optimally allocate their resources for multiple measurements. We first describe the parameters used in this computation and then report the computed optimal quantum mining strategies. Then, we report the expected payoffs for all the previously computed optimal quantum mining strategies. For computing these optimal quantum mining strategies, we use the same parameters as the computation for c = 2. However, here we assign nq ← 200,
(4.21)
41
1
i2 3 0.23
0.18
0.14
0.11
0.08
0.06
A ( k)
0.06
0.05
0.03
0.03
0.03
0
(a) 1
i2 3 0.23
0.18
0.14
0.11
0.08
0.06
B ( k)
0.06
0.05
0.03
0.03
0.03
0
(b) FIG. 10. The support of the mixed strategies for (a) Alice and (b) Bob in the Nash equilibrium for c = 3 in the low-difficulty regime, shown in the same format as Fig. 8. which in this case also gives the dimension of Alice’s and Bob’s payoff matrices. We report the computed optimal quantum mining strategies for c = 1. As the optimal quantum mining strategies for c = 1 contain many pure strategies in their support, we present the distribution of Grover iterations performed in the support of these optimal strategies as a histogram rather than a heatmap as for c ≥ 2. Figure 15 shows an optimal quantum mining strategy for the low-difficulty regime, whereas Fig. 16 shows an optimal quantum mining strategy for the ideal regime. For the high-difficulty regime, we find that the only optimal quantum mining strategy 32 is where Alice and Bob perform kopt (2.35) Grover iterations before measuring.
42
1 κ 2
i 3 0 4
0.40
0.24
0.13
0.12
0.08
0.01
0.01
σA (k)
(a)
1 κ 2
i 3 0 4
0.31
0.17
0.17
0.10
0.10
0.09
0.06
σB (k)
(b) FIG. 11. The support of the mixed strategies for (a) Alice and (b) Bob in the Nash equilibrium for c = 4 in the low-difficulty regime, shown in the same format as Fig. 8.
43 κ
1
i 2 3
0
0.20
0.11
0.11
0.09
0.07
0.06
0.06
0.04
0.04
0.04
0.04
0.04
0.03
0.03
0.03
0.02
0.01
σA (k)
(a) κ
1
i 2 3
0
0.20
0.11
0.11
0.09
0.07
0.06
0.06
0.04
0.04
0.04
0.04
0.04
0.03
0.03
0.03
0.02
0.01
σB (k)
(b)
FIG. 12. The support of the mixed strategies for (a) Alice and (b) Bob in the Nash equilibrium for c = 3 in the ideal regime, shown in the same format as Fig. 8.
44
1 κ 2
i 3 0 4
0.40
0.24
0.13
0.12
0.08
0.01
0.01
σA (k)
(a)
1 κ 2
i 3 0 4
0.31
0.17
0.17
0.10
0.09
0.09
0.06
σB (k)
(b) FIG. 13. The support of the mixed strategies for (a) Alice and (b) Bob in the Nash equilibrium for c = 4 in the ideal regime, shown in the same format as Fig. 8.
45
1
i2 3 0.25
0.22
0.10
0.10
0.09
0.07
A ( k)
0.07
0.06
0.05
<0.01
0
(a) 1
i2 3 0.23
0.16
0.14
0.12
0.11
0.08
B ( k)
0.05
0.04
0.04
0.03
0
(b) FIG. 14. The support of the mixed strategies for (a) Alice and (b) Bob in the second Nash equilibrium for c = 3 in the low-difficulty regime, shown in the same format as Fig. 8.
46 0.25 0.25 0.20
σB (k)
σA (k)
0.20 0.15 0.10
0.15 0.10
0.05
0.05
0.00
0.00 0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
k/κ
k/κ
(a)
(b)
0.8
1.0
0.25
0.25
0.20
0.20
σB (k)
σA (k)
FIG. 15. The distribution of Grover iterations in the support of the mixed strategies for (a) Alice and (b) Bob in the Nash equilibrium for c = 1 in the low-difficulty regime. The normalized number of Grover iterations k/κ is shown on the abscissa, divided into equal-width bins. The probability of performing the number of Grover iterations corresponding to each bin in the support of the Nash equilibrium σA,B (k), is shown on the ordinate, with the probabilities adding to one.
0.15
0.15
0.10
0.10
0.05
0.05
0.00
0.00 0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
k/κ
k/κ
(a)
(b)
0.8
1.0
FIG. 16. The distribution of Grover iterations in the support of the mixed strategies for (a) Alice and (b) Bob in the Nash equilibrium for c = 1 in the ideal regime, shown in the same format as Fig. 15.
47 Now we report the quantum miners’ expected payoffs for each of the previously computed optimal quantum mining strategies (Remark 18). Tables III and IV summarize Alice’s and Bob’s expected payoffs for the low-difficulty and ideal regimes, respectively. The expected payoffs for all difficulty regimes are reported to six decimal places, as any differences beyond this precision occur beyond the numerical precision of Python’s 64-bit floating-point arithmetic. In the high-difficulty regime, all computed optimal strategies yield an expected payoff of 8.9 × 10−5 . c Quantum Miner U (σ ∗ ) 1 Alice 0.537708 1 Bob 0.534115 2 Alice 0.625250 2 Bob 0.625250 3(1) Alice 0.617527 3(1) Bob 0.617527 3(2) Alice 0.607639 3(2) Bob 0.596411 4 Alice 0.639309 4 Bob 0.580668
TABLE III. Alice’s and Bob’s expected payoffs U (σ ∗ ) for each computed optimal quantum mining strategy in the low-difficulty regime. The superscripts (1) and (2) denote the two distinct Nash equilibria computed for c = 3.
c Quantum Miner U (σ ∗ ) 1 Alice 0.532788 1 Bob 0.532788 2 Alice 0.624900 2 Bob 0.624900 3 Alice 0.633620 3 Bob 0.633620 4 Alice 0.639528 4 Bob 0.580464
TABLE IV. Alice’s and Bob’s expected payoffs U (σ ∗ ) for each computed optimal quantum mining strategy in the ideal regime.
C.
Decrease of 51% attack threshold
We report our results for estimating pstale from simulating the deployment of the computed optimal quantum mining strategies in the Bitcoin network. We begin by presenting the estimated values of pstale for all previously computed optimal quantum mining strategies. These estimates are obtained by simulating the deployment of the optimal quantum mining strategies in the Bitcoin network by the quantum miners. Then, we show estimates of pstale over a range of network difficulties for c ∈ [4]. First we report the results of performing a Monte Carlo simulation to estimate pstale . Table V reports the 95th and 99th percentiles P95 and P99 (3.53), the maximum observed per-day stale-rate, the empirical probability P>1/3 (3.54), the empirical detection probability Pdet (3.55), and the average blocks and forks per day for all computed optimal quantum mining strategies, organized by the number of quantum measurements c. We now report on how pstale is affected by the value of the network difficulty D. Our simulations provide insight into how Bitcoin’s security is affected as the quantum miners allocate their resources over additional quantum measurements. For each c ∈ [4], we compute an optimal quantum mining strategy and estimate P95 (3.53) and Pdet (3.55) resulting from the quantum miners employing a corresponding optimal quantum mining strategy over 50 000 days. Figure 17 shows P95 and Pdet as a function of D ∈ 2[30,45] (3.57) in increments of powers of two, for each value of c. V.
DISCUSSION
Now we discuss our results. We first discuss the payoff derived for quantum miners. Next, we provide insight into the optimal quantum mining strategies computed for c ∈ [4] (2.28) across the three network difficulty regimes (Def. 45), and discuss the expected payoffs associated with these optimal quantum mining strategies. Subsequently, we discuss
48 c diff P95 P99 max P (pstale > 1/3) Pdet abd afd 1 High 0.0000 0.0000 0.0135 0.000000 0.000001 144.02 0.004 1 Low 0.2899 0.3011 0.3387 0.000008 1.000000 376.74 98.731 1 Ideal 0.2894 0.3005 0.3350 0.000001 1.000000 376.47 98.464 2 High 0.0000 0.0000 0.0146 0.000000 0.000004 144.01 0.004 2 Low 0.2639 0.2753 0.3126 0.000000 1.000000 388.05 91.659 2 Ideal 0.2644 0.2757 0.3232 0.000000 1.000000 388.19 91.873 3 High 0.0000 0.0000 0.0142 0.000000 0.000005 144.03 0.004 3 Low1 0.2722 0.2834 0.3271 0.000000 1.000000 393.31 96.167 3 Low2 0.2588 0.2703 0.3067 0.000000 1.000000 386.28 89.167 3 Ideal 0.2600 0.2714 0.3143 0.000000 1.000000 387.36 89.945 4 High 0.0000 0.0000 0.0154 0.000000 0.000005 144.01 0.004 4 Low 0.2543 0.2656 0.3198 0.000000 1.000000 384.22 87.123 4 Ideal 0.2545 0.2659 0.3063 0.000000 1.000000 384.29 87.205
TABLE V. Monte Carlo simulation for all computed optimal quantum mining strategies with averages taken over 1 000 000 simulated days. All values are reported to the fewest decimal digits to ensure distinguishability. Each row corresponds to a specific combination of the number of quantum measurements c and network difficulty regime (diff), where High/Low/Ideal denotes the difficulty regime and the superscripts distinguish the first and second Nash equilibria for the c = 3 low-difficulty case. The reported quantities are the 95th and 99th percentiles P95 and P99 , the maximum observed stale rate, the empirical probability P>1/3 that any given day’s stale rate exceeds the 1/3 benchmark, the empirical detection probability Pdet , and the average blocks (abd) and forks per day (afd). 0.30
1.0
c=1 c=2 c=3 c=4
0.25
0.8
0.20
Pdet
P95
0.6 0.15
0.4 0.10 0.2
0.05 0.00
0.0 2
31
2
33
2
35
2
37
2
39
2
41
2
43
2
45
231
233
235
237
D
D
(a)
(b)
239
241
243
245
FIG. 17. Estimated P95 (a) and Pdet (b) as functions of D for quantum miners employing an optimal quantum mining strategy over 50 000 simulated days. Four curves are shown on each plot, each representing a specific number of quantum measurements c over which the quantum miners allocate their resources. In (b), all four curves lie on top of each other. our simulation results for estimating pstale when the computed optimal quantum mining strategies are deployed and discuss the broader security implications for the Bitcoin network. Here we discuss our result that Alice and Bob each have constructed their respective payoff matrices for the case that each only performs one quantum measurement. Alice and Bob then use their knowledge of their payoff matrices to compete in a quantum race with the goal of finding a valid proof-of-work before the other. Alice’s and Bob’s payoff matrices represent their preferences over every combination of pure strategies and fully summarize the strategic game (Def. 30) representing the quantum race. In the S2QR model for Bitcoin [3], Alice’s and Bob’s payoff matrices were determined for the setting where they perform only one quantum measurement between consecutive blocks and are peaceful (Remark 15). The measurement-only terms in Alice’s and Bob’s payoff matrices (4.3) are similar to the S2QR model for Bitcoin: each entry corresponds to the joint probability that a quantum miner succeeds in their current quantum measurement, given that all previous quantum measurements from either quantum miner failed. For c = 1 and γS → 0, we recover the payoff matrices of the S2QR model for Bitcoin [3].
49 Extending this single-quantum-measurement case for payoff matrices to the general case of c multiple quantum measurements each, the entries of Ameas and B meas capture every possibility in which Alice and Bob can win the quantum race respectively across their c quantum measurements each. Likewise, the entries of AAQMS and B AQMS reflect the number of Grover iterations that Alice or Bob have accumulated when the other yields a valid proof-ofwork, triggering the employment of Sattath’s AQMS, depending on the relative timing of Alice’s and Bob’s c quantum measurements. We validate our result for c = 2 by showing that Ameas (4.6) and Ameas (4.7) agree with the result 1 2 derived in Ray’s PhD thesis [36], which is the sole prior case of studying a quantum race between two competing quantum Bitcoin miners with more than one quantum measurement. Alice and Bob use their payoff matrices to compute optimal quantum mining strategies corresponding to Nash equilibria. Given the identical resources of the quantum miners, we expect the optimal quantum mining strategies to be symmetric equilibria. Of our 13 computed optimal strategies for c ∈ [4], the equilibria are symmetric in nine cases. We observe asymmetric equilibria for c ∈ {1, 4} in the low-difficulty regime, c = 4 in the ideal regime, and the second optimal strategy computed for c = 3 in the low-difficulty regime. As symmetric equilibria are guaranteed to exist in symmetric games (Theorem 3), these cases of asymmetric equilibria likely reflect the path-dependence of the Lemke-Howson algorithm. In the low-difficulty and ideal regimes, Alice and Bob should allocate their fixed resources over multiple quantum measurements. Specifically, for c = 2, Alice and Bob should allocate their resources across both quantum measurements to balance the high success probability of the FQS algorithm in these regimes against the temporal advantage of one measuring before the other. However, for c ≥ 3, sometimes Alice and Bob should perform zero Grover iterations before a quantum measurement (Remark 11) to maximize the success probability of other quantum measurements. For all computed optimal strategies with c ≥ 3, the strategies involve pure strategies in which Alice and Bob concentrate their resources into fewer quantum measurements. This outcome is influenced by the Grover iteration budget κ (3.3) and reflects that spreading this budget over many quantum measurements is suboptimal, as the success probability of the FQS algorithm grows quadratically with the number of Grover iterations performed. For c = 1, Figs. 15 and 16 show that, most of the time, Alice and Bob should perform approximately half of their budgeted Grover iterations before measuring. We note that this distribution is specific to the computed optimal quantum mining strategy and may not generalize. In the high-difficulty regime, the optimal strategy is for the quantum miners to allocate all of their resources into their final quantum measurement. This result is counterintuitive, as one might expect that it would be more advantageous for Alice or Bob to allocate all of their resources into their first quantum measurement and gain a temporal advantage. This outcome is likely a result of the combination of the near-zero success probability of the FQS algorithm in this regime and payoff contributions from Sattath’s AQMS (3.41), which could slightly favour later quantum measurements. Although we do not have a rigorous explanation of this behaviour, including Sattath’s AQMS terms omitted from Alice’s and Bob’s payoff (III B) could remove this bias and result in the more intuitive strategy of allocating all resources to the first quantum measurement. With respect to the expected payoff of the computed optimal quantum mining strategies, allocating resources into two quantum measurements each yields the highest expected payoff (Tables III and IV). However, the computed optimal quantum mining strategies are not unique, as we demonstrate by computing two distinct optimal quantum mining strategies for c = 3 in the low-difficulty regime (Figs. 10 and 14). The Lemke-Howson algorithm traces a singular path through the space of strategy profiles of Alice and Bob, returning the first Nash equilibrium found [8]. Therefore, other optimal quantum mining strategies with higher expected payoffs might exist but were not returned by the Lemke-Howson algorithm. Alice and Bob deploy their optimal quantum mining strategies to beat each other at the race without regard to beating the classical Bitcoin network. Their quantum race has the side effect of increasing pstale due to the employment of Sattath’s AQMS [2]. This increased stale rate poses a threat to the entire network by creating stale blocks through forks, but the significance of this threat decreases and even becomes negligible in the high-difficulty regime. For all cases in the high-difficulty regime, 99% of the simulated days exhibit no forks at all, as the 95th and 99th percentiles are zero up to machine precision. Similarly, Pdet is negligible in this regime, meaning that the presence of the quantum miners is statistically indistinguishable from the classical network. The maximum observed pstale in the high-difficulty regime across all cases is 0.0154, which is approximately 20 times higher than the classical stale rate but still not significant in the sense that the 51% attack is still infeasible. The empirical probability that pstale > 1/3 is zero up to machine precision. Despite that two quantum miners are racing each other, the Bitcoin network produces the expected 144 blocks per day (Remark 5), confirming the negligible impact of quantum miners in this regime. This result that quantum miners have negligible effect in the high-difficulty regime is expected, as the success probability of the FQS algorithm is near-zero in this regime. Contrariwise, in the ideal and low-difficulty regimes, a single execution of the FQS algorithm is sufficient to yield a proof-of-work with high probability. A single execution suffices in the low-difficulty regime as the expected number of nonces to check is fewer than 232 , and, in the ideal regime, the quantum oracle encodes the entire block header.
50 As a general trend, increasing the value of c decreases P95 and P99 , as allocating resources over more quantum measurements decreases the success probability of those quantum measurements. Across all nine cases in the ideal and low-difficulty regimes, the empirical probability that pstale exceeds the 1/3 benchmark (Prop. 4) is zero empirically in all but two cases. These two exceptions to being zero arise for either c = 1 in the low-difficulty regime with probability 8 × 10−6 or c = 1 in the ideal regime with probability 1 × 10−6 . These cases do not contradict Prop. 4, as a 51% attack requires pstale to exceed the threshold (3.5) throughout the duration of the attack, not on a single day (Remark 7). Even then, these cases correspond to a threat emerging once every 342 or 2738 years, respectively, meaning that the Bitcoin network remains secure against this quantum attack. Finally, we find Pdet = 1 across all nine of these cases, meaning that it is statistically certain to detect the presence of quantum miners in the ideal and low-difficulty regimes. Finally, to assess the impact of optimal quantum mining strategies on Bitcoin’s security, we study how P95 and Pdet vary as functions of D for c ∈ [4] (2.28) shown in Fig. 17. For D ≤ 232 , P95 plateaus, as a single execution of the FQS algorithm is sufficient to yield a proof-of-work with high probability. For D > 232 , P95 approaches zero, which is consistent with the fact that the success probability (2.32) decreases for increasing D whereas the number of Grover 32 iterations is restricted to at most kopt (2.35). Pdet follows the same trend, but drops off at a higher value of D than P95 . This offset is because even a small increase in pstale above the classical baseline is statistically detectable by the network due to the small value of that baseline. For all values of D and c considered, P95 < 1/3, reinforcing that the Bitcoin network remains secure against this quantum threat for our model. We now explain that the threat posed to the Bitcoin network by a pair of quantum miners racing each other is negligible for the foreseeable future. In the high-difficulty regime, which reflects both current and projected values of the network difficulty D, the optimal quantum mining strategies of Alice and Bob produce a pstale that is statistically indistinguishable from the classical value of 0.0024 [17], meaning that the Bitcoin network remains secure in this regime. In the low-difficulty and ideal regimes, pstale increases significantly, approaching the 1/3 benchmark on some days, which is evidenced by the nonzero P>1/3 for c = 1. However, neither of these regimes is likely to hold in practice. The low-difficulty regime requires a network difficulty D at values not seen since the early days of Bitcoin, and the ideal regime requires a quantum-phase oracle capable of encoding the entire 640-bit block header (instead of just the 32-bit nonce), which is unrealistic given that even the 32-bit quantum-phase oracle is known to be expensive to construct [4]. Furthermore, even if these conditions were met in reality, we find that Pdet = 1 in both regimes, meaning that one could detect quantum mining with statistical certainty.
VI.
CONCLUSIONS
We solved Problem 1 by determining optimal quantum mining strategies for two quantum miners and estimating the impact of these strategies on Bitcoin’s security against a 51% attack. We extended the S2QR model for Bitcoin [3] to include multiple quantum measurements between successive blocks and Sattath’s AQMS [2]. We derived the payoff matrices of the two quantum miners in this novel setting, computed optimal quantum mining strategies across three network difficulty regimes, and estimated the effect of these optimal strategies on the stale rate pstale . We find that two quantum miners cannot raise pstale sufficiently to render the Bitcoin network vulnerable to a 51% attack according to our model. In other words, we show that the Bitcoin network is safe against our adversarial model. In the high-difficulty regime, which reflects both the current and projected values of the network difficulty D, the effect of quantum miners on pstale is negligible and statistically indistinguishable from that of classical Bitcoin miners. In the low-difficulty and ideal regimes, quantum mining produces a significant increase in pstale compared to classical values. However we find that pstale < 1/3 on all but a vanishingly-small fraction of simulated days, meaning that the Bitcoin network remains secure according to the historical benchmark. Furthermore, these regimes are unlikely to hold in practice, and it is statistically certain that the presence of the quantum miners would be detected by the classical network. The method we develop for studying two quantum miners sets the foundation for studying the threat posed by three or more quantum miners. We now present our views on next steps for this work. Our model for two quantum miners only accounts for query-related overhead and not for overhead associated with other tasks such as quantum-state preparation and constructing the quantum-phase oracle for each candidate block. Thus, we have only modelled a best-case scenario for the quantum miners. Hence, the quantum miners’ combined effect on pstale will be less than we have predicted. Directions for future work could include generalizing to colluding quantum miners or to more than two non-colluding quantum miners, as well as determining the minimum number of quantum miners racing each other that would create a dangerous pstale given a network difficulty D. Other future work could incorporate the classical Bitcoin network as a single or multiple players joining the quantum race. Future work could account properly for overhead associated with building and querying the oracle. Each of these investigations would be valuable to connect the potential threat of quantum mining to the actual Bitcoin network. Overall, we conclude that the Bitcoin network remains secure against
51 the threat posed by two quantum miners on pstale . VII.
ACKNOWLEDGMENTS
This work has been supported by Canada’s Natural Sciences and Engineering Research Council (NSERC). ZM thanks R. R. Nerem for his insightful conversations in the nascent stage of our work. We acknowledge the traditional owners of the land on which this work was performed at the University of Calgary: the Treaty 7 First Nations and the Métis Nation of Alberta.
52
[1] Andreas M. Antonopoulos. Mastering Bitcoin: Unlocking Digital Crypto-Currencies. O’Reilly Media, Sebastopol, CA, 1st edition, 2014. [2] Or Sattath. On the insecurity of quantum Bitcoin mining. Int. J. Inf. Secur., 19(3):291–302, Jun. 2020. [3] Troy Lee, Maharshi Ray, and Miklos Santha. Strategies for Quantum Races. In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), volume 124 of Leibniz International Proceedings in Informatics (LIPIcs), pages 51:1–51:21, Dagstuhl, Germany, 2019. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. [4] Divesh Aggarwal, Gavin Brennen, Troy Lee, Miklos Santha, and Marco Tomamichel. Quantum attacks on Bitcoin, and how to protect against them. Ledger, 3:68–90, Oct. 2018. [5] E O Kiktenko, N O Pozhar, M N Anufriev, A S Trushechkin, R R Yunusov, Y V Kurochkin, A I Lvovsky, and A K Fedorov. Quantum-secured blockchain. Quantum Sci. Technol., 3(3):035004, May. 2018. [6] Ryan Babbush, Adam Zalcman, Craig Gidney, Michael Broughton, Tanuj Khattar, Hartmut Neven, Thiago Bergamaschi, Justin Drake, and Dan Boneh. Securing Elliptic Curve Cryptocurrencies against Quantum Vulnerabilities: Resource Estimates and Mitigations, 2026. arXiv:2603.28846. [7] Pierre-Luc Dallaire-Demers and BTQ Technologies Team. Kardashev scale Quantum Computing for Bitcoin Mining, 2026. arXiv:2603.25519. [8] C. E. Lemke and J. T. Howson, Jr. Equilibrium points of bimatrix games. SIAM J. Appl. Math, 12(2):413–423, 1964. [9] Lorne Lantz and Daniel Cawrey. Mastering Blockchain. O’Reilly Media, Sebastopol, CA, 2020. [10] Paul Grassi, Michael Garcia, and James Fenton. Digital Identity Guidelines. Special publication 800-63-3, National Institute of Standards and Technology, Jun. 2017. Accessed: 2026-01-07. [11] National Institute of Standards, Technology (NIST), and Quynh Dang. Secure Hash Standard. Federal Inf. Process. Stds. 180-4, National Institute of Standards and Technology, Aug. 2015. Accessed: 2026-01-07. [12] Satoshi Nakamoto. Bitcoin: A Peer-to-Peer Electronic Cash System. https://bitcoin.org/bitcoin.pdf, 2008. Accessed: 2026-01-07. [13] Ittay Eyal and Emin Gün Sirer. Majority is not enough: bitcoin mining is vulnerable. Commun. ACM, 61(7):95—-102, Jun. 2018. [14] Ayelet Sapirshtein, Yonatan Sompolinsky, and Aviv Zohar. Optimal selfish mining strategies in bitcoin. In Jens Grossklags and Bart Preneel, editors, Financial Cryptography and Data Security, pages 515–532, Berlin, Heidelberg, 2017. Springer. [15] R. Bowden, H. P. Keeler, A. E. Krzesinski, and P. G. Taylor. Block arrivals in the Bitcoin blockchain, 2018. [16] Alex Hern. Bitcoin currency could be destroyed by ’51% attack’. The Guardian, 2014. Accessed: 2024-10-15. [17] Nicholas Stifter, Philipp Schindler, Aljosha Judmayer, Alexei Zamyatin, Andreas Kern, and Edgar Weippl. Echoes of the past: Recovering blockchain metrics from merged mining. Cryptology ePrint Archive, Paper 2018/1134, 2018. [18] Barry C. Sanders. Quantum Computation, pages 202–210. Elsevier, 2025. [19] Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’96, pages 212–219, New York, NY, USA, 1996. Association for Computing Machinery. [20] Cătălin Dohotaru and Peter Høyer. Exact quantum lower bound for Grover’s problem. Quantum Info. Comput., 9(5):533— -540, May. 2009. [21] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. In Quantum computation and information (Washington, DC, 2000), volume 305 of Contemp. Math., pages 53–74. Amer. Math. Soc., Providence, RI, 2002. [22] Phillip Kaye, Raymond Laflamme, and Michele Mosca. An Introduction to Quantum Computing. Oxford University Press, Oxford, England, 2006. [23] Abhijeet Alase, Robert R. Nerem, Mohsen Bagherimehrab, Peter Høyer, and Barry C. Sanders. Tight bound for estimating expectation values from a system of linear equations. Phys. Rev. Res., 4:023237, Jun 2022. [24] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010. [25] Robert Riley Nerem and Daya R. Gaur. Conditions for advantageous quantum bitcoin mining. Blockchain: Research and Applications, 4(3):100141, 2023. [26] Martin J. Osborne and Ariel Rubinstein. A Course in Game Theory. The MIT Press, Cambridge MA, July 1994. [27] Steven Tadelis. Game Theory: An Introduction. Princeton University Press, 2013. [28] Michael Maschler, Eilon Solan, and Shmuel Zamir. Game Theory. Cambridge University Press, 2013. [29] Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani. Algorithmic Game Theory. Cambridge University Press, Cambridge, 2007. [30] John Nash. Non-cooperative games. Ann. Math., 54(2):286–295, 1951. [31] Michael Kearns, Michael L. Littman, and Satinder Singh. Graphical models for game theory. In Proceedings of the Seventeenth Conference on Uncertainty in Artificial Intelligence, UAI’01, pages 253—-260, San Francisco, CA, USA, 2001. Morgan Kaufmann Publishers Inc. [32] Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. The complexity of computing a Nash equilibrium. SIAM J. Comput., 39(1):195––259, 2009. [33] C.H. Papadimitriou. Computational Complexity. Theoretical Computer Science. Addison-Wesley, 1994.
53 [34] Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci., 48(3):498–532, 1994. [35] M. D. Hirsch, C. H. Papadimitriou, and S. A. Vavasis. Exponential lower bounds for finding brouwer fixed points. Complexity, 5:379–416, 1989. [36] Maharshi Ray. On Some Optimisation Problems Arising From Quantum Computing. PhD thesis, National University of Singapore, Singapore, Jul. 2020. [37] Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, Cambridge, UK, 1995. [38] William Feller. An Introduction to Probability Theory and Its Applications. Wiley, New York, 1965. [39] Rahul Savani and Theodore L. Turocy. Gambit: The package for computation in game theory. https://www. gambit-project.org, 2025. Version 16.3.0. [40] Blockchain.com. Network difficulty. https://www.blockchain.com/explorer/charts/difficulty. Accessed: 2025-10-12.