# Merkle tree

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:

```
099111170
012341213
088842299
071438819
```

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.

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:

```
e21e49a9eb5857b37356588b34a68caa194dddff0aa64a3d1dbd3f70f4234dcb
632f92020c9a9783b4b97648d7cd92d4e2fef49f6d3ef1c90f437b3db5fe4760
adc5bb92652d8ed42f870b8081e1812a8aeeeb328338b4495ea5629a912251ac
018a0c04e71ed4a6060e2e9d3f91fb57600b1d400f50b9466e2e0b8a15834a4b
```

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:

```
e21e49a9eb5857b37356588b34a68caa194dddff0aa64a3d1dbd3f70f4234dcb632f92020c9a9783b4b97648d7cd92d4e2fef49f6d3ef1c90f437b3db5fe4760
adc5bb92652d8ed42f870b8081e1812a8aeeeb328338b4495ea5629a912251ac018a0c04e71ed4a6060e2e9d3f91fb57600b1d400f50b9466e2e0b8a15834a4b
```

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

```
015b375433ae108146bd1ca9cd5d0fa9c8d863e5343511111c17793f61427adb
6af0149ff62b9c99a96b17b6e09afac84e0c686d0c0ab0bc20b5431d0943ec29
```

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

```
015b375433ae108146bd1ca9cd5d0fa9c8d863e5343511111c17793f61427adb6af0149ff62b9c99a96b17b6e09afac84e0c686d0c0ab0bc20b5431d0943ec29
```

And this value has to be hashed again:

```
60a40dc93d1f953f19120aea1dd79694950fd67af88ea6b8c0e9715d0cb55aa1
```

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.

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.