Support tree operation on mixed tree types

[hackaugusto]

The virtual machine has the following instructions: mtree_get, mtree_set. These instructions use the tree's root to identify the target tree of the operation.

That means it is possible to write code that runs mtree_get in a tree backup by a Merkle Mountain Range, and mtree_set the data into a Simple Merkle Tree.

The open questions are, which combinations of trees and operations should be supported?

• column is write target
• row is read target

	Sparse Merkle Tree	Merkle Mountain Range	Simple Merkle Tree
Sparse Merkle Tree	x
Merkle Mountain Range	?	x
Simple Merkle Tree	?	?	x

Note: This is not important for mtree_cwm since we can assume the resulting copy has the same type, i.e. the instruction does not have a way to change the resulting tree type. This could in theory be modified by the VM's advice provider though.

[hackaugusto]

I think that supporting the operations as defined in this issue is not useful. Here is why:

• Sparse Merkle Tree leaves have their position determined by their value, this is not the case for the other trees, so we can't get a leaf and its path from one tree and insert into another and expect anything but the leaf value to be the same. I.e. the node depth, position, and the merkle path all have to change.
• The Merkle Mountain Range has has invariants to the internal nodes. The height and which elements are hashed is predetermined. So here too one can't assume the level, depth, or path from one tree can be used in the other.

What does make sense to me is to copy a leaf from one tree and insert into another, but that requires computing the equivalent depth/index on the target's tree. It could also be useful to support copying all the leafs of one tree, and creating a tree of another type with these leaves. This would be useful for protocol upgrades.

[grjte]

I think this issue may be superseded by the new discussion about the MerkleStore (https://github.com/0xPolygonMiden/crypto/issues/89) and maybe the points you've raised should be moved in there. Wdyt?

[hackaugusto]

@grjte I think this is still relevant. #89 can only do one of the two:

1. Define a shared trait for all the data structures, since they can all be viewed a some type of tree
2. Define a shared storage for all the tree implementation we have

However, the things above doesn't change the invariants we want from these data structures.

For example, the simple merkle tree must have a power-of-two number of leaves, and the tiered sparse merkle tree may only have leaf set at specific heights, it happens to be the case that a tiered tree is also a perfectly balanced tree with a power-of-two number of leaves, so we can copy an element from that into a simple merkle tree, that should always be valid, but we can only copy elements form the simple merkle tree on very special cases, namely when the power-of-two number of leaves happen to require a simple merkle tree with a depth that matches a tier in the tiered version.

There is an additional requirement that we have to keep in mind when laying out the operations, namely which operations have to be supported in the VM. For the Rust side of things this is just about implementing TryInto traits.

[hackaugusto]

closing this. the merkle store allows arbitrary operations, validation is outside of the scope.