# Note Discovery Summary

:::info
Author: Mike
This note is PUBLIC, so Jay can read it :)
:::

We're using the term "Note Discovery" to mean the scheme through which encrypted note information can be (privately) discovered by the intended recipient of that information.

## Notes in Aztec

An Aztec user can store custom information in the form of a 'Note'.

A Note is basically a struct of information:

struct MyNote {
    a: Field,
    b: bool,
    c: Field,
}

> Note: throughout, 'Field' means the scalar field of the altBN-254 curve. So it's a 254-bit field.

In our current design, there's technically no limit to the amount of data members a custom note struct can contain. Here we're showing an example where the note's preimage contains 3 fields. It could be many more fields.

> Note: we might discover (during our research into the best 'Note Discovery' scheme) that we cannot enable users to create _any_ size of struct. We might determine that an upper bound on note size is required for a particular Note Discovery scheme.

## Note Hashing in Aztec

In Aztec, extra Aztec-specific information gets 'combined' with a Note, through various stages of hashing, before that note's hash is stored in the Notes Tree:

> Note: `h()` is lazily being used to mean "some hash function which outputs a `Field` element". We're yet to decide on the exact hash. Possibly pedersen. Possibly poseidon.

### `inner_note_hash`

`inner_note_hash = h(storage_slot, ...my_note)`

where `storage_slot: Field` is a field element which helps domain-separate what different notes represent within the scope of a contract. (This is much like how Solidity has the concept of a storage slot in a contract). The lazy `...` syntax here is like the javascript 'spread' operator for arrays.

E.g. `inner_note_hash = h(1, my_note.a, my_note.b as Field, my_note.c)`.

### `siloed_note_hash`

`siloed_note_hash = h(contract_address, inner_note_hash)`

where `contract_address: Field` is an identifier of the contract which is writing this note to the tree. This ensures contracts cannot cross-contaminate each others' storage spaces.

### `unique_siloed_note_hash`

`unique_note_hash = h(nonce, siloed_note_hash)`

where `nonce: Field` is a unique value which is derived and injected by the kernel circuits of the protocol, to prevent Fairie Gold attacks. This `nonce` is derived from the nullifiers which are created as part of the transaction, but that's outside the scope of this doc.

### What gets added to the Note Tree?

The `unique_note_hash: Field` is added as a leaf in the note tree.

### Unravelled

So the note hash added to the tree is:

`h(nonce, h(contract_address, h(storage_slot, ...my_note)))`

So that's:
- 3 `Field` elements; plus
- However many `Field` elements the serialised version of `MyNote` requires.

## Aztec Txs

An Aztec tx is invoked through a single function call. I.e. a user passes some arguments to some function of a smart contract. This first function might make calls to other functions. And those functions might make calls to other functions.

A single function will be able to create `NUM_NEW_NOTES_PER_FUNCTION` new note hashes.
A single transaction will also be limited to an upper bound of `NUM_NEW_NOTES_PER_TX` note hashes.

A function or tx doesn't _need_ to produce a number of new note hashes equal to these upper bounds (it may produce fewer). It can emit `0` values instead of actual new note hashes (although that will have implications on hiding which function has been executed).

> We won't be able to come up with concrete numbers until we've tested our GalacticGoblinHonk proving system with our protocol circuits, to see how slow the proofs are for different circuit sizes. We also will need to adjust the numbers based on the limitations of our 'Note Discovery scheme' candidates.

For Note Discovery, `NUM_NEW_NOTES_PER_TX` is a more important number.

## The Note Tree

- An append-only merkle tree
- Leaves and nodes of the tree are `Field` elements
- The tree will likely be $> 2^{40}$ high (over 1 trillion leaves)
- The hash function will be snark friendly, e.g. Pedersen or Poseidon.

### Why is the tree so big?

We expect _a lot_ of notes will be created.

> We won't be able to come up with concrete numbers until we've tested our GalacticGoblinHonk proving system with our protocol circuits, to see how slow the proofs are for different circuit sizes. We also will need to adjust the numbers based on the limitations of our 'Note Discovery scheme' candidates.

But, as an example:

