SHA256 transition

[charlie137]

How would network transition from sha256 and remain its stability in the process? And very likely we would not be able to develop strong replacement without tools that would first allow us to break that very same sha256 (likely quantum tools ahah). Price stability right now is very heavy dependent on lost coins - but this would change dramatically during off-sha256 transition, or I am missing something?

[1714973892]

1714973892

[1714973892]

1714973892

[1714973892]

1714973892

[hatshepsut93]

First, SHA-256 isn't under big threat from quantum computers, they might be better at finding collisions, but not dramatically better like they are with cracking ECDSA. Also it's a very common misconception to think that you need a quantum computer to defend from quantum computers, in fact all you need is the right algorithm. Quantum computers aren't good because they are faster than classical computers, they just have certain properties that make them excel at certain specific things.

There's really no reason to worry about it, the whole world will be changing to post-quantum cryptography when/if the time will come, because it concerns everything, not just Bitcoin. Your bank account and payment cards, your browser, military communications, etc. If a powerful quantum computer was created tomorrow, we'd have far bigger problems than Bitcoin getting hacked.

[charlie137]

My bad, I didn’t really expanded there, but I mostly meant bruteforced collisions, assuming quantums’ extra state would allow seamless achievement on legacy (sha/ecdsa) scope.

Banking, military, utilities, etc - none of this is really relevant for the question since workflow around such common things is regulated/insured/etc. But with blockchain you your own bank, so you better be a competent one)

I am in no way worrying about this, not even close) I wish Id still be alive to observe such transition, but thats as likely as my wallet generate collision with satoshi private key) Just curious about the topic and possible approaches community could talk about already.

sha transition would mean almost all public hashes transition, so in that way it would be global parade indeed

[pooya87]

How would network transition from sha256 and remain its stability in the process?

first a vulnerability has to be found in SHA256 algorithm or some hardware has to be created that would be able to compute an enormous number of hashes in seconds for it to be at risk.
then we have to figure out if the problem is with Merkle–Damgård construction or with 256-bit size or something else so that we can choose a list of alternative hash algorithms.
finally the alternatives are explored and the best one is chosen and a hard fork is proposed. when it reaches supermajority support (>95% of the network) the hash algorithm used by bitcoin is changed to that new one.

Price stability right now is very heavy dependent on lost coins - but this would change dramatically during off-sha256 transition, or I am missing something?

price has very little to do with lost coins as they don't amass to enough to affect that much.
additionally lost coins have nothing to do with SHA256. you are confusing hash algorithm (SHA256) with asymmetric cryptography (ECC).

[o_e_l_e_o]

but I mostly meant bruteforced collisions, assuming quantums’ extra state would allow seamless achievement on legacy (sha/ecdsa) scope.

A quantum computer will not be able to bruteforce SHA256 collisions.

At best, a quantum computer can provide a quadratic speed up in this case, reducing the security of a SHA function from 2^x to 2^sqrt(x). So SHA256 would still require in the order of 2¹²⁸ operations, rather than 2²⁵⁶. 2¹²⁸ operations is still far too large for any current computer, and definitely far too large for the tiny quantum computers we have at the moment.

It is ECC which is vulnerable to quantum computers, not SHA, and would require bitcoin to transition to a quantum resistant signature scheme.

[Amph]

but I mostly meant bruteforced collisions, assuming quantums’ extra state would allow seamless achievement on legacy (sha/ecdsa) scope.

A quantum computer will not be able to bruteforce SHA256 collisions.

At best, a quantum computer can provide a quadratic speed up in this case, reducing the security of a SHA function from 2^x to 2^sqrt(x). So SHA256 would still require in the order of 2¹²⁸ operations, rather than 2²⁵⁶. 2¹²⁸ operations is still far too large for any current computer, and definitely far too large for the tiny quantum computers we have at the moment.

It is ECC which is vulnerable to quantum computers, not SHA, and would require bitcoin to transition to a quantum resistant signature scheme.

what if you use again quadratic computer on the applyed root square algorithm, would this be result in 2^64? and so vulnerable

i'm not even sure recursion bruteforce is something that can exist...

[Artemis3]

How would network transition from sha256 and remain its stability in the process?

