0xPolygonMiden/miden-base

Refactor account storage to use sequential hash rather than a Merkle tree

Closed this issue · 1 comments

Once #667 is closed, account tree will be converted to a sequential hash. We should do something similar for the storage tree as well.

Basically, instead of using a fixed depth 8 Merkle tree to commit to storage slots, we could use a sequential hash for this. Then, in the prologue, we'd "unhash" the commitment and save all storage slots into kernel memory. The benefits of this are:

  • Access to storage slots would be much more efficient in most cases. That is, instead of proving a Merkle path of depth 8 on every access, we'd just update the relevant slot directly in kernel memory.
  • The actual number of storage slots can be variable - i.e., some accounts could need only a few storage slots, while others may need a lot. We can even go beyond limiting the number of slots to 256 - though, not sure that's needed.
  • The layout of the storage does not need to be fixed upfront. This will make it easy to add new storage slots for to updatable accounts.
  • Rust code for AccountStorage should become simpler.

The main downside is that we will need to spend some cycles in the prologue and epilogue to "unhash" and "hash" the storage slots - but I think this cost should be negligible in most cases.

Implementation details

The commitment to account storage could be defined as a sequential hash of storage slots. Each slot would be defined by a tuple (slot_value, slot_type). Since a slot type only requires 1 field element, we'll pad it with 3 ZERO elements to make sure it takes exactly 1 permutation to absorb 1 storage slot into the hasher state. Account storage commitment can the be computed as:

hash(SLOT1_VALUE || [slot1_type, ZERO, ZERO, ZERO] || SLOT2_VALUE || [slot2_type, ZERO, ZERO ZERO] ... ) 

The above implies that when we unhash storage slots in memory, type information will be right next to the value, and so, it would be very easy to check if the access is being done correctly (e.g., we are not trying to treat a simple slot like a storage map).

On the Rust side, the AccountStorage struct could be redefined as follows:

pub struct AccountStorage {
    slots: Vec<StorageSlot>,
}

pub enum StorageSlot {
    Value(Word),
    Array(StorageArray), // we don't have this yet
    Map(StorageMap),
}

Structs like StorageSlotType and SlotItem will no longer be needed.

This design also implies that we don't need to have a dedicated storage slot for storage layout. So, for regular accounts, there will be no reserved slots.

We still, however, will need a reserved slot for faucet accounts (to track already issues assets). This could always be slot 0.

Closed by #846.