TLDR:
The researchers attempt to determine whether the Bitcoin backbone protocol is resistant to a quantum attacker.
They establish a logical framework for the projected equations associated with
determining a quantum attacker’s probability of success using a quantum random oracle to determine the current state of the network in order to target the attack.Their analysis shows that the blockchain backbone protocol is resistant to a quantum attacker as long as the number of search queries is limited, with the likelihood of success increasing relative to the increase in number of queries.
Core Research Questions
 Will the Bitcoin backbone protocol be resistant to quantum attackers in the presence of a quantum random oracle? Are quantum attacks a threat to the current Bitcoin framework?
Citation
 Cojocaru, A., Garay, J., Kiayias, A., Song, F., & Wallden, P. (2020). PostQuantum Security of the Bitcoin Backbone and Quantum MultiSolution Bernoulli Search. arXiv preprint arXiv:2012.15254.
Background
 RSA PublicKey Cryptosystem was developed for the purpose of transmitting securely encrypted messages. It is a form of symmetric key cryptography that factors the product of two large prime numbers as its means of determining the private key that will permit public keys to execute transactions.
 Bernoulli Distribution is a method of determining discrete possible outcomes labeled by n = 0 and n = 1 (in which 1 is defined as “success and 0 is defined as “failure”) occurs with probability p where 0 < p < 1. This framework enables a user to determine the probability density function, or the likelihood that an event will occur or not.
 Random Oracles (RO) is a method of randomly generating a string of bits relative to a query, such that the randomly generated string perpetually identifies that query path to reduce time needed to make the same query through the oracle.
 Quantum Random Oracles (QRO) are a variation on the Random Oracle model which gives the oracle the capacity to describe and analyze the quantum state of an object, so that it can be queried through the oracle.
 SHA256 Encryption an easy to compute, but difficult to invert function that maps a message of arbitrary length into a fixed length, also known as an mbit or hash value. Secure Hash Algorithm 256 is given the 256 designation in reference to the number of bits used to hash a message.
 Lamport Logical Clocks are a means of ordering asynchronous events within a multiprocessor system. This method of mapping networks is performed with the intent of avoiding scenarios that would create deadlock or threaten the network concurrency.
 Hashbased signatures are digital signatures that use various forms of algorithmic encryption to establish a public key and private key pair, both using the same chosen algorithm to encrypt the signatures so that they can only be decrypted using the same algorithm.
 Elliptic curve digital signature algorithm is an approach to keypair generation that uses a group of points over a finite field to establish the algorithmic factoring of the digital signature in contrast to using discrete integers calculated from taking the root of prime numbers factored together. This approach leads to a significantly stronger key perbit.
 The Chain of PoWs problem is described as an abstract representation of the minimum length of the chain that would be susceptible to a quantum attacker’s query Q if given N queries to the QRO, as Q would have to determine the length of the chain before attempting to retarget the chain to its malicious chain.
 Quantum computing theory utilizes a combination of classical computing theory and quantum physics to establish a framework in which quantum states can be utilized to solve classical cryptography problems in a system that employs quantum entanglement to reduce latency between quantum oracles to near 0 seconds due to the nature of the shared quantum database not needing to adhere to the deadlock avoidance strategies associated with classical computing multiprocessor thread scheduling.
 Quantum Resistance efforts have produced multiple protocols that claim to have infrastructures that are capable of preventing a quantum attacker from being able to solve the most current proof being attempted by the miners on a Proof of Work chain.
 The kBerSearch problem requires that a given function is sampled according to Bernoulli distribution to determine the probability of success of finding the proof for the function in question. The researchers ask if Q has N queries, what is the probability of solving kBerSearch.

 kBerSearch is important to determine Q’s capacity to target the proper function that will be needed to inject a malicious proof to retarget the entire blockchain.
