{"id":12044,"date":"2025-01-23T11:35:17","date_gmt":"2025-01-23T11:35:17","guid":{"rendered":"https:\/\/metaschool.so\/articles\/?p=12044"},"modified":"2025-01-27T11:36:05","modified_gmt":"2025-01-27T11:36:05","slug":"understanding-merkle-trees-and-proofs","status":"publish","type":"post","link":"https:\/\/metaschool.so\/articles\/understanding-merkle-trees-and-proofs\/","title":{"rendered":"Understanding Merkle Trees and Proofs: Comprehensive Guide 2025"},"content":{"rendered":"<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_56_1 ez-toc-wrap-left counter-hierarchy ez-toc-counter ez-toc-custom ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title \" >Table of Contents<\/p>\n<span class=\"ez-toc-title-toggle\"><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/metaschool.so\/articles\/understanding-merkle-trees-and-proofs\/#Why_Do_We_Need_Merkle_Trees\" title=\"Why Do We Need Merkle Trees?\">Why Do We Need Merkle Trees?<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/metaschool.so\/articles\/understanding-merkle-trees-and-proofs\/#Understanding_Merkle_Trees_Starting_with_the_Basics\" title=\"Understanding Merkle Trees: Starting with the Basics\">Understanding Merkle Trees: Starting with the Basics<\/a><ul class='ez-toc-list-level-3'><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/metaschool.so\/articles\/understanding-merkle-trees-and-proofs\/#What_is_a_Merkle_Tree\" title=\"What is a Merkle Tree?\">What is a Merkle Tree?<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/metaschool.so\/articles\/understanding-merkle-trees-and-proofs\/#The_Building_Blocks\" title=\"The Building Blocks\">The Building Blocks<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/metaschool.so\/articles\/understanding-merkle-trees-and-proofs\/#Building_a_Merkle_Tree_A_Simple_Example\" title=\"Building a Merkle Tree: A Simple Example\">Building a Merkle Tree: A Simple Example<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/metaschool.so\/articles\/understanding-merkle-trees-and-proofs\/#Merkle_Proofs_The_Magic_of_Verification\" title=\"Merkle Proofs: The Magic of Verification\">Merkle Proofs: The Magic of Verification<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/metaschool.so\/articles\/understanding-merkle-trees-and-proofs\/#Real-World_Applications\" title=\"Real-World Applications\">Real-World Applications<\/a><ul class='ez-toc-list-level-3'><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/metaschool.so\/articles\/understanding-merkle-trees-and-proofs\/#Bitcoin_and_Cryptocurrencies\" title=\"Bitcoin and Cryptocurrencies\">Bitcoin and Cryptocurrencies<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-9\" href=\"https:\/\/metaschool.so\/articles\/understanding-merkle-trees-and-proofs\/#File_Sharing_Systems\" title=\"File Sharing Systems\">File Sharing Systems<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-10\" href=\"https:\/\/metaschool.so\/articles\/understanding-merkle-trees-and-proofs\/#Advantages_of_Merkle_Trees\" title=\"Advantages of Merkle Trees\">Advantages of Merkle Trees<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-11\" href=\"https:\/\/metaschool.so\/articles\/understanding-merkle-trees-and-proofs\/#Limitations_to_Consider\" title=\"Limitations to Consider\">Limitations to Consider<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-12\" href=\"https:\/\/metaschool.so\/articles\/understanding-merkle-trees-and-proofs\/#Advanced_Concepts_Made_Simple\" title=\"Advanced Concepts Made Simple\">Advanced Concepts Made Simple<\/a><ul class='ez-toc-list-level-3'><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-13\" href=\"https:\/\/metaschool.so\/articles\/understanding-merkle-trees-and-proofs\/#Sparse_Merkle_Trees\" title=\"Sparse Merkle Trees\">Sparse Merkle Trees<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-14\" href=\"https:\/\/metaschool.so\/articles\/understanding-merkle-trees-and-proofs\/#Merkle_Patricia_Trees\" title=\"Merkle Patricia Trees\">Merkle Patricia Trees<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-15\" href=\"https:\/\/metaschool.so\/articles\/understanding-merkle-trees-and-proofs\/#Implementing_Your_Own_Merkle_Tree\" title=\"Implementing Your Own Merkle Tree\">Implementing Your Own Merkle Tree<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-16\" href=\"https:\/\/metaschool.so\/articles\/understanding-merkle-trees-and-proofs\/#Conclusion\" title=\"Conclusion\">Conclusion<\/a><\/li><\/ul><\/nav><\/div>\n\n<p>Ever wondered how Bitcoin verifies\u00a0a\u00a0transaction\u00a0without downloading the entire blockchain,\u00a0or how, in peer-to-peer networks,\u00a0file integrity\u00a0is ensured\u00a0when\u00a0portions\u00a0of it are downloaded\u00a0from\u00a0different\u00a0sources? The answer\u00a0involves\u00a0a\u00a0really\u00a0smart\u00a0data structure\u00a0known\u00a0as\u00a0a Merkle Tree. In this\u00a0post, we&#8217;ll\u00a0see\u00a0Merkle Trees from the ground up and understand\u00a0not just what they are\u00a0but why they&#8217;re so important in modern technology.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Why_Do_We_Need_Merkle_Trees\"><\/span>Why Do We Need Merkle Trees?<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>Suppose\u00a0you\u00a0are\u00a0downloading\u00a0some\u00a0big\u00a0file,\u00a0such\u00a0as\u00a0a movie or\u00a0game, from the Internet.\u00a0You\u00a0have\u00a0no\u00a0guarantee\u00a0that\u00a0what\u00a0was\u00a0downloaded is\u00a0precisely\u00a0what you\u00a0got.\u00a0You\u00a0might\u00a0even\u00a0suspect\u00a0that\u00a0someone\u00a0tampered with it\u00a0en route. This is\u00a0what\u00a0Merkle Trees\u00a0ensures.<br><br>This\u00a0problem\u00a0becomes\u00a0even\u00a0more\u00a0critical\u00a0in\u00a0<a href=\"https:\/\/metaschool.so\/blockchains\" data-type=\"link\" data-id=\"https:\/\/metaschool.so\/blockchains\">blockchain\u00a0systems<\/a>\u00a0such\u00a0as Bitcoin. You might want to verify that your transaction was\u00a0in\u00a0one\u00a0block without downloading the\u00a0whole\u00a0blockchain,\u00a0which is hundreds of gigabytes in size. Merkle Trees\u00a0allows\u00a0you\u00a0to\u00a0do\u00a0just\u00a0that\u00a0and\u00a0ensure\u00a0data integrity\u00a0efficiently.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Understanding_Merkle_Trees_Starting_with_the_Basics\"><\/span>Understanding Merkle Trees: Starting with the Basics<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"What_is_a_Merkle_Tree\"><\/span>What is a Merkle Tree?<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p>A Merkle Tree is like a family tree for data. Just as a family tree shows how everyone is connected, a Merkle Tree shows\u00a0via\u00a0the\u00a0&#8220;fingerprints&#8221; or cryptographic hashes\u00a0of\u00a0the\u00a0data\u00a0how\u00a0pieces\u00a0of\u00a0data\u00a0are\u00a0related. Let&#8217;s break this down step by step.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"652\" src=\"https:\/\/metaschool.so\/articles\/wp-content\/uploads\/2025\/01\/image-13-1024x652.png\" alt=\"Understanding Merkle Trees\" class=\"wp-image-12046\" srcset=\"https:\/\/metaschool.so\/articles\/wp-content\/uploads\/2025\/01\/image-13-1024x652.png 1024w, https:\/\/metaschool.so\/articles\/wp-content\/uploads\/2025\/01\/image-13-300x191.png 300w, https:\/\/metaschool.so\/articles\/wp-content\/uploads\/2025\/01\/image-13-768x489.png 768w, https:\/\/metaschool.so\/articles\/wp-content\/uploads\/2025\/01\/image-13.png 1200w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"The_Building_Blocks\"><\/span>The Building Blocks<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Data Blocks<\/strong>: These are the\u00a0chunks\u00a0of information you want to\u00a0validate;\u00a0in Bitcoin, these\u00a0are\u00a0transactions,\u00a0but\u00a0they\u00a0might\u00a0be pieces of the file\u00a0in some sort of file-sharing scenario.<\/li>\n\n\n\n<li><strong>Hash Functions<\/strong>: You can\u00a0think of these as\u00a0fingerprint machines:\u00a0they take any input,\u00a0say\u00a0a transaction,\u00a0and produce a fixed-size output,\u00a0the fingerprint\u00a0that\u00a0identifies\u00a0that input\u00a0uniquely. If you change even one tiny bit of the input, the fingerprint changes completely.<\/li>\n\n\n\n<li><strong>Tree Structure<\/strong>: A\u00a0tree is\u00a0formed\u00a0by\u00a0arranging\u00a0those\u00a0fingerprints in\u00a0such\u00a0a\u00a0way\u00a0that\u00a0all\u00a0the data\u00a0sits\u00a0at the\u00a0very\u00a0bottom,\u00a0then\u00a0combines\u00a0the\u00a0fingerprints as we move\u00a0upwards.<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Building_a_Merkle_Tree_A_Simple_Example\"><\/span>Building a Merkle Tree: A Simple Example<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p>Let&#8217;s build a Merkle Tree with four transactions (Tx1, Tx2, Tx3, and Tx4). Here&#8217;s how it works:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>First Level (Leaf Nodes)<\/strong>:<\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Take each transaction and create its hash (fingerprint)<\/li>\n\n\n\n<li>Hash of (Tx1) = H1<\/li>\n\n\n\n<li>Hash of (Tx2) = H2<\/li>\n\n\n\n<li>Hash of (Tx3) = H3<\/li>\n\n\n\n<li>Hash of (Tx4) = H4<\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Second Level<\/strong>:<\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Combine pairs of hashes and hash them together<\/li>\n\n\n\n<li>Hash of (H1 + H2) = H12<\/li>\n\n\n\n<li>Hash of (H3 + H4) = H34<\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Final Level (Root)<\/strong>:<\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Combine the last pair to get the Merkle Root<\/li>\n\n\n\n<li>Hash of (H12 + H34) = Root Hash<\/li>\n<\/ul>\n\n\n\n<p>This root hash is special because it represents all the data beneath it. If any transaction changes, the root hash will also change.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Merkle_Proofs_The_Magic_of_Verification\"><\/span>Merkle Proofs: The Magic of Verification<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>Here&#8217;s where Merkle Trees get interesting. Let&#8217;s say you want to prove that Tx2 is part of this tree without showing all the transactions. You only need three pieces of information:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>The transaction (Tx2)<\/li>\n\n\n\n<li>Hash1 (to combine with Hash2)<\/li>\n\n\n\n<li>Hash34 (to combine with Hash12)<\/li>\n<\/ol>\n\n\n\n<p>With just these pieces, anyone can:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Calculate Hash2 from Tx2<\/li>\n\n\n\n<li>Combine Hash2 with Hash1 to get Hash12<\/li>\n\n\n\n<li>Combine Hash12 with Hash34 to get the Root Hash<\/li>\n<\/ol>\n\n\n\n<p>If this calculated root matches the known root hash, the transaction is verified! This is called a Merkle Proof.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Real-World_Applications\"><\/span>Real-World Applications<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Bitcoin_and_Cryptocurrencies\"><\/span>Bitcoin and Cryptocurrencies<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p>Bitcoin uses Merkle Trees in every block of transactions, especially in the implementation of Simple Payment Verification (SPV). When you use a lightweight wallet (like on your phone), it doesn&#8217;t download the whole blockchain. Instead, it:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Downloads just the block headers (which contain Merkle roots)<\/li>\n\n\n\n<li>Gets Merkle proofs for your transactions<\/li>\n\n\n\n<li>Verifies that your transactions are included without needing the other thousands of transactions in each block<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"File_Sharing_Systems\"><\/span>File Sharing Systems<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p>When you download a large file through BitTorrent or IPFS:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>The system divides the file into pieces<\/li>\n\n\n\n<li>Creates a Merkle Tree of all pieces<\/li>\n\n\n\n<li>As you download each piece from different sources, you can verify it&#8217;s correct using Merkle proofs<\/li>\n\n\n\n<li>If any piece is corrupted or tampered with, you&#8217;ll know immediately<\/li>\n<\/ol>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Advantages_of_Merkle_Trees\"><\/span>Advantages of Merkle Trees<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Efficiency<\/strong>: You only need a small amount of data to verify that something is part of a larger set<\/li>\n\n\n\n<li><strong>Security<\/strong>: It&#8217;s practically impossible to fake a Merkle-proof<\/li>\n\n\n\n<li><strong>Space Saving<\/strong>: Light clients (like mobile wallets) can work without downloading everything<\/li>\n<\/ol>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Limitations_to_Consider\"><\/span>Limitations to Consider<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Initial Computation<\/strong>: Building the tree requires calculating many hashes<\/li>\n\n\n\n<li><strong>Updates<\/strong>: If data changes, you need to recalculate parts of the tree<\/li>\n\n\n\n<li><strong>Proof Size<\/strong>: While efficient, proofs get slightly larger as the tree gets bigger<\/li>\n<\/ol>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Advanced_Concepts_Made_Simple\"><\/span>Advanced Concepts Made Simple<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Sparse_Merkle_Trees\"><\/span>Sparse Merkle Trees<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p>Imagine a Merkle Tree with slots for every possible piece of data, even if most slots are empty. This is a Sparse Merkle Tree. It&#8217;s like having a huge library with mostly empty shelves but being able to quickly prove whether a book exists or not.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Merkle_Patricia_Trees\"><\/span>Merkle Patricia Trees<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p>Used in Ethereum, these are like Merkle Trees with a better filing system. They make it easier to track accounts and their balances, like a super-efficient filing cabinet that can prove what&#8217;s inside any drawer.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Implementing_Your_Own_Merkle_Tree\"><\/span>Implementing Your Own Merkle Tree<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>Here&#8217;s a simple Python implementation for Merkle Tree. If you want to get an in-depth idea of the implementation, read the blog: &#8220;<a href=\"https:\/\/medium.com\/coinmonks\/merkle-tree-a-simple-explanation-and-implementation-48903442bc08\" data-type=\"link\" data-id=\"https:\/\/medium.com\/coinmonks\/merkle-tree-a-simple-explanation-and-implementation-48903442bc08\" target=\"_blank\" rel=\"noopener\"><strong>Merkle Tree: A Simple Explanation<\/strong> <strong>and Implementation.<\/strong><\/a>&#8221; <\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"import hashlib\n\nclass MerkleTree:\n    def __init__(self, data_blocks):\n        self.leaves = [self.hash_data(block) for block in data_blocks]\n        self.root = self.build_tree(self.leaves)\n\n    def hash_data(self, data):\n        return hashlib.sha256(str(data).encode()).hexdigest()\n\n    def build_tree(self, leaves):\n        if len(leaves) == 1:\n            return leaves[0]\n\n        new_level = []\n        for i in range(0, len(leaves), 2):\n            if i + 1 < len(leaves):\n                new_hash = self.hash_data(leaves[i] + leaves[i+1])\n            else:\n                new_hash = leaves[i]  # Duplicate last node if odd\n            new_level.append(new_hash)\n\n        return self.build_tree(new_level)\n\n# Example usage\ntransactions = [&quot;Tx1&quot;, &quot;Tx2&quot;, &quot;Tx3&quot;, &quot;Tx4&quot;]\ntree = MerkleTree(transactions)\nprint(f&quot;Merkle Root: {tree.root}&quot;)\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #C586C0\">import<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #9CDCFE\">hashlib<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #9CDCFE\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #9CDCFE\">MerkleTree<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #9CDCFE\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #9CDCFE\">__init__<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">data_blocks<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">.<\/span><span style=\"color: #9CDCFE\">leaves<\/span><span style=\"color: #D4D4D4\"> = [<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">.<\/span><span style=\"color: #9CDCFE\">hash_data<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">block<\/span><span style=\"color: #D4D4D4\">) <\/span><span style=\"color: #9CDCFE\">for<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #9CDCFE\">block<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #9CDCFE\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #9CDCFE\">data_blocks<\/span><span style=\"color: #D4D4D4\">]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">.<\/span><span style=\"color: #9CDCFE\">root<\/span><span style=\"color: #D4D4D4\"> = <\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">.<\/span><span style=\"color: #9CDCFE\">build_tree<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">.<\/span><span style=\"color: #9CDCFE\">leaves<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #9CDCFE\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #9CDCFE\">hash_data<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">data<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #9CDCFE\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #9CDCFE\">hashlib<\/span><span style=\"color: #D4D4D4\">.<\/span><span style=\"color: #9CDCFE\">sha256<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">str<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">data<\/span><span style=\"color: #D4D4D4\">).<\/span><span style=\"color: #9CDCFE\">encode<\/span><span style=\"color: #D4D4D4\">()).<\/span><span style=\"color: #9CDCFE\">hexdigest<\/span><span style=\"color: #D4D4D4\">()<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #9CDCFE\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #9CDCFE\">build_tree<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">leaves<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #9CDCFE\">if<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #9CDCFE\">len<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">leaves<\/span><span style=\"color: #D4D4D4\">) == 1:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #9CDCFE\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #9CDCFE\">leaves<\/span><span style=\"color: #D4D4D4\">[0]<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #9CDCFE\">new_level<\/span><span style=\"color: #D4D4D4\"> = []<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #9CDCFE\">for<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #9CDCFE\">i<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #9CDCFE\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #9CDCFE\">range<\/span><span style=\"color: #D4D4D4\">(0, <\/span><span style=\"color: #9CDCFE\">len<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">leaves<\/span><span style=\"color: #D4D4D4\">), 2):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #9CDCFE\">if<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #9CDCFE\">i<\/span><span style=\"color: #D4D4D4\"> + 1 &lt; <\/span><span style=\"color: #9CDCFE\">len<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">leaves<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #9CDCFE\">new_hash<\/span><span style=\"color: #D4D4D4\"> = <\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">.<\/span><span style=\"color: #9CDCFE\">hash_data<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">leaves<\/span><span style=\"color: #D4D4D4\">[<\/span><span style=\"color: #9CDCFE\">i<\/span><span style=\"color: #D4D4D4\">] + <\/span><span style=\"color: #9CDCFE\">leaves<\/span><span style=\"color: #D4D4D4\">[<\/span><span style=\"color: #9CDCFE\">i<\/span><span style=\"color: #D4D4D4\">+1])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #9CDCFE\">else<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #9CDCFE\">new_hash<\/span><span style=\"color: #D4D4D4\"> = <\/span><span style=\"color: #9CDCFE\">leaves<\/span><span style=\"color: #D4D4D4\">[<\/span><span style=\"color: #9CDCFE\">i<\/span><span style=\"color: #D4D4D4\">]  # <\/span><span style=\"color: #9CDCFE\">Duplicate<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #9CDCFE\">last<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #9CDCFE\">node<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #9CDCFE\">if<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #9CDCFE\">odd<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #9CDCFE\">new_level<\/span><span style=\"color: #D4D4D4\">.<\/span><span style=\"color: #9CDCFE\">append<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">new_hash<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #9CDCFE\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">.<\/span><span style=\"color: #9CDCFE\">build_tree<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">new_level<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\"># <\/span><span style=\"color: #9CDCFE\">Example<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #9CDCFE\">usage<\/span><\/span>\n<span class=\"line\"><span style=\"color: #9CDCFE\">transactions<\/span><span style=\"color: #D4D4D4\"> = [<\/span><span style=\"color: #CE9178\">&quot;Tx1&quot;<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #CE9178\">&quot;Tx2&quot;<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #CE9178\">&quot;Tx3&quot;<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #CE9178\">&quot;Tx4&quot;<\/span><span style=\"color: #D4D4D4\">]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #9CDCFE\">tree<\/span><span style=\"color: #D4D4D4\"> = <\/span><span style=\"color: #9CDCFE\">MerkleTree<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">transactions<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #9CDCFE\">print<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">f<\/span><span style=\"color: #CE9178\">&quot;Merkle Root: {tree.root}&quot;<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Conclusion\"><\/span>Conclusion<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>Merkle Trees are\u00a0an\u00a0intelligent\u00a0solution to\u00a0one\u00a0complex problem:\u00a0ensuring\u00a0data integrity\u00a0is\u00a0effectively achieved\u00a0in a distributed system.\u00a0 From\u00a0Bitcoin\u00a0to\u00a0even\u00a0downloading\u00a0a\u00a0file\u00a0or building\u00a0up\u00a0your\u00a0system,\u00a0the\u00a0concept of a\u00a0Merkle\u00a0Tree\u00a0provides\u00a0a\u00a0way\u00a0to\u00a0understand\u00a0how\u00a0most\u00a0modern digital systems maintain trust\u00a0with\u00a0efficiency.<br><br>If\u00a0you\u00a0want\u00a0to\u00a0understand\u00a0more\u00a0of the details, try\u00a0to\u00a0implement\u00a0the simple Merkle Tree\u00a0above and\u00a0play\u00a0with different data sets.\u00a0 Once\u00a0you\u00a0feel\u00a0comfortable with the basics, you can\u00a0then\u00a0go ahead to understand some\u00a0more advanced\u00a0versions,\u00a0such\u00a0as\u00a0Sparse Merkle Trees,\u00a0or\u00a0study\u00a0how Bitcoin and Ethereum use these structures in their protocols.<br><br>Remember, every complex system is built on simple principles combined in clever ways. Merkle Trees are a perfect example of this\u2014nothing but a combination of multiple\u00a0simple hash. <\/p>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":24,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"neve_meta_sidebar":"","neve_meta_container":"","neve_meta_enable_content_width":"","neve_meta_content_width":0,"neve_meta_title_alignment":"","neve_meta_author_avatar":"","neve_post_elements_order":"","neve_meta_disable_header":"","neve_meta_disable_footer":"","neve_meta_disable_title":"","footnotes":""},"categories":[17],"tags":[],"class_list":["post-12044","post","type-post","status-publish","format-standard","hentry","category-blockchain"],"_links":{"self":[{"href":"https:\/\/metaschool.so\/articles\/wp-json\/wp\/v2\/posts\/12044","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/metaschool.so\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/metaschool.so\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/metaschool.so\/articles\/wp-json\/wp\/v2\/users\/24"}],"replies":[{"embeddable":true,"href":"https:\/\/metaschool.so\/articles\/wp-json\/wp\/v2\/comments?post=12044"}],"version-history":[{"count":4,"href":"https:\/\/metaschool.so\/articles\/wp-json\/wp\/v2\/posts\/12044\/revisions"}],"predecessor-version":[{"id":12054,"href":"https:\/\/metaschool.so\/articles\/wp-json\/wp\/v2\/posts\/12044\/revisions\/12054"}],"wp:attachment":[{"href":"https:\/\/metaschool.so\/articles\/wp-json\/wp\/v2\/media?parent=12044"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/metaschool.so\/articles\/wp-json\/wp\/v2\/categories?post=12044"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/metaschool.so\/articles\/wp-json\/wp\/v2\/tags?post=12044"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}