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.
4 Likes