Bitcoin, cryptos and the imminent threat of a Quantum Computer

[mpufatzis]

Many of us have heard about the Quantum Computer (QC).
Although it has been on an experimental stage yet, it is a matter of time to be built.
In one of his speeches, Antonopoulos said that a full working QC could have been in full function within the next decade.

So, when this happen, a QC could be a risk regarding all cryptocurrencies in the market.

Furthermore, to be more specific about what a QC is capable of it is that, a QC could mine all the rest coins in a few minutes, maybe, and break the keys of all the addresses.

Some people believe that there are more interesting fields for a QC to be used like medical research, industrial secrets, espionage (in general), than just have it for cryptos which it could meant extra time for us to get prepared for what is coming next.

In this forum, I have read many times about quantum resistant wallets / blockchain (whatever could be utilized to protect us). However, I have never heard of computer engineers able to develop a defence system, or any BTC team that would be ready to confront a possible QC threat.

Additionally, in case of a QC and a successful Quantum resistant ecosystem, a QC would allow somebody to break the keys of all the owners’ “lost” addresses because they themselves will not be able to change them on time to the new ecosystem field.
The “lost” coins (BTC or crypto) could be used again, contributing to the price.

Please, just imagine the scenario:
1 million or more BTC available in the exchanges, simultaneously!
BTC’s price, and the crypto ecosystem, could collapse instantly by selling  in a ridiculous cheap price.
This is the bad scenario.
A good one is, that the new owners could sell them, one by one, for fiat, to get rich, or to finance their QC research.

Do you think that all these could ever be a reality?
In my opinion, we are not allowed to think otherwise or ignore it.

It reminds me as I am thinking of the QC, the Enigma Engine and “Bombe”, the computer built by Alan Touring, who broke the German code.
Its existence was a top-secret and was finally revealed many decades later, in the ‘70s...

[bitmover]

It is silly to think that processing power will evolve and cryptography won't.

[ranochigo]

Furthermore, to be more specific about what a QC is capable of it is that, a QC could mine all the rest coins in a few minutes, maybe, and break the keys of all the addresses.

You cannot. The difficulty ensures that there is at least an increasing difficulty for mining. Unless you can consistently increase your hashpower AND outpace all the advanced ASICs that there is right now, you'll likely not be able to do so.

QC has not been proven to be able to break RIPEMD160 and SHA256 yet so breaking the keys to all the addresses is a stretch.

Some people believe that there are more interesting fields for a QC to be used like medical research, industrial secrets, espionage (in general), than just have it for cryptos which it could meant extra time for us to get prepared for what is coming next.

In this forum, I have read many times about quantum resistant wallets / blockchain (whatever could be utilized to protect us). However, I have never heard of computer engineers able to develop a defence system, or any BTC team that would be ready to confront a possible QC threat.

Trust me, when it is time, the mitigation would be quick. For now, it's definitely more than sufficient to defend against attacks if we don't reuse addresses. QC is not a magical machine that is able to break everything.

Additionally, in case of a QC and a successful Quantum resistant ecosystem, a QC would allow somebody to break the keys of all the owners’ “lost” addresses because they themselves will not be able to change them on time to the new ecosystem field.
The “lost” coins (BTC or crypto) could be used again, contributing to the price.

Please, just imagine the scenario:
1 million or more BTC available in the exchanges, simultaneously!
BTC’s price, and the crypto ecosystem, could collapse instantly by selling  in a ridiculous cheap price.
This is the bad scenario.
A good one is, that the new owners could sell them, one by one, for fiat, to get rich, or to finance their QC research.

Do you think that all these could ever be a reality?

How many of the addresses are lost AND their public keys are not revealed yet?

[joniboini]

However, I have never heard of computer engineers able to develop a defence system, or any BTC team that would be ready to confront a possible QC threat.

I'm not sure what you mean by BTC team, but discussion about this possible attack vector exists on the wiki and there's some solution mentioned already. Maybe you have to read further.

[Cnut237]

It is silly to think that processing power will evolve and cryptography won't.

Good point, but it doesn't solve the concern completely. Migration to newer system always takes times, especially when we're talking about P2P/distributed system where we need to make sure there's backward compatibility or majority agreed to upgrade their system (which incompatible with older system).

Yes. This does lead into the huge question of "lost" coins...

a QC would allow somebody to break the keys of all the owners’ “lost” addresses because they themselves will not be able to change them on time to the new ecosystem field.

Yes. If some consensus can be achieved on implementing a quantum-resistant system for bitcoin, the crucial point here is that in order to be safe against quantum attack, all coins will need to be moved to new, quantum-safe addresses. So what happens to coins that can't be moved because wallet-access has been lost, or the owners are deceased and the keys lost? What happens to Satoshi's bitcoins? The two options are a) leave the coins that aren't moved, and let them get stolen by a QC, or b) after some given grace period, burn any coins that haven't been moved to prevent any subsequent theft.

