Bitcoin and the Quantum Threat

The quantum computer is a reality. Satoshi bitcoins still linked to addresses not protected by SHA-256 will soon be vulnerable.

Symmetric and asymmetric cryptography

The Bitcoin protocol works with symmetric and asymmetric cryptography. In the second case, we also speak of “public key” cryptography. It is at the heart of the mechanics of transactions.

A private/public key pair is essentially a mathematical relationship. Asymmetric cryptography relies on a “one-way” mathematical function. Clearly, the public key can be easily derived from the private key, but not the other way around. It is immensely difficult to discover a private key from a public key.

But not for long because of quantum computers. The latter can break the most common asymmetric cryptography thanks to the quantum algorithm of mathematician Peter Shor.

Bitcoin is therefore concerned since it uses asymmetric cryptography (secp256k1 Elliptic Curve Cryptography) for the creation of private/public key pairs. A large enough quantum computer can easily use Shor’s algorithm to discover a private key from a public key.

Before we go any further, let’s summarize how bitcoin transactions work.

Rather than having accounts maintained by banks, bitcoiners build their own accounts by generating public addresses.

The wallets take care of this by randomly selecting a 256-bit cipher (the seed) from which private keys and public keys are derived.

Performing a bitcoin transaction means “moving” bitcoins from one public key to another. To be precise (and more abstract…), behind each transaction hides the creation of a “UTXO”.

The UTXO is a “script” linked to a public key and an amount of BTC (a number). Only the private key matching the public key can “unlock” (sign) scripts to bind BTC to a new public key.

This is how a bitcoin transaction works. One (or more) UTXOs disappear to form one (or more) new UTXOs attached to new public keys.

Your wallet therefore does not contain bitcoins as such. It contains the private keys to “sign” transactions. Once the transaction is added to a “block” by a miner, all nodes update the UTXO list. There are about 104 million currently.

Script, private/public key, address

Several types of scripts exist. The first used the Pay-to-Public-Key (P2PK) method. At that time, we were talking about the public key.

Example: 03673afdb0fe6748271967f……….84df7ba0b8d578a4c702b6bf11d5

Subsequently appeared Pay-to-Public-Key-Hash (P2PKH). This method introduces the use of addresses that are obtained by passing the public key through the hash functions SHA-256 and RIPEMD-160. Public keys are transformed into hashes.

Hashing the public key with SHA-256 obfuscates the public key, which introduces resistance to quantum computers. Indeed, SHA-2 is based on symmetric cryptography which is more resistant to the quantum computer than asymmetric. Just use longer keys.

Moreover, the public keys are very long, which unnecessarily weighs down the UTXOs kept in memory by the nodes. Public keys hashed by SHA-256, then hashed by RIPEMD-160, are smaller. This results in a need for less disk space to run a node, which reinforces decentralization.

P2PKH addresses consist of 34 or 33 characters. They are encoded in Base58 format. They start with the number 1 and are found in about 40% of UTXOs, more than any other type of address.

Example: 12higDJCCNXSA95xZMWUdPvXNmkAdbhWv

There is also the Pay-to-Witness-Public-Key-Hash (P2WPKH) method introduced in the 2017 SegWit soft fork. This is the SegWit variant of P2PKH which saves on transaction fees.

SegWit addresses are very different from older address types. They use Bech32 encoding instead of Base58. In particular, there are no capital letters in Bech32. This type of address begins with bc1q and consists of 42 characters.

Example: bc1q34aq5drpuwy3wgl9lhup9892qp6svr8ldzyy7c

It exists other types of addresses, and in particular the most recent: Pay-to-Taproot (P2TR). This uses a signature algorithm called Schnorr which differs from the ECDSA format (Elliptic Curve Digital Signature Algorithm) used until now.

The signatures Schnorr have several advantages for “multisig” transactions. Lower costs and increased confidentiality.

All this to say that asymmetric cryptography based on elliptic curves can be broken by quantum computers. UTXOs including public keys rather than addresses are therefore vulnerable.

How many bitcoins could be stolen?

Many of the bitcoins mined by Satoshi Nakamoto are bound to still be tied to public keys rather than Pay-to-Public-Key (P2PK) addresses. A quantum computer running Shor’s algorithm could derive the private key for all of these UTXO P2PKs.

Conversely, UTXOs using the Pay-to-Public-Key-Hash (P2PKH) method are protected by SHA-256. The public key is revealed only at the time of the transaction.

HOWEVER, once the public key has been revealed, it must no longer be used to receive bitcoins! Not only to enhance your anonymity, but also because of the quantum threat.

To know exactly how many bitcoins are vulnerable, just count the UTXOs whose scripts work with the Pay-to-Public-Key (P2PK) method as well as all the Pay-to-Public-Key-Hash (P2PKH) addresses reused .

Here is the distribution of bitcoins in the different types of addresses over time:

P2PK addresses dominated in the first year. Then, from 2010, the P2PKH quickly imposed itself.

We also observe that the number of bitcoins linked to reused P2PKH addresses is slowly decreasing (~2.5 million bitcoins). This trend suggests that more and more people are adopting the good practice of generating a new address (a new private/public key pair) for each transaction.

Nevertheless, more than 4 million BTC (about 25% of all Bitcoins) remain potentially vulnerable to a quantum attack.

That is a jackpot of 120 billion dollars at the current price. This is the reward of the creators of the quantum computer: Satoshi’s BTC.

Mathematicians believe that we should 317,000,000 qubits to crack in one hour the asymmetric cryptography using the elliptic curves (secp256k1) of Bitcoin keys. That is 35,600 qubits to achieve this in one year.

It’s not for tomorrow since IBM’s largest quantum computer has only 433 qubits. But we will have to move on to post-quantum cryptography in the near future.