# How to calculate chance of missing an error with overlapping hashes?

Assume that I have a huge file, which I split up into blocks. Each block is hashed with a hash function of $x$ bits. The chance of an error going undetected in a block should therefore be $1/2^x$.

Now, let's assume a block is $y$ bytes in size, meaning there are $2^y$ possible values for that block of data. As $y$ gets bigger, there are more possible collisions for any given hash value, yet the chance of such a collision occurring seems to remain the same (correct?).

For my purposes, I need to split the data in many blocks, the more the better, but the more blocks, the more hashes which at some point take quite a lot of space to store. So I want to use a hash where $x$ can be small while still having a high chance of detecting errors.

So I got this idea that instead of hashing every block with a hash function of $x$ bits (illustation 1), I instead hash every block with a hash of $x/2$ bits. However to ensure that it is still possible to detect errors at the same rate as before, I add a second hash over every group of 4 blocks of $x/2$ bits (illustration 2):

Illustration 1

 |-----|-----|-----|-----|   4 hashes of x bits

Total bits = 4*x


Illustration 2

 |-----|-----|-----|-----|   4 hashes of x/2 bits
|-----------------------|   1 hash of x/2 bits

Total bits = 5*x/2 = 2.5*x


Are these equivalent, how do they differ if not and how can I compare them?

Another possibility would be:

 |-----|-----|-----|-----|   4 hashes of x/2 bits
|-----------------------|   1 hash of x bits

Total bits = 4*x/2 + x = 3*x


I couldn't find much on this topic through the usual sources.

• As a note: You're not expected to find collisions in cryptographic hashes, except if they're severely broken or you picked the output length too short. What about just throwing BLAKE2 at your problem and stopping to worry?
– SEJPM
Jan 19 '17 at 8:36