Consolidate authentication components

[bobbinth]

Currently, we have the following standard authentication components:

• no_auth
• ecdsa_k256_keccak
• ecdsa_k256_keccak_acl
• rpo_falcon_512
• rpo_falcon_512_acl
• multisig_ecdsa_k256_keccak
• multisig_rpo_falcon_512

This is already quite a few and there is a lot of code duplication between them. In the next release of the VM we also have added support for EdDSA signature scheme, and in subsequent releases we'll have ECDSA over P256 curve and canonical Falcon signature support added. This will make matters quite a bit worse.

I think we should try to consolidate these authentication components to be "signature agnostic". The list of components could be:

• no_auth (same as now).
• auth_singlesig (maybe a different name is needed) - authentication component where only single signature controls the account.
• auth_singlesig_acl.
• auth_multisig - an $m$ of $n$ multisig.
• auth_multisig_acl.

The idea is that these components would be extensible with respect to signature schemes and the potential approaches of how to support this are described in #2083 (comment).

A couple other open questions:

• Should we also include the PSM-enabled multisig into the set? In this case, we could have something like auth_basic_multisig and auth_psm_multisig.
• Should we somehow consolidate the ACL and non-ACL variants? Maybe this could be done via component templates (e.g., the simple component is just a special case of the ACL component). Though, there is an argument for keeping some components as simple as possible.
• How much flexility do we want to support in regards to mixing signature schemes? For example, do we want to have a multisig that can mix ECDSA and Falcon signatures?
• How do we handle key rotations? Would these be a part of these standard components?

Related issues:

• Decide whether to refactor verify_signatures and standard faucets #2135
• Consider rename the repo to miden-protocol #1563
• Templating of auth procedures #1956

[MCarlomagno]

Thanks Bobbin! overall the idea makes sense to me,

with respect to #2083 (comment): I'm wondering if it's possible a 3rd approach using pre-compiles, where we define a generic precompile for signature verification that also does the work of detecting what type of signature scheme it is? then the MASM code remains up-to date with new schemes and the code for verification is safe behind a precompile?

About the questions:

Should we also include the PSM-enabled multisig into the set? In this case, we could have something like auth_basic_multisig and auth_psm_multisig.

How auth_basic_multisig would look like? I guess the only difference is that we don't require any PSM signature verification in the template? Maybe they could be both the same component and optionally switch on the PSM feature by passing some flag when creating the account, wdyt?

Should we somehow consolidate the ACL and non-ACL variants? Maybe this could be done via component templates (e.g., the simple component is just a special case of the ACL component). Though, there is an argument for keeping some components as simple as possible.

I guess one question is how often would ACL be used in comparing with non-ACL, if ACL is rare case I would keep it separated

How much flexility do we want to support in regards to mixing signature schemes? For example, do we want to have a multisig that can mix ECDSA and Falcon signatures?

I think having this flexibility would be better, ideally accounts should not be locked in in some specific signature scheme if down the road there will potential migrations (e.g. ECDSA -> Falcon post quantum?)

How do we handle key rotations? Would these be a part of these standard components?

I think yes, and I think in the cases of multisigs is already handled by add/remove cosigner, and for single signer we can just expose some rotate_key proc? - or maybe you mean Timelocked rotations? in that case here are some points of discussion, @onurinanc we should aim to unify the approach

[onurinanc]

Hi Bobbin, thank you for opening the issue!
Related to: #2083 (comment). Related to the approaches, I agree @MCarlomagno adding a generic signature precompiles would be super cool. This is also how it works in EVM, which makes the things super easier for the developers when comparing with other two approaches.

If this approach is not possible, I would prefer to go with the 2nd approach that you've described. There will be some cons that we need to make some changes in the verify_signatures procedure every time when a new signature scheme is added, but we can get rid of dynexec and possible security considerations related to that. Other than that, I believe "mixing signature schemes in a multisig" would be a desired feature in case of combining 1 hardware key + 1 software key, or using different wallets for signing.

Should we also include the PSM-enabled multisig into the set? In this case, we could have something like auth_basic_multisig and auth_psm_multisig.

For this one, I agree the @MCarlomagno approach. The reason is that the only part Multisig.masm differs from the MultisigPSM will be call.psm::verify_psm_signature. See here: https://github.com/OpenZeppelin/miden-confidential-contracts/blob/3773f1c85fd2b409ba6b1991243b45200dcacf37/masm/auth/multisig.masm#L418
So, we could have a storage slot such a const INITIALIZE_PSM_SLOT, so that we can have a if-else statement in the MASM code for verifying the psm signature.

How do we handle key rotations? Would these be a part of these standard components?

Here, I have implemented the propose/execute logic similar to how you mentioned in this discussion: OpenZeppelin/private-state-manager#61

Here is how I have implemented: https://github.com/OpenZeppelin/miden-confidential-contracts/blob/3773f1c85fd2b409ba6b1991243b45200dcacf37/masm/auth/timelocked_account.masm#L156-L258 . It's currently for Single User (Primary Key + Secondary Key) Timelocked Multisig Account

