Re: Thinking aloud.

On Fri, Oct 26, 2012 at 07:51:50AM +1100, Nigel Cunningham wrote:
> Taking it one step further, would you agree with the assertions of
> others that even if the SHA1s match, I still need to memcmp the
> pages to check they're actually the same (so SHA1 is effectively
> reducing an O(n^2) comparison of pages with each other to O(n)).

SHA1 creates a 160 bit hash.  So let's suppose you have a 64GB worth
of memory, which means you have 2**44 4k pages.  What's the
probability that there will be a collision?  Well:

    m = 2**44
    n = 2**160
    P = 1 - e**(-m**2 / 2n)
      = 1 - e**(-2**88 / 2**160)
      = 1 - e**(-2**(-72))
      = 2.1175 x 10**-22 (or 2.1775E-22)

This is a very tiny number.  To give you some context, let's assume
the annual failure rate percentage is 0.34%.  (Other manufacturers
have claimed an AFR of 0.88%, and the "Disk Failures in the Real
World" paper by Schroeder and Gibson claim rates of 2-4%, with up to
13% observed in some cases.)  But will assume a super-reliable disk
and assume the annual failure rate of 0.34%.  OK, let's turn that into
a failure rate on a per-second basis (assuming that we can suspend and
resume in a second).   What is the per-second failure rate?  1.07813E-10

So it is **far** more likely that the hard drive will fail than the
chance that you will observe a SHA1 hash collision.  Heck, I'm pretty
sure chances of the memory going wonky on you when you do the memcmp
is probably more likely....

Regards,

					- Ted