# Maps of Multiple Types ([#2820](https://github.com/AztecProtocol/aztec-packages/issues/2820))
## Problem Statement
When private data is stored, new notes are created and have to be discovered by their 'owner' (whomever knows about this private data and wishes to use it in the future). This discovery process includes validating that the note is legitimate and actually exists in the state tree. To do this, the contract that supposedly created the note is asked to produce the note hash given the plaintext.
This requires that all contracts know how to hash any note created by them. Since a contract might produce notes of multiple types (e.g. addresses, structs, etc.), **they must be able to determine the type of the note** in order to know which hash method to apply.
We've used the notion of 'storage slot' to achieve this so far, but unfortunately many common use cases are not covered by this approach. This document describes possible solutions to this problem.
_Pictured here: note type woes._
## Current Art
### How Maps Are Different
**Singletons** are made up of a single note, identified by its storage slot. Example: the admin of a contract.
**Sets** are made up multiple notes, all of which are identified by the set's single storage slot. These notes are typically aggregated in some way. Example: the balance of a user, represented as the sum of all their unspent receipts.
**Maps** link keys to values of some other data type, each of which gets their own unique storage slot. Example: a map of user address to a set of value notes might represent the balance of different users in a token contract.
Maps are different because their backing data are notes stored in **multiple** different storage slots, unlike Singletons or Sets. These slots are dynamically computed for each key as `value_storage_slot = hash([map_storage_slot, key])`, which means that given a random storage slot it is not possible to determine to which map or key it corresponds to (if at all).
### `compute_note_hash_and_nullifier`
All contracts must implement this function, which receives a storage slot and note plaintext [^1] and returns the note's hash and nullifier, which are user-defined and depend on the note type. Contracts use the storage slot value to determine how to decode and hash the plaintext.
Consider a contract with two private state variables: a singleton ValueNote on storage slot 1, and a set of FieldNotes on storage slot 2:[^2]
```
fn compute_note_hash_and_nullifier(storage_slot, note_plaintext):
if storage_slot == 1:
return compute_value_note_hash_and_nullifier(note_plaintext)
elif storage_slot == 2:
return compute_field_note_hash_and_nullifier(note_plaintext)
else:
throw
```
We now wish to add to our contract's private state a map from user address to some struct. The map will be assigned storage slot 3, but recall that maps store each value at dynamically determined storage slots, and we can't relate these to the original storage slot of the map.
All we can do is assume that any storage slot that is not 1 or 2 corresponds to a value in our map:
```
fn compute_note_hash_and_nullifier(storage_slot, note_plaintext):
if storage_slot == 1:
return compute_value_note_hash_and_nullifier(note_plaintext)
elif storage_slot == 2:
return compute_field_note_hash_and_nullifier(note_plaintext)
else:
return compute_struct_note_hash_and_nullifier(note_plaintext)
```
This means **we can only support maps of a single type**. If we had a second map to a different kind of struct, we would not be able to know from the storage slot alone which of the maps we're using, and therefore which of the struct types we need to decode and hash.
## Proposals
We need to use some other information in addition to the storage slot in order to determine the type of the note.
### Using the Preimage Size
If each type has a different size (e.g. structs with a different number of fields), then this data would suffice. However, there's no guarantee that this will be the case, and even then differently-sized notes might be undesirable altogether since they leak privacy (the logs with the encrypted note will also have a different size).
### Adding a Note Type Field
Notes that are stored in maps could have a special leading field that indicates their type. This could then be used whenever the note type is ambiguous.
```
fn compute_note_hash_and_nullifier(storage_slot, note_plaintext):
if storage_slot == 1:
return compute_value_note_hash_and_nullifier(note_plaintext)
elif storage_slot == 2:
return compute_field_note_hash_and_nullifier(note_plaintext)
else:
type_identifier = note_plaintext[0]
if type_identifier == 1:
return compute_struct_note_hash_and_nullifier(note_plaintext)
```
This has the nice property of only adding extra data to the notes when its actually required, but also has significant downsides. This approach is quite error-prone, since developers must take care to add this special field to the underlying note type, meaning e.g. a set of value notes would be different from a set of value notes that are stored in a map. This type mismatch would likely also hurt reusability and lead to special-casing, while also worsening the learning experience.
### Extending the Note Header
This is essentially a generalization of the previous approach: instead of making some notes carry a type identifier, we instead extend the header to **always** include this extra field. `compute_note_hash_and_nullifier` would then use this new type identifier instead of the storage slot to determine which hash function to use.
The type identifier can be easily autogenerated. A simple approach would be to use the storage slot of the variable: in the above example the singleton and set would have equal storage slot and type identifier (1 and 2 respectively), while map notes would have unique derived storage slots but share the type identifier value of 3. A second map could then be assigned storage slot (and hence type identifier) 4, and so on.
```
fn compute_note_hash_and_nullifier(type_identifier, note_plaintext):
if type_identifier == 1:
return compute_value_note_hash_and_nullifier(note_plaintext)
elif type_identifier == 2:
return compute_field_note_hash_and_nullifier(note_plaintext)
elif type_identifier == 3:
return compute_struct_note_hash_and_nullifier(note_plaintext)
...
```
Because of this simplification, it is reasonable to expect we'd be able to automate all of this and **hide these implementation details from users**.
This does unfortunately result in a cost increase, since the larger note header results in an encrypted log size increase that makes it all the way to the Data Availability layer. Unlike storage slots however, the type identifiers only need to represent the different _types_ of data, and are independent of the number of values stored. In other words, a new type identifier is required for each state variable, regardless of however many notes or storage slots might be used by it. It might be therefore feasible to only use a few bits to represent this value.
Note that we still need to include the storage slot in the note header even if we don't use it to determine the note type, as it is required for other purposes.`
> ❗ This is the leading proposal: the rest of the discussion will assume this is the path taken.
## Implementation
- Yellow Paper: unchanged. This entire feature is built on top of the concept of encrypted logs, and does not require protocol changes. Note headers are an Aztec Noir construct.
- Aztec Noir: add the TypeIdentifier field to NoteHeader and populate it accordingly depending on the state variable type (for singletons and sets both storage slot and type identifier would be the same, in maps they'd be different).
- Contracts: update `compute_note_hash...` in all on contracts to receive an extra `type_identifier` parameter and determine the hashing method based on it. Remove the comments mentioning 'stuff of nightmares'.
- PXE:
- update `addNote` to receive an extra `typeIdentifier`.
- update block processing to decode `typeIdentifier` along with the rest of the note header values.
- change calls to `compute_note_hash_...` to also pass the `typeIdentifier` .
## Possible Future Improvements
### Reduced Data
As mentioned above, we can expect for each contract to only have a couple different values for the note type identifier (easily fewer than 50). Additionally, many state variables don't require this feature in the first place (namely singletons and sets), and therefore share note type identifier and storage slots. Both of these facts combined mean we could reasonably expect to be able to apply simple compression techniques that'd reduce the impact of having an extra (encrypted) field be published on the Data Availability layer.
### Computable Type Identifiers
While we can't get around publishing the note type identifier, we can avoid having to store the identifier inside note data structure during execution. This boils down to assigning each note type a value for their type identifier and then making that available via a function call.
These identifiers need to be unique across the entire contract, but using globally unique identifiers (e.g. a hash of the type name) has the downside of requiring multiple bytes. Manual assignment would be great in terms of space requirements, but very cumbersome and error-prone.
Instead, we can use Noir macros to automatically generate this values by listing all note types used in the contract's storage and then assigning each an incrementing value (similarly to how we might assign storage slots, except for note types instead of state variables). This has the nice side effect of minimizing the number of note type values and therefore how much space they require.
[^1]: Actually the contract's address and note nonce are also passed, but we can ignore those here.
[^2]: This pseudo-code example has been simplified to illustrate a point, the real version also includes other parameters such as the nonce.
Sign in with Wallet
Connect another wallet