# Merkle Expansions in BOLD

In the BOLD implementation, we have a data structure called a "Merkle expansion" that is quite confusing but used for the purpose of representing commitments to some list of hashes in a compact way, and for verifying that some commitment of hashes is a **prefix** of another commitment. This can be done by providing a Merkle expansion to some list of hashes A, and another B, and proving that A is a prefix of B.

Some terminology:
- **level**: Refers to the distance from the leaves layer to a node in the tree. The leaves are at level 0, their parents at level 1, and so on
- **complete subtree**: no nodes with one child

The tree below is a complete tree because every level, is fully filled. All nodes are as far left as possible.

          ROOT
         /    \
       AB      CD
      /  \    /  \
     A    B  C    D

### Merkle Expansion

A Merkle expansion is a data structure that represents trees above in a compact manner. It represents the tree in an array where each **index** corresponds to a **level** in the tree. For the tree above, we will compute the root of the complete tree, and represent it as compactly as possible. We can represent it as `ROOT`, because it is complete. We do not need to store A, B, C, or D, or its parents, because they give us all the information we need to compute a complete root.

expansion = []
append(expansion, A) -> [hash(A)]
append(expansion, B) -> [0, hash(A, B)]
append(expansion, C) -> [hash(C), hash(A, B)]
append(expansion, D) -> [0, 0, hash(hash(A, B), hash(C, D))]

### Lopsided Trees

Now, let's say we want to add `E` into our expansion. We will end up with something like this:

             NEWROOT
            /       \
          ABCD       E000
         /    \        /     \
       AB      CD       ..E0.  00
      /  \    /  \     / \
     A    B  C    D   E  0  0  0

ABCD is a complete subtree, but whatever is on E's side is not, so our merkle expansion looks something like this:

``[hash(E), 0, hash(ABCD, E000)]``

as E is a complete subtree by itself at lvl 0, at lvl 1 we have no complete subtree, and at lvl 2 we have a complete subtree in ABCD