Bitcoin And The Quantum Threat

The quantum computer is making headlines again and rekindling concerns that offer us the opportunity to dive back into the cryptographic guts of bitcoin.

QC

First of all, let’s roughly remind ourselves that a quantum computer is a processor that uses the quantum properties of matter.

A classical computer is made of transistors operating with binary data (bits worth 0 or 1). The quantum computer works with qubits existing in multiple states at the same time. This property allows for a multiplication of computing speed.

Google is at the forefront of technology. Its new quantum processor ” Willow ” marks a turning point thanks to the exponential reduction of errors inherent in quantum systems.

Willow was able to perform a standard reference calculation in less than five minutes that would take the best supercomputer 10 million trillion trillion years (10 to the power of 25).

Introducing Willow, our new state-of-the-art quantum computing chip with a breakthrough that can reduce errors exponentially as we scale up using more qubits, cracking a 30-year challenge in the field. In benchmark tests, Willow solved a standard computation in <5 mins that would…

— Sundar Pichai (@sundarpichai) December 9, 2024

There are many areas where a quantum computer could prove more useful than a conventional computer. The case that particularly interests us is Shor’s quantum algorithm. This algorithm can break bitcoin.

The reason is that Bitcoin operates with hash functions (SHA-256), but also with asymmetric cryptography. In the latter case, we also refer to “public key” cryptography, which is at the heart of transaction mechanics. It is this that is at the mercy of the quantum computer.

A pair of private/public keys is essentially a “one-way” mathematical relationship. That is to say, the public key can be easily found from the private key, but not vice versa. It is immensely difficult to discover a private key from a public key.

This is what makes bitcoin so solid. But perhaps not for long…

Cryptographic Key

Before going further, let’s revisit our explanation. Transactions operate with “public key” cryptography.

More specifically, it involves elliptic curve cryptography. It is with an elliptic curve (secp256k1) that pairs of private/public keys are created, to which BTC are linked.

These keys are generated by a wallet from a random 256-bit number (the seed). This seed is the starting point from which all private/public keys of the wallet are derived.

Making a transaction means “moving” bitcoins from one public key to another. It is said in jargon that an “utxo” is created, which is a small piece of code (a “script”). This script links a public key to a quantity of BTC (a number). Only the corresponding private key can “unlock” the script to link the BTC to another public key, aka making a transaction.

In simple terms, a wallet does not contain bitcoins per se. It houses private keys used to unlock utxos that nodes in the network keep in memory.

All nodes in the network update their list of utxos with each new block of transactions. Currently, there are approximately 188 million utxos, and therefore as many public keys (bitcoin addresses).

The Shor Threat

Elliptic curves have been a fundamental element of the cryptographic landscape for over thirty years. They are used in bitcoin, national identity cards, the Tor network, as well as in the encrypted messaging application Signal. This asymmetric cryptography secures most of our data and communications.

The security of elliptic curve cryptography relies on the so-called discrete logarithm problem. Unfortunately, Shor’s quantum algorithm can efficiently factor a very large number into prime factors and thus shatter elliptic curve cryptography. However, this requires a sufficiently large quantum computer.

Researchers from the University of Sussex estimate that it would require 13 million qubits to break Bitcoin’s encryption in a single day (and only 2,500 logical qubits). The Willow processor consists of 105 qubits. So, theoretically, it would take 124,000 willows.

That being said, there is no need to worry excessively. Bitcoin also uses hash functions (SHA-256 and RIPEMD-160) that are not threatened by quantum computers. In the worst-case scenario, it would be sufficient to use slightly longer keys.

Here is the reaction from Charles Guillemet, CTO of Ledger:

“Although impressive, Willow has no practical applications yet. It is unlikely to factor even small numbers like 42 faster than classical computers […]. To break asymmetric cryptography, millions of qubits and solutions to other problems would be required […].”

Did Google Create a Quantum Computer That Breaks Blockchain Security?

TL;DR: No. While the research results are impressive, we're still far from breaking modern cryptography.

A thread. 🧵 https://t.co/a0DTfvzlxh

— Charles Guillemet (@P3b7_) December 10, 2024

As of now, according to current knowledge, bitcoin is not threatened by quantum computers. But let’s revisit how bitcoin works for a moment to convince ourselves.

The Shield of Hash Functions

During a transaction, a script (utxo) is created. This script mathematically links an amount of BTC to a public key.

Originally, the bitcoin protocol did not obfuscate public keys. The Pay-to-Public-Key method (P2PK) was used. In summary, all public keys were used as they were, making them vulnerable to Shor’s algorithm.

This is no longer the case today. Public keys are transformed into “addresses” by passing them through the SHA-256 and RIPEMD-160 hash functions.

One of these new methods is called Pay-to-Public-Key-Hash (P2PKH), which uses the hash of the public key instead of the public key itself.

Hashing public keys allows them to be obscured and made resistant to quantum computers. Phew… However, many bitcoins are still tied to scripts that directly use public keys. Notably, those belonging to Satoshi.

How Many Bitcoins Are at Risk?

The National Institute of Standards and Technology (NIST) predicts that quantum computers capable of executing Shor’s algorithm will exist in 10 to 20 years. Those who have not yet moved their bitcoins to secure addresses have plenty of time to do so.

In total, 1,723,900 BTC are still found in P2PK utxos (including Satoshi’s million BTC). But that’s not all. More than 4 million additional BTC are also at risk due to address reuse.

All is well as long as an address only receives BTC. However, the public key is revealed as soon as part of the received funds is spent, regardless of the type of script used.

In other words, generating new addresses for each transaction not only enhances your anonymity but also protects you from the quantum threat.

Here is a recent presentation on the matter, backed by figures:

My latest talk, on the threat of quantum computing advancements to Bitcoin, is now available.

Key takeaway: one way or another, whether we do something or do nothing, inviolable properties of Bitcoin will eventually be violated.https://t.co/4qv5KrD8Mo

— Jameson Lopp (@lopp) October 23, 2024

Certainly, several asymmetric cryptography algorithms resistant to quantum computers already exist. But let’s remember that most of the early algorithms proposed to NIST were broken in just a few months.

Once the right cryptography is chosen, users will still need to take action by moving their BTC to secure addresses themselves. Given what bitcoin is, one cannot just install a new type of signature, and voilà, it works against quantum.

Jameson Lopp calculated that it would technically take 20,500 blocks (142 days) to migrate all bitcoins to new addresses. Or even several years for a realistic scenario.