first a vulnerability has to be found in SHA256 algorithm or some hardware has to be created that would be able to compute an enormous number of hashes in seconds for it to be at risk.
then we have to figure out if the problem is with Merkle–Damgård construction or with 256-bit size or something else so that we can choose a list of alternative hash algorithms.
finally the alternatives are explored and the best one is chosen and a hard fork is proposed. when it reaches supermajority support (>95% of the network) the hash algorithm used by bitcoin is changed to that new one.

This sounds great in theory, but if such a thing were to occur, will Bitcoin be able to afford this delay in decision making?

Unfortunately these kinds of things can spell doom once proven correct. The chance is not zero, and some sort of contingency plan must be put in place. You just cannot afford an scenario where. company X declares sha256 has been compromised. Gee lets start the procedure for a hard fork to take effect next year when 90% of the nodes accept...

Its pretty much a zero day exploit, you need a mitigation/patch NOW. Because it hasn't occurred, you (still) have some time to plan, but you cannot ignore the issue entirely as if it doesn't exist.

Are you going to fare like humanity did against corona? Completely unprepared? You must not "wait" until a vulnerability is found, even if one is never actually found. Because if it does, malicious actors won't wait for your bureaucracy to act.

If anything, a contingency plan should be ready even if its never needed.

[o_e_l_e_o]

You just cannot afford an scenario where. company X declares sha256 has been compromised. Gee lets start the procedure for a hard fork to take effect next year when 90% of the nodes accept...

I might be missing something obvious here, but how does SHA256 being compromised instantly compromise bitcoin?

In isolation, it does not make knowing an address dangerous. You still can't reverse it to a public key, because there is also a RIPEMD160 function in the way, and even if you could, you still can't reverse a public key to a private key, as there is an elliptic curve multiplication in the way.

In terms of mining, even if it is broken in such a way which makes finding a suitable hash for a block very fast, then that still doesn't allow anyone to steal anyone else's coins. It allows whomever is using the exploit to take a bunch of the block reward for themselves, the devs would push a hard fork to a different PoW algorithm, and potentially rollback the chain to when the exploit was first used. It's not going to take a year when it is a critical bug like this - the value overflow bug was fixed and rollbacked via a fork within a few hours.

[hatshepsut93]

https://csrc.nist.gov/projects/post-quantum-cryptography/workshops-and-timeline

https://www.nist.gov/news-events/news/2020/07/nists-post-quantum-cryptography-program-enters-selection-round

NIST has 7 finalist candidates for post-quantum crypto algorithms, and the winner is expected to be chosen in 2022/2024. They will standardize algorithms for encryption and digital signatures - notice that there's no algorithm's for hashing, which probably means that they aren't to worried about quantum computers suddenly breaking them.

[pooya87]

This sounds great in theory, but if such a thing were to occur, will Bitcoin be able to afford this delay in decision making?

these things won't happen overnight. in other words it won't be like waking up one day and seeing SHA256 has become obsolete last night!

it takes years to happen. consequently there will be more than enough time to make a decision, create proposals, take the network to upgrade and have some years to spare working with the new algorithm.
as an example you can check the history of SHA1. in 2005 it was considered unsafe against certain attacks,  it took 5 years (until 2010) for most tools to start switching to alternatives, and it took until 2017 for major browsers to stop using SHA1 entirely and the attack itself happened in 2017 (12 years after it was considered unsafe) with the cost of "the equivalent processing power of 6,500 years of single-CPU computations and 110 years of single-GPU computations".
on top of all that SHA1 is still strong against a lot of other attacks hence it is still used in many applications such as in git, PGP fingerprints,...

[charlie137]

How would network transition from sha256 and remain its stability in the process?

first a vulnerability has to be found in SHA256 algorithm or some hardware has to be created that would be able to compute an enormous number of hashes in seconds for it to be at risk.
then we have to figure out if the problem is with Merkle–Damgård construction or with 256-bit size or something else so that we can choose a list of alternative hash algorithms.
finally the alternatives are explored and the best one is chosen and a hard fork is proposed. when it reaches supermajority support (>95% of the network) the hash algorithm used by bitcoin is changed to that new one.

Price stability right now is very heavy dependent on lost coins - but this would change dramatically during off-sha256 transition, or I am missing something?

price has very little to do with lost coins as they don't amass to enough to affect that much.
additionally lost coins have nothing to do with SHA256. you are confusing hash algorithm (SHA256) with asymmetric cryptography (ECC).

