Expand description


Incremental Merkle Trees are fixed-depth Merkle trees with two primary capabilities: appending (assigning a value to the next unused leaf and advancing the tree) and obtaining the root of the tree. Importantly the tree structure attempts to store the least amount of information necessary to continue to function; other information should be pruned eagerly to avoid waste when the tree state is encoded.


Merkle trees are typically used to show that a value exists in the tree via an authentication path. We need an API that allows us to identify the current leaf as a value we wish to compute authentication paths for even as the tree continues to be appended to in the future; this is called maintaining a witness. When we’re later uninterested in such a leaf, we can prune a witness and remove all unnecessary information from the structure as a consequence.

Checkpoints and Rollbacks

The structure is not append-only in the strict sense. It is possible to identify the current state of the tree as a “checkpoint” and to remove older checkpoints that we’re no longer interested in. It should be possible to roll back to any previous checkpoint.


  • A space-efficient implementation of the Tree interface.


  • A type-safe wrapper for indexing into “levels” of a binary tree, such that nodes at altitude 0 are leaves, nodes at altitude 1 are parents of nodes at altitude 0, and so forth. This type is capable of representing altitudes in trees containing up to 2^255 leaves.
  • A type representing the position of a leaf in a Merkle tree.


  • A possibly-empty incremental Merkle frontier.
  • A trait describing the operations that make a value suitable for inclusion in an incremental merkle tree.
  • A Merkle tree that supports incremental appends, witnessing of leaf nodes, checkpoints and rollbacks.