FIP: Countable Messages (Leaderboard Events)

[michaelhly]

Abstract

Leaderboards enable Farcaster clients to build social components that promote gamification, engagement, and discovery. The frequency of updates (write operations) necessary to keep leaderboards up-to-date in real-time make leaderboards difficult and cost prohibitive to maintain on-chain.

Hubs, on the other hand, are well-suited for real-time updates:

Unlike blockchains, Hubs use a different consensus model to make changes possible in real-time. Changes are synchronized using a delta-graph, which is a data structure that uses CRDT's to achieve real-time updates with strong eventual consistency.

Terms

• node: Point inside a graph connected by directed edges
• countable: A set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers
• operator: A mapping or function that acts on elements of a space to produce elements of another space (we will primarily focus on arithmetic operators)

Proposal

Farcaster should define a MessageData format designed for arithmetic to enable the construction of arbitrary leaderboards.

[Insert picture of many nodes labeled countable nodes with numbers all pointing to a single node labeled target]

=>

[Insert picture of a leaderboard titled target with row values of the countable nodes rendered by a Farcaster client]

Specification

I propose to introduce a new countable message type, which defines a countably finite set, that represents an arithmetic delta a user may accrue in relation to another user, a cast, or some FIP-2 compatible embed. Leaderboards can be constructed by aggregating a collection of countable messages (series of arithmetic deltas) of the same target(s). We define the necessary protos as follows:

enum CountingOperator {
    UPSERT = 0;
    ADD = 1;
    MULT = 2;
    MOD = 3;
    EXPO = 4;
}

message CountableTarget {
   oneof target {
     uint64 fid = 1;     // for `from` -> `to` relationships between two users
     Embed embed = 2;     // see FIP-2
   }
}

message CountableAddBody {
    CountingOperator operator = 1;    // operator for this countable value
    int32 value = 2;    // countable value for arithmetic 
    uint32 decimals = 3;    // number of decimals for formatting
    CountableTarget primary_target = 4;    // *root* node this message points to
    
    // optional _secondary_ node this message points to
    optional CountableTarget secondary_target = 5;
    
    // optional value for representation of a rational number
    optional uint32 divisor = 6;  // if set to 0, this message should be interpreted as NaN
    
    // metadata supplied by the client that originates the countable message
    optional google.protobuf.Struct origin_meta = 99;     // we can also just use map<string, string>
}

// Remove all countable messages associated with the primary target 
message CountableRemoveBody {
     CountableTarget primary_target = 1;
}

• Counting operators
  • upsert type should be used when a target's countable values need to be replaced by a new value
  • add type should be used when a target's countable values need to be added together
  • multiply type should be used when a target's countable values need to be multiplied together
  • mod type should be used when the remainder needs to be taken from a target's countable values
  • expo type should be used when a target's countable values need to be exponentiated together
• Counting operators should be applied on a set of countable messages according to timestamp order
• Optional metadata can be supplied by the originating client providing instructions on how the countable message should be handled by other clients

Message Validation

• If the primary_target or secondary_target is a CastID embed, validate that the CastID exists
• If the primary_target or secondary_target is a fid, validate that the fid is registered
• origin_meta can be at most 128 bytes (Rationale: We give enough room for an ECDSA signature — 65 bytes, we leave 63 bytes for other kinds of metadata)
• signature_scheme of the countable message must be SIGNATURE_SCHEME_ED25519

Countable CRDT Limits

• The countable CRDT has a per-primary_target size limit of 300 (Rationale: I chose based on the number of Game 5 NFT mints)
• Last-write-wins with some finite expiration
• Both limit and expiration should be fine tuned accordingly based on real usage rates

Countable APIs

Hubs must also provide the following APIs to fetch + stream countable messages:

// Returns a set of countable messages in timestamp order
rpc GetCountablesByTargets(GetCountableByTargetsRequest) returns (MessagesResponse);

rpc StreamCountablesByTargets(CountableTargets) returns (stream MessageResponse);

message GetCountableByTargetsRequest {
	CountableTargets targets = 1;
	optional int32 limit = 2;
	optional bool reverse = 3;
}

// If the secondary_targets are set, return the countable set on the intersection of primary and secondary targets
// If the secondary_targets are not set, return the countable set of the primary target only 
message CountableTargets {
    CountableTarget primary_target = 1;
    repeated CountableTarget secondary_targets = 2;
}

Out of Scope

Long-term persistence

Clients should expect hubs to persist countable messages for a finite duration. For long-running leaderboards, clients should consume countables as ephemeral events and persist countable messages outside of hubs.

Ordering by countable value

Clients should not rely on hubs for reliable ordering of countable messages by their values. Algorithms used to determine the ordering of countable messages (or collections of countable messages) by value may vary from client to client.

Trust model for timestamps

Currently, timestamps are user-reported. We should explore a better trust model for timestamps at the protocol level such as application specific signers at a later time. For now, clients are free to submit a verifiable app-specific signature in origin_meta, and publish its signing key somewhere for other clients to verify that the counting message was produced from a particular client.

Recounting

