Checking Database Integrity With Merkle-Tree in Blockchain

*Written by Mary Moore and Kirill Semenov*

When you are required to keep database integrity and stability, hashing can be utilized. For example, if we are required to transmit a file across the network but want it to be transeffred in one complete piece, then we can hash its contents:

const verificationHash = SHA256(...fileContent);

Then transmit the hash to the recipient so they may confirm that 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
}

But occasionally we simply need to examine a segment of the data. For example, in the BitTorrent protocol, we have to check that the chunk received from a peer is indeed a segment of the downloading file with the hash we possess. Or, as in the Bitcoin protocol, we verify that a particular transaction is contained in the block with the given hash.

That’s why we employ a Merkle-tree data structure and its inherent property, Merkle-proof.

What is a Merkle-tree

This procedure divides the data into sections. BitTorrent refers to these as chunks, but Bitcoin divides the block into individual transactions. Then, we compute the hash for each portion and group them into pairs. If the final hash does not include a pair, it is duplicated. The procedure continues: compute hashes from the pairings and repeat until only one hash remains, the tree root known as Merkle Root.

Using this Merkle hash tree, we may determine if a certain data portion (e.g., D1, D2, or D3) belongs to a generic set with a known hash (Merkle Root). We don’t need to know D2 or D3 to verify that D1 is from the general set; simply applying the Merkle-proof procedure would suffice.

What is Merkle-proof

The Bitcoin network frequently employs thin clients. These devices only save the block headers, not the whole blockchain. Such clients do not see a list of all transactions in a block; instead, they request data on only the transactions they want from the whole network nodes. However, a whole node giving the information may be hacked. In this situation, there should be verification that certain transactions are included in the block, but without querying the full list of transactions (which may be large).

Instead of a full transaction list, the node offers Merkle-proof.

Merkle-proof is a way to the Merkle-tree in blockchain that allows us to compute the Merkle Root using the data of interest. For example, to ensure that the D1 transaction is included in the block, a complete node must transmit hashes H1 and HH2 as evidence. This will be sufficient to compute Merkle Root and compare it to the value supplied in the block header on the client side.

Let’s have a look at the image below, which explains Merkle-tree:

• Green nodes are Merkle-proof and required for determining the Merkle Root.
• Yellow nodes are computed during the verification process.
• Red nodes are unnecessary for verification and can be disregarded.

As you can see, to determine whether a transaction is contained in a block, we must obtain Merkle-proof (H2, HH2), compute Merkle Root, and compare it to the header.

Similarly, file portions are validated in the BitTorrent protocol. Because validating the file content by hash before it is fully downloaded is difficult, the torrent tracker offers Merkle Root as the download begins. Then, for each chunk downloaded from distinct peers, the client asks Merkle-proof. This indicates that the chunk is part of the file.

Leverage Merkle-Tree in Blockchain

It is a core component of blockchain technology that you can leverage to validate and confirm data integrity in real time. When you build Merkle-tree, you secure transactions in a structured format, which lowers the data each node must handle. This really makes security stronger and smoothened out the entire network performance. As a programmer, you show that you care about security and efficiency standards.

Originally published at https://shakuro.com.