Can your bitcoins be stolen by a quantum computer? 

The short answer: no... at least, not right now or anytime soon.

However, you’ve likely come across clickbait articles that describe the doomsday scenario where quantum computers get so advanced they will “break” Bitcoin. This is yet another topic, much like “mining centralization”, which critics use to try to spread FUD without telling the full story or acknowledging how realistic various scenarios are.

Quantum computers do in fact pose a potential threat to Bitcoin’s security in the distant future, but there are engineering solutions that can keep Bitcoin secure long-term. In this blogpost, we'll explain the real threat of quantum computers, the prospect of quantum computers pulling off a 51% attack, and how Bitcoin can continue to exist even after significant advancements in quantum computing take place.

What is SHA-256?

Let’s start with some important background information.

If a quantum computer were used to 51% attack the Bitcoin network, what it would actually be doing is trying to break the underlying hash algorithm used in bitcoin mining, SHA-256. 

In simple terms, SHA-256 is a mathematical operation used for storing information on the internet securely and privately. How and why SHA-256 works is best left for a different article, but just know this algorithm is used in countless important applications throughout the web including protecting passwords and securing communication between websites and servers.

The point is that a quantum computer breaking SHA-256 would have huge implications throughout the digital world, not just with Bitcoin. Government agencies, financial institutions, and large online retailers, among others, would be facing a similar situation as Bitcoiners.

However, we want to understand the implications specifically for Bitcoin, which means we have to look at the ways that SHA-256 is used in the Bitcoin network. There are two of these:

1. Mining uses SHA-256 as the proof of work algorithm
2. Bitcoin addresses appear on the blockchain as SHA-256 hash outputs

Attacking Bitcoin Mining 

Bitcoin mining is performed by specialized hardware, called ASICs (Application Specific Integrated Circuits), which plug random input values from a huge set of possibilities into the SHA-256 hash function in hopes that an output value will be below the difficulty target. Finding such a value allows the miner to propose a block and earn the block reward with newly issued bitcoins. 

Currently, there is no way to strategically narrow down the search space of random input values. Every input is equally as likely to produce a valid output as all the others. Hence, miners are simply plugging in random values in hopes that they’ll eventually find one that meets the difficulty target. This property of the SHA-256 hash function is commonly called “puzzle friendliness.”

In the case of a quantum computer, it is actually possible in theory to narrow down the vast search space of random inputs, to the point where it would take quadratically fewer (basically, a lot less) hashes than is needed by a typical miner. This can be achieved using a Grover search algorithm. 

The catch is that using the Grover algorithm requires a lot of processing power. So much so that the speed and efficiency at which a quantum computer would operate for this application is still inferior to that of today’s ASICs, negating the quadratic speedup that could occur with the Grover algorithm.

To put some actual numbers on it, we can reference the work of Divesh Aggarwal, Gavin Brennen, Troy Lee, Miklos Santha, and MarcoTomamichel in their research article analyzing quantum attacks on Bitcoin. They calculated that a quantum computer at the time in 2018 would be about a thousand times slower than a single Antminer S9 with a hashrate of 14 TH/s. 

While advancements in quantum computing are happening quickly, so are advancements in ASICs. Today’s top-performing ASICs produce roughly 100 TH/s of hashrate, over 7x as much as the Antminer S9’s hashrate. Meanwhile, Bitcoin’s total network hashrate has climbed from 20 EH/s in 2018 to 150 EH/s at the time of writing.

In other words, quantum computers cannot be used to competitively mine bitcoin, and that isn’t going to change anytime in the foreseeable future.

Attacking Bitcoin Signatures 

Moving away from mining and looking at wallet security, this is where quantum computers pose a more realistic threat. Bitcoin uses digital signatures as a way for users to securely send bitcoins to one another. Every time you transfer some bitcoin, your wallet verifies your signature which comes from the private key associated with your public key. (Not your keys, not your coins.) This entire process is typically handled behind the scenes via your wallet.

The method used to create these signatures are based on the Elliptic Curve Digital Signature Algorithm (ECDSA) — specifically the secp256k1 curve. For decades, this specific curve has been deemed safe from being reversed. However, it’s a known possibility that it could theoretically be broken in the distant future. In other words, a quantum computer could derive a wallet’s private key from a public key, rendering the signature scheme insecure and making bitcoin wallets vulnerable to theft.

However, a really important caveat here is that your public key is only revealed when you spend bitcoin from legacy P2PK addresses. Once it’s revealed in the presence of a quantum computer, the address is no longer safe and shouldn’t be used again. Regardless of address type, you can already make your personal funds more secure against future quantum computers by never reusing a wallet address when you spend coins.

In more technical terms, this means that you would always send your UTXO change to a new address instead of sending it back to the same address. This is considered best practice already, even without considering quantum computers. In case you aren’t familiar with UTXOs and change, you can learn about them in our article explaining Taproot and on-chain privacy for beginners. 

When Will Quantum Computers Pose a More Serious Threat?

Now the big question is: when might quantum computers actually be a threat to SHA-256 or ECDSA encryption?

As of late 2020, IBM is boasting a 65 qubit quantum computer, while about 1500 qubits is the estimated requirement to hack Bitcoin private keys. However, today’s quantum computers have impractically-high error rates and can operate only in lab conditions at temperatures near absolute zero.

Estimates on when quantum computers could achieve the necessary qubit processing power to attack Bitcoin range from several years to a few decades. The most optimistic estimates claim that a quantum computer could exist by 2028 that can break the signature scheme in less than 10 minutes, but more realistic estimates are that such advancements will be 10+ years out.

The significance of the time that it takes to break the encryption is that public keys are revealed when transactions are broadcasted to the mempool, even before they get added to the blockchain. If an attacker could reverse the signature and get the associated private key during this window before the transaction gets included on-chain, they could then broadcast a higher-fee transaction sending the coins to themselves instead.

The scenario described above is the main reason why avoiding address reuse without changing to a different encryption algorithm isn’t a foolproof solution long-term. That being said, the threat of quantum computers is not immediate and Bitcoin developers have lots of time to think about ways to mitigate possible vulnerabilities.

Defending Against Quantum Computers

One of the most obvious ways to maintain Bitcoin’s security in a future with more powerful quantum computers would be to upgrade the Bitcoin network to a stronger form of encryption —  often called "quantum-resistant encryption". Some alternative quantum-resistant encryption algorithms already exist, and the main selection criteria for developers would be to use one which is efficient and wouldn’t be memory intensive. 

How this upgrade would be introduced is subject to debate, but one method would be through a soft fork upgrade. This results in the creation of a new address type which users would send their bitcoins to in order to achieve quantum security. Users who don’t send their coins to the new, quantum-resistant wallet type would leave their funds vulnerable to theft.

TL;DR: Is the quantum attack pure FUD?

In terms of the common FUD about quantum computers "breaking" Bitcoin, here are the two key takeaways:

• Quantum computers cannot mine Bitcoin more efficiently than ASICs
• Advancements in quantum computing might eventually pose a threat to Bitcoin, but there are viable engineering solutions to mitigate the threat and plenty of time to work on them

‍