Research summary: Post-Quantum Security of the Bitcoin Backbone and Quantum Multi-Solution Bernoulli Search

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). Post-Quantum Security of the Bitcoin Backbone and Quantum Multi-Solution Bernoulli Search. arXiv preprint arXiv:2012.15254.

Background

  • RSA Public-Key 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.
  • SHA-256 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 m-bit 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 multi-processor system. This method of mapping networks is performed with the intent of avoiding scenarios that would create deadlock or threaten the network concurrency.
  • Hash-based 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 key-pair 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 per-bit.
  • 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 k-BerSearch 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 k-BerSearch.
    • k-BerSearch 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.
  • k-BerSearch 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 “Chain-of-PoWs” 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 Chain-of-PoWs 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 p-1/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 k-BerSearch 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 k-BerSearch problem and generate a longer chain to replace the honest chain.

Implications & Follow-ups

  • 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 quantum-resistant 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 time-weighted towards settlement.
6 Likes

What would it take to completely reassure you that the Bitcoin blockchain is quantum secure? I’m guessing that because this is all theoretical, there might be some uninvestigated avenues. Any sense of what those might be? What would it take to reassure you that this mostly safe from a quantum attack?

1 Like

Honestly, that is not even the framing anymore. The framing should be “how does a quantum attacker access a blockchain that makes its computing power useful in an attack?”

In that framing, the notion of safety is relative to the actual chance of success for a quantum attack, which no one has actually demonstrated as being “likely”. A theoretical quantum attack has to have a logical framework, or else it’s just a macguffin for a magical scenario.

People have talked about quantum computing like an attacker will just be able to “plug it into bitcoin” and overturn it. It’s no-where near that simple.

2 Likes

First of all, I do want to specifically call out how much I enjoyed that you used macguffin. A+

I wasn’t just drawn in by the use of macguffin though. I appreciate the shift in framing that you are arguing for here.

For developers with finite time/resources, having to track down every single abstract/theoretical weakness/vulnerability seems like a nightmare. In some ways, that might also be a rabbit hole for researchers as well, as there might be more immediately pertinent RQs to track down and solve.

So where is that framing point or set of criteria? Where are good starting points for “useful in an attack” that researchers or developers might use?

1 Like

So this is where the crypto-space at large has not been good about using pre-existing frameworks, where-as the auditing community has followed the established protocols concerning how to articulate risks, vulnerabilities, and likelihoods that either will be exploited.

The NIST risk management framework is the American standard across industries from which a security auditor would start their assessment:

NIST Risk Management Framework | CSRC

I realized that everyone does not follow American standards and thus everyone is not familiar with NIST.

In that regard, establishing that a vulnerability or exploit exists is different than establishing the potential for the problem to be seen in the wild. The higher the likelihood of that attack occurring, the more a security agent needs to focus on that attack to harden the system specifically against that type of attack. A common and easy to understand example would be a DoS or DDoS (Denial of Service, Distributed Denial of Service) attack. In this case, it is extremely easy and cheap to execute a DDoS, so it becomes a high risk to the organization in its ease of execution.

Conversely, an attack like a “man in the middle” attack in which nodes are spoofed to compromise the integrity of a system’s data or node structure would be potentially more damaging, but less likely to occur than a DDoS.

The issue becomes attackers rarely being so simple in their approaches, resulting in what is known as an Advanced Persistent Threat (APT).

Due to the nearly infinite number of strategies that could occur with an APT, it makes it extremely difficult to get a one-size-fits-all security regimen even though corporate scaling would demand such a tool. I think there needs to be a reframing of how we see security and fitness, in that the most likely threats always get the most capital and resources dedicated to them so that the extremely abstract attacks that are not grounded in logic do not distract from the most relevant threats.

Another framework is “Designing for the Attacker” in which the security system attempts to anticipate the easiest avenues in which an attacker could breach a system, make it easier for an attacker to go down those paths, and then utilize the honey pots as a warning system to alert the security team when an attacker or APT starts an attempt to breach the perimeter.

P.S. I am sincerely glad that someone appreciated the “macguffin” usage :partying_face:

2 Likes

I think there are some interesting parallels between this thread and the discussion @lnrdpss and I were having on the Defi Financial Crisis thread. In particular, this issue about what makes for a good study and worthwhile threat assessment.

I do want to stay a little focused on the quantum element here. You’re asking for this reframing:

As people are assessing quantum threats (maybe more in the future as opposed to right now), what do you think this paper/our experiences indicates are the most realistic and likely “in the wild” type of threats? Or maybe better questions are these:

  1. What are the characteristics of quantum attacks that we should take seriously?
  2. What are the capability that quantum “has” that we need to be considering going forward?
  3. In preparing for those types of attacks, would we have more secure networks overall?
  4. Are these so far from being achievable in the wild that we as a community can mostly ignore quantum?

Sorry about the list of questions, and they’re certainly not only targeted toward you @Larry_Bates. Analysis and prevention of attacks are of interest to most of the people here!

It will be interesting to see how this thread ages.

2 Likes