FIP: Introducing Ordering

[varunsrin]

Problem

Farcaster hubs are finding it harder to stay in sync. The problem is that user data changes at a very rapid pace. If you aren’t familiar with Farcaster’s sync model, read this before continuing.

It’s easiest to think of a hub as a bag of items or “deltas”. When a user creates a new cast, they add a delta into the bag. Hubs sync by comparing bags and copying new deltas. This works in the simple case but we run into problems because:

• Sync is slowing down. With over 500M messages, traversing the bag to find missing messages within a sync window is becoming difficult.
• Rate limits are local. Farcaster imposes a per-user per-hub rate limit to reduce spam. A user might trip limits on one hub only which could cause it to drift out of sync with others.
• Onchain state is missing. If a hub fails to read onchain events it may not be able to accept some deltas. Hubs get out of sync if either of them is missing an onchain event.
• Gossip fails occasionally. Hub A might have new messages for Alice and Hub B might have new messages for Bob. If these messages failed to make it into gossip, they may take hours or days to reach the other hub due to the randomness and unidirectional nature of sync.
• Pruning amplifies the problem. If two hubs end up with a different latest message for Alice due to rate limits, they will also choose to prune different messages. Therefore, Alice’s state differs across these hubs by 3 items instead of just one.

Hubs practically become inconsistent — sync may require multiple retries or waiting for a while, but that delay may cause more state changes which exacerbates the problem.

Hubs also find it hard to stay in sync with databases — apps like Warpcast face similar problems keeping in sync with the Hubs and end up with complex reconciliation processes.

Beliefs

1. Decentralized, global state is necessary. If there is no source of truth outside Warpcast, developers will be far less likely to invest time into Farcaster.

2. Sync should be easy for apps. It must be easy for developers to keep their applications in sync with the state of hubs.

3. Posting should be instant and without fees. Requiring onchain transactions or any kind of per-post fee creates too much friction for the network to reach escape velocity.

4. Storage and bandwidth must be constrained. If users are allowed freedom in either dimension we will just end up with a lot of spam.

5. Turing-completeness is undesirable. If people can build anything and there is no fee to use the network, spam of all kinds is inevitable.

Ideas

If deltas had stronger ordering many of our problems would become simpler. There are two ways we can approach this:

Account Ordering

Alice adds a sequence number to each delta creating a strict order or chain of deltas. She has a separate chain for each app key so that her apps don’t need to coordinate. Hubs enforce that sequence numbers are monotonic and handle conflicts by picking the delta with the lowest lexicographic hash value. The system is partially ordered, but not totally ordered.

Partial ordering makes many of our sync problems an order of magnitude easier:

1. Sync speed - sync is now O(N+M) where N is the number of unique app keys and M is the number of net new messages. this is 10x - 100x faster than the current sync algorithm.
2. Rate limits — hubs can limit sequence increments over time periods per account. malicious users can generate collisions and we would still need local rate limits. but they would be an order of magnitude less frequent, causing fewer sync issues.
3. Onchain state — hubs will still need some system to manage onchain state unrelated to account ordering. this is not improved by this solution, but can be solved with some effort.
4. Gossip failures — hubs can recover from a failed gossip by using sequence ids to identify when some messages failed to get transmitted.

The pros of account ordering are:

1. Implementation is easier — it’s a much smaller rewrite than implementing global ordering.
2. Decentralization — hubs are strongly decentralized and there are no single points of failure.
3. Shardable — the account model makes sharding the network by account trivial in the future.

The cons of this approach are:

1. Nonce management — clients must now manage sequence numbers for all of its users
2. Edge cases — sync is not as clean as with global ordering and there is more complexity at the sync level that needs to be managed.

Global Ordering

Alice submits deltas to a hub which puts them in the mempool. A sequencer periodically pulls messages out of the mempool and organizes them into blocks. Hubs fetch block from the sequencer and can also fetch them from each other in a p2p manner. The system is totally ordered across all messages.

Total ordering trivializes many of the problems we discussed:

1. Sync speed — sync is now O(N+M) where is the number of new blocks and m is the number of new messages, which is 100x faster. it is also simpler since it can be unidirectional.
2. Rate limits — can be easily enforced by the sequencer correctly.
3. Onchain state — can be packaged into blocks making this part simpler.
4. Gossip failures — message gossip failures and block gossip failures are easier to recover from since we can detect when this happens with sequences and refetch or reissue them.

The benefits of global ordering are:

1. Cleaner solutions — there are fewer edge cases and the solutions to the problems are more thorough in addressing the issues.
2. Cross-account constraints are easier — for example, you prevent users from writing a reply to a cast that doesn’t exist. this is possible with account harder but has more edge cases.

The downsides of global ordering are:

1. Sequencer is a single point of failure — without multiple sequencers, a failure in the sequencer means that deltas cannot move across apps.
2. Decentralization is harder — a sequencer is a central point of failure and we will need to develop a multi sequencer system run by independent parties, which is just harder to coordinate.
3. Implementation is harder — this is a rewrite of our system and will take longer than account ordering.

[vrypan]

Ordering makes sense. A variation of per-account ordering could be per-signer ordering (easier to maintain by each app).

[vrypan]

I didn't think of this. But if the benefits are worth it, there may some workarounds.

[vrypan]

However, per-signer ordering may be a good direction even without assigning hubs to signers.

[varunsrin]

the per-hub thing will be hard as @SamuelLHuber pointed out. most apps will end up using at least 2 hubs for reliability purposes. warpcast and neynar both do this today.

[vrypan]

@varunsrin, is the "app key" a signer? (In which case my per-signer direction is the same as you describe).

Re: hub-signer association, if it makes sync resolution easier, it could be just a suggestion: If you want to find the full chain, check this hub. No strong opinion for it, just adding it for consideration.

[varunsrin]

yes, trying to rebrand signers as app keys

[polymutex]

On the problem of rate-limiting enforcement causing desyncs: I'd suggest looking at Rate-Limiting Nullifiers (RLNv1 spec here, RLNv2 spec here). They would eliminate the problem of hubs locally enforcing rate-limits, because it is now the responsibility of the clients to prove that they are respecting specified rate-limits.

In such a model, rate-limits would no longer be per-(hub, account), but only per account (or per app key in the "account ordering" model). Hubs would check a message's RLN proof on receipt. Hubs having divergent views of rate-limiting state would no longer be a thing.

To avoid the proof-checking overhead on each message (for fully-synced hubs), hubs could continue to keep track of a local rate limit as they already do, but have that rate to be slightly stricter (i.e. slower) than the rate that the RLN would allow. Then, a hub only needs to actually check the RLN proof if its view of the local rate limit is exceeded. For the vast majority of users that do not spam, this would remove the need to check RLN proofs at all.

If an invalid proof is ever sent, the hub can simply "ban" the account from ever sending a message again by remembering to refuse all further messages from it. Farcaster already enforces some degree of mass-account-creation sybil resistance by enforcing paid registration, so this may be enough of a deterrent without requiring a complex slashing scheme involving posting the bad proof onchain.

Downsides:

• Involves relatively complex zero-knowledge cryptography (which may not be worth it if the rate-limiting problem isn't that bad), which is an implementation burden both on clients and servers. Waku has RLN libraries such as js-rln that may alleviate this.
• Might require specifying the intended per-account rate upfront. Implementing a way to change that rate-limit is not impossible but adds further implementation complexity.

[varunsrin]

RLN is a very interesting idea.

We might start with a simpler hub rate limit first but would be cool to implement this at some point in the future.

[polymutex]

Thanks! I agree that this seems secondary relative to the more immediate problem of speeding up syncs in general.

[TimDaub]

It sounds like this is a solution to the problem that is rate limiting? Or what Am I missing? Shouldn‘t the merkle sync still do well over a large set of messages otherwise?

Can you speak to why you‘re enforcing local rate limiting?

You have framed timestamping in the past as discretionary to users. You said an FC acc is a „user’s blog.“ You also ask users to pay for storage.

Why then do users have to be policed with rate limiting? Is it because they can still create an infinite amount of deltas, which cause cost to the system? So rate limiting plus the sharing per users can isolate load?

The crypto currency dev in me says that whatever causes a lot of load to the system must be taxed by introducing a financial cost, not by optimizing the system for better throughput.

[TimDaub]

I agree in general with what you are saying, but I don't think your metaphor maps onto the situation, as the rate limiting is addressing a specific user group that is putting the system under 'non-normal' load.

Additionally, timestamps are user-defined, so aren't rate limits anyways circumventable by users? The sync algo cannot differentiate between a message sent right now vs a message that happens to be synced via the merkle algo.

[varunsrin]

@vrypan's answer is correct. rate limits prevent overconsumption of bandwidth by flooding the network with gossip.

[TimDaub]

@vrypan's answer is correct. rate limits prevent overconsumption of bandwidth by flooding the network with gossip.

I have written everything above under this assumption too

[varunsrin]

in all seriousness, i don't understand what your question is anymore after trying to read over your comments.

[TimDaub]

Good luck with building a protocol by yourself then

[TimDaub]

The benefits of packaging messages into blocks would be that these blocks could get historically sealed.

I'm not exactly sure about the FC algo at the moment, but for Kiwi one vector for spam/manipulation is that while the node can reject gossiped messages that don't have a timestamp +- 5minutes from the wall clock, these messages could easily be inserted during the Merkle sync. So people can travel back in time. In user space, this is an issue when someone makes an outrageous claim and then pretends to have "said this already in the past" whereas this seems to also be a vector for circumventing rate limits or not?

If messages were finalized in blocks that had to be signed/sealed then this back traveling wouldn't happen anymore but to get to consensus on the block order and what they should include would probably be a rather complex undertaking.

[varunsrin]

yes, that would be a nice benefit of the block approach. but it's not a big consideration in picking the solution because there are many ways to build checks outside the protocol.

for example, you could have a service which fetches an accounts messages, creates a merkle-chain and publishes the hash. if that ever changes you would know that the person tampered with history.

[vrypan]

• in many cases any of the ordering solutions (account, global, etc) may be enough to prove that a message was submitted after other messages. I can set any date I like, but if my cast comes after a message dated today, it can't be 6 months old. Maybe not very strong assurance, but in most cases, good enough.

[vrypan]

Between Account and Global ordering, maybe we could consider Application ordering? If each App had their "chain", then the app is the sequencer.

1. Sequencer is a single point of failure — without multiple sequencers, a failure in the sequencer means that deltas cannot move across apps.

Already is a pof, for the users that use it.

2. Decentralization is harder — a sequencer is a central point of failure and we will need to develop a multi sequencer system run by independent parties, which is just harder to coordinate.

Users already trust the app

3. Implementation is harder — this is a rewrite of our system and will take longer than account ordering.

Not sure, but it seems simpler than global ordering. Plus, each app will have to maintain one nonce for all their users.

[varunsrin]

it's an interesting idea - i think it will be tricky because we don't have a canonical list of "apps" like we do users. so identifying all the chains we want to sync will be hard unless we introduce a new model to register applications.

[vrypan]

Each signer is associated with an app (I'm sorry, the nomenclature is not very clear). So, all messages signed by a signer associated with WC will be submitted as blocks by the WC sequencer. This can also include onchain activity associated with WC (signer approvals/revocations).

[vrypan]

High level idea:

Hub A receives a block. The block metadata include (app) FID, block signature, nonce, reference hub.

• Hub A checks that the signature corresponds to the (app) FID.
• Hub A checks that all messages included in the block are signed by a signer owned by the (app) FID.
• If nonce > 0, and Hub A does not have the previous blocks, it asks the reference hub for them, or it asks other hubs.

[varunsrin]

will think more on this approach

[vrypan]

Application ordering may have additional advantages. Since we will practically have N sequencers, it's easy to ask them to do some extra work, like respect user blocking. This work would happen "off chain", before each block is submitted, so it's easier to add features (much like WC adds new features at the app level). And then, if some of these apps/sequencers are not behaving according to the social consensus, other apps may ignore their blocks.

(This is inline with pushing work to the edge, that I mentioned in an other comment)

[adityapk00]

This is a great idea! The Account ordering idea specifically is a great one, solving many of the current bottlenecks with sync. I like it more than Global ordering, because it has additional advantages (depending on how its implemented)

• There's a nonce per fid per signer.

  • The signers/apps don't need to co-ordinate to create messages.
  • Creating new signers is trivial and local, since they will always start with nonce 0

• When a hub starts (or recovers after downtime), it can immediately know which messages are missing, and request them by ID/None (instead of hash, which will make sync substantially faster, since currently drilling down into the sync trie is very slow)

• We could keep the last N messages in the "active" trie, and offload older messages into an archive block (per fid) that is "sealed"

  • For eg, lets say an fid has 999 messages currently. After the message with nonce 1000 is merged in, the messages with nonces 0-99 are pruned from the active merge set, and "sealed".
  • The "sealing" process could be very similar to how the current CompactStateLinkMessage works. The messages are hashed together, sealing the set, and now become immutable, (similar to what the sequencer would do in the Global ordering option)
  • The sealed messages are synced by hubs as a single block, and don't need to be merged - Making the sync much faster, and specifically catchup sync significantly faster (since older, archived messages don't need to be merged).
  • This means we can make the active set smaller, improving the regular merge speed (The bottleneck for the current merge is looking up potentially conflicting messages from the RocksDB)

[varunsrin]

Sealing per fid is interesting - how would you think about handling pruning and revoking once a message is sealed?

[aditiharini]

Is it feasible to represent a "seal" message efficiently? CompactStateLinkMessage only deals with links which have very little state to represent and the churn on links alone is probably smaller than the churn across all the messages.

[vrypan]

I understand that some (many?) of the problems occur due to pruning (and we haven't seen large scale pruning due to expired storage units).

Here is a wild idea.

What if pruning was performed by a single (or select few) hub, and propagated across the network as a strictly ordered blockchain?

We can add checks that would allow hubs to reject these pruning blocks if the pruning "sequencer" misbehaved (due to a bug or if a malicious actor takes over). But it would 1) take some load from the hubs and 2) provide a universal point of reference on what has to be pruned, no conflicts.

