[Feature Request] Multi-Ed25519 Scheme: Ease the check when deserializing multi-ed25519 public keys

[JackyWYX]

🚀 Feature Request

The feature request is a follow up of https://github.com/aptos-labs/aptos-core/issues/4307.

Move the validation check for each Ed25519PublicKey of multi-ed25519 public key from transaction deserialization to multi signature verification.

1. At the current implementation, each public key in Multi-Ed25519 public key is required to fit into ed25519_dalek schema when the input transaction is deserialized into SignedTransaction.
2. But for some use cases, it is intended that some of the public key is not a valid Ed25519 public key (Illustrated in chapter Motivation).
3. Thus, we propose to remove the check of whether a 32 byte is a valid Ed25519 at transaction deserialization, and add it to signature verification as a lazy check.

Motivation

The current public key schema for multi-ed25519 is limited in the number of multi-sig addresses can be created for the same group of people. E.g. For two users, A and B, they are only able to create at most two 2/2 multi-sig account with Aptos native multi-ed25519 schema:

pubkey1 = pk_a | pk_b | 2 | 0x01
pubkey2 = pk_b | pk_a | 2 | 0x01

The number of multi-sig accounts created by the same group of people with the same setting is limited to the permutation of the user public keys. However, this can not satisfy the need where exact the same group of people want to create multiple multi-sig wallets. Taking this user need, momentum safe propose a schema as a variant of Aptos multi-sig schema by introducing the noncePublicKey, thus it will remove the number of accounts can be created by the same people. Take the above example:

pubkey1 = pk_a | pk_b | 0x00.....0001 | 2 | 0x01
pubkey2 = pk_a | pk_b | 0x00.....0002 | 2 | 0x01
pubkey2 = pk_a | pk_b | 0x00.....0003 | 2 | 0x01

The nonce public key is used as a public key as the owner of the multi-sig wallet. Since the private key of a given public can never be achieved as a cryptographic premise, the new scheme has the same effect as the aptos default mutlsig schema. So in this case, the nonce public key can be an "invalid" ed25519_dalek public key as intended.

The code snippet to generate the multi-sig transaction of new schema is here, where the third public key is the little endian encoding of the nonce of value 2.

    const publicKeys = [
        new TxnBuilderTypes.Ed25519PublicKey(Buffer.from('841a1ca8e47f78c03dc4ec61eb7a6f1aba5f3e4235389a20e7018388bf631f7d', 'hex')),
        new TxnBuilderTypes.Ed25519PublicKey(Buffer.from('50081a3900885a635bf480d27827c71ff55d06fbc6f1e9fb737d49b758df81ec', 'hex')),
        new TxnBuilderTypes.Ed25519PublicKey(Buffer.from('0200000000000000000000000000000000000000000000000000000000000000', 'hex')),
    ];

