IOTA tutorial 18: Merkle Tree
HTML-код
- Опубликовано: 18 мар 2018
- If you like this video and want to support me, go this page for my donation crypto addresses:
/ mobilefish
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:
goo.gl/aNHf1y
Subscribe to my RUclips channel:
goo.gl/61NFzK
The presentation used in this video tutorial can be found at:
www.mobilefish.com/developer/...
#mobilefish #howto #iota 
Наука
It has been a long time since I watched a tutorial explained in this great and well-organized way. Well done, and thank you!
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.
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,
Thank you very much.
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!
Excellent tutorial! Waiting anxiously for your next video :)
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.
This is by far the best explanation I have seen on Merkle trees
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.
Thank you, this was a very nice tutorial and a perfect preperation for a paper I am about to read, bless you
Thank you for the lucid explanation.
Thanks for this amazing tutorial !!
Very clear and well explained. Thank you!
Excellent explanation Sir. Thanks.
thank you, very well-explained!
Thnak u so much this was so easy to understand
Excellent video!!!!!!
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.
Jian Yaaaaaang
Thanks for the great tutorial! :)
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?
Very helpful. Thanks.
Good explanation!
great video!
💗 Great video! 😍 😻
thanks, it clears a lot
Thank you! :)
Thank you so much
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?
Thank you!!
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
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.
best 6 minutes of my life
good stuff :)
Got it!
Along with merkle tree , this video also explain its usage (for usage explanation jump to ~2:20) .. nice video.
Saw this comment at 2:18.
Lucid af!
Hi Professor, I have a question. In the example where you explained about what are the hash values, Alice needs to send Bob while using Merkle Hash Tree. Can you please tell me how to decide that what hashed sibling values Alice has to send? For instance, if we look at the leaf node m6 then off course m6 hash is not required to be sent (because Bob should compute it) so we select hash of m7. but later on why the hashed value from the leftmost part of the tree? why not the rightmost part of the tree? Sorry, I am pretty naive to this field I hope you will guide me. Thank you for your amazing effort in making these videos. I hope you will come up with more videos covering other crypto areas as well.
So the data is indeed sent to Bob (then Bob computes hash). Call the level of the data level 0. When Bob calculates the hash of the data that was sent, he has available one hash on level 1 (one level higher than the original data). Then, in order to proceed to calculate the root hash, you need the hash value of the sibling of the data that was sent... Because you want to combine this sibling's level 1 hash with the hash you computed from the data that was sent. If you have that sibling's hash, you can compute a hash of level 2 by combining the two level 1 hashes you have available now. But in order to be able to proceed to a level 3 hash, you need the 'neighbor' hash of the level 2 hash you calculated.
This explains exacly the hashes you need to send in a Merkle tree. :)
@@BongboBongbongThank you sir. Can you please tell me which type of traversal it is? If I am not wrong there are further classifications for traversal styles in Merkle Tree.
How to define the message is m6 but not other?
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.
I don't understand why verification by merkle tree requires siblings of successors from message block to root.
Binary tree Data Structure
I like Merkle tree more...
4:17
15, not 16
Merkle Tree is not IOTA specific I suggest changing the name to blockchain basics
You are very sharp! I was thinking doing that, but I have decided to make it part of the IOTA tutorial series otherwise IOTA developers / interested parties are going to say "hey... IOTA has nothing to do with blockchain.." when referring a link to a blockchain tutorial.
And the next tutorial 19 "Masked Authenticated Messaging" will nicely build upon tutorial 18.
Thanks, I really want to learn about IOTA functionalities :)
IOTA has a Miracle Tree :-)
Mobilefish.com thank you for sharing all the tutorials, they are great
Merkle trees are not specfic to blockchains; authors choice, authors power, authors altruism.