Implement offset-based storage access

[bobbinth]

For more context see https://github.com/0xPolygonMiden/miden-base/issues/550#issuecomment-2094666725.

For any storage access (i.e., via account::get_item, account::set_item, account::get_map_item, and account::set_map_item) we should apply an offset based on which procedure is trying to access the item. For this, we should do two things:

1. Change the format of the account code tree. Specifically, each leaf in that tree should be a tuple (procedure_root, storage_offset) instead of the current procedure_root. We should also consider changing moving away from using a Merkle tree here in favor of using a simple sequential hash.
2. Introduce authenticate_storage_access procedure which would look like so:

#! Verifies that the procedure root is part of the account code Merkle tree and applies the offset
#! associated with this procedure to the provided slot index.
#!
#! Panics if the procedure root is not part of the account code Merkle tree or if the computed slot
#! index is greater than the maximum storage slot index.
#!
#! Stack: [PROC_ROOT, slot_index]
#! Output: [PROC_ROOT, offset_slot_index]
#!
#! - PROC_ROOT is the hash of the procedure to authenticate.
export.authenticate_storage_access

The current maximum slot index varies between faucet and non-faucet accounts, but I think we should set it to be 250 for both.

Moving away from using a Merkle tree for account code mentioned in the item 1 above would mean that we'd "unhash" account code commitment during transaction prologue, and then would look up the relevant info in kernel memory (rather than in the Merkle tree). This would also affect authenticate_account_origin procedure and should make it more efficient.

[phklive]

Hello @bobbinth hoping that you are doing well, would be glad to have some clarifications regarding the following points:

Before going into questions I would like it if you could clarify the reason why we are implementing this offset-based storage access, I understand the implementation needs but not the reason of the implementation (benefits and why do we need it).

1. Where should the authenticate_storage_access proc live?
2. Most of the functions manipulating accounts take for granted the fact that the account procedure_tree is a tree hence we will need to refactor all these functions to be able to function with the data living is the advice provider considering the sequential hash, am I correct?
3. Could you point me towards where I could find the maximum slot index for the faucet and non-faucet accounts in order for me to set them to 250 I have not found it.
4. We would use RPO to build the sequential hash of the Vec<(proc_root, storage_offset)> right?

Thank you

[bobbinth]

Before going into questions I would like it if you could clarify the reason why we are implementing this offset-based storage access, I understand the implementation needs but not the reason of the implementation (benefits and why do we need it).

The reasoning for this was discussed in https://github.com/0xPolygonMiden/miden-base/issues/550 - but to summarize, without offset-based storage it is not clear how we can combine multiple code components in one account (a component could be some new functionality implemented by an account; for example, basic wallet is component, so is Falcon signature authentication).

Where should the authenticate_storage_access proc live?

It could be somewhere in tx-kernel's account module (basically close to get_item, set_item, get_map_item, and set_map_item procedure). But it may make sense to move these procedures into a separate module.

Most of the functions manipulating accounts take for granted the fact that the account procedure_tree is a tree hence we will need to refactor all these functions to be able to function with the data living is the advice provider considering the sequential hash, am I correct?

Which functions do you mean here? (I think there is only one function that does the authentication against the procedure tree).

Could you point me towards where I could find the maximum slot index for the faucet and non-faucet accounts in order for me to set them to 250 I have not found it.

These are implicitly defined by the following:

• SLOT_LAYOUT_COMMITMENT_INDEX says that slot 255 of the storage is used to store the storage layout.
• FAUCET_STORAGE_DATA_SLOT says that for faucet accounts slot 254 is used to store faucet-related data.

But I think we can change storage into a sequential hash as well and then we don't need to worry about maximum slot number. Would be a bit more work - but would be a much cleaner and more flexible design.

We would use RPO to build the sequential hash of the Vec<(proc_root, storage_offset)> right?

Correct. There will be two operations:

• In the prologue, we'd need to "unhash" the data into memory. We have procedures for this in Miden stdlib.
• In the epilogue, we'll need to compute the hash of the data in memory. I don't remember if we already have a procedure for this - but it should be fairly straightforward.

[bobbinth]

Closed by #763 and #843. The small remaining peace is described in #851.