Append function

The append function is used to add a new leaf to the MMR. The new leaf is added to the right of the last leaf in the MMR. Appending a new leaf might require creating some amount of new nodes. This is because MMR can contain at most one tree of each height, so if the last tree is a single node, appending a new leaf without creating other nodes would result in two trees of height 0.

For example above, we have an MMR with 11 leaves. Appending a new node (20) would require nodes 21 and 22 to be created, because trees of size 0 and 1 already exist.

Now let's see how to calculate how many new nodes will be created besides the new leaf.

As we mentioned in leaf count to MMR size article, we can calculate number of nodes in MMR using the following formula:$$2 \cdot n - \operatorname{count\_ones}(n)$$where $n$ is the number of leaves in the MMR.

To calculate how many new nodes will be created, we can subtract the number of nodes in the MMR before appending the new leaf from the number of nodes in the MMR after appending the new leaf:$$2 \cdot (n+1) - \operatorname{count\_ones}(n+1) - (2 \cdot n - \operatorname{count\_ones}(n) = 2 + \operatorname{count\_ones}(n) - \operatorname{count\_ones}(n+1)$$This formula looks good, however, it can be simplified further. Let's take a closer look at binary representation of numbers $n$, $n+1$ and their number of ones.

Because of how binary addition works, first bit will always flip:$$b_0 = 1 - a_0$$and $i$-th bit flips only if all bits from $0$ to $i-1$ are $1$:$$b_i = \begin{cases} 1-a_i & \text{if $\; \forall_{j<i} \, a_j=1$} \\ a_i & \text{otherwise} \end{cases}$$Let's define $t$ such that $$a_t = 0 \text{ and } \forall_{i<t} a_i = 1$$Now we can notice that only bits from $0$ to $t$ will flip. Moreover, bit $t$ will flip from $0$ to $1$ and all bits from $0$ to $t-1$ will flip from $1$ to $0$. Also notice that $t$ is the number of trailing $1$ bits in $n$.

So now we can simplify the formula:$$\operatorname{count\_ones}(n+1) - \operatorname{count\_ones}(n) = 1 - \operatorname{trailing\_ones}(n)$$$+1$ comes from flipping the $t$-th bit and $-\operatorname{count\_ones}(n)$ from flipping all bits from $0$ to $t-1$.

After plugging this into the formula, we get:$$2 - (1 - \operatorname{trailing\_ones}(n)) = 1 + \operatorname{trailing\_ones(n)}$$