Learn Solidity (0.5) - Merkle Tree
HTML-код
- Опубликовано: 23 дек 2019
- Learn about Merkle tree and merkle proof using Solidity.
Code: solidity-by-example.org/app/m...
Remix IDE: remix.ethereum.org
Solidity: solidity.readthedocs.io
Follow on Twitter: @ProgrammerSmart / programmersmart
Website: smartcontractprogrammer.com 
Наука
just noticed that you are the author of the"solidity by example" which I have been using. Kudos for you.
I don't know what I'd have done without these videos man. Very well explained.
Merkle tree is a complete binary tree, which allows one to calculate all of the information about its parent node simply by been able to differentiate the left and right nodes. I'm glad that MEXC have also adopted it
most underated solidity channel by far
Perfect explanation, thank you!
Really good explanation! Loved it
you did a great job explaining it . thank you
Great explanation dude. Super helpful
Great tutorial! Thanks!
The code in TestMerkelProof assumes you have a list of leaves that is a power of 2 in length, making it generic would be a great programming exercise.
Great explanation! Thanks :)
Jesus, how can you explain so clearly😂, 🐐 always！！！
Absolutely awesome visual !! Very helpful !! But probably need to watch a few time to digest. 🎄 + 🎅 is super 😄
I didn't explain it in the clearest way possible either
Smart Contract Programmer ???!!! I thought it was very well explained!!! Just with my limited brain power 🤯 need to process it slowly 😯
@@smartcontractprogrammer she spoke my mind off. probably you need to define what is proof, leaf, index, root then being the detailed part. but not a big deal a quick google would do
@@kiranvysya Thanks for the feedback. I will explain stuff in more details in future videos
@@smartcontractprogrammer thanks wish you more success
Nice explanation
Great video but slightly confused how we are generating the proofs? We are doing this in the second contract (Test Merkle Proof) right? We are looping through the data/transactions, creating the hashes (aka proofs), and storing them in the "bytes32[] public hashes" array? Also what we are calling "bytes32 public hashes" later becomes bytes32[] public proof which we use in the first contract when we are verifying? In essence "bytes32 public hashes" is our "bytes32 public proof" or do i have something mixed up here?
And with respect to ....
while (n > 0) {
for (uint i = 0; i < n - 1; i += 2) {
is it "i +=2" in the for loop because we are appending everthing to index 2, aka the 3rd transaction? Is that how we are calculating the rest of the proofs?
How would you generate the 3rd leaf, root, and 2 proofs?
Nice!
Pretty poetic.
Nice vidéo 💜💜💜💜💜💜
I didn't understand, that how can anyone get to know the index number of their address? Can anyone explain this please.
Merry Chirstmas!
Thank you for creating such great video. Would you mind to show how to generate Merkle Proof?
there is a merkle tree js library
Does calculating the proof array require calculating the hashes of all nodes of the tree? It seems the highest indexed element of the proof array would require computing all hashes that came before it. Or is there an easier way to access the proof array? Like accessing only the needed elements from a saved list of all hashes of the tree.
simplest solution is to log all the leaf hashes and re-compute all the hashes to produce the proof
Ive watched this 2 times, I still dont understand how the example turns "i" which is 0 in the first iteration into index 3. proof[0] -> index 3?
Is the loop condition correct?
proof[0] = hash(arr[3])
proof[1] = hash(hash(arr[0]), hash(arr[1]))
proof[2] = hash(hash(hash(arr[4]), hash(arr[5])), hash(hash(arr[6]), hash(arr[7]))
i = 0 index = 2 hash = keccak256(hash, proof[0])
i = 1 index = 1 hash = keccak256(proof[1], hash)
i = 2 index = 0 hash = keccak256(hash, proof[2])
Implies that to add transaction we need to wail till transaction are in the form of 2 to pow n ?
Nope, the leaf nodes get duplicated so that the number of leaves is a power of 2, then you can compute the tree (1:19)
Thanks for the video!
So for the entire blockchain, in which the merkle tree can be gigabytes of data - you will need all that data (basically a list of all txs in order) to be able to get the correct hashes to recompute the root and verify that a tx is indeed in the blockchain?
Yes in theory. In practice I think it does other clever cryptographic tricks to save space
Why are those four hashes significant??
Thanks a lot
could you elaborate on what does the proof array actually contain?
does it contain the all the leaf nodes or just the hashes required to build to the root using our leaf?
If it is the latter, which i think it is, i cannot understand how through the variable 'i' we are accessing the required hashes. How are the actually stored?
in the example used in the video, is this how hashes are stored proof=[hash(0,1),hash(3),hash(4,5,6,7)] ?
> does it contain the all the leaf nodes or just the hashes required to build to the root using our leaf?
just the hashes required to build the Merkle root
> is this how hashes are stored proof=[hash(0,1),hash(3),hash(4,5,6,7)] ?
[hash(3), hash(0, 1), hash(4,5,6,7)]
@@smartcontractprogrammer thank you for the response, it is clear now. Completed this playlist. it was really helpful
Hi great video thanks. I see some people including openZeppelin do it without index, does this has special requirements!? Like sorted leafs ?
By sorting, you can prove that an element is in or not in the merkle tree.
Without sorting, you can only prove that an element is in the merkle tree
@@smartcontractprogrammer wow thanks 👏🏻
Can you give the link to explain sorting in merkle proof ?
but
why light theme?
It was my understanding that if a Merkle tree has odd leaves, we assume the current hash of the odd child to be the parent on the next level, not populating the tree with duplicate transactions?
Guess it depends on what sort of encoding you want to do for your tree, but I assumed that was the standard (e.g. for a transaction trie with say 7 transactions)
awesome! excuse me but I don't get it. In 3:00 if you want to check if tr3 is in the block why you just check if the hash is the same that the hash in position 3?
how do you check that the hash in position 3 is correct?
@@smartcontractprogrammer well if you know what your transaction 3 is, you can hash it and compare with the hash. I'm sure I'm missing something here
Nice tutorial. But a question where is the code ? I clicked the link provided for the code but there is no code in that page
solidity-by-example.org/app/merkle-tree
Sorry, how did You find proof hashes? And can this be done automaticly by leaf?
the proof hashes are computed by hashing the hashes of the left and right branch of the tree.
Yes you can compute the proof hashes from the leaf, but the point of merkle tree is that you don't need all leaves to compute the root hash.
@@smartcontractprogrammer I think his question who supplied the proof array, which is basically the list of sibling hash node at each level from the bottom up.
why would your function require customly cherrypicking the N different hashes instead of all the hashes as generated in the constructor in TestMerkleProof ?
that's the idea of merkle tree. You don't need all data to compute the merkle root.
@@smartcontractprogrammer aha so you just need log2 n + 1 items but the ordering has to be very particular for the algorithm to work. from the commented code it wasn't so obvious as to what is going on
man you are damn Good kudos🤭
how did you generate the actual merkle root from the array of strings?
1. hash the array elements
2. hash each pair of hashes
3. repeat 2 until there is only one hash
@@smartcontractprogrammer are you able to search by the specific data point? like if i were looking for an address, would i pass that in as the bytes32[] proof argument? or would it be the hash of the proof as a leaf?
Merkle tree cannot be used to search for a specific address.
It's used to prove that some array element is included in the tree by providing the proof in bytes32[] and then checking that the known and computed merkle roots match
Exactly two years later.
Great explanation, you are a crack
why only those four hashes?
The leaf nodes of the merkle tree are the transactions. Say you want to verify one transaction, you only need one more transaction (the adjacent) to compute the node in the next level, and then you can take the adjacent node to compute the next level node, and so on until you get to the root. So if you have a merkle tree with n levels you only need to know n nodes to verify if your transaction is in the tree.
"proof" is an array of only those hashes which are needed along with leaf to construct the hash root.
"root" is the hash root of the merkel tree, which is supposed to contain my data. Whether this is true, that I need to verify.
"leaf" is the hash of my data/transaction.
"index" is the position of hash of my data/transaction in the array of transactions that constitute the block.
I dont need the other data hashes from the array to calculate the hash root of the merkel tree built from this block. This is the advantage of using merkel tree.
So, if the block contains 'n' data points, I dont need all the hashes of the 'n' data points, instead around log(n) hashes are sufficient to compute the hash root of the merkel tree.
These log(n) hashes are present in the 'proof' array. And these log(n) hashes are present in proper sequence, else the algorithm wont work.
Let's say, there are 8 data in a block.
I take the hashes of each data, and store them in an array (say arr).
I am verifying whether the 5th hash [index 4] in the array is my hash or not.
I already have "leaf" as an input which is supposed to be same as arr[4].
Along with leaf, I will need hash of arr[5] (since index 4%2 = 0, so arr[4] will be hashed with arr[5] ), hash of arr[6] and arr[7] combined, and hash of (arr[0], arr[1], arr[2], arr[3]), which is nothing but hash(hash(arr[0], arr[1]), hash(arr[2], arr[3])).
So, 'proof' array will contain arr[5], hash(arr[6], arr[7]), and hash(hash(arr[0], arr[1]), hash(arr[2], arr[3])) as the three elements.
How will proof array be computed for passing as an input to the verify function, I have no idea about that.
Inside the verify function, the steps are self-explanatory.
First the hash variable is initialised with the leaf value.
The loop will run for three iterations ('proof' array length).
In each iteration, the current hash's index is checked if it is in even position or odd position.
Accordingly the hash operation is carried out with current element in proof array.
The hash value that is calculated in previous step is the parent node of those two elements in merkel tree.
The hash variable is updated with this computed hash value, and the index is divided by 2 to reflect index position of the parent node.
This process is repeated till the final hash value is computed, which should be the hash root of the merkel tree.
If this final hash value is equal to the input hash root, then the block indeed contains the desired data/transaction.
First paragraph is correct.
Can you break down the rest of the sentences? Hard to comprehend without line breaks.
Put in extra effort to make your question easier, I will do my part and answer your questions
still don't understand merkle tree, will come back later when I learned more
I think I'm getting old. I got so lost on this video.
do you live in japan
I feel my brain is limited when I encounter MERKEL TREE dad. lol
yes
you will get used to it
@@smartcontractprogrammer Thanks for your message! I’m in japan too. Have a nice day!
Let's NOT reveal where in Japan we live. Keep it zero knowledge proof :D
+algorithm
confused the fuck out out of me bro...
Thanks. I will try better
Not well explained !!!
I will try better next time