Key Rotation 2025

[Mike]

Key Rotation 2025

Copying over an internal hackmd, originally written around July

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.aka “Pretty Good Key Rotation”.(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 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 (at the time of writing) 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:

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.

Disclaimer

The information set out herein is for discussion purposes only and does not represent any binding indication or commitment by Aztec Labs and its employees to take any action whatsoever, including relating to the structure and/or any potential operation of the Aztec protocol or the protocol roadmap. In particular: (i) nothing in these posts is intended to create any contractual or other form of legal relationship with Aztec Labs or third parties who engage with such posts (including, without limitation, by submitting a proposal or responding to posts), (ii) by engaging with any post, the relevant persons are consenting to Aztec Labs’ use and publication of such engagement and related information on an open-source basis (and agree that Aztec Labs will not treat such engagement and related information as confidential), and (iii) Aztec Labs is not under any duty to consider any or all engagements, and that consideration of such engagements and any decision to award grants or other rewards for any such engagement is entirely at Aztec Labs’ sole discretion. Please do not rely on any information on this forum for any purpose - the development, release, and timing of any products, features or functionality remains subject to change and is currently entirely hypothetical. Nothing on this forum should be treated as an offer to sell any security or any other asset by Aztec Labs or its affiliates, and you should not rely on any forum posts or content for advice of any kind, including legal, investment, financial, tax or other professional advice.

[KevinLomax]

Will there be work to propose an audited upgrade proposal to include key rotation in Aztec in 2026?