Pages:
Author

Topic: What needs to be changed when SHA-256 is broken? (Read 438 times)

hero member
Activity: 813
Merit: 1944
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.
jr. member
Activity: 34
Merit: 35
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?
jr. member
Activity: 34
Merit: 35
Thanks again, garlonicon, for all your answers!
copper member
Activity: 821
Merit: 1992
Pawns are the soul of chess
In other words - is it easily repairable for the next versions?
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.

Quote
(state of the UTXO set at some block height?)
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.

Quote
then the new nodes would sync only from the new Genesis Block?
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.
jr. member
Activity: 34
Merit: 35
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?
copper member
Activity: 821
Merit: 1992
Pawns are the soul of chess
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.
jr. member
Activity: 34
Merit: 35
Quote
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?

Quote
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.
copper member
Activity: 821
Merit: 1992
Pawns are the soul of chess
Quote
So that is about soft-forking, am I right?
Yes, I can see a soft-fork way for breaking SHA-256.

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

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

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

Quote
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).
sr. member
Activity: 333
Merit: 506
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).
jr. member
Activity: 34
Merit: 35
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.
legendary
Activity: 3276
Merit: 2442
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.
jr. member
Activity: 34
Merit: 35
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
sr. member
Activity: 333
Merit: 506
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.
copper member
Activity: 821
Merit: 1992
Pawns are the soul of chess
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.
sr. member
Activity: 333
Merit: 506
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.
legendary
Activity: 3472
Merit: 10611
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.
sr. member
Activity: 333
Merit: 506
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?
legendary
Activity: 3472
Merit: 10611
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.
jr. member
Activity: 34
Merit: 35
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.
copper member
Activity: 821
Merit: 1992
Pawns are the soul of chess
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.
Pages:
Jump to: