Re: Merge with git-pasky II.

[Sanjoy Mahajan <sanjoy@mrao.cam.ac.uk>]

> So until proven otherwise, I worry about accidental hashes, and in
> 160 bits of good hashing, that just isn't an issue either...[Going
> from 128 bits to 160 bits made it] so _unbelievably_ less likely to
> happen that it's not even funny.

You are right.  Here's how I learnt to stop worrying and love the 160
bits.

A 160-bit hash requires 2^80=10^24 files before the collision
probability is roughly 0.5 (actually 1-e^{-1/2}).  Now be very
conservative: Instead of tolerating a 0.5 probability, worry about
even a 10^-8 probability of a collision anywhere, anytime.

The magic number of files for that probability is 10^20 (roughly 10^40
pairs for 2^160=10^48 boxes).

Given 10 billion people using git, each producing 1 source file per
second -- busy beavers all -- they would need 300 years to produce
10^20 files.  And to reach the 10^-8 collision probability, all 10^20
files must belong to the same project, and even OpenOffice will not be
that bloated.

-Sanjoy