The advent of Smart Contracts in blockchain technology raises the bar for blockchain use cases. Smart contract-enabled blockchains are chiefly responsible for various new protocols and projects being birthed on blockchains to expand blockchain applications. Smart contracts are created via a programming language called Solidity.
What is Solidity?
Solidity is an object-oriented programming language developed by Ethereum for developing and deploying smart contracts on blockchains. The functionalities of tools and improvement of protocols in public blockchains are usually encoded in a string of automated and pre-defined terms of agreement themed "Smart Contract." A smart contract is used to design the behavior and functionalities of Merkle Tree and a host of other tools in blockchains.
What is a Merkle Tree?
A Merkle tree is a data structure hierarchy used to verify if a particular data is part of a dataset without expending too many resources. The verification is done by merging data layers to form a single Merkle Root. This Merkle root is then used to verify any or all data in the Merkle tree. The tree is also called a Binary Hash Tree because the hierarchical data structure is built from hashes of contrasting data blocks. The tree comprises the leaves or leaf nodes, branches, and the Merkle Root.
- Leaf Nodes The leaf nodes store the hash value of hashed data transactions in a block. It is located at the base of the Merkle tree
- Non-leaf Nodes Non-leaf nodes are formed when leaf nodes are jointly hashed in pairs. They are called non-leaf nodes because they have no direct connection with the transaction. However, the non-leaf nodes might be in layers, depending on the number of transactions in a block. Irrespective of the number of layers formed, all the layers are referred to as Branches or Intermediate nodes.
- Merkle Root The non-leaf nodes are also jointly hashed in pairs leading to a final layer of just two nodes. These two nodes are jointly hashed too to form a single hash called the Merkle Root or Root hash, which is the Merkle tree's final hashing.
How to Write a Smart Contract for a Merkle Tree
The Merkle Tree is usually created on a backend to get its Merkle root or Root hash. This is done using the popular MerkleTreeJS and keccak256 libraries using the following JavaScript code:
const {MerkleTree} = require("merkletreejs")
const keccak256 = require("keccak256")
let list = [ /* eth addresses */ ]
let leaves = addresses.map(addr => keccak256(addr))
let merkleTree = new MerkleTree(leaves, keccak256, {sortPairs: true})
let rootHash = merkleTree.getRoot().toString('hex')
Verifying Data with a Merkle Proof
This is done using two pieces of code which are
- Server-side code: To create a proof
- Solidity code: For the Smart contract
The input (address) is hashed to create a proof.
let address = "0x..." // The input
let hashedAddress = keccak256(address)
let proof = merkleTree.getHexProof(hashedAddress)
The proof can then be used as call data to the smart contract in order for the smart contract to verify the validity of the proof on-chain.
import "@openzeppelin/contracts/utils/cryptography/MerkleProof.sol";
// ...
bytes32 public root = 0x...;
function checkValidity(bytes32[] calldata _merkleProof) public view {
bytes32 leafToCheck = keccak256(abi.encodePacked(msg.sender));
require(MerkleProof.verify(_merkleProof, root, leafToCheck), "Incorrect proof");
// Do stuff
}
Do not forget to save the root of the newly created tree in the smart contract.
Thanks for reading!