Scott Rotondo wrote:
> Krishna Yenduri wrote:
>> On 10/15/09 11:17 AM, Lori Alt wrote:
>>> I presented the question :"Are SHA256 questions good enough to
>>> establish block equality?" to Jeff Bonwick. His answer:
>>>
>>>> Yes. Collision probability is 10-77, i.e. 77 nines. Nothing else
>>>> in a computer is even close to that reliable.
>>
>> Note that the probability of a collision also depends on the number
>> of blocks
>> in the stream. For example, one would need to do 2^128 SHA256
>> digests to
>> get a probability of a collision > 0.5.
>>
>> There is a nice table at
>> http://en.wikipedia.org/wiki/Birthday_paradox#Probability_table
>> that gives the upper bound on the number of blocks to achieve
>> a given probability.
>>
>> I would agree that this is a reliable way to establish block equality
>> given the number of blocks needed for even a probability of 10^-18.
>>
>
> Perhaps it's worth pointing out that both statements above are
> correct, but they are answers to different questions. 10^-77 is the
> probability of a hash collision for a particular pair of blocks. For
> ZFS, we care if there is a collision between *any* pair of unequal
> blocks. That probability depends on the number of blocks, as Krishna
> points out. Finally, both of these calculations rely upon the implicit
> assumption that the 2^256 possible hash values are uniformly
> distributed; that assumption is widely accepted to be at least
> approximately true, but I'm not aware of a mathematical proof.
>
> In any case, I think it's safe to conclude that SHA-256 is more than
> adequate for filesystem block equality comparisons.
That's true today. At what point will Moore's law catch up though?
(In other words, how long will it take for storage densities to reach
the point where where the risk of a collision becomes significant?)
Start from a petabyte (probably about the largest practical filesystem
size in use today), and double every 12 months. (I think storage has
been outpacing Moore somewhat.)
- Garrett
>
> Scott
>
