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 摘要。