How to Write Smart Contracts for Merkle Tree Using Solidity

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!

Leave a Reply

Your email address will not be published.