In the early 1980s, Ralph Merkle, a computer scientist known for his work on public-key cryptography, put forth the idea of a Merkle Tree.An effective structure for ensuring the accuracy of data in a set is a Merkle tree. In peer-to-peer networks, where users must exchange and independently verify information, they are especially intriguing.

How do Merkle trees function?

Imagine you wish to download a huge file. When using open-source software, you should normally verify that the file’s Hash matches one that the developers have made available to the public. If it happens, you can be certain that the file you have on your computer and theirs are identical.

If the hashes differ, there is an issue. Either you downloaded a malicious file that was disguised as the software, or the download went wrong, preventing the software from working. If the latter is the case, waiting a while for the file to download won’t likely make you too happy. You must now resume the process and pray that it won’t become corrupt once more.

You wish there was a simpler method for doing this. Fortunately, Merkle trees come into play here. You would have your file divided into sections if you used one of these. You could split a 50GB file into 100 pieces, each of which would be 0.5GB in size. It would then be downloaded in pieces. When you torrent files, you effectively do this.

In this instance, your source should have given you the Merkle root hash. Every single data tidbit that is part of your file is represented by this one hash. The Merkle root, however, makes it considerably simpler to validate the data.

Let’s use an 8GB file divided into eight parts as an example to make things clearer. Call the various pieces A through H. The hash algorithm is then applied to each fragment, yielding eight distinct hashes.

Now that we have something that makes a little more sense, okay. Since we have the hash of every fragment, we can compare it to the hash from the source to determine which pieces are accurate. Possibly, but that would also be a colossal waste of time. Are you going to hash every single one of your file’s hundreds of fragments and carefully compare the results?

No. Instead, we’ll aggregate each pair of hashes before performing another hash on them. Consequently, we hash hA + hb, hc + hd, he + hf, and hg + hh. In the end, we have four hashes. With this, we perform another round of hashing to produce two. To reach our master hash, the Merkle root, we finally hash the final two (or root hash).

Thankfully, there is a simple way for us to determine which part is broken. Let’s say it’s hE in our situation. To begin, you should ask a peer for the two hashes that resulted in the Merkle root (hABCD and hEFGH). Because there is no error in that subtree, your value for hABCD should equal theirs. You know to check in there since hEFGH won’t. After that, you request hEF and hGH and compare them to your own. You can tell if hEF is the culprit because hGH will appear normal. Finally, you contrast hE and hF’s hashes. You can redownload that portion now that you are aware that hE is inaccurate.

All things considered, a Merkle tree is produced by breaking data into numerous pieces and repeatedly hashing each component to produce the Merkle root. Then, you can quickly determine if a piece of data has a problem. There are also more intriguing applications, as we’ll see in the part after this.