How can one find an element in a Merkle tree, as effectively as possible?

Each internal node has a hash value. So I think, first, hash the value to find, and if an internal node has the same value exactly, get its leaf node. But this is correct in 2-depth, not all cases. Because each internal node has a hashed what is concatenation of their child nodes, by the avalanche effect, the concatenated hash value is unexpected.

So I cannot find the value to do hash and compare.

  • $\begingroup$ I can't understand your second paragraph at all, though I guess the question is clear enough from the first paragraph. :-) $\endgroup$ – David Richerby Jul 29 '16 at 8:50

Merkle trees are not designed to support efficient lookup. The best you can do is search the entire tree (all the leaves) and check each node for a match. This is $O(n)$ time.

If you want to be able to efficiently look up an item in a Merkle tree, construct a separate "index": i.e., a separate hashtable (or binary search tree) storing the mapping from hash value to position in the tree.


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.