Google's Quantum Breakthrough Renews Bitcoin Security Concerns

Recent advancements in quantum computing have brought the threat to Bitcoin's security into sharper focus. Google's researchers have made significant strides in optimizing Shor’s algorithm, reducing the qubit requirements to break RSA-2048 by a factor of 20. This breakthrough has renewed concerns within the Bitcoin community, as it suggests that the cryptographic foundations of Bitcoin could be at risk.

The optimization of Shor’s algorithm and improved error correction for quantum decoherence have made it possible to break RSA-2048 with one million qubits, down from the previous requirement of 20 million qubits. However, it is important to note that the largest quantum processor currently available, IBM’s Condor, has only 1021 qubits. The challenge of maintaining quantum coherence increases exponentially with the number of qubits, making the practical implementation of such a breakthrough still a distant prospect.

Despite these advancements, the quantum computer still cannot factor even a small number like 35, indicating that tangible progress in quantum computing remains elusive. Nevertheless, the potential threat to Bitcoin's security is real, as companies like Apple and Microsoft are planning to adopt post-quantum cryptography this fall. This underscores the urgency for the Bitcoin community to prepare for a post-quantum future.

Google’s breakthrough involves Shor’s algorithm, which can solve the discrete logarithm problem exponentially faster than classical computers. This means that it is theoretically possible to derive a private key from a Bitcoin public key. However, Bitcoin's elliptic curve "secp256k1" is not directly impacted by Google’s recent advance. The Pauli Group’s founder warns that ECDSA, the cryptographic algorithm used by Bitcoin, is generally easier to crack than RSA, and it is not impossible that AI might optimize Shor’s algorithm to more easily break ECDSA.

Doubling the public key length, for example by using an elliptic curve "secp512k1," would only make deriving the private key twice as hard using Shor’s algorithm. This protection would still be insufficient. According to quantum computer maker IonQ, the elliptic curve "secp32k1" could be broken by 2027, and "secp256k1" (Bitcoin) by 2029. These predictions should be taken with caution, as they are based on current technological capabilities and future advancements are uncertain.

The National Institute of Standards and Technology (NIST) is working on standardizing post-quantum cryptography algorithms. Three candidates are favored for digital signatures: CRYSTALS-Dilithium, SPHINCS+, and FALCON. These algorithms could theoretically replace ECDSA. However, the transition to post-quantum cryptography will not be without its challenges. Signatures and keys are much larger, which will inevitably reduce on-chain transaction throughput. Creating and verifying signatures also takes much longer.

For example, for CRYSTALS-Dilithium Level I, a public key is 1,312 bytes and a signature is 2,420 bytes, far larger than current ECDSA (72 bytes) or Schnorr (64 bytes) signatures. NIST Level I security offers equivalent security to 128-bit keys, and Level V equates to 256-bit security. In summary, the solution already exists, but the community still needs to choose the right algorithm and manually migrate to post-quantum addresses.

BIP-360, proposed by Hunter Beast, is a "pragmatic first step" by introducing a new type of UTXO called "Pay to Quantum Resistant Hash" (P2QRH) whose addresses would start with "bc1r." Currently, a Bitcoin transaction reveals a public key along with a signature based on the ECDSA algorithm. BIP-360 proposes transactions include both ECDSA signatures and post-quantum signatures, similar to multi-sig transactions. This mix allows an ECDSA fallback if a flaw is discovered in the chosen post-quantum algorithm.

Hunter Beast advocates the FALCON algorithm, which has the advantage of enabling signature aggregation. His first candidate (SQIsign) was eventually abandoned due to its slowness. Post-quantum public keys and signatures are much larger than a 64-byte Schnorr signature. SLH-DSA (SPHINCS+) signatures can reach 29,000 bytes or more, depending on the parameters chosen. That means about 40 times fewer transactions per block! FALCON signatures are 20 times larger than Schnorr signatures and 13 times larger than ECDSA signatures.

Other proposals are on the table. For example, the BIP "Quantum-Resistant Address Migration Protocol" (QRAMP) proposed by Agustin Cruz plans a hard fork instead. In other words, bitcoins that do not migrate to post-quantum addresses would be lost forever. In 2020, Deloitte estimated that 25% of bitcoins are linked to old address types vulnerable to quantum attacks.

To protect your bitcoins, it is important to understand that "public keys" are not really public anymore. They are encoded by passing through quantum-resistant hash functions SHA-256 and RIPEMD-160. The resulting hash is known as the "Bitcoin address." However, public keys must be revealed at the time of transactions. They are therefore vulnerable as long as they remain in the mempool waiting for a miner to include them in a block. The threat ends once the block propagates. Unless you make the mistake of sending funds back to the same address.

Here is a summary of a transaction to better understand: Your wallet contains a UTXO of 1 BTC. This UTXO is public and contains information such as the amount (1 BTC) and a P2PKH (Pay-to-Public-Key-Hash) locking script. Now imagine you make a payment of 0.5 BTC. You supply your public key and a signature to unlock the script and perform the transaction. Since your UTXO is 1 BTC, this is what the transaction generates: -0.5 BTC to the recipient’s address, -0.0001 BTC to the miner’s address (transaction fee), and -0.4999 BTC sent back to a NEW change address generated by your wallet. Each of these three transactions creates a new UTXO. The 0.4999 BTC change linked to a new Bitcoin address (a new public key) is no longer vulnerable. On the other hand, you should never send new funds back to the original address that contained 1 BTC since it is now known to everyone.