Given just the hash of a file, can I verify that the file contains a specific data block?

Question

Imagine I only have the hash of a file which we can call hash(file). Then a user sends me a data block (or section) of the same file, which we can call section1(file). Is there a way to verify that such section belongs to the file, given only the hash of it?

I was thinking of constructing a Merkle tree. So the hash(file) would actually by the Merkle root. However, to verify that a section belongs to the file I would need the entire Merkle tree (not just a single hash).

Any thoughts about proving that a file contains a specific data block? It doesn't matter which hashing methodology I use as long as I can verify it with little information.

Answer 1

Assuming that you know that $h_0$ is the root hash of a Merkle tree for the file, you can be sure that $h_1$ is a hash of a section of the file if you know that it's one of the hashes of the sections one level below the root and you know its sibling hashes, i.e. you have values $(h_1^1, \dots, h_1^{m_1})$ such that $\mathscr{H}(h_1^1, \dots, h_1^{m_1}) = h_0$ where $\mathscr{H}$ is the hash function used to build the Merkle tree. Because of collision resistance, if you have a preimage for $h_0$, it must be the right one, so the $h_1^k$ values are the hashes of the section at a level below.

More generally, you can verify that $h$ is a hash of a section of the file knowing the hashes of the siblings of that section, and the hashes of the siblings of its parents, and so on recursively up to the root. This requires the knowledge of $b \cdot n$ hashes where $n$ is the depth of the section and $b$ is the tree's branching factor. Note that you only need to be given the hash values, you don't need to trust them; they'll all be verified in the process.