<h1>Merkle Trees and Merkle Proofs</h1>
<ul>
<li><code>Efficient Data Verification</code>: Merkle trees help verify data presence without downloading the entire blockchain.</li>
<li><code>Structure</code>: Data is hashed, and these hashes are organized in a tree-like structure (Merkle tree).</li>
<li><code>Verification Process</code>: By comparing hashes from the data to the tree’s root, one can confirm data authenticity.</li>
<li><code>Why Important:</code> Without Merkle proofs, verifying a transaction would require checking all previous blocks and transactions.</li>
<li><code>Hashing Role</code>: Hash functions are used to build the tree by repeatedly hashing pairs of nodes until reaching the root.</li>
</ul>
<h2>Merkle Tress!!!</h2>
Note: We can use merkle trees and proofs to efficiently store the <code>1000+ addresses on-chain</code> to verify and use for any verification tasks.
<ul>
<li>It is a data structure similar to binary tree</li>
<li>It acts as a summary of all the transactions in a block, <code>enabling fast and secure verification</code> of data across larger datasets.</li>
<li>We can use merkle tree to store data in hash form to <code>optimize the searching and security of our application</code></li>
</ul>
Example for merkle trees:
<ol>
<li>
Leaf Nodes:
<ul>
<li>Consider four transactions block or data (T1,T2,T3,T4)</li>
<li>hash form of above data (H1,H2,H3,H4)</li>
<li>T1,T2,T3,T4 -&gt; Actual data need to be stored</li>
</ul>
</li>
<li>
Intermediate Nodes:
<ul>
<li>This nodes will be hash of its children nodes</li>
<li><code>H12 -&gt; hash of H1 and H2</code></li>
<li><code>H34 -&gt; hash of H3 and H4</code></li>
</ul>
</li>
<li>
Root Nodes:
<ul>
<li>also called (merkle root!!!)</li>
<li>This contains the hash of its intermediate nodes</li>
<li><code>H1234 -&gt; hash of H12 and H34</code></li>
</ul>
</li>
</ol>
<ul>
<li>Each pair has a computed hash that is stored directly in the parent node</li>
<li>These nodes are then grouped into pairs, and their hash is stored on the next level up.</li>
<li>This process continues until reaching the top of the Merkle tree (root node)</li>
</ul>
<img src="https://media.daily.dev/image/upload/s--MV6qy-oP--/f_auto/v1742129703/ugc/content_4b390db6-788b-409e-aa72-2b7551b97bc8" alt="MerkleTree">
<h2>Merkle Proofs</h2>
<ul>
<li>
It is a method to prove that a specific piece of data is a <code>part of Merkle tree</code>, without needing access to the entire Merkle tree.
</li>
<li>
For verification we need the hash of <code>sibling nodes</code>!!!
</li>
<li>
To verify that data is indeed present in tree, we need the <code>hash of sibling nodes</code> and <code>hash of actual data</code>
</li>
</ul>
Example to verify data presence:
<ol>
<li>
Get hash of data:
<ul>
<li>Let’s check for T2 presence</li>
<li>Get hash of T2-&gt;H2</li>
<li>Need hash of sibling node (H1)</li>
</ul>
</li>
<li>
Check hashing with H12:
<ul>
<li>Hash both leaf node (H1 and H2) to get H12</li>
<li>We will require hash of H34</li>
</ul>
</li>
<li>
Check with intermediate sibling node:
<ul>
<li>Hash both H12 and H34</li>
<li>Compare the above hash(H1234) with provided hash of root node.</li>
<li>If correct -&gt; data is Present in tree</li>
</ul>
</li>
</ol>
A smart contract can store only the Merkle root on-chain, saving more gas than storing every address on an airdrop. The Merkle tree generates a Merkle proof, which can be verified to prove eligibility. This proof authenticates a specific wallet address included in the list of eligible wallets by comparing it to the Merkle root.
<h2>Sources</h2>
<ol>
<li>
Merkle trees and Proofs:
<ul>
<li><a href="https://medium.com/@swastika0015/merkle-proofs-explained-208a72971a50" target="_blank" rel="noopener nofollow">https://medium.com/@swastika0015/merkle-proofs-explained-208a72971a50</a></li>
</ul>
</li>
<li>
EIP-712 and EIP-191:
<ul>
<li><a href="https://www.cyfrin.io/blog/understanding-ethereum-signature-standards-eip-191-eip-712" target="_blank" rel="noopener nofollow">https://www.cyfrin.io/blog/understanding-ethereum-signature-standards-eip-191-eip-712</a></li>
</ul>
</li>
<li>
ECDSA signature algorithm:
<ul>
<li><a href="https://www.cyfrin.io/blog/elliptic-curve-digital-signature-algorithm-and-signatures" target="_blank" rel="noopener nofollow">https://www.cyfrin.io/blog/elliptic-curve-digital-signature-algorithm-and-signatures</a></li>
<li><a href="https://fitsaleem.medium.com/ethereums-elliptic-curve-digital-signature-algorithm-ecdsa-88e1659f4879" target="_blank" rel="noopener nofollow">https://fitsaleem.medium.com/ethereums-elliptic-curve-digital-signature-algorithm-ecdsa-88e1659f4879</a></li>
</ul>
</li>
<li>
Openzepplein create merkle tree js library:
<ul>
<li><a href="https://github.com/OpenZeppelin/merkle-tree" target="_blank" rel="noopener nofollow">https://github.com/OpenZeppelin/merkle-tree</a></li>
<li><a href="https://github.com/OpenZeppelin/openzeppelin-contracts/blob/master/contracts/utils/structs/BitMaps.sol" target="_blank" rel="noopener nofollow">https://github.com/OpenZeppelin/openzeppelin-contracts/blob/master/contracts/utils/structs/BitMaps.sol</a></li>
</ul>
</li>
</ol>
#blockchain #smart-contracts #web3 #merkltrees #merkleproofs #solidity #ethereum #development #coreconcepts

An independent squad focused on Ethereum blockchain development and the Web3 ecosystem. We'll explore and understand Solidity smart contracts and dive into tools like Web3.js, Truffle, Ganache, Hardhat, and Foundry-Forge.

Ethereum BlockChain Development

Merkle trees are a data structure used to verify data presence efficiently within a blockchain without downloading the entire chain. They consist of hashed data organized in a tree-like structure to ensure data authenticity through hashing and comparing nodes. Merkle proofs allow users to verify the presence of specific data in the tree without accessing the whole structure, optimizing data storage and verification processes.

What are Merkle Trees and Proofs?