Addresses, keys, and sending notes (Dec 2023 edition)

This post outlines the requirements, functional and not, that we want to meet for addresses, encryption keys, and sending notes in Aztec, along with a proposal that fits the bill and a few other candidates we considered in discussions with @Mike. All feedback is welcome!

A fundamental action in Aztec is sending an encrypted note to another user. This involves looking up their encryption public keys, their preferred method of note tagging (and possibly encryption as well), executing and proving the execution of such methods, and broadcasting the resulting encyrpted note through the chain. See Challenges in abstracting encryption for a previous post on this topic.

Requirements

  • Users must be able to choose their note tagging mechanism. We know the solution we have today is not ideal, so we expect better note discovery schemes to be designed over time. The protocol should be flexible enough to accommodate them and for users to opt in to using them as they become available.
  • Users must be able to receive notes before interacting with the network. A user should be able to receive a note, eg representing a token transfer, just by generating an address. It should not be necessary for them to deploy their account contract in order to receive a note.
  • Applications must be able to safely send notes to any address. Sending a note to an account could potentially transfer control of the call to that account, allowing the account to control whether they want to accept the note or not, and potentially bricking an application, since there is no catching exceptions in private function execution. See the motivation for the pull-over-push pattern in Ethereum for more info, or the king-of-the-hill Ethernaut challenge.
  • Addresses must be as small as possible. Addresses will be stored and broadcasted constantly in applications. Larger addresses means more data usage, which is the main driver for cost. So we want addresses to fit in at most 256 bits, or ideally a single field element.
  • Total number of function calls should be minimized. Every function call requires an additional iteration of the private kernel circuit, which adds several seconds of proving time.
  • Encryption keys should be rotatable. As a nice-to-have, should a user have their encryption private key leaked, they should be able to rotate them so that any further interactions with apps can be private again, without having to toss out their account and create a new one.

Addresses and encryption abstraction

To meet the requirement of having small addresses, we define an address as the hash of a set of public keys, a class identifier (ie a pointer to the code for the contract), the constructor arguments (to guarantee deterministic deployment addresses to be used for counterfactual deployments), the deployer address, a salt, and an identifier for an encryption and tagging method.

This last parameter allows an address to define how notes should be encrypted and tagged for it. The protocol will keep a shortlist of valid methods, and support additional ones through upgrades. The rationale for not letting the account freely implement its own encryption and tagging methods is to avoid security issues when an app sends notes to an account (remember king-of-the-hill!).

Note that our initial requirement was to support note-tagging abstraction and not encryption abstraction. However, since we already need to support one, including the other was pretty much free.

As an alternative, we entertained the idea of using the public key as the address. However, couldn’t come up with a scheme where the address could double as a public key and a commitment to all the data needed to guarantee deterministic deployments (ie the class identifier, constructor arguments, and deployer address), all while fitting in a single field element (well, we did come up with a scheme, but @jean demolished it).

Canonical registry

We propose a global singleton contract, deployed at a well-known address, where accounts register their public keys and their preference for encryption and tagging methods. This data is kept in public storage for anyone to check when they need to send a note to an account.

An account can directly call the registry via a public function to set or update their public keys and encryption method. New accounts should register themselves on deployment. Alternatively, anyone can create an entry for a new account (but not update) if they show the public key and encryption method can be hashed to the address. This allows third party services to register addresses to improve usability.

An app contract can provably read the registry during private execution via a merkle memebership proof against the latest public state root. Rationale for not making a call to the registry to read is to reduce the number of function calls. When reading public state from private-land, apps must set a max-block-number for the current transaction to ensure the public state root is not more than N blocks old. This means that, if a user rotates their public key, for at most N blocks afterwards they may still receive notes encrypted using their old public key, which we consider to be acceptable.

An app contract can also prove that an address is not registered in the registry via a non-inclusion proof, since the public state tree is implemented as an indexed merkle tree. To prevent an app from proving that an address is not registered when in fact it was registered less than N blocks ago, we implement this check as a public function. This means that the transaction may leak that an undisclosed application attempted to interact with a non-registered address but failed.

If an account is not registered in the registry, a user could choose to supply the public key along with the preimage of an address on-the-fly, if this preimage was shared with them off-chain. This allows a user to send notes to a recipient before the recipient has deployed their account contract.

Pseudocode

The registry contract exposes functions for setting public keys and encryption methods, plus a public function for proving non-membership. Reads are meant to be done directly via storage proofs and not via calls to save on proving times.

