Hash collision

[Bill Barry]

Brian Mearns wrote:
> Thanks for the thorough feedback. I'll set up a script to commit every
> second, and once the age of the Universe has reached about 10^31 times
> what it is now, I should get my moment in the sun!
>   

I think it'd actually be quite humorous if someone wrote a script that 
did something like this:

hg pull
hg merge
hg ci -m "scripted merge"
hg push
hg id > servername.txt
hg ci -m "servername commit"


and then ran it as a cronjob every second against some centralized repo 
from a hundred machines or so.

At one point I thought there was a bug in the local commit numbers code 
which would prevent you from having a revision number > 2^32

We could bet on how long the repository would keep getting new revisions.

all things running smoothly:
2^31 revisions would be hit in 125 days (possible problem point where 
signed 32 bit integers roll over)
2^32 revisions would be hit in 250 days (unsigned 32 bit integers roll over)
2^64 = 2.9*10^9 years (unsigned 64 bit integers: read never gonna happen)
2^69 = 9.4*10^10 years (expected complexity of sophisticated 
cryptographic attack on sha1)
2^80 = 1.9*10^14 years (expected repetition of a hash based solely on a 
birthday attack)
2^160 = 2.3*10^38 years (guaranteed collision)

chances are much better though that:
1. the hard drives on the servers holding the repository will become 
full (though possibly this might happen after the 250 day mark; 
conservatively I would estimate a repository with 2^32 revisions entered 
into it at a lower bound of around 27GB)
2. some other bug within hg would prevent pushes/pulls/merges (possibly 
there could be something that is O(revision count) somewhere which would 
start becoming noticeable at around 100K revisions or so)

> Okay, I'm pretty convinced now.
>
> -Brian
>
>   
notes:
Math:
revisions / 100 / 2 = seconds to make
(100 servers, 2 commits per server per cronjob exec)
revisions * (64 + 40) = bits for size of repository
(64 = revlog entry size, 40 = estimated average size of delta)
used google to do conversions