A Merkle tree in blockchain is a data structure that hashes data parts in pairs, level by level, until only one hash remains: the Merkle Root. A Merkle proof, a short path of hashes from that tree, shows that a transaction belongs to a block, or a chunk to a file, without access to the full data set.
The basic integrity check is hashing. To make sure a file sent over the network reaches the recipient unaltered, we hash its contents:
const verificationHash = SHA256(...fileContent);
Then we send the hash, so the recipient can verify the received file:
const receivedFileHash = SHA256(...receivedFileContent);
if (receivedFileHash === verificationHash) {
// All good, the hashes match
} else {
// Attention! The file or its parts were altered
}
Sometimes we need to check only a part of the data, like a BitTorrent chunk sent by a peer or a Bitcoin transaction in a block with the specified hash. That is where the Merkle-tree data structure and its property, Merkle-proof, come in.
Below, we cover what a Merkle tree and a Merkle proof are and how they are used in blockchain.
What is a Merkle-tree
In this process, the data is split into parts. In BitTorrent, these are chunks, in Bitcoin, the block is divided into individual transactions. Then, we calculate the hash for each part and group these hashes into pairs. If the last hash doesn’t have a pair, it is duplicated. The process continues: calculate hashes from the pairs and keep doing it until only one hash remains, the tree root called Merkle Root.
Using this Merkle hash tree, we can check whether a certain data part (e.g., D1, D2, or D3) belongs to a general set with the known hash (Merkle Root). To verify that D1 is from the general set, we don’t need to know D2 and D3—it is enough to apply the Merkle-proof algorithm.
What is Merkle-proof
The Bitcoin network often uses thin clients. These devices store only block headers, and not the entire blockchain. Such clients don’t see a list of all transactions in a block, they request data only on the transactions they need from the full network nodes. Still, a full node providing the info may be compromised. In this case, there should be proof showing that specified transactions are included in the block, but without querying the entire list of transactions (there may be many).
Instead of the complete transaction list, the node provides so-called Merkle-proof. Verifying data instead of trusting its source is one of the core secure coding practices.
Merkle-proof is a path to Merkle-tree in blockchain, which allows us to calculate the Merkle Root based on the data of interest. For instance, to verify that the D1 transaction is included in the block, a full node must send hashes H1 and HH2 as proof. This will be enough to calculate Merkle Root and compare it to what is specified in the block header on the client side.
Let’s take a look at the picture below with Merkle-tree explained:
- Green nodes are Merkle-proof and necessary for calculating Merkle Root.
- Yellow nodes are calculated on the verification side.
- Red nodes are not necessary for verification and can be ignored.
As you can see, to check whether a transaction is included in a block, we need to get Merkle-proof (H2, HH2), calculate Merkle Root, and compare it with the header.
Similarly, file chunks are verified in the BitTorrent protocol. Since checking the file content by hash before it is fully downloaded is impossible, the torrent tracker provides Merkle Root when the download starts. Then, for each chunk, downloaded by the client from various peers, it requests Merkle-proof. This confirms that the chunk is a part of the file.
FAQ
What is a Merkle tree in blockchain?
A Merkle tree is a hash-based data structure used to verify data quickly. The data is split into parts, for example, a Bitcoin block into individual transactions. Each part is hashed, the hashes are grouped into pairs and hashed again, and the process repeats until one hash remains. It lets nodes check data integrity while handling far less data.
What is a Merkle root?
The Merkle Root is the single hash at the top of a Merkle tree, calculated from all the data parts below it. If the number of hashes at any level is odd, the last one is duplicated to make a pair. In Bitcoin, the Merkle Root is stored in the block header, so any change to a transaction changes the root and becomes visible.
What is a Merkle proof?
A Merkle proof is the set of hashes needed to rebuild the path from a specific data part to the Merkle Root. For example, to verify that transaction D1 is in a block, a full node sends the hashes H2 and HH2. The client calculates the root from D1 and these hashes and compares it with the block header, without seeing the other transactions.
How does Bitcoin use Merkle trees?
Bitcoin thin clients store only block headers, not the entire blockchain. When they need data on specific transactions, they request it from full network nodes, which may be compromised. Instead of the complete transaction list, the node provides a Merkle proof, and the client checks that the recalculated Merkle Root matches the one in the block header, verifying the data instead of trusting its source.
How does BitTorrent use Merkle trees?
In BitTorrent, a file can’t be checked by its full hash before it is completely downloaded. So the torrent tracker provides the Merkle Root when the download starts. For each chunk the client receives from various peers, it requests a Merkle proof and uses it to confirm that the chunk is really a part of the file with the known hash.
Leverage Merkle-Tree in Blockchain
It is a critical component of blockchain technology, which you can use to check data integrity and verification quickly. When you create Merkle-tree, you secure transactions in a structured way, minimizing the amount of data each node needs to handle. This indeed strengthens security and smooths out the entire network performance. As a developer, you show you care about security and efficiency standards.
If you are looking for a development team experienced in crypto app development, contact us. Let’s work together to make transactions and other processes in your app secure.
Related reading
- Crypto Wallet Development: How to Build a Secure Cryptocurrency Wallet App
- Cryptocurrency Exchange Software Development: How to Build a Secure Crypto Trading Platform
- DeFi Platform Development: How to Build a Secure Decentralized Finance Platform
- NFT Marketplace Development: How to Build a Scalable NFT Platform
* * *
Written by Mary Moore and Kirill Semenov