Quantum Computers pose a credible threat to the security of Bitcoin

“… to avoid that failure of nerve for which history exacts so merciless a penalty — we must have the courage to follow all technical extrapolations to their logical conclusion.” — Arthur C. Clarke

Tl;dr: People vastly underestimate the problems quantum computing will pose for today’s cryptocurrencies which rely on ECDSA and may be overestimating how long useful quantum computers (QCs) will take to arrive. Bitcoin and other coins cannot easily fork to quantum security and avoid these issues.

There is a huge amount of confusion surrounding QCs and their relation to cryptocurrency. This is intended to be a resource and starting point for people who want to research this issue. I am by no means a quantum computing expert, but all of these pieces are available for anyone to investigate on their own. Don’t take my word for it (and please let me know if you feel I have misrepresented anything).

When talking about the relationship between QCs and today’s blockchain systems, there are two aspects which are often conflated and confused:

• The impact of QCs on mining / hashing (SHA-256) and the fundamental viability of the blockchain concept (not as much of an issue)
• The impact of QCs on wallet/address security for current blockchain implementations like BTC which rely on ECDSA (a very serious issue)

These aspects are directly related to two algorithms which are frequently cited when discussing QCs: Grover’s Algorithm and Shor’s Algorithm. People often dismiss the QC threat because they only consider Grover’s algorithm while completely ignoring the threat that Shor’s algorithm will pose to cryptocurrency private keys / wallets, and they often don’t understand the difference between the two. More detail on the math behind Shor’s and Grover’s algorithms, and relevant blockchain mechanics, can be explored here and here.

Why are current wallets vulnerable to a QC (what kind of problems do QCs excel at)?

If you were tasked you with finding the two prime factors of the number 15, you would tell me that they are 5 and 3.

If you were asked to find the two prime factors of a number that is 1000+ digits long, you might have some trouble. Even our fastest supercomputers cannot solve this type of problem in a reasonable time frame (it would take them millions of years), and this fact is what underlies the internet’s present-day cryptographic systems. The asymmetry of this setup is the crucial part: if one claims to know the numbers, or has the private key, it is easy to verify that claim — but it is functionally impossible to derive it for ourselves from the public key. It is easy/efficient in one direction and computationally intractable in the other.

The difficulty of this integer factorization problem (and the related discrete logarithm problem) is what underlies the security of Public Key Infrastructure (PKI), which allows us to transmit credit card numbers on the internet and to guarantee that a message was signed by the holder of a given public key. The specific implementation that takes advantage of this type of assumption and provides security for most contemporary blockchain wallets is called the Elliptic Curve Digital Signature Algorithm (ECDSA).

Quantum Computing destroys this assumption. Using Shor’s algorithm, a sufficiently powerful QC will reduce the time required to factorize the product of two primes from millions of years to a number of minutes/seconds and will allow the QC to derive a private key from a public key. Any BTC address which has broadcast a transaction has an exposed public key, and all of Satoshi’s one million coins, representing $6.5B USD and more than 5% of all BTC in circulation, are exposed to this type of attack (before 2012, block rewards were paid to an ECC public key, but they are now paid to the SHA256 hash of a public key). Over 40% of bitcoin balances are held by wallets with exposed public keys (see ‘address reuse’ chart here).

Anything which relies on ECDSA currently will be forced to attempt an upgrade at some point in the future, but there are significant problems with such a transition that I have never seen adequately addressed.

The major problems with blockchains that are not quantum-resistant from genesis:

1) Even if a project successfully forks their blockchain to have a quantum-proof crypto signature scheme (this is definitely possible) their old coins (and by extension, their updated “quantum-proof” blockchain) can still be attacked as if they were not protected by quantum-proof cryptography at all.

A hard-fork can result in two separate coins (as in the case of BTC and BCH) or it can represent a sort of update, where one coin is the result of an update and the other is abandoned (as we see with ETH’s regular hard forks). Either way, after the fork, your new coin will be where you had your old coin: in a wallet or an exchange. This implies that the new coin(s) are still accessible through your old private key. This old private key is not quantum proof, because forking does not and cannot make the old private key disappear. If the new coin wasn’t somehow connected with the old private key, how would it end up in your wallet / exchange and be accessible for you?

To finalize the hypothetical quantum proof update, users would need to move their quantum proof coin to a new address/wallet. That way, the user would leave their old private key behind with their old wallet, while the new coin(s) sent to their new address/wallet would only be accessible with a new quantum-proof private key. This seems relatively simple, but there are hidden problems. Besides the issue of human nature which suggests that not everyone will participate in a timely manner given a sudden black-swan QC advance, there is a more pressing concern:

There are a lot of coins which are lost or inaccessible due to users losing their keys/passwords or getting locked out in some other way. This is especially true for blockchains which have existed for the longest periods of time, such as BTC and ETH (it is estimated that up to 20% of BTC are permanently lost). For almost every blockchain project and platform, there are a lot of coins that nobody even can move to a new wallet. This entire subset of coins will remain accessible through their associated old/original/legacy private key even after “quantum proofing” a given blockchain, and will therefore not be accessible to transfer for their original human owners but will be accessible to a QC if the public key of the address in question has ever been exposed. A QC attacker could access these old coins and migrate them to the new system, which could result in updated and “quantum-proof” blockchains where a QC attacker owns 10%+ of all the coins in existence, allowing them to manipulate the price severely. If the NSA suddenly owned 10% of all Bitcoins and wanted to crash the price, potentially in response to a sudden abandonment of fiat currencies, would that not cause a crisis of confidence in the security of the BTC system as a store of value?

People will say: “We could simply make a deadline, and any coins not migrated in time will become unspendable” — and it is true that this is possible through a soft-fork. But when/if Satoshi’s coins don’t move by the deadline, will people accept the new “quantum-proof” Bitcoin chain as legitimate if it cuts off the ability of Bitcoin’s inventor (and the ability of anyone else who missed the deadline, for any reason) to move their BTC? At best, it will be significantly more contentious than the block size debate, and since BTC would likely only make such a transition in reaction to some quantum computer news, the time-frame available to organize such a transition is likely to be seriously compressed. Managing to get even 50% of BTC to participate in such a migration (especially under time pressure) would be a huge feat, and even with 50% participation it would be far short of the majority required to resolve questions of legitimacy.

2) Let’s assume that the above problem is solved, deus ex machina, and that we obtain a guarantee that every single address will migrate its balance to a new quantum-secure address as soon as it is physically possible, with the additional bonus that there are no lost coins whatsoever to worry about.

There is a second type of attack which would completely paralyze a blockchain network in the midst of an attempted upgrade, if it waited until QC was a threat to attempt a transition. As soon as a user attempting to migrate their coins submits a transaction to the network, a sufficiently armed QC attacker could derive the private key (a transaction cannot be submitted without exposing the public key in the bitcoin system) and submit a second transaction with a higher fee, effectively re-routing the BTC in transit to a quantum-proof address under the control of the QC attacker. There would be no way to send any transactions without having it be hijacked (that I have been able to find), unless you introduced some sort of temporary centralization into the network.

Below are some common responses and misconceptions I often see when the topic of QC risk in relation to today’s cryptocurrencies comes up

But doesn’t the whole internet also rely on PKI? If sufficiently powerful QCs exist, we will have bigger problems!

This is a common non-response to the QC threat. While migrating legacy systems will definitely be hard, it will actually be significantly easier to update centralized systems (banks, HTTPS, nuclear weapon systems etc) to something like XMSS than it will be a decentralized blockchain. System downtime for a centralized system is not a big deal — blockchains, on the other hand, are predicated on the idea of no downtime and no central authority that could dictate the terms of a temporary pause and subsequent rebooting.

Post-quantum standards are being solidified and the effort to transition legacy institutional systems to Quantum Security is already well underway, being led by groups such as the ISARA Corporation.

Mining: SHA256 is a hash function, not an encryption technique, won’t be broken by QCs

This is true, and one of the reasons people often cite when claiming that QCs aren’t a threat. When thinking about mining, Shor’s algorithm is not relevant. This is where Grover’s algorithm comes in, because it provides quantum computers a quadratic advantage over classical computers for searching in an arbitrary data-set. Bitcoin mining falls into this category of a search problem (difficulty of 2²⁵⁶ would become difficulty of 2¹²⁸). This is one of the reasons the QC threat is frequently (and wrongly) dismissed.

While it is does not represent nearly as much of an existential risk as Shor’s algorithm, even the mining / Grover’s algorithm threat may be more severe than people are considering. As the author of this paper explains in a reddit thread: “It has been previously argued that the only side-effect of quantum mining would be an increased difficulty, due to this quadratic speed-up which can be applied to Bitcoin mining. In this work we argue that a crucial argument in the analysis of Bitcoin’s security breaks down when quantum mining is performed. Classically, a Bitcoin fork occurs rarely, when two miners find a block almost at the same time: only if both miners are unaware of the other’s block, due to propagation time effects. The situation differs dramatically when quantum miners use Grover’s algorithm.”

QCs are just theoretical — wake me up when they actually exist!

Another common misconception is that QCs remain mostly theoretical. It has been said that there is a point in the life-cycle of many technologies where an idea goes from being a physicist’s dream to being an engineer’s nightmare. QCs are at that point and they already exist, albeit in a nascent form.

• IBM has a publicly accessible 20 qubit quantum computer
• MIT researchers implement Shor’s algorithm, factor the number 15
• Google has a processor with 72 qubits, and intends to demonstrate quantum supremacy (when a QC first performs a calculation impossible on a classical computer) with it

Your BTC are safe if you don’t reuse addresses / never expose the public key of an address with coins in it

This concerns Local vs Global Quantum Security. It is often said that if you use proper wallet technique (don’t ever use a wallet for more than one transaction) an individual wallet will remain safe from attack by a QC, which is true. Despite it being true, if all of Satoshi’s coins are stolen and sold and the market price crashes by 90%, your safe bitcoins will still be worth 90% less because the network as a whole will not be sufficiently quantum-resistant to retain confidence.

Other problems with forking to new signature schemes

Quantum proof signatures are much larger the ECDSA ones, which would significantly increase transaction costs and times if implemented in BTC. A fork would affect many parts of the Bitcoin system, and may lead to unavoidable inefficiencies compared to a system which was designed to be quantum resistant form the ground up. With the slow moving and contentious nature of blockchain development, it may not be feasible to do this type of fork quickly in response to an unforeseen advance in QC ability.

If this is true, why aren’t people taking the quantum threat seriously?

Professionals who rely on cryptography are taking the threat posed by quantum computing very seriously. In 2015, the NSA announced that it plans to move to a new cipher suite due to concerns about QC attacks on current encryption standards.

What solutions have been proposed for today’s cryptocurrencies?

Andreas M. Antonopoulos: his response is basically we will update the signature scheme when the time comes, but this does not take into account the points made above about the difficulties of a transition.

Vitalik Buterin: Vitalik himself wrote an article in 2013 about why Bitcoin is vulnerable to a QC attacks and how to fix it, and gave a talk on the same subject. The arguments transfer to Ethereum currently because it uses the same assumptions as the basis for its security. Note that in his proposed solution, Vitalik makes two major assumptions:

• that there will be a “warning period” of a month where quantum computers are announced but not used in attacks (if the NSA has one in a few years and decides to destabilise BTC to stop the abandonment of USD, for example, there will be no warning period. The advantage for any nation-state possessing a quantum computer would be much greater if their possession remained a secret, since they could break encrypted communications of other countries in real-time).
• that users will all cooperate in a timely manner (his solution also relies on temporary centralization, something that I doubt could be organized in a month even if that month existed, because of the contentious/slow moving nature of blockchain modification). There is also no resolution to the problem of lost BTC or Satoshi’s coins.

A commit–delay– reveal protocol: This is probably the best proposal so far, but emphasises “the necessity of a substantial delay phase to provide sufficient protection against accidental and, especially, adversarial chain reorganisation” which may last up to 6 months, during which time the BTC chain would become unusable, and assumes that “the Bitcoin community has agreed on and deployed a quantum-resistant signature scheme.” As noted above, changing the signature scheme is not a small fork and it is questionable whether it would be feasible to implement, especially considering time constraints.

If I have missed any proposed solutions, which take into account the difficulties elaborated above, please let me know.

Properties required for true Quantum Security in a blockchain

Most of the claims of quantum-security today are misleading or outright false. To be completely quantum secure, a blockchain:

• Cannot rely on ECDSA
• Must be quantum-secure from genesis

A QC arms race is underway

The recent uptick in investment surrounding quantum technology by nation-states should not be ignored. China has announced its intention to build a $10 billion national laboratory for quantum information sciences, which is slated to open in 2020. The US Department of Defense has requested $105M in the FY19 budget to improve its quantum abilities specifically, and Senator Kamala Harris recently proposed a US quantum initiative. Canada and Australia are other governments investing heavily into this area of research.

A quantum computer is one of the most valuable advantages a government could possibly have, and it is likely that intelligence agencies are stockpiling encrypted communications of other nations which will eventually become decipherable.

A Caveat and Conclusion

Quantum Computing technology is hugely complicated, and while the remaining hurdles could be surpassed earlier than experts expect (as was the case when AI experts predicted in 2015 that AI techniques would not be able to beat a human Go champion for a decade, and then it happened the next year), it could also take longer than expected.

A key distinction to make is between “qubits” and “logical qubits”, a complicating descriptor on an already nebulous concept. It has been estimated that a Quantum Computer would require at most 2330 qubits and 129 billion gates to crack Bitcoin’s secp256k1 elliptic curve implementation. As a reddit commenter aptly put it, in order to be intellectually honest we must concede that the 2330 qubits refer to ideal, fault-tolerant, logical qubits, whereas the 17 qubits achieved in 2017 by IBM’s quantum processor are raw, imperfect qubits which could be used to encode 7 logical qubits. Quantum error-correction of a single fault-tolerant qubit has not yet been achieved in experiments.

The difficulties of error-correction, noise, and scaling should not be underestimated. They are likely among the most formidable engineering tasks the human species has yet faced. That being said, there are multiple avenues of research ongoing, into wholly separate qubit architectures, all with different properties and tradeoffs, some of which would be much easier to scale. Microsoft, for example, is working on highly scalable topological qubits and aims to “scale to thousands, ten thousands, hundreds of thousands and beyond.”

News of QC advances is piling up quickly, with fundamental discoveries being reported frequently. Recent news includes research which could allow quantum computers operate at room temperature, for example.

Quantum computers could make the world much better

The promise of QCs is almost unlimited, and will help accelerate advances in almost every other field of science. The most immediate benefits will be in materials design, drug development, AI research, and in the fight against climate change. We will one day be able to perform calculations that would take longer than the age of the universe with today’s best supercomputers, in the time it takes to make a cup of coffee.

*Edit 8/24/2019: The discovery of new properties in the superconductor UTe2 is exactly the type of thing that could precipitate a black swan advance / significant breakthrough and re-adjustment of quantum computer timelines.

Since the writing of this article, the US govt has passed a $1.2B quantum computing bill to advance research.