stdlib: procedure to check if a given merkle path corresponds to the first/last element of a tree

[hackaugusto]

# Input: [leaf_pos, sibling_hash*, ...]
# Output: [bool, ...]
export.is_first
  # ...
end

Rough algorithm for is_left:

# go up the tree while the node is the left leaf
while leaf_pos != 0 and is_leaf(leaf_pos):
  go_up(leaf_pos)

# go up the tree and check every hash corresponds to this depth empty hash 
while leaf_pos != 0:
  # if not an empty hash, then there is another value in a lower index
  if !is_empty_hash(depth(leaf_pos)):
    return false

# if reach the root, then this was the left-most element of the tree
return true

Context: https://github.com/0xPolygonMiden/crypto/issues/170

[bobbinth]

I think this approach may be prohibitively expensive for trees of meaningful depth (e.g., depth > 10). A more efficient, though probably a more complicated approach is not to traverse all possible nodes but look at subtree roots. If we have a root of an empty subtree, we can be sure that all leaf nodes should be zeros.

[hackaugusto]

That is the proposal, this is only walking up the tree and checking the hash of the subtrees (i.e. only checking a merkle path), so the complexity here is O(n) where n is the depth of the tree.

[bobbinth]

Ah - I missed that! Makes sense.