Checking Database Integrity With Merkle-Tree in Blockchain

Hashing may be used to verify the stability and integrity of databases. For instance, we can hash a file's contents if we wish to transfer it across a network and ensure that the receiver receives it unaltered.

const verificationHash = SHA256(...fileContent);

The receiver may then confirm that the received file is identical by receiving the hash.

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 verify a portion of the data. For example, in the BitTorrent protocol, we must use the hash we know to confirm that the chunk delivered by a peer is, in fact, a portion of the downloaded file. Or, similar to the Bitcoin system, we use the given hash to verify that a certain transaction is part of the block.

Here is the reason why we use a Merkle-tree data structure and its important property—Merkle-proof.

What is a Merkle-tree

The data is divided into segments throughout this procedure. In Bitcoin, the block is separated into separate transactions, but in BitTorrent, these are chunks. The hash for each component is then determined, and these hashes are grouped into pairs. The last hash is replicated if it lacks a pair. The procedure proceeds as follows: compute hashes from the pairings and repeat until the tree root, known as the Merkle Root, is the sole hash left.

We can determine if a certain data point (such as D1, D2, or D3) is a member of a generic set with the known hash (Merkle Root) by using this Merkle hash tree. We may use the Merkle-proof technique to confirm that D1 is from the general set without knowing D2 or D3.

What is Merkle-proof

Thin clients are often used on the Bitcoin network. The whole blockchain is not stored on these devices; just block headers are. These clients just ask the whole network nodes for information on the transactions they want; they do not view a list of every transaction in a block. However, a whole node that provides the information might be hacked. Without looking through the complete list of transactions—which may be rather large—there should be evidence in this instance that the designated transactions are part of the block.

The node offers so-called Merkle-proof information in place of the whole transaction list.

In blockchain, Merkle-proof is a route to Merkle-tree that enables us to determine the Merkle Root using the relevant data. For example, a complete node has to submit hashes H1 and HH2 as evidence that the D1 transaction is part of the block. This will be sufficient to compute Merkle Root and compare it to the client-side specifications in the block header.

Let's examine the image below, which explains Merkle-tree.

• Green nodes are required to calculate Merkle Root and are Merkle-proof.
• The verification side calculates yellow nodes.
• Red nodes can be disregarded and are not required for verification.

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

Similarly, the BitTorrent protocol verifies file pieces. The torrent tracker gives Merkle Root as the download begins since it is difficult to verify the file content by hash until it has finished downloading. Next, it seeks Merkle-proof for every chunk that the client has downloaded from different peers. This attests to the chunk's inclusion in the file.

Use Merkle-Tree in Blockchain

It is an essential part of blockchain technology, which allows you to rapidly verify and validate the integrity of data. By reducing the volume of data that each node must manage, Merkle-tree secures transactions in an organized manner. Indeed, this improves network speed overall and fortifies security. You demonstrate your concern for efficiency and security requirements as a developer.

Written by Mary Moore and Kirill Semenov