Decorator to get position of the first/last non-empty element of a merkle tree. about miden-vm

[hackaugusto]

One possible design is to have the target position of the element on stack and the Merkle tree root:

Stack: [el_pos, tree_root ...]

And the decorator would push the leaf position to the advice stack.

The Advantage of the above is that a single decorator supports not only the first/last position, but also arbitrary values in-between. The disadvantage is that to get the position of the last element either the number of elements must be known, or a magic value needs to be used.

[bobbinth]

I'd probably go for the simpler approach for now as figuring out the correct position will be quite complicating, I think.

A couple things to clarify:

• We probably want to return both the index and the depth as zero nodes could theoretically be located at different depths in different parts of the tree.
• What should we return if there are no zero nodes in the tree?

[hackaugusto]

correct position will be quite complicating, I think

It should be easy:

container.inner_nodes().filter(|n| n.is_leaf()).nth(index)

The complexity is basically O(n) where n is the number of leaves.

What should we return if there are no zero nodes in the tree?

Undefined? We can easily check if the tree is empty by looking at the root value.

[bobbinth]

It should be easy:

container.inner_nodes().filter(|n| n.is_leaf()).nth(index)

Not sure this will work as in the MerkleStore the order of nodes is not defined.

What should we return if there are no zero nodes in the tree?

Undefined? We can easily check if the tree is empty by looking at the root value.

Comparing against empty tree root in MASM would require comparing words. I think we we return a well-defined value for empty trees we can make it more efficient (i.e., need to compare only single element).

Assuming, this decorator puts (depth, index) on the top of advice stack, we could say that (0, 0) means that the tree is empty. Or maybe just returning depth=0 is good enough.