logo academy

Do quantum computers threaten Bitcoin’s security?

August 1, 2022

11 min

Do quantum computers threaten Bitcoin’s security?
Expert

Bitcoin’s blockchain is protected by walls of cryptography, impregnable by classic computers. However, a new technology is arising: quantum computers, machines based on the subatomic states of matter. Is ‘quantum supremacy’ a threat? Let’s find out what quantum computers are and whether they are a risk to the blockchain

What is a quantum computer?

The growth in computational power, i.e. the ability of devices to perform calculations, is proportional to the increase in technological performance and potential. According to Moore’s law, in fact, the complexity and miniaturisation of technological devices doubles every 18 months, thus increasing their computing power.

A concrete example of miniaturisation concerns microprocessors, which have seen the number of transistors that can be integrated on the same chip double. Thus, the central processing units (CPUs) and graphics units (GPUs) of computers went from single 4-bit processors (Intel 4004) to 64-bit multi-core solutions in less than 40 years.

Our quad-core computers, however, avoid a problem without solving it: creating even smaller microchips, over time, has become very difficult, so to increase computing power, several processors are used in parallel

Transistor

Electronic semiconductor device used to control current in analogue and digital circuits: it amplifies or switches (like a switch) electrical signals and power.

As an alternative, computer engineers have proposed a paradigm shift: building a new generation of computers by exploiting the properties of quantum physics. In a nutshell, this technology makes use of the quantum states of subatomic particles, units in the order of magnitude of electrons and protons, sometimes called ‘quanta’. Their probabilistic nature, in particular, is the key to increased computing capabilities, let’s find out how. 

We know that the unit of information of electronic computers is the bit (binary digits), the alternative representation of two states through the digits 1 (true/on) or 0 (false/off). Now, let us jump into the quantum realm: the information units of quantum computers are qubits (quantum bits) and they associate data with the quantum states of matter, thus achieving immense computing power. At the same instant, a subatomic particle exists in multiple spatial configurations, positions and velocities, as it is enveloped by ‘probability clouds’, so that it has different values at the same time.

Simplifying greatly, qubits can take on the values of 0 and 1 simultaneously, along a probability spectrum (e.g. 30% of 0 and 70% of 1). Let us take an example: 4 bits can only exist in one of 16 combinations, while 4 qubits can simultaneously represent all 16 values, i.e. correspond to all numbers from 0 to 15. Quantum computers exploit the superposition of the qubits’ states: they try to solve a problem in several ways, processing several data ‘together’, before a (probable, but never certain) solution is ‘fixed’. The final state of the qubits, in fact, will be ‘fixed‘ and measured in bits: following the calculations, the quantum algorithm will return a string of 0s and 1s, comprehensible to any computer.

Ultimately, how does a quantum computer work? Schrödinger‘s paradox is the perfect metaphor: a cat is locked in a box and its survival depends on the decay of a radioactive substance. Since this event is random and probabilistic, it is not possible to conclude with certainty whether the cat in the box is dead or alive unless you open it. Until the state of the system is observed, in fact, it will be in a superposition of states: the cat is both dead and alive, both 0 and 1.

Now, imagine that the box is a quantum computer, isolated from external factors, and replace the cat with subatomic particles: the qubits will rely on the superposition of their quantum states to represent, simultaneously, several values and conduct calculations in parallel, before the box is ‘opened’ to discover the final result.

Furthermore, measuring the state of one qubit (i.e. defining whether it is 1 or 0) will consequently determine the values associated with some others, subtracting them from the probability of quantum states: two particles that originate at the same instant or interact, remain connected even at a distance of space and time, in such a way as to influence each other’s parameters (such as spin or polarisation state). This phenomenon is called quantum entanglement, or quantum correlation, and it exponentially amplifies the computational capabilities of quantum computers: recording the values of a single qubit transforms the states of all the qubits connected to it into ‘binaries’ (0 or 1), so that a lot of information can be discovered with a single observation.

Imagine two qubits in entanglement as marbles of different colours, one red and one green. Assigned randomly to two friends, so that they do not see the colour of the marble they received, they say goodbye to each other and go home: as soon as one of the two, curious, discovers which one he got, he will also know the colour of his friend’s marble, despite living a few blocks away.

If you understand what a quantum computer is, you will have already realised that it could have implications for complex cryptographic calculations in general, but also specifically for blockchain technology. In particular, we know that to produce Bitcoin blocks, miners need a lot of computational power in order to solve cryptographic ‘puzzles’. The security of the blockchain is based on the impossibility of deciphering its cryptographic codes, essentially due to a lack of time and powerful enough hardware. A quantum computer, however, can overcome these limitations: by performing calculations in 36 microseconds that a supercomputer would have solved in 9000 years, it asserts its quantum supremacy. So, could a quantum computer threaten the immutability and security of the blockchain?

Quantum supremacy

Quantum supremacy is the ability of a quantum computer to perform a task significantly faster than a classic computer or supercomputer, sometimes performing calculations in a matter of seconds that would take millenia for a traditional computer to solve

Quantum computers vs Bitcoin

Let’s step out of the quantum realm for a moment: is Bitcoin‘s bit technology really at risk?