Yes you right I did mixed up the question) I was actually thinking about more simple and trendy scenario when the machine is powerful enough to crunch sha256 in "human timeframe set". Such situation would mean that pretty much all our current hashes/algos would be weak for such machine, sha256/512/etc, ecc/rsa and the rest (guess excluding quantum-resistant). The network transition is pretty straightforward, I was expected that its probably gonna be same mechanics between nodes. But what about addresses and corresponded coins? Correct me if not, but so far the need to move coins from current legacy address is to avoid a grab from the collider (?). And sha/ecdsa transition seems like kinda same case, but multiplied to unspeakable scale))) Theres been tons of articles in recent years with a common topic that due low price in first 10 years total amount of coins without accessible privatekey became a holding factor) Thats probably why other projects started to massively "burn" coins to stronger the market for remained circulation. So from that topic one could assume that if the network would need to transition crypto because it got too weak - that could also mean unspent coins are now behind weak crypto as well. Thats of course in case network would not adopt stronger crypto way ahead of the need, but that seems more and more unlikely reading about the progress on the topic already.

[pooya87]

But what about addresses and corresponded coins? Correct me if not, but so far the need to move coins from current legacy address is to avoid a grab from the collider (?). And sha/ecdsa transition seems like kinda same case, but multiplied to unspeakable scale)))

i can't think of a way that any problem with SHA would affect existing coins. any vulnerability in SHA mostly affects mining and the usage of dSHA256 in signing could simply be replaced with another algorithm (so it will affect OP_CHECK(MULTI)SIG(VERIFY) OP codes) without having to move the coins (OP_HASH160 remains the same though).
but this is all just theory, the actual issue greatly affects how we should move forward.

Theres been tons of articles in recent years with a common topic that due low price in first 10 years total amount of coins without accessible privatekey became a holding factor) Thats probably why other projects started to massively "burn" coins to stronger the market for remained circulation.

in early years people were experimenting a lot on mainnet which is why there are some burnt coins. nowadays they experiment on testnet mostly.
the "other projects" that burn coins are doing it to hype their altcoin and pump it for short time to get a good profit before it dumps again.

[charlie137]

But what about addresses and corresponded coins? Correct me if not, but so far the need to move coins from current legacy address is to avoid a grab from the collider (?). And sha/ecdsa transition seems like kinda same case, but multiplied to unspeakable scale)))

i can't think of a way that any problem with SHA would affect existing coins. any vulnerability in SHA mostly affects mining and the usage of dSHA256 in signing could simply be replaced with another algorithm (so it will affect OP_CHECK(MULTI)SIG(VERIFY) OP codes) without having to move the coins (OP_HASH160 remains the same though).
but this is all just theory, the actual issue greatly affects how we should move forward.

Theres been tons of articles in recent years with a common topic that due low price in first 10 years total amount of coins without accessible privatekey became a holding factor) Thats probably why other projects started to massively "burn" coins to stronger the market for remained circulation.

in early years people were experimenting a lot on mainnet which is why there are some burnt coins. nowadays they experiment on testnet mostly.
the "other projects" that burn coins are doing it to hype their altcoin and pump it for short time to get a good profit before it dumps again.

Not just sha, ecdsa is also not quantum-resistant, so what could be mechanics if all crypto is being replaced?)

[charlie137]

But what about addresses and corresponded coins? Correct me if not, but so far the need to move coins from current legacy address is to avoid a grab from the collider (?). And sha/ecdsa transition seems like kinda same case, but multiplied to unspeakable scale)))

i can't think of a way that any problem with SHA would affect existing coins. any vulnerability in SHA mostly affects mining and the usage of dSHA256 in signing could simply be replaced with another algorithm (so it will affect OP_CHECK(MULTI)SIG(VERIFY) OP codes) without having to move the coins (OP_HASH160 remains the same though).
but this is all just theory, the actual issue greatly affects how we should move forward.

Theres been tons of articles in recent years with a common topic that due low price in first 10 years total amount of coins without accessible privatekey became a holding factor) Thats probably why other projects started to massively "burn" coins to stronger the market for remained circulation.

in early years people were experimenting a lot on mainnet which is why there are some burnt coins. nowadays they experiment on testnet mostly.
the "other projects" that burn coins are doing it to hype their altcoin and pump it for short time to get a good profit before it dumps again.

Not just sha, ecdsa is also not quantum-resistant, so what could be mechanics if all crypto is being replaced?)