Obviously both solutions here are problematic and would be highly contentious, and go right to the core of what bitcoin, from an ideological perspective, is.

This has been discussed a lot over the years, and as far as I'm aware it remains an impasse. Meanwhile development of quantum computers continues apace...

QC is not a magical machine that is able to break everything.

Quite true. Asymmetric cryptography is hugely vulnerable to a QC running Shor's algorithm, but symmetric cryptography remains relatively unscathed under the best QC attack (Grover).

[NotATether]

Did you consider the learning curve and time it will take to train people to program a quantum computer, the time it will take them to code a bitcoin brute-forcer and the time it will take to test it? That gives us a few extra years of leeway, counting from the date that a quantum computer is commissioned for public commercial general-purpose use.

[pvmgg]

It is a game of cat and mouse, cryptocurrencies will have to adapt or die out, and by the time quantum computers reaches mass production we probably would have figured it out, unless a shady government is racing to production to break the current blockchain , which imo is unlikely

[HeRetiK]

Did you consider the learning curve and time it will take to train people to program a quantum computer, the time it will take them to code a bitcoin brute-forcer and the time it will take to test it? That gives us a few extra years of leeway, counting from the date that a quantum computer is commissioned for public commercial general-purpose use.

We don't have to wait for QC to be available for the general public to become a threat to Bitcoin's security. It should be considered critical as soon as a single government or corporation has access to a powerful-enough quantum computer.

Remember, Bitcoin's security proposition is that no single entity has the power to compromise it. That goes out the window as soon as the technology becomes available, even with limited access. But luckily even that is still many years out.

[Cnut237]

by the time quantum computers reaches mass production we probably would have figured it out

even that is still many years out.

We do need to remember that processing power of quantum computers can increase much more rapidly than we are accustomed to with classical computers.
With each extra bit, a classical computer has more possibilities, but can still only process one at a time. The difference with a quantum computer is the quantum superposition of states - all possible options can be tried simultaneously - so each time you add an extra qubit, the processing power doubles. 1 qubit - 2 states, 2 qubits 4 states, 3qubit 8 states and so on, effectively 2^n classical processors running in parallel.
But having said this I do agree that a QC that is a threat to bitcoin is likely some time away - it's just that the problems are more to do with phenomena such as decoherence, error rates and a near-absolute-zero temperature constraint, rather than, as we might think, the number of qubits. It's more single problems to be overcome than it is scaling up the processing power. Tremendously challenging problems, yes, but a different sort of problem to what we're used to thinking of in terms of computer advancement.

Did you consider the learning curve and time it will take to train people to program a quantum computer, the time it will take them to code a bitcoin brute-forcer and the time it will take to test it?

I don't think this is an issue. The algorithm already exists. Whilst a classical computer would take an unimaginably huge 2^128 operations to derive a bitcoin private key, with a QC running Shor this becomes a much more manageable 128^3.

[HeRetiK]

We do need to remember that processing power of quantum computers can increase much more rapidly than we are accustomed to with classical computers.
With each extra bit, a classical computer has more possibilities, but can still only process one at a time.

Processing power of quantum computers may increase more rapidly relative to classical computers but it does not in terms of qbits gained. Quantum computers still need to increase their processing power by a factor of 20-30 before things get interesting.

Did you consider the learning curve and time it will take to train people to program a quantum computer, the time it will take them to code a bitcoin brute-forcer and the time it will take to test it?

I don't think this is an issue. The algorithm already exists. Whilst a classical computer would take an unimaginably huge 2^128 operations to derive a bitcoin private key, with a QC running Shor this becomes a much more manageable 128^3.

That was my first thought as well, but just because the algorithm already exists doesn't mean it's necessarily easy to implement. I do assume development on implementing Shor's algorithm will start as soon as it's computationally possible though.

[Cnut237]

Processing power of quantum computers may increase more rapidly relative to classical computers but it does not in terms of qbits gained. Quantum computers still need to increase their processing power by a factor of 20-30 before things get interesting.

20 to 30x is only an extra 4 or 5 qubits, though (2^4=16, 2^5=32).

just because the algorithm already exists doesn't mean it's necessarily easy to implement. I do assume development on implementing Shor's algorithm will start as soon as it's computationally possible though.

Yes, you're right. I concede the point.