[varunsrin]

In global ordering, that's exactly what would happen - the sequencer / selected hub would decided on pruning.

Are you proposing doing that for account ordering too? I think local prune is fine, it can be done reasonably deterministically.

[vrypan]

Yes, even if we don't add any type of ordering. My understanding is that some of the sync problems occur when one hub prunes some messages, while an other hub prunes other messages (for example, if an fid has reached their storage limits, and they submit two new messages to two different hubs).

What I suggest is that there is a pruning sequencer, and that hubs wait for the pruning blocks to tell them what to prune.

And we can have fallbacks, like triggering pruning manually on a hub, etc.

[varunsrin]

ah yes, this is true but it is because the other sync problems make pruning non-deterministic.

if we solve all these sync issues with account level ordering pruning might become a non issue. if it doesn't, i think this is a great direction to explore. .

[vrypan]

I think that even with app-account level ordering, pruning may be an issue (same fid, two apps, using two different hubs). But it would be great if it was solved (or solved for most cases), or became a non-issue because it does not affect syncing.

[vrypan]

Adding some more context/thoughts.

As a principle, I think we should add more work to the edges of the network. We've done this with shuttle for example, in one direction (read). I think we should also do it in the other direction (write).

Nonces is one such type of work: the app submitting a message has to maintain a nonce. Maybe we can add more, like packaging messages in blocks, or ordering messages, etc.

