## Merkle Trees & Merkle Proofs Merkle Trees are a data structure in computer science. They are used to encrypt blockchain data more securely and efficiently. A Merkle Tree is comprised of nodes. At the base of the tree are leaves. Each leaf represents a hash of some data. At the top of the tree is the root, which is the root hash. This root hash is created by hashing all of the leaf hashes together. We can take two adjacent nodes at a time and hash them together. This produces a parent node. We repeat this process up the tree, hashing the parents until we reach the top of the tree and are left with a single hash: the root hash. A Merkle Proof is a method of proving that some data is in the tree. For example, if someone wanted to prove they were part of a club, we can provide a Merkle Proof. This proof includes all the hashes from the leaf to the root, except for the leaf hash itself. **Example:** Let's say we had a club with different tiers, like Bronze, Silver, Gold, and Platinum. For each tier, there is a password to prove you belong to that tier. We can create a Merkle Tree that includes each tier's password as a leaf. To prove someone belongs to a particular tier, we need to provide the hashes from that tier's leaf node to the root, except for the tier's leaf. This is called a Merkle Proof. **How Merkle Proofs Work:** Let's say we wanted to prove someone is a member of the club. We can take a Merkle Proof for the Bronze tier. This proof would include the following hashes: * **Hash 1-2:** This is a parent node, which was generated by hashing the Bronze tier's leaf node. * **Hash 3-4:** This is another parent node that is also part of the proof. * **Root Hash:** This is the top node in the tree, which is generated by hashing the two parent nodes, Hash 1-2 and Hash 3-4. This Merkle Proof gives us the ability to verify membership in the Bronze tier, without requiring the user to provide all of their data. We can verify the Merkle Proof by hashing the two parent nodes together, `Hash 1-2` and `Hash 3-4`. The result should match the Root Hash provided in the proof. **Advantages of Merkle Trees:** * **Efficiency:** Merkle Trees are very efficient in terms of data verification. * **Security:** Merkle Trees are very secure, making them ideal for use in cryptography. * **Scalability:** Merkle Trees are scalable and can be used to verify large amounts of data. We use Merkle Trees in a variety of use cases, such as: * **State changes in Rollups:** When a Rollup executes a transaction, we can use a Merkle Proof to prove the transaction was valid. * **Airdrops:** We can create an Allow List of addresses for an airdrop and use Merkle Proofs to determine which addresses are eligible. **OpenZeppelin:** We can use OpenZeppelin's Merkle Proof smart contract to make this even easier. The code includes a `verify` function that takes the Merkle Proof, the Merkle Root, and the leaf that we want to verify. ```javascript function verify(bytes32 proof, bytes32 root, bytes32 leaf) internal pure returns (bool) { return processProof(proof, leaf) == root; } ``` This function starts by taking the leaf and the first hash in the proof and hashing them together. This will update the `computedHash`. This is then used to hash the next element in the proof. We repeat this process until we've iterated through the entire proof array. The `computedHash` is returned, which will be compared to the `rootHash` that was provided in the proof. We can then determine if the leaf was actually in the Merkle Tree. Let's look at how OpenZeppelin uses Keccak256 in their hashing algorithm: ```javascript function efficientHash(bytes32 a, bytes32 b) private pure returns (bytes32) { return a < b ? efficientHash(a, b) : efficientHash(b, a); } ``` This code shows OpenZeppelin's implementation of Keccak256 using assembly. **Merkle Proofs for Our Airdrop:** We can now implement Merkle Proofs into our airdrop contract. This can help us eliminate the need for the inefficient loop through a long array of addresses. This approach uses the OpenZeppelin Merkle Proof smart contract and is much more efficient than the previous method.