2023-06-28
7745
Will quantum computers destroy Bitcoin?
This question is related to whether it is possible to generate an arbitrary SHA256 collision within a meaningful timeframe. (Reference: What is a Hash Function?)
SHA256 is a hash function that takes arbitrary input and produces a fixed 256-bit number as output, usually represented as a 64-character hexadecimal value. While SHA256 is generally assumed to be collision-resistant, the variety of digital data is infinite, while the SHA256 output is limited to 256 bits. Therefore, according to the pigeonhole principle, if more than 2^256 different inputs are given, a collision will inevitably occur. In other words, if a computer with incredibly fast performance capable of performing 2^256 operations quickly exists, it can easily find collisions in arbitrary SHA256 hash values. So, how large is 2^256? For convenience, let's approximate it to about 10^77.
Currently, the hash rate of the Bitcoin network is an average of 350 EH/s, which means it performs 3.5 * 10^20 SHA256 calculations per second and 10^28 calculations per year. At this rate, the Bitcoin network will inevitably find a SHA256 collision within the next 10^49 years. So, how long is 10^49 years? Considering that the age of the universe is estimated to be 'only' about 1.38 * 10^10 years, it is practically impossible to find a SHA256 collision using current computing technology.
So, what about quantum computers?
Most people's image of quantum computers is that they are 'incredibly fast computers.' However, this is not an accurate understanding. Quantum computers are specialized machines that can efficiently solve specific problems using special quantum algorithms, such as Shor's algorithm, which can factor integers in polynomial time. Some of these problems include the decryption of public key cryptosystems like RSA and ECDSA (Elliptic Curve Digital Signature Algorithm), which Bitcoin uses to implement the public-private key relationship. However, no efficient method for finding arbitrary SHA256 hash collisions with a quantum computer is known yet. While there is Grover's algorithm, it merely allows for the increase of the bit length of the cryptographic system to easily counteract it.
Furthermore, examining the process by which Bitcoin addresses are derived, we see that a Bitcoin address is not simply the public key obtained by applying ECDSA to the private key. Instead, two additional hashing processes are applied using SHA256 and RIPEMD160. Therefore, if there is no efficient way to quickly find hash collisions for SHA256 and RIPEMD160, it is virtually impossible to determine the private key from a Bitcoin public address. Even if such a method existed, the probability that the input found to create the collision corresponds to the public key of that address would be extremely low.
In conclusion, if quantum computers develop rapidly to the point of becoming a visible threat, this would cause significant damage to the global military, economic, and financial sectors that extensively use RSA and ECDSA. However, Bitcoin would still be the fastest to adapt and prevent adverse outcomes.
The Bitcoin community is already researching the implementation of new signature schemes that follow quantum-resistant signatures. This implementation is also considered feasible as a soft fork, similar to how SegWit and Taproot implemented new scripts for locking and using Bitcoin.
However, even in this case, for addresses that use the P2PK script, where 'the address itself is the public key', like those from the early Satoshi era, it would become possible to derive the private key from the address. Therefore, the possibility of these coins entering the market could arise.
Additionally, since transactions waiting in the mempool contain public keys, if an attacker exists who can quickly reverse-engineer the private key using that public key, they could double-spend the coins from that address and move them elsewhere.
What would happen if arbitrary collisions of SHA256 and RIPEMD160 could be found?
1. In this case, it would still be nearly impossible to determine the private key from an arbitrary Bitcoin address. Even if an input producing the same hash value as the public key used to generate these addresses were found, the probability that it would be the public key for that address would be extremely low.
2. However, mining would become significantly easier, and the network difficulty would adjust accordingly to stabilize the creation of one block every 10 minutes. At that time, unless one were using a quantum computer designed for this purpose, they would not be competitive in mining.
Nevertheless, as mentioned earlier, the collapse of SHA256 is considered highly unlikely, making it practically not a concern compared to the potential exposure of ECDSA vulnerabilities.
In summary:
- SHA256 will remain safe even with the emergence of highly capable quantum computers. The difficulty will simply increase accordingly, and the hash rate will rise, enhancing the network's security.
- ECDSA could become vulnerable if quantum computers become sufficiently powerful. However, since Bitcoin addresses are derived through two additional hashing functions (SHA256 and RIPEMD160) after applying ECDSA, they will remain secure until a method to produce arbitrary collisions in SHA256 is discovered. Even if such a method is found, the probability that the input causing the collision corresponds to the public key of that address is extremely low.
- If a situation arises where private keys can be reverse-engineered in a timely manner, it could enable double-spending attacks on transactions waiting in the mempool that have exposed public keys. Also, UTXOs in the era of Satoshi, P2PK addresses will become vulnerable.
- Research is ongoing into new Bitcoin scripts with quantum resistance, and it will be possible to implement them through a soft fork update.
References:
1. Will quantum computing break SHA-256 encryption?
2. Quantum Computers Break Encryption in China But Far From Cracking Bitcoin
3. 사토시가 사라지기 전, 그가 남긴 기록들 - 1분 비트코인
4. SHA-256 충돌은 왜 발견되지 않았을까?
5. @atomicBTC - Will quantum computer kill bitcoin?
6. Committing to Quantum Resistance, Better: A Speed-and-Risk-Configurable Defence for Bitcoin against a Fast Quantum Computing Attack
2024-12-11 added
7. BIP-P2QRH(Pay to Quantum Resistant Hash)
2025-04-09 added
8. BIP-0360 (Pay to Quantum Resistant Hash)
Most people's image of quantum computers is that they are 'incredibly fast computers.' However, this is not an accurate understanding. Quantum computers are specialized machines that can efficiently solve specific problems using special quantum algorithms, such as Shor's algorithm, which can factor integers in polynomial time. Some of these problems include the decryption of public key cryptosystems like RSA and ECDSA (Elliptic Curve Digital Signature Algorithm), which Bitcoin uses to implement the public-private key relationship. However, no efficient method for finding arbitrary SHA256 hash collisions with a quantum computer is known yet. While there is Grover's algorithm, it merely allows for the increase of the bit length of the cryptographic system to easily counteract it.
Furthermore, examining the process by which Bitcoin addresses are derived, we see that a Bitcoin address is not simply the public key obtained by applying ECDSA to the private key. Instead, two additional hashing processes are applied using SHA256 and RIPEMD160. Therefore, if there is no efficient way to quickly find hash collisions for SHA256 and RIPEMD160, it is virtually impossible to determine the private key from a Bitcoin public address. Even if such a method existed, the probability that the input found to create the collision corresponds to the public key of that address would be extremely low.
In conclusion, if quantum computers develop rapidly to the point of becoming a visible threat, this would cause significant damage to the global military, economic, and financial sectors that extensively use RSA and ECDSA. However, Bitcoin would still be the fastest to adapt and prevent adverse outcomes.
The Bitcoin community is already researching the implementation of new signature schemes that follow quantum-resistant signatures. This implementation is also considered feasible as a soft fork, similar to how SegWit and Taproot implemented new scripts for locking and using Bitcoin.
However, even in this case, for addresses that use the P2PK script, where 'the address itself is the public key', like those from the early Satoshi era, it would become possible to derive the private key from the address. Therefore, the possibility of these coins entering the market could arise.
Additionally, since transactions waiting in the mempool contain public keys, if an attacker exists who can quickly reverse-engineer the private key using that public key, they could double-spend the coins from that address and move them elsewhere.
What would happen if arbitrary collisions of SHA256 and RIPEMD160 could be found?
1. In this case, it would still be nearly impossible to determine the private key from an arbitrary Bitcoin address. Even if an input producing the same hash value as the public key used to generate these addresses were found, the probability that it would be the public key for that address would be extremely low.
2. However, mining would become significantly easier, and the network difficulty would adjust accordingly to stabilize the creation of one block every 10 minutes. At that time, unless one were using a quantum computer designed for this purpose, they would not be competitive in mining.
Nevertheless, as mentioned earlier, the collapse of SHA256 is considered highly unlikely, making it practically not a concern compared to the potential exposure of ECDSA vulnerabilities.
In summary:
- SHA256 will remain safe even with the emergence of highly capable quantum computers. The difficulty will simply increase accordingly, and the hash rate will rise, enhancing the network's security.
- ECDSA could become vulnerable if quantum computers become sufficiently powerful. However, since Bitcoin addresses are derived through two additional hashing functions (SHA256 and RIPEMD160) after applying ECDSA, they will remain secure until a method to produce arbitrary collisions in SHA256 is discovered. Even if such a method is found, the probability that the input causing the collision corresponds to the public key of that address is extremely low.
- If a situation arises where private keys can be reverse-engineered in a timely manner, it could enable double-spending attacks on transactions waiting in the mempool that have exposed public keys. Also, UTXOs in the era of Satoshi, P2PK addresses will become vulnerable.
- Research is ongoing into new Bitcoin scripts with quantum resistance, and it will be possible to implement them through a soft fork update.
References:
1. Will quantum computing break SHA-256 encryption?
2. Quantum Computers Break Encryption in China But Far From Cracking Bitcoin
3. 사토시가 사라지기 전, 그가 남긴 기록들 - 1분 비트코인
4. SHA-256 충돌은 왜 발견되지 않았을까?
5. @atomicBTC - Will quantum computer kill bitcoin?
6. Committing to Quantum Resistance, Better: A Speed-and-Risk-Configurable Defence for Bitcoin against a Fast Quantum Computing Attack
2024-12-11 added
7. BIP-P2QRH(Pay to Quantum Resistant Hash)
2025-04-09 added
8. BIP-0360 (Pay to Quantum Resistant Hash)
10
