<blockquote>
<p>I've read and watch about merkle trees but can't figure out how to implement is_present(element) method.</p>
</blockquote>
<ol>
<li>Put the entire contents of the merkle tree in an array.</li>
<li>Check that the result of hashing all of the elements equals the root of the merkle tree. (If not, this is not the correct merkle tree.)</li>
<li>Check if the element is in the array.</li>
</ol>
<p>This takes O(n) time and space, where n is the number of elements in the merkle tree.</p>
<h3>Proving that to another node</h3>
<p>You can create a proof that a particular element is in a tree. This proof takes O(log n) space to store, and O(log n) time to verify, but still takes O(n) time to construct.</p>
<p>Construction:</p>
<ol>
<li>Run through steps 1-3 above.</li>
<li>Start with the element you want to prove the presence of. Add it to the result list.</li>
<li>Find its buddy. In other words, find the hash that it would be hashed with to form the merkle branch containing both. Add it to the result list.</li>
<li>Repeat 2 through 3 until you get to the merkle root, which has no buddy.</li>
<li>The resulting list is your proof.</li>
</ol>
<p>Verification:</p>
<ol>
<li>Start with the first item in the list. Verify that it's the one you're trying to prove the presence of. Set A to this.</li>
<li>Hash it with the second item, with it either first or second depending on where the original item is in the merkle tree. Set A to this hash.</li>
<li>Repeat 2 with the next item until you run out of items.</li>
<li>Verify that A equals the merkle root.</li>
</ol>
<p>If the merkle tree is in sorted order, you can also create a proof that an element is <em>not</em> in the merkle tree. It works in a similar way, except that you find the two elements that would have been the neighboring elements. Then, you prove that both are in the tree, and that they are next to each other.</p>

CC BY-SA 3.0
2016-11-06T08:32:27.353Z
for me the most tricky part is finding "buddy". Can you explain how to find it?
ka4eli
CC BY-SA 3.0
2016-11-06T21:19:30.910Z
A tl;dr: you don't check whether something is present in a Merkle tree. You ask the party who claims that something is in it to prove to you instead.
Pieter Wuille
CC BY-SA 4.0
2023-06-16T00:20:21.307Z
Why would `hash(hash(A, B), hash(C, D)) == hash(A, B, C, D) `?
Zaz
CC BY-SA 4.0
2023-06-16T00:21:42.470Z
@Zaz It doesn't.
Nick ODell
CC BY-SA 4.0
2023-06-21T17:45:32.360Z
Then why would the hash of the array equal the root of the Merkle tree?
Zaz
CC BY-SA 3.0
2016-11-06T00:03:17.857Z
2016-11-06T04:07:00.570Z
2020-06-16T11:10:03.350Z
Nick ODell
<p>I've read and watch about merkle trees but can't figure out how to implement <em>is_present(element)</em> method. Explainations and links are accepted.</p>

<blockchain><merkle-tree>
Algorithm of checking whether an element is present in a merkle tree
ka4eli
# Algorithm of checking whether an element is present in a merkle tree

(Asked by: username_0 on 2016-11-05)

I've read and watch about merkle trees but can't figure out how to implement *is\_present(element)* method. Explainations and links are accepted.

**Tags:** blockchain, merkle-tree


---

## 1 answers

### Answer by username_1 on 2016-11-06. Score: 7 | Accepted answer

> I've read and watch about merkle trees but can't figure out how to implement is\_present(element) method.

1. Put the entire contents of the merkle tree in an array.
2. Check that the result of hashing all of the elements equals the root of the merkle tree. (If not, this is not the correct merkle tree.)
3. Check if the element is in the array.

This takes O(n) time and space, where n is the number of elements in the merkle tree.

### Proving that to another node

You can create a proof that a particular element is in a tree. This proof takes O(log n) space to store, and O(log n) time to verify, but still takes O(n) time to construct.

Construction:

1. Run through steps 1-3 above.
2. Start with the element you want to prove the presence of. Add it to the result list.
3. Find its buddy. In other words, find the hash that it would be hashed with to form the merkle branch containing both. Add it to the result list.
4. Repeat 2 through 3 until you get to the merkle root, which has no buddy.
5. The resulting list is your proof.

Verification:

1. Start with the first item in the list. Verify that it's the one you're trying to prove the presence of. Set A to this.
2. Hash it with the second item, with it either first or second depending on where the original item is in the merkle tree. Set A to this hash.
3. Repeat 2 with the next item until you run out of items.
4. Verify that A equals the merkle root.

If the merkle tree is in sorted order, you can also create a proof that an element is *not* in the merkle tree. It works in a similar way, except that you find the two elements that would have been the neighboring elements. Then, you prove that both are in the tree, and that they are next to each other.

> **Comments:**
> **username_0**: for me the most tricky part is finding "buddy". Can you explain how to find it?  
> **username_2**: A tl;dr: you don't check whether something is present in a Merkle tree. You ask the party who claims that something is in it to prove to you instead.  
> **username_3**: Why would `hash(hash(A, B), hash(C, D)) == hash(A, B, C, D) `?  
> **username_1**: @username_3 It doesn't.  
> **username_3**: Then why would the hash of the array equal the root of the Merkle tree?  

---

