1. What is a Merkle tree?
2. Cryptographic Hash Functions
3. How do Merkle trees work?
4. Merkle trees Uses
5. Why it used in Bitcoin?
Source: Bitcoin whitepaper
What is a Merkle tree?
Merkle tree (also known as hash tree) a tree in which every leaf node is labelled with the cryptographic hash of a data block, and every non-leaf node is labelled with the cryptographic hash of the labels of its child nodes.
In a Merkle tree, every non-leaf node is labelled with the hash of the labels of its child nodes (or the hash of the value of a leaf at the bottom of the tree), a process which repeats itself moving up the tree until a single hash remains: the Merkle root.
Merkle root: is the hash of all the hashes of all the transactions that are part of a block in a blockchain network.
Its structure is used to efficiently verify the integrity of data in a group.
The idea was created and patented by Ralph C. Merkle in 1979, with the patent expiring in 2002.
Cryptographic Hash Functions
Hash function is any function that enables us to obtain an output of a fixed size as it is completely unique to the input and the function itself is deterministic.
It also leads to significant savings in storage and helps increase efficiency.
You can find out more information by reading the previous topic that I wrote about hash function for dummies
Example:
Code:
In-put: H
Out-put: 44bd7ae60f478fae1061e11a7739f4b94d1daf917982d33b6fc8a01a63f89c21
In-put: Husires
Out-put: 198d93f2c0bff9767d4cdc047f2191b0921d81e410c10c0744311fadfdb516f9
In-put: Today is 1/9/2020 and i used my username: Husires
Out-put: 2afbf1c88e101259002a592dbcc9340af2f0fa8f51a06e77910b6aca63a97c0c
In-put: Today is 1/9/2020 and i used my username: Husires
Today is 1/9/2020 and i used my username: Husires
Today is 1/9/2020 and i used my username: Husires
Today is 1/9/2020 and i used my username: Husires
Today is 1/9/2020 and i used my username: Husires
Out-put: 43a322d0eb09caaf26762ae18a369f5e8e06ac32c9e6a0d9fb4972aa53654db8
What did you get from this example?Out-put: 44bd7ae60f478fae1061e11a7739f4b94d1daf917982d33b6fc8a01a63f89c21
In-put: Husires
Out-put: 198d93f2c0bff9767d4cdc047f2191b0921d81e410c10c0744311fadfdb516f9
In-put: Today is 1/9/2020 and i used my username: Husires
Out-put: 2afbf1c88e101259002a592dbcc9340af2f0fa8f51a06e77910b6aca63a97c0c
In-put: Today is 1/9/2020 and i used my username: Husires
Today is 1/9/2020 and i used my username: Husires
Today is 1/9/2020 and i used my username: Husires
Today is 1/9/2020 and i used my username: Husires
Today is 1/9/2020 and i used my username: Husires
Out-put: 43a322d0eb09caaf26762ae18a369f5e8e06ac32c9e6a0d9fb4972aa53654db8
How do Merkle trees work?
Let's simplify it, suppose you have a large file size of 8 GB and you want to verify its authenticity, so you match the hash that you have with the hash that was made available to the public by the developers and therefore if each file in it matches all the data then you downloaded the correct file, but how will we do that?
you can compare each file separately until you reach the last file (so you need to compare 8 GB files) but it will take a long time. Merkle trees offer a solution which will reduce your running time.
First, we will divide the big problem into smaller ones. For example, instead of having an 8 GB file, we will divide it into eight pieces. Call the different parts A through H. Then each part is passed through a hash function, which gives us eight different hashes.
Now we take each pair and compare them (hA + hB, hC + hD, hE + hF, and hG + hH,) and then combine them, using the hash function and repeat.
So any slight modification to the data will give us a completely different Merkle root. We can also check the non-conforming part easily.
Merkle trees Uses
can be used to verify any kind of data stored, help ensure that data blocks received from other peers in a peer-to-peer network are received undamaged and unaltered, used in the IPFS, Btrfs and ZFS file systems, the Bitcoin and Ethereum peer-to-peer networks, and a number of NoSQL systems such as Apache Cassandra, Riak, and Dynamo.
Why it used in Bitcoin?
They are an integral part of every block, as they can be found in the block headers.
Use it in SPV: Many of us have limited resources in terms of space and internet so we all rely on light clients, and instead of downloading all block transactions, you require Merkle proof - evidence provided by the full node proving that your transaction is in a particular block.
If we go back to the previous example, we can verify through 3 steps instead of 7 steps, for example to verify hB. If we have hA, we can work out hAB. so we can calculate hABCD by using hCD and with hEFGH, we can check that the resulting Merkle root matches the one from the block header.
3 Steps only.
You can read more in https://bitcoin.org/bitcoin.pdf
It has some Drawbacks with a successful 51% attack which will talk about it in another topic.
Mining: Bitcoin block is made up of two pieces, Header (fixed-size) and a list of transactions (variable-size)
Often times, much of the block remains the same, and the nonce is changed.
Merkle root simplifies the whole process, the miner selects all the transactions it wants to include in the block, creating a Merkle tree and only need to hash the head of the block, rather than the entire block.
Hence, any change in the transaction list will change the Merkle root and thus reject the block.
Sources
Code:
https://en.wikipedia.org/wiki/Merkle_tree
https://brilliant.org/wiki/merkle-tree/
https://www.youtube.com/watch?v=fB41w3JcR7U
https://golden.com/wiki/Merkle_tree-W3DMKV
https://academy.binance.com/blockchain/merkle-trees-and-merkle-roots-explained
https://blockonomi.com/merkle-tree/
https://brilliant.org/wiki/merkle-tree/
https://www.youtube.com/watch?v=fB41w3JcR7U
https://golden.com/wiki/Merkle_tree-W3DMKV
https://academy.binance.com/blockchain/merkle-trees-and-merkle-roots-explained
https://blockonomi.com/merkle-tree/