Merkle trees and Merkle roots are cryptographic data structures invented in the 1980s. Satoshi Nakamoto, the founder of Bitcoin (BTC), implemented this technology for Bitcoin’s SHA-256 hashing algorithm to help verify transactions and blocks on the Bitcoin blockchain.
The Merkle tree in Bitcoin and other crypto is used as a digital footprint to process and verify transactions. If we need revert back to the first transactions of Bitcoin in 2009, we can use the hashes of those transactions and locate them on the blockchain using block explorers.
Back in 1995, a time-stamping service called Surely published hash values for ads in the NY Times. This was the first commercial deployment of blockchain technology, and since Satoshi Nakamoto implemented it in Bitcoin, it was used in all other popular altcoins.
What Is A Merkle Tree?
A Merkle tree is a digital hash tree comprised of multiple nodes (computers). These nodes join together to create a tree-like structure. Miners use the hash values to broadcast transactions and produce new blocks on the blockchain.
Unlike a physical tree in the real world, tree structures are usually reversed with the root node at the top and branches spreading downward, each terminating in one or more leaf nodes.
Merkle trees are comprised of multiple transaction hashes. For example, a single Bitcoin transaction hash can be included in one of the bottom leaves, which are then joined together and hashed in another tree branch called a block.
The Merkle tree of the Bitcoin blockchain. (Source: Medium)
What Is A Merkle Root?
A Merkle root is the ultimate hash that combines all hashes in the Merkle tree. Once all the transactions in a Merkle tree are hashed together, they produce the final hash known as the Merkle root.
Let’s say you have 200 transactions at the bottom of the Merkle tree, then those are hashed to 50 transactions, then 10, then 5, then 1. The final hash would represent all previous hashes in a group and used as an identifier for all those transactions combined.
easily because each block is represented by a single root hash. Merkle roots are used to verify the accuracy of previous blocks. Each block can only have one Merkle root and historic data can be synced
History of The Merkle Tree
The technology behind the Merkle Tree was patented in 1989. It’s named after Stanford professor, Ralph Merkle, who invented the technology by publishing a paper on digital signatures called “A Certified Digital Signature”.
Decades before Bitcoin was invented, cryptography was used in software development to secure data. The Merkle tree was one of the ways to verify giant batches of data and save memory.
If you have a large encrypted database and don’t want to individually verify the validity of small parts of the database, you could use the Merkle root to verify the hash data of an individual part of the database and save on memory.
Merkle’s paper was featured in the Bitcoin Whitepaper as one of the core components of Bitcoin. He remained a supporter of crypto and advocated for the advancement of DAOs (Decentralized Autonomous Organizations).
Hashing Data on Bitcoin
To understand how Merkle trees help save memory, we start at the hash. Hashing is cryptographic technology that produces a unique number for each encrypted computation.
If you compile a set of data and hash it, it will produce a number that cannot be changed for that set of data. For example, if you upload your Bitcoin private keys and hash them, then the output will be the same no matter how many times you re-hash it. If you change one number, the output hash will be different.
In blockchain, the block hash numbers are fixed to ensure the blockchain cannot be breached. If the transaction hashes don’t match with the Bitcoin blockchain’s Merkle root, the transaction will be invalidated by the nodes on the Bitcoin network.
The problem is that large databases such as blockchains need to hash together millions of transactions at the same time. Since 2017, more than 5 million transactions were processed on the Bitcoin blockchain.
Cumulative transactions on the Bitcoin blockchain since 2017. (Source: Statista)
If each transaction ID was indexed in a large hash file, it would require a lot of memory to access a particular transaction. This would make the Bitcoin blockchain unusable for users that are not miners.
However, if every transaction is hashed in a single Merkle root, you can instantly access that transaction without having to download the entire Bitcoin blockchain (350GB at the time of writing).
The Merkle tree allows users to instantly send transactions on the Bitcoin blockchain. Instead of downloading a data-heavy blockchain, a user can download a light client for the Bitcoin network such as Electrum (one of the oldest Bitcoin wallets) and transact from that wallet.
Satoshi Nakamoto used Merkle roots for the “Simple Payment Verification” (SPV) feature of Bitcoin to support light clients. These wallets can connect to blockchain nodes and send or receive Bitcoin without downloading the entire Bitcoin blockchain.
Bitcoin Block Metadata
The Bitcoin blockchain is comprised of thousands of “blocks” that contain transactions, and the net summary of those blocks creates the blockchain. The memory size limit for blocks is 1 MB.
Satoshi implemented a 1MB limit for block size. (Source: BitcoinInsider)
At an average rate of 550 bytes per transaction, the Bitcoin network can process up to 3,500 transactions per block. At the current average, most blocks carry between 1,500 and 2,000 transactions per block. This averages it down to 4–6 transactions per second.
Bitcoin blocks have “headers” containing metadata about the block. The header data is hashed to create proof of work which gives out mining rewards for nodes — computers that validate the network.
Bitcoin runs on a consensus algorithm that specifies certain hashing and work standards a node has to compute in order to receive awards. A miner has to hash data thousands of times in order to produce ideal mathematic conditions that allow them to mine a block. A miner could even make billions of attempts before they can mine a block and receive an award.
As mining difficulty increases, the network consumes more energy for computation. In the past when the computation difficulty requirements were lower, people were able to mine Bitcoin on their laptops using their graphics cards.
Recently, mining work is done on ASIC miners such as AntMiners that are energy-intensive and cost tens of thousands of dollars.
When a miner makes a computing attempt, they have to hash the header of the block and all the transactions in it. The header weighs 80 bytes and contains the Merkle root hash at 32 bytes. This is smaller than the transactions in the block, each occupying an average of 550 bytes.
Bitcoin transactions have measurable memory consumption, which can be viewed on block explorers, such as Blockchair, under “size.” In this example, a Bitcoin transaction consumed 343 bytes:
Data from a Bitcoin transaction that consumed 343 bytes (Source: Blockchair.com).
As blocks are passed on, miners only need the header hash of the previous blocks instead of the whole blocks to advance the chain.
The Merkle tree allows miners to streamline the hashing process. Satoshi designed Bitcoin in such a way that all block transactions are compact and easy to validate. Later, if a block is accepted as valid by other nodes, the transaction list cannot be reverted, because that would reverse the irreversible blockchain and change the Merkle root.
Validating Blocks Using the Merkle Tree
The Merkle tree is used to validate the authenticity of the blocks.
Bitcoin transactions and blocks are stored in a sequential order since the original Genesis Block of Bitcoin in 2009.
Candidate blocks passing data on the Bitcoin ledger. (Source: OpenNode)
At the highest level is the single Merkle root. Everything below it comprises the Merkle tree. There are two types of nodes below the Merkle root: leaf nodes and non-leaf nodes.
Leaf nodes are transactions on the Bitcoin network. There can be thousands of transactions/leaf nodes in a single block. Each leaf node is identified with a transaction ID (TXID).
Leaf nodes are hashed together to create non-leaf nodes. Depending on the size of the block, the number of leaf nodes and non-leaf nodes hashed varies. However, at the top there are always two final non-leaf nodes and a Merkle root.
For example, in a block with 1,500 transactions, there would only be two transaction hashes (non-leaf nodes) at the highest level. Below that, we would have a tree terminating in 1,500 leaf nodes. Each one of these hashes feeds into each other until it reaches the top two nodes.
The top two nodes are the nodes below the main Merkle root, hence the name “Binary Tree.” Above the top two nodes, there is the Merkle root, a hash that contains information about every single hash that occurred on the Bitcoin network and can be invoked to validate the authenticity of every block and transaction.
If a miner wants to verify that a certain transaction came from a certain block, they can check the Merkle root for that particular block and validate it.
The payment verification process on Bitcoin. (Source: CoinGeek)
This is how the block header looks in the native C++ code that the Bitcoin blockchain is written in:
The Bitcoin block header includes metadata about a candidate block. (Source: DataDrivenInvestor)
If a transaction claims to come from block #12,213 on the Bitcoin network, the miner would only need to check block #12,213’s header for information and would not have to connect to block #12,212 or #12,214, or any other blocks, easily verifying the authenticity of the transaction.
This process forms a parent-child relationship between the main Merkle root of the blockchain and the millions of leaf nodes carrying it. It also makes it easier for miners to do their jobs, such as validating blocks and producing new ones.
Conclusion
Merkle trees and Merkle roots are tools whose primary purpose is to hash cryptographic data and make it accessible for software applications.
Merkle roots have been used in crypto, in particular Bitcoin, since the beginning of the Genesis block for hashing transaction IDs and blocks. They were later adopted by altcoins such as Ethereum (ETH) and thousands of other cryptos.
Satoshi’s vision was to scale Bitcoin to millions of users, and the only way to achieve that was to simplify blockchain syncing so that data could be used by light wallets such as mobile wallets that could interact with the blockchain without having to download the entire blockchain.
Satoshi also introduced the “Simplified Payment Verification” (SVP) feature that allows users to use Bitcoin without running their own node. This is one of the main reasons crypto reached critical mass and adoption among millions of users.
Register to get $180 Welcome Bonus!
