Quantum Computers Do Not Pose an Existential Threat to Bitcoin (Part 1)

This content is for informational purposes only, you should not construe any such information or other material as investment, financial, or other advice. Nothing contained in this document constitutes a solicitation, recommendation, or endorsement to buy Bitcoin.

Because I am personally invested in Bitcoin, any current or future vulnerability in the Bitcoin network intrigues me. As a result, I am self-incentivized to learn and research possible attack scenarios and potential dangers to the Bitcoin network. If any single scenario poses a somewhat realistic and existential threat to Bitcoin that couldn’t be mitigated – it could be rendered worthless.

Beware Bitcoiners, the Quantum Ghost is coming.

A vastly simplified and shortened analysis of the quantum computing threat follows. To learn more about the scenarios described below, check out the sources linked at the end. If you are an expert on this particular topic, please reach out to me so this article can be continuously improved upon. I’m nowhere near being a quantum computer expert, but that doesn’t keep me from at least trying to understand this threat scenario.

Some of the statements I’ve come across quite often in regards to quantum computing and Bitcoin are:

• “Quantum computers will make Bitcoin obsolete.”
• “Quantum computers will mine all remaining Bitcoins.”
• “Quantum computers will crack Bitcoins cryptography.”

The rationale goes something like this:

Bitcoin is a cryptocurrency. A cryptocurrency has something to do with cryptography. Quantum computers are faster than anyone can imagine and they will break cryptography sooner or later. Therefore, they will break Bitcoin.

This sounds somewhat reasonable, so let’s dive in to learn more.

But first, what are quantum computers?

Quantum physics is the study of structures smaller than atoms. The conventional principles of physics are thrown out the window while studying subatomic structures, and novel phenomena on a microscopic level begin to emerge. Quantum computers exploit those properties to perform calculations faster than even the most powerful supercomputers.1

The computers we use today store information in the form of bits (with each bit having two possible states 0 or 1), while a quantum computer encodes information in far richer states called qubits (which can be in any state on the surface of the sphere below).2

Due to a phenomenon known as quantum superposition, qubits can exist in numerous states simultaneously. This feature increases their speed exponentially when compared to binary computer systems.3 Generally speaking, the more qubits a quantum computer has, the stronger it will be (more qubits = more computing power). Qubits vary in quality, which will be discussed further down the article. Quantum computing becomes a fascinating topic to learn about when looking into the opportunities: Once fully developed, it will act as a catalyst for scientific discovery and innovation, transforming areas such as energy storage, chemical engineering, material science, drug discovery, and machine learning.4

Second, how far are quantum computers developed?

In 2019, Google claimed to have achieved quantum supremacy, a long-awaited milestone for scientists worldwide.5 They revealed that they had built a system that could do a calculation that would take a traditional computer 10,000 years in just over three minutes. Although groundbreaking, it remains to be seen whether a quantum computer can tackle a valuable task that cannot be accomplished in any other way.6

Right now, the most advanced (publicly known) quantum computer of IBM can reach 127 qubits, but the quantum states are challenging to control.7

While I was searching for the most powerful quantum computer that is publicly known today, I was quite surprised to stumble upon the company D-Wave which seems to be achieving more than 5,000 qubits with its quantum annealers.8 In summary, these quantum annealers are not capable of running the algorithms needed to “break Bitcoin”, so they are irrelevant for this article. Instead, it is “universal gate quantum computing” that matters in this context.9

The timetable for quantum computing progress is highly debated by experts. The threats and uncertainty potentially resulting from quantum computing, according to some, will be decades away due to its complexity. Others, such as Alphabet CEO Sundar Pichai, believe quantum computing will break encryption as we know it within the next three years. This year, IBM plans to deploy a 433-qubit quantum processor, followed by a 1,121-qubit Condor-class quantum processor in 2023.10 The progress in quantum computing is, as so often in the world of technology, progressing exponentially.11 The graph below illustrates a prediction of qubit advancement for the next decades. The research article is from 2018, and we are currently trending between the two blue dotted lines.12

Prediction for the number of qubits – Source 12

Note that the y-axis is scaled logarithmically – by 2025, quantum computers with 10,000 qubits could be a reality. In 2040, quantum computers could have 10 billion qubits.

Engineering, building, and programming quantum computers are very complex, to say the least. They are extremely sensitive to their surrounding environment, hampered by noise, defects, and the loss of so-called quantum coherence. The slightest vibration, temperature variation, or electromagnetic wave destroys these computers’ quantum advantage.13 Quantum computers are not universally better than classical computers, which will be immediately relevant to the topic.14 But this exciting new technology field definitely doesn’t lack funding, as seen in the graphic below.15

Government spendings on quantum research – 2021 – Source 15

The graphic only contains public funding.

Private capital flowing into this field has been increasing to an all-time high recently. Investors are anticipating the chance to earn good money with quantum applications in the future.16

Quantum computing advancement forecasts are frequently based on commercially available quantum computers and do not consider covert advances. So further down this article, we will play devil’s advocate and include a scenario where a supreme quantum computer appears out of the blue tomorrow morning.

Third, what are the potential quantum computing attack vectors regarding Bitcoin?

Estimates to penetrate some of Bitcoin’s current quantum vulnerabilities vary but start at around 1,500 qubits.17 It is important to note that once a quantum computer reaches 1,500 qubits (which could be the case quite soon), that doesn’t simply mean the Bitcoin network is in danger.

