Waiting for "Q-Day": What answer to quantum computers are Bitcoin developers preparing
#Биткоин #квантовые #QuantumBlock
On December 10, Google Quantum AI unveiled its new quantum chip, Willow. This event has once again raised concerns in the crypto community about the quantum threat to Bitcoin, a topic that has been raised periodically in the past.
However, it seems that after Google's release, "quantum FUD" has started to be taken much more seriously. Thus, already on December 18, a Bitcoin upgrade proposal (BIP) called Pay to Quantum Resistant Hash (P2QRH) was assigned a number (BIP-360).
Together with the team of the bitcoin mixer Mixer.Money, we figure out how developers are preparing for “Q Day” - a possible moment in the future when the first cryptocurrency may become vulnerable to quantum attacks.
What is the essence of the quantum threat?
The Bitcoin protocol uses public-key cryptography to make transactions. When a new wallet is created, a pair of keys is generated - a public and a private key, mathematically related. The private key must be kept secret, while the public key is available to everyone. This system allows digital signatures to be created using a private key. They can be verified by anyone who has the corresponding public key.
The security of the keychain is based on a one-way function: a public key can easily be derived from a private key, but not vice versa. However, in 1994, mathematician Peter Shor published a quantum algorithm that could violate this principle. Any organization with a Cryptoanalytically-Relevant Quantum Computer (CRQC) could use the algorithm to derive a private key from the corresponding public key.
In this regard, the author of BIP-360, under the pseudonym Hunter Beast, emphasized that preventing the appearance of a public key in the blockchain is an important step towards ensuring quantum security.
Back in 2019, Bitcoin developer Peter Welle suggested that around 37% of the supply could be at risk due to the disclosure of the public key in the blockchain. The reasons for this are the receipt of cryptocurrency directly to public keys or the reuse of addresses.
In earlier versions of the software, coins could be obtained in two ways:
Pay-to-Public-Key (P2PK). The public key itself serves as the recipient's address. Coins mined by Bitcoin creator Satoshi Nakamoto are stored in such wallets and can be compromised by CRQC.
Pay-to-Public-Key-Hash (P2PKH) - The recipient address consists of a hash of the public key, so the latter is not directly revealed on-chain.
Until a P2PKH address has made any transfers, its public key is not visible on the blockchain. It will only become known when the owner sends coins from it.
Once transferred, the address is not recommended for receiving bitcoins. Modern wallets are set up to generate a new address for each transaction, although this was done primarily for privacy reasons rather than quantum resistance.
However, in 2024, ordinary users, as well as cryptocurrency exchanges and custodial services, store hundreds of thousands of bitcoins in reused addresses.
Long-range. The public key is known, giving attackers unlimited time to crack it;
Short-range: This attack must be performed quickly while the transaction is in the mempool.
The latter type of attack is possible due to the disclosure of the public key during the spending of coins. It requires powerful CRQCs to be successful, as it must be carried out in a short period of time. In the early stages of CRQC development, Long-range attacks are more likely, where the public key is known in advance.
Short-range attacks are vulnerable to any transactions in the mempool, while Long-range attacks target:
P2PK (Satoshi coins, CPU miners);
reusable addresses (any type);
extended public keys wallets (also known as xpub);
Taproot addresses (start with bc1p).
The table below informs Bitcoin users whether their coins are vulnerable to a Long-range attack:
In an interview with Unchained Hunter, Beast explained the vulnerability of Taproot addresses:
"Unfortunately, Taproot contains an on-chain short version of the public key - the x-coordinate of the elliptic curve point. This information is enough to reconstruct the full public key."
Satoshi's Shield
Coinbase public key transactions (P2PK) go all the way up to block #200,000. Most of them hold 50 BTC.
Hunter Beast calls these coins “Satoshi’s shield.” He believes that any address with a balance of less than 50 BTC can be considered economically unprofitable to attack.
“For this reason, those who want to be prepared for a quantum emergency are advised to store no more than 50 BTC in a single unused Native SegWit address (P2WPKH, bc1q). This assumes that the attacker is motivated by financial considerations and is not, for example, a nation state seeking to undermine confidence in Bitcoin,” he says.
QuBit
BIP-360 could be the first proposal under QuBit, a soft fork that will make the first cryptocurrency resistant to quantum attacks.
“A qubit is the fundamental unit of quantum computing, and the capital B stands for Bitcoin. The name QuBit also rhymes somewhat with SegWit,” BIP-360 says.
The proposal introduces a new type of address that begins with bc1r. P2QRH is proposed to be implemented on top of P2TR, combining classical Schnorr signatures with post-quantum cryptography.
"This hybrid cryptography allows for no loss of security in the event of a vulnerability in one of the signature algorithms used. The key difference between P2QRH and P2TR is that P2QRH encodes a hash of the public key. This is a significant departure from how Taproot works, but it is necessary to avoid exposing public keys on-chain," says the author of BIP-360.
P2QRH uses the HASH256 algorithm to hash the public key. This allows for smaller new outputs and increased security since the public key itself is not revealed on-chain.
BIP-360 proposes the implementation of FALCON signatures. Once approved, it is planned to add SQIsign and other post-quantum algorithms: SPHINCS+, CRYSTALS-Dilithium. The SQIsign specification states that this algorithm has the smallest total size among known post-quantum schemes.
FALCON is approximately four times larger than SQIsign and 20 times larger than Schnorr signatures.
“FALCON is a more conservative approach than SQIsign. Its use has recently been approved by NIST, which simplifies implementation by achieving consensus in the scientific community. However, even SQIsign signatures are approximately five times larger than Schnorr signatures. This means that to maintain current transaction throughput, the witness discount will likely need to be increased in the QuBit soft fork. This will be specified in a future QuBit BIP,” the proposal says.
Hash-based cryptosystems are more conservative and time-tested. Lattice cryptography is relatively new and brings new security assumptions to Bitcoin, but its signatures are smaller and may be considered by some to be an adequate alternative to hash-based signatures. The SQIsign algorithm is much smaller, but it is based on a new form of cryptography and has not yet been approved by NIST or the wider community at the time of publication.
According to BIP-360, the inclusion of four cryptosystems is due to the need to support hybrid cryptography, especially for large outputs like exchange cold wallets. A library similar to libsecp256k1 will be developed to accommodate the update.
Hunter Beast admits that after the implementation of P2QRH, there will be a need for Pay to Quantum Secure (P2QS) addresses:
"There is a distinction between cryptography that is simply resistant to quantum attacks and cryptography that is secured using specialized quantum hardware. P2QRH is resistant to quantum attacks, while P2QS is quantum secure. They will require specialized quantum hardware to sign, but they will use public keys that can be verified classically. P2QS will require additional BIPs to implement."
While quantum cryptography hardware is not yet widely available, quantum-resistant addresses may serve as an acceptable interim solution.
Quantum transition
In October 2024, researchers at the University of Kent published a study that calculated the time it would take to transfer bitcoins to quantum-resistant addresses.
"We calculate a lower bound on the total time required for the above transition to be 1827.96 hours (or 76.16 days). We also show that the transition must be completed before quantum devices break ECDSA to ensure the security of Bitcoin," the study says.
In his presentation at the Future of Bitcoin 2024 conference, Casa CTO Jameson Lopp calculated that it would take at least 20,500 blocks (or 142 days) to migrate all UTXOs.
"But it's probably much more, because this is the most optimistic scenario, where the Bitcoin network is used exclusively for migration. Such expectations are certainly unrealistic. The process could take years. We have to be conservative and assume that it could take many years," Lopp says.
He concluded that even if the quantum threat seems like a distant prospect, it is better to start talking about it “sooner rather than later.”
Conclusions
Over the years, Bitcoin has faced various FUDs: 51% attacks, government bans, altcoin competition, and the threat of quantum computers. These issues are regularly discussed in the community, but so far the first cryptocurrency has demonstrated resilience to various challenges.
"After the ETF adoption and BlackRock's educational videos on Bitcoin, no one is talking about bans anymore. Concerns about a 51% attack have always been exaggerated, and its impact on the network is extremely limited," Mixer.Money representatives note.
The quantum threat is deeper, but the proposed QuBit soft fork shows that developers are well aware of it. Ethereum’s roadmap also takes quantum resistance into account, and the Bitcoin community can learn useful lessons from these developments.
"However, it is worth noting that another hard fork is enough for Ethereum to undergo a quantum transition. In Bitcoin, everything is more complicated: there are no hard forks, and Satoshi's bitcoins cannot simply be frozen - this would undermine the fundamental principles of the first cryptocurrency," Mixer.Money believes.
The possible fate of the Satoshi Shield and other coins that do not migrate to quantum-resistant addresses remains unclear. Bitcoin developer Luke Dash Jr. believes that in the future, such coins could be considered the equivalent of mining.
“In the end, the 37% of supply mined by quantum computers is no different from the 37% mined by ASIC miners,” he said.