Solidity: Merkle Tree

Today we are going to look at an interesting topic — the implementation of the Merkle tree with a smart-contract (Solidity). What can you use it for? Well, for example you can implement whitelist logic for an NFT collection.

Introduction

Suppose we have 8 transactions that are combined into one block. We need to make sure:
1) that this block has not been tampered with
2) all transactions in it have really been represented

To do it this way -> For each transaction (or any other data) calculate its hash (H₁, H₂…). This will be considered as one “sheet”. Then we produce a new hash (layer 2) based on two hashes and so on at each level, until the Root hash.

How can we make sure that the transaction (e.g. T₅) is really in the block (Root)?
We have a Root hash which we will compare.

1. We take the transaction hashes(H₅ and H₆) and recalculate the hash H₅-₆
2. We take hashes(H₅-₆ and H₇-₈) and recalculate H₅-₆-₇-₈
3. Take (H₁-₂-₃-₄ and H₅-₆-₇-₈), count the new Root hash and compare it with the original Root

If the Root hashes match — then the transaction is correct and nothing was changed in it.
Note that we don’t need all the transaction hashes.

Important: The number of leaves in the tree is not arbitrary and is limited to the following value 2ⁿ
The example in the following photo will not work

Merkle Tree writing Solidity code

The following is the code that implements a hash tree using a smart-contract written in solidity. Don’t be afraid, I’ll take this code apart below😉

Consider the variables:
bytes32[] public hashes — an array where we will store all our hashes, they will represent the tree;
string[4] transactions = [...] — an array of strings that will mimic transactions. This can be any kind of data;

Let’s write a hash function:

function makeHash(string memory input) public pure returns(bytes32){        
  return keccak256(
    abi.encodePacked(input)
  ); 
}

keccak256 returns a hash with a predefined length of 32 bytes, but it needs to pass a correctly encoded value, which we get with abi.encodePacked().

We will produce hashes in the constructor:

1. Go through the transactions array, make hashes for all transactions and add them to the hashes array

constructor() {        
  for(uint i = 0; i < transactions.length; i++) {                   
    hashes.push(makeHash(transactions[i]));  // H1 H2 H3 H4        
  }
  ...
}

2. Now we need to combine these hashes.
Remember that the number of leaves is halved at each successive level.
Count how many leaves there are at a given moment uint count = transactions.length //number of leaves .
Let’s implement the while(count > 0) loop {…}. Since we are going to go to a higher level we need to add a new variable uint offset = 0;

For the combination of hashes, we implement the for() loop. The photo shows the iteration of the loop (red — first, second; green — third; purple — fourth iteration, it will not be executed).

This is how we calculated the Root hash and other.

Check function

Let’s implement the transaction validation function. Suppose that we want to know the authenticity of T₃(H₃). We need 2 hashes(H₄, H₁-₂) to do this. We will store these elements in the array bytes32[] memory proof .

Variable bytes32 hash = makeHash(transaction); stores the hash of the transaction we are going to check.
Next, we write a for() loop to traverse the proof array.
Notice that we are checking element (index) for parity, because if the element is even (example H₃), we have to take the element to the right (H₄) and vice versa to build the total hash.

Depending on the parity of the element we fulfill the following conditions if-else:

function verify(...) public pure returns(bool) {      
  bytes32 hash = makeHash(transaction);
  for(uint i = 0; i < proof.length; i++) {            
    bytes32 element = proof[i];  
    if(index % 2 == 0) {                
      hash = keccak256(abi.encodePacked(hash, element));
    } else {               
      hash = keccak256(abi.encodePacked(element, hash));
    }
}

Then we have to go to the level above. We remember that this halves the number of elements, so we add index = index / 2; . At the end we compare the original Root hash with what we counted return hash == root; .

Functionality check

Go to Remix, create a new file in /contracts folder and copy/paste the code from this repository (don’t forget to put a star⭐).
1) Compile this contract.
2) Deploy the contract.
3) Try to check the transaction

I will check the transaction with index 2.
You can get the hashes from the hashes button (you write the index of the hash you want in the input) after the deploy.
Root hash will be the last element in the hashes array.
Proof array for the transaction with index 2(H₃) will include hashes H₄ and H₁-₂.
I got the following data:

// transaction expm: "TX3: John -> Mary"
// index: 2
// root: 0x4aebbc948c21be9df7ac8d63e2f1c6d9a58998d4edfba9b192a6f8d4d7d07958
// H4: 0x69a40d72d1258df801a7ae1e36dd586717a112334f8d9ca4664a339168874ef5
// H1-2: 0x83d2dbc9a1246936e38d7f1d4de7709616ac8c32e5159f4a79b5587800249d24

If I put these values into the verify function call, I get true. If there is even the slightest change in any data we get false.

Phew, that was really a lot, but now you understand how to implement and how the Merkle Tree in a smart-contract works. In the future, I might take apart the implementation of whitelist(allowlist) using Merkle’s tree.

I look forward to your reactions and comments✍🏻

Important: this code not able for real world, read this article if you want create airdrop/whitelist for your collection