An Intro to Merkel Tree: What is it and How Does it Work?

A Merkle Tree is a binary tree of hash values, where each leaf node represents a single piece of data or a hash of a piece of data. It is used to verify the integrity of large amounts of data efficiently. It was invented by Ralph Merkle in 1979 and is widely used in cryptocurrencies like Bitcoin and Ethereum. A hash function is like a fingerprint machine. It takes any input, such as a file, a text, or a number, and produces a unique output, called a hash, that is much shorter than the input. The hash is like a fingerprint of the input. It is tough to find two different inputs that have the same hash. And it is impossible to get the original input from the hash. For example, if you have a file called " " that is 1 MB in size, you can use a hash function to get a hash that is only characters long, such as . kishan.jpg 64 0A6DF48A27EF7DB48B213DF3DBA84FAD1BB4FD9B47568DA1F570C067D9A4867F If you change even one pixel in the file, the hash will be completely different, such as . C69E60E932F3D0C6C2363B68301E202551C09123A71F639E6AB3BC8F847BE4AF So you can use the hash to verify that the file is the same as before. Calculating and storing the hash for each file separately would be tedious. That's where Merkle trees come in handy. But what if you have many files? A Merkle tree is like a family tree of hashes. . Then you pair up the hashes and combine them to get new hashes. You repeat this process until you reach the top of the tree, where you have only one hash left. This hash is called the . You start with the hashes of each file as the leaves of the tree Merkle root The Merkle root is like a fingerprint of all the files in the tree. . So you can use the Merkle root to verify that all the files are the same as before. If any file changes, its hash will change, and so will all the hashes above it until the Merkle root changes But how do you verify a specific file? You don't need to download and check all the files in the tree. You only need to download and check a few hashes along the path from the file to the Merkle root. This path is called a . Merkle proof For example, suppose you want to verify whether the file "cat.jpg" is correct. You only need to download its hash which is , its sibling's hash , their parent's sibling's hash , and the Merkle root . H A 0a6df4 H B (ea12e7) H CD (b582ae) H ABCD (7bd24f) Then you can calculate by combining and and calculate by combining H AB and H CD . If H ABCD matches the Merkle root, you can be sure that." " is correct. H AB H A H B H ABCD cat.jpg You can use the same analogy to verify if the transaction present in the block is tempered by verifying the Merkle root instead of cat.jpg or dog.txt. It'll be a bunch of transactions at the leaf nodes. Please note: I have truncated the hash value to 6 characters in the above example to make the diagram look clean. What if I only have three leaf nodes? How will I create a Merkle Tree? This scenario can quickly be addressed by duplicating one node, thus making the total number of nodes four. For example, suppose you have transactions. , , and . You can calculate their hashes. , , and . . Afterward; you can pair up and combine the hashes to get , , and . The Merkle root is . T A T B T C H A H B H C Then you can duplicate H C to get H C' H AB H CC’ H ABCC’ H ABCC’ Summing up, Merkle trees benefit blockchain and other distributed systems, where many computers must share and verify large amounts of data. By using Merkle trees, they can save bandwidth, storage, and computation time. Here's a quick Java example to show how you can create your own Merkle tree: import java.nio.charset.StandardCharsets; import java.security.MessageDigest; import java.security.NoSuchAlgorithmException; class MerkleTree{ static class Node { String content; public Node(String content) { this.content = content; } public String getHash() throws NoSuchAlgorithmException { MessageDigest md = MessageDigest.getInstance("SHA-256"); byte[] hash = md.digest(content.getBytes(StandardCharsets.UTF_8)); StringBuilder buffer = new StringBuilder(); for (byte b : hash) { buffer.append(String.format("%02x", b)); } return buffer.toString(); } } public static void main(String[] args) throws NoSuchAlgorithmException{ Node cat = new Node("I am a cat, this is a cat file called cat.jpg"); Node dog = new Node("I am a dog, this is a dog file called dog.txt"); // we have two leaf nodes, in order to create a merkle root, // we simple need to get their individual hashes // and then combine those hashes and hash them again String HA = cat.getHash(); String HB = dog.getHash(); Node merkleRoot = new Node(HA + HB); String HAB = merkleRoot.getHash(); System.out.println("Merkle Root: " + merkleRoot.getHash()); // let's say we altered the cat file cat = new Node("I am a cat, this is a cat file called dog.jpg"); // notice we have changed the cat.jpg to dog.jpg String HA_MODIFIED = cat.getHash(); Node modifiedMerkleRoot = new Node(HA_MODIFIED + HB); String HAB_MODIFIED = modifiedMerkleRoot.getHash(); System.out.println("Merkle Root: " + HAB_MODIFIED); } } Output: Merkle Root: d1da3503d679f032134b4330768d31e67813fcfe2824fceed93f8185a405bdf9 Merkle Root: 1a898c7fee0e46647e55d5f9874f090e5ed76726acf39308527a0bba22a34b3e I thank you for taking the time to read my article. Do support me by following me on so that you get notified whenever I publish an article. Hackernoon Thanks a lot. Dive into insightful articles on decentralized systems, Tech, and AI trends: . Do visit to show your support. https://www.0xkishan.com Also published here.