# Key Rotation 2025

> Author: Mike

Defi-Wonderland have been exploring how to build a multisig on Aztec.

A key feature that users expect of a multisig is... key rotation.

DW are exploring how to build a multisig using the current Aztec protocol -- where rotation of viewing keys and nullifier keys is not possible.

To emulate key rotation, they're going down avenues of:
- Threshold decryption
- [Threshold plume nullification](https://hackmd.io/sFVGNA4PRvKh5FnRkzFPiA)

It'll be interesting to hear their opinions on using those approaches, and I believe a report is in the works...

## Key rotation in 2025

> Here are the 2024 notes on key rotation https://hackmd.io/ujdgb7U6TFm94OAqDyPT0w, but some parts are now outdated because the protocol has changed over time.
>
> Iiuc, the "onboarding problem" and the "king of the hill problem" described in that doc are no-longer relevant, because an address _is_ an encryption public key now.

Let's explore what key rotation would look like in 2025.

### Summary

The 2024 approach -- of putting the Npk inside a note, and using that Npk to nullify -- is still valid. It had some shortcomings though (see the table).

This doc looks at a new approach which seeks to improve on those shortcomings, at the expense of some constraints. I'll call it **"Pretty good key rotation"**.

Summary of approaches:

| Strategy: | Nullify with Npk from Note | Nullify with Address from Note | Nullify with the latest Npk from the Registry.</br>aka "Pretty Good Key Rotation".</br>(see later in this doc) |
| ------------------------------------------------------------------------------------------------- | ------------------------------------ | ----------------------------------------------------------- | ------------------------------------------------------------------------------------------------------------------------------------------------------- |
| Description | `Note = h(..., Npk)` - Use this Npk. | `Note = h(..., Address)` - use Npk from within this Address | `Note = h(..., Address)` - Lookup the current Npk for this `Address` from the registry, and prove that any nullifiers of older Npks were never emitted. |
| Extra cost to lookup recipient Address | 3-4k | 3-4k | 3-4k |
| Extra cost to lookup sender Npk | - | - | 3-4k |
| Extra cost to prove older sender nullifiers have not been used (happy path: sender has never rotated keys) | n/a | n/a | ~600 |
| Extra cost to prove older sender nullifiers have not been used (if >=1 rotation has happened) | n/a | n/a | 👎 1 fn call (at least 28k gates in the function to recursively verify vanilla noir proof). |
| After rotation, do you need to migrate (manually spend) your existing notes to update their keys? | Y 👎 | Y 👎 | N ✅ </br> Automatic updating of keys. |
| If you lose your nsk, are your existing notes spendable? | N 👎 | N 👎 | Y ✅ (you can rotate your keys, as long as you still have your tx auth key). |
| If an attacker learns your nsk, can they spend your notes? | Not without tx auth key ✅ | Not without tx auth key ✅ | Not without tx auth key ✅ |
| Attacker (who learns old nsk's) can see when you nullify your "pre-rotation" notes, in future? | Y 👎 | Y 👎 | N ✅ |
| Attacker (who learns old nsk's / ivpk's) can see your note history? | Y | Y | Y |
| Protocol changes required? | N | N | Hash the block timestamp into every new note, within the AVM/Base Rollup. |

:::info
So to do an ordinary transfer (2 notes in, 1 note out for recipient, 1 note out for sender), using the "Pretty Good Key Rotation" approach, it would be ~7,000-10,000 gates on the happy path of never having rotated.
That sounds like a lot. But it's actually just ~100 poseidon2 hashes.
Newer proving systems like Ligero quote 20,000 poseidon2 hashes _per second_ in the browser. So 100 should be considered ~nothing.
:::

### Background

The hard-coded preimage of an AztecAddress is:


You can see the hard-coded public keys in yellow.

:::info
Recall, aztec does have "account abstraction", but it's different from Ethereum account abstraction: users cannot rotate all of their keys.

A user can only rotate their "tx auth key", because that's the only key that gets verified within the user's abstract account contract.

The nullifier key and the viewing key are baked-into the user's address, and app functions have hard-coded constraints to use those hard-coded keys. So rotation of those keys is not possible in today's protocol.

So only "tx auth" keys can be rotated, currently. That might confuse users.
:::

#### Precedent for rotating hard-coded address preimage data

A user _can_ already rotate their account contract's `contract_class_id` by calling `update()` in the `ContractInstanceRegistry`.

There's a mapping:

#[storage]
struct Storage<Context> {
    updated_class_ids: Map<AztecAddress, DelayedPublicMutable<ContractClassId, DEFAULT_UPDATE_DELAY, Context>, Context>,
}

This is effectively a mapping for each address:

address -> contract_class_id_2

> The `contract_class_id_2` is stored in a `DelayedPublicMutable`, which means there's a delay before the change takes effect, to enable private functions to safely read the value for some time without being rugged by public changes.

So already whenever any function of any smart contract is called, we have some conditional logic:

- Lookup the `address` in the `ContractInstanceRegistry`.
- If there is a nonzero `contract_class_id_2`:
- Assert that whenever a function of this `address` is called, the function belongs to the new `contract_class_id_2`.
- Else:
- Use the hard-coded `contract_class_id_1` within the `address`, and assert that the function belongs to that.

It costs ~3-4k gates to do this check.

## Interesting approach: "Pretty Good Key Rotation" -- "Nullify with the latest Npk from the Registry"

:::info
Summary of approach:

`Note = h(..., Address)`

Lookup the current `Npk` for this `Address` from the registry, and recursively prove that any nullifiers derived from older Npks were never emitted.
:::

Let's copy the registry approach used to update an address's `contract_class_id`:

Address_1 -> { contract_class_id_2, Address_2, Ivpk_2, Npk_2, timestamp_of_change_2 }

Again, we'd store this struct of info in a `DelayedPublicMutable`.

The act of updating would require proof that `Address_2` is the same as `Address_1`, but for the new `contract_class_id_2, Ivpk_2, Npk_2`.

### Creating and encrypting a note for a Recipient

As today, let's store the address in the note.

> In our previous attempts at key rotation, we instead stored the user's Npk in the note, to prevent double-spend. I'm seeking to use the address with this attempt.

The logic for deciding which address to use would be:

- "I want to create a note owned by `Address_1` (i.e. they're the person who may nullify (the nelly))".
- "I want to encrypt the contents of the note to `Address_1`".
- Lookup `Address_1` in the `ContractInstanceRegistry`.
- If there is a nonzero struct
- Use the `Address_2` of that struct.
(glossing over the inner workings of DelayedPublicMutable)
- Else:
- Use `Address_1`

:::info
Extra constraints: ~3-4k to read from the registry.
:::

**Before rotation**, we use `Address_1`:

`new_note = { ..., nelly: Address_1 }`

Encrypt the `new_note` to `Address_1`.

**After rotation**, we use `Address_2`:

`new_note = { ..., nelly: Address_2 }`

Encrypt the `new_note` to `Address_2`.

The Recipient will recieve their note.

We'll look at the complexities of nullifying that note next.

### Spending a Note

Suppose a user has:

`note_1 = { ..., nelly: Address_1, creation_timestamp_1 }`, created during "era 1" -- before they rotated their keys.

:::info
Notice that this requires a tiny protocol tweak: within the Base Rollup circuit (and/or AVM), we hash into every note the timestamp of the block in which the note was created -- a `creation_timestamp`.

Without that change, we'd need the user to do two archive membership proofs: one against the block in which the note first got inserted, and one against the immediately prior block to show that the leaf was previously empty. So ~8k gates of membership proofs, instead of an extra field in the note.

But... putting the block timestamp inside each note isn't without its downsides: the user who creates the note would have to keep listening to the blockchain until the note is "mined", in order to know the block timestamp to inject into their note.
:::

Logic to nullify:

- Get note: `note_1 = { ..., nelly: Address_1, creation_timestamp_1 }`
- Extract the `nelly: Address_1` and `creation_timestamp_1`.
- Lookup `Address_1` in the `ContractInstanceRegistry`.
- If there is a nonzero struct
- Read `Npk_2, timestamp_of_change_2` from the struct.
- Else:
- Use `Npk_1` from the address preimage.
- Get the corresponding `nsk` of the looked-up `Npk`.
- `nullifier = h(..., nsk)`

To nullify `note_1` during "era 1" (before the `timestamp_of_change_2` at which `Address_2` takes effect in the registry):

- We'll read `Npk_1`
- `nullifier_1 = h(..., nsk_1)`

To nullify `note_1` during "era 2" (after the `timestamp_of_change_2` at which `Address_2` takes effect in the registry):

- We'll read `Npk_2, timestamp_of_change_2` from the registry.
- We'll see that `creation_timestamp_1 < timestamp_of_change_2`, so there's a chance that `note_1` was already nullified during "era 1".
- We **must** check that `nullifier_1` has not been emitted:
- Perform a historical proof of non-membership of `nullifier_1` in some historic block header with timestamp _after_ `timestamp_of_change_2`. This will demonstrate that `nullifier_1` was not emitted during "era 1".
- Note: `nullifier_1` cannot be emitted during "era 2", because `Npk_2` will be read thereafter, when attempting to nullify.
- `nullifier_2 = h(..., nsk_2)`

:::info
Extra constraints to spend:
- ~3-4k to read from the registry
- ~3k to prove non-membership in a nullifier tree
:::

BUT...

What if the keys are rotated again, before `note_1` is spent?

We'd enter "era 3", with a new set of keys in the registry: `{ contract_class_id_3, Address_3, Ivpk_3, Npk_3, timestamp_of_change_3 }`

Well then things get tricky.
- We would need to prove non-membership of `nullifier_1` up to the end of "era 2".
- We would need to prove non-membership of `nullifier_2` up to the end of "era 2".

Notice then that we can't overwrite the entry in the registry with a new entry, because we **must** retain the knowledge that the keys of "era 2" existed, because we **must** know to compute and check for non-existence of `nullifier_2`.

So the registry would need to become a [dynamic array](https://github.com/AztecProtocol/aztec-packages/issues/2211):

Address_1 -> [
                 { contract_class_id_2, Address_2, Ivpk_2, Npk_2, timestamp_of_change_2 },
                 { contract_class_id_3, Address_3, Ivpk_3, Npk_3, timestamp_of_change_3 },
                 length: 2,
             ]

We can't really have this "dynamicness" (a dynamic number of nullifiers being checked for non-membership) in a vanilla circuit.
We could:
- Have a fixed number (possibly 0) of nullifiers be checked for non-membership within the "main" circuit;
- and for any extra spillover nullifiers, recursively call a function that checks for non-membership.
- Or, rather than costly aztec function calls, we _could_ perhaps verify an ultrahonk proof directly in the circuit.

:::info
Extra constraints to spend:
- ~3-4k to read from the registry
- ~600 constraints to line-up a function call (which may or may not be called, depending on how many times the user has rotated their keys -- see pseudocode below).

That's pretty good, considering that we can leave old notes alone (we don't have to spend them to update their owner address).
:::

// Pseudocode
// This shows low-level syntax that would get
// hidden behind state vars in reality.
fn spend_a_note() {
    let note = get_note(...);
    let { Address_1, creation_timestamp } = note;

    let nullifier = ensure_not_nullified_yet(note);
    
    emit nullifier;
}

// I'm trying to quickly illustrate: there's likely a much better design
// for dynamic arrays:

struct DynamicArrayEntry<T> {
    entry: T,
    // Some kind of info that lets us get 
    // the _previous_ entry in the array,
    // like a linked list.
    // E.g.: a nested hash of all entries in the array
}

struct LastEntry<T> {
    length: u32,
    entry: DynamicArrayEntry<T>,
}

struct DynamicArray<T> {
    last_entry: DelayedPrivateMutable<LastEntry<T>>,
}

struct UpdatedAddressData {
    contract_class_id: Field,
    Address: AztecAddress,
    Npk: Point,
    Ivpk: Point,
    timestamp_of_change,
}

fn ensure_not_nullified_yet(note) {
    let { Address_1, creation_timestamp } = note;
    
    // Some kind of constant-size read from the array:
    let { last_entry } = ContractInstanceRegistry::read_updated_address_data_array(Address_1);
    
    let (Npk, timestamp_of_change) = if last_entry.length == 0 {
        let Npk = get_npk_from_address_preimage(Address_1);
        (Npk, 0)
    } else {
        let { Npk, timestamp_of_change } = last_entry;
        (Npk, timestamp_of_change)
    }
    
    let nsk = get_nsk(Npk);
    let nullifier = h(..., nsk)
    
    if (creation_timestamp < timestamp_of_change) 
        && (last_entry.length > 1) {
        // there were other nullifiers that could have been emitted already
        ensure_not_nullified_yet_recursive(note, last_entry);
    }
    
    nullifier
}


fn ensure_not_nullified_yet_recursive(note: Note, entry_to_process: DynamicArrayEntry<UpdatedAddressData>) {
    let { Npk, timestamp_of_change } = entry_to_process;
    let nsk = get_nsk(Npk);
    let nullifier = h(..., nsk);
    
    let anchor_block_header = context.get_block_header();
    
    // Check that the nullifier has not been emitted:
    anchor_block_header.assert_nullifier_does_not_exist(nullifier);
    
    if entry_to_process.index != 0 {
        // Recursively find earlier entries for which 
        // we need to demonstrate non-existence of a nullifier.
        let prev_entry = entry_to_process.get_prev_entry();
        
        // Recursively call this function:
        ensure_not_nullified_yet_recursive(note, prev_entry);
    }
    
}

#### Managing lots of nullifier non-membership proofs

Each time you rotate your keys, you'll need to do some one-off work:

- Record all not-yet-nullified notes that you own.
- Compute the nullifier for each note, under _all_ of your "old" nullifier keys.
- Take a snapshot of the archive tree just after the "new" keys take effect.
- Generate a proof of `ensure_not_nullified_yet_recursive` for each note, using the archive tree snapshot.

**Some cool realisations:**

**Realisation 1:**

You can generate a proof for `ensure_not_nullified_yet_recursive` for _all_ of your notes, at the time your newly-rotated keys take effect! You don't need to wait until the time at which you come to spend your notes. So all this extra recursive proving is effectively "free" if you've done it in advance: it doesn't slow-down your tx*.

The design would have to be:

- First call to `ensure_not_nullified_yet_recursive` is an Aztec function call (because on the happy path where no key rotation has happened, we'll just line-up a cheap 600-gate call, without actually making the call).
- Subsequent calls to `ensure_not_nullified_yet_recursive` would be vanilla noir programs, that can be verified within each other.
- It's **~28k gates** to verify an UH proof within an Aztec contract function, so we want to avoid those constraints on the happy path. We're happy to incur such extra constraints in these precomputed snarks, because it's not time-sensitive.

This incurs the least constraints on the happy path.

**Realisation 2:**

If you're rotating your keys for a 5th time (say), we might be able to architect things so that you don't need to redo the work of proving non-membership of your notes from "eras 1,2,3", but just extend that proof for "era 4".

**Realisation 3:**

A user might be able to outsource the proving of `ensure_not_nullified_yet_recursive` for all their notes. This would require a redesign vs the pseudocode above, to avoid leaking:
- Linking notes with their nullifiers (violating tx unlinkability);
- Leaking nullifier secret keys.

What would probably have to happen is the nullifiers would need to be computed within the user-generated proof (to avoid leaking the notes and secret keys), whilst the proofs of non-membership of those nullifiers would be done by a 3rd party.

So the recursive proof would be _"here's proof that this list of nullifiers didn't exist by this time"_, instead of _"here's proof that this note wasn't nullified with any of these old nullifier keys by this time"_.

This 3rd idea is similar to the ZCash Tachyon ideas, in a way.

#### What if one of your newer Addresses is used inside a note?

We've been talking about the `Address_1` inside the note being the original user's address, because then we can lookup the address in the registry.

I guess, ideally, it would always be this original address that gets put inside a note.

If a _later_ address (comprising a later set of keys) were to be used, we'd have trouble looking-up that later address in the registry. I suppose we could introduce a new mapping in the registry, to map from each new address back to the original address. Then to do a lookup, we'd lookup the new address to get the original address; then lookup the original address to get the newest keys. But that's double the reads. Sounds scary though. We'd have multiple addresses pointing to 1 original address.