How to Write Smart Contracts for Merkle Tree Using Solidity

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.

1. 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
2. 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.
3. 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!