Uniqueness of Rev. Hex Id.s

[Matt Mackall]

On Fri, 2014-01-24 at 04:59 +0000, Pietro Moras wrote:
> I
> see:  "Secure
> Hash Algorithm"
> SHA-1,
> first
> 12 of 40 Hex digits.
> Thanks.
> Asked
> as testing a simulated Hg distributed network.
> I
> dare:  Ever heard of duplicated Rev. Hex Id.s? Thanks.

If we did, we would be world-famous. A SHA1 hash collision would cause
quite a lot of excitement and probably result in (inaccurate) front page
headlines in the New York Times.

Again, we _display_ 12 hex digits, but _use all 40 internally_.

To have a roughly 50% chance of having a duplicate just by chance, you
need to gather up about 2^80 hashes. That's about 4 yottabytes of
storage just for the hashes, which is about 1000 times more disk space
than all data storage on earth combined. So it's fairly unlikely that
this has ever happened in the wild.

The odds of collision for the 12 digit version is roughly one in 16
million... and would be relatively harmless.

-- 
Mathematics is the supreme nostalgia of our time.