Learn Merkle Trees by programming your own!

O Merkle Tree, O Merkle Tree. How lovely are thy branches!

Alright, what is a Merkle Tree and what does it do?

Quite simply, a Merkle Tree is a data structure that allows us to make efficient verifications that data belongs in a larger set of data.

They are commonly used in Peer to Peer networks where efficient proofs of this nature will help increase the scalability of the network.

Let’s take a step back and take a look at a binary Merkle Tree from a high-level. A Merkle Tree is a collection of hashes reduced to a single hash:

      ABCDEFGH <-- Merkle Root
       /    \
    ABCD     EFGH
    / \      / \
   AB  CD   EF  GH
  / \  / \  / \ / \
  A B  C D  E F G H

We use letters for convenience in this illustration. Each single letter represents a hash. The combined letters represent concatenated hashes that have been combined and hashed to form a new hash.

Over a series of a steps the eight leaf hashes A, B, C, D, E, F, G, andH are combined to create a single, unique hash that allows us to quickly check for inconsistencies without having to look at each individual data point.

As peers in a system, I can simply ask if your root matches mine. If so, we agree. This is a nice optimization for distributed systems of any kind!

Now, if we’re just comparing roots, you might be asking:

Why the tree structure? Could we not concatenate all eight hashes at once and store that hash?

Great question! We certainly could. This binary tree structure affords us one further optimization. It allows us to verify a single piece of data belongs in the tree without having all of the data. Consider the merkle tree from above with some missing data:

      ABCDEFGH
       /    \
    ABCD     EFGH
    / \      / \
   -  -     EF  GH
  / \  / \  / \ / \
  - -  - -  E F -  -

What do we need in order to prove that E belongs in this tree?

Just F, GH , ABCD . We use these to calculate EF, EFGH, and ABCDEFGH. Then we can compare the result to our expected root ABCDEFGH .

If something went wrong along the way, we would notice it at the root. For example if we replaced E with M:

      ABCDMFGH
       /    \
    ABCD     MFGH
    / \      / \
   -  -     MF  GH
  / \  / \  / \ / \
  - -  - -  M F -  -

We can quickly check ABCDMFGH against the our expected root ABCDEFGH and see we did not get our expected hash. Something’s wrong.

The savings become important with larger trees where the average case for verification of tree is log2(n) where n is the number of nodes in the tree. So for a tree of size 128, it would take only 7 hashes to determine the root.

Build a Merkle Tree in JavaScript

As a programmer, I find I learn best by building things from scratch. I believe this holds true for most engineers; we like to get our hands on things.

You can build your own Merkle Tree in the ChainShot Ethereum Developer Bootcamp. This curriculum is full of challenges and tutorials designed to take your blockchain programming skills to the next level!

Join the Merkle Tree Class

Want to actively take part in an interactive classroom to build your own Merkle Tree? Here’s a preview of what the class holds:

Join our Merkle Tree Class!

Want to learn more about the ChainShot Classroom? Check it out here.

As always follow us on Twitter and Medium for all the latest ChainShot updates!