A pruning sequencer is in this direction (if it's actually needed).

[vrypan]

If we have ordering, how do we ensure that hubs maintain the whole state? Would it be possible for a hub to keep just N blocks and still appear as an active hub? Is this good or bad?

[varunsrin]

we have the same problem in an unordered system. it also exists in pretty much any distributed system like Ethereum.

in all cases, the solution is some kind of peer scoring to kick out malfunctioning hubs.

[deodad]

I want to dig into the cleaner solutions advantage of Global Ordering:

Pruning
In account ordering pruning is non-deterministic since messages are only ordered at the signer level but pruning happens at the account level. In global ordering pruning is deterministic. This will make sync faster and eliminates a class of sync problems.

Syncing a client - reading
With account ordering, a client that disconnects from a hub needs to do a full sync when reconnecting to a new hub to ensure no messages were missed. In global ordering it can resume from the last block it read.

Syncing a client - writing
With account ordering, a client that disconnects from a hub doesn't know whether messages it published made it to network or not. It's possible the hub that accepted a message never broadcasted it. The fact that a client needs to maintain a nonce for each signer compounds this problem. In global ordering the client can use a block hash to know if a message was included.

Remove the need for tombstones and message compaction
A remove can simply evict a message from the set. There's no need to keep around tombstones and clients don't need to worry about compacting removes.

It also seems the benefits mentioned around rate limits and cross-account constraints are more significant than I initially realized. With total ordering it becomes more practical to do things like:

• enforce hard storage limits — prevents accidental data loss in the case exceed a user exceeds their follow limit
• explore more dynamic forms of network regulation — as an example, storage / bandwidth could be purchased and consumed by an application rather than an account which could create lower barriers to entry for users (i.e. free sign ups)
• additional constraints like block and gating

[varunsrin]

censorship resistance is much more time sensitive on blockchains. if you're able to tip the scales, you can change who profits from MEV.

it's a different story with social networks. if you even have 20 sequencers and each of them gets to product a block every minute, as long as one of them accepts you casts the impact to you will be negligible.

[vrypan]

I was talking about censorship, not MEV extraction. Like, no ETH can move out of this address, because OFAC.

I think that we will find that building a system where anyone can spin up a network-size-capable sequencer and participate in block production is much more complicated than described. Why is this sequencer is acting in good faith? Why are they configured properly? What's the cost for not doing what they should do? For producing a bad block? Staking/slashing? Who decides when? How?

The more I think about Global ordering the less attractive it seems to me.

There's an other aspect. Even if we manage to have multiple sequencers, each sequencer must be able to support the whole network (for example if doing round robin). Which means that the requirements (hw, bandwidth) will go up as the network grows, and if we are successful, the cost of running one will be extremely high.

And in the end, we will end up with a few sequencers that will cost a lot of $$$/month to run, who will actually be the network, and satellite hubs who will just push deltas to the mempool and receive updates from the few validators hubs.

The more I think about all this, the more attractive Application-ordering seems to me:

• No extra trust assumptions: Users already trust applications with a signer (and more).
• "Sequencer" requirements are relative to the size of the app, which makes sense.
• Censorship is only possible at the app level, which is possible anyway.
• No single point of failure.

[varunsrin]

We explored this idea quite a bit since you suggested it and there seems to be one big challenge - conflict resolution.

Since blocks can be produced in parallel there is no way to resolve conflicts between them. Consider the case where I like something once on Supercast and once on Warpcast and they both issue blocks simultaneously with the like. There are now two distinct like objects to the same cast which violates the rule that each author can like each cast only once.

I don't think it's possible for apps to produce blocks in parallel without generating conflicts that must be resolved by some other step, which basically erodes most of the value of this change.

[vrypan]

I tried to put my thoughts on this in one place. Not claiming everything is solved, but to give a better overview of how I think about it.

Update: Using terms such as blockchain and blocks, creates a context and comes with a mental model that may not reflect the solution proposed. I consider these blocks just an upgraded version of the bundles we are currently using.

---

Every signing key is associated with an App FID. Every App FID submit its deltas as blocks. Each block contains:

1. The App FID
2. A number of deltas signed by a key associated with the App FID
3. A block hash
4. A block signature that proves that the block was signed by the App FID.
5. The block height
6. The hash of the previous block

This means for example that Warpcast will create its own blockchain, and Supercast its own separate blockchain.

Assumption 1: Applications are capable of maintaining their blockchain, without unreasonable increase in complexity and resources from their side.

I think this is a reasonable assumption. Each app is a centralized entity that can order the deltas generated by their users
and bunble them in blocks.

When a hub receives a block, it checks the validity of the block (signature). Then it checks if it has received the previous
block of this chain. If not, it will reject it (ideally, there can be a mechanism to search for the missing blocks from other nodes).

Each hub maintains the last N blocks of each chain. If it receives a block of heignht lower than last_seen-N, it will reject it.
This allows for some reordering, but only if reordering happens within the last N blocks. It also allows hubs to provide previous
blocks to other hubs that are missing them.

Once a block is accepted, the hub reads the deltas contained and update their CRDTs.

The chain-state of a hub is defined by a Merkle tree with leaves (ChainId, Block Heigigh, Last Block hash).

Assumption 2: Two hubs with the same chain-state will have the same CRDTs.

This means there is a function that takes as input all the blocks of M chains and generates the same result (CRDTs), regardless of the ordering of the blocks. This seems to be feasible given the current protocol specification.

My understanding is that submitting messages to hubs in a different order does not produce different global states.

OnChain Events

OnChain Events are not part of any app chain. Which means that they can affect the state of hubs in different ways, depending
on the events a hub has received or missed. However, this does not affect syncing. A healthy hub should be able to bring its
OnChainEvent up to date because the source of truth is the OP chain.

Applications can bundle OnChainEvents in their blocks. These events will have to be validated onchain by hubs, but it's a good practice to make sure that a hub has received all onchain events that may affect it from accepting or rejecting a block (invalid signers). OnChainEvents inside app blocks are only recommendations to help hubs, they do not replace hubs listening to onchain events and they should always be validated.

This does not add much overhead to hubs, in a healthy hub, this validation will be just a local DB lookup that will confirm that the event has already received.

Pruning

An other factor that affects the state of a hub is pruning. Two hubs may prune different deltas. While this does not affect syncing of app blocks, it may create inconsistencies between hubs. If we really want pruning to be global, I suggest we have a separate pruning sequencer that generates pruning events for all FIDs. Otherwise, if we accept that two hubs can be temporary in two different states, this means they may prune different deltas.

Initial sync

The initial sync of a hub consists of getting the CRDTs of an other hub, together with the last N blocks held per app chain.

Recovering from a long out-of sync period

If a hub looses connection to the network for a long period of time, it may be M > N blocks behind of other hubs, but since hubs will only keep the last N blocks of each app chain, the hub will not be able to find them.

There are two solutions to this problem.

1. Force an initial sync.
2. Let each app maintain one or more servers where the whole block history is stored and can be retrieved. This however does not solve the problem in the general case, because if the hub is not able to retrieve all the missing blocks from all app chains, it will still be out of sync. But it could be a solution for short or mid downtime periods, if the most active app chains offered it.

[vrypan]

Compared to what we do today:

• Rn, hubs group deltas in bundles and exchange bundles.
• My proposal requires that applications bundle deltas in blocks themselves and submit the blocks to hubs.

Since applications have better understanding of the deltas they include (for one thing, they know that they are original), they can add more properties to their blocks., that make syncing more efficient (like ordering). Also, in most cases, the content of these blocks will be unique, which is not the case of bundles used today.

So, yes, I can like a cast on Warpcast and on Supercast. This is the same thing as submitting the same like, with different signers, to two different hubs today: One of them will be eventually dropped and will not make it to the CRDT.

[deodad]

questions on Global Ordering:

• how do sequencers order messages within a block?
• to remove SPOF, can N sequencers be run so long as each FID maps to exactly one sequencer?

[deodad]

comments and questions on Account Ordering:

• how are conflicting nonces handled during sync? if two hubs can have different values for the same nonce isn't the sync optimization diminished?
• since CRDTs are across accounts, but chains across signers, what happens when Signer A's LinkAdd message get's replaced by a Signer B's LinkRemove message? if it's at the head does the client for Signer A need to use the next nonce still? if it's in the middle and breaks the chain how does sync work?
• how does a client establish what nonce it should be on for a particular signer in the event it either loses that state internally or needs to connect to a new hub? at the very least it seems like the client would need to replay any messages greater than the hubs last seen nonce, but given other signers can generate conflicts and it seems like difficult to reason about edge cases can pop up that require resign different message with the same nonce (I publish LinkAdd 1, LinkAdd 2 to Hub A, both are accepted and then connection is lost, I connect to Hub B and it has seen none of my message, I try replay LinkAdd 1 but it's now in conflict, how to proceeed?)

[deodad]

"Hubs enforce that sequence numbers are monotonic and handle conflicts by picking the delta with the lowest lexicographic hash value."

This doesn't answer how it's handled during sync. Two hubs can't sync from the highest common nonce if the lower nonces can have changed.

Actually, it seems that all apps will be required to have the ability to replay messages. Like you said, you submitted 2 messages to hub A, then try to submit the next one to hub B, but hub A went down and never broadcasted the messages, now the only way to proceed is to replay messages 1 and 2 to hub B, or any new message will be rejected because there is a nonce gap.

What if I got to replay the first message but it is no longer valid due to a CRDT conflict? Now I have to replay sign the second message with nonce 1 and knowingly introduce a conflict (since I already had published M2 with nonce 2 earlier). My suspicion is connecting to a new hub requires starting from the beginning and republishing everything to be certain that nothing is missed (similar to today).

[vrypan]

This doesn't answer how it's handled during sync. Two hubs can't sync from the highest common nonce if the lower nonces can have changed.

Maybe we should not have just ordered blocks, but blockchains (each block linking to the previous one).

[vrypan]

Yes, I'm talking about "blocks", but the Account Ordering approach does not have blocks, just messages with a nonce. In which case we have to as a link to prev message (and increase storage and bandwidth requirements?).

[aditiharini]

Do you expect the stream of events from hub -> client to be reliable? Should the client request replay if it sees gaps in sequence numbers from the stream? If we want gaps in sequence numbers to be an indicator of missing messages, does pruning break this model?

[vrypan]

I guess "client" is something like shuttle? Because if your client is for example a bot looking for specific events, then they may be following an FID, or a specific type of events (CastRemove, or LinkAdd, or something else) where blocks do not matter, and they will be using the existing gRPC APIs. I don't know what types of errors/fails an app with the scale of Warpcast faces...

It's worth noting that in case of Application-ordering, you can identify that you are missing a block from a chain (i.e. app) you already follow, but not from one you haven't seen yet.

[vrypan]

Has this FIP been put on hold? If not, it would be great to hear your thoughts and the direction you're moving.

[varunsrin]

no, should have something to share this week

[varunsrin]

tl;dr - we're leaning towards global ordering after exhaustively exploring the options so far. we haven't made a final decision yet and will present a draft of our proposal at the dev call.

We've explored four different options over the last week. I'll try to summarize each of them quickly and present the tradeoffs in this post. in a follow up post, i'll go into our proposed solution in a lot more detail. A big thank you to @sanjayprabhu @CassOnMars @aditiharini @deodad @danromero @adityapk00 and @vrypan who have made significant contributions.

1. Do Nothing

We stay with the current model and try to fix the problems with smaller patches. The main benefit is that this requires the least work of all the options discussed, and the team could instead focus on other features that might be more beneficial to Farcaster.

The problem is that if the network grows by 10x we'll start seeing problems syncing between apps that we might not be able to patch over. We will have to pursue some larger refactor and we'll be doing it under pressure and while the user experience is degraded for weeks or months. This doesn't seem viable for this reason.

2. Account Ordering

We introduce ordering at the account level, which is described about in some detail. An account's app key (signer) must add a sequence number to every message and ensure that it is monotonically increasing. Sync is quick because you can just compare sequence numbers and download missing messages instead of comparing all message ids. Gossip also becomes more reliable because dropped messages can be identified by non-monontonic sequence changes.

The biggest problem is that we can't easily retrofit sequence numbers to existing data. We need users to come back online and resign all their messages with sequence ids and will need to handle the case where users never return.

The other problem is that we've only mitigated the sync issues and they still persist in milder forms. For example, sync still won't complete and result in two hubs reaching the same state because its likely that a hub is "ahead" for some accounts and "behind" for others. One way to think about this is that we've made everything 60% better but we still have to deal with all the edge cases. This doens't seem worth it relative to the time invested and additional complexity to handle the sequence id problem.

3. App Ordering

@vrypan's proposal sidesteps the need to modify messages by making apps do the ordering with sequenced bundles. We really liked this because its like each app having its own ordered bundles of messages. Sync is even faster than account ordering because you only have to do the sequence number comparison once per app instead of once per user.

You can broadly think about this change as further dampening the sync problems by reducing the number of distinct sequences we care about. In (1) we had infinite items to check, in (2) we had to do a check per account and in (3) we have to do a check per app. In other words, it eliminates something like 80-90% of our sync problems relative to option (2) which was only 60%.

A problem is that conflicts with bundles are really hard to resolve. Imagine the case where an app re-issues bundle number 1 and invalidates its entire sequence history but re-introduces some part of that history again. Handling all the edge cases is quite likely and its hard to prevent this from happening.

Another challenge is that you can't allow everyone to create apps and publish messages or this will just degrade to the performance of (2) with additional downsides. Choosing which apps get to publish messages is not a trivial problem and must be done thoughtfully to prevent centralization of control.

4. Global Ordering

We introduce global ordering by grouping messages using a "sequencer". There is only once sequence to worry about and this is like the model that Ethereum L2's use to produce blocks. Sync is trivial and many of the sync problems like rate limits are totally eliminated. The only thing you need to do is compare sequence numbers and download anything you've missed.

The big problem with this approach is that you have to figure out how get multiple sequencers working. The good news is that it will be a lot easier than decentralizing blockchains sequencers because state changes are independent, the bad news is that it's still a lot of work. This is a cleaner solution than the other approaches but is probably a lot more work to get right.

We think (4) is our best bet - if we're going to embark on a fairly large rewrite of our system we want something that changes the paradigm and eliminates entire classes of sync issues instead of something that just mitigates them. I'll share a more detailed proposal soon.

[varunsrin]

@sanjayprabhu also put together a table comparison for the four options

[SamuelLHuber]

would anyone be able to run sequencers to ensure decentralization? if so how would that differ from the bottlenecks currently faced with low performing hubs and global consensus limitations in existing blockchain systems?

I assume due to not requiring a strict time order it's not as limited as blockchain block production, though am worried that slow sequencers will be a bottleneck

[varunsrin]

here's the draft of the proposal: https://warpcast.notion.site/Snapchain-Public-0e6b7e51faf74be1846803cb74493886?pvs=74

i'll reformat it and add it to github soon

[varunsrin]

Since writing the Snapchain doc, @sanjayprabhu has been doing a lot more research into decentralization and scalability.

We want the next iteration of Farcaster to last at least 5 years whics means supporting a 100x in growth. Back of the envelope math puts that at 5,000 TPS and 100 GB state growth per day.

We also want it to be sufficiently decentralized. Snapchain doesn't change read access, but it does reduce the number of writers to improve scalability. We think it's important to get to a point where write access is distributed across at least 10 entities distributed geographically. That prevents anyone from stopping two people who want to communicate, which is our test for sufficient decentralization.

Snapchain v2

Our proposal is to modify Snapchain to start with sharding and multiple writers. It's still a WIP, but we wanted to share a draft early for feedback. The core elements remain unchanged - we have onchain events to create accounts, deltas to add state to accounts and hubs to store and sync this data. The main improvement is that we have a blockchain-like mechanism to order data inspired by NEAR's Nightshade.

Snap Production

Users create deltas and submit them to hubs which broadcast them into a mempool via some rpc or gossip network. Special hubs called validators read deltas out of the mempool and publish snaps every few seconds.

A validator is assigned to a set of fids (e.g. fids ending with 0) and keeps track of their onchain events and deltas. Each fid's items are placed in a separate store and their hashes in a trie. The validator maintains a trie-of-tries (validator trie) whose leaves are the merkle root of every fid's trie. When onchain events and deltas are received, they are applied according to the state transition rules. For example, a "delete cast" delta removes the deleted cast delta from the user's store and it's hash from the trie. This modifies the fid trie's merkle root which also affects the validator trie. Validators will periodically produce a chunk which contains all the onchain events and deltas since the last chunk, plus the root of the validator trie and a signature over this data.

A leader is responsible for collecting chunks from the validators and producing a snap. The snap contains all the chunks and some metadata that links it to previous chunks. The leader then streams this out to the rest of the network. The snap is self verifying - any hub that receives can validate the data and apply the state transition rules.

Chunks and Validators

1. We propose sharding the network into two chunks - even fids are assigned to chunk0 and odd fids to chunk1.
2. We propose assigning three validators per chunk - each of these validators only listens to accounts within the chunk.

Chunking the network like this is trivial because operations on one account do not depend on any other account. It allows us to scale snap production by reducing the load on a validator. Using multiple validators per chunk helps protect against downtime of any single validator. Ensuring that validators are distributed across different entities also improves censorship resistance.

We expect to add more chunks or validators in the future. The network - via a hard fork - can issue a special snap that reassigns accounts across chunks and remaps validators to specific chunks.

Validator Election

If all the validators for a chunk were controlled by a single entity, they could block some users from publishing data. It's important that the three validators are run by different entities spread across geographies. We also plan to increase the number of validators up to 10 to improve sufficient decentralization.

Validators are elected by voters who represent the interest of developers and users in the Farcaster ecosystem. An example system might be something like:

1. The Warpcast team nominates 10 "voters" such Warpcast does not have majority influence.
2. Every 6 months a new voting round starts, where a group of people apply to run validators.
3. The voters do a ranked choice vote to elect the validators that get to participate.
4. The voters may then propose a vote to replace some members

Voters must be capable of assessing whether an applicant has the technical skills, finances and motivation to run a validator. Otherwise we may need to do an emergency vote to remove a validator who drops out. We might start with votes recorded with offchain signatures for simplicity and trigger the change in validators with a hard fork. over time we would want to get to a point where votes happen onchain and the validators can automatically rotate without a network update.

Voters can also trigger an emergency round to kick out a malfunctioning validator at any time. We may consider adding stakes so that validators have more skin in the game, but this may be unnecessary to start with.

Leader Election

A malfunctioning leader could stop snap production or exclude chunks from snaps. To prevent this, we have a system for leader election that can handle fallbacks. It also periodically rotates leaders to minimize the impact from a malicious leader until voting can remove them as a validator.

The leader rotation function might start with a simple round-robin system starting with validator0. This validator is responsible for epoch1 which is the first 1,000 snaps. The function also defines the next leaders - validator2, validator3 in this case - who take over in successive epochs or if this leader fails during the epoch.

Pruning

When a snap's chunks are processed the deltas are applied to each user's account and stored there. The chunks themselves can be discarded after a delay to save space. This lets hubs be very efficient and only store the current state of the network "Alice liked X" instead of all of the past history that led to that state "Alice liked X, unliked X and then liked X again". Pruning will be important to ensure that the network scale because users will generate a lot of state changes on social networks.

Introducing a delay for pruning will be important since we want the majority of the network to process and validate the state transitions before they are discarded. If a leader produces an invalid snap, hubs will detect it while processing it and reject the block requiring the error to be fixed. We propose a delay of one week for pruning so that even hubs that are down overnight or over a weekend can catch back up to the state.

Sync

A hub subscribes to a gossip topic and gets alerts about new snaps from the validator or another hub. It pings that hub to compare snap heights and download any missing ones. Failures in gossip can be handled by waiting for the next message or trigger random manual syncs. This is significantly simpler than our current sync model and is the main benefit of this design.

Deltas

We don't need to change deltas very much in this world. The core mechanic of users signing messages to add and remove casts and likes and follows remains the same as it does today.

Attack Vectors

• Censorship: a validator could refuse a delta from an fid. this is a similar attack vector to how l2 sequencers can refuse to accept a transaction from an address. we mitigate this approach by introducing multiple validators per chunk which requires multiple parties to collude. if wide scale collusion is present it cannot be proved deterministically, but it can be observed by watching the mempool. if sufficient evidence exists the voters can eject the offending validators with an emergency vote.

• Invalid snaps: a leader could produce and accept invalid chunks into a snap which include either invalid deltas or invalid merkle states for tries. such a case could be detected by hubs which will stop accepting new snaps until this is fixed by re-issuing a snap at the same height with valid headers.

[vrypan]

App ordering does not seem to solve the sync problem we set out to solve, which makes it a non-starter. Unless there is some clever modification to the design that we are missing. See my post from earlier.

Yes, this is clear, I'm not pitching the idea again :-) Just bringing it up as an example of how a model could align incentives in a natural way: An app with many users/messages would have to use a sequencer with higher specs than an app with a single user.

[SamuelLHuber]

how will the state representation change if history is pruned? currently one takes all messages stored on a Hub and combines these messages into a state aggregate.

Say number of Likes on Samuel's recent post -> ask hub for all Reaction Messages that add a like to the post and return the sum

with the snaps being very limited in history that won't be possible if the same format is used? What am I missing in that thought model?

[sanjayprabhu]

So, the account state representation doesn't change. What's pruned is the state change history. Say you liked a cast and then unliked it, both of those actions can be pruned.

In the current model, we have to keep the unlike around for CRDT resolution. In the traditional blockchain model, you have to keep both the like and unlike around. With snaps, you can prune both.

If you just liked a message, nothing changes, we keep the like message and the snap in which it happened.

[vrypan]

Do chunks have a max size?

[varunsrin]

Yes, there will be some max size but we haven't yet figured out what the optimal parameters should be

[pmohun]

Thanks for sharing. Can you share a bit about the expected costs and hardware requirements to run a validator? What types of organizations do you expect to run these machines and what are their incentives to do so? For example, running a Hub is feasible today due to the relatively low hardware costs and economic benefit of access to direct social data. Becoming a Validator seems to have a much higher set of requirements around availability and upgrade synchronization, so curious who these actors are.

…

On Sat, Sep 21, 2024 at 02:21 Panayotis Vryonis ***@***.***> wrote: App ordering does not seem to solve the sync problem we set out to solve, which makes it a non-starter. Unless there is some clever modification to the design that we are missing. See my post from earlier. Yes, this is clear, I'm not pitching the idea again :-) Just bringing it up as a model that showcases how a model could align incentives in a natural way: An app with many users/messages would have to use a sequencer with higher specs than an app with a single user. — Reply to this email directly, view it on GitHub <#193 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACYR3S4AFEMWPO74SQTWOJTZXS3YVAVCNFSM6AAAAABNHECEIOVHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTANZRGAZTCMA> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.*** com>

[varunsrin]

In terms of compute, bandwidth and storage I would guess its roughly the same as today, though we'll have to build a prototype to validate this. The only additional requirement is that validators have a high degree of uptime probably something like 99.99%.

Neynar is very interested in running a validator on day one, so we'll start with at least two parties. I suspect that anyone who is investing heavily in building on Farcaster will want to run a validator to ensure they have access to the network that isn't dependent on anyone else.

In the unlikely event that there aren't enough validators, we could for example use storage fees to incentivize people to run validators with grants.

[vrypan]

This is a proposal inspired by a Bitcoin-like blockchain. The main advantage of this solution is that the ordering process is decentralized.

TLDR; There is a mempool where every hub submits deltas. Miners (nothing special, spec-wise compared to normal hubs) propose new blocks, each block is linked to the previous one in a blockchain. There may be forks, but they are reasonably easy to resolve. The design provides better censorship resistance, and I think it scales nicely.

Mempool

There is a mempool where any hub can submit messages

Miners

There are special nodes that we will call miners.

Miners read messages from the mempool and bundle them in blocks.

• Every X seconds, the miners broadcast their block.
• Messages in a block must be ordered lexicographically by hash.
• Messages include onchain events.
• All messages must be valid.
• Messgaes in a block must not be in a previous block
• Each block links to the hash of the previous block
• If there are more than one proposed blocks, the one with most messages wins

We call "block summary" the contents of a block without the message bodies (only block header and the message hashes). Miners do not need
to maintain the full state of the network, just the block summary, because once they validate messages, they only care
about the message hashes.

"Block score" = number_of_messages / percentage_of_blocks_contributed_by_miner_in_last_100_blocks

"Chain volume" is the number of messages inluded in the chain, ie. sum( count(messages) for messages in all blocks ).

Volume is important, more important than chain length. The best chain has more messages, not necesserily more blocks.

Hubs

Hubs work like they work today, with the following changes:

• They do not listen for onchain events. When they receive an onchain event as part of a block, they validate it.
• They submit new messages to the mempool
• They update their state when they receive a new valid block.
• If they have to pick between forks, they pick the largest chain (based on chain volume, not length).
• If they are missing blocks, they ask them from other hubs
• In addition to the state (messages), hubs also store the block summaries. This means they can reconstruct any block.
• They validate blocks and reject invalid ones
• Between two new valid blocks (same previous block) they pick the one with the higher block score

Note: Hubs check if messages in a block are new (they must be) by comparing them to the block summaries, not their state.
This is importatn when it comes to deciding between forks (covered later).

Problem Handling

Blockchain forks

It is important to keep in mind that forks do not invalidate messages. A valid message submitted to the network should eventually reach all hubs. So, forks will usually be "better ways to organize the network history", and one fork does not invalidate messages in an other. It is assumed that two "honest" forks will eventually converge (needs more thought).

So, even if a hub follows one chain and after X blocks there is a block reordering, the messages that may not be present in the reordering are valid and should be part of the hub state. In theory, these messages will have to be included in a future block, and we can also consider letting a hub submit these "missing" messages to the mempool as a security measure.

Assuming that a hub is on Chain A and wants to switch to chain B, it has to follow these steps.

First, identify the fork block, block N.

Then, starting from block N+1 on chain A, replay all blocks with the following rules:

1. SignerAdd --> Skip
2. SignerRemove --> Add Signer (This signer was approved before Chain B block N+1, so, let’s approve it again, before looking at Chain B.)
3. Messages submitted by users --> Skip

Next, group all messages in Chain B blocks M > N:

1. Check that SignerAdd messages are valid, if not, abort. Add all the new signers to the local state. (Some of them will already be present.)
2. Validate all user messages. If they are all valid, update the local state. If a message is already in the local state, skip. If a message is invalid, abort.
3. Replay all SignerRemove messages, and delete messages signed by these signers.
4. Switch to chain B.

If the process aborts, then replay all Signer Remove messages in chain A, in blocks M>N.

Censorship

A miner with priviledged access to new messages (for example Warpcast or Neynar) can try to censor specific messages. Since
they have access to messages that may not be submitted to the mempool, they can always create blocks with more messages than
other miners and keep the sensored messages out of the blockchain. However, as they fill the chain with more blocks, their
blocks get a lower block score (percentage of contributed blocks goes up) which makes it easier for a competing miner to
propose a new block that includes the censored messages and has a higher score.

(Additional thought must be put in this attack vector)

Mallicious attack: new, longer chain with missing messages

An attacker can generate a chain with 10,000 blocks where each block contains one (valid) message. However this chain is
smaller than the "good" chain that may have a lower hight but more messages, and will be ignored by hubs.

Two opinionated miners that keep different messages out of their chains

There may be a situation where miner A wnats to leave message m1 out of the chain and miner B wants to leave message m2 out of the chain. They keep generating competing blocks, their chains have the same volume (missing one message).

There is not much point in doing this. Hubs will switch from one chain to the other (as block score changes and favors one over the other), but this means that both m1 and m2 will be part of their state (reordering does not invalidate messages).

[CassOnMars]

Generally if you need a leader selection mechanism that is transparent, trustless without invoking the demons of hashcash-esque approaches, a VRF is a good choice. There are many out there, but it's worth noting that if VRFs rely on the input of the predecessor block, you must also consider the "unbounded adversary" problem where a leader can parallelize search by inputs of adjusted blocks such that they find an output that makes them the leader constantly.

[vrypan]

Ideally, I wouldn't want random selection of miners (open to change my mind). For Farcaster, I like it that in this model apps that generate most messages (and have a vested interest in the network working properly) can produce most blocks, while making it easy for a smaller miner/app to introduce the next block if the big ones censor messages. I think this reflects how the network actually works, and who has the biggest stake in it working properly.

[vrypan]

The main challenge I see is that using "most messages"

I see what you mean now. I can create a new chain that is exactly like the current chain but introduce a new, valid message 1000 blocks ago, and it will be larger, and trigger a reordering.

The idea behind this was to pick the most complete chain that does not leave out messages. But I think that volume should be calculated only using onchain events. I.e. volume = sum( count(onchain events) for events in all blocks ). Any other omitted messages can be added in the next block, there is no reason to add them 1000 block ago (the result will be the same, anyway, they were not visible until now, and they will become visible now).

OnChain events are visible to everyone the moment they are emitted. So, unless there is a bug or censorship every chain must have the same volume. In this case, the attacker's chain (case "new, longer chain with missing messages") will not be larger (volume-wise) than the current chain.

This will reduce the number of forks significantly. Unless an onchain event is missing (which it shouldn't), the race is for the next block. And there, the apps that generate messages have the first word, because their blocks will contain more messages and their score will be usually higher.

Does this make more sense, @varunsrin?

[vrypan]

Some more thoughts on this, and why counting onchain events is important.

1. Possible attack: Warpcast is controlled by V's evil twin. I revoke my Warpcast signers, but Warpcast does not add the revocation event in the blocks they produce. I will have to wait for the block score wars, and in the meantime Warpcast can use my signer in frames, etc. It should be trivial for an independent miner to introduce the revocation in the next block.

2. It is also important because missing onchain events may result in messages treated as invalid.

3. In case we introduce staking, or some other onchain activity that affects users, hubs or miners, these must be able to be propagated immediately to the network. (Hubs do not listen for onchain events in this model, they only check their validity when they receive them in a block.)

This part (checking the chain volume) may probably be omitted for now, but I think it's a good thing to have it in place. And it does not seem to add significant complexity.

[vrypan]

I don't want to keep updating my comment (with the proposal), because the rest of the discussion loses context.

I'm keeping an updated version that includes changes discussed, here: https://gist.github.com/vrypan/1ae6a60ecb3741ab031b5b06c974acab

I think it's becoming simpler and better, especially the change that calculates volume using only onchain events, simplifies a lot of things.

[vrypan]

A general question that relates to any of the proposed ordering solutions.

If we use ordering, hubs are free to keep or throw away any deltas they want, and the network will never know.

This can have multiple implications, I think mostly positive, but I'd like to hear thoughts on it. For example, an archival hub that keeps everything and never applies historical pruning. An other one, who is used by a bot farm, that throws away everything. A pair of hubs that shard deltas between them, based on odd/even fids. And a dev node that only keeps my fid deltas.

This is more apparent in my "miners" proposal, where hubs only need to keep the block summary. But I think it applies to every ordering solution: blocks are announced to hubs, but we don't know what they do with them.

Thoughts? Other implications?

• For example, what's the meaning of storage units in this context? Today, the protocol provides assurances that hubs will preserve my content according to some rules. Who provides this assurance to users in an ordered blocks/snaps model?
• Is storage a service provided by the protocol, or is it something provided by service providers? For example, I pay for a hub to keep my history for at least one year. Or maybe, there's a side protocol, that rewards hubs that keep enough history, and users pay it separately?
• Do we need to add retrieval in the protocol? How will a client locate my content if they don't have it?