# Farcaster Message Identifiers

*Contributors: Paul Fletcher-Hill, Varun Srinivasan, Shane da Silva, Dan Romero*

## Problem

Farcaster messages should each have a unique identifier. Applications need unique id's to compare two messages quickly. Some messages, like replies and reactions need them to point to their parent. Databases can use them as a unique key to store and look up values.

Today, Farcaster calculates and stores a 256-bit Blake2B hash on every message. When a reply wants to link to a message or a hub wants to store a message, they construct an identifier of the form `<fid>:<hash>` to uniquely reference the message. The `fid` prefix is not necessary for uniqueness but makes it easier to look up data sharded across many systems.

Unfortunately, these identifiers are 512-bits long and take up a lot of space. Each additional byte on an id increases total storage costs by 1% since ids are repeated [many times for indices](##Appendix). These ids also have no causal ordering, and Hubs resort to generating keys of the form `<fid>!<timestamp>!<hash>` to perform efficient time-sorting.

## Prior Art

Timestamp-based schemes like UUIDs, Snowflake IDs and Hybrid Clocks generate ordinal identifiers to solve similar problems in distributed systems. They can be implemented in Farcaster and may provide some savings over the current solution.

However, Farcaster already encodes some of this data in other fields like the fid and hash. Instead of creating an entirely new ordinal identifier, we can combine these thre fields to create a more space-efficient system.

## Solution

We propose a 320-bit id system of the form `<fid>:<timestamp>:<hash>`, where

- `fid` is a uint256 representing the user id for sharded lookups
- `timestamp` is a uint32 epoch timestamp starting from jan 1, 2022
- `hash` is a uint32 blake2b hash of the message bytes

The identification scheme is ordinal first by user id, then by time and finally by message hash. Datastores like Hubs often use Sorted String Tables where keys are stored sequentially on disk. Such identifiers can be used as keys to easily shard data stores by users, or to quickly look up the earliest or latest data generated by a user without needing expensive indices.

Combining a seconds timestamp and hash causes fewer collisions than a more precise timestamp and leverages data already stored in the envelope.

### Usage

References must ids of the form `<fid>:<ts-hash>`, where `ts-hash` is obtained by combining `message.data.timestamp` and `message.envelope.hash` into a uint64. An example of the id for a cast from user 123 might look like this: `123:16665069151918922938`.

Database keys can use the same form or extend it with additional fields to optimize ordering. For instance, Hubs will likely use keys of the form `<fid>:<set>:<ts-hash>` to make purging the earliest member of a set easy.

### Timestamps

A 32-bit seconds timestamp with an epoch of Feb 1, 2022 can track dates until Mar 10, 2158. An upgrade will be required to timestamps in the next century but this seems like a reasonable tradeoff for avoiding 64-bit timestamps which take up a lot more space.

Second-level precision is sufficient since timestamps only order unrelated messages like top-level casts. Replies, reactions and deletes all have a pointer to their parent cast, ensuring they are never rendered before their parent in a chronological feed.

### Handling Collisions

The downside is that identifers for two distinct messages can collide. The user experience is annoying since Hubs will drop one of the messages. However, we can show that a collision is only likely if a user generates tens of thousands of messages every second since a 32-bit hash collision only approaches a 50% collision rate after generating 2^16 messages.

A malicious user can exploit collisions to change history. Two casts could be pre-computed with different messages ("i love bears", "i hate bears") but with the same `ts-hash value`. The user broadcasts the first message, waits for likes to accrue and then broadcasts the second one to replace it on the hubs.

Fortunately, most message properties cannot be changed without invalidating the message itself. A cast collision, for example, must be generated by twiddling just the embed and mentions fields while keeping all other fields constant. While the bit-space can be iterated over quickly, the probability of finding a collision is extremely low given a well distributed hash function.

### Future Proofing

Hash functions can be changed by modifying the `hashType` field to indicate that a new algorithm or digest length is being used. This change can happen in a backwards compatible way at any time and we expect that hash functions may be changed periodically as newer, faster or more secure implementations emerge.

Timestamps cannot be changed as easily since the epoch is encoded into the value of the time itself. While it is possible to follow a similar scheme, we do not expect the timestamp requirements to change as often (perhaps once a century) and therefore breaking changes are acceptable for the gains in storage space by omitting a `timestampType` field.

### Storage Savings

An identifier is stored once on every message, once on every message that points to it and once for every index built on the Hub. Assume that 50% of messages point to other messages, and the average number of indices for a message on a Hub is 5.5 (see Appendix below). That give us the rough heuristic that each key is stored ~7 times.

Our new approach saves ~168 bytes per message. Given that the average size each message was ~530 bytes this represents a 30% improvement in Hub data storage.

### Open Questions

- Show that an intentionally malicious collision is practically impossible to compute

## FAQ

**Why not use the signature instead of the hash for the identifier?**
A change in signers would change the signature which changes the identifier of the message and breaks all references. We expect users to resign their messages when migrating between clients and this would make that impossible without losing all your likes and replies permanently.

**Why not use a larger size hash to reduce collisions?**
Every byte saved in a key reduces the Hub's storage requirements by as much as 1%. If there isn't a practical attack vector to be exploited then the savings justify the additional risk taken.

**Why not compute the hash as needed instead of saving it on the message?**
Computing hashes "just in time" would save 4 bytes on every message. But apps have no way to verify the correctness of identifiers they compute and a small misconfiguration would lead to broken references. The additional fragility does not justify the space savings at this time.

**Why not place identifiers only on casts since other messages aren't referenced?**
Casts are expected to be > 50% of the messages on the network so this would save an average of 2 bytes per message. However, this makes it impossible to address other messages permanently, which is not worth the relatively small savings.

**Why not combine the identifier in a single message field?**
A `timestamp-hash` can be constructed and stored inside the `message.data` field if the hash excludes the timestamp itself but encodes all other message properties. This avoids having to combine the fields to generate the key. While copying such hashes becomes easier, verifying them requires taking apart the timestamp and computing them requires constructing a new timestamp-excluded message object.

## Appendix A: Rocks DB Keys

### All Messages

- <fid>!<set indicator>!<message key>: <flat message>
- <fid>!<messages by signer idx>!<signer>!<type>!<message key>: true

### Casts

- <fid>!<cast adds idx>!<cast key>: <message key>
- <fid>!<cast removes idx>!<cast key>: <message key>
- <casts by parent idx>!<parent cast key>!<cast key>: <message key>
- <casts by mention idx>!<mention fid>!<cast key>: <message key>

### Reactions

- <fid>!<reaction adds idx>!<reaction type>!<cast key>: <message key>
- <fid>!<reaction removes idx>!<reaction type>!<cast key>: <message key>
- <reactions by cast idx>!<cast key>!<message key>: true

### Follows

- <fid>!<follow adds idx>!<user id>: <message key>
- <fid>!<follow removes idx>!<user id>: <message key>
- <follows by user idx>!<user id>!<message key>: true

### Signers

- <custody events idx>!<fid>: <custody event>
- <fid>!<signer adds idx>!<signer key>: <message key>
- <fid>!<signer removes idx>!<signer key>: <message key>

### Verifications

- <fid>!<verification adds idx>!<verification key>: <message key>
- <fid>!<verification removes idx>!<verification key>: <message key>

### Profile

- <fid>!<profile idx>!<profile key>: <message key>