Theory and practice are often far apart: Today, the vast number of qubits are used for quantum error correction schemes so that only relatively few qubits remain for actual computation.18 The number of qubits achieved by the newest quantum computers refer to physical qubits, which might sound wonderful, but means almost nothing. What matters are logical qubits which are highly dependent on the error correction of the underlying physical ones. Quantum computers may have 1,500 qubits in the next few years, but only two logical qubits.

It’s difficult to estimate a specific qubit threshold will break Bitcoin since it depends on the quality and precision of the qubits. Keeping this in mind, Bitcoin does currently have certain vulnerabilities when it comes to quantum computers.

While the SHA-256 hash functions that Bitcoin uses for mining and the creation of new Bitcoin addresses are sometimes cited to be a vulnerability, it is, in fact, incredibly safe – even with severe quantum computer advancements. SHA-256 is theorized to be quantum-safe (collision-resistant).19 But if it weren’t – when the time comes, the cryptography for Bitcoin can be adapted and changed to be quantum-resistant. There is already more robust cryptography available; they are just seen as overkill so far: SHA3 with 384 or 512, for example. Furthermore, a quantum computer breaking SHA-256 would have huge implications throughout the digital world, not just for Bitcoin. Government agencies, financial institutions, and large online retailers, among others, would be affected.

But there are other and perhaps realistic attack vectors a quantum computer could go after regarding Bitcoin. The consensus among experts seems to be that there are three categories of vulnerabilities to consider:

1. Elliptic Curve Cryptography (ECC) and Public Key Unveiling
2. Quantum computers mining for Bitcoins
3. The Quantum Surprise – Sudden, secret, and massive quantum computing advancements

Attack vector 1 – ECC and Public Key Unveiling

Asymmetric cryptography’s security is based on a mathematical principle known as a “one-way function.” The public key can be easily derived from the private key, but not the other way around. That isn’t to say that deriving the private key from a public key is impossible with a sufficient quantum computer. Two major quantum algorithms that threaten the current state of cryptography have already been developed: Grover’s and Shor’s algorithms.20

Anyone with a sufficiently large quantum computer could theoretically derive the private key from a known public key and thus, falsify any digital signature. This scenario seems to be the most realistic and vulnerable one. It basically boils down to the unveiling of public keys (a quantum computer could then theoretically “calculate” the private keys), which can occur in different scenarios:21

1. Pre-2010 Bitcoin addresses (P2PK)
2. Re-used Bitcoin addresses (2010 onwards – P2PKH)
3. Unprocessed transactions

We will distinguish between these three cases to answer attack vector 1 in more detail. Each one is affected differently by a quantum computer (other cases of known public keys, such as with lightning payment channels or Bitcoin forks, are not included in the analysis but wouldn’t have a significantly different outcome).

Attack vector 1a – Pre-2010 Bitcoin addresses (P2PK)

In 2009, the most common address type was ‘pay to public key’ (P2PK). It is the initial script model used in the Bitcoin network to send and receive transactions in the early days.22

Many of Satoshi Nakamoto’s original coins are still “stored in this address” type. Anyone can obtain the public key from a P2PK address. The private key could then be derived from these public keys using a quantum computer. This would allow a quantum computing attacker to spend the money associated with that address.

Attack vector 1b – Re-used Bitcoin addresses (2010 onwards – P2PKH)

The public key is not immediately revealed by the address with ‘pay to public key hash’ (P2PKH), introduced in 2010, but hidden behind two cryptographic hashes.23

It is only exposed when the owner initiates a transaction. The majority of coins have been held in this form of address. This means that the public key is unknown, and a quantum computer cannot calculate the private key if funds have never been moved from a P2PKH address. Today, most Bitcoin wallets are programmed to avoid address re-use as much as possible. Always using fresh addresses is already the suggested best practice in Bitcoin, but this is not always followed.

Any address that has Bitcoin and for which the public key has been revealed is potentially insecure in the presence of a quantum computer.24

Since 2014, the number of Bitcoins kept in re-used P2PKH addresses has steadily decreased. Estimates put the total amount of Bitcoins potentially vulnerable to a quantum attack between 3,925 to 4 million (~21% of current supply).26

Attack vector 1c – Unprocessed transactions

The common issue that cryptocurrencies have is the need to disclose the public key and signature to execute the unlocking script to prove ownership and move funds.27 When a user spends Bitcoin, they are broadcasting their public key to the network. All information a quantum computer needs to fully impersonate the owner of an address has been revealed by initiating the transaction.28 A quantum attack can occur after a transaction has been broadcast to the network but before it has been written on the blockchain.

To do this, the attacker would need to:29

a) run Shor’s algorithm to derive the private key from the unveiled public key, and
b) create, sign, and broadcast the conflicting transaction to their own address, and
c) pay a significantly higher transaction fee to (maybe) overtake the original transaction.

All of this would need to be well-timed and finished in a relatively small time window. This attack is often seen as the most severe attack because it wouldn’t “just” affect a few million Bitcoins (attack vector 1a and b) but rather every Bitcoin transaction.30 The number of qubits needed to crack the signature within 30 minutes could be done with a minimum of 485,550 qubits (when working efficiently and calculated optimistically).31 With the most (over-)confident predictions, this could be achieved roughly five years from today. This attack, when practical, would indeed render the current Bitcoin system highly insecure.32

You liked the first part of this article? Look forward to the second part!

You can get more information about the author -Michael Weymans – here on LinkedIn. 

Original source: https://blog.bitbeginner.com/p/quantum-computers