Google Drive
Gist
Clipboard
or
or
By clicking below, you agree to our terms of service.
Sign in with Wallet
New to HackMD? Sign up
| Syntax | Example | Reference | |
|---|---|---|---|
| # Header | Header | 基本排版 | |
| - Unordered List |
|
||
| 1. Ordered List |
|
||
| - [ ] Todo List |
|
||
| > Blockquote | Blockquote |
||
| **Bold font** | Bold font | ||
| *Italics font* | Italics font | ||
| ~~Strikethrough~~ | |||
| 19^th^ | 19th | ||
| H~2~O | H2O | ||
| ++Inserted text++ | Inserted text | ||
| ==Marked text== | Marked text | ||
| [link text](https:// "title") | Link | ||
|  | Image | ||
| `Code` | Code |
在筆記中貼入程式碼 | |
| ```javascript var i = 0; ``` |
|
||
| :smile: |  |
Emoji list | |
| {%youtube youtube_id %} | Externals | ||
| $L^aT_eX$ | LaTeX | ||
| :::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Do you want to remove this version name and description?
Syncing
xxxxxxxxxx-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
SubscribeFarcaster 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. Thefidprefix 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. 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>, wherefidis a uint256 representing the user id for sharded lookupstimestampis a uint32 epoch timestamp starting from jan 1, 2022hashis a uint32 blake2b hash of the message bytesThe 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>, wherets-hashis obtained by combiningmessage.data.timestampandmessage.envelope.hashinto 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
hashTypefield 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
timestampTypefield.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
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-hashcan be constructed and stored inside themessage.datafield 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
Casts
Reactions
Follows
Signers
Verifications
Profile