Deloitte Article on Threat of Quantum Computers

[pushups44]

Here is an interesting article from Deloitte: https://www2.deloitte.com/nl/nl/pages/innovatie/artikelen/quantum-computers-and-the-bitcoin-blockchain.html

Does anyone have any idea how consensus will be established to make bitcoin quantum resistant? Or when this will likely be implemented?

Excerpts:

What can one do to mitigate the risk of Bitcoins being stolen by an adversary with a quantum computer?

In the previous section we explained that p2pk and reused p2pkh addresses are vulnerable to quantum attacks. However, p2pkh addresses that have never been used to spend Bitcoins are safe, as their public keys are not yet public. This means that if you transfer your Bitcoins to a new p2pkh address, then they should not be vulnerable to a quantum attack.

The issue with this approach is that many owners of vulnerable Bitcoins have lost their private keys. These coins cannot be transferred and are waiting to be taken by the first person who manages to build a sufficiently large quantum computer. A way to address this issue is to come to a consensus within the Bitcoin community and provide an ultimatum for people to move their coins to a safe address. After a predefined period, coins in unsafe addresses would become unusable (technically, this means that miner will ignore transactions coming from these addresses). Such a drastic step needs to be considered carefully before implemented, not to mention the complexity of achieving consensus about such a sensitive issue.

Here's a similar article: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6030263/

In the light of the emerging threat of QCAs in Bitcoin, we have outlined how Bitcoin could become subject to theft of funds rooted in the exposure of public keys. Thus, we have proposed a commit–delay–reveal scheme to allow for the secure transition to a quantum-resistant address scheme in Bitcoin, the underlying protocol modifications for which can be implemented as a soft fork. For the security of the transition scheme we emphasize the need for a sufficiently long delay period and propose an initial period of six months in order to prevent possible blockchain reorganization. The proposed time frame should suffice for allowing honest clients and miners to reach consensus on manually rejecting long-range forks that exceed the delay period. However, we suggest that by intuitive continuity arguments there must exist some length of chain-rewind time where the community would be indecisive on how to proceed given that a conflicting branch created by an adversary exists. Hence, we note that the optimal duration of the delay period may be subject to future discussion and analysis.

[BlackHatCoiner]

I'm afraid the abandoned p2pk addresses are doomed to be compromised sometime in the future. Is that 5 years? 10? 20? Their public keys are exposed, their private keys are likely to be found one day. The problem is that they're abandoned. If came into an agreement to move to a quantum-resistant algorithm, the owners could secure their funds.

However, if the owners have lost their keys, they can't move them. And the community will, hopefully, never agree on transfering money without the permission of their owners. That would be unconstitutional.

This means that if you transfer your Bitcoins to a new p2pkh address, then they should not be vulnerable to a quantum attack.

Debatable. What if the algorithm is strong enough to compromise a private key while the transaction is still in the mempool?

[o_e_l_e_o]

Does anyone have any idea how consensus will be established to make bitcoin quantum resistant? Or when this will likely be implemented?

There are a number of quantum resistant algorithms which we could potentially fork to, but many are still in the infancy of their development. The one we end up using is probably still largely unfamiliar to most people today. Not to worry though, we have decades before quantum computing becomes a serious threat.

This won't be difficult to reach consensus on, I would imagine. Everyone is in agreement that bitcoin will need to move to a quantum resistant algorithm when the time comes. There may be a debate over which algorithm or exactly how to implement it, but everyone will agree it needs to happen. The far larger debate will be what to do with the coins which are at risk of being stolen. Every time this topic arises there are strong views on both sides and very little progress is made in reaching some kind of middle ground. My view is we should do nothing, and if the owners of those coins do not secure them in to quantum resistant addresses, then they will be stolen.

Debatable. What if the algorithm is strong enough to compromise a private key while the transaction is still in the mempool?

I think what the quote is saying is that if you send your coins to an unused P2PKH address now, then they will be safe from future quantum attacks.

[DaveF]

What most of these articles seem to be missing is the fact that when these addresses do become vulnerable some time in the future, unless a lot of other things are changed in the way people use encryption changes many more things will be vulnerable and most of them are worth a lot more money.

You think some p2pk and reused p2pkh are vulnerable. Try some older NFC / RFID cards. How about old web & internet services and so on.

I put stuff like this in the FUD pile and move on. Yes it's going to happen, yes people will loose money, and YES there will be a way to stop it long before it happens and yes some people will not do it. They are the same people who go to https://haveibeenpwned.com/ and find that the one password they use for everything has been compromised and still do not change it.

-Dave

[dkbit98]

Does anyone have any idea how consensus will be established to make bitcoin quantum resistant? Or when this will likely be implemented?

I read something about this few days ago and it's all related with Taproot upgrade that happened recently, this will enable to mitigate any quantum attacks, but I have no idea how exactly this will be achieved.
On the other hand, I remember few months ago some people screaming how Taproot is bad for privacy and it just increases possibility of quantum bugs.

EDIT:
I just remembered the source of information for my first sentence, it was from Trezor blog:

The concern over quantum computers has been going around for years, mostly leveraging the fact that currently utilized signature schemes (both ECDSA and Schnorr) are susceptible to the theoretical threat of sufficiently-advanced computers breaking the cryptography.
As Jeremy Rubins argues in his recent blog on the topic, a previously disabled Bitcoin opcode called OP-CAT could help in this regard. As we mentioned above, Taproot brings an easier implementation of new opcodes, and OP_CAT is among those under consideration, as it could help with use cases such as those described by Rubins.

https://blog.trezor.io/taproot-v2-how-will-the-latest-bitcoin-upgrade-evolve-in-the-future-e8559d0c5886

[j2002ba2]

Quantum computers are vastly inferior and super expensive to use devices. Selling QC as a "superior to classic computers" is a scam. There is only one quantum superiority - generating noise.

The biggest number factored by QC so far has only 19 bits. It's almost like one can find the factors faster by hand. Something more, it was done by "adiabatic quantum computer", which is useless for ECDLP. There is a fishy result of factoring 41 bit number, but it consists of mostly zeroes, and in fact is equivalent to factoring a 9 bit number.

Companies are making devices with more and more magical qbits, but the reality strikes back:

The largest number reliably factored by Shor's algorithm is 21 which was factored in 2012.

Yes, this is 5 bits. No improvement for 9 years. No better result from 53 qbit, or 127 qbit quantum computers.

This is what will happen one day: someone will discover an ECDLP algorithm and keep it to himself, nobody will know. In the event of NSA or the likes finding out such algorithm, they would claim it's done by using quantum computer, in order to lead astray everybody and keep the advantage.

[Ozero]

The proposed method to use the new p2pkh addresses, which have never been used to spend bitcoins, cannot effectively address the threat posed by quantum computers. Here it is really necessary to apply quantum-resistant algorithms to solve this issue radically. Hiding our bitcoins in new addresses so that they are not visible to quantum attacks is not an option. After all, it will still be necessary to make certain transactions with bitcoins.
We need to prepare for this now and not think that we still have a lot of time. Technologies do not stand still and there may appear those that will significantly speed up this process in time.

[kaggie]

Does anyone have any idea how consensus will be established to make bitcoin quantum resistant? Or when this will likely be implemented?
..
The issue with this approach is that many owners of vulnerable Bitcoins have lost their private keys. These coins cannot be transferred and are waiting to be taken by the first person who manages to build a sufficiently large quantum computer.

These are only assumptions.

The threat of quantum computing is overstated at present. Not all algorithms are susceptible for QC enabled cracking. You aren't going to easily replace your 5 GHz processors and algorithms tuned over decades with something that has been shown with a few qubits in a lab. It will be years if not several decades or longer before this becomes an issue.

Changing the consensus mechanisms of bitcoin prematurely would destroy its long term value prospects. To the point, if the algorithms are changed so rapidly that people can't store wealth for ~10 years, then it won't become the global settlement layer that it should be.

Finally, those vulnerable bitcoin are high prized targets that serve as a warning for when and if major QC enabled cracking became prevalent. Of course, those addresses are a small drop in the global bucket for the havoc that would be caused if someone had such capabilities without warning, but that makes them worthwhile to leave untouched. (Although if those addresses moved it could be misconstrued as QC becoming available..)

I see no point to rush this, as there could be worse flaws in future algorithms that we might prematurely assume would be safe. These addresses have done well enough so far, so they might be safe enough for a long while yet.

[unrealisticexpectations]

I would not worry much about quantum computer. Yeah sure they can potentially break SHA256 and public / private key crypto, however most of the modern web relies also on those technology.

Eg: when you login on your bank account you will do a key exchange with the bank website. If we can "trivially" break asymmetric encryption there are a lot of things that will be broken, not just bitcoin. Encrypted communications, online bank, e-commerce... It would be a massive crash / chaos around the world. Most of $$$ in the world is already transferred digitally and relies on the same encryption to secure the transfer of data.

What will happen is largely speculative but most likely we could do what other industries would do. If SHA256 can be solved faster, the network will simply adjust the difficulty, if pub/priv crypto and or hashing is is broken we could slowly enable and upgrade the protocol to quantum resistant cryptography. Due to the threat I expect the majority of node would agree to upgrade. Very similar to how early in the network with the buffer overflow exploit. There was a direct economic incentive for everyone to upgrade their node.

[o_e_l_e_o]

Hiding our bitcoins in new addresses so that they are not visible to quantum attacks is not an option.

Why not? It is a trivial thing to do.

After all, it will still be necessary to make certain transactions with bitcoins.

Of course. But it will be years between a quantum computer which can reverse elliptic curve multiplication, and a quantum computer which can elliptic curve multiplication in the 10 minutes it takes for a transaction to confirm.

Changing the consensus mechanisms of bitcoin prematurely would destroy its long term value prospects.

Not to mention that the post QC algorithms we have access to at the moment will undergo significant improvements and developments and have their own weaknesses discovered in the next 10-20 years. If we forked now, we might end up with a clunky solution with huge signatures and yet find we still need to fork again in the future.