Summary
 Recording Oracle technique keeps track of a quantum adversary’s knowledge after it has interacted with a RO. This approach is meant to monitor the behavior of quantum adversaries to determine which queries are being made.
 Bitcoin Backbone Protocol states that an adversary attempting to corrupt the chain would have to generate a chain longer than the honest chain being targeted.
 Quantum adversary model is established by the researchers and assumes Q as the number of quantum queries to the QRO to then define N = sQ as the total number of quantum queries in s rounds.
 kBerSearch problem is established to show that Q must first solve which function is being executed by the honest chain, which utilizes time and energy in order for Q to gain knowledge of the state of the oracle
 Recording technique for Bernoulli distributions states that establishing the chance of success for determining the state of the oracle gives researchers the capacity to project the success of Q if given N queries in s rounds.
 Analysis of Backbone Protocol against quantum adversaries is intended to show whether, in the presence of a quantum adversary that has bounds on their computational hashing power, the Backbone’s time for safe settlement would be short enough to prevent the quantum attacker from solving the next blockhead first.
Method
 The researcher established base variables by which to define the parameters being measured in the analysis
 The researchers define the problem of the “ChainofPoWs” which states that the Quantum adversary will have to produce a chain longer than that of the honest chain in order to successfully overtake the block production at the next round
 The ChainofPoWs problem is used as the foundation to establish five theorems and thirteen lemmas describing the parameters and bounds placed on the quantum attacker within the system designed.
 The researchers assert that the examples used are for the sake of representing the most simplistic example, and aren’t meant to be an exhaustive set of lemmas.
 The bounds and parameters established within the paper are meant to represent real world limitations with the understanding that no quantum attacker will ever be able to have unlimited time, and thus it is logical to examine the number of queries in the context of an asymptote that will forever have an upper bound on the number of queries that is possible to execute which it will never achieve.
Results
 The researchers were able to provide a comparison between classical adversaries, restricted quantum adversaries and the most general quantum adversaries against the Backbone protocol.
 The Honest Majority expresses the relation between the honest hashing power on the chain and the hashing power of the adversary
 The probability that one honest party finds a PoW in a round is f = npq, with the current honest majority condition represented as Q ≤ n · q · p 1/2 · O(1) meaning each quantum query is worth p1/2 classical queries.
 In assessing the classical adversary compared to the restricted quantum adversary, the number of rounds required to reach safe settlement is the same in presence of both adversaries.
Discussion & Key Takeaways

While the researchers had shown that there was an increased settlement time and an increase in cost in an initial assessment of settlement times, the addition of the kBerSearch problem as part of the bounds limiting the attacker resulted in the researchers showing that a restricted quantum attacker would not increase the number of rounds needed for the Backbone protocol to reach safe settlement.

This effectively shows that the honest majority can reach safe settlement before the quantum adversary can solve the kBerSearch problem and generate a longer chain to replace the honest chain.
Implications & Followups
 The research results indicate that the current Bitcoin Backbone protocol will be resistant to quantum adversaries with a bound on their queries in a specific type of attack.
 This paper does not explore the concept of the quantum attacker using different types of attacks in tandem with the attempt at overturning the oracles, but the researcher asserts this paper’s framework is meant to represent the most basic and direct targeted attack.
 The paper indicates that a quantum adversary would have a higher probability of success the more queries against the honest chain were run to be used as projection data to retarget the attack.
 In the context of the increased probability of success that comes with increasing queries; a quantum adversary will have to be able to calculate the current position of the chain, calculate the problem, and solve the problem before the chain can reach safe settlement which still represents a limited window of attack and by proxy makes it more difficult to correctly time an attack to start at the exact moment the next block starts being produced.
Applicability
 While this work is not meant to assert that quantum attacks are no longer a threat, it presents a logical framework in which quantum attacks are not as much of a looming threat as was presented in the abstract concept of a quantum attacker.
 As the researchers have expressly stated the theorems are to be limited in their application for projections. The frameworks presented in the paper will be useful to inform development of quantumresistant protocols in the future to understand how to further facilitate easy settlement between honest parties. It will also make it more difficult for quantum adversaries to determine the current state of the chain to make the gap between the search time and the settlement timeweighted towards settlement.