Introduce PCALL operation in TransactionKernel

[frisitano]

Overview

The PCALL operation was recently implemented in miden-vm. This allows for dynamic execution of CodeBlocks by positioning the hash of a CodeBlock at the top of the stack and executing the dynexec or dyncall instructions. The CobeBlocks must be made available as part of the Programs CodeBlockTable provided to the Processor.

Implications

The dynamic call instruction is of particular interest for the transaction kernel as it allows for notes and the transaction script to be invoked dynamically at runtime as opposed to the current requirement of having them specified at compile time. This is beneficial for two reasons:

• The transaction kernel program will always have the same hash regardless of the inputs. This means the batch kernel will not have to compute the hash for each transaction program as they will always be the same (this is dramatic efficiency improvement).
• For client side proven transactions the clients will not need to provide the hash of the note scripts and transaction scripts that they have included in their transaction, ultimately resulting in a higher level of privacy. However, we may still want to enforce this requirement at the node level for testnet.

Implementation

We should introduce an internal masm module named main or note_processing. This will be responsible for looping over all notes, running the note setup script, loading the note script hash onto the top of the stack and invoking the dyncall instruction. We also need to modify the TransactionCompiler to account for the changes in the kernel.

Note Inputs

We currently read the 16 input values as part of the note setup script such that the inputs are provided as the top 16 elements on the stack when the note script is invoked. The introduction of the dynamic call instruction complicates this as the top 4 elements need to be the hash of the note script. Ultimately this limits the number of inputs for the note to 12. However, we can consider ways in which we can address this. Firstly, there are changes that can be make to the semantics of the dyn* instructions - a proposal has been made here. An alternative approach is to change the way in which note inputs are provided to the note scripts. We can introduce a pattern which is similar to the way in which we read assets from notes. Instead of providing the note inputs as elements of the stack when the note script is invoked, we can introduce a kernel procedure - get_note_inputs_hash, as well as a public facing procedure which will unhash the note inputs and read them to a specified region of memory. This would also allow us to support a dynamic number of note inputs however we probably need to consider the implications here as we don't want state bloated with note inputs.

Transaction Script

We may need an authenticated mechanism to provide the transaction script hash to the transaction kernel. This should be done via providing either the transaction script hash or a commitment to the transaction script hash. Currently the stack is initialised as: [BH, acct_id, IAH, NC] where BH is the block hash, acct_id is the account id, IAH is the initial account hash and NC is the nullifier commitment. This equates to a total of 13 elements where the limit is 16. We need four elements to provide the transaction script which we currently do not have capacity for. An option we have here is to introduce an additional layer of indirection by defining TX_INPUT = hash([0,0,0,acct_id, IAH, NC, TXSR]) where TXSR is the transaction script root. The stack would then be initialised as [BH, TX_INPUT] and the transaction inputs would be provided via the advice provider.

An alternative would be to remove the acct_id from the global inputs and just use the IAH as a proxy commitment to the acct_id. The stack could then be initialised to [BH, IAH, NC, TXSR].

However, from the protocol perspective it is irrelevant what transaction script has been executed, it only cares that it was executed correctly. As such we do not necessarily need a commitment to the transaction script at the protocol layer (via stack inputs). Instead we could delegate this to the transaction authorisation procedure, i.e. the user would sign on a message of the form TX_INPUT = hash([0,0,0,acct_id, IAH, NC, TXSR]).

[bobbinth]

Thank you! This captures all the aspects that I was thinking about. To address a couple specific points:

An alternative approach is to change the way in which note inputs are provided to the note scripts. We can introduce a pattern which is similar to the way in which we read assets from notes. Instead of providing the note inputs as elements of the stack when the note script is invoked, we can introduce a kernel procedure - get_note_inputs_hash, as well as a public facing procedure which will unhash the note inputs and read them to a specified region of memory. This would also allow us to support a dynamic number of note inputs however we probably need to consider the implications here as we don't want state bloated with note inputs.

