# Farcaster Improvement Proposal: Links

Source: https://github.com/farcasterxyz/protocol/discussions/85
Kiwi News: https://news.kiwistand.com/stories/Farcaster-Improvement-Proposal-Links?index=0x645cb9f9a3fdb3ff94ef6f9ea160d232c60e9389956e422889d80255f9427517858e4643
Submitted by tim on 2023-05-11 UTC, 1 upvote, 0 comments

## Summary

Farcaster Improvement Proposal "Links" by Varun Srinivasan and Cassandra Heart proposes a new message type that stores long-lived, directed, typed relationships between users, such as follows, so that they can be kept on Hubs and make switching applications easier. Each user can store 2,500 links, a limit chosen after analysis of Warpcast follow data, and a Link message is at most 164 bytes, adding up to 382 GB per million users. The proposal says Links will be included in the 2023.5.31 protocol release, and Hubs must not accept Link messages until 2023.6.14 (1686700800000 in unix epoch), when older versions are shut down.

## Article

FIP: Links

Title: Links Type: Implementation FIP Author: Varun Srinivasan (gh: @varunsrin , fc: @v), Cassandra Heart (gh: @CassOnMars , fc: @cassie)

Abstract

A proposal to add Links, a new message type that expresses relationships between users.

Problem

Users of social networks have explicit relationships with other users (e.g. following, subscribing) which is used to generate feeds or make recommendations. Such relationships cannot be stored on Hubs today which makes switching applications difficult for users.

Specification

We propose a new Message type called a Link, which is a long-lived, directed, typed relationship between two users (e.g. Alice follows Bob). Links can express different types of relationships and be upgraded to express relationships between users and non-user objects.

Links are similar to Reactions, except that they never expire due to a time based limit. They require active management from applications to ensure a good user experience when limits are reached (see Appendix A and Appendix B). Each user can store 2500 links, which was chosen after analysis of existing behaviors (see Appendix C). A Link message is at most 164 bytes, which will add a total of 382 GB / million users at most.

Message Data

Add a new LinkBody type to MessageData at the empty position 8.

message MessageData { .... oneof body { ... LinkBody link_body = 8; .... } }

Message Type

Add LINK_ADD and LINK_REMOVE types at the empty positions 5 and 6.

enum MessageType { ... MESSAGE_TYPE_LINK_ADD = 5; MESSAGE_TYPE_LINK_REMOVE = 6; ... }

Link CRDT

Add a Link CRDT which validates and accepts LinkAdd and LinkRemove messages. The CRDT also ensures that the message m passes these validations:

m.signer must be a valid Signer in the add-set of the Signer CRDT for message.fid

A conflict occurs if two messages have the same values for m.data.fid, m.data.body.target and m.data.body.type. Conflicts are resolved with the following rules:

If m.data.timestamp is distinct, discard the message with the lower timestamp.

If m.data.timestamp is identical and m.data.type is distinct, discard the LinkAdd message.

If m.data.timestamp and m.data.type are identical, discard the message with the lowest lexicographical order.

The Link CRDT has a per-user size limit of 2,500.

Link Message

A Link is a relationship between two users which can be one of several types. Links are added with a LinkAdd message and removed with a LinkRemove message which shares a common body structure.

message LinkBody { string type = 1; optional uint32 displayTimestamp = 2; oneof target { uint64 fid = 3; } }

A Link message m must pass these validations and the validations for LinkAdd or LinkRemove:

m.signature_scheme must be SIGNATURE_SCHEME_ED25519.

m.data.body must be LinkBody.

m.data.body.type must be ≤ 8 bytes.

m.data.body.target must be a known fid.

m.data.body.displayTimestamp must be ≤ m.data.timestamp

A LinkAdd message m is valid only if it passes these validations:

m.data.type must be MESSAGE_TYPE_LINK_ADD

A LinkRemove in a message m is valid only if it passes these validations:

m.data.type must be MESSAGE_TYPE_LINK_REMOVE

Link APIs

Hubs must also provide the following APIs to fetch Link Messages:

