|

Merkle Mountain Range (MMR)

|
Visualizer

Leaf count to MMR size algorithm

Let's take a closer look at how an MMR is structured. As we mentioned in another article, an MMR is a collection of balanced binary trees, but that collection has an important property - it is a sequence of trees ordered descending by their height. Notice that this inequality is strict, which implies that there are no two trees with the same height. (Height is the number of edges between the root node and leaves.)

Since every tree in an MMR is a balanced binary tree, it has 2h2^h leaves, where hN0h \in \mathbb{N}_0 is the height of that tree. To calculate the number of all nodes, we have to notice that on every layer (set of nodes which have the same distance to the root) there are exactly 2i2^i nodes where ii is the layer's height. So when we sum the number of nodes in each layer we get i=0h2i=2h+11\sum_{i=0}^{h} 2^i = 2^{h+1}-1.

Because the number of leaves in every tree is a power of 22 and every tree size appears at most once in an MMR, we can represent the number of leaves ll as a sum of powers of 22:l=i=0nli2i,li{0,1}l = \sum_{i=0}^n l_i 2^i, \quad l_i \in \{ 0, 1 \}In that representation, lil_i is 11 if and only if a tree of height ii is present in an MMR. Therefore, MMR size (ss) can be calculated using the following formula:s=i=0nli(2i+11)s = \sum_{i=0}^n l_i \cdot (2^{i+1}-1)After some simplifications, we get:s=i=0n2li2ii=0nli=2li=0nlis = \sum_{i=0}^n 2 \cdot l_i 2^i - \sum_{i=0}^n l_i = 2 \cdot l - \sum_{i=0}^n l_iNotice that i=0nli\sum_{i=0}^n l_i is just counting ones in the binary representation of number ll, so we can simplify even further:s=2lcount_ones(l)s = 2 \cdot l - \operatorname{count\_ones}(l)

Here are implementations in some languages

function count_ones(n: number) { let sum = 0; while (n) { sum++; n &= n - 1; } return sum; } function leaf_count_to_mmr_size(leaf_count: number) { return 2 * leaf_count - count_ones(leaf_count); }

Converter

© 2024 Herodotus Dev Ltd. All rights reserved.
Powered by