Bitcoin Forum

I have found a lot of threads about PoW but not much about other aspects of SHA-256 dependence so I hope this won't be a duplicate.

Assumptions:

1) Let's say we know that SHA-256 is weakened in every possible way (collisions/preimage attacks/second preimage attacks) and will become risky to use within 10 years.
2) We have 10 years to migrate (we know the attacks will be possible but will come gradually, not overnight)
3) Let's say we have a safe replacement in the form of, for example, SHA-3 (just theoretically, it can be any hash function of the future, it is not important for the following questions)

How critical do you think the situation would be for Bitcoin? Not particularly concerned about PoW at the moment.

Questions:

1) What would have to be upgraded in Bitcoin besides mining - txids, merkle trees, block headers, signature hashes?
2) How hard would be to migrate these parts of Bitcoin with a minimum damage?
3) What would happen to all the UTXOs in e.g. P2SH, P2WPKH, etc. - could they still be moved after the hash function change (which would be a hardfork probably)?

I know we probably won't have to deal with this in our lifetime, but again, in theory, I would like to know how you think about a similar emergency scenario.

Thanks a lot!

Not that I'm a genius when it come to hash functions, but wouldn't it be much more likely to have 160-bit collisions (from RIPEMD-160) first? I remember reading that SHA2 is more computationally expensive than RIPEMD-160. That would mean drastic measures way before 256-bit hashing algorithms become weak.

