BaseTree

Git Source

BaseTree is a struct representing incremental merkle tree.

  • Contains only the current branch.
  • The number of inserted leaves is stored externally, and is later supplied for tree operations.
  • Has a fixed height of ORIGIN_TREE_HEIGHT.
  • Can store up to 2 ** ORIGIN_TREE_HEIGHT - 1 leaves.

Note: the hash function for the tree H(x, y) is defined as:

  • H(0,0) = 0
  • H(x,y) = keccak256(x, y), when (x != 0 || y != 0)

Invariant for leafs

  • The leftmost empty leaf has index == count, where count is the amount of the inserted leafs so far.
  • Value for any empty leaf or node is bytes32(0).

Invariant for current branch

branch[i] is always the value of a node on the i-th level. Levels are numbered from leafs to root: 0 .. ORIGIN_TREE_HEIGHT. branch[i] stores the value for the node, such that:

  • The node must have two non-empty children.
  • Out of all level's "left child" nodes with "non-empty children", the one with the biggest index (the rightmost one) is stored as branch[i].

branch could be used to form a proof of inclusion for the first empty leaf (index == count). Here is how:

  • Let's walk along the path from the "first empty leaf" to the root.
  • i-th bit of the "first empty leaf" index (which is equal to count) determines if the path's node for this i-th level is a "left child" or a "right child".
  • i-th bit in count is 0 → we are the left child on this level → sibling is the right child that does not exist yet → proof[i] = bytes32(0).
  • i-th bit in count is 1 → we are the right child on this level → sibling is the left child sibling is the rightmost "left child" node on the level → proof[i] = branch[i].

Therefore proof[i] = (count & (1 << i)) == 0 ? bytes32(0) : branch[i])

struct BaseTree {
    bytes32[ORIGIN_TREE_HEIGHT] branch;
}