Assuming the following:
- tx throughput of 100 tx/s.
- up to 16 new note hashes can be added per tx.
- I.e. `NUM_NEW_NOTES_PER_TX = 16` (perhaps)

... that would be 5 billion new leaves per year! So 1 trillion leaves would give 200 years of runway.

> If we can, we'd increase the `NUM_NEW_NOTES_PER_TX` to be as big as we can get away with, without ruining proving times, or on-chain gas costs. So we're not ruling out the possibility of more-than 16 new note hashes per tx. This is just illustrative.

### Tree epochs

We might be able to break the tree into epochs, but that feels like a separate issue from note discovery?

## Note Discovery

If Alice calls a function, and that function creates a note for Bob, how does Bob discover this note?

### Note Encryption

Our current plan is to enshrine an encryption scheme at the protocol level. Something like AES or chacha20.

Any function which emits new note hashes, is able to emit 'encrypted logs' which can contain an encryption of the preimage data of each note hash.

A symmetric encryption scheme will require a setup such as:

`Bob_Pk = bob_sk * G` (for some Grumpkin generator point `G`, so `Bob_Pk` is a Grumpkin point)
`ephemeral_sk <- random`
`Ephemeral_Pk = ephemeral_sk * G`
`Shared_Secret = ephemeral_sk * Bob_Pk = bob_sk * Ephemeral_Pk`

Use the `Shared_Secret` as the symmetric encryption key.

#### What data is broadcast on L1?

Bob will be able to see the following data for every tx:

- New note hashes
- New nullifiers
- Encrypted Logs
- (other data which isn't relevant to this topic)

#### What must a note ciphertext contain?

See the [Unravelled section](#Unravelled):

- `Ephemeral_Pk` (a Grumpkin point, which could be compressed)
- `contract_address`
- ~~`nonce`~~ - not needed in the ciphertext: it can be derived from the publicly visible new nullifiers data.
- `storage_slot`
- `...my_note`

That's quite a lot of `Field` elements per note:
- 1 point
- 2 `Field`s
- n `Field`s, depending on the size of the serialised custom Note struct.

> We might be able to cleverly amortise the `contract_address` and `Ephemeral_Pk` values across multiple notes, if several notes originated from the same function, or are intended for the same recipient, but we haven't considered such an optimisation yet, and such an optimisation wouldn't be enforceable at the protocol level.

### Note Discovery, continued

So, we need a way for Bob to efficiently discover that a ciphertext is intended for him, without anyone learning.

## Trial decryption bottlenecks

The main bottlenecks which make trial decryption impractical are:
- Bandwidth
- Bob might not have a good enough internet connection to download all ciphertexts in a reasonable amount of time (or at all). Especially if he tries to sync to the network after many years away.
- Decryption speed
- Trial-decrypting all those ciphertexts will take too long!

## Handshaking, Tagging and PSI

A suggestion by Charlie last year (and tweaked a bit below) was for Alice and Bob to perform a 'handshake', in order to establish some `Shared_Secret`. This `Shared_Secret` could then be used to derive a deterministic sequence of 'tags'.

> A simple sequence would be `tag_i = hash(Shared_Secret, i)` for a sequence $\{ i \}$.

The idea would then be:
- Every note ciphertext would be accompanied by a `tag`.
- A server could download all of the ciphertexts that are ever emitted to the network (as Ethereum L1 calldata) and store those ciphertexts against their associated tags in a key:value database.
- Bob could then query the server, via PSI (if possible!!!), providing the `tag` and receiving the corresponding ciphertext, if it exists.

### Handshaking is problematic too!!!

If Alice and Bob can meet in person, or can perform a handshake via web2 (e.g. email or whatever they fancy), then they can establish a sequence of tags easily. Hooray!

BUT... in some cases, Alice and Bob will not know each other, and they won't know anything about each other. Alice might only know Bob's ethereum address. Alice might only know an address (and the address might be owned by an anon).

> E.g. in Ethereum defi, you rarely know the identity or web2 details about the counterparty to your trade or lending etc. You only know their Ethereum address.

> Warning: the following is hand-wavy and imprecise - sorry!
> **See [here](https://hackmd.io/@aztec-network/HJBf3tW_3) for a more detailed (but still not rigorous, nor validated) suggestion.**

So... how does Alice handshake with Bob, before creating a note for Bob, so that she can establish a sequence of tags, and then send the first such `tag` along with the new note's ciphertext?

Well, we could naively implement a brute-force handshake discovery scheme! We could establish the `Shared_Secret` in much the same way we dicussed [earlier](#Note-Encryption):

- As part of the transaction which creates a note for Bob, Alice could optionally broadcast an `Ephemeral_Handshaking_Pk`.
- Bob could iterate through all handshaking attempts, and try to generate a `Shared_Secret` using his secret key and the `Ephemeral_Handshaking_Pk`.
- Once Bob has learned of a `Shared_Secret`, he can generate the sequence of `tags`.
- Bob can then start making PSI queries (if possible!!!) to the server for his note ciphertexts, sent by Alice!

> This scheme is similar to [Stealth Address tagging in Ethereum](https://vitalik.ca/general/2023/01/20/stealth.html).

Now, although this is still brute force, it is only brute forcing _handshakes_. The (hopefully reasonable) assumption* is that there will be _far fewer_ handshakes than there will be new notes. So syncing handshakes will be practical and possible.

> * _This assumption should be questioned and challenged, though. In a lot of defi, you interact with a new person each time you transact..._

---

> Pulling numbers out of thin air: if we assume 100 million people use Aztec, and each person handshakes with 100 other people, that's 10 billion handshakes that Bob would need to sift through. That's quite a lot. If each handshake payload is something like 64 bytes, that's 640GB data. For an internet speed of 10Mbits/s, that's 512,000 seconds to sync handshakes... that's 6 days. But... I can't think of anything better yet...

### Race conditions

Phil also mentioned there are possible race conditions. If Alice sends a tx from Device 1, and then sends a tx from Device 2, and both txs create a note for Bob, then the same `tag` would be used by both devices, causing a database entry collision in the server.

We could either accept that collisions are possible (and put the honus on Alice's devices to communicate with each other before sending transactions). Or, we could prevent collisions by inserting each tag into the Aztec protocol nullifier tree (each nullifier in the tree is enforced to be unique by the protocol). Using the nullifier tree in this way would be very bad, imo, because it would 'blow up' the number of nullifiers created in each tx (there would need to be a nullifier for every new commitment!!!).

This topic needs more thought and discussion. Maybe race conditions could be avoided in some other way.

---

### PSI (private set intersection)

There's a lot of handwaving above. But if we assume handshakes are possible, the question remains:

**Could we use PSI to query a note ciphertext from a server, using a `tag` as a 'lookup key' in the server's DB?**

**Key size**: we could probably design it to be a single `Field` element.

**Value size**: a note ciphertext. See [here](#What-must-a-note-ciphertext-contain). 1 `Point`, 2 `Field`s, and n more `Field`s (depending on the size of the custom note).

Perhaps we can compress the `Point` to 1 `Field` and 1 bit for the sign, but to be safe, let's say a `Point` is 2 `Field`s.

So the size of a DB entry is roughly (4 + n) `Field` elements. We have simple examples where n is 3. That's a total ciphertext of size 4 + 3 = 7. But I can envisage examples where we might want n to be larger.

**Perhaps we could explore the practicality of PSI for:**

- Number of DB entries: $2^{40}$ (1 trillion).
- Perhaps the tree can be broken into chunks or something?
- Size of each DB lookup key:
- A scenario where each key is 1 `Field`
- (I don't think we'll be in a scenario where each key is 2 `Field`s, but if it's easy to model, it'd be worth seeing).
- Size of each DB entry:
- A scenario where each entry is 7 `Field`s
- A scenario where each entry is 8 `Field`s
- A scenario where each entry is 12 `Field`s
- A scenario where each entry is 16 `Field`s
- Can the number of Fields per entry vary?
- If yes, understanding how PSI would work.
- If not, we'd need to pad entries in the DB with zeroes, so that all entries are the same size, because some custom note ciphertexts will not use all of the `Field`s.

**Perhaps we could also explore this handshaking scheme, to determine its practicality, or if there are better ways to establish a sequence of tags?**

**Perhaps we could explore whether there are completely different approaches from anything described in this document?**