The quantum computer is making headlines again and rekindling concerns which offer us the opportunity to delve back into the cryptographic depths of bitcoin.
QC
First of all, let us roughly recall that a quantum computer is a processor that uses the quantum properties of matter.
A classic computer is made of transistors operating with binary data (bits equal to 0 or 1). The quantum computer works with qubits in several states at the same time. This property allows you to increase the calculation 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 benchmark calculation in less than five minutes that would take the best supercomputer 10 million billion billion years (10 raised to the power of 25).
There are many areas in which a quantum computer could be more useful than a conventional computer. The case that interests us more particularly is Shor's quantum algorithm. This algorithm can break bitcoin.
The reason being that Bitcoin works with hash functions (SHA-256), but also asymmetric cryptography. In the second case, we also speak of “public key” cryptography which is at the heart of the mechanics of transactions. It is she who is at the mercy of the quantum computer.
A private/public key pair is in essence a “one-way” mathematical relationship. That is, 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.
It’s this one-way cryptography that makes bitcoin so strong. But maybe not for long…
Cryptographic key
Let’s go back to our explanation. Transactions operate with “public key” cryptography. More specifically, it is elliptic curve cryptography. It is with an elliptic curve (secp256k1) that we create the private/public key pairs to which the BTC are linked.
Wallets generate these keys 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.
These keys are used to carry out transactions which amount to moving bitcoins from one public key to another. We say in the jargon that we create a “utxo”, that is to say a small piece of code (a “script”). This script binds a public key to an amount of BTC (a number). Only the corresponding private key can “unlock” the script in order to link the BTC to another public key, aka complete a transaction.
Clearly, a wallet does not contain bitcoins strictly speaking. It hosts private keys used to unlock utxos that the network nodes keep in memory.
All nodes update their utxo list as soon as miners add a new transaction block to the blockchain. There are currently approximately 188 million utxos and therefore as many public keys (bitcoin addresses).
The Shor threat
Elliptic curves have been a fundamental part of the cryptographic landscape for thirty years. They are used for bitcoin, national identity cards, the Tor network and the encrypted messaging application Signal. This asymmetric cryptography secures our data and communications.
The security of elliptic curve cryptography relies on the discrete logarithm problem which Shor's quantum algorithm can break since it is capable of efficiently factoring a very large number into prime factors. Provided, however, that you have a sufficiently large quantum computer.
Researchers from the University of Sussex estimate that it would take 13 million qubits to break Bitcoin's encryption in a single day (and only 2,500 logical Qubits). The Willow processor includes 105 qubits. So, theoretically, it would take 124,000 willows.
All that being said, there is no need to worry too much. Bitcoin also uses hash functions (SHA-256 and RIPEMD-160) that are not threatened by quantum computers. In the worst case, it would be sufficient to use slightly longer keys.
Here is the reaction from Charles Guillemet, CTO of Ledger:
“While impressive, Willow has no practical applications yet. It is unlikely that it can factor even small numbers like 42 faster than classical computers […]. Breaking asymmetric cryptography would require millions of qubits and solutions to other problems […]. »
Bitcoin is not threatened by the quantum computer in the current state of knowledge. But let’s go back for a moment to how bitcoin works 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 include public keys. We used the Pay-to-Public-Key method (P2PK). In short, the public keys were used as is, in full view of everyone. This transparency makes them vulnerable to Shor's algorithm.
This is no longer the case today. Public keys are transformed by running through SHA-256 and RIPEMD-160 hash functions. These keys become what we commonly call bitcoin addresses.
Today we use the Pay-to-Public-Key-Hash (P2PKH) method which uses the hash of the public key rather than the public key itself. There are other methods like Pay-2-Taproot (P2TR), Pay-2-Script-Hash (P2SH), etc…
Hashing public keys allows them to be obfuscated to avoid being attacked by a quantum computer. Phew… However, many bitcoins are still linked to the old P2PK script which uses public keys directly. Notably Satoshi's bitcoins which alone are a good reason to invest in quantum research.
How many bitcoins are at risk?
The National Institute of Standards and Technology (NIST) predicts that quantum computers capable of running Shor's algorithm will exist in 10 to 20 years. Those who have not yet moved their bitcoins to tamper-proof addresses have plenty of time to do so.
In total, 1,723,900 BTC are still in P2PK utxos. But that's not all. Over 4 million additional BTC are at risk due to address reuse.
Everything is fine as long as an address only receives BTC. But you should know that the public key is revealed as soon as part of the funds received are spent, regardless of the type of script used.
In other words, generating new addresses for each transaction not only reinforces your anonymity, but also protects you from the quantum threat.
Here is a recent presentation on what it is, with supporting figures:
Certainly, several asymmetric cryptography algorithms resistant to quantum computers already exist. But remember that the majority of the first algorithms proposed to NIST were broken in just a few months.
Once the right cryptography has been chosen, users will still need to take the action by moving their BTC to secure addresses themselves. Bitcoin being what it is, we cannot install a new type of signature, and there you have it, resistant!
Jameson Lopp calculated that it would technically take 20,500 blocks (142 days) to migrate all of the bitcoins to new addresses. Even several years for the realistic scenario.
Maximize your Tremplin.io experience with our 'Read to Earn' program! For every article you read, earn points and access exclusive rewards. Sign up now and start earning benefits.
