4 ms·
Suppose there are 100 billion computers in the world, including phones, smart watches, toasters, etc. Suppose each of those can perform at the level of a state
by dmurray 8y ago
Suppose there are 100 billion computers in the world, including phones, smart watches, toasters, etc. Suppose each of those can perform at the level of a state of the art specialized mining ASIC, 10 million million hashes per second, and they've all been generating 256-bit hashes constantly for 30 years, or a billion seconds.
Suppose further that sha256 is pretty good and the probability of a collision is close to that of random chance.
Then there have been 1e33 sha256 hashes generated ever. Looking at the probability table on Wikipedia for the birthday problem [0] and the row for 256 bits, interpolating it gives a probability of 1e-10 that there has been a collision.
So there would be a chance of one in ten billion that some two hashes have collided over the last 30 years. Your piece of toast, perhaps, and my bitcoin digest.
I think for practical purposes we're pretty safe.
[0]https://en.wikipedia.org/wiki/Birthday_problem https://en.wikipedia.org/wiki/Birthday_problem
- cm2187 8y agoI think you are assuming it has a perfectly uniform distribution.
- dmurray 8y agoYes, that's what I meant by saying sha256 is at least "pretty good" as a hash function. Which is not at all proven, but one of the reasons sha256 is popular is that it looks like it should be close to uniform.
- lostmsu 8y agoImpressively, my Facebook interviewer did not recognize validity of nearly identical explanation for using sha256 hashes instead of full strings as a key for purpose of counting stack traces.