How feasible is migration to Quantum-Resistant Signatures in Bitcoin?

[MarryWithBTC]

The discussion around Bitcoin and quantum computing often swings between two extremes:

• It is dismissed as pure FUD (as some have argued).
• It is treated as an inevitable cryptographic apocalypse.

I’m not interested in either framing, i’m just looking for a technical answer.

My question: Is it accurate to call the quantum threat a “myth”?:  If sufficiently advanced quantum systems are developed in the future, could exposed public keys practically theoritically become vulnerable?

We know Bitcoin is not static (it’s still labeled beta, after all). So, signature schemes can be upgraded.

Now a second question follows:
If a large-scale quantum computer capable of breaking secp256k1 were eventually built, is migration to quantum-resistant cryptography technically feasible within Bitcoin’s consensus model?
In other words, my real concern is’nt whether quantum computers exist today. It is rather; if Bitcoin can adapt before such machines become practically usable.
Bitcoin’s history shows strong adaptability, but cryptographic transitions are not trivial. i would be interested in hearing technical perspectives on how realistic such a migration would be.

[NotFuzzyWarm]

Read some of the numerous existing threads about QC & BTC.You will find your questions have already been answered many many times...

[stwenhao]

Is it accurate to call the quantum threat a “myth”?

Currently? Yes. In the future? Nobody knows.

If sufficiently advanced quantum systems are developed in the future, could exposed public keys practically theoritically become vulnerable?

Theoretically? They can be broken, without any quantum computers at all. For each and every valid public key, there is one, and only one valid private key. In smaller curves, you can see it exactly, how public keys are turned into private keys. In bigger ones, it is exponentially harder, but during curve construction, the total number of keys is calculated, and is mathematically proven to be correct.

is migration to quantum-resistant cryptography technically feasible within Bitcoin’s consensus model?

Yes. You will have just a new address type, with a different cryptography. We already migrated from ECDSA to Schnorr signatures. Migration to "foobar signatures" can be done in exactly the same way. I said "foobar", because it is not yet sure, what exactly will be picked. There are some proposals, but nothing is set in stone yet.

if Bitcoin can adapt before such machines become practically usable

Technically? Yes. Socially and politically? Nobody knows. Even if new signatures would be deployed tomorrow, it is unknown, how long it would take for people to upgrade, and how many people will refuse to do so, for various reasons.

i would be interested in hearing technical perspectives on how realistic such a migration would be

Instead of "OP_1 <taproot_key>", you would have something like "OP_2 <quantum_key>", or something similar. And maybe that key will be hashed, when people will scream, that hashing with many collisions is more difficult to break than provably collisionless secp256k1. Or if these things would take too much space, when used, so they will be moved to inputs.

By the way, the main reason why Satoshi hashed public keys, was because of space. Public keys took 65 bytes in uncompressed form, then 32 bytes after SHA-256, and then 20 bytes after RIPEMD-160. Maybe quantum keys will also be hashed, just to make outputs smaller.

[BattleDog]

Also worth separating "quantum breaks Bitcoin" from "quantum breaks keys that are already exposed." A lot of UTXOs are still sitting behind a hash of a pubkey, so there's no pubkey on-chain until you spend. Those are in better shape in a Shor-doomsday timeline than anything that's already published a raw pubkey in the output script (old P2PK, and yes, Taproot outputs are literally a pubkey on-chain).

If you're trying to be rational-paranoid today, the lowest-effort move is boring: stop address reuse, keep long-term coins in hashed-pubkey outputs, and don't be the guy broadcasting the same pubkey to the world for a decade like it's a bumper sticker.

[ABCbits]

We know Bitcoin is not static (it’s still labeled beta, after all). So, signature schemes can be upgraded.

Yeah, Bitcoin isn't static. There are many forks that upgrade/change Bitcoin protocol. But do you say "labeled beta" that because Bitcoin Core claim it's experimental software on the about page?

if Bitcoin can adapt before such machines become practically usable

Technically? Yes. Socially and politically? Nobody knows. Even if new signatures would be deployed tomorrow, it is unknown, how long it would take for people to upgrade, and how many people will refuse to do so, for various reasons.