Multi-sig Pay-to-Witness-Scripts are SHA256 encoded with bech32. SHA256 is also used in address generation of every other address type, although the 256-bit number that is resulted from it is then hashed with RIPEMD-160. This shouldn't change unless RIPEMD-160 became weak. Then, it's the Lightning Network (https://github.com/lightning/bolts/blob/master/08-transport.md).

I have a feeling that it won't be that hard. As far as I know, Bitcoin has had a hard fork only once, with the value overflow incident (https://en.bitcoin.it/wiki/Value_overflow_incident), but if it's a necessity (as it was in 2010), I believe consensus will be found.

In other words: If it's favoring every user, it's reasonable to assume that there won't to be a lot of noise. If we're bordering on benefits, such as back then with the block size war, it's going to be tough.

There are two choices.

• We leave them untouched, which means they can be taken by those who own the required computational power.
• We announce that SHA256 will not be recognizable by the hard-forked client after block x. This could leave few years for their owners to upgrade to a collision-safe algorithm. Those who had lost access to them or wouldn't want to upgrade for some reason, would have them removed from the hard-forked Bitcoin's circulation.

If there is a flaw found, then it's first come, first serve. You can't get around it because there isn't an unquestionable registry of attached names to all the addresses used, and there won't be.

As BHC suggests, it may be that addresses subject to the flaw will be locked, but it's the same effect as if they were not locked: the value goes down. If it becomes trivially easy to crack the hashes of old unused addresses, then all associated bitcoin will automatically become worth less and less in either case without a new solution. Locking them might actually cause a bigger crash then coming to a different solution.

Another solution rather than locking them is changing the fungibility between address types - like enforcing an additional (transaction?) cost with a new kind of address when coming from an older address.  Right now, all kinds of addresses can be traded to the other kinds of addresses, but if a critical flaw were discovered, that should not be the case. It would create multiple networks within a network, which I suspect is unavoidable over a very, very long period.

Because we don't know what the most severe flaws will exist yet, it's fine to have fungibility between address types. Having several strong hedges against flaws hopefully helps. Blindly discovering the key to any reasonably random address is costly and probably impossible right now, regardless of address type. Presently having multiple address types provides a protection against those unknowns, such that including even P2PK despite Pollard's kangaroo provides a protection, because the other addresses may have flaws yet undiscovered.

Bitcoin has proven itself against numerous flaws over the past 13 years, and so is reasonably well established. Moving to new types of hashes may present worse unknown flaws without as rigorous of testing.

Let alone that if it hasn't even shown a sign of weakness, as ECDLP has, it won't do any good all. No one tells us that the new algorithm won't become weak in few decades, but the system will get less efficient. There's also the temporary community upheaval asides.

You can test that case. Just replace 64 rounds of SHA-256 with 16 rounds of SHA-256. Then you can test all attacks you want, you will have full control over this hash function.

Just create some honest nodes that will check hashes incrementally. Then, create one node that will produce stronger and stronger hashes, raising difficulty to the insane levels. You will quickly see, how that scenario looks like.

Try fixing your 16 rounds SHA-256 with real SHA-3 and see, why it is not so trivial.

It is probably the first problem you will see, because if SHA-256 is fully broken, then you can create a block with zero hash. That would also mean, it would be a previous block from the Genesis Block perspective, so you will have a ring, instead of a chain. By breaking SHA-256, you can quickly realize that your attack will shut down nodes, will freeze the chain, will cause huge blockchain reorganization after passing difficulty adjustment, and will cause huge damage, unless carefully planned and gradually introduced.

Bitcoin Message signing (outside of on-chain signatures of regular transactions). Also all hashed public keys (because if you can execute a preimage attack, then you can replace public keys). All hashed scripts (faster than hashed public keys, because you can just use "<randomData> OP_DROP <yourPubKey> OP_CHECKSIG" everywhere and spend that). The same with commitments (if you commit anything to the chain and it uses SHA-256, then that commitment is no longer valid). All timestamps outside Bitcoin that used block hashes will be invalid. In short, it would be just a public database that anyone can modify, so it will be useless, unless fixed.

Porting txids: every txid should be re-hashed, just like in Segwit you have txid and hash, here you will have one more field for a new hash.
Mining: you will have two difficulties, one to preserve the old, SHA-256 chain, and the new, to keep it unaltered.
Merkle trees: each merkle tree should be re-hashed, it could be a commitment, like in Segwit, but could be also better compressed.
Block headers: you will have 80-byte new header that would contain both old and new data, in a combined and compressed form.
Signature hashes: you have to use new hashes, and re-hash old signatures, because it is the same (or even worse) case than txids.
Bitcoin Message: the same solution as for signature hashes; also encourage upgrading to signet-way-of-signing-things.
Hashed public keys: old coins should be moved to the new addresses; it could be spendable or not, whatever option will win.
Hashed scripts: the same solution as for hashed public keys.
Commitments: the new chain will be started with one, huge commitment, containing the whole old chain.
Timestamps: they are invalid, new timestamps should be year-2038-resistant and year-2106-resistant, it could be modulo 2^32, but should be clearly defined, whatever it will be.

It could be a soft-fork if done correctly. It is just a matter of data format. We can stick to the old format, but just put more rules on top of that, making it as soft as Segwit or Taproot.

It would be. We have ASIC's for SHA-256d, we could have ASIC's for RIPEMD-160(SHA-256) faster than SHA-256 will be fully broken (they now would require 2^80 operations, but I think it could be simplified to something like 2^64, that would make it as real as SHA-1 collision).

There are currently a few coins using the SHA-3 algorithm, namely Nexus / TERA / MaxCOIN / Bitcoin Classic / Cruzbit ...so the lessons learned from these coins will show us how successful a hard fork will be for Bitcoin (BTC) ...right?

Can something like this not be tested on a TestNet for Bitcoin (BTC) to see what impact it will have? I think Ethereum uses KECCAK-256 and it does not follow the FIPS-202 based standard?  

https://eprint.iacr.org/2019/147.pdf

Old article ...: https://www.csoonline.com/article/3256088/why-arent-we-using-sha3.html

It can be even better than that: it is possible to store it as a SHA-3 prefix in the previous block hash. It could be backward-compatible, so that only upgraded nodes would use rehashed chain with SHA-3. Then, all nodes will be in the same network as non-upgraded nodes, no matter if it is mainnet, testnet, signet, regtest, or dragon-lives-there-network. Also, it is possible to have an activation rule, expressed as SHA-256 collision or SHA-256 preimage, things like that. We even have existing outputs with such challenges, so it is trivial to plan automatic soft-fork activation from the block, where any of such coin will be moved for the first time.

So, to sum up, you can safely run SHA-3 node on mainnet, if you do that correctly, and if you know how to make it compatible with non-upgraded nodes. It is the same case as chain compression: there are nodes that use compressed format and they are still in the same network.

You would have to avoid exposing the new hash with the old.
If SHA256 or RIPE hashes are compromised and the key is discovered, then that would cause SHA-anything to also be compromised if the same key is used. Nevermind that a key now has two points of failure for derivation  (although still practically impossible to discover).

For an added step, how about: all willing transactions incorporate a second key which is hashed with SHA-3 or other. The user would have to store this somehow, and the network might make sure it didn't interact with the network until ready. This separate key could be chosen by the user or in Core, perhaps derived by a longer generating key. The SHA-3 hash could be put into something like the OP_RETURN, and activated when the network was appropriate. Until the new network machinery was activated, you simply ignore these SHA-3 hashes, so it would add a byte cost, but at the chance of additional security when needed.

I doubt that you can avoid having a second network or network-in-network due to eventual changes in technologies at some point. These flaws are hopefully not too soon, and are probably on the orders of multiple decades before occurring (and if bitcoin can't last that long, crypto is hopeless). I hope that there always remain methods to choose to move into it and build naturally rather than be forced.

Thanks a lot for your excellent answer! What do you think would happen to L2 layers, especially LN? Would all the channels needed to be closed and re-opened again or could there be any better migration path?

Don't they have to be closed anyways now when upgrading the software on a node?

If SHA-256 is broken, then you can spend all coins, where you know the public key. You can start with random ECDSA signature, and then create SHA-256 preimage. For example:
I wrote that example some time ago, but it is still valid in the context of this topic. Here, you have "z=abb986eeb49536362f4d845641ae21e813680b4848c1daa84a07c389a65530dc". As long as you don't know any transaction that can be hashed to this value, Satoshi's coins are safe. But if you can do SHA-256 preimage, then you can make such transaction, include (r;s) pair, and his coins are yours.

That means, all LN channels have to move to the new address type, when SHA-256 will be fully broken.

Thanks for this answer, garlonicon, once again.
This is all very helpful!

Two more questions if I may:

1) As I understand quantum computers will be (Bitcoin related and if they will ever exist with enough logical qubits) a threat only to public key cryptography.
Regarding SHA-256 and Grover's algorithm - this should not effect safety of this hashing function in Bitcoin that much, am I right?

2) This will be more about your personal opinion rather than a technical explanation.