In the event of network failures (or other failures), consuming clients may miss countable messages that fall out of the CRDT limit.
Consuming clients should be able to send a request to the originating client for a recount.

We can introduce a recount CRDT message set, where consuming clients ask the originating client to re-publish the updated countable message set for requested targets. The proto message for the recounts may look like:

message RecountBody {
     CountableTarget primary_target = 1;
     optional CountableTarget secondary_target = 2;
}

After receiving the recount message, the originating client should publish countable messages with the UPSERT operator for consuming clients to update their countable set. (We may need to augment the CountableAddBody message with additional fields for recounts to be handled properly, but we'll leave that out of scope.)

There aren't enough clients on the Farcaster network today, so requests for recounts can be done ad-hoc outside of Hubs. Also, app-specific signatures on the protocol level would help consuming clients verify that countable messages submitted for recount were submitted by the same originating client.

Other Use Cases

• Click here for an example Farcaster client that can be built using countable message types
• Counting watches for a cast
• Counting the number of allowed participants for a gated channel

[danromero]

Interesting proposal. A few questions:

1. Do you have a hypothetical example of where two different apps would want to share a leaderboard?
2. Could you use existing messages today to accomplish this (albeit, less efficiently and requiring more regex)?

[davidfurlong]

Farcaster messages have a maximum finite length consisting of a finite set of characters - they are finite and neither uncountable nor bijective to the set of arbitrary strings.

I still don't really understand this - correct me if I'm wrong, but it seems like you're saying that you think it's a bad abstraction to use a string datatype in a database for storing numbers, which I agree with, but farcaster isn't a database for storing arbitrary data, adding more complexity to it has a cost, and there are some challenges distinct from databases, wherein different farcaster apps need to have a fallback way of interpreting and displaying content in the network. Messages as strings are currently the way that structured data can get stored in a human readable format that is also parseable. For example there isn't a dedicated 'event' message type, including necessary fields for date, time and location of the event, instead eventcaster uses a preset string format for it, so that each client doesn't need to figure out how to make it human readable.

I think there are many potentially interesting use cases for storing arbitrary data on hubs, including the storage of numerical data, for uses like leaderboards, or arbitrary json, to make it easier for farcaster apps to interoperate, and many use cases we haven't even thought of yet. However it's somewhat unclear to me today exactly which data we should try to store within farcaster hubs vs stored elsewhere such as arweave, ceramic or some other more agnostic data storage layer.

[michaelhly]

Help me figure out how to do arithmetic on “💩💩”?

Should I do 💩+💩,💩x💩,💩^💩, or💩%💩?

[davidfurlong]

I think it's pretty clear, and if it isn't to you, or the apps that are sharing this abstraction, then, the string doesn't need to be “💩💩”, but can include more complex arithmetic if you're doing exponential 💩s like replying with "💩^💩"

[davidfurlong]

personally unsubscribing from this thread as I no longer think it's a sensible use of my time

[michaelhly]

Okay. Does there exist a one-to-one correspondence between the set of text field on CastAddBody messages and the set of natural numbers?

I'm trying to say that the set of num(operators) * 2 * 2^32 is strictly more countably finite than the set of arbitrary strings.

Rules for arithmetic are unambiguous, we shouldn’t use strings b/c they can be interpreted in many different ways.

[michaelhly]

Adding this message type should enable more developers to build apps that are orthogonal to Warpcast.

[michaelhly]

[michaelhly]

Source: https://www.eugenewei.com/blog/2019/2/19/status-as-a-service

[varunsrin]

Just read through the proposal, my initial reaction is that the design seems way more complicated than what the problem outlined needs.

If you want to build a leaderboard, couldn't we just get away with a message with a simple signed integer, numeric type? Apps can issue "delta counts" periodically, and you just sum them up to get the current count.

LMK if I'm missing some use cases that you're thinking of here.

[michaelhly]

Operators
I found that we should distinguish at least two operators:

• ADD: to sum up all delta counts in a set
• UPSERT: to have clients update their current count value to the provided count (necessary when the size of the countable set surpasses the CRDT limit, and clients need to know what count to start counting from)

I added the additional operators (*,^,%) to complete all arithmetic operations.

Targets
We need to point these countable messages to other nodes in the graph, thus the primary and secondary targets. I also included fid as a countable target to enable PvP-style leaderboards. This allows us to construct leaderboards not only based on the user who produced the message, but also the user who the message is targeted towards.

Origin metadata
Allow the originating client to attach metadata to the countable message. Defined size limit:

origin_meta can be at most 128 bytes (Rationale: We give enough room for an ECDSA signature — 65 bytes, we leave 63 bytes for other kinds of metadata)

Divisor
Support for rational numbers. This allows division and square root operations, which completes support for all arithmetic operations.

[michaelhly]

The initial draft of this FIP was about leaderboard events where:
Feed-based clients can use this message type to support leaderboards, which boosts user participation and engagement.
Non-feed-based clients can use the atomic unit (the count) of the leaderboard to compose features orthogonal to feed-based clients.

See examples here.

[varunsrin]

Closing due to inactivity