3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ To prove that a section belongs to a Merkle tree, you only need to provide the path up to the root; you don't need to provide the entire Merkle tree. $\endgroup$ – Chris Aug 14 '15 at 22:01
  • $\begingroup$ Right but the user could give me any section, hence I would need all the paths. $\endgroup$ – Luca Matteis Aug 14 '15 at 22:02
  • $\begingroup$ The user gives you any section, and then you provide the path from that section up to the root. You only have to provide the entire tree if you have to provide a proof for every section in the file. $\endgroup$ – Chris Aug 14 '15 at 22:08
  • $\begingroup$ Right but my requirement is that I don't want to provide the proof to the user, I want to prove it myself with as little information as possible. The user sends me section of the file, and I need to prove (just for my own sake) that such file section is "contained" within my hash. $\endgroup$ – Luca Matteis Aug 14 '15 at 22:10
  • $\begingroup$ Ah I guess what you're saying is that the user could send me the path? $\endgroup$ – Luca Matteis Aug 14 '15 at 22:12
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.