Let us compare the security of Bitcoin and the computational power of a quantum computer to understand the order of magnitude.

Bitcoin has two main cryptographic layers:

  • Secure Hashing Algorithm, SHA-256: The Proof-of-Work Algorithm Behind Block Production;
  • Elliptic Curve Cryptography, ECC: the curve on which the production of public and private keys (also of other cryptocurrencies, such as Litecoin) is based.

The SHA-256 function, as is suggested by the acronym itself, always produces strings composed of 256 bits, regardless of the input given to it. Most importantly, it always returns the same output if the input data does not change. In particular, SHA-256 produces the hashes that form the basis of Bitcoin’s blockchain encryption: each block is represented by an alphanumeric string that encodes any information it contains, such as senders and recipients of transactions. Each hash also contains part of the hash of the previous block, thus making the blockchain immutable, as we have explained here.

The component of the hash for which miners compete is a binary sequence called a ‘nonce‘ (number used once): random and varying according to time, it reflects the difficulty of mining and consists of ‘only’ 32 bits. Whoever first finds the winning string of 0s and 1s has the authority to produce the next block of Bitcoin and receives the corresponding reward. An algorithm produces the nonce in such a way that it can be found within 10 minutes by the mining hardware: essentially, they brute force test each combination until the correct one is found. A quantum computer would have an almost unfair advantage over even the best of ASICs: it would only need 32 qubits to simultaneously represent all possible combinations, including the ‘golden nonce’, i.e. the missing ‘piece’ to the puzzle of a Bitcoin block.

Cryptographic keys, used to receive, send cryptocurrencies and approve any kind of operation on the blockchain, are instead produced on the basis of the ECC curve; a function of the type P=k*G, where P is the public key, k the private key and G a constant. This type of cryptography is secure because no classical computer has the computational power to derive the private key from the public one: a puzzle called discrete logarithm. Perhaps, however, a quantum computer could solve it. The ECC on which Bitcoin is based is called secp256k1 and, in fact, generates keys of 256 bits: a quantum computer could theoretically represent all the private keys of Bitcoin’s network with 256 qubits!

Considering that the most powerful quantum computer is the IBM Eagle, equipped with a 127 qubit processor, it seems that for now Bitcoin’s cryptographic keys are safe, but the blockchain could be hacked and rewritten with such computational power. This prospect becomes more concrete when we consider that IBM’s roadmap envisages the production of an 1121-qubit quantum computer in 2023 and that the IBM Quantum System One, available to all for use in the cloud, has a power of 27 qubits, soon to be upgraded to 65 and then 127.

So, is Bitcoin’s blockchain really in danger? Not exactly: even quantum computers have certain limitations and, in any case, ‘quantum-resistant‘ cryptocurrencies exist; let us find out together why quantum computers do not really threaten the security of Bitcoin.

Is Bitcoin in danger? The limits of quantum computing

Quantum computers, as we have said, exploit the superposition of states and the entanglement of subatomic particles to conduct their calculations through qubits. Qubits, however, are very unstable units: they are often pure energy, such as photons, ‘packets’ of electromagnetic energy. This instability heats up quantum computing systems, which must therefore be kept at very low temperatures, close to absolute zero (-273 °C). In addition, the systems must be completely isolated to obey the rules of quantum physics: any external interference would ‘open’ Schrödinger’s box and determine the state of the cat-qubit, causing useful information to be lost to the calculation process. This is a very difficult event to prevent, called quantum decoherence, a consequence of Heisenberg’s uncertainty principle: it is impossible to know the details of a system without disrupting it.

Finally, precisely because of this instability, quantum states are very difficult to record by quantum algorithms, which must therefore always work with a margin of error. In fact, 32 qubits can never determine the nonce of a hash with certainty!

How to mitigate these possible deviations in the result, essentially due to the probabilistic nature of quantum particles? Add more qubits!

Actually, research by the University of Sussex has estimated that, considering the computational errors of quantum computers, 1.9 billion qubits would be needed to break Bitcoin encryption in 10 minutes, 317 million for a hack in one hour, and 13 million if the attack were to take an entire day. Encouraging numbers: innovation is light years away from creating such powerful quantum computers. Moreover, in the meantime, the blockchain could also implement better cryptographic mechanisms.

By strengthening the encryption of Bitcoin’s blockchain, the progress of quantum computers could be rendered futile. For instance, by progressively lengthening the hashes and cryptographic keys from the current 256 bits, the number of qubits needed for the hack would grow to infinity. Quantum computers could thus chase classical computers forever: an eternal marathon, as in the Achilles and the Tortoise paradox.

We mentioned quantum-resistant solutions earlier: post-quantum cryptography can protect classical computers from the computing power of quantum computers through advanced mathematical mechanisms. Examples of this are lattice-based cryptography, cryptographies based on multivariate equations or elliptic curves; and isogenic cryptography. Currently, there are already projects of this kind, such as the Quantum Resistant Ledger (QRL) on Ethereum, which is, however, still under development. Alternatively, blockchain technology could in turn exploit quantum computers to encrypt data on multiple levels, thus both producing the blocks and creating the cryptographic keys: fighting fire with fire.

Related