{"id":359,"date":"2019-02-17T16:13:17","date_gmt":"2019-02-17T16:13:17","guid":{"rendered":"http:\/\/nitk.acm.org\/blog\/?p=359"},"modified":"2019-02-17T16:13:17","modified_gmt":"2019-02-17T16:13:17","slug":"merkle-trees-and-their-application-in-blockchain","status":"publish","type":"post","link":"https:\/\/nitk.acm.org\/blog\/2019\/02\/17\/merkle-trees-and-their-application-in-blockchain\/","title":{"rendered":"Merkle Trees and their application in Blockchain"},"content":{"rendered":"

Merkle Trees are a fundamental component of Blockchain technology and allow them to function with transaction integrity.<\/p>\n

To develop an understanding of decentralized systems and their efficient functionality, let us start from the basics.<\/p>\n

What is a cryptographic hash function?<\/b><\/h2>\n

A cryptographic hash function is a function which takes an input and gives an output of fixed length. The resulting hash from the arbitrary input is not only fixed in length, it is also completely unique to the input and the function itself is deterministic, i.e. if you run the function on the same input, the output will always be the same.<\/p>\n

\"\"<\/p>\n

Notice how in the first and second examples, even though the difference of the inputs is only one word, the resulting outputs are completely different. This is very important as it allows for \u201cfingerprinting\u201d of data.<\/p>\n

Since the output of the hash function is always fixed, huge amounts of data can be identified by their hash function.<\/p>\n

Merkle Trees<\/b><\/h2>\n

Now, Merkle Trees are basically data structures where each non-leaf node is the hash of its respective child nodes. The leaf nodes are the lowest tier of nodes in the tree. Merkle trees are binary and therefore require an even number of leaf nodes. If the number of transactions is odd, the last hash will be duplicated once to create an even number of leaf nodes.<\/p>\n

\"\"<\/p>\n

Essentially, Merkle Trees are data structures that can take ‘n’ number of hashes and represent it with a single hash. In blockchain terms, a Merkle Tree summarizes all the transactions in a block by producing a single fingerprint of the entire set of transactions. It maintains the integrity of the data. If a single detail in any of the transactions or the order of the transactions changes, so does the Merkle Root. Using a Merkle tree allows for a quick and simple test of whether a specific transaction is included in the set or not.<\/p>\n

The single code that a Merkle Tree produces is called the Merkle Root. Each block in a blockchain has exactly one. The Merkle Root is a crucial piece of data because it allows computers to verify information with incredible speed and efficiency.<\/p>\n

Now let\u2019s look at a bigger Merkle Tree<\/p>\n

\"\"<\/p>\n

Now let\u2019s suppose we want to validate a transaction ID in this tree.<\/p>\n

Fred says that he paid George a certain sum of Bitcoin.<\/p>\n

He says \u201cAsk me no questions and I\u2019ll tell you no lies<\/i> \u201d.<\/p>\n

HAHA, I\u2019m sorry, Fred, that\u2019s not how it works, we need to verify whether you actually sent Bitcoins to George.<\/p>\n

Fred obliges and tells us that the transaction ID to be verified is H<\/strong>E.<\/p>\n

We already have the block\u2019s Merkle Root, so Fred doesn\u2019t need to send us that. He also sends us 4 hashes: H<\/strong>F, H<\/strong>GH, H<\/strong>ABCD and H<\/strong>IJKLMNOP. That\u2019s all the information that needs to be sent or received to verify Fred\u2019s payment to George.<\/b> These 4 nodes are collectively known as the \u201cAuthentication Path<\/i>\u201d of H<\/strong>E. Let\u2019s see how we verify the transaction using the Authentication Path of H<\/strong>E.<\/p>\n

We start by hashing the first code H<\/strong>F with the transaction ID H<\/strong>E, which gives us the result H<\/strong>EF. Fred didn\u2019t send us this code but he didn\u2019t need to because we\u2019re using the same hashing algorithm as him. Therefore, we receive the exact same results.<\/p>\n

We then take the second code Fred sent us, H<\/strong>GH, and hash it with the new code H<\/strong>EF we just derived. This, of course, produces the number H<\/strong>EFGH .<\/p>\n

Then, we hash the third code Fred gave us, H<\/strong>ABCD, with the other new code we received, H<\/strong>EFGH, and we end up with the correct Merkle Root: H<\/strong>ABCDEFGH.<\/p>\n

Finally, we hash the fourth code Fred gave us, H<\/strong>IJKLMNOP, with the other new code we received, H<\/strong>ABCDEFGH, and we end up with the correct Merkle Root: H<\/strong>ABCDEFGHIJKLMNOP.<\/p>\n

This procedure is sufficient to verify that Fred actually paid George and didn\u2019t just lie that he did.<\/p>\n

Notice that we only need 4 nodes from Fred and only had to run the hashing algorithm 4 times to see that Fred\u2019s transaction is valid. That means our computer has done less than half the work that would\u2019ve been required to verify the entire Merkle Tree. But more than half of the tree isn\u2019t necessary to verify Fred\u2019s transaction! In this example, the number of transactions is only 15, while in reality, blocks in a Blockchain contain several thousands of transactions.<\/p>\n

It\u2019s easy to see how Merkle Trees increase efficiency so dramatically.<\/p>\n

– Nishanth Subramanian<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"

Merkle Trees are a fundamental component of Blockchain technology and allow them to function with transaction integrity. To develop an understanding of decentralized systems and their efficient functionality, let us start from the basics. What is a cryptographic hash function? A cryptographic hash function is a function which takes an input and gives an output…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_exactmetrics_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":""},"categories":[25,10],"tags":[113,79,114],"class_list":["post-359","post","type-post","status-publish","format-standard","hentry","category-sanganitra","category-tech","tag-blockchain","tag-cryptography","tag-merkle-trees"],"_links":{"self":[{"href":"https:\/\/nitk.acm.org\/blog\/wp-json\/wp\/v2\/posts\/359","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nitk.acm.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nitk.acm.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nitk.acm.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nitk.acm.org\/blog\/wp-json\/wp\/v2\/comments?post=359"}],"version-history":[{"count":2,"href":"https:\/\/nitk.acm.org\/blog\/wp-json\/wp\/v2\/posts\/359\/revisions"}],"predecessor-version":[{"id":364,"href":"https:\/\/nitk.acm.org\/blog\/wp-json\/wp\/v2\/posts\/359\/revisions\/364"}],"wp:attachment":[{"href":"https:\/\/nitk.acm.org\/blog\/wp-json\/wp\/v2\/media?parent=359"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nitk.acm.org\/blog\/wp-json\/wp\/v2\/categories?post=359"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nitk.acm.org\/blog\/wp-json\/wp\/v2\/tags?post=359"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}