Using `hperm` instead of `hmerge` when constructing the message for `auth_tx_rpo_falcon512`?

[Dominik1999]

In asm/eoa/basic.masm we use

# M = h(OUTPUT_NOTES_HASH, h(INPUT_NOTES_HASH, h(0, 0, 0, account_id, 0, 0, 0, nonce)))

hmerge hmerge hmerge

It is more efficient to use the hperm operation for sequential hashing. It would look something like this:

# prepare hasher capacity elements
padw 

# prepare first hasher rate word
exec.account::get_nonce push.0.0.0

# prepare second hasher rate word
exec.account::get_id push.0.0.0

# apply first permutation
hperm

# drop rate elements
dropw dropw

# prepare third hasher rate word
exec.tx::get_input_notes_hash

# prepare fourth hasher rate word
exec.tx::get_output_notes_hash

# apply second hasher permutation
hperm

# extract the digest (message)
dropw swapw dropw

This will give a different result to the hmerge method but it is a more efficient way of computing a message. We would also have to adjust the rust implementation accordingly.

However, I'm not sure if there was a specific reason to use hmerge here if thats a standard for constructing messages?

_Originally posted by @frisitano in https://github.com/0xPolygonMiden/miden-base/pull/294#discussion_r1387636140_

[bobbinth]

A couple of additional thought here:

• I'm not sure we need to include the nonce in the message to be signed.
• On the other hand, I think we should include the tx_script root into the message.

The reasoning is as follows:

One of the main reasons for constructing a specific message to be signed is that the signature is valid for this transaction only (this is mostly relevant for network transactions where a malicious operator could try to use a signature for an unintended transaction). Including the hash of input and output notes ensures that the signature is valid only on a transaction which consumes/produces the exact set of notes. Including account ID ensures that the signature is valid only for transactions against this account.

However, it doesn't seem like including nonce provides any additional benefits and maybe makes the transaction too "rigid". On the other hand, not including tx_script root, could mean that a malicious operator could execute a different transaction script and the signature would still be valid. I'm not seeing any immediate issues with this (as TX scripts would probably have internal authentication mechanisms) - but it might be good fix the script explicitly.

[Dominik1999]

I am still missing a vital piece here. Why do I need to sign this message within the VM in the first place?

Can't I construct and sign this message outside the VM? When I sign something within the VM, I have a proof that I signed it. But that is the role of a signature anyway, without zkProofs. If I sign something, then that should be enough proof that I signed it.

[bobbinth]

What you are describing would work for private transactions. The simplest approach here is not even a signature - but proving that you know some hash pre-image. If you do know it, then you are authorized to execute a transaction against this account. No need to compute and sign a message at all.

However, this scheme doesn't work if we want to delegate transaction proving to the operator (or any other party). The main reason is that for the operator to execute the transaction, they would need to know the pre-image and that would allow them to execute any transaction.

We can replace the simple pre-image based scheme with a real signature scheme, and in this case, only you could generate a signature (because only you know the private key). But we need to sign something (i.e., some message). We could pick a dummy message - but this would not be secure: as soon as we reveal this signature to the operator, the operator would be able to create transactions by themselves. So, we need to sign a message which is tied to a specific transaction. This way, the operator would not be able to take the signature and apply to some other transaction.

To summarize:

• For private transactions, we don't need "real" signatures - we just need a way for the user to prove that they are authorized to make transaction.
• However, if we want to delegate transaction proving to someone or have "training wheels", we need to have a way for the user to generate signatures which cannot be applied to any other transaction.

[Dominik1999]

Thanks for the explanation. I think I got this part. My question is more about why do we need to sign using the Miden VM?

The message M contains some transaction-specific data. That part is clear to me. Now, there are two options:

• the user can sign M inside the VM
• the user can sign M outside the VM

If we now delegate proof generation to the Miden Operator, there must be a check of the signed message M inside the VM at the network level. But to comply with this, the user can construct and sign the message M outside the Miden VM and provide it as transaction metadata with the public transaction. Or am I missing something?

[bobbinth]

I think that's how it works now - the signing happens outside of the VM and inside the VM we verify the signature.

Specifically, in the VM we use adv.push_sig decorator to push a signature for a given key/message onto the advice stack. How this signature is obtained is up to the implementation of the Host interface. In the default host, the signing is done by the host itself (and the private key is expected to be in the advice provider), but a different implementation of the host interface (e.g., for the operator) may contain a set of signatures generated previously and push them onto the stack as requested.

[Dominik1999]

Ah, ok. We need that in the docs.