What do you think would happen to all the not-moved UTXO's (lost/forgotten/etc. coins) - or what do you think the consesus would be?
I think there would never be a consensus to freeze these coins (and it should not be IMO).
I think these coins should serve more like a honeypot for all the "hash-breakers" or quantum computers (in case of ECDSA).

1) I don't know. I don't think quantum computers will be a problem. I think there are more serious issues, like lattice attacks, that can be done on a non-quantum PC's.
2) For now, there is no consensus. No BIP's, no other proposals, just some discussions. But I expect some of them will be created, as we will get closer and closer to 128 leading zero bits in our difficulty.

If they will not be frozen, the new owner could decide to freeze them anyway, by using OP_RETURN or some unspendable (or potentially unspendable) new address. So, if our consensus will be "just do nothing", then it still depends on future actions of someone, who will move them.

We already have such honeypots, for example our famous transaction puzzle. I think that kind of puzzles will be solved first, just because they are easier. For now, 64-bit hash is untouched and 120-bit public key is still not moved. Maybe some Taproot-based puzzles will be created, like this testnet3 puzzle: 448b81b2b3c2c8558d268e4f515ff38eb6367d156babbc3733a14834a5a6e7b0

Never heard of it but a little bit of googling and it looks quite scary.
How serious do you think it could become? Can there be any countermeasures against these attacks?

Quite serious, because with two signatures, 128-bit public keys can be broken. With more signatures, it gets easier and easier, so maybe it is possible to get, I don't know, 100 signatures, break 240-bit keys (or something around it), then tweak the real key 2^16 times, and you will have it.