It's true ECDSA isn't quantum-resistant, but only address where it's public key is known is vulnerable against quantum computer.

so does this mean that coins that arent moved from legacy address would be “recovered” during such transition?))

[o_e_l_e_o]

Not just sha, ecdsa is also not quantum-resistant, so what could be mechanics if all crypto is being replaced?)

While elliptic curve multiplication is vulnerable to quantum attacks, SHA256 isn't. At best, SHA256 being attacked with a quantum computer still requires 2¹²⁸ operations, which would take trillions upon trillions of years.

so does this mean that coins that arent moved from legacy address would be “recovered” during such transition?))

Coins sent to a brand new legacy P2PKH address would be safe from quantum attacks. Coins on any P2PKH address which has previously moved coins out of it would be vulnerable.

[charlie137]

Not just sha, ecdsa is also not quantum-resistant, so what could be mechanics if all crypto is being replaced?)

While elliptic curve multiplication is vulnerable to quantum attacks, SHA256 isn't. At best, SHA256 being attacked with a quantum computer still requires 2¹²⁸ operations, which would take trillions upon trillions of years.

so does this mean that coins that arent moved from legacy address would be “recovered” during such transition?))

Coins sent to a brand new legacy P2PKH address would be safe from quantum attacks. Coins on any P2PKH address which has previously moved coins out of it would be vulnerable.

and what about pre-bip47 and rest legacy utxos?

[pooya87]

and what about pre-bip47 and rest legacy utxos?

while theoretically any coin inside a script containing hash of the public key is safer but you have to keep in mind that any weakness in any part of the bitcoin protocol, specially in something so fundamental such as ECDSA will affect the entire bitcoin system the same way.
BTW BIP-47 (ie. reusable payment codes for HD wallets) is irrelevant here.

[charlie137]

and what about pre-bip47 and rest legacy utxos?

while theoretically any coin inside a script containing hash of the public key is safer but you have to keep in mind that any weakness in any part of the bitcoin protocol, specially in something so fundamental such as ECDSA will affect the entire bitcoin system the same way.
BTW BIP-47 (ie. reusable payment codes for HD wallets) is irrelevant here.

O yea you right, that would be number 16 i thought about. Is it?) Trying to figure which one started the script flow

[DooMAD]

How would network transition from sha256 and remain its stability in the process?

first a vulnerability has to be found in SHA256 algorithm or some hardware has to be created that would be able to compute an enormous number of hashes in seconds for it to be at risk.
then we have to figure out if the problem is with Merkle–Damgård construction or with 256-bit size or something else so that we can choose a list of alternative hash algorithms.
finally the alternatives are explored and the best one is chosen and a hard fork is proposed. when it reaches supermajority support (>95% of the network) the hash algorithm used by bitcoin is changed to that new one.

This sounds great in theory, but if such a thing were to occur, will Bitcoin be able to afford this delay in decision making?

Unfortunately these kinds of things can spell doom once proven correct. The chance is not zero, and some sort of contingency plan must be put in place. You just cannot afford an scenario where. company X declares sha256 has been compromised. Gee lets start the procedure for a hard fork to take effect next year when 90% of the nodes accept...

Its pretty much a zero day exploit, you need a mitigation/patch NOW. Because it hasn't occurred, you (still) have some time to plan, but you cannot ignore the issue entirely as if it doesn't exist.

Are you going to fare like humanity did against corona? Completely unprepared? You must not "wait" until a vulnerability is found, even if one is never actually found. Because if it does, malicious actors won't wait for your bureaucracy to act.

If anything, a contingency plan should be ready even if its never needed.

It should definitely be planned in advance.  One could argue that if there wasn't a sufficient distribution of hardware available to mine whatever new algorithm was chosen, rushing into a hardfork with a mere fraction of the current hashrate would, conceivably, cause more problems than it solves.  Miners simply wouldn't be in a position to literally bin all their hardware overnight and start from scratch.  It would likely decimate the security of the network if we tried to do it in such an abrupt fashion.

In previous topics on this subject, people have often expressed a preference for a gradual migration, meaning that the new algorithm could be used to mine alongside SHA256 for a defined transition period.  We would effectively use multiple algorithms until SHA256 can be safely deprecated.  That way, there would be no sudden plummet in the overall security of the network and we wouldn't have to resort to an 'emergency difficulty adjustment' being added to the protocol (like certain forkcoins needed to do in order to survive).