Add support for multi-value storage slots
- Dominant language
- Rust
- Stars
- 132
- Forks
- 167
- Avg merge
- 1d 23h
- Merged PRs (30d)
- 110
Description
Currently, we have two types of storage slots: a single-value slot and a storage map. These can over most cases, but quite frequently a need for a storage slot the can hold multiple words comes up. A few examples of these are:
- Multisig accounts where we may want to store multiple keys in a single slot. Currently, we use storage maps for these, but this is rather inefficient.
- Storing Keccak or other hashes that don't neatly fit into a single word.
- Small, fixed-size data structures like queues or small arrays.
The design for multi-value slots was envisioned from the very beginning (see [here](https://github.com/0xMiden/miden-base/issues/239#issuecomment-1791479475)), but we've never gotten around implementing them (since we didn't really need them). Now, we may have gotten to the point where introducing such slots would be desirable.
To introduce such slots, we'll need to make updates on both the Rust side and the transaction kernel. Specifically:
#### Storage content changes
One of the things we'll need to change on the Rust side is the definition of the `StorageSlotContent`. The updated version could look something like this:
```rust
pub enum StorageSlotContent {
Value(Word),
List(StorageList), // this is the new variant
Map(StorageMap),
}
pub struct StorageList {
values: Vec,
commitment: Word,
}
pub enum StorageSlotType {
Value = Self::VALUE_TYPE,
List(u8) = Self::LIST_TYPE, // the internal value specifies list length
Map = Self::MAP_TYPE,
}
```
We can set the maximum length of the `values` vector to something like 256.
#### Kernel changes
In the transaction kernel, we'll need to decide how to encode storage slot type. We could make it a part of the `type` element, or we could allocate the currently unused element to track the number of elements. The latter option would look like this:
```
[[num_elements, slot_type, slot_id_suffix, slot_id_prefix], SLOT_VALUE]
```
We will also need to define new kernel procedures for reading and writing list types. These could look like so:
```
#! Writes the list located at the specified storage slot to the specified location in memory.
#!
#! Inputs: [slot_id_prefix, slot_id_suffix, ptr]
#! Outputs: [num_items]
pub proc get_list
...
end
#! Writes the list located at the specified memory pointer into the specified storage slot.
#!
#! Inputs: [slot_id_prefix, slot_id_suffix, ptr]
#! Outputs: [num_items]
pub proc set_list
...
end
#! Returns the number of items in the list located in the specified storage slot
#!
#! Inputs: [slot_id_prefix, slot_id_suffix]
#! Outputs: [num_items]
pub proc get_list_num_items
...
end
```
Unlike the current map and value slots, accessing list items would be done through memory - i.e., the `get_list` procedure would write all the contents of the list to memory (e.g., using the `pipe_preimage_to_memory` procedure) and the `set_list` procedure would hash the entire list (e.g., using the `hash_words` procedure) and save the resulting commitment into the storage slot.
#### Storage delta changes
Another thing that we'll need to update is how we track storage deltas. Instead of tracking the full list, we'd probably need to track something like `(item_index, new_value)` for all changed items (where each item would be a word). Doing this in Rust is probably going to be pretty easy, but MASM changes may be quite involved.
------
Once we have multi-value slots, we can re-evaluate the need for [Storage Arrays](https://github.com/0xMiden/miden-base/issues/383). We may still choose to implement them for list of data that are very large (e.g., greater than 256 words), but I think the priority of storage arrays would be quite a bit lower.
Contributor guide
Assessment
This issue has not been assessed yet.