Merkle Mountain Range (MMR) Visualizer

Merkle Mountain Range (MMR)

MMR size to leaf count algorithm

Coverting MMR size to leaf count is a bit more complicated than the other way around, because unlike leaf count, MMR size doesn't immediately tell us how the tree looks. In case of leaf count, every tree had $2^n$ leaves, but when it comes to MMR size, every tree has $2^{n+1}-1$ nodes. That means that we can't simply look at binary representation of MMR size and tell something about the tree structure.

So to solve this problem we will use the following approach. Find the largest $n$ , so that $2^{n+1}-1$ fits in MMR size. Then subtract that number from MMR size and add $2^n$ to leaf count (variable that starts at $0$ and accumulates total number of leaves). Repeat until MMR size is $0$ .

When it comes to actual implementation, instead of finding the largest $n$ as described above, we will just start with $n = \lfloor \log_2 (\text{MMR size}) \rfloor$ and at each step check if it fits in MMR size, then do subtraction and decrement $n$ .

Here are implementations of that exact algorithm in some languages

function bit_length(n: number) {
    return n.toString(2).length;
}

function mmr_size_to_leaf_count(mmr_size: number) {
    let leaf_count = 0;
    for (let height = bit_length(mmr_size); height >= 0, height--) {
        const tree_leaf_count = 1 << height;
        const tree_size = 2 * tree_leaf_count - 1;
        if (tree_size <= mmr_size) {
            leaf_count += tree_leaf_count;
            mmr_size -= tree_size;
        }
    }
    if (mmr_size > 0) {
        throw new Error(`Invalid elements count`);
    }
    return leaf_count;
}

But how can we know that this algorithms is correct? We need to do a proper mathematical proof.

So what we have to proof is that for every valid MMR size, there exists only one set $S \subset \mathbb{N}_0$ (set of tree heights) so that $\sum_{s \in S} \left( 2^{s+1}-1 \right) = \text{MMR size}$

You may ask how it could be possible that two sets represent the same MMR size. Indeed that's not possible, but if we take a look at the following example, we'll understand why proper proof is needed.

Let's define another set $T$ in a similar way as $S$ but with one difference. $\sum_{t \in T} \left( 2^{t+1}+1 \right) = Z$ Now let $T_1 = \{ 0, 1, 2 \}$ $T_2 = \{ 3 \}$ And when we calculate $Z$ value for those sets we get $Z_{T_1} = \sum_{t \in T_1} \left( 2^{t+1}+1 \right) = 2^1 + 1 + 2^2 + 1 + 2^3 + 1 = 17$ $Z_{T_2} = \sum_{t \in T_2} \left( 2^{t+1}+1 \right) = 2^4 + 1 = 17$ As you can see, for $Z$ defined as above, it's not the case that there exists one set so that the equation holds.

So going back to our proper equation for $S$ and MMR size, how do we show that there is only one such set for a given MMR size? We need to proof that if there are two sets that give the same mmr size, then those sets are equal.

We want to proof that $\sum_{s \in S_1} \left( 2^{s+1}-1 \right) = \sum_{s \in S_2} \left( 2^{s+1}-1 \right) \implies S_1 = S_2$ We'll do a proof by contradiction. Assume that there are two sets $S_1$ and $S_2$ that give the same MMR size, but they are not equal. $\sum_{s \in S_1} \left( 2^{s+1}-1 \right) = \sum_{s \in S_2} \left( 2^{s+1}-1 \right) \land S_1 \neq S_2$ That means that there is at least one element that is in one set but not in the other. Without loss of generality, let's assume that $u \in S_1 \setminus S_2$ , also we can assume that $u$ is the greatest of such elements. Therefore, we can write the following equations $\sum_{s \in S_1} \left( 2^{s+1}-1 \right) = \sum_{s \in S_1 \land s > u} \left( 2^{s+1}-1 \right) + 2^{u+1}-1 + \sum_{s \in S_1 \land s < u} \left( 2^{s+1}-1 \right)$ $\sum_{s \in S_2} \left( 2^{s+1}-1 \right) = \sum_{s \in S_2 \land s > u} \left( 2^{s+1}-1 \right) + \sum_{s \in S_2 \land s < u} \left( 2^{s+1}-1 \right)$ Since we assumed those sums are equal, we can write $\sum_{s \in S_1 \land s > u} \left( 2^{s+1}-1 \right) + 2^{u+1}-1 + \sum_{s \in S_1 \land s < u} \left( 2^{s+1}-1 \right) = \sum_{s \in S_2 \land s > u} \left( 2^{s+1}-1 \right) + \sum_{s \in S_2 \land s < u} \left( 2^{s+1}-1 \right)$ Because $u$ is the greatest element on which $S_1$ and $S_2$ differ $\{ s : s \in S_1 \land s > u \} = \{ s : s \in S_2 \land s > u \}$ Then we can cancel first sums on both sides of the equation $2^{u+1}-1 + \sum_{s \in S_1 \land s < u} \left( 2^{s+1}-1 \right) = \sum_{s \in S_2 \land s < u} \left( 2^{s+1}-1 \right)$ Intuitively, we see that the greatest power of $2$ is on the left hand site, so we want to maximize the sum on the right hand side and minimize the sum on the left hand side. If that results in left hand site still being greater than right, we have a contradiction. $\sum_{s \in S_2 \land s < u} \left( 2^{s+1}-1 \right) \leq \sum_{s = 0}^{u-1} \left( 2^{s+1}-1 \right) = \sum_{s=1}^u 2^s - u = 2^{u+1} - 2 - u$ $2^{u+1}-1 + \sum_{s \in S_1 \land s < u} \left( 2^{s+1}-1 \right) \geq 2^{u+1}-1$ Since $u \geq 0$ $2^{u+1} - 2 - u < 2^{u+1}-1$ $\sum_{s \in S_2 \land s < u} \left( 2^{s+1}-1 \right) < 2^{u+1}-1 + \sum_{s \in S_1 \land s < u} \left( 2^{s+1}-1 \right)$ So we get a contradiction and therefore we proved that for a given MMR size there is only one set $S$ so that $\sum_{s \in S} \left( 2^{s+1}-1 \right) = \text{MMR size}$ Because of that, if we iterate over that set starting from the greatest element, we will get the correct result.

Notice that this proof wouldn't work in example with $Z$ , because in that case there would be $+u$ instead of $-u$ in the equation and the inequality wouldn't hold.

MMR size to leaf count algorithm

Converter