However, the transaction fails the transaction deserialization on server side reporting error since the Ed25519 public key check is enforced at SignedTransaction.deserialize, which makes the transaction fails with error Failed to deserialize input into SignedTransaction. (See https://github.com/aptos-labs/aptos-core/issues/4307 for full error message)

Thus, we propose to do the ed25519_dalek check in a lazy mode only during transaction signature verification.

Pitch

Describe the solution you'd like

We propose a lazy ed25519_dalek public key check during multi-signature verification. This solution will have the full backward compatibility without introducing a breaking change. The change only need to take place in rust code.

At SignedTransaction deserialization, deserialize the multi-signature into an unverified Ed25519 public key.

// aptos-core/crates/aptos-crypto/src/multi-ed25519.rs:40
pub struct MultiEd25519PublicKey {
    public_keys: Vec<Ed25519PublicKeyUnverified>,
    threshold: u8,
}

Create a new struct Ed25519PublicKeyUnverified that implements DeserializeKey but only checks the byte size === 32 during deserialization.

#[derive(DeserializeKey, SerializeKey, SilentDebug, SilentDisplay)]
pub struct Ed25519PublicKeyUnverified

Convert Ed25519PublicKeyUnverified to Ed25519PublicKey during signature verification, and skip Ed25519PublicKeyUnverified that cannot fit into ed25519_dalek scheme.

impl Signature for MultiEd25519Signature {
    type VerifyingKeyMaterial = MultiEd25519PublicKey;
    type SigningKeyMaterial = MultiEd25519PrivateKey;

    fn verify<T: CryptoHash + Serialize>(
        &self,
        message: &T,
        public_key: &MultiEd25519PublicKey,
    ) -> Result<()> {

Describe alternatives you've considered

Change the multi-ed25519 schema by adding a nonce to it. However, we do not recommend this approach since it will introduce a breaking change that will require changes in all multi-sig related code (including account.move).

pubkey1 = pk_a | pk_b | nonce (as u64) | 2 | 0x01

Are you willing to open a pull request? (See CONTRIBUTING)

[JackyWYX]

Hey guys, any comments? @jjleng @gregnazario @davidiw

[JackyWYX]

Hey guys, any updates yet?

[davidiw]

This seems insecure. Using the same set of private keys for distinct accounts. All you're doing is defining a distinct authorization key and account. We made a decision internally to also not re-use a single mnemonic for multiple accounts.

Will let @alinush chime in before closing out.

[JackyWYX]

Would you please elaborate a bit more on the "insecure" part? What vulnerability is added from this feature request?

From my understanding, reusing a single mnemonic shall be the best practice for single sig wallets. However, we are talking about multi-sig scenario in this case. It's shall be a feature for the same set private keys may form distinct accounts for different use cases. Adding this limitation will only effect user experience, since:

1. Duplicate mnemonic check is not applicable on chain level.
2. User can always add another valid ed25519 (owned by no one) to form a valid multi-ed25519 public key to form a 2/3 wallet that is controlled by 2 private keys. It shall be a feature suggested by the nature of multi-sig.
3. What we are doing here is basically extending the use of the existing multi-sig scheme and fix a use case that the original scheme does not support.

All we ask here is to alleviate the check in multi-ed25519 deserialization, and only add ed25519 dalek check when the bitmap for the specific public key is provided, which shall add no vulnerability in protocol level.

[JackyWYX]

@davidiw @alinush Feedbacks? Thanks!

[alinush]

I will reply with thoughts in a few days; a little too busy with other things to think through this carefully right now. Apologies.

[JackyWYX]

👀

[alinush]

Hi @JackyWYX,

Apologies for the delay.

The bad news is what you are trying to do will likely get you into trouble via signature replay attacks.

Specifically, consider your pubkey1 and pubkey2 MultiEd25519 PKs from your "Motivation" section above, which both contain Ed25519 PKs for Alice and Bob. Next, notice that any signature $\sigma$ under pubkey1 can be turned into a signature $\sigma'$ under pubkey2 by just re-arranging things.

Depending on your use case, this could be very bad!

@davidiw, we should consider the implications of this in general and if we want to prevent this (although it would be a breaking change).

The good news is that you can achieve what you want without us changing anything: just generate a valid Ed25519 public key whose corresponding secret key nobody provably knows.

How?

1. Pick some random bytes and hash them to an EdwardsPoint via EdwardsPoint::hash_to_bytes()
2. Compress and serialize that EdwardsPoint to get a serialized Ed25519 public key via EdwardsPoint::compress() and CompressedEdwardsY::to_bytes()

That being said, you are likely playing with fire due to the replay attack mentioned above, AFAICT...

[JackyWYX]

Thanks for the attention!

I don't think I get the bad news part yet. There is a sender field in the transaction payload that need the owner sign on it, which shall be different for the default address for pubkey1 and pubkey2. Even there is a collision in public key, the sender field will differentiate the transaction sent from different senders. Still curious how does the replay attack happens.

For the good news, we don't think we have EdwardsPoint is public in ed25519.move. There is some work around, but that will cost user some additional gas to find a valid public key. We think it is more reasonable to have the feature implemented in the node level, since it won't do any harm at least (Just like Ethereum address 0x0000000, or aptos 0x4 0x5 is not a valid address as well).

[JackyWYX]

What you are concerned with is more related to signing a general message. And I think there shall be something to work on the Aptos sign message standard (including a sender address in message payload). Can be a similiar standard to EIP-712

[alinush]

Indeed, for transaction signatures, they will be domain-separated by other things, like the address of the account. Nonetheless, people could still shoot themselves in the foot when verifying MultiEd25519 signatures in Move via the aptos_stdlib::multi_ed25519 module.

Also, indeed, we are working on a standard for domain separation similar to EIP-712.

If you want support for hashing a sequence a bytes to an Ed25519 PK in Move, we would have to figure out where this would fit and can implement it.

For now though, you could simply generate the dummy PK offline in Rust and pass in its serialization into Move and call ed25519::new_validated_public_key_from_bytes?

Or is that not gonna work for your use case?

[JackyWYX]

Yea, understood. The issue we have is two:

1. There is no implementation in TS that we can find, but we do need to compute this dummy key in react, which is not available ATM. If you know any ts implementation of dalek, please let us know.
2. There is a work around we have already implemented to increment and loop the nonce until finding the next valid public key. Since a number falls on Dalek is approximately 50%, it should not take too much resource / gas to obtain a valid public key.
3. But the best solution to allow dummy public key DURING TRANSACTION DESERIALIZATION is still the best solution we can think of. You do not need to change any move code, or update any code logics, but just add a lazy deserialization for multi-ed25519 Dalek public key during transaction deserialization.

[JackyWYX]

Hey is there any updates in this? We don't think this feature request will result in any kind of replay attack, nor will adding security vulnerabilities. Any updates?

[alinush]

Hey @JackyWYX, I thought your last comment kind of settled it.

For now, we do not want to relax the public key validation criteria, since your issue can be dealt with either by:

1. Paying a higher gas fee as you suggested by iterating through a few PKs.
2. Changing an existing Ed25519 TS library to implement hash_to_point

[JackyWYX]

Hey @alinush, Thanks for reply. Yes, there is a temporary fix that makes everything works. Wondering whether Aptos core is able to address this issue further so that user gas fee can be saved for computing an unnecessarily valid public key.

[github-actions[bot]]

This issue is stale because it has been open 45 days with no activity. Remove the stale label or comment - otherwise this will be closed in 15 days.