|

Merkle Mountain Range (MMR)

|
Visualizer

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 2n2^n leaves, but when it comes to MMR size, every tree has 2n+112^{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 nn, so that 2n+112^{n+1}-1 fits in MMR size. Then subtract that number from MMR size and add 2n2^n to leaf count (variable that starts at 00 and accumulates total number of leaves). Repeat until MMR size is 00.

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

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 SN0S \subset \mathbb{N}_0 (set of tree heights) so that sS(2s+11)=MMR size\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 TT in a similar way as SS but with one difference.tT(2t+1+1)=Z\sum_{t \in T} \left( 2^{t+1}+1 \right) = ZNow letT1={0,1,2}T_1 = \{ 0, 1, 2 \}T2={3}T_2 = \{ 3 \}And when we calculate ZZ value for those sets we getZT1=tT1(2t+1+1)=21+1+22+1+23+1=17Z_{T_1} = \sum_{t \in T_1} \left( 2^{t+1}+1 \right) = 2^1 + 1 + 2^2 + 1 + 2^3 + 1 = 17ZT2=tT2(2t+1+1)=24+1=17Z_{T_2} = \sum_{t \in T_2} \left( 2^{t+1}+1 \right) = 2^4 + 1 = 17As you can see, for ZZ 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 SS 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 thatsS1(2s+11)=sS2(2s+11)    S1=S2\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_2We'll do a proof by contradiction. Assume that there are two sets S1S_1 and S2S_2 that give the same MMR size, but they are not equal.sS1(2s+11)=sS2(2s+11)S1S2\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_2That 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 uS1S2u \in S_1 \setminus S_2, also we can assume that uu is the greatest of such elements. Therefore, we can write the following equationssS1(2s+11)=sS1s>u(2s+11)+2u+11+sS1s<u(2s+11)\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)sS2(2s+11)=sS2s>u(2s+11)+sS2s<u(2s+11)\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 writesS1s>u(2s+11)+2u+11+sS1s<u(2s+11)=sS2s>u(2s+11)+sS2s<u(2s+11)\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 uu is the greatest element on which S1S_1 and S2S_2 differ{s:sS1s>u}={s:sS2s>u}\{ 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 equation2u+11+sS1s<u(2s+11)=sS2s<u(2s+11)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 22 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.sS2s<u(2s+11)s=0u1(2s+11)=s=1u2su=2u+12u\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 - u2u+11+sS1s<u(2s+11)2u+112^{u+1}-1 + \sum_{s \in S_1 \land s < u} \left( 2^{s+1}-1 \right) \geq 2^{u+1}-1Since u0u \geq 02u+12u<2u+112^{u+1} - 2 - u < 2^{u+1}-1sS2s<u(2s+11)<2u+11+sS1s<u(2s+11)\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 SS so thatsS(2s+11)=MMR size\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 ZZ, because in that case there would be +u+u instead of u-u in the equation and the inequality wouldn't hold.

Converter

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