Cheap and Secure Web Hosting Provider : See Now

[Answers] How can one find an element in a Merkle tree?

, , No Comments
Problem Detail: 

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.

Asked By : Donghyeon Lee

Answered By : D.W.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/61019

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback