FIP: Cross-shard communication in Snapchain

[aditiharini]

Problem

There are cases where we want some kind of cross shard communication in snapchain. Most importantly for Storage Delegation. There are cases where a user in one shard wants to delegate to a user in another shard. Cross shard communication is also required to process fname transfers correctly (currently we work around by every shard having a copy of all fname transfers). This would also allow us to remove the fname server and bring it into snapchain in the future.

Design

A simple approach to cross shard communication is to have all global data stored in shard 0, and have it manage sending signed messages to the individual shards to let them know to change their state. Note this is not a true “cross shard” solution, in that shards don’t directly talk to each other. Communication relies on the shard 0 forwarding all messages to the right shards. It is possible to extend this to do actual shard-to-shard messaging, it would require shard 0 to be a hop in the middle. We don’t currently anticipate any need to do this kind of communication.

At a high level,

1. All cross shard messages must be submitted to shard 0
2. The engine for shard 0 batches these messages into a transaction and commits them updating state as required. Shard 0 generates events for these state changes. These are same as existing HubEvents, except, they are included in the block.
3. Once the block is committed, the entire block is passed to the individual shards as a validator message in their mempools
4. The individual shards pick up the block, validate the commits and process the shard 0 events like how they process onchain events currently. The hash of the shard 0 block is included in the block generated by the shard.
5. Shard 0 scans for committed blocks from the individual shards (as it does currently) and checks that the block it sent them has been included into all shards. It waits until all shards have confirmed it before processing more cross-shard messages. This ensures that shards don’t miss or process cross shard messages out of order if they went down or run at different speeds.
6. Repeat from 1.

This design is meant for low throughput and latency tolerant operations. It does not work for cases where cross shard transfers happen very frequently or need to be fast (e.g. block on being able to reply to a cast until a the cast is included in another shard). It increases confirmation times of cross shard messages to 3 blocks across all shards in the ideal case. But shards still run independently and it does not impact normal messages.

Specification

Prerequisite

Currently shard 0 waits for the matching block number on each shard. This means shard 0 runs at the speed of the slowest shard and is therefore behind shards which have higher block numbers. This means shard 0 does not have a view of the latest state of each shard. We need to fix that so we can enable cross shard communication.

Shard 0 should now wait upto 500ms (block_time / 2) to receive a confirmed block for both shards. If it received a block and it’s higher than the previously witnessed blocks then it will validate and commit the headers into it’s own block.

If it did not receive a block from at least one of the shards, shard 0 will still commit the rest of the blocks it witnessed. If it received no blocks, it will commit an empty witness.

At a future point, when it receives the missing blocks, it will pick the latest block number it have received for the shard and commit that header. It will validate all the intermediate blocks for that shard. So shard 0 witnesses serve as the high watermark proof that all block numbers below that height are considered valid even if they may be missing.

If a block is missing or invalid after a certain period of time (10 mins?), then shard 0 must halt. This is to ensure that other shards will not receive out of date cross shard messages while one or more shards are down.

Protobuf changes

message BlockHeader {
  ...
  bytes state_root = 7;
  bytes events_hash = 8;
}

message Block {
	...
	repeated BlockEvent events = 5;
	repeated Transaction transactions = 6; 
}

message BlockEvent {
	BlockEventType = 1;
	bytes hash = 2; // One reason why this is not a HubEvent is we need an explicit hash
	oneof body {
		message StorageLend = 3
	}
}

// Mempool message types need to be updated
message MempoolMessage {
  oneof mempool_message {
	  Message user_message = 1; // Currently exists
	  ValidatorMessage validator_message = 2;
  }
}

message ValidatorMessage {
  OnChainEvent on_chain_event = 1;  // Currently exists
  FnameTransfer fname_transfer = 2; // Currently exists
	Block block = 3; // New. We can add the whole block since it's quite small, and the messages are rare
}

// HubEvent will also support the same StorageLend message and will be emitted 
// by the shards when they process the block event
enum HubEventType {
	...
	STORAGE_LEND_PROCESSED = 12;
}

message HubEvent {
  ...
  oneof body {
	  ...
	  message StorageLend = 17;
  }
}

