Github link to my code - Merkle Tree

What is a Merkle Tree ?

A Merkle Tree is a tree data structure where all of its nodes are hashed using a secure hash function, like SHA 256.

Implementing Merkle Trees as arrays

A Merkle Tree can be implemented using generic C like array data structure available in most procedural programming languages. Today we will see an example of how it is done in Rust.

Let’s say we have 4 elements that we need to create a Merkle tree out of. Then we need to figure out a number of things,

• Total Number of elements in the array containing the Merkle Tree will have.

Figuring out number of elements

Question is how big should be the Merkle array ?

Answer is simple, notice that each level of the tree, the number of elements halve in 2, assuming we are creating a binary tree.

Now lets take a look at the code that calculates the size of the Merkle Array.

fn calculate_array_capacity(input_arr_size: i32) -> i32 {
    let mut temp_arr_size = input_arr_size;
    let mut capacity = 0;
    while temp_arr_size > 1 {
        capacity += temp_arr_size;
        temp_arr_size = (temp_arr_size + 1) / 2;
    }
    capacity + temp_arr_size  # this a return statement, Rust lang discourages the use of `return` keyword
}

Once you have the size of the Merkle Array you can move on to hashing and creating the nodes of the tree. If you know about Segment trees this might look very similar, because it is the same thing basically, just hashed.

Building the tree

Now comes the interesting part of figuring out how to iterate over the array to fill in the right index. But first, we need to decide if we will fill the array from the front or the back.

Array filling order does not really matter we can choose anything, because of the way array iteration works in Rust, I chose to go with filling from from element 0. But you can just as easily use the other way round and it would be just be a matter of iterating from the last element.

Now, How do you iterate over the array ?

Lets take a look at the code first then we can go into each line.

pub fn new(arr: Vec<String>) -> Self {
    let arr_size = arr.len();  
    let capacity = Self::calculate_array_capacity(arr_size as i32); ------> line 3
    let mut merkle_tree = Vec::with_capacity(capacity as usize); -------> line 4
    let mut index: usize = 0;
    merkle_tree = vec!["".to_string(); capacity as usize];

    // encrypt each element in original array and fill in the Merkle Array
    for el in arr.iter() {
        let val = el.clone();
        let encrypted_val = Self::encrypt_sha256(val);
        merkle_tree[index] = encrypted_val;
        index += 1;
    }
    let mut N = arr_size;

    //helps in calculating the real index of the elements 
    // to hash while traversing over the array.
    let mut offset = 0; ------------------------> helps keep track of real index of the array to fill

    // Here on out we pick 2 elements and start hashing
    // them and putting them in proper index at Merkle
    // Tree
    while N > 1 {    -------------------------->  line 18, iterate over tree level until reaching level 0
        for j in (0..N).step_by(2) {  ----------> line 19, iterate over the elements of a level of the tree, and pick its elements
            // calculates the real index in the array.
            let left_node_index = offset + j; 
            let last_index = offset + N - 1;
            let left = merkle_tree[left_node_index].clone();
            let right = merkle_tree[std::cmp::min(left_node_index + 1, last_index)].clone(); ----> line 24
            let concatenated_value = left + right.as_str();
            merkle_tree[index] = Self::encrypt_sha256(concatenated_value);
            index += 1;
        }
        offset += N;
        N = N.div_ceil(2);
    }
    Self { merkle_tree }
}

Notice line 3 and line 4 create the new array for Merkle Tree. Then this loop fills the merkle tree from element 0.

Take each element of the original array, encrypt it and put it in the Merkle array.

for el in arr.iter() {
    let val = el.clone();
    let encrypted_val = Self::encrypt_sha256(val);
    merkle_tree[index] = encrypted_val;
    index += 1;
}

Now comes the most interesting part:

1. because we are filling an array, how do you choose the 2 elements you are going to pick and hash?
2. how do we pick the index where the hash of those two will be written to?

Look at these series of pictures, this will help to make it more clear what that while loop indicated at line 3 is doing

• Move the index of the index i to i + 2, and j to j + 2, x to x + 1.

Now when i moves to index 4, this means we have gone beyond level 2.

Now see how array indexes map to tree level 0, level 1 and level 2.

Now let talk about each line in the while loop.

while N > 1 {

This line keeps track of, on which level we are in the tree. We have to stop when we reach N = 1.

for j in (0..N).step_by(2) {

This line jumps 2 element on each iteration meaning it will always land on an even index.

let left_node_index = offset + j;
let left = merkle_tree[left_node_index].clone();

This is most critical piece of code, j pick an element on the tree level and then adding offset help us to get the real index of the element in the array. Thus basically this becomes the left node that we pick, now we have to pick the right node of the tree to concatenate and hash.

let right = merkle_tree[std::cmp::min(left_node_index + 1, last_index)].clone();

This is where we run into a tricky situation, what if there is no element on the right then that means the left node is alone without a right node, then we have reached the end of the number of nodes on this level (this does not mean the Merkle array’s last element). It means that on this level of the tree there is no nodes on the right to pick from.

Thus if there is no node on the right then we pick left node twice, because in that case left_node_index = last_index, they both become equal.

let concatenated_value = left + right.as_str();
merkle_tree[index] = Self::encrypt_sha256(concatenated_value);
index += 1;

Once you have both the left and right nodes you concatenate them and encrypt them and store them at the index being tracked incrementally (+ 1, on each iteration of the for loop)

offset += N;

Once you are done with a level on the tree, the offset value must move to so that on the next iteration we can choose and populate the right index in the Merkle Array.

N = N.div_ceil(2);

Then at last, because we have processed one level now we need to move to another level of the tree.

I hope the explanations made sense for the reader. Doing a dry run of the code, greatly increases the understanding and clear the picture.

• Thank you for reading my shennanigans