Assuming a $k$-ary Merkle tree:

If the length of a file is known, based on a fixed chunk size, one could calculate the number of chunks and thus the depth of the tree. Then, based on $k$, the chunk index and the depth, one can parallelize the construction of the Merkle tree.

But if the file size is not known, i.e., the input is a stream, and we are reading the input until EOF, what could be an efficient procedure to build up the $k$-ary Merkle tree, assuming as usual that leaf nodes contain the chunk hash, while branch nodes contain the hashes of their children?

  • $\begingroup$ One could first read the input until EOF, then out of this determine the number of chunks and thus build the tree the same way as described in the question. I wonder if one can just read chunks and then send them to a routine in parallel and build the tree as we go... $\endgroup$ – faboolous Mar 26 '17 at 20:29
  • 3
    $\begingroup$ I'd create a scheme with a fixed block and size (say, 4KiB) and $k$ value, say 16 minimum (to allow 16 worker-threads to calculate the values). You can always create a new root (i.e. make the tree deeper) when you need more space. In other words, I would make the Merkle tree depth a function of the size. But that's just my idea / opinion. $\endgroup$ – Maarten Bodewes Mar 26 '17 at 21:53
  • $\begingroup$ @MaartenBodewes it took me some time to understand what you mean. But I think your basic proposal is what I will need. Thanks. (You can post it as an answer if you like, I didn't post any code either so I may accept your generic idea, but I'll give myself some time) $\endgroup$ – faboolous Mar 29 '17 at 17:31

Your Answer

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

Browse other questions tagged or ask your own question.