feat(collections): implement LookupMap and TreeMap

[testinginprod]

Context

In order to make the SDK provable, the assumptions we need to make around storage or the underlying commitment structure need to be smaller.

Currently all the modules assume that the underlying KV can:

• Get
• Set
• Remove
• Iterate

But it should not always be a given that the underlying storage can iterate. And it should not be a given that when iteration happens the underlying commitment structure can prove the iteration range (RangeProofs).

Also not all modules need iterations by default. Iteration is always needed for genesis, but it is not always required for the module to execute its own state transitions.

In order to reduce the assumption around state storage to be:

• Get
• Set
• Remove

And in order to reduce the assumptions around commitment structure to be:

• ProveExistence
• ProveNonExistence

We propose to introduce two new collections types:

LookupMap

LookupMap is like a Map[K, V] but is not iterable.

In order to implement this, it should be sufficient to take (literal copy paste) the collections.Map code and remove the following methods:

• Iterate
• Walk
• Clear

TreeMap

TreeMap is like a LookupMap  but provides ordered iteration. It builds an iterable (ordered) tree on top of the KV.

We can find an example here: https://docs.rs/near-sdk/latest/src/near_sdk/collections/tree_map.rs.html#42

[alexanderbez]

SGTM!

[kocubinski]

I think this abstraction makes sense to support other commitment types. For the current status quo in the SDK (IAVL) TreeMap could just be a pass through.

[robert-zaremba]

I'm very familiar with the Near data model, and honestly, I think that removing "native" iterations is a premature abstraction. It's a clear overhead for map structure which requires prefix scan or ordered scan. The TreeMap is done by implementing AVL structure of the KV store. So, here it would either be AVL over IAVL (sic!), or AVL over KV when we have SS (which usually is also a sort of a tree).

[robert-zaremba]

I think the proposal can be implemented as "optional", but we should still keep the current model, so module developers an use the existing assumptions like efficient prefix scan, which is often used!

[tac0turtle]

I think the proposal can be implemented as "optional", but we should still keep the current model, so module developers an use the existing assumptions like efficient prefix scan, which is often used!

We won't be removing the current design as state migrations would be horrendous. If chains or modules want to be more efficient in proving they will need to do something like this.