Is Quantum Computing Threatening Blockchains?

Soooo… two of your favorite buzzwords just collide…

IBM Q System One

Talking about noise surrounding quantum computing and blockchain — I have seen my beloved city of Cleveland preparing for its comeback as the leader of blockchain technology (the Blockland, as they call it); the word “quantum” showing up on almost every tech prediction list of 2019; The CSO of China’s insurance giant Pin’An announced that the blockchain technology is now ready for mature business application, and most recently IBM’s shiny sci-fi looking Q System One, reportedly the first quantum computer for commercial use…

I don’t have to say more to convince you just how much hype we all devote to quantum computing and blockchains. However, so far we have been talking about them separately. So I thought it is time to follow our sensational instinct and combine these two buzzwords together, hence the question: Is quantum computing threatening blockchains?

Quantum Computing and Blockchains, Explained in 60 Seconds

Before I dive in, a bit background knowledge (as we always do in history to make our paper longer).

Quantum computing operates on quantum bits, or qubits. Bits are the basic unit of information that a computer takes when performing a computation. Traditional binary computers have bits that store data as either 1s or 0s. However, qubits can exist as 1s and 0s simultaneously, thanks to a special quantum property called “superposition.” This means that a quantum computer can compute much faster than a regular computer by processing information stored on qubits.

Blockchain has a lot of components to it, but only two things are relevant to our discussion here:

1. Cryptocurrencies, the most popular blockchain application, relies on private key encryption for secure transaction. For example, Annie wants to spend 10 bitcoins. She can do so by accessing her digital wallet with her private key (any random series of 256 bits number). The private key is only known to Annie, and she can use it to generate a public key with the Elliptical Curve Digital Signature Algorithm. The public key is known to anyone on the blockchains and is used to verify that Annie’s transaction information is not tempered during the transaction, (for example changing 10 bitcoins to 20). The important thing here to note is that because ECDSA is not easily reversible, one cannot guess Annie’s private key from her public key. The generation of the public key from the private key is a one-way street.
2. Transaction information is not written on blockchains in plain binary codes. They are instead subject to hash functions, which take data of any length and give back a value of finite length, aka, a hash value. This process is called “hashing”, and it is used not just in blockchains but in almost all information security scenarios such as verifying the integrity of messages or generating digital signatures. One of the biggest advantages of the hash function is that if a small change is made to the original file, the hash value would change dramatically. Transaction information stored on blockchains is usually hashed several times, so to make any change to that information would mean to go back and change every hash value generated along the way. The computation cost is simply so high that it is unrealistic to temper the information.

Bottom line 1: Both the hash function and the private key encryption are common cryptological schemes used in modern digital information security systems. Both are based on computationally hard to solve mathematical problems or computationally hard to reverse algorithms. This means they are not unsolvable or irreversible, but it may take millions of years to break them.

The Long Existing Tension Between Machines and Mathematics

Now, the possibility of quantum computing threatening blockchains essentially lies in one general thesis:

Increasing computing power v.s. Encryption technology based on difficult-to-solve math problems

Bottom line 2: the faster a computer is able to compute, the faster it will solve a math problem and the less secured the current encryption technique would be.

This thesis has been in existence since several ingenious researchers in the 1950s tried to build an automated proving machine that was based on a set of axioms provided by Bertrude Russell and Alfred Whitehead to prove *allegedly* (ahem Gödel) all mathematical theorems. A lot of different designs were proposed since then to make the proving machine more efficiently, but there were limitations:

Brute force deduction (providing the machine with all axioms and rules of inferences so they can follow every path and deduce everything) had to be combined with some sort of human insights (shortcuts to proofs —e.x. use axiom A whenever you see statement B) because the constraint on time and resources dictates that the machine cannot get to the correct results in any foreseeable finite amount of time before it drained all energy available to power it.

In other words, the computing power of traditional computers, be that in the 50s or now, is not great enough to support the brute force operation needed to follow pure deduction.

However, as we have seen, quantum computing can very likely be the solution to limited resources and time by dramatically increasing computing power and shortening computing time. (This is not to say that quantum computers are not constrained by the finite amount of time and resources of course… what does?)

Quantum Computing V.S. Private Key Encryption

So all the above is about proving a mathematical theorem. What about solving an arithmetic problem that was previously deemed as difficult to solve, such as factoring two large prime numbers? You guess it. With the development of a quantum algorithm, factoring a 300 digit number into two prime only takes less than 1 second, in comparison to 15,000 years with the best classic algorithm.

Now hard arithmetic problems of this kind are important because they are the backbone of the current digital encryption schemes. From online banking to e-commerce, a secured transaction essentially means that they are encrypted by these math problems to make sure that nobody can figure out the answers fast enough to steal information.

However, in 2016 the National Instutitue of Standards and Technology issued a report warning that large scale quantum computer would render all common cryptographic algorithms compromised, including those hard math problems we just talked about (RSA, DSA), some hash functions, and ECASA, which, if you recall from the previous section, Bitcoins use to generate public keys from users’ private keys.

Report on Post-Quantum Cryptography, NIST, 2016

This means that the previous one way street from private key to public key that Annie, our bitcoin protagonist, secured her transaction with is no longer secure. Jay, the malicious antagonist who happens to have a quantum computer, can figure out Annie’s private key from the public key, access her digital wallet, and spend all her bitcoins on crypto kitties!

However, this threat is not blockchains specific. It is rather cryptocurrency specific, since the latter is essentially like any other financial vehicles that are secured by the private key cryptography and therefore become vulnerable under quantum attack. In other words, the emergence of quantum computing poses threat to the entire communication digital infrastructure, impacting both governmental agencies and mobile phone users alike.

But what about hash functions? Turn out that hash functions are very difficult to reverse. Even though one hash algorithm is broken, such as what Google did to SHA1, you can always increase the number of digits in the hash value to increase its security. FYI, the bitcoin network runs on SHA256, that is 256 bits in the hash value.

However, there is one caveat: during the mining process to find the desirable hash value to verify a block, it could be the case that a miner with a quantum computer has an upper hand against others using regular computers. This is because a quantum computer can compute fast enough that it will find the desirable hash value faster. However, this threat is just as real as using any existing crazily expensive, carefully guarded supercomputers to mine cryptocurrencies — it is possible, but unlikely.

If you read thus far, you will probably be disappointed in the fact that there is no blockchain specific security threat that quantum computers could pose yet. However, the change that quantum computing may bring will radiate across all digital infrastructure, and the blockchain technology needs to prepare itself for it.

The historian side of me would very much not mind seeing the deployment and popularization of commercial quantum computers. If that really happens, there could be an infrastructure revolution that affects not just digital encryption, but also data storage and processing, AI training, information transmission and much much more.

I will write more on this if there is ever another polar vortex hitting Chicago and my school decides to give me another day of break.