Dealing with SHA-256 Collisions
2010 Jun 14
See all posts
Dealing with SHA-256 Collisions @ Satoshi Nakamoto
- Author
-
Satoshi Nakamoto
- Email
-
satoshinakamotonetwork@proton.me
- Site
-
https://satoshinakamoto.network
lachesis
Dealing with SHA-256 Collisions
June 14, 2010, 01:01:11 AM
A mathematician friend of mine pointed out that there are very few if
any hash protocols that have survived for 10 years or more. What would
Bitcoin's solution be if SHA256 were to be cracked tomorrow?
theymos
June 14, 2010, 02:34:57 AM
I don't think that broken cryptography could ever be the end of
BitCoin if it becomes popular. Since the block chain can be forked
without losing too much data, modifications to all aspects of BitCoin
are possible. If SHA-256 was broken, a new version of BitCoin would be
released that would switch to a stronger hash function for addresses.
Changing the hash function used for blocks might not be necessary if the
weakness still required some non-trivial amount of computation. The new
version would ignore SHA-256 blocks after a certain point in time, but
most old transactions would survive.
In case the weakening of SHA-256 is gradual instead of sudden (much
more likely, IMO), BitCoin could stretch the process of switching to a
different hash algorithm over a long time. First accept SHA-512 (or
whatever) in addition to SHA-256, then use SHA-512 by default, and
finally stop accepting SHA-256 for new blocks.
Xunie
June 14, 2010, 04:30:41 AM
Quote from: theymos on June 14, 2010, 02:34:57 AM
In case the weakening of SHA-256 is gradual instead of sudden (much
more likely, IMO), BitCoin could stretch the process of switching to a
different hash algorithm over a long time. First accept SHA-512 (or
whatever) in addition to SHA-256, then use SHA-512 by default, and
finally stop accepting SHA-256 for new blocks.
Wouldn't the users lose their coins?
lachesis
June 14, 2010, 04:31:14 AM
So it's possible to switch "on the fly" to a new hash function?
Wouldn't all the old transactions then be compromised (because they
could be trivially recomputed)?
SHA-256 has already been weakened by a factor of 16 (according to my
friend. I can't find documentation on that, but I trust him). That's 16
out of 2^256, so not a huge deal, but still.
theymos
June 14, 2010, 06:09:58 AM
Quote from: lachesis
Wouldn't all the old transactions then be compromised (because they
could be trivially recomputed)?
After thinking about this some more, I've realized that breaking the
hash function used in blocks would be more disastrous than I had
originally thought. But it should still be possible to change the hash
function "on-the-fly" by including secure hashes of each real block in
the old chain with the new BitCoin release. Some mechanism of doing this
(hopefully more elegant) would also have to be used for a gradual hash
change.
Xunie
Wouldn't the users lose their coins?
Everyone's balance is publicly available, so it should always be
possible to preserve this data, no matter what changes are made to
BitCoin.
Satoshi Nakamoto
June 14, 2010, 08:39:50 PM
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.
Dealing with SHA-256 Collisions
2010 Jun 14 See all postsSatoshi Nakamoto
satoshinakamotonetwork@proton.me
https://satoshinakamoto.network
A mathematician friend of mine pointed out that there are very few if any hash protocols that have survived for 10 years or more. What would Bitcoin's solution be if SHA256 were to be cracked tomorrow?
I don't think that broken cryptography could ever be the end of BitCoin if it becomes popular. Since the block chain can be forked without losing too much data, modifications to all aspects of BitCoin are possible. If SHA-256 was broken, a new version of BitCoin would be released that would switch to a stronger hash function for addresses. Changing the hash function used for blocks might not be necessary if the weakness still required some non-trivial amount of computation. The new version would ignore SHA-256 blocks after a certain point in time, but most old transactions would survive.
In case the weakening of SHA-256 is gradual instead of sudden (much more likely, IMO), BitCoin could stretch the process of switching to a different hash algorithm over a long time. First accept SHA-512 (or whatever) in addition to SHA-256, then use SHA-512 by default, and finally stop accepting SHA-256 for new blocks.
Wouldn't the users lose their coins?
So it's possible to switch "on the fly" to a new hash function? Wouldn't all the old transactions then be compromised (because they could be trivially recomputed)?
SHA-256 has already been weakened by a factor of 16 (according to my friend. I can't find documentation on that, but I trust him). That's 16 out of 2^256, so not a huge deal, but still.
After thinking about this some more, I've realized that breaking the hash function used in blocks would be more disastrous than I had originally thought. But it should still be possible to change the hash function "on-the-fly" by including secure hashes of each real block in the old chain with the new BitCoin release. Some mechanism of doing this (hopefully more elegant) would also have to be used for a gradual hash change.
Everyone's balance is publicly available, so it should always be possible to preserve this data, no matter what changes are made to BitCoin.
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.