contract Registry
    
    // Note that we may need to store additional information aside from encryption_key and method_preference
    public mapping(address => {encryption_key, method_preference}) registry
    
    // The valid_methods list should be expanded via protocol upgrades that update this contract
    public enum valid_methods
    
    public fn set(encryption_key, method_preference)
        assert method_preference in valid_methods
        registry[msg_sender] = {encryption_key, method_preference}
        
    public fn set_from_preimage(address, encryption_key, method_preference, class_id, constructor_hash, salt, deployer)
        assert address not in registry
        assert hash(encryption_key, method_preference, class_id, constructor_hash, salt, deployer) == address
        registry[address] = {encryption_key, method_preference}
    
    public fn assert_non_membership(address)
        assert address not in registry

Apps that want to provably encrypt and tag a note for an address should check the registry first, and then optionally fall back to the preimage if supplied via an oracle call. This would be implemented as a helper function in the aztec-nr library.

fn send_note(recipient, note)
    
    let block_number = context.latest_block_number
    let public_state_root = context.roots[block_number].public_state
    let storage_slot = calculate_slot(registry_address, registry_base_slot, recipient)
    
    let encryption_key, method_preference
    if storage_slot in public_state_root
        context.update_tx_max_valid_block_number(block_number + N)
        encryption_key, method_preference = indexed_merkle_read(public_state_root, storage_slot)
    else if recipient in pxe_oracle
        address_preimage = pxe_oracle[recipient]
        assert hash(address_preimage) == recipient
        encryption_key, method_preference = address_preimage
    else
        call_public_function(registry_address, "assert_non_membership", [recipient])
        return
        
    execute method_preference with encryption_key, recipient, note

Note the three code paths when sending a note to a recipient:

  • If the recipient is in the public registry, the application uses the public key and encryption method declared there.
  • If not, the user assembling the tx can choose to supply the address preimage and load the public key and encryption method from it.
  • If not, the application can prove that it doesn’t know how to create a note for a given address, and skip it.

The last code path is what prevents attacks that could brick an application trying to encrypt private state to an address for which its public key is unknown. A simple example would be the king-of-the-hill contract in which the king defines an arbitrary payout address.

Execution

Let’s drill down on the last pseudocode line. We propose having a contract for each valid encryption and tagging method. Each contract would have a standard interface with an encrypt_and_tag function that receives a recipient address, their public key, any additional data associated with the address in the registry, and the note. This function would be responsible for encrypting the note, tagging it, and broadcasting it.

These singleton contracts would potentially be stateful. This allows the implementation of, for example, note tagging methods that require creating additional state, without having to create state in the account contract itself. This solves any issues associated with creating state in an undeployed contract in the event of having to send a note to an undeployed account.

This pattern requires one function call per note, which may not be acceptable given the requirement of minimizing the number of function calls. We then propose a new method for batching calls: instead of a directly issuing a private call, a contract may enqueue a message to be handled by a target contract. This message, much like an enqueued public call, is not executed synchronously, but enqueued for later execution. Once the private call stack has been emptied, the kernel circuit is then responsible for executing these calls, grouped by target contract.

In pseudocode, the application would do something like:

fn send_note(recipient, note)
    let encryption_key, method_preference = ...
    context.enqueue_call_to(method_preference_contract_address, "encrypt_and_tag", [recipient, encryption_key, note])

And a specialized kernel iteration, once the private call stack is empty, would dispatch these calls like:

fn execute_enqueued_private_calls(context):
    let unique_targets = unique context.enqueued_calls[].target
    for target of unique_targets
        let messages = context.enqueued_calls[].filter(enqueued_call.target == target)
        call_private(target.address, target.function_selector, messages)

By implementing encryption contracts as message handlers, we can batch all note encryption and tagging operations that use the same method within a transaction in a single function call. Given we anticipate few unique encryption and tagging methods, batching should provide considerable improvements.

As a further optimization, we could have handler contracts implement the same function with multiple batch sizes. The message could then be targeted not to a specific function selector, but to a merkle root of all the implementations of the same function, and then the kernel chooses the one that best fits the current batch size.

In pseudocode, the handler contract would look like the following:

contract SimpleEncryptor
    for BATCH_SIZE in 1..32
        fn encrypt_and_tag(requests[BATCH_SIZE])
            for request in requests
                ...

The calling application contract would then enqueue a call to the merkle root of all 32 encrypt_and_tag(requests[BATCH_SIZE]) selectors, and the kernel would pick one, and constrain it to be in the merkle tree.

