Re: Merge with git-pasky II.

From: Sanjoy Mahajan <sanjoy@mrao.cam.ac.uk>
Date: Apr 18, 2005, 04:16 UTC
Message-ID: <E1DNNgy-0003He-00@skye.ra.phy.cam.ac.uk>
In-Reply-To: <Pine.LNX.4.58.0504171014430.7211@ppc970.osdl.org>

> 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