It basically works as:

• fixing the threshold and number of approvals inside the update_signers_and_threshold -> this will be renamed to update_signers and the logic will be changed a bit by fixing the threshold
• pub proc update_signers -> proc.update_signers
• update_signers internally called by execute

So, I believe AuthTimelockedMultisig will be different than the AuthMultisig (but it's a special case of multisig), but it would be better to have AuthMultisig.with_component(timelocked_account) somehow but I'm not sure how the MASM files should be located in this case.

Should we somehow consolidate the ACL and non-ACL variants? Maybe this could be done via component templates (e.g., the simple component is just a special case of the ACL component). Though, there is an argument for keeping some components as simple as possible.

I think we can keep them separate since the only use case for ACL that I've seen is for distributing tokens (correct me if I wrong) and this can be also done by ownable logic with notes. For Multisig account, we already have a logic for auth trigger procedures.

The other potential code duplication would be the logic inside compute_transaction_threshold this would be changed for the upcoming features such as "handling amount-based thresholds"

[bobbinth]

I'm wondering if it's possible a 3rd approach using pre-compiles, where we define a generic precompile for signature verification that also does the work of detecting what type of signature scheme it is? then the MASM code remains up-to date with new schemes and the code for verification is safe behind a precompile?

I agree @MCarlomagno adding a generic signature precompiles would be super cool. This is also how it works in EVM, which makes the things super easier for the developers when comparing with other two approaches.

We don't really have a concept of "precompiles" (in the Ethereum sense). We could deploy an account that would be used by other accounts to perform signature verification via FPI calls. Presumably, this "precompile" account would maintain a registry of available signature schemes which it will manages using dynamic invocation. But then, this is not too different from using dynamic invocation locally.

If this approach is not possible, I would prefer to go with the 2nd approach that you've described. There will be some cons that we need to make some changes in the verify_signatures procedure every time when a new signature scheme is added, but we can get rid of dynexec and possible security considerations related to that. Other than that, I believe "mixing signature schemes in a multisig" would be a desired feature in case of combining 1 hardware key + 1 software key, or using different wallets for signing.

I largely agree with this. There is some elegance to using dynexec but not sure it is justified and it also would prevent us from being able to mix different signature schemes in the same account. So, my take is to standardize the second approach (and we should be able to support the 4 - 5 core signature schemes before mainnet), and then, maybe some time down the road we can re-evaluate the dynexec approach.

---

I think the next step would be to create a document to describe the functionality we want to have for each of the auth components. For example, for singlesig, it would be something like:

• Ability to sign with core signature schemes (e.g., Falcon, ECDSA(k256), EdDSA).
• Ability to rotate the key (with or without the delay? - but how useful is this?)
• Ability to delay large transfers?

Or maybe we need 2 variants for signlesig:

Basic variant

• Ability to sign with core signature schemes (e.g., Falcon(RPO), ECDSA(k256), EdDSA).
• Ability to rotate the key (no delay).

Extended variant

• Ability to sign with core signature schemes (e.g., Falcon(RPO), ECDSA(k256), EdDSA).
• Ability to rotate the key (with delay).
• Ability to delay large transfers.

These are just examples and we may end up with some other set of capabilities - but would be great to do this for the different options of signlesig and multisig as well. Could you guys put this into a document?

[onurinanc]

Hey! What's the current progress related to having pluggable signature schemes? Is there any work we can help with this?

[onurinanc]

Hi @bobbinth what do you think about allowing both Falcon and ECDSA signatures to be used in the same multisig? If we do allow this, what would need to be implemented in the protocol-level?

If we decide not to allow both within the same multisig, we would introduce a single flag at account setup. For example, 0 -> Falcon and 1 -> ECDSA. Then, during verify_signatures, we could dispatch based on this flag.

• If the account was created with 0, we call falcon::verify_signatures
• If it was created with 1, we call ecdsa::verify_signatures.

Alternatively, we can change the storage layout so that the signature scheme is stored alongside the key_index. In that case, we would also update falcon::verify_signatures and ecdsa::verify_signatures accordingly.

For example:

# Map entries: [key_index, signature_scheme, 0, 0] => APPROVER_PUBLIC_KEY
const APPROVER_PUBLIC_KEYS_SLOT = word("miden::standards::auth::ecdsa_k256_keccak_multisig::approver_public_keys")

These are my proposals at the MASM level. Do you have any suggestions for changes we could make at the protocol level?

I’m not sure about your thoughts on supporting Falcon, but it appears to be roughly ~80× less efficient than ECDSA. Given this, I would suggest deprecating this signature scheme. Is Falcon planned to be used in the long term? If so, could you share the benefits it provides?

[bobbinth]

what do you think about allowing both Falcon and ECDSA signatures to be used in the same multisig?

I think there is a benefit to this because we could have different types of keys for different purposes. This is not necessarily specific to Falcon vs. ECDSA - but a bit more general. For example, a "hot key" could be using a signature scheme that is easily supported in browsers, but a "cold key" could use a different scheme which requires HSM or something like that.

If we decide not to allow both within the same multisig, we would introduce a single flag at account setup. For example, 0 -> Falcon and 1 -> ECDSA. Then, during verify_signatures, we could dispatch based on this flag.

• If the account was created with 0, we call falcon::verify_signatures
• If it was created with 1, we call ecdsa::verify_signatures.

Yes, this will work. I would make keep this somewhat more extensible though as we will probably want to add a few more signatures schemes before mainnet (the ones I have in mind are EdDSA, ECDSA with p256 curve, and canonical Falcon).

The main question here is where to put this scheme. There are a few options:

1. We could have a separate map to track the scheme - this feels a bit wasteful.
2. We could do what you've suggested and put the scheme into the key of the storage map. This could work, but I haven't thought through all the implications here (e.g., how would we be able to iterate over such a map?).
3. We could add an event to the transaction kernel that would retrieve the key scheme from the authenticator (via the TransactionAuthenticator::get_public_key() and then push it into the advice provider).

The 3rd option requires a bit more work, but I think it is a bit cleaner. @PhilippGackstatter @mmagician - what do you guys think?

I’m not sure about your thoughts on supporting Falcon, but it appears to be roughly ~80× less efficient than ECDSA. Given this, I would suggest deprecating this signature scheme. Is Falcon planned to be used in the long term? If so, could you share the benefits it provides?

One of the advantages of Falcon RPO is that it doesn't require precompile support and still runs in reasonable time. Another advantage is that it is Post-Quantum secure. But I think it is a good point that we probably shouldn't rely on it as much any more. So, in my mind, there are two questions:

1. Do we deprecate it entirely or just switch the default scheme to ECDSA?
2. Or maybe instead of deprecating, we should replace it with canonical Falcon (which would have to use a pre-compile for hashing)?

Also, cc @Al-Kindi-0 in case you have any additional thoughts.

[mmagician]

These are my proposals at the MASM level. Do you have any suggestions for changes we could make at the protocol level?

The choice of the signature scheme is an application-level concern, so we should not try to touch the protocol for it if possible.

---

Map entries: [key_index, signature_scheme, 0, 0] => APPROVER_PUBLIC_KEY

I think the only downside is that iterating through the map will be N x M with N = number of keys, M = total number of signature schemes supported. This is not bad, but the map iteration won't be a very clean pattern.

We could have a separate map to track the scheme - this feels a bit wasteful.

This is definitely the simplest approach, and given a rather small amount of keys that we expect, I don't think it's necessarily bad in terms of performance.

---

A fourth approach is using the double-array abstraction for which I have a PR open. This would let us store public keys + scheme type under the right index.
The interface would change from constructing the map key manually to simply providing a single-Felt index. The return value of that would be [APPROVER_PUBLIC_KEY, [0, 0, 0, scheme_id]. The iteration interface ends up much cleaner than approach 2. above. Also, it's using a single storage map (as opposed to two storage maps like approach 1.), so overall I think it's the best of the two worlds.

[PhilippGackstatter]

I agree with @mmagician that ideally this shouldn't require changes at the protocol level.
It seems like this use case would also benefit from having a storage list (#2176) or array (#383), so maybe this is something we should do soon. In the storage list case, the account would store a list of entries:

[[0, 0, key_index, signature_scheme], [APPROVER_PUBLIC_KEY]]

It would be retrieved in a single kernel call (e.g. active_account::get_list) and iteration would be pretty efficient since it's entirely in memory.

Additionally, we could use miden::core::collections::sorted_array::find_half_key_value for looking up an approver public key if we already know key_index and signature_scheme (which requires sorting by key_index and signature_scheme so the host-based support can work efficiently, but afaict sorting should be fine). We can also design it in such a way that we can look up only by key_index or only by signature_scheme by putting only either of those into element 3 and leaving element 2 empty. I haven't thought enough about this to understand if that would help, but wanted to bring up the idea as it doesn't require any additional protocol changes (except for the general storage list support).

[bobbinth]

We could have a separate map to track the scheme - this feels a bit wasteful.

This is definitely the simplest approach, and given a rather small amount of keys that we expect, I don't think it's necessarily bad in terms of performance.

Overall agree, and we should probably start here. Once storage lists become available, we could switch to them and it should address most of the efficiency concerns.

---

There is one other option though, we could "embed" the scheme ID into the public key commitment. The simplest way to do that would be to just overwrite 8 bits of the public key commitment with AuthScheme. Giving up 8 bits would not have any significant impact on collision resistance, and it would also have the nice benefit that looking at the PublicKeyCommitment struct, we'd always be able to tell which scheme does the underlying key belong to.

I think the main complication here is that signature verification procedures (which are in miden-vm) would need to be updated to expect not the "real" commitment to the public key but a slightly modified version. This may be a bit too big of a lift right now. cc @Al-Kindi-0 and @adr1anh in case you guys have thoughts on this.