Alternatives

The original idea was not to have whitelisted contracts that implement the encryption methods, but to introduce the concept of protocol functions, which are functions blessed by the protocol that a contract could include in its interface. However, this new concept required a bigger change in the protocol to implement. It was also unclear how calls could be batched, or how a contract could update their choice of protocol functions. Also, protocol functions were expected to run in the context of the account contract itself, which required running code and potentially updating state in undeployed contracts (though we may end up supporting this, stay tuned!).

Aside from how the encryption methods were implemented (whitelisted contracts or protocol functions), we considered storing the public key and encryption method preferences in the account contract public storage, removing the need for a registry. However, this requires standardising a set of storage slots for keeping the public key and encryption method preferences, which could get accidentally overwritten by a contract. It also made it difficult to keep an easy-to-update whitelist of valid encryption methods. It also requires the deployment of an account contract in order to publicly store its public key.

We also considered not storing the public key and encryption method preference at all, and just broadcasting them as an unencrypted event on deployment, along with the entire address preimage. Nodes would need additional logic to track these broadcasted preimages, so that app contracts could load them via an oracle call, and prove the preimage hashes to the recipient address. This is a small performance improvement over keeping keys in storage, since it requires less hashing for the storage membership proof. However, this disallows key rotation and updating encryption method preferences, which is a nice property to have.


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.

49 Likes

Does this assume that keys still follow the same BIP-32 based scheme for address etc?

21 Likes

On the idea of enqueueing private calls to be batched by target contract, does that mean those calls have to be the end of the chain? Or can they make further calls? e.g.

  1. Alice calls ‘send note’ to send to Bob, this enqueues a call to encrypt_and_tag(bob, note)
  2. Alice has never sent notes to Bob before, so Bob’s tagging mechanism means that a call is needed to HandshakeContract::createHandshake(bob).
  3. The handshake contract creates a shared secret and calls Bob’s encryption method ‘encrypt(bob, secret)’, Alice’s encryption method encrypt(alice, secret), emit_unencrypted_log(encrypted_secret_bob) and emit_unencrypted_log(encrypted_secret_alice).
  4. Secret returned from handshake contract back to encrypting and tagging contract.
  5. Shared secret is stored (not broadcast as that was done during handshake).
  6. An index is needed for tagging. This might need to be created as a note for Alice so she can later retrieve it. So encrypt_and_tag(alice, index_note) is called.

Alice sends multiple notes to bob during a single transaction. So the above is repeated but without the handshake as it was already done. The shared secret is re-used and the index note is consumed and the index incremented.

Not sure if the details above are exact but hopefully it illustrates a possible flow.

13 Likes

We’re assuming we’re not doing BIP32-like derivation for app-siloed encryption keys, since we couldn’t find an IBE scheme that fit the bill. We will be doing derivation for nullifier secrets though, but that’s solved.

What we haven’t defined is what exactly will be stored in each entry of the registry. Today we have a bunch of keys identified (incoming viewing, incoming internal, outgoing, nullifying, tagging). If we can derive them all from a single master one, then the registry may be able to just store that one; otherwise, we’ll need to store more information per address.

19 Likes

I think that the overall kernel logic should be:

  • If there’s something on the call stack, pop it
  • Else, if there’s something on the enqueued messages, batch by target and run it
  • Else, finish
  • Loop

So any sync call performed from an enqueued message handler would be executed on the spot. Still, it probably makes sense for message handlers to be able to enqueue more messages if needed. In other words, these handlers should be able to do everything a regular function does.

Hmm this means that contracts that implement encryption and tagging methods need to expose as separate functions encrypt_and_tag and encrypt (and possibly tag). We hadn’t considered that, good to know!

Super clear. If I understand correctly, in the event that a handshake is not needed, then there’s no need for additional calls, right?

23 Likes

Super clear. If I understand correctly, in the event that a handshake is not needed, then there’s no need for additional calls, right?

Well, I still think there might be a call to encrypt_and_tag(alice, index_note) without the handshake. Either way, don’t take the example as being concrete, more an illustration.

Overall though this sounds great. Going completely off-topic, why don’t we do this across the board? If I do 10 token transfers in a single transaction won’t I end up with 10 sets of largely identical function calls? Identical in contract address and selector that is.

Or have I missed something? Just a thought.

5 Likes

Good point, the tag_index note needs to be encrypted with Alice’s preferred scheme, not Bob’s. Though I think that Mike was working on an approach where that note wasn’t needed and the index was instead stored in a nullifier, but it’s an optimization.

