0xPolygonMiden / miden-base

Core components of the Polygon Miden rollup
MIT License
61 stars 34 forks source link

Add support for storage array #383

Open bobbinth opened 6 months ago

bobbinth commented 6 months ago

In #307 and #310 we implemented basic new account storage structure described in https://github.com/0xPolygonMiden/miden-base/issues/239#issuecomment-1791479475. Specifically, we have support for value types but not for maps or arrays.

We need to add support for arrays as well. This would make storage more efficient and flexible for use cases where a small-sh number of items needs to be index-accessible.

To support this on the kernel side, we need to add two procedures to the kernel API:

#! Inputs:  [slot, index, ...]
#! Outputs: [VALUE, ...]
#!
#! Fails if the slot contains a simple value or a storage map.
export.get_array_item

#! Inputs:  [slot, index, VALUE, ...]
#! Outputs: [OLD_VALUE, ...]
#!
#! Fails if the slot contains a simple value or a storage map.
export.set_array_item

We also need to add support for maps to AccountStorage as well as DataStore trait in miden-tx. The backing data structure for this is probably going to be Simple SMT.

Dominik1999 commented 2 months ago

For this PR, you should be able to follow the PR about StorageMaps https://github.com/0xPolygonMiden/miden-base/pull/521

bobbinth commented 2 months ago

One potentially tricky thing would be to figure out which Rust struct to use as the "backing" type. We may not be able to use SimpleSmt for this because the depth parameter is generic. So, we may need to create a new struct for this in miden-crypto.