Building a Merkle Tree using Typescript

October 1, 2022 · ⏱️ 3 min read

TL;DR

You can find the finished repository here.

Introduction

I was trying to get into Web3 space ever since the rise of blockchain technologies but lacked the motivation for it.

So these days since I'm in a job break, I applied to several start-ups in Web3 space hoping that I finally have that push to get my hands dirty with Web3. Fortunately with one of them, I proceeded to the last interview stage where I was assigned with creating a Merkle Tree builder on Polkadot Block Headers using Typescript. Let's dive into it.

What is a merkle tree?

In cryptography and computer science, a hash tree or Merkle tree is a tree in which every "leaf" (node) is labelled with the cryptographic hash of a data block, and every node that is not a leaf (called a branch, inner node, or inode) is labelled with the cryptographic hash of the labels of its child nodes.

Basically it's kind of the web3 equivalent of a binary tree. Every node has 2 children but every node in the tree contains hashed information.

How does it work?

Hashing is a pretty interesting subject, we all know that it's some kind of vodoo magic that encrypts some value until we actually look up how it works but the principle is very straight forward. What's complicated is the algorithms (e.g. SHA256, MD-5) used to hash information. To get a better understanding on the blockchain and its essential technologies, you should definitely check out the Web3 Foundation's Blockchain Fundamentals videos on Youtube.

Given n different blocks (or any information, it doesn't necessarily need to be a block in the blockhain), Merkle Tree will hash each of those blocks. Typically you want this n to be a power of 2 since a binary tree structure will be generated. Then all these hashes are combined and hashed together until it reaches the root. Thanks to this approach, no matter how many blocks there are in a tree, we can represent a block by one hashed value while also being able to generate proofs to check if a certain piece of information is included in the tree. Using this mechanism, it can be verified that the informations received from a source are received without any modifications and/or damage.

Tips and tricks

You can check the end-result repository here in my Github. But here are some key points I faced while building this:

• Definitely use Buffers to store hashes, Buffers will let you store information in byte arrays thus making sure all the information in a block is uniquely represented.

• Do not just create a function to validate if an information is in the tree. Instead, generate an inclusion proof step by step, reaching all the way to the root and then validate based on this proof.

• Make sure your types comply with whatever chain you're going to work with. I built this MerkleTree to work with Polkadot's Kusama Chain.

And that's it! I think the repository is explanatory enough so I didn't want to go into implementation details here. Hope this was helpful.