perfect-merkle-forest

We arrange the elements of the accumulator into a forest of perfect binarytrees with the largest tree on the left and smallest on the right. This arrangement allows for a more intuitive visualization of trees merging and splittingwhen needed. Row operations are also possible where elements can movebetween sub-trees.

As the trees in the forest are always perfect, they hold 2^h leaves, whereh is the height of the tree. Any natural number of leaves can be organizedinto a forest of perfect binary trees, just as any natural number can berepresented by a sum of powers of two. This relation provides a convenientshortcut: the number of trees in the accumulator is the number of 1-bits inthe binary representation of the number of leaves. The heights of those treesis the bit-position of the 1-bits in that representation. For example, a forestwith 133 leaves would have 3 trees: a height 7 tree, a height 2 tree, and aheight 0 tree. This is quickly visible by looking at the binary representationof the number 133: 10000101.

Any set of leaves can be grouped into binary trees using this method. Inall cases, it is possible to add one more leaf to the forest knowing only theroots of each tree. In the 133 leaf example, adding an extra leaf would resultin 134 leaves, with a binary representation of 10000110. The 0-height tree(which itself is a leaf) would combine with the newly added leaf to create a1-height tree with 2 leaves. A further addition to 135 would then create a0-height tree with the additional leaf.

• Thaddeus Dryja, Utreexo paper