0xMiden / 0xMiden/protocol

Add support for multi-value storage slots

未关闭
#2,176 14 条评论 1 个 reaction 已指派 0 人 在 GitHub 查看
kernels rust
主要语言
Rust
星标
132
派生
167
平均合并
1 天 23 小时
30 天内合并 PR
110

描述

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.

贡献指南

打开贡献指南

评估

这个 Issue 还没有评估数据。

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。