What needs to be changed when SHA-256 is broken?

[BlackHatCoiner]

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?

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.

[kaggie]

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?

Did the developers convince them invest into it back in 2009?

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

So, why should they expect a conviction now?

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:

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.

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.

[Adam_xx]

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

2) We have 10 years to migrate (we know the attacks will be possible but will come gradually, not overnight)

[BlackHatCoiner]

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

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.

You would have havoc everywhere, with bitcoin being the smallest of concerns now.

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.

[garlonicon]

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

Satoshi answered both questions.

SHA-256 is very strong.  It's not like the incremental step from MD5 to SHA1.  It can last several decades unless there's some massive breakthrough attack.

If SHA-256 became completely broken, I think we could come to some agreement about what the honest block chain was before the trouble started, lock that in and continue from there with a new hash function.

If the hash breakdown came gradually, we could transition to a new hash in an orderly way.  The software would be programmed to start using a new hash after a certain block number.  Everyone would have to upgrade by that time.  The software could save the new hash of all the old blocks to make sure a different block with the same old hash can't be used.

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.

[Adam_xx]

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.

[pooya87]

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.

[kaggie]

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?

[pooya87]

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.

[kaggie]

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.

[garlonicon]

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.

[kaggie]

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.

[Adam_xx]

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

[mindrust]

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.

[Adam_xx]

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.

[kaggie]

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

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).

[garlonicon]

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

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

1) If we found a consensus to hard fork (because it would be maybe necessary), how would we proceed?

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.

I guess we would not have to re-hash things but start with a new hash function from a certain block?

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.

Would the old SHA-256 chain/history be safe even without re-hashing if we do the hard fork?

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

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

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).

[Adam_xx]

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.

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?

You can also hard-code it into the new Genesis Block as a commitment, but I think we should not do that.

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

[garlonicon]

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?

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.

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

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.

[Adam_xx]

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.

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?

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 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?