[AIP-101][Discussion] Safe onchain key rotation address mapping for standard accounts

[alnoki]

Problem statement

Authentication key mapping has functional issues that render
originating address mapping unsafe.

Generally this means that address mappings can be lost, leading to
account loss and ultimately inability to access funds purely from CLI.

Impact

This impacts projects or users who have used key rotation functionality,
in particular the unproven rotation used for exotic purposes like passkeys.

For more, see:

https://aptos.dev/en/build/guides/key-rotation
https://aptos.dev/en/build/cli/trying-things-on-chain/ledger#authentication-key-rotation

Summary

The onchain key rotation address mapping has functional issues which inhibit
safe mapping of authentication key to originating address for standard accounts.
I propose resolving these issues with the reference implementation.

Motivation

There are currently several issues with the OriginatingAddress table (which is
supposed to be a one-to-one lookup table) that render the mapping unsafe in
practice:

1. Per [Framework][Key rotation] Add OriginatingAddress followup reconciliation function for key rotations without a proof challenge aptos-labs/aptos-core#13517,
   rotate_authentication_key_call does not update the OriginatingAddress
   table for an "unproven" key rotation without a RotationProofChallenge.
2. During an operation that attempts to map an authentication key (which has
   already been mapped) to a different originating address, the inner function
   update_auth_key_and_originating_address_table overwrites the initial
   mapping, rather than aborting. This oversight can lead to account loss if
   someone accidentally attempts to rotate to the same authentication key twice,
   because they will not be able to identify their old account from private key
   alone unless they keep an external record of the rotated accounts it has been
   used to secure.
3. Standard accounts that have not yet had their key rotated are not registered
   in the OriginatingAddress table, such that two accounts can be
   authenticated by the same authentication key: the original account whose
   address is its authentication key, and another account that has had its
   authentication key rotated to the authentication key of the original account.
   Since OriginatingAddress is one-to-one, a dual-account situation can
   inhibit indexing and OpSec.

Proposed solution

Assorted checks and extra function logic in
aptos-labs/aptos-core#14309

Alternative solutions

Per @davidiw in a separate chat:

something where we update the rotation command to take in new and removed keys
as well as any additional metadata that might be useful such as parameters for
the authkey type. Then we add to the indexer a set of all keys that point to
potential addresses.

As I understand, this approach would require breaking changes and would
introduce offchain indexing as an additional dependency in the authentication
key mapping paradigm.

My solution, captured in the proposed reference implementation, offers a
purely onchain solution to existing issues and does not require altering the
existing design space or introducing an offchain dependency.

Specification

N/A

Reference implementations

aptos-labs/aptos-core#14309

Risks and drawbacks

Enforces a one-to-one mapping of private key to account address in the general
case of following best practices, which extreme users (wishing to use one
private key to authenticate all their accounts) may find restrictive.

Security considerations

Note that the function account::set_originating_address proposed in
aptos-labs/aptos-core#14309 must remain a private entry
function to prevent unproven key rotation attacks.

Multisig considerations

In a separate chat, @davidiw asked about how the changes in the reference
implementation will interact with multisig v2. Note that even without the
changes in this PR, it is already possible for a multisig to have an entry in
the OriginatingAddress table:

1. Rotate account A to have a new authentication key, thus generating an entry
   in the OriginatingAddress table.
2. Convert account A to a multisig via
   multisig_account::create_with_existing_account_and_revoke_auth_key, which
   will set the account's authentication key to 0x0, but which will not
   mutate the OriginatingAddress table, since it makes an inner call to
   account::rotate_authentication_key_internal.
3. The OriginatingAddress table then (incorrectly) reports that a mapping from
   the authentication key (from before multisig conversion) to the multisig
   address.

Timelines

Ideally during next release

Future potentials

Potentially in a separate update, logic to eradicate the existing multisig v2
indexing issues mentioned above (which is outside the scope of what the
reference implementation intends to resolve).

Verifying changes in reference implementation

As requested by @ThePOM on 2024-09-17:

1. Install the Aptos CLI [from source] using the changes in this PR.

2. Make a new test directory called localnet-data, then use it to start a
   localnet with the framework changes in this PR:

   aptos node run-localnet --test-dir localnet-data

3. Save the localnet shell running off to the side.

4. In a new shell, create a private key file:

   aptos key generate --output-file keyfile-a

5. Use it to create a localnet profile:

   aptos init \
       --network local \
       --private-key-file keyfile-a \
       --profile localnet-a

6. Store the address:

   ADDR_A=<profile-address>

7. Use the new originating_address view function to observe that the account
   does not have an entry in the OriginatingAddress table:

   aptos move view \
       --args address:$ADDR_A \
       --function-id 0x1::account::originating_address \
       --profile localnet-a

8. Use the new set_originating_address private entry function to set a mapping
   in the table:

   aptos move run \
       --function-id 0x1::account::set_originating_address \
       --profile localnet-a

9. Check the originating_address view function again and note the result:

   aptos move view \
       --args address:$ADDR_A \
       --function-id 0x1::account::originating_address \
       --profile localnet-a

10. Now that you've established a one-to-one mapping for the authentication key,
    the new check for ENEW_AUTH_KEY_ALREADY_MAPPED in
    update_auth_key_and_originating_address_table will prevent another account
    from rotating its authentication key to that of keyfile-a, thus preserving
    a one-to-one mapping. To verify this, create a new profile:

    aptos init \
        --network local \
        --profile localnet-b

11. Press enter when prompted to generate a new private key for the profile.
    Then observe the new guard against breaking the one-to-one mapping, by
    trying to rotate the authentication key to that of keyfile-a:

    aptos account rotate-key \
        --new-private-key-file keyfile-a \
        --profile localnet-b \
        --save-to-profile localnet-b-secured-by-keyfile-a

[igor-aptos]

Thank you for the design review, these changes look sound, I vote for "approve".

On the broader question, this raises valid concerns about OriginatingAddress, some of which are not resoled by the above, as noted.
As main use is for being able to figure out account address(es) from a given auth key, I think more general and canonical way is to index Account.authentication_key => list of account addresses, and provide API to query it. Given that, it seems like there might not be need for having OriginatingAddress onchain at all.

[davidiw]

Approved on my end.

[sherry-x]

Looks good to me, approved.

[wrwg]

Approved from my end.

[movekevin]

Approved