Absolutely. That’s one of the drivers for abstracting this batching mechanism and not making it something exclusive to note encryption and tagging. For the token transfer example, it hinges on whether you need one of the transfers to complete in order to proceed, but then it’s for the application to decide how it wants to structure the calls.

Another driver for abstracting this mechanism is that we may need it ourselves for building the kernel circuit, so we may already have to build some primitives to support it in Noir.

6 Likes

Heya, was just talking with @spalladino on Slack and just to add a note on this:

An app can always choose not to check the registry, opting to emit notes encrypted with my original encryption key (the one that’s part of the my address’ pre-image). This would break key rotation for users of that app.

2 Likes

Does this mean that each account contract deployment has to make a call to the public registry, leaking they are deploying an account? Or can I always operate without touching the registry if my wallet doesn’t support key rotation?

1 Like

You can operate without ever touching the registry as long as you trust that whoever is sending you a note will actually do so. In a payments scenario, this trust assumption is valid, since the sender wants you to get the money they are sending you. In a more complex scenario, like filling a swap order where the sender can get the funds in it and not send you the encrypted note with your side of the trade just to grief you, you probably want to register.

This is rellated to the decision “what should an app do if it needs to provably send encrypted data to someone who has not provably disclosed their encryption public key”. We got two options:

  • Put the burden on the sender. Sender should do all off-chain efforts to get that public key so they can provably encrypt and emit the note. This can lead to security issues if the recipient does not disclose the public key and ends up bricking an application flow.
  • Put the burden on the receiver. If the receiver has not publicly disclosed their public key, a sender has no obligation to send them a note, even if the application forces them to do so. This is the option we’ve preferred.

Still, the send_note implementation in this post would be part of the aztec-nr library, and not part of the protocol. Apps have the choice to use an alternate method, like skipping the registry (as @alexghr said), or preferring to halt execution by putting the burden on the sender, if it makes sense for their use case.

Edit: Forgot to address one of the main points. If your wallet doesn’t support key rotation, there’s still a need for a registry, so that senders can prove that you haven’t broadcasted your keys and can skip encrypting a note for you.

Edit2: If we wanted to remove key rotation altogether, we could probably use nullifiers instead of public state (since pubkeys would be immutable) for the registry, but that’s pretty much it.

4 Likes

A few more comments after discussions with @jaosef and @Mike.

TLDR: if we want to be able to update the implementation of encryption and tagging methods via protocol upgrades (which seems desirable, in order to fix bugs or improve performance), then we should store the contracts that implement them in protocol-reserved addresses (much like ethereum precompiles), which removes the need for an actual whitelist in the registry. The process of adding a new encryption method is just adding a new precompile via an upgrade, and no changes to the registry are needed.

How to store encryption method preferences

We have not yet defined how the “encryption & tagging method preference” is expressed, either on the address preimage or in the registry. One option is using the address of the contract that implements that method. However, that means that we cannot change the implementation of the contract if we find a bug or optimization without the address changing.

A better option seems to be storing an enum (1,2,3…) that maps to new methods as they are added in the registry, which requires less bytes to store, and allows a protocol upgrade to update the mapping from index to address. However, this requires to look up that mapping, which cannot be hardcoded into app code if we want to update it.

Seems like the best option is to borrow the concept of “precompile contracts” from Ethereum: we store in the addresses 0x1, 0x2, 0x3… the contracts that implement these methods. Addresses declare their preference to these short addresses, and apps make calls to them. And when the kernel needs to dispatch a call to 0x1, it looks up the code for 0x1 based on a hardcoded table in the kernel circuit.

How to update the list of valid encryption methods

When an account registers itself in the registry, the registry needs to check that the encryption method it chooses is valid. To do it, it keeps a whitelist, which needs to be upgradeable as the protocol rolls out new vetted encryption methods.

If we keep this whitelist in public storage, then a protocol upgrade must insert a new value in the registry’s public state, or craft a tx that calls a privileged update_whitelist function in the registry that takes care of doing so. The update_whitelist function should implement an access control check such that only a protocol upgrade can trigger it.

Alternatively, we could just remove the whitelist, and assume that all valid encryption methods will be stored in addresses 0x01 to 0xFF (255 should be more than enough, right?). Accounts can declare any precompile address within that range when registering. And to prevent a malicious account from registering a value that’s still unused and bricking an app, the kernel can route any call to an unused precompile address to a noop, so “encrypting a note” using a yet-unregistered encryption method does nothing.

4 Likes