Blockchains process thousands of transactions with each block before it gets added to the digital ledger. Since blockchains are built upon public-key cryptography that requires hashing out data, this means that the network has to validate thousands of hashes in order to have a single valid block. How do blockchains manage that? Simple, they use Merkle trees.
Merkle trees are data structures that are used in blockchains to efficiently encode data and significantly reduce the amounts of data needed to be processed for the purpose of verification.
So, what are Merkle trees and why are they so important?
Blockchain Hashing
Before we get into what Merkle trees are, let’s have a recap of how blockchains verify transactions. After conducting a transaction, miners group a batch of transactions into a single block. Then, each miner competes in solving complex computing puzzles in order to have a chance of winning the block reward, thus adding the block to the blockchain.
Every transaction conducted on the blockchain uses hashing algorithms to increase the security of the ledger, avoiding any possible attack. Hash is a mathematical function that transforms an arbitrary length of data (input) to a fixed encrypted value (output). This means that all transactions present within a block are hashed.
Example of a hash function:
Input: Chainwitcher
Hash: c5165a52fc12c022ff975d35ba02bef5df68c2d56eab1bd4d72c88f0e6826cf5
So, imagine in a world where there are no Merkle trees, each node has to download the entire terabyte-sized blockchain with the addition of verifying each transaction one at a time. So, how do Merkle trees make this process efficient?
What Is a Merkle Tree?
Merkle trees are named after the scientist Ralph Merkle who also was one of the creators of public-key cryptography. Also known as Binary hash trees, Merkle trees are mathematical data structure used in computer science that aids in verification and security. In blockchains, Merkle trees are used in order to quickly check the validation of the overall data without having to check every single data.
In simpler terms, it’s basically grouping all transaction hashes into one single hash. This way, miners can check whether a certain transaction is valid by looking at the overall hash, instead of going through all hashes in a block.
Let’s see how a Merkle tree is structured to get a better understanding:
Merkle trees are tree-like structure that has 3 elements:
- Merkle Root
- Non-leaf Nodes
- Leaf Nodes
Merkle trees are binary tree structures. What does that mean? It means that each node has two child nodes. Also, Merkle trees work from the bottom up instead of the other way around.
This means that transactions’ hashes get grouped together in pairs and rehashed to get their parent hash. Then, the two parent nodes/hashes get hashed together again to get their equivalent parent node, and so on until the last possible hash.
Leaf Nodes
Each crypto transaction in a block has a specific ID (TxID). When a miner hashes the transactions’ IDs, these hashes are referred to as leaf nodes. This is due to the fact that the first hashes are the very first elements in a Merkle tree, and being at the very extreme of the tree makes them resemble “leafs”.
Non-Leaf Nodes
After creating the hashes of the transaction, miners would then combine leaf nodes in pairs and hash them together again. This creates an upper layer of hashes called “non-leaf nodes”. The layer is non-leaf because, well, it’s in the middle tier of the tree. You can consider it as the branches of the Merkle tree.
So, if every pair of leaf nodes get hashed together to create one parent non-leaf node, this means that there are half as many hashes in this layer as opposed to the leaf node layer. These non-leaf layers will continue to be hashed in pairs as the tree narrows until two non-leaf nodes remain.
Merkle Root
The hash of the last remaining pair of leaf nodes creates the Merkle root. The Merkle root is the hash of all transactions combined that later gets stored in the block header. Miners can verify a transaction in the leaf node layer by just verifying the Merkle root. So, this last hash makes sure that data blocks are unaltered and undamaged.
What If There Are No Pairs?
Sometimes, transactions in a block can be an odd number. This means that one hash would not have another one to be paired with. In this case, the hash of the single leaf node will be duplicated repeatedly to provide an even number of nodes.
How Do They Work?
We’ve established that Merkle trees are created by hashing different pairs of nodes until one hash remains, which is the Merkle root. Let’s illustrate in an example how this would work to get a better understanding.
Let’s say we have four transactions in a block. Transaction A, B, C, and D. Each transaction has its own respective hash, Hash A, Hash B, Hash C, Hash D. Here, every hashed transaction gets combined with another hashed transaction to create a new hash. In this case, Hash A pairs with Hash B to create Hash AB. So do Hash C and Hash D to create Hash CD. The last pairs of hashes we have now are Hash AB and Hash CD. These two hashes pair together to create the final hash of all transactions, Hash ABCD, which is also the Merkle root.
So, what happens after we have the Merkle root? This hashed value gets added to the block header of a proposed block. Miners verify transactions using only the Merkle root instead of going over all hashed transactions.
Benefits of Merkle Trees
Merkle trees are very beneficial, especially for blockchain technology. Let’s see what advantages they provide.
Insures Immutability
In blockchains such as Bitcoin, each block has a unique Merkle root hash. The block is linked to the previous block by also containing the previous block’s Merkle root, thus forming a chain of data. If any transaction is altered or changed, so will its hash, and consequently, so will the Merkle root. This will render the block and its hash invalid. This then is reflected by the next block holding the previous block’s invalid hash, and thus, the whole blockchain becomes invalid. Therefore, Merkle trees make sure of data immutability.
Efficient Block Verification
Another benefit Merkle trees provide is their efficiency when it comes to data verification. The blockchain is made up of thousands of blocks, with each block holding thousands of transactions. This will require massive computing power in order to process these transactions. Without Merkle trees, miners would have to go over every single transaction. Merkle trees however reduce the amount of data that has to be processed during verification.
Importance of Merkle Trees in Blockchain
Merkle trees are a fundamental technique used in blockchain technology. They facilitate the fast processing and verification of blocks without the need for heavy computational power. They compress large sets of data by hashing transactions together in an efficient manner. In short, Merkle trees enhance data integrity, speed up validation, reduce storage requirements, and facilitate a secure and transparent verification process.