Merkle Mountain Range (MMR) Visualizer

Merkle Mountain Range (MMR)

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 $2^h$ leaves, where $h \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 $2^i$ nodes where $i$ is the layer's height. So when we sum the number of nodes in each layer we get $\sum_{i=0}^{h} 2^i = 2^{h+1}-1$ .

Because the number of leaves in every tree is a power of $2$ and every tree size appears at most once in an MMR, we can represent the number of leaves $l$ as a sum of powers of $2$ : $l = \sum_{i=0}^n l_i 2^i, \quad l_i \in \{ 0, 1 \}$ In that representation, $l_i$ is $1$ if and only if a tree of height $i$ is present in an MMR. Therefore, MMR size ( $s$ ) can be calculated using the following formula: $s = \sum_{i=0}^n l_i \cdot (2^{i+1}-1)$ After some simplifications, we get: $s = \sum_{i=0}^n 2 \cdot l_i 2^i - \sum_{i=0}^n l_i = 2 \cdot l - \sum_{i=0}^n l_i$ Notice that $\sum_{i=0}^n l_i$ is just counting ones in the binary representation of number $l$ , so we can simplify even further: $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);
}

Leaf count to MMR size algorithm

Converter