Yes, as usual, the whole cryptography is based on unsolved mathematical problems. If ECDSA is gone, but lattice attacks are not, then lattice-based cryptography can be used. By introducing new opcodes like OP_CHECKLATTICE instead of OP_CHECKSIG, it could be possible to solve that. Definitely breaking ECDSA is less scary than breaking SHA-256, because in that case we can still use the heaviest Proof of Work to choose the right way (and in case of breaking SHA-256, ECDSA is also gone).

I know the form of past breaks do not imply how fast the future breaks will be.
But if the past repeats the breaks will be rather gradual than 0-day so we have hopefully enough time to migrate.
Your opinion/"hopes" on that?  :)

I can only guess that it will be gradual, because it was in the past.

One more question - would everything above (txids, merkle trees, signature hashes, etc.) need to be re-hashed back to the Genesis Block or the new client would rehash only the new "activity" - like from the UTXO set state at a certain point of time, from some UTXO commitment (I mean practically importing the UTXO set into the new system)? If it is back to Genesis Block and every client would need to do that, it would be computationally difficult I suppose.

It really comes down to what "broken" means. For example SHA1 is considered broken but you still can't reverse it or you can't find another message that produces the same hash unless you also control the initial message.
It would be the same for SHA256, if there is a chance that the content of the chain could be changed then some extreme measures needs to be taken that may include a hard fork that discards the previous chain and all its hashes and replaces it with something new.

You could only do it back to the accepted version where everyone believed it wasn't tampered with. Before that, it's hopeless.
The benefit of validation nodes, both mining and non-mining, is that they keep this transaction history, so you wouldn't lose with the general consensus that they provide distributed throughout all of the hard disks globally.

The much bigger problem is really one of culture and politics. If SHA-256 was broken, would you be able to convince all of the previously invested interests to invest in a new system - if it wasn't already built in? I doubt that there would be a quick consensus about what the new system would be. It would take a long time to recover.

Did the developers convince them invest into it back in 2009? No, they entered the system at their own will; they had convinced themselves that it's worth the money. So, why should they expect a conviction now?

If SHA-256 became broken, right now, a chaos would prevail. Besides Bitcoin and other PoW cryptos that wouldn't be able to prevent double-spending in that case, software's integrity verification, passwords and encrypted messages that use SHA-256 could all be altered and read.

2009 was a dead year for near anything but software development. It wasn't a large ecosystem.

It's a larger ecosystem. You'd have schisms and splits. You'd not regain the trust that has been built up until now if there was a flaw that occurred rapidly. What you describe next would happen:

That was the point I was trying to make. You would have havoc everywhere, with bitcoin being the smallest of concerns now. On top of that, you'd have large cultural shifts into many different factions of currencies. You'd lose a major coin and the benefit that brings (like increasing stability). It would take time to recover, which it never would into the exact same thing.

My question was more about what would have to be changed if it occurs gradually, not overnight.

And no one outside cryptographic communities was having any idea of how a cryptocurrency would even work. Those who invested time and money had made their research, had cleared out confusions and misconceptions etc. They'd convinced themselves.

Indeed, it's a much larger ecosystem today. If one had found a way to break SHA-256, it'd be a matter of time until Bitcoin lost its purpose. I don't think there could be a way to correct the situation; it's an absolutely fucked up scenario. But, it's highly unlikely to happen overnight.

Not a small-scale concern. As said, it's a large ecosystem now. It'd probably be one of the top concerns along with national security and online banking.

Satoshi answered both questions.


So, to sum up: in case of a gradual breakdown, it would be easier, because we could also upgrade gradually, in a carefully planned and step-by-step introduced soft-fork. Actually, the mining process is by definition "a gradual breakdown", because you have more and more zero bits. For now, you can assume that 96 leading zero bits are broken, because this value is around the total chainwork since 2009.

Also, some answers I gave you assumed preimage attacks (because you asked about the case where "SHA-256 is weakened in every possible way"). That's hard to do today even on MD5, so I think there is quite a long way before we ever reach that point.

Thanks, garlonicon.

