On Thu, Jan 06, 2011 at 11:44:31AM -0800, Peter Taps wrote:
> I have been told that the checksum value returned by Sha256 is almost
> guaranteed to be unique.
All hash functions are guaranteed to have collisions [for inputs larger
than their output anyways].
> In fact, if Sha256 fails in some case, we
> have a bigger problem such as memory corruption, etc. Essentially,
> adding verification to sha256 is an overkill.
What makes a hash function cryptographically secure is not impossibility
of collisions, but computational difficulty of finding arbitrary
colliding input pairs, collisions for known inputs, second pre-images,
and first pre-images. Just because you can't easily find collisions on
purpose doesn't mean that you can't accidentally find collisions.
That said, if the distribution of SHA-256 is even enough then your
chances of finding a collision by accident are so remote (one in 2^128)
that you could reasonably decide that you don't care.
> Perhaps (Sha256+NoVerification) would work 99.999999% of the time. But
> (Fletcher+Verification) would work 100% of the time.
Fletcher is faster than SHA-256, so I think that must be what you're
asking about: "can Fletcher+Verification be faster than
Sha256+NoVerification?" Or do you have some other goal?
Assuming I guessed correctly... The speed of the hash function isn't
significant compared to the cost of the verification I/O, period, end of
story. So, SHA-256 w/o verification will be faster than Fletcher +
Verification -- lots faster if you have particularly deduplicatious data
to write. Moreorever, SHA-256 + verification will likely be somewhat
faster than Fletcher + verification because SHA-256 will likely have
fewer collisions than Fletcher, and the cost of I/O dominates the cost
of the hash functions.
> Which one of the two is a better deduplication strategy?
> If we do not use verification with Sha256, what is the worst case
> scenario? Is it just more disk space occupied (because of failure to
> detect duplicate blocks) or there is a chance of actual data
> corruption (because two blocks were assumed to be duplicate although
> they are not)?
If you don't verify then you run the risk of corruption on collision,
NOT the risk of using too much disk space.
> Or, if I go with (Sha256+Verification), how much is the overhead of
> verification on the overall process?
> If I do go with verification, it seems (Fletcher+Verification) is more
> efficient than (Sha256+Verification). And both are 100% accurate in
> detecting duplicate blocks.
You're confused. Fletcher may be faster to compute than SHA-256, but
the run-time of both is as nothing compared to latency of the disk I/O
needed for verification, which means that the hash function's rate of
collisions is more important than its computational cost.
(Now, Fletcher is thought to not be a cryptographically secure hash
function, while SHA-256 is, for now, considered cryptographically
secure. That probably means that the distribution of Fletcher's outputs
over random inputs is not as even as that of SHA-256, which probably
means you can expect more collisions with Fletcher than with SHA-256.
Note that I made no absolute statements in the previous sentence --
that's because I've not read any studies of Fletcher's performance
relative to SHA-256, thus I'm not certain of anything stated in the
David Magda's advice is spot on.
zfs-discuss mailing list