Bitcoin Vulnerabilities in Mining, Signatures and Transactions to Quantum Computers

by

Quantum computers leverage some aspects of quantum physics to make computers. They can create huge amounts of quantum states but it is also difficult to make the actual algorithms to use the abundant states. A classical (regular) computer would need more atoms than are in the entire universe to match the number of quantum stats in a 500-qubit quantum computer.

Quantum computers have huge problems with errors. The errors and noise can prevent those who use quantum computers from being able to get the answers. The quantum system could generate the correct answer but this is useless if the answer is still a needle in a universe scale haystack.

There was a breakthrough in error corrected quantum computers announced last week and QuEra has the goal in 2025 of 100 logical qubits with thousands of times reduction in error. If they achieve this goal, then quantum computer systems that could impact Bitcoin security could arrive in the 2026-2029 timeframe. When quantum computers start getting close to being a major threat then trading around Bitcoin and bank financial security could be a factor.

There is a 2017 research paper on Arxiv that analyzed Quantum Computer attacks on Bitcoin.

Attack on Mining

Using Grover search [Gro96], a quantum computer can perform the hashcash PoW (proof of work) by performing quadratically fewer hashes than is needed by a classical computer. However, the extreme speed of current specialized ASIC hardware for performing the hashcash PoW, coupled with much slower projected gate speeds for current quantum architectures, essentially negates this quadratic speedup, at the current difficulty level, giving quantum computers no advantage. Future improvements to quantum technology allowing gate speeds up to 100GHz could allow quantum computers to solve the PoW about 100 times faster than current technology.

A vastly superior quantum computer that suddenly appears as a fellow miner, produces 2,016 empty blocks in 1 minute, and then disappears just as suddenly. That would increase Bitcoin mining difficulty by 20,160 times. All the traditional miners in the world would then have to work for 140 days instead of 10 minutes to find the hash value of a single block. Not a single Bitcoin transaction could go through in the blockchain during this time.

Attack on Signatures

Signatures in bitcoin are made using the Elliptic Curve Digital Signature Algorithm based on the secp256k1 curve. The security of this system is based on the hardness of the Elliptic Curve Discrete Log Problem (ECDLP). While this problem is still believed to be hardclassically, an efficient quantum algorithm to solve this problem was given by Shor [Sho99]. This algorithm means that a sufficiently large universal quantum computer can efficiently compute the private key associated with a given public key rendering this scheme completely insecure.

The implications for bitcoin are the following:

1. (Reusing addresses) To spend bitcoin from an address the public key associated with that address must be revealed. Once the public key is revealed in the presence of a quantum computer the address is no longer safe and thus should never be used again. While always using fresh addresses is already the suggested practice in Bitcoin, in practice this is not always followed. Any address that has bitcoin and for which the public key has been revealed is completely insecure.

2. (Processed transactions) If a transaction is made from an address which has not been spent from before, and this transaction is placed on the blockchain with several blocks following it, then this transaction is reasonably secure against quantum attacks. The private key could be derived from the published public key, but as the address has already been spent this would have to be combined with out-hashing the network to perform a double spending attack. As we have seen in Section III A, even with a quantum computer a double spending attack is unlikely once the transaction has many blocks following it.

3. (Unprocessed transactions) After a transaction has been broadcast to the network, but before it is placed on the blockchain it is at risk from a quantum attack. If the secret key can be derived from the broadcast public key before the transaction is placed on the blockchain, then an attacker could use this secret key to broadcast a new transaction from the same address to his own address. If the attacker then ensures that this new transaction is placed on the blockchain first, then he can effectively steal all the bitcoin behind the original address.

The unprocessed transactions the most serious attack. To determine the seriousness of this attack it is important to precisely estimate how much time it would take a quantum computer to compute the ECDLP, and if this could be done in a time close to the block interval.

3 thoughts on “Bitcoin Vulnerabilities in Mining, Signatures and Transactions to Quantum Computers”

  1. Brian, is there a reason my comment about old dormant wallets suddenly becoming active around the time Q* emerged hasn’t posted?

    It was made at the same approximate time as my post about converting laser sails into a plasma was made, which posted right away.

    That was a couple of days ago.

    If there was something wrong with my post, please let me know.

    Thanks.

Comments are closed.