Is Quantum Computing a Real Threat to Bitcoin?

Quantum Computing

Bitcoin miners use their computing powers to solve cryptographic puzzles which, in turn, build up the blockchain by adding blocks of transactions. This process is fundamental to how Bitcoin transactions are authorised in the absence of a central authority, although the energy consumption involved has raised concerns.

Now a new threat to the blockchain is on the horizon. Quantum computers, could, with their overwhelming computing power, crack the public key encryption that determines the relationship between a public and private key.

Background to Quantum Computing

In a classical computer all data—text, images, even audio—is stored as sequences of binary numbers. In a binary system every piece of data stored or processed can only take two values “1” or “0.” Early computer pioneers used this binary system because it was the only practical solution given hardware based around simple on/off switches (transistors).

Modern computers may seem incredibly complex, but they’re built from many millions of these simple on/off building blocks.

Key, though, is that each speck of data—each bit—is definitely either a zero or a one. No other states exist. And your computer is deterministic: if you ask it to perform a calculation on a particular sequence of data repeatedly, it’ll give you exactly the same result every single time.

Quantum computers, however, differ radically. Instead of working with classical bits, which are definitely either a one or a zero, quantum computers use quantum bits: qubits. Qubits are somewhat mind-bending in that they can be in an unknown, undetermined state: they can represent a one and a zero simultaneously, only actually deciding on what state they really were, after you’ve performed calculations on them.

Solving the puzzles

The crypto puzzle concept at the core of blockchain technologies is simple to explain, but time-consuming to solve: it takes the form of “I have a complex equation, and a known result – but what number would I have to have input into the equation to get that result?”

The only way classical computers can solve such a problem (and hence crack the security of crypto) is by using brute force, trying every possible input to the equation until the result comes out right. The equation has to be calculated every single time until you hit success, which is impossibly time-consuming.

Broadly speaking, quantum computers work the other way around: they can test all the possible inputs at the same time: you pick the result you wanted, and only then do the qubits—the inputs—reveal what state they needed to be in for that result to happen.

So quantum computers make it possible to search for needles in haystacks incredibly fast. Which makes them perfect for dealing with big numbers.

Big numbers

Each Bitcoin private key is a randomly generated number 256 bits long. This gives 2^256 (2 to the power of 256) possible keys, or

1,597,920,937,330,902,918,203,684,832,716,283,019,655,932,542,976 possible keys.

To put that in perspective, there are only an estimated 2^63 grains of sand on all the beaches on Earth. If each grain of sand was itself a tiny planet containing all the grains of sand on earth, there would still be more possible Bitcoin addresses than grains of sand by a gigantic number.

Brute force guessing an address using an average 2018 computer is therefore impractical, it would take astronomically longer than the age of the universe. Even using all the computing power on earth wouldn’t start to touch the problem.

So what’s the problem?

Theoretically, with enough power, a quantum computer would be able to speed up this brute force process radically. Let’s take a look at where the threat is, and how it can be mitigated:

Hash your cash

Bitcoin hashing

Both of these transforms are essentially one-way; unbreakable with current computer technology. To work backwards from them would require a brute-force approach which, as we’ve seen, is simply not practical with current computers.

Unlike binary computers however, quantum computers are potentially capable of working fast enough to break the first of these – the public/private key elliptic curve function – in a reasonable timeframe.

Researchers from Cornell are predicting that as a worse-case scenario, quantum computing could crack the elliptic curve function in about 10 minutes by 2027 [1].

However, hackers need to get to the public key to do so. As long as an address hasn’t been used more than once, quantum computers cannot similarly reverse the second HASH160 algorithm used to generate the addresses.

So, in short, as things stand, Bitcoin funds are safe from potential quantum computing threats as long as:

  • they are stored in an address that you have not sent money from (so the public key is unknown) and;
  • You only use each receiving address generated from that public address once.

So all is not lost, even if quantum computing materialises as a serious threat. Although we may have a period where we need to be very careful while Bitcoin’s algorithms are updated to mitigate this threat.

How real is the threat?

The 2027 prediction above, as with all predictions concerning Bitcoin, should be treated with some scepticism. For a start, no one is quite sure when, if ever, these computers will be produced with enough qubits to crack the public key encryption that protects Bitcoin users.

A researcher at Hebrew University in Jerusalem, Gil Kalai, has stated quantum computers cannot work, even in principle. Kalai believes that, “noise [random and unavoidable errors] will corrupt the computation.”

However, it appears the opponents of quantum computers are a minority. Large corporations such as IBM, Facebook and Google as well as governments and inter-governmental organisations such as the European Union are spending billions of dollars researching this field.

Recently Google unveiled its new quantum computing chip called the “Bristlecone” which contains a record 72 qubits. This is a significant increase from the 50 qubits achieved by IBM last year.

Putting this into perspective however, some pundits are saying that to get the ‘safe cracking’ down to under an hour a quantum machine would need to have around half a million qubits, it’s clear we have a way to go before it’s a real threat.

Meanwhile the cost of such machines means they are, for the moment at least, only available to large tech companies and governments, and large teams of physicists and engineers are needed to ensure the cooling system and energy consumption remain under control.

Will we see a quantum equivalent of Moore’s law? Gordon Moore (the founder of Intel) made the uncannily accurate prediction in 1965 that the number of transistors on an integrated circuit would roughly double every two years. This exponential growth rate has proven stunningly accurate, and has been accompanied by the exponential growth in power of conventional computers. A similar rate of growth would see us go from the current 72 to half a million qubits in around 26 years.

Possible Solutions

If it is to be assumed that quantum computing will exist in the future then the cryptography upon which Bitcoin and other blockchains rely, will eventually have to adapt.

One possible way in which this could be done is through the use of ‘Lamport signatures’, a variant on public-private key cryptography thought to be quantum-hardened. Another approach may be the nascent field of quantum cryptography. Research into other encryption systems is still ongoing with a focus on ensuring it is safe from a brute force quantum attack whilst, at the same time, not undermining the principles outlined by Satoshi Nakamoto in the Bitcoin white paper.

The CoinDesk article, The New Ways to save Crypto from Quantam  written by Alyssa Hertig discusses other possible solutions.

Many financial institutions, such as banks and stock exchanges, use the same or similar encryption to protect their data. If quantum computers are to be a threat to Bitcoin then they will also be a threat to all other institutions and programs that rely on classical cryptography.

It is arguably easier for a centralised institution to adapt and strengthen its encryption than a decentralised network like Bitcoin. The rows over Segwit and other innovations are demonstrative of the immense difficulty with the pace at which Bitcoin can change even when change is necessary.

The general reaction from the crypto community to the threat of quantum computing has been one of indifference so far, perhaps because the machines are so far from being a threat at the moment. But knowing how fast the field of computing can change, and how quickly exponential growth can creep up on us, this is an area that clearly bears keeping an eye on.

Sources

Leave a Reply

Your email address will not be published. Required fields are marked *