IOTA tutorial 18: Merkle Tree

If you like this video and want to support me, go this page for my donation crypto addresses:

This is part 18 of the IOTA tutorial.

In this video series different topics will be explained which will help you to understand IOTA.
It is recommended to watch each video sequentially as I may refer to certain IOTA topics explained earlier.

The main objective of this video is to provide you with some basic knowledge about the Merkle tree.
The Merkle tree is used in IOTA's Masked Authenticated Messaging.
IOTA's Masked Authenticated Messaging will be explained in IOTA tutorial 19.

A hash tree or Merkle tree is a tree structure in which each leaf node is a hash of a block of data and each non-leaf node is a hash of its children.
This results in a single hash called the Merkle root.
If every node has two children, the tree is called a binary hash tree.

Why use a Merkle tree?
Why not hash all messages (m0-m15), append the hashed messages and then hash it all to get one root hash value.

Bob get the root hash from a trusted source.
If Alice wants to proof to Bob that m6 is not tampered with, she needs to send message m6 and all other hashed values:
H(m0), H(m1), H(m2), H(m3), H(m4), H(m5), H(m7), H(m8), H(m9), H(m10), H(m11), H(m12), H(m13), H(m14) and H(m15) to Bob.
Bob hashes message m6, append all hashes to a single string and hash this string to get one root hash.
Bob compares this new root hash with the trusted source root hash to check if message m6 is not tampered with.

In this example Alice has to provide 15 hashed values and the message m6 to Bob to prove that message m6 is not tampered with.
A much better solution is using a Merkle tree (16 leaves)
Again as before Bob gets the root hash from a trusted source.
If Alice wants to proof that m6 is not tampered with, she needs to send m6 and 4 hashed values to Bob.
With the received information Bob calculates the root hash value.
Bob compares this root hash with the trusted source root hash to check if message m6 is not tampered with.
In this example Alice only needs to provide 4 hashed values and the message m6 to Bob to prove that message m6 is not tampered with.

Using a Merkle tree provides integrity and validity of your data using a small amount of data that a trusted authority has to maintain.
This also means little memory / disk space is needed.

If a Merkle tree has more leaves less hashed values are needed, in comparison to the number of leaves, to validate if a message is not tampered with.

A perfect Merkle binary tree has the following properties:
- The number of leaves is always 2n (n=0, 1, 2, 3,..).
- Each node has 0 or 2 children.
- All leaves are on the same level.
In a perfect binary tree the following formulas can be applied:
Total number of leaves = L = (N + 1) / 2
Total number of nodes = N = 2L - 1
Total number of levels = LV = log2(L) + 1 = (ln(L) / ln(2)) + 1

Number of leaves = L = 1
Number of nodes = N = 1
Number of levels = LV = 1

Number of leaves = L = 2
Number of nodes = N = 3
Number of levels = LV = 2

Number of leaves = L = 4
Number of nodes = N = 7
Number of levels = LV = 3

Number of leaves = L = 8
Number of nodes = N = 15
Number of levels = LV = 4

Number of leaves = L = 16
Number of nodes = N = 31
Number of levels = LV = 5

Check out all my other IOTA tutorial videos:

Subscribe to my YouTube channel:

The presentation used in this video tutorial can be found at:

#mobilefish #howto #iota

[tallsamurai]

This is by far the best explanation I have seen on Merkle trees

[azamatbagatov]

i watched a lot of videos on Merkle trees but this is the only one that really helped me understand what it is. Thank you!

[drj]

This is very clearly explained. Thank you. One small addition would help. To be explicit about which hashed values need to be provided and why. I'm inferring from what was presented that the 4 hashed values that need to be provided in this example are the siblings of the newly computed value at each level. See ~3:30.


Once the hash for m6 is computed, it becomes part of the Merkle Tree at level 5. Then it is combined with the sibling to the right, also at level 5. When the hash is computed, the new value at level 4, one level up, is combined with its sibling, the blue node is given, in the position to the right and a new hash is computed. That new value for the node at level 4 is combined with the provided sibling node at level 4 to yield the grey node at level 3. Once that's computed then it is combined with the provided sibling node at level 2, and finally, the hash computed is combined with the given blue sibling to the right to yield the root node, which is compared to verify that it was not modified.


Level 2, the sibling is at the right
Level 3, the sibling is at the left
Level 4, the sibling is to the left
Level 5, the sibling is at the right side of the computed node,

[Randomuser.anonymous]

It has been a long time since I watched a tutorial explained in this great and well-organized way. Well done, and thank you!

[kartikeyabhargava]

This is so brilliantly done. Thank you for this and keep up the great work. I use this frequently to explain the usage of Merkle Trees to people.

[justJunoGiant]

Absolutely incredible. I love you. Adopt me. Be my teacher fovever. Don't stop being you. It makes sense, I have learned abut merkle trees about 5 times never gave a shit until you explained it to me, then I saw why we use them.

[jabl]

Excellent tutorial! Waiting anxiously for your next video :)

[amalsunil]

Great explanation sir!
But I have a doubt how are the hashes of the intermediate levels of the Merkle tree readily available from other nodes? if they are available then why don't we just get the hash of the message we want to check if it's tampered with?

Well explained, simple and comprehensive. Thank you, few clarifications, please do help with them

MERKLE TREE Properties says

1. Number of leaves always 2^n, where n = 0, 1, 2, 3 .. etc
Explained even number of leafs, what happens when n=0, that means single leaf for a parent node?
in this case how the appended hash will be achieved for that node? since there will be a single hash.

2. Each node will have 0 or two children
Then, what is the significance of the node with '0' children?

[digital-content-guy]

Robert, I love your videos, you're an amazing teacher. I am an IOTA developer and I think you should keep the title Merkle Trees as most IOTA devs that develop MAM don't know the Merkle tree is used.

[swaaalla]

That was really good. Do you also explain why you must follow the path of the blue nodes, they all seem to be the opposing hash.

[penguinmonk]

Thank you, this was a very nice tutorial and a perfect preperation for a paper I am about to read, bless you

[ethandong]

Very clear and well explained. Thank you!

[vishallad]

Along with merkle tree, this video also explain its usage (for usage explanation jump to ~2:20) .. nice video.

[sanchezzak]

Jian




Thanks for the great tutorial! :)

[mockingbird]

3:49 If we need to prove m6 is not modified, Why we need to send m7's hash and the hash of the sibling? Shouldn't we send m6's hash and such? I don't understand that part.

[akinyemidayotafiq]

I'm excited to see exchanges like MEXC Binance and others allowing users to validate their assets using the binary hash tree. This is gonna increase users trust for them. Yeah

[josephdeatrick]

what is the standard protocol for adding to a Merkle Tree if your data doesn't break nicely into a power of 2? i.e. if we currently have 8 blocks of data and then want to append another one.

[georgemavimbela]

Thnak u so much this was so easy to understand

[rishabhbhatnagar]

I don't understand why verification by merkle tree requires siblings of successors from message block to root.