One more question regarding the solution you described earlier - would everything above (txids, merkle trees, signature hashes, etc.) need to be re-hashed back to the Genesis Block or the new client would rehash only the new "activity" - like from the UTXO set state at a certain point of time, from some UTXO commitment (I mean practically importing the UTXO set into the new system)? If it is back to Genesis Block and every client would need to do that, it would be computationally difficult I suppose.

It is computationally expensive but it is not more expensive that the initial block download when your full node first syncs with the network. Like IBD it also is something your node would need to do only once.

Agreed that hashing isn't that computationally expensive... if you have the originating keys.

But hashing everything with a new hash back to the genesis block would be impossible though due the lack of available keys, right? You also wouldn't want to re-hash everything with the same key, as it would be a security issue by providing an additional equation and point to solve for the generating key. Is there something I'm missing about other things that can be hashed? Wouldn't these be broken along with a SHA-256 break?

I don't know what you mean by "keys" since you don't need a key to compute a hash. There is just a message (like the block header, raw transaction,..) that you feed to a function to get the resulting hash.

Oh, I see. I've only been considering pre-image attacks where a key is SHA256 hashed as part of creating an address. As gnarlicon said, pre-image would never be trivial. At the minimum, you would have a warning, like many very old accounts activating more and more, which you'd have to distinguish from people who have incredible patience. I think Satoshi's "Everyone would have to upgrade by that time" isn't specifically about blocking addresses susceptible to pre-image attacks but enforcing that all new transactions use the new hash systems in address generation and transaction verification. (I also disagree with him on this last point. It's ok to allow people to continue to use non-upgraded methods if they know that these risks exist when they are discovered. It's their choice to continue with that risk.)

This seems the most relevant, gnarlicon's/satoshi's answer, "If the hash breakdown came gradually, we could transition to a new hash in an orderly way." It looks like BIP-47 / paynym has something that already kind of incorporates what I was suggesting that could work to counteract future pre-image attacks (..and could even be used now with small tweaks).

It doesn't make sense to me hashing everything back to the genesis block either way. It isn't about computation either - hash functions are reasonably simple to calculate. It wouldn't be possible because all transaction messages back to the genesis block don't exist anymore anywhere. You've only paid for what is stored on the blockchain and thrown away the rest. I'm not even sure what benefit there would be in rehashing everything back to the genesis block, considering if we have the ability to do this, everybody has the ability to do this. So the information there exists with and without a new hash method. I also don't think that you can gain anything for privacy or security. You could move forward with new hash functions but I can't see how this is possible working backwards.

I know what you mean. Every OP_CHECKSIG (or every opcode based on that) needs a valid signature. Every OP_SHA256 (and OP_HASHes based on that) needs SHA-256 explicitly. You cannot just replace one z-value with another z-value without breaking ECDSA. So, the solution is not to re-hash absolutely everything, but to re-hash things that could be re-hashed, and protecting the rest by hashing those signatures. That part is kind of tricky.

So, to preserve backward compatibility, things should be:
1) calculated as today
2) re-hashed and checked with the new hash function
That means, we could for example re-hash input scripts with SHA-3 and create commitments for that.

Yeah, I agree with that. That makes sense.

So that is about soft-forking, am I right?

1) If we found a consensus to hard fork (because it would be maybe necessary), how would we proceed?
I guess we would not have to re-hash things but start with a new hash function from a certain block? Would the old SHA-256 chain/history be safe even without re-hashing if we do the hard fork?

2) Could all the existing UTXOs stay spendable (even if they could be stolen if not moved to a new safe address)?

Thank you

The whole world will need to change when SHA256 is broken. This encryption algo is being used almost everywhere. Mostly in banking. When SHA256 gets hacked, crypto will be the last thing you'll worry about. The civilization will collapse if we don't act in time. People will lose their assets, their bank accounts, their passwords and everything else. Crypto will be a drop in the bucket.

This is the answer I always get.
I am sorry but that was not my question.

Yes, in the slow break scenario, which is the most likely and would come with substantial warning.

Address generation and transaction confirmation could integrate the new algorithm over time, as gnarlicon and satoshi stated: "orderly".

(You might think to lock out very old addresses from being able to do move with such a break, but I disagree in the slow scenario. Keys to old addresses still wouldn't be trivial to solve, so finding the keys to those old addresses would become the new mining reward if a preimage break were to happen. It would even have decreasing rewards over time since larger accounts would be targeted first. Quite the bounty! But worth it for the warning to all users.)
-

In plenty of ways, bitcoin is less susceptible to a break than other currencies due to its distributed nature of computing, keys, values, people, etc. If a bank or nation were to have its major ledgers corrupted, I'm not sure they could recover the trust from the public so quickly. I doubt any proof-of-stake system could survive due to the loss of confidence. Bitcoin would remain feasible even with a break due to having to solve for the many different values, large warnings from users about it (at very unfortunate losses to those individuals, but where a larger institution might remain silent for too long with much greater losses), and the ability to institute new methods as fast as necessary (although forks would happen in all scenarios).

Yes, I can see a soft-fork way for breaking SHA-256.

I don't know, because we don't have a clear proposal for 2038 year problem or 2106 year problem. For now, the latest Core version is crashing in 2038. The whole chain will stop in 2106. Then, we may be forced to do some hard-fork. And I guess many things could be fixed at once, because it is quite rare to have no soft-fork solution. But in case of SHA-256, we can make it very soft. As soft as Segwit and Taproot. We only need adding new hash function on top of what we have, so it is a clear way.

You need re-hashing if you want to preserve the history. You can also hard-code it into the new Genesis Block as a commitment, but I think we should not do that.

No, because that's why we need re-hashing.

Yes. I think they should be by default. Then, you move it for the first time and decide, if it will be moved to some new spendable or to some new unspendable address (or maybe coinbase-burned).

Can you please elaborate? I though the timestamp overflow bug will cause the chain to stop in 2106. Did the latest Core version bring a worse bug?

What are the risks of that? It seems to be a clean solution at first sight.

It is worse, because the current implementation has also 2038 year bug: https://bitcointalk.org/index.php?topic=5365359.msg58166985#msg58166985
You can test that, just download Bitcoin Core 22.0, set your computer clock to 2040, and run the Core client in regtest mode. Then try to mine some blocks.

It is clean, but it is hard-fork. In general, hard forks can do everything and make it clean. But we cannot use hard forks for everything, because of backward compatibility, that's why BTC is going to do soft-fork or no-fork every time when possible.

I am trying to read the github thread but it is probably beyond my capabilities.
I thought that because of unsigned 32-bit integers used in Bitcoin the problem is "postponed" till 2106.

In other words - is it easily repairable for the next versions?


I absolutely agree with that. I was just curious how this exact hard fork would work. If we do the hard fork with hard-coded chain (state of the UTXO set at some block height?) then the new nodes would sync only from the new Genesis Block? They would not check the history prior to the hard fork?

Everything is explained in that linked topic: https://bitcointalk.org/index.php?topic=5365359
Technical details are in this post: https://bitcointalk.org/index.php?topic=5365359.msg58166756#msg58166756

Yes, it can be fixed for Bitcoin Core. But: that version 22.0 and some versions around it are affected and will be affected. That means, those clients using these versions will crash in 2038.

Could be. If you start doing hard fork, then from that moment you can do everything, and build something that will not even be a blockchain at all. Because if that backward compatibility is broken, it does not matter if you cross that border by an inch or by a mile.

I think they should check everything, but yes, if you freeze UTXO's in time, then you can skip it, because then they are hard-coded by consensus. Also, doing such freeze make things less resistant to chain reorgs. For that reason, I think we don't need any new Genesis Block. One is enough for everything we need.

Thanks again, garlonicon, for all your answers!

One more thing - could potentially extension blocks be a solution for this?

I mean to start a "new parallel" SHA-3 chain like an extension block chain, with interoperability (people can move coins from "old" to "new" and vice versa) which can last even for decades.
If SHA-256 is then dangerously close to being broken, could the original chain be somehow eliminated/merged into the extension block chain without the coins not moved to "new" being lost?

If SHA-256 will be fully broken, then the answer is no. Just because you can reach SHA-256 collision or SHA-256 preimage and include SHA-3 for something else.