# Note Discovery Summary

:::info
Author: Mike
This note is PUBLIC.
:::

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.

---

# High level summary

Many blockchain privacy protocols enable a transaction "sender" to relay private information about the transaction to some "recipient". For example, a private token protocol might enable a sender to create new "note commitments" for the recipient, and relay the underlying private note data to the recipient via a ciphertext which accompanies the transaction payload.

We wish to find a way to "tag" each ciphertext, so that the recipient (and only the recipient) can detect that the ciphertext is intended for them. In particular, this approach needs to be significantly faster than having the recipient brute-force trial-decrypt every ciphertext that's ever been submitted to the blockchain.

Existing tagging techniques have some limitations. Many approaches aim to outsource the detection of ciphertexts to a remote server, without revealing to the server the exact set of matching messages.

- **Brute-force trial-decryption**
- This works up to a point. But the amount of work a user needs to do increases with the number of notes in the system. If Aztec intends to (hopefully) have billions or trillions of notes (and ciphertexts) then a consumer device would not be able to sync from scratch via brute force in a reasonable amount of time.
- Interestingly, the main bottleneck is not decryption time (although that is a factor). The main bottleneck is broadband speeds. Ordinary users would take an unacceptably long time to download all the ciphertexts.

- **[Fuzzy message detection](https://eprint.iacr.org/2021/089.pdf) (FMD)**
Tags each ciphertext with a "fuzzy detection key". This enables a server to identify which ciphertexts belong to the recipient, but also identifies non-matching ciphertexts with some false-positive rate. Depending on the false-positive rate, the server will only gain a 'fuzzy' understanding of which notes belong to the recipient.
- A drawback of this approach, is that it might not withstand statistical analysis and other attacks. Over time, it's possible for the server (and indeed other entities) to piece together information about users. See more [here](https://fc22.ifca.ai/preproceedings/9.pdf)
- Penumbra have devised a [variant of FMD](https://protocol.penumbra.zone/main/crypto/fmd.html). Iiuc, this might also not withstand analysis, although more investigation is needed here.

- **[Oblivious Message Retrieval](https://eprint.iacr.org/2021/1256.pdf) (OMR)**
- This enables a server to detect the recipient's ciphertexts and return them to the recipient, without the server learning which ciphertexts (or notes) belong to the recipient. This uses FHE, and has some performance limitations, especially at the scale Aztec hopes to achieve.
- Jay has actually implemented a prototype of OMR, to benchmark its capabilities.

- **Brute-force tag detection, and PIR**
- Rather than trying to trial-decrypt every ciphertext, a slight optimisation is for each ciphertext to be accompanied by a 'tag', and for the recipient to initially only download and process all of the tags. If a particular tag indicates that it is intended for the recipient, the recipient can then request the corresponding ciphertext by its index.
- Private Information Retrieval (PIR) schemes could be used by the recipient to request ciphertexts by index. PIR schemes have some performance limitations, especially at the scale Aztec hopes to achieve.

- **"Tag hopping", and PSI**
- Borrowing ideas from frequency-hopping encryption. The sender and recipient agree on a pre-determined sequence of tags. Every time the sender sends the recipient a ciphertext, they accompany the ciphertext with the next tag in the sequence.
- A server can gobble up all tags and all ciphertexts, and arrange them in a key:value database (where the tags are the 'db-keys', and the ciphertexts are the 'db-values').
- Using Private Set Intersection (PSI) techniques, the recipient can make queries to the server, requesting the db-values for a collection of db-keys. The db-keys that the recipient requests would be the next tag(s) in the sequence(s) (the recipient might have established many sequences of tags with many counterparties). Crucially, the server wouldn't learn the actual values of the db-keys (i.e. of the tags). The server would then return the ciphertexts back to the user, without learning which ciphertexts have been returned.
- **This is our current favourite avenue of research**, but it's not without its problems.
- [More info](#Tag-Hopping-and-PSI) further down the page.

- **Alternatives???** :)

---

# More info about Aztec, specifically

## 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!

---

# Tag-Hopping and PSI

A suggestion by Charlie last year (and tweaked a bit below) was for Alice to convey a `Shared_Secret` to Bob, which could be used to derive a deterministic sequence of 'tags'. Let's call this a **"Tag Sequence Initialisation Transmission" (TSIT)** (or something? Naming suggestions welcome!).

> We were colloquially calling it a "handshake", but it's non-interactive.

> A simple sequence would be `tag_i = hmac(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, providing the `tag` and receiving the corresponding ciphertext, if it exists.

## Establishing a tag sequence is problematic too!

If Alice and Bob can meet in person, or can perform a TSIT 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 submit a TSIT to 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 TSIT 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_TSIT_Pk`.
- Bob could iterate through all handshaking attempts, and try to generate a `Shared_Secret` using his secret key and the `Ephemeral_TSIT_Pk`.
- Once Bob has learned of a `Shared_Secret`, he can generate the sequence of `tags`.
- Bob can then start making PSI queries 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 _TSITs_. The (hopefully reasonable) assumption* is that there will be _far fewer_ TSITs on the blockchain than there will be new notes. So syncing TSITs 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, we 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.

Perhaps we could prevent collisions by inserting each tag into the Aztec protocol nullifier tree (which prevents duplicates). Then if a device's tx is rejected by the network, it could simply try the next tag in the sequence. This would have the unfortunate side effect of greatly bloating the nullifier set (since a tag (and hence a nullifier) would be needed for nearly every new commitment).

Or perhaps Alice's devices could just chat to each other?

Or perhaps the PSI scheme can permit occasional duplicate entries against the same tag. (Jay has verified that this approach is possible).

---

## PSI (private set intersection)

Jay's currently doing some promising research in this area.

"I ran a few tests on complete setup. For a dataset of 16M with 256 bit entries, to request 3500-4000 values takes 3.5 seconds on a machine with 16 cores (m6a.16xlarge on ec2). Upload communication cost is around 22 Mb and download communication cost is around 14 Mb."

Coming soon, queries to a data set with 1 billion entries. (And maybe even bigger soon).