snippetMinor
How can one find an element in a Merkle tree?
Viewed 0 times
canhowoneelementfindtreemerkle
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#61019, answer score: 3
Revisions (0)
No revisions yet.