in this article, the principle behind the Merkle tree would be broken down and the relationship between the blockchain and Merkle tree would be explained.
Merkle tree is an important component of the blockchain that makes the blockchain work and perform efficiently. Merkle tree basically is an efficient storage and verification system which can take in a large chunk of data and provides a functionality where one of the chunks of data can prove that it is a part of the data chuck without fetching the full data chunk.
Merkle tree employs a cryptographic hashing function to carry out this functionality and it is important to know that the simplest form of merkle tree is a binary merkle tree.
How is merkle tree used in the blockchain?
Merkle tree has some implementation in the blockchain, but I would be stating two and explaining one.
Block Header computation and block transaction proof
NFT minting whitelisting
Block Header computation
A block in a simple text can be said to be a sum of transactions, meaning a block can contain any amount of transaction depending on the blockchain’s specification. So let’s paint this scenario; A block containing ten thousand transactions, to prove that 1 transaction(a) is a part of these ten thousand transactions we would have to fetch all these transactions and loop through each of them to see if the transaction(a) is part of the ten thousand transactions. Now as observed, this process is very inefficient, with a time complexity of O(n) and a total waste of computation power and storage. A Merkle tree on the other hand if employed can solve this problem with a time complexity of log(n) and also save computational power and storage. Now I guess you are wondering how this Merkle tree works seeing that it is this powerful.
Technically, How does a Merkle tree work?
Considering this example, this is an array of transactions [0,1,2,3,4,5,6,7,], to compute a merkle tree from this array, each of this transactions are first hashed using a hashing function h, resulting in this new array; [h(0), h(1), h(2), h(3), h(4), h(5), h(6), h(7)], now a process similar to a binary tree algorithm is carried out in such that the index 0 and index 1 of the array are summed and hashed so does index 2 and 3 then index 4 and 5 on and on till this result is achieved [h(0+1), h(2+3), h(4+5), h(6+7)]. The same process is carried out again to achieve this [h(0+1+2+3), h(4+5+6+7)] and the process is carried out again to return this; [h(0+1+2+3+4+5+6+7)], this output is regarded as the merkle root of a no leaf node. Using the merkle root, a member of the array transaction(a) can be proven to really be a member of the array transactions without fetching all the members of the array.
Benefits of Merkle Trees
Validate data integrity
Take a very little disk space
Tiny information across networks
Efficient and non-time costly verification
Why is a Merkle essential to the blockchain?
- Verifying that a transaction was mined in a block would be very time consuming and computationally costly.
