Quantum Computers Do Not Pose an Existential Threat to Bitcoin
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.
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
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
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:
Elliptic Curve Cryptography (ECC) and Public Key Unveiling
Quantum computers mining for Bitcoins
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
Pre-2010 Bitcoin addresses (P2PK)
Re-used Bitcoin addresses (2010 onwards - P2PKH)
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
Solutions for attack vectors 1a and b
One option for dealing with the quantum vulnerable Bitcoins discussed in attack vectors 1a and b is to reach a consensus within the Bitcoin community and issue an ultimatum for users to move their funds to a safe address. But the private keys of many owners of ‘quantum susceptible’ Bitcoins have been lost. Therefore, these coins are not transferable and could be claimed by the first person to construct a suitably powerful quantum computer. A proposal may be that coins in unsafe addresses become unusable after a set amount of time (technically, this means that miners will ignore transactions coming from these addresses). Given the difficulty of establishing a consensus on this sensitive issue, such a substantial step must be thoroughly reviewed before being approved.33 On the other hand, if this rule-change is not done in a timely manner, a bounty pool of a few million Bitcoins remains in the open (although every Bitcoin address would have to be cracked individually - adding more time and pressure to change the protocol). A more realistic scenario to occur is that repeatedly conveying the message to the community to not re-use Bitcoin addresses twice and to move their funds to a safe address will decrease the amount of quantum vulnerable Bitcoins significantly. Once a quantum computer appears to attack the first unveiled public keys (or gets closer to achieving this), pressure to finally move funds to a safe address will rise to be the utmost priority for these users. This would result in a substantially decreasing honey-pot of Bitcoins for the quantum computer so that almost only the funds of users that have lost their private keys in the past would be prone to be hacked.
Principles of effective incentive design can be used to speed-up changes in consensus rules, such as applying a markup on transaction fees for P2PK and reused P2PKH wallets. This would prompt users to switch to safer behavior.34
I don’t think it’s likely that there will ever be a consensus established to cut old addresses off the network, given the censorship-resistant properties of the network itself - one of the pillars of Bitcoin. The “code is law” ruling will probably remain dominant.35 The total sum of lost Bitcoins to date is estimated to be around 3,7 million.36 The honey-pot would only be a fraction of that number because most of these “lost Bitcoins” do not have unveiled public keys and therefore cannot be acquired by a quantum computer. All-in-all, it is quite likely that one day, a few hundred thousand Bitcoins will be obtained by a quantum computer.
Whether these implementations to mitigate attack vectors 1a and b fail or not, the “a-few-hundred-thousand-Bitcoins-carrot”, dangling right in front of scientists and engineers worldwide, could act as a stimulus to accelerate the development of this groundbreaking technology.
Solutions for attack vector 1c
The Bitcoin protocol may be modified to meet post-quantum cryptography standards and protect against flaws using the fork mechanism. Unfortunately, this defense mechanism implemented in Bitcoins design is often neglected (or not known) by quantum experts in their predictions of “cracking Bitcoin”.
The history of Bitcoin is filled with examples of hardware and software changes that had to be made to make the network more secure and performant37 — and good security practices in the present (avoiding wallet re-use) can help prepare for a more uncertain future.38 Some of these approaches have been in development for many years.
Similar to the recently activated taproot development update, where the timeline of development looked like this:39
Premature optimization of issues that do not exist yet can lead to more significant problems.40
There are many ideas about how to mitigate the risk of effective quantum computing attacks, even with long-term solutions: Lattice-based schemes (GPV, LYU, BLISS, ring-TESLA, DILITHIUM, and NTRU), multivariate polynomials (RAINBOW), and hash-based signatures (LMS, XMSS, SPHINCS, and NSW) are examples of proposals and solutions to the risk of quantum computing.41 However, these typically involve some kind of trade-off, be it higher costs, higher processing power, or greater network traffic.42
Adding to that, various other solutions have existed for many years regarding the serious attack vector described in 1c.43 One of them, suggested by Vitalik Buterin in 2013, is Lamport signatures.44 However, this has some limitations (one-time signatures and management of the same) to remain quantum-safe. NIST post-quantum signature schemes are a better alternative in comparison.45
Other post-quantum cryptography solutions include some zero-knowledge proof schemes.46 The event that quantum computers, which are generally still useless noise-making machines at this point, can derive the private key from the public key within the crucial time window is still some years away. The most optimistic predictions are five years (other, probably more realistic estimates range from 10-20 years), ignoring the fact that the quantum computer would also have to be “trained” to perform this specific task.47
A lot can happen in this timeframe regarding further research to find the most optimal solution. An unconventional and non-protocol-changing idea involves data collection via the mempool APIs to run real-time machine learning algorithms. These could spot anomalies and flag attempts at transaction hijacking.48
Attack vector 2 - Quantum miners
Another area of concern comes on the quantum mining front.
The most likely scenario is that a slow transition to better technology as it becomes available will be the outcome with quantum computing, as is the standard practice today when new hardware is released. Once quantum computers reach a state of development acceptable for mining, a quick adoption among miners can be expected, establishing an equilibrium as the network difficulty adjusts.49
Miners are incentivized to accumulate greater computing power, but they are also rewarded for maintaining the chain’s integrity. It would almost certainly be short-lived if a quantum attack were to happen. Miners would immediately agree and defend the network, demonstrating basic game theory in action. Additionally, the Bitcoin network is safer today than ever before - the hash rate is at an all-time high, with mining facilities located worldwide.50 It’s unlikely that a single person or organization will amass enough processing power to take over the network.51
Additionally, the proof-of-work mechanism used by Bitcoin is relatively resistant to substantial speedup by quantum computers for at least another five years, mainly because ASIC miners are extremely fast compared to the estimated clock speed of near-term quantum computers.52
These five years are an extremely optimistic estimate for quantum computers, as the further exponential advancement of ASICS is not added to the equation. From my research, it seems like the whole quantum mining fear is totally overhyped - the theoretical issues described in attack vectors 1a and b are the most “urgent” to solve, while this one might never become one.
Attack vector 3 - The Quantum Surprise - Sudden, secret, and massive quantum computing advancements
One of the main concerns portrayed in the public realm appears to be someone building an incredibly advanced quantum computer in secret.
This quantum computer would be capable of compromising cryptography throughout the world, but then choose specifically Bitcoin that will almost immediately lose most or all of their value using the most powerful and (probably) expensive machine ever built in human history. That is undoubtedly a danger that should be explored, but it is not realistic, like other “movie plot” risks.53
Attack vector 3a - The Quantum Surprise - Bitcoins cryptography
To minimize this attack from even occurring, a public bounty for anyone who publicly discloses the secret advance of quantum computers while remaining anonymous has been put in place.54 And even if it were to happen, an emergency fork of the Bitcoin network with ready-to-implement solutions exists. These transition protocols even function when ECDSA (used for the generation of signatures in Bitcoin) has already been compromised.55
As an immediate consequence, I would expect an extreme price crash accompanied by newspaper headlines “Bitcoin hacked by quantum computer”. Plenty of digital ink will be spilled. In the middle and long term, on the other hand, the survival of the quantum-proof Bitcoin fork will prove the resilience and adaptability of the network to yet another attack vector. The attacker has revealed their secret weapon that could theoretically break the encryption keys of military intelligence networks, practically throwing away a vast advantage - the ace up their sleeve - for absolutely nothing. It’s fun to discuss this theory in theory, but it’s not going to happen in the real world.
Attack vector 3b - The Quantum Surprise - A 51% attack on the Bitcoin network
For the sake of this article, we are interested in the worst-case scenario - even if it’s improbable to ever happen. We need a combination of:
a massively unexpected and secretive leap in quantum computing, and
a quantum computer specialized in mining for Bitcoins that vastly outperforms all ASIC miners on earth, which then
leads to a possible 51% attack of the network which, of course
could then be upheld for a more extended time - and not to forget -
no other competing quantum computer interferes the attack, and
the actor doesn’t want to support but rather destroy Bitcoin (spending billions and earning nothing).
Now that we have our recipe of unlikely-to-happen and economically pointless ingredients mixed together: The quantum miner can theoretically enable an attack on the Bitcoin network: Re-writing parts of the blockchain, reversing transactions, leading to the possibility of a double-spend.56 And indeed, a quantum miner could use Grover search to perform the Bitcoin proof-of-work using quadratically fewer hashes than are needed classically.57 If all of these combined unlikelihoods come true and the quantum miner could maintain the 51% attack long enough, the Bitcoin network would indeed have an existential crisis. The chances of this event ever occurring are theoretically possible (that’s a nice way of saying it never will).
And even if it were to happen; proof-of-work models without a quantum advantage exist - meaning that the proof-of-work can’t be accomplished significantly faster with a quantum computer than with a classical computer (e.g., memory-intensive proof-of-works such as Momentum,58 Cuckoo Cycle,59 and Equihash60). But changing to a new mining algorithm is not as easy as it might sound, especially in an emergency setting: The forked chain would immediately lose the entire hash rate because the current ASIC miners do not support the new algorithm. Meaning that the safety of the network would be severely compromised.
Conclusion:
The threat of quantum computers for Bitcoin is not as intimidating as it is often portrayed. Bitcoin has multiple quantum vulnerabilities, the realistic one to theoretically be exploited one day being unveiled public keys. It is not unlikely that hundreds of thousands of lost Bitcoins will be obtained by quantum computers one day.
For all other described quantum vulnerabilities, the combination of
the network’s capacity to evolve (to resist attacks) and
the quantum-proof solutions available (which are just seen as an overkill so far)
provide Bitcoin with the tools needed to mitigate such threats, even in the case of very high-capacity quantum computers.
Many experts discuss the potential adverse effects quantum computing has for Bitcoin (which are true) but dismiss its capacity to adapt and improve. Vulnerabilities exist, but so do solutions. The exposure of the vulnerabilities mentioned above is still several years away, and countermeasures can be implemented safely. The quantum threat is not entirely far-fetched but definitely exaggerated. Quantum computers will eventually break the current Bitcoin system, but Bitcoin will already have evolved until that has happened.
BitBeginner.com is launching on the 21st of March 2022.
It’s an ad-free, non-profitable, beginner-friendly, education platform focused on Bitcoin. Stay tuned.
Connect with me on LinkedIn.
Sources used in this article:
decrypt.co/28560/quantum-computers-could-crack-bitcoins-encryption-by-2022
jonathan-hui.medium.com/qc-what-is-a-quantum-computer-222edc3a887d
nasdaq.com/articles/can-governments-shut-down-bitcoin-with-quantum-computers-2021-09-15
imf.org/-/media/Files/Publications/WP/2021/English/wpiea2021071-print-pdf.ashx
ft.com/content/b9bb4e54-dbc1-11e9-8f9b-77216ebe1f17
nature.com/articles/d41586-019-03213-z
newscientist.com/article/2297583-ibm-creates-largest-ever-superconducting-quantum-computer
techcrunch.com/2020/09/29/d-wave-launches-its-5000-qubit-advantage-system
amarchenkova.com/posts/quantum-annealing-vs-universal-gate-quantum-computer
nature.com/articles/d41586-021-03476-5
en.wikipedia.org/wiki/Moore%27s_law
ledger.pitt.edu/ojs/ledger/article/view/127/107
blogs.scientificamerican.com/observations/the-problem-with-quantum-computers
forbes.com/sites/rogerhuang/2020/12/21/heres-why-quantum-computing-will-not-break-cryptocurrencies/?sh=436a8700167b
rolandberger.com/en/Insights/Publications/Quantum-technology-The-next-big-disruption.html
rolandberger.com/en/Insights/Publications/Quantum-technology-The-next-big-disruption.html
royalsocietypublishing.org/doi/pdf/10.1098/rsos.180410
blogs.scientificamerican.com/observations/the-problem-with-quantum-computers/
crypto.stackexchange.com/questions/59375/are-hash-functions-strong-against-quantum-cryptanalysis-and-or-independent-enoug
decrypt.co/28560/quantum-computers-could-crack-bitcoins-encryption-by-2022
royalsocietypublishing.org/doi/pdf/10.1098/rsos.180410
academy.bit2me.com/en/what-is-a-p2pk
academy.bit2me.com/en/what-is-a-p2pk
ledger.pitt.edu/ojs/ledger/article/view/127/107
royalsocietypublishing.org/doi/pdf/10.1098/rsos.180410
deloitte.com/nl/nl/pages/innovatie/artikelen/quantum-computers-and-the-bitcoin-blockchain.html
eprint.iacr.org/2021/967.pdf
bitcoinmagazine.com/technical/bitcoin-is-not-quantum-safe-and-how-we-can-fix-1375242150
ledger.pitt.edu/ojs/ledger/article/view/127/107
deloitte.com/nl/nl/pages/innovatie/artikelen/quantum-computers-and-the-bitcoin-blockchain.html
ledger.pitt.edu/ojs/ledger/article/view/127/107
deloitte.com/nl/nl/pages/innovatie/artikelen/quantum-computers-and-the-bitcoin-blockchain.html
deloitte.com/nl/nl/pages/innovatie/artikelen/quantum-computers-and-the-bitcoin-blockchain.html
bitcoinmagazine.com/technical/quantum-computing-and-bitcoin-security
journals.openedition.org/factsreports/4518
de.statista.com/infografik/23933/anzahl-der-geschuerften-nicht-geschuerften-bitcoins
visualcapitalist.com/major-bitcoin-forks-subway-map
forbes.com/sites/rogerhuang/2020/12/21/heres-why-quantum-computing-will-not-break-cryptocurrencies
kraken.docsend.com/view/9e9y7may8526z934
en.wikipedia.org/wiki/Program_optimization#When_to_optimize
ledger.pitt.edu/ojs/ledger/article/view/127/107
coinshares.com/research/bitcoin-and-the-quantum-computing-risk
bitcoinmagazine.com/technical/bitcoin-is-not-quantum-safe-and-how-we-can-fix-1375242150
en.wikipedia.org/wiki/Lamport_signature
eprint.iacr.org/2021/967.pdf
bitcoin.stackexchange.com/questions/93047/could-taproot-create-larger-security-risks-or-even-hinder-future-protocol-adjust
ledger.pitt.edu/ojs/ledger/article/view/127/107
bitcoinmagazine.com/technical/quantum-computing-and-bitcoin-security
royalsocietypublishing.org/doi/pdf/10.1098/rsos.180410
ycharts.com/indicators/bitcoin_network_hash_rate
academy.aax.com/en/what-is-a-51-attack-on-the-bitcoin-blockchain
researchgate.net/publication/320727053_Quantum_Attacks_on_Bitcoin_and_How_to_Protect_Against_Them
lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-March/018648.html
bitcointalk.org/index.php?topic=293382.0
royalsocietypublishing.org/doi/pdf/10.1098/rsos.180410
mach37.com/new-blog/quantum-crypto
ledger.pitt.edu/ojs/ledger/article/view/127/107
hashcash.org/papers/momentum.pdf
link.springer.com/chapter/10.1007%2F978-3-662-48051-9_4
ledger.pitt.edu/ojs/ledger/article/view/48