I suppose what I'm trying to say is that it's very difficult to estimate when a QC that is capable of cracking bitcoin might become available, and that we can't use the development history of classical computers as a guideline.  The challenges to building a workable, reliable large-scale QC do remain immense, but we are all aware that work is continuing at pace, and a QC threat to bitcoin may be with us soon than we might envisage. I do think it's important that making bitcoin quantum-safe be considered as a problem to resolve now, rather than at some indefinite point in the future.

[HeRetiK]

Processing power of quantum computers may increase more rapidly relative to classical computers but it does not in terms of qbits gained. Quantum computers still need to increase their processing power by a factor of 20-30 before things get interesting.

20 to 30x is only an extra 4 or 5 qubits, though (2^4=16, 2^5=32).

No, I mean literally in terms of qubits. Google latest quantum chip is at 72 qubits (up from 54 qubits last year). The estimates I found on how many qubits are required to break ECDSA are conflicting, but most sources place it at 1500-3000 qubits.

I suppose what I'm trying to say is that it's very difficult to estimate when a QC that is capable of cracking bitcoin might become available, and that we can't use the development history of classical computers as a guideline.  The challenges to building a workable, reliable large-scale QC do remain immense, but we are all aware that work is continuing at pace, and a QC threat to bitcoin may be with us soon than we might envisage. I do think it's important that making bitcoin quantum-safe be considered as a problem to resolve now, rather than at some indefinite point in the future.

Agreed.

[AdamBlade]

Processing power of quantum computers may increase more rapidly relative to classical computers but it does not in terms of qbits gained. Quantum computers still need to increase their processing power by a factor of 20-30 before things get interesting.

20 to 30x is only an extra 4 or 5 qubits, though (2^4=16, 2^5=32).

just because the algorithm already exists doesn't mean it's necessarily easy to implement. I do assume development on implementing Shor's algorithm will start as soon as it's computationally possible though.

Yes, you're right. I concede the point.

I suppose what I'm trying to say is that it's very difficult to estimate when a QC that is capable of cracking bitcoin might become available, and that we can't use the development history of classical computers as a guideline.  The challenges to building a workable, reliable large-scale QC do remain immense, but we are all aware that work is continuing at pace, and a QC threat to bitcoin may be with us soon than we might envisage. I do think it's important that making bitcoin quantum-safe be considered as a problem to resolve now, rather than at some indefinite point in the future.

Yes, this is undoubtedly a very important issue related to QS reliability issues. And it must be resolved immediately.

[Cnut237]

No, I mean literally in terms of qubits.

Thanks for the clarification - I was making a lazy assumption. But I do think that, in the end, we come back to this:

the problems are more to do with phenomena such as decoherence, error rates and a near-absolute-zero temperature constraint, rather than, as we might think, the number of qubits. It's more single problems to be overcome than it is scaling up the processing power. Tremendously challenging problems, yes, but a different sort of problem to what we're used to thinking of in terms of computer advancement.

It's not really adding extra qubits that's the problem, it's more ensuring that the quantum system is stable enough to allow sufficiently persistent and low-noise entanglement - and whilst obviously the challenges do increase as we scale up the number of qubits, if the challenges affecting low-qubit systems can be overcome, then adding extra qubits and scaling up the processing power is much less of a problem and is likely to happen very quickly.

[j2002ba2]

Processing power of quantum computers may increase more rapidly relative to classical computers but it does not in terms of qbits gained. Quantum computers still need to increase their processing power by a factor of 20-30 before things get interesting.

20 to 30x is only an extra 4 or 5 qubits, though (2^4=16, 2^5=32).

No, I mean literally in terms of qubits. Google latest quantum chip is at 72 qubits (up from 54 qubits last year). The estimates I found on how many qubits are required to break ECDSA are conflicting, but most sources place it at 1500-3000 qubits.

I suppose what I'm trying to say is that it's very difficult to estimate when a QC that is capable of cracking bitcoin might become available, and that we can't use the development history of classical computers as a guideline.  The challenges to building a workable, reliable large-scale QC do remain immense, but we are all aware that work is continuing at pace, and a QC threat to bitcoin may be with us soon than we might envisage. I do think it's important that making bitcoin quantum-safe be considered as a problem to resolve now, rather than at some indefinite point in the future.

Agreed.

The lowest number of physical qubits in order to break secp256k1 ECDSA is more than 10⁶ - yes, one million - and this is assuming at least 10 times better error rate, than the current record one. The 1-3k number is for perfect logical qbits. Additionally 10¹¹ Toffoli gates are needed. All this has to work in perfect sync without errors.

But I highly doubt it would ever work. Before spitting out a solution, the system would have to simultaneously represent 2²⁵⁶ states. Obviously all and every physical disturbance would destroy the state, and render the computation futile. A neutrino is enough to turn this billions dollars equipment useless.