Merging Merkle Mountain Ranges

English CKB Development & Technical Discussion
1

Merging Merkle Mountain Ranges

MMR’s (or Merkle Mountain Ranges) are the most efficient accumulator in use in blockchain systems today. I’ll do my best to make this explanation straightforward but if background information helps- check out these links from Peter Todd and the Grin community.

Creating an MMR

A MMR can be simply represented by a fixed array.

Position Value
0 0
1 0
2 0
3 0

When a item is added to the list, we start the lowest value in the array.

If there is no value at this position, we insert the value and we are done.

Position Value
0 JimiHendrix
1 0
2 0
3 0

Alternatively, if there is a value at the position (as demonstrated by adding the second value), we run this process:

  1. Hash the existing value in this position and the new value

  2. Write a null value to the position

  3. Repeat the test at the next position

Position Value
0 0
1 h(JimiHendrix|JanisJoplin)
2 0
3 0

In this case Position1 was empty, so the value was written to Position1

Adding another value, we start at the lowest position. In this case, there’s no value at this position- we insert the value and we are done.

Position Value
0 KurtKobain
1 h(JimiHendrix|JanisJoplin)
2 0
3 0

Let’s add a fourth value, this time, instead of just showing the outcome, let’s step through the process

We start at the lowest position, there is a value at this position.

Position Value
0 KurtKobain JuiceWRLD
1 h(JimiHendrix|JanisJoplin)
2 0
3 0

Given there is a value in the position:

  1. Hash the existing value at this position and the new value

  2. Write a null value to the position

  3. Repeat the test at the next position

Position Value
0 h(KurtKobain|JuiceWRLD)
1 h(JimiHendrix|JanisJoplin)
2 0
3 0
Position Value
0 0
1 h(JimiHendrix|JanisJoplin) h(KurtKobain|JuiceWRLD)
2 0
3 0

We see at Position1, there is an existing value:

  1. Hash the existing value at this position and the new value

  2. Write a null value to the position

  3. Repeat the test at the next position

Position Value
0 0
1 0
2 h(h(JimiHendrix|JanisJoplin|h(KurtKobain|JuiceWRLD))
3 0

There is no value at Position2, so we write the value and we are done

I realize this demonstration ended up looking like alot but I hope for some readers it’s clear why this structure is so efficient in an on-chain environment.

MMR’s and Binary Addition

The process of building an MMR is binary addition (with hashing).

The “peaks” of the MMR are found at the 1 bits of the binary representation of the number of items in MMR.

Don’t take my word for it, add up the numbers in the examples above. If there’s a value at the position, add the number to your sum.

(Binary numbers)

Position Value
0 1
1 2
2 4
3 8

This point is important, as we have the architecture of an authenticated data structured described very succinctly in the number of items in the structure.

Given that these structures are built with binary addition, we can also combine them using binary addition.

Merging Merkle Mountain Ranges

Overall we are going stick with the same process we started with.

We start the lowest value in the array, if there is no value at this position, we insert the value and we are done.

If there is an existing value:

  1. Hash the existing value at this position and the new value

  2. Write a null value to the position

  3. Repeat the test at the next position

(I’m quickly adding the concept of a “Carry” here… binary addition explained).

Position Value1 Op Result Op Value2 Carry
0 0xab 0
1 0 0xcd
2 0xef 0xac
3 0xfd 0
4 0 0
Position Value1 Op Result Op Value2 Carry
0 0xab → 0xab 0 0
1 0 0xcd
2 0xef 0xac
3 0xfd 0
4 0 0
Position Value1 Op Result Op Value2 Carry
0 0xab → 0xab 0 0
1 0 0xcd ← 0xcd 0
2 0xef 0xac
3 0xfd 0
4 0 0
Position Value1 Op Result Op Value2 Carry
0 0xab → 0xab 0 0
1 0 0xcd ← 0xcd 0
2 0xef + 0 + 0xac h(0xef|0xac)=0xff
3 0xfd 0
4 0 0
Position Value1 Op Result Op Value2 Carry
0 0xab → 0xab 0 0
1 0 0xcd ← 0xcd 0
2 0xef + 0 + 0xac h(0xef|0xac)=0xff
3 0xfd + 0 + 0 h(0xfd|0xff)=0xaa
4 0 0
Position Value1 Op Result Op Value2 Carry
0 0xab → 0xab 0 0
1 0 0xcd ← 0xcd 0
2 0xef + 0 + 0xac h(0xef|0xac)=0xff
3 0xfd + 0 + 0 h(0xfd|0xff)=0xaa
4 0 0xaa 0

This doesn’t look all that impressive honestly. To me it looks pretty straightforward.

However, let’s think about this in the context of the cell model, MMR’s for authenticated data can grow separately and then be combined for efficiency later. These could be lists of transactions in L1.5/2 protocols, records of non-fungible asset issuance, etc.

Values inside of an MMR can later be changed through state transition proofs but that’s a very different topic.

2 Likes