// Also need a StorageLend message type, which is a normal user message. 
// This will be covered by the Storage Delegation FIP. What's relevant here 
// is that these messages will only be processed by Shard 0, not the other shards.

BlockEngine Changes

Shard 0 needs a MerkleTrie and an on chain event store. It needs to know about valid signers so it can validate the StorageLend user messages. Once these are added, the onchain events have to be backfilled on this shard.

When Shard 0 receives a StorageLend messages, it will process it similar to how stores work on the other shards. The main difference is these messages will emit a BlockEvent instead of a HubEvent and these block events will be included directly in the block. Once a block is decided, if it contains a block event, these blocks will be queued for inclusion into the shard’s mempool.

When shard 0 processes commits from the other shards, if it has previously submitted a block into the mempool, it will monitor the decided blocks to make sure that the block is present in the transactions list. Once the block is confirmed to have been included in all the shards, only then will the next shard 0 block be published to the mempool. This ensures that the shards receive the block events in order.

ShardEngine Changes

When the ShardEngine pulls transactions from the mempool, if it sees a block from shard 0 in the system messages, it first validates the block hash and the signatures to ensure it’s a valid block. Then, it processes the BlockEvents from the block in order, before processing any user messages.

Pros and Cons

Pro

• It’s a better long term design
• Works for foreseeable future usecases
• Ensures consistency across the network

Cons

• Adds complexity to the protocol
• Implementation will take time and could be risky to rollout
• Only works for latency tolerant and low throughput use cases

Rollout plan

This is a complicated change that will require multiple protocol releases. We would need to break it up into:

1. Add BlockEvents/Transactions to Shard 0
2. Backfill OnChainEvents on Shard 0
3. Start publishing blocks into the mempool/consuming decided blocks
4. Implement Storage Delegation

Future Work

Once we have this in place, we could move fname transfers into Shard 0 as well and remove the requirement for a separate FName server.

It might also be worth considering if we can move all OnchainEvents to Shard 0 and propogate changes via the messages mechanism instead of having each shard listen to onchain state changes.

Alternatives Considered

Passing Merkle Proofs

This is the more standard approach. We could do this, but it’s more work and we have to design the stores to merkleize all state, which we don’t do currently. Since we’re going to prune blocks anyway, it should be acceptable to put the events into the block. They will be cleaned up eventually.

Design

To implement this, we’d need to merkleize all state on shard 0 that we’d need to communicate. Easiest way to do this would be to re-use the merkle trie. This would mean creating a new store type that uses the mekle trie and all puts will insert or update the trie. Deletes would remove from the trie.

Then, when another shard needs to know about state in the shard 0, we’d pass the block header (which contains the commit certificates and the shard root), the value it needs to know about, and the path/sibling hashes of the value up to the root. The shard would validate the proof by:

1. Ensuring the block height/timestamp is not too old
2. Commit certificate is valid
3. Merkle proof is valid by and the re-calculated root hash matches the root hash in the header

At this point the data is considered valid and the shard can perform operations on the data.

Downsides

• No one is enforcing ordering, if shards care about order, they may need to enforce their own ordering by storing the block height of the most recent proof and ensuring all future proofs have a higher height/timestamp. This also adds complexity to clients where they may need to retry and fetch new proofs in case of races/mempool being busy
• Not suitable for high traffic/frequent checks. This method still won’t work if we need to check for storage status on shard 0 for every merge on shard 1, overhead would be too high

Replicate state across all shards

Design

For messages that are relevant to multiple shards (e.g. fname transfers from one fid to another, storage lending from one fid to another) send messages to all shards in the mempool.

Problems

• Race conditions causing state to be inconsistent across shards
  • Say you have the following scenario
    • Node 1 receives lend a → b, puts it in mempool
    • Node 2 receives lend a → c, puts it in mempool
    • Node 1 is the current proposer for shard 1, accepts a → b in a block
    • Node 2 is the current proposer for shard 2, accepts a → c in a block
    • Node 2 is the next validator for shard 1, rejects a → c in a block because a doesn’t have sufficient storage
    • Node 1 is the next validator for shard 2, rejects a → b in a block because a doesn’t have sufficient storage.
    • Now shard 1 and shard 2 have inconsistent views on who a has lent to. It looks like a has lent to both b and c while it only has sufficient storage to lend to one of them.
    • All shards have to receive all the lending messages because fid a may lend to any other fid in the future. Now because the data is inconsistent, lending behavior on shard 1 may differ from lending behavior on shard 2 and a has lent more than the storage it has available
  • Potential solutions
    • Back to CRDTs: We could use CRDT logic to resolve lending events. When a lending event comes in, check if the lender is over their limit and if so evict the most recent event based on message timestamp and if there’s a tie use message hash. This way the shards will arrive at the same state regardless of which order the messages are sequenced in.
    • Accept transient inconsistencies and reconcile after the fact:
      • There’s the question of where this reconciliation would happen. We’d need to build some system into Snapchain that looks at data across shards. This is fine now because all nodes run all shards but will be messy if not.
      • We would need some CRDT logic anyway to resolve the inconsistencies and figure out which lending events to keep so it’s not clear why we should do this after the fact vs in the critical path.
  • Requires reconciliation to resolve inconsistent state across shards (e.g. missed messages)
  • Also requires duplicating all on chain events on all shards because we need to know total storage available to be lent out
• Missed messages causing state to be inconsistent across shards
  • The main way this would happen is if a node crashes while a message is still in the mempool for 1 shard while it has already been processed for another shard
  • Potential solutions
    • Realtime reconciliation outside snapchain: If the submitting client hasn’t seen the event on the event stream for the appropriate shard, it should try to resubmit
    • Reconciliation process inside snapchain: We could have a job that goes through all lender fids and makes sure that the messages are consistent across all shards. We have the same problem for fname transfers right now and would need a similar process for that.
• Scalability
  • Duplicating data across all shards may not scale as the amount of data on the network grows and as different nodes become responsible for different shards. This is less of a concern than the above but something to consider regardless.

[vrypan]

How about using onchain events?

[sanjayprabhu]

A few downsides to onchain events:

1. We'd have to have custom contracts for each type of message. Or even if we built one generic contract, it's much harder to iterate
2. It will require paying fees to send messages, which while probably cheap is not ideal. The message throughput is expected to be low, but not low enough where the fees won't add up
3. There's a lot of overhead and complexity around sending on chain transactions at scale (e.g. nonce management, monitoring wallet balances etc)

Finally, even if we didn't implement cross chard message for this feature and went with some other approach, I think it's inevitable we'll need it in the future. So, might as well build it now.

[vrypan]

I have to be honest, I don't have a grip on this FIP, it touches parts of the snapchain design I was not aware of and I don;t have deep understanding of.

But at a high level, I read "there are shards, and there is shard zero". And I'm concerned that we moved from network where every hub was equal, to a snapchain, where an aristocracy of validators is above hubs, and now (or was this already the case?) Shard Zero becomes the king to rule them all.

Maybe too poetic for an FIP comment, but am I wrong to worry that with every change we move more towards a centralized db? Is the design becoming more fragile, where the answer to resilience (both to failures and censorship) is a "trusted, high-availability" single point of failure?

[sanjayprabhu]

Shard 0 is equivalent to ETH's Beacon chain (back when sharding was on the roadmap). The purpose of shard 0 is to coordinate the other shards but not hold user data itself. It is integral to the network, even though most users only interact with their shards. I wouldn't say it's more important that the other shards, if anything it used to be far less important (you could completely ignore it in practice) than the other shards. Now it's becoming slightly more important.

But the shards are all still completely independent and don't rely on shard 0 for normal operations. You can still register/rent storage/post messages without requiring "permission" from shard 0. Where shard 0 matters is for the few cases in the network where fids interact with each other (transferring fnames from one fid to another, lending storage units from one fid to another etc). If we want to keep the shards independent, there needs to be a central place to route and validate these inter-shard messages through.

[vrypan]

Reading this and FIP-240 again. I realize that what triggered both is design choices related to fnames. What exactly?