Foreign procedure invocation

[bobbinth]

Currently, it is pretty easy to access the state of an account in a transaction when we are executing the transaction agains this account (I'll call such accounts "native" transaction account below). For this we expose get_account_item, get_account_map_item etc. procedures in the transaction kernel. Accessing states of other accounts is much more complicated. Currently, this would require:

1. Get a block header for the transaction (e.g., by using get_block_hash procedure and then "unhashing" the it into a block header).
2. Prove that account with a given state is in the account tree for of the block header.
3. Prove that specific storage items are in the storage of that account.

The 3rd item here is the most problematic because it requires the caller to understand the storage layout of the account they want to access, and if the storage layout changes, the code that access it would need to change as well.

Simplifying the above is important for things like oracles, but probably can be useful for many other types of applications. For example, it would allow note consumption conditions which are based not only on the target account state, but also on the state of other accounts in the chain. This proposal introduces a concept of "foreign procedure invocation" (FPI) which aims to address this.

Note: this proposal assumes no modifications to the Miden VM. If we could modify the VM, this can be made much more powerful (see the end of this post).

Invoking foreign procedures

From the user's point of view, we would add two new kernel procedures which would look something like this:

#! Tells the transaction kernel that we are about to execute a procedure on a foreign account.
#!
#! Panics if we are already in a foreign context.
#!
#! Inputs:  [foreign_account_id, ...]
#! Outputs: []
export.start_foreign_context

#! Tells the transaction kernel that we are done executing a procedure on a foreign account.
#!
#! Panics if we are not in a foreign context.
#!
#! Inputs:  []
#! Outputs: []
export.end_foreign_context

Then, to invoke a foreign procedure, we'd do the following:

push.<account id>
syscall.start_foreign_context
push.<foreign procedure root>
dyncall
syscall.end_foreign_context

But we can actually hide all of this behind a wrapper procedure (as we do for all other kernel procedures) which could look something like this:

#! Inputs:  [FOREIGN_PROC_ROOT, foreign_account_id ...]
#! Outputs: [<values returned from the foreign procedure>]
export.execute_foreign_procedure

And then the user would execute it as:

push.<account_id>
push.<foreign procedure root>
exec.tx::execute_foreign_procedure

Or, if the procedure is present in one of the linked libraries, we could use a procref instruction to get its root like so:

push.<account_id>
procref.foo::bar::baz
exec.tx::execute_foreign_procedure

Foreign procedure semantics

Any procedure exposed by an account can be invoked via FPI as long as it has no side effects or does not invoke another foreign procedure. This would exclude procedures which internally invoke procedures like:

1. set_account_item, set_account_map_item, account_vault_add_asset etc. as they modify the account state directly.
2. create_note and add_asset_to_note as they modify the state of a transaction.
3. Any procedure on the native account which would modify its state (i.e., account A calls a foreign procedure on account B, and then B calls a procedure back on account A).

Restriction 2 can be relaxed - but I would defer this to the future so that we reduce the complexity of the initial implementations.

Restriction 3 and ability to have nested FPIs may be relaxed in the future, but it would require changes to the VM mentioned at the end of this post.

Separately, we may consider adding a new procedure to the kernel - e.g., get_native_account_id (or maybe get_root_account_id). This procedure would return the ID of the "native" account (i.e., the account against which the transaction is being executed). If invoked not in a foreign procedure, this procedure would be equivalent to the get_account_id procedure. But maybe this should be a separate (pretty small) issue.

Handling foreign procedure invocations in the kernel

When start_foreign_context is called, the kernel would need to load and "unhash" the account data for the account specified by the provided ID. For this, we should normalize account data layout to look something like this:

This way, we could always allocate exactly 2048 words per account (padding in the above is included for future potential uses). Then, multiple accounts can be laid out as follows:

That is, the native account would be located starting at offset 2048 (instead of the current 400), then the first invoked foreign account would be located right after it etc.

Then, the start_foreign_context would do the following:

1. Check if a foreign account for the specified ID has already been loaded. If not, load its data (from the advice provider) into the next available account section and verify that the hash of this account's data against the account_root of the transaction.
2. Set the current_account_id and current_account_data_offset variable to the this account's ID and offset. These new variables would need to be added to the kernel's bookkeeping section.

The end_foreign_context procedure then would just reset the current_account_id and current_account_data_offset to the ID of the native account and 2048 respectively.

In addition to the above, we would need to update all procedures which access account state and can be called from the foreign context (e.g., get_account_item, get_account_map_item etc.) to read the offset of the account data section from the kernel's bookkeeping section rather than use constants. For procedures which cannot be called from the foreign context, we should add asserts to make sure they are executing against the native account.

Impact on other components

Ability to invoke foreign procedures requires that all the relevant data is available in the advice provider. For this, we'd need to modify both the client and the node. Here is a brief summary of the potential changes.

Client

On the client, we'd need to identify somehow that a transaction is making FPIs and request all the relevant data from the node. One way to do that is to modify the TransactionRequest struct to include information about potential FPIs (e.g., account IDs and maybe storage keys for potential storage accesses) and then have the client fetch the relevant information from the node for these accounts. This way, the creator of the transaction request would be responsible for providing this data.

The above should work for cases when the foreign account is public. In case the foreign account is private, the createor of a transaction request would need to load the data into the request's advice inputs directly. This may require also adding an optional block_ref field to the TransactionRequest struct.

cc @igamigo

Node

To support the above functionality on the client, we'd need to add an endpoint to the node to retrieve data for a specific account (assuming the account is public). The data we'd need to return is:

1. Account header (account ID, nonce, vault root, storage root, code root).
2. A Merkle path proving that this account is in the account database.
3. Account procedure infos (procedure roots + their storage offsets).
4. Account storage slot infos (slot value + slot type).
5. Account map items together with Merkle paths proving that the are in one of account's maps.
6. Account's assets.

Items 1 - 4 can always be returned as in the worst case it will be about 20KB of data (and usually much less). Item 5 should be optional - i.e., we return data only for the requested keys.

I'm not quite sure yet what to do with item 6. Returning all of account's assets may be quite expensive (if there are lots of assets in the account) - but also, not sure if there is a simple way to limited what should be returned. Maybe at first we don't return this data at all. This would limit FPI in that they won't be able to read account vault data - but maybe that's OK for now.

cc @Mirko-von-Leipzig.

Potential VM modifications

We can make the above scheme much more powerful if we allow using call instructions from inside syscalls in the VM. However, this would require some redesign of the decoder and the associated constraints. I think this should be possible but I haven't thought this through.

If we can enable this in the VM, the scheme above could be changed as follows:

1. We would not need separate start_foreign_context and end_foreign_context procedures and could put execute_foreign_procedure procedure directly into the kernel.
2. We would be able to allow nested FPIs (i.e., one foreign procedure could call a foreign procedure on a different account) this would make things very composable.
3. We would be able to allow calls from the foreign account back to the native account asking it to modify its state (e.g., a foreign procedure would be able to modify native account state in a similar way as a note or transaction script can).

These would make the protocol quite a bit more powerful. For example, we'd be able to have oracles where reading an oracle state would require paying a fee to the oracle account.

cc @plafer and @bitwalker

[Dominik1999]

One quick question:

We can always only prove / read that a given foreign account at state S has item i. What happens if the foreign account's state that we read it too old already? In the case of an oracle that could become relevant.

The transaction kernel knows the block it is executing against. But the transaction should be rejected by the Node if the block it is executed against is too old, right? This is already covered in #354, right?

[bobbinth]

We can always only prove / read that a given foreign account at state S has item i. What happens if the foreign account's state that we read it too old already? In the case of an oracle that could become relevant.

The transaction kernel knows the block it is executing against. But the transaction should be rejected by the Node if the block it is executed against is too old, right? This is already covered in #354, right?

Correct, #354 should address this - but I think we need to think it through a bit more (e.g., from the standpoint of the oracle use case). In that proposal, we can dictate recency conditions via note and transaction scripts - but is this sufficient?

For example, it allows us to make consumption of a note conditional on a recent state of the oracle. But I don't think it allows the same if we want to create a new note. One potential way to address this is to allow foreign procedures to dictate their own recency conditions - but we should probably discuss this in #354.