When you need to check database integrity and stability, you can leverage hashing. For example, if we want to send a file over the network and make sure that it reaches the recipient without any alterations, we can hash its contents:
const verificationHash = SHA256(...fileContent);
And then send the hash to the recipient, so they can verify whether the received file is the same:
const receivedFileHash = SHA256(...receivedFileContent);
if (receivedFileHash === verificationHash) {
// All good, the hashes match
} else {
// Attention! The file or its parts were altered
}
However, sometimes, we need to check only a part of the data. For instance, in the BitTorrent protocol, we need to verify that the chunk sent by a peer is indeed a part of the downloading file with the hash we know. Or, just like in the Bitcoin protocol—we confirm that a certain transaction is included in the block with the specified hash.
For these reasons, we use a Merkle-tree data structure and its important property—Merkle-proof.
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.
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.
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.
* * *
Written by Mary Moore and Kirill Semenov