arber
arber is a Merkle-Mountain-Range (MMR) implementation.
The following description is taken from this excellent introduction.
Merkle Mountain Ranges [1] are an alternative to Merkle trees [2]. While the Merkle tree relies on perfectly balanced binary trees, Merkle Mountain Ranges can be seen either as list of perfectly balanced binary trees or a single binary tree that would have been truncated from the top right. A Merkle Mountain Range (MMR) is strictly append-only: elements are added from the left to the right, adding a parent as soon as 2 children exist, filling up the range accordingly.
This illustrates a range with 11 inserted leaves and total size 19, where each node is annotated with its order of insertion.
Height
3 14
/ \
/ \
/ \
/ \
2 6 13
/ \ / \
1 2 5 9 12 17
/ \ / \ / \ / \ / \
0 0 1 3 4 7 8 10 11 15 16 18
This can be represented as a flat list, here storing the height of each node at their position index of insertion:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
0 0 1 0 0 1 2 0 0 1 0 0 1 2 3 0 0 1 0
This structure can be fully described simply from its size (19).
🚧 arber is currently under construction - a hardhat is recommended beyond this point 🚧
[1] Peter Todd, merkle-mountain-range