I agree with this approach. I think it gives us more flexibility and "stability" (i.e., we won't have to refactor as much going forward). There is a slight performance degradation but:

1. We may be able to avoid most of it if we "unhash" the inputs only when requested by the note script.
2. Even if we need to "unhash" them twice, the overhead is not that big.

A natural question is whether we should put an upper limit on the number of inputs. I think here we can do the same as with assets: limit the number to 256 (this way, we can record the number in a single byte). This limits the maximum size of note inputs to 8KB - which I think is fine as I think in most cases it'll probably be way less than that.

Another question is where to put the number of inputs. We could do something similar to what we do with the number of assets - i.e., put it into note metadata. But I'm actually having second thoughts about having number of assets be a part of public info in the first place. So, if there is a good way to handle the number of inputs differently, we can do it now. Or if it is simpler, we could treat them similarly to the number of assets, and then refactor our handling of both as a separate task.

We may need an authenticated mechanism to provide the transaction script hash to the transaction kernel. This should be done via providing either the transaction script hash or a commitment to the transaction script hash. Currently the stack is initialised as: [BH, acct_id, IAH, NC] where BH is the block hash, acct_id is the account id, IAH is the initial account hash and NC is the nullifier commitment. This equates to a total of 13 elements where the limit is 16. We need four elements to provide the transaction script which we currently do not have capacity for. An option we have here is to introduce an additional layer of indirection by defining TX_INPUT = hash([0,0,0,acct_id, IAH, NC, TXSR]) where TXSR is the transaction script root. The stack would then be initialised as [BH, TX_INPUT] and the transaction inputs would be provided via the advice provider.

An alternative would be to remove the acct_id from the global inputs and just use the IAH as a proxy commitment to the acct_id. The stack could then be initialised to [BH, IAH, NC, TXSR].

There is a 3rd option: to put TXSR onto the output stack. I believe currently we use only 8 elements (for created not commitments and final account hash) - so, we should have enough space there.

If the above doesn't work for some reason, I'd prefer the approach with crating TX_INPUT over the one with using IAH as a proxy commitment to the account ID. The main reason is that we'll need to send account ID with the transaction anyway (so that the operator knows which account is being updated), and if we don't include it as a separate input, we'll need to provide other parts of IAH so that operator could confirm that the ID is valid.

However, from the protocol perspective it is irrelevant what transaction script has been executed, it only cares that it was executed correctly. As such we do not necessarily need a commitment to the transaction script at the protocol layer (via stack inputs). Instead we could delegate this to the transaction authorisation procedure, i.e. the user would sign on a message of the form TX_INPUT = hash([0,0,0,acct_id, IAH, NC, TXSR]).

This is an interesting idea - but probably needs a bit more consideration. Signatures are expensive and we may not need them in all contexts. So, we'll need to think through various scenarios here.

Last thing I wanted to mention, as a part of this, we'll also need to update a couple of standard note scripts that we already put together as they currently expect the inputs to come from the stack.

[frisitano]

I agree with this approach. I think it gives us more flexibility and "stability" (i.e., we won't have to refactor as much going forward). There is a slight performance degradation but:

1. We may be able to avoid most of it if we "unhash" the inputs only when requested by the note script.

This is the idea - we only unhash the inputs if they are requested. We do not unhash them in the prologue - only the inputs hash is relevant in the prologue. As such I don't think the performance degradation will be that significant.

A natural question is whether we should put an upper limit on the number of inputs. I think here we can do the same as with assets: limit the number to 256 (this way, we can record the number in a single byte). This limits the maximum size of note inputs to 8KB - which I think is fine as I think in most cases it'll probably be way less than that.

Yes, I think this is a reasonable limit.

Another question is where to put the number of inputs. We could do something similar to what we do with the number of assets - i.e., put it into note metadata. But I'm actually having second thoughts about having number of assets be a part of public info in the first place. So, if there is a good way to handle the number of inputs differently, we can do it now. Or if it is simpler, we could treat them similarly to the number of assets, and then refactor our handling of both as a separate task.

I don't think this is a problem. When we read the the inputs from the advice provider, the first element of the advice provider input can define the number of inputs words. I will proceed with the implementation. I think the same approach can be taken for the note vault, we do not need the number of assets to be part of the public info. I will create an issue to refactor the note vault implementation as a separate unit of work. Created #281

There is a 3rd option: to put TXSR onto the output stack. I believe currently we use only 8 elements (for created not commitments and final account hash) - so, we should have enough space there.

Good call, lets go with this solution.

Last thing I wanted to mention, as a part of this, we'll also need to update a couple of standard note scripts that we already put together as they currently expect the inputs to come from the stack.

Noted, thanks for the heads up.

[frisitano]

We have a challenge in terms of allowing the number of note inputs to be dynamic and using the advice provider to provide the number of input words. The challenge arises from the fact that for a naive solution, when we have an odd number of input words we would pad with an empty word to get an even number of words when computing the inputs hash. The problem here is that we would get the same hash when the prover suggests there is n input words, where n % 2 = 1 and also when the prover says there is n + 1 input words (with an empty final word). I think we would need to implement the more robust hashing scheme which handles this case as implemented here. I think this concern will also hold true for the note vault if we want to remove the number of assets from the NoteMetadata. It is easier to check if it an assert is valid in a note script but we should do this at the protocol layer.

For the first draft of this PR I will migrate to the pattern where we fetch the inputs via a kernel procedure, however I will keep it to the current standard of 4 input words. We can then decide if we want to address dynamic inputs as part of this PR or a follow up.

One option is to enforce that note inputs must be an even number however we probably still need to address hashing of the note vault and as such we can reuse the same solution which means we would not have to place such a restraint on the note inputs.

[bobbinth]

Closed by #283.