Merkle tree

February 15, 2021

Alice and her friends are incredibly grateful for everything Bob is doing. They've decided to surprise him for his birthday. And it should be something special.

A gold shoe? Eh, no. Temporary animal society tattoos? Eh, no. A couple of Pakistani Bulldogs? Well, not too shabby, but no. Not special enough.

No, they'll give him a Merkle tree constructed from their national identification numbers. Great, right?

Yeah, we know.

But, hey, how do they even know what a Merkle tree is? Well, they contacted a world-famous cryptographer to get some ideas. They went to a lot of trouble. But it was worth it. The Merkle tree is just wonderful.

Let's say the identification numbers of Alice and her friends are:


By constructing a Merkle tree, Alice and her friends have obtained a Merkle root. The Merkle root is something like a fingerprint of their identification numbers.

Merkle tree
Bob's engine

The first step was to compute hashes from their identification numbers. Sure, nothing easier than that with Bob's engine. For example:

sha256 099111170

They obtained Hash00, Hash01, Hash10, and Hash11:


The second step was to concatenate the pairs of hashes. There are only two pairs – the first two hashes and the last two hashes. The concatenated values are:


The concatenated values need to be hashed again. This way the friends obtained Hash 0 and Hash 1:


Again, the next step is to concatenate the pairs of hashes. There is only one pair left, the concatenated value is:


And this value has to be hashed again:


This value is called the Merkle root.

You might have guessed it. Bob was indescribably happy when Alice handed him this truly special gift. He knew Alice didn't like cryptography. And now she gave him a Merkle tree!

And that wasn't all! Having such a Merkle tree means one day one of Alice's friends could easily prove to Bob she or he is – one of Alice's friends.

All this person would have to show Bob is her identity document with the identification number. Let's say it is 071438819. Bob can now easily check whether this person is really one of Alice's friends.

Hash 11 = sha256(071438819)
Hash 1 = sha256(Hash 10 || Hash 11)
M = sha256(Hash 0 || Hash 1)

Note that || means concatenation. Bob only needs to check whether M is the same as Merkle root in a tree Alice gave him. This way, Bob would possess the proof that the person standing in front of him is really one of Alice's friends.

Merkle tree

Alice may not care, but such verification is very efficient – Bob doesn't need to reconstruct the tree completely. He just needs to compute a number of hashes proportional to the logarithm of the number of identification numbers at the bottom of the tree. Whatever that means. Yeah, Bob is immensely grateful for such a wonderful gift.

The Alice and Bob newsletter

Get highlights of Alice and Bob's adventures delivered to your email box.

Made by XLAB with ❤️
Follow us
Twitter Twitter