We can roughly estimate minimum time required for migration, based on block size, total "old" UTXO (that doesn't use QC resistant signature) and average TX size for the migration purpose (while estimate average "old" UTXO).

I also recall one of BIP 360 author make speculation that 90% people/UTXO will migrate within 5 years, although it seems he don't explain in detail.

[Lucius]

~snip~

if Bitcoin can adapt before such machines become practically usable

Technically? Yes. Socially and politically? Nobody knows. Even if new signatures would be deployed tomorrow, it is unknown, how long it would take for people to upgrade, and how many people will refuse to do so, for various reasons.

I wonder why someone would refuse to move their coins to an address that would theoretically be resistant to a quantum computer attack - is there perhaps some pitfall/risk in that?

I know that even today there are those who for some reason do not want to use SegWit, but it's just about someone saving on fees and those who hold long-term do not feel threatened - but if the quantum threat became real, I don't know what anyone would cite as a meaningful reason not to secure their coins.

[philipma1957]

Also worth separating "quantum breaks Bitcoin" from "quantum breaks keys that are already exposed." A lot of UTXOs are still sitting behind a hash of a pubkey, so there's no pubkey on-chain until you spend. Those are in better shape in a Shor-doomsday timeline than anything that's already published a raw pubkey in the output script (old P2PK, and yes, Taproot outputs are literally a pubkey on-chain).

If you're trying to be rational-paranoid today, the lowest-effort move is boring: stop address reuse, keep long-term coins in hashed-pubkey outputs, and don't be the guy broadcasting the same pubkey to the world for a decade like it's a bumper sticker.

Broadcasting the same pubkey addresses is what satoshi has done since 2009-2011.

 Pretty good advertisement that cracking them is not
POSSIBLE.

Since he is doing that for us for no charge. WE can take advantage and move from older addresses

[BlackHatCoiner]

I wonder why someone would refuse to move their coins to an address that would theoretically be resistant to a quantum computer attack - is there perhaps some pitfall/risk in that?

People resist making the first move out of fear, so it will not surprise me if it takes a long time for the migration. Remember how much time it took to move from Legacy to Segwit and how little Taproot usage there is today even after so many years.

A good argument as to why people might not feel entirely confident with the quantum-safe addresses is that the quantum math might break and a classical computer can break them before a quantum is capable of being a threat.

[NotATether]

Would Bech32m still be used in such a case?

For instance, let's suppose that we have a keypads generated by some quantum-safe curve. Then you also presumably have to replace SHA256 and RIPEMD160 with something else which then adjusts the final payload size, violating BIP 142 constraints.

Or do we keep a RIPEMD160 hash last for compatibility purposes, hash it again with something else, and accept that people will be able to peel off one layer of the onion?

[stwenhao]

Then you also presumably have to replace SHA256 and RIPEMD160 with something else

Breaking secp256k1 is a different thing, than breaking SHA-256. If you can break this hash function, then it affects mining, merkle root construction, and many other things.

Which means, that SHA-256 will stay as it is. And even if it will be upgraded anyhow, then still: it will be similar as to what was done to SHA-1, when hardened SHA-1 was created. But even then, OP_SHA1 is still executed in the old way, just like it was. Which is why 37k7toV1Nv4DfmQbmZ8KuZDQCYK9x5KpzP is still spendable.

By the way: there are challenges for hash function collisions, and puzzles for SHA-256 or RIPEMD-160 are still unsolved.

[Satofan44]

~snip~

if Bitcoin can adapt before such machines become practically usable

Technically? Yes. Socially and politically? Nobody knows. Even if new signatures would be deployed tomorrow, it is unknown, how long it would take for people to upgrade, and how many people will refuse to do so, for various reasons.

I wonder why someone would refuse to move their coins to an address that would theoretically be resistant to a quantum computer attack - is there perhaps some pitfall/risk in that?

Don't waste time on such thoughts as they are pointless. Average people do all sorts of stupid things for stupid reasons. There are people who still have legacy addresses, I am not talking about addresses before SegWit I am talking about P2PK which are the most vulnerable types of addresses when it comes to this topic. You can find also all kinds of stupid reasoning for other decisions, refusing to update Core to some version, refusing to use LN at any cost and so forth it goes.

I know that even today there are those who for some reason do not want to use SegWit, but it's just about someone saving on fees and those who hold long-term do not feel threatened - but if the quantum threat became real, I don't know what anyone would cite as a meaningful reason not to secure their coins.

Don't confuse good reasons with meaningful reasons. Anyone can draw any kind of stupid reason, and no matter how wrong it is, they can assign meaning to it. Many people in the modern world are lost, they have no purpose and some of these acts are their own way of coping with their own failure -- vanity and other bullshit.

Then you also presumably have to replace SHA256 and RIPEMD160 with something else

Breaking secp256k1 is a different thing, than breaking SHA-256. If you can break this hash function, then it affects mining, merkle root construction, and many other things.

Exactly, breaking SHA-256 is the least probably scenario of quantum computers. Given the number of unknowns today and the number of assumptions that are made when talking about these theoretical discussions, this topic can be completely ignored right now. We should focus where we are primarily vulnerable, and design ways to deal with various scenarios of the future. That we need new signatures is clear. The question is which ones, and the other question is how to deal with those that don't upgrade (for whatever reason) starting with the oldest addresses. If we were a centralized shitcoin like ETH it would be simple, you have 6 months to upgrade and anyone who does not will be unable to spend their coins. That is how many shitcoin projects did various transitions from different tokens within the same blockchain or across different blockchains.

[MarryWithBTC]

We know Bitcoin is not static (it’s still labeled beta, after all). So, signature schemes can be upgraded.

Yeah, Bitcoin isn't static. There are many forks that upgrade/change Bitcoin protocol. But do you say "labeled beta" that because Bitcoin Core claim it's experimental software on the about page?

Searched the github to confirm what Achow101 said years ago.

Bitcoin Core still (intentionally) contains a line that says "this software is experimental". The line saying that Bitcoin Core is beta software was removed in 2014.

Even though the beta line is removed, Bitcoin Core still acknowledges it is experimental.

I read from a post, that was actually a factoid in the early days.

FACTOID THREE:
 Remember that Bitcoin is still beta software. Don't put all of your money into BTC!
My Question or Input:
I know that BTC is still in the beta software. I also know that it is not good to put all your money in BTC. But, will there ever be an upgrade from the beta version of BTC and when will this happen?

I wonder why someone would refuse to move their coins to an address that would theoretically be resistant to a quantum computer attack - is there perhaps some pitfall/risk in that?

I know that even today there are those who for some reason do not want to use SegWit, but it's just about someone saving on fees and those who hold long-term do not feel threatened - but if the quantum threat became real, I don't know what anyone would cite as a meaningful reason not to secure their coins.

I think the hesitation may come from cold storages, lost keys, inactive hodlers. Also people could fear unforeseen bugs in the new cryptography. Humans are afraid of change, especially when they are not part of those that implemented the change.

I'm curious: would a mandatory migration via hard fork ever be acceptable, if the danger looms and there is slow migration.