Alternatives to TSMT about miden-vm

[bobbinth]

Perhaps the depth of the single tier TSMT could be parameterised.

Setting the depth much smaller than 64 could become a significant attack vector (at least if we keep colliding keys in a sorted list). The main factor is the cost of generating key collisions. I estimate that with RPO, finding a 64-bit pre-image probably costs many million dollars (probably north of $100M) and so the cost of generating more than a few hundred keys with the same 64-bits prefix as some existing key is prohibitively expensive - even in the medium term.

16-bit (and even 32-bit) pre-images are pretty easy to find though. So, this opens up various attack vectors (e.g., someone could make accessing a specific key in account storage prohibitively expensive). I'm sure these can be worked around, but it does require users to be aware of these edge-case behaviors and is probably undesirable.

[Dominik1999]

Do you think it makes sense to wait for that until we have a first testnet?

[plafer]

My 2 cents re: complexity. I will not touch on whether applying these suggestions would make using TSMT still useful.

I don't think the data structure is fundamentally too complex; i.e. it is relatively simple to explain, and understand how it works at a high level. I believe there are 2 low-hanging fruits to reduce the accidental complexity of the current implementations:

1. Refactor the Rust code

• There are certain patterns that are unintuitive and could lead to bugs, that could simply be refactor out. For example, the ValueStore::get_first(prefix) method is typically used in conjunction with the leaf_exists output of NodeStore::get_proof(), such as here. get_first(prefix) in theory could return an entry from another node, but if we get information from elsewhere that a leaf exists at index, then both methods in conjunction end up giving the key/value stored at some leaf. I would vote for a refactor where there's a single method along the lines of get_key_value_at_leaf(leaf_index) to get that information.
• Define more newtypes (across the codebase) instead of using RpoDigest for key, account hash, and many more that I currently can't think of off the top of my head.
• Better naming, as captured in 0xPolygonMiden/crypto#208

2. Properly document the behavior and non-deterministic inputs of the MASM stdlib functions

• Specifically, it would be good to not only know how the advice map and Merkle store need to be loaded, but provide an explanation of how these are used internally.

[frisitano]

The simplest alternative

Perhaps the simplest alternative is to reduce the number of tiers in TSMT to just one (at depth 64). This would make it almost equivalent to the [SimpleSmt]

Perhaps the depth of the single tier TSMT could be parameterised. The depth of the TSMT would be use case specific i.e. for account vaults we would use a single tier TSMT of depth 16 (or maybe even less), for account and nullifier db's we would have a TSMT of depth 64. For account storage it would be the responsibility of the user to specify the depth of the TSMT as part of the type information.

Alternative with 2 tiers

We could also reduce the number of tiers to 2 - at depth 32 and 64 (or 16 and 64). This would not be as simple as the previous approach, but also, would be much more efficient for trees containing a small number of values.

Similarly we could paramaterise the depth of the upper tier in the 2 tier construction.

I'm in favour of a single tier TSMT with parameterisable depth as through the depth configurability it gives a good balance between performance and simplicity for many use cases.