From: Sanjoy Mahajan Date: Mon, 18 Apr 2005 04:16:59 GMT Subject: Re: Merge with git-pasky II. Message-ID: In-Reply-To: > 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