// Returns a single Link message of a specific type between two fids rpc GetLink(LinkRequest) returns (Message); // Returns all Links for a given fid, with optional parameters to filter and sort then rpc GetLinksByFid(LinksByFidRequest) returns (MessagesResponse); // Returns all Links to a given fid, with optional parameters to filter and sort then rpc GetLinksByTarget(LinksByTargetRequest) returns (MessagesResponse); // A convenience alias on GetLinksByFid rpc GetAllLinkMessagesByFid(FidRequest) returns (MessagesResponse); message LinkRequest { uint64 fid = 1; string link_type = 2; oneof target { uint64 target_fid = 3; } } message LinksByFidRequest { uint64 fid = 1; optional string link_type = 2; optional uint32 page_size = 3; optional bytes page_token = 4; optional bool reverse = 5; } message LinksByTargetRequest { oneof target { uint64 target_fid = 1; } optional string link_type = 2; optional uint32 page_size = 3; optional bytes page_token = 4; optional bool reverse = 5; }

Rationale

Why are applications incentivized to publish the follow graphs of their users?

Farcaster cannot enforce publishing of data, but apps are strongly incentivized to publish casts (or users won't get engagement and churn) and weakly incentivized to publish reactions (or users will eventually notice and be annoyed). Publishing follows and other links can be incentivized if users and apps reward others who maintain follow relationships (e.g. airdrops for long term followers). There is some probability that such incentives are too weak to enforce publishing links and we may need to roll back this change.

Why not just extend reactions with a new 'Follow' type and fid target?

Reaction CRDT's expire messages to optimize for storage of a greater number of recent messages, since those are more valuable. The same is not true of Links, where older messages might be more valuable than newer messages and time-based expiry is a bad user experience.

Why is there a string type instead of an enum type like in Reactions?

A string type allows a greater deal of flexibility without requiring protocol changes, at the expense of being slightly larger in size and adding more complexity for apps to interpret and render them. If this works well, it might be worth upgrading reactions to have string types instead of enum types.

Release

Links will be included in the 2023.5.31 protocol release. Adding Links is not backwards compatible since it may cause Hubs to believe they are out of sync. Hubs must not accept Link messages or respond to Link RPC queries until 2023.6.14 or 1686700800000 in unix epoch, when older versions of the Hub are shut down.

Appendix A: Compaction

Message Graph CRDTs impose a per-user limit on the number of messages, and both add and remove messages are counted in the limit. A user who follows 2,500 people and then unfollows 500 people still takes up 2,500 slots because they have 2000 add and 500 remove messages. When the 2501-th message is received, the oldest message is kicked out which is usually a follow, resulting in 2000 add and 500 remove messages.

Applications can improve this UX by re-signing and re-ordering the add messages by giving them a greater timestamp than follows. When the 2501-th message is received, it replaces a remove message, resulting in 2001 adds and 499 removes. This allows users to take advantage of the maximum size allowed by CRDTs. Since timestamps become unreliable, links have an optional display timestamp property that can be set by users to indicate the “real” time of the action.

Apps should pick a full-ness limit (80%) and a compaction threshold (e.g. 1%). If a user adds a message using the application which uses up more than 80% of the CRDT’s limit and more than 1% of the messages are taken up by remove messages, a compaction is triggered. Apps should not trigger compaction constantly or in the background since this can result in network thrash, which may trigger hubs to rate limit the user.

Appendix B: Curation

When users approach their CRDT limit and there is no more room for compaction, some links must be removed to make space for new ones. Apps can make curation suggestions to users to remove unnecessary follows based on interaction or usage patterns.

Since CRDT’s are eventually consistent it may be possible the application is not aware of all the links yet. A user may have 2,495 links on one Hub and 2,500 on another which are in the process of syncing. Apps should therefore recommend curation well before this limit to prevent the oldest link from unintentionally being pruned. As a safety measure, apps can keep track of pruned LinkAdd messages and prompt the user to see if they intended to clear out the links. If not, the user can choose to remove some other Link and regenerate the pruned Link.

Appendix C: Follow Graph Analysis

The following data is taken from Warpcast, which implements a centralized form of follow relationships between users. Warpcast has ~ 12,000 registered users.

Number of follows created by users who were active within the last 90 days:

95th percentile: 307 99th percentile: 1898

Percentage of users active in the last 90 days with > x follows:

1000: 1.63% of users 2000: 0.96% of users 3000: 0.71% of users 4000: 0.61% of users 5000: 0.53% of users