Namespace/Sharding Proposal

This document describes how to we plan to upgrade from the Rchain State Proposal to a sharded version. The word name group and shard are used interchangeably.

Shard Hierarchy

The nomenclature still needs some work. For now, I've drawn a potential valid Rchain blockDAG simulation below.

The time axis goes from bottom to top and the horizontal axis represents different shards - I tried to keep it so each column is a shard but it sort of gets messier towards the top. The diagram provides an example of how child shards S1, S2, and S3 are forked off the root shard. It then gives an example of how a sub-hierarchy change is made: someone deploys a contract that has names that span S1 and S2. If one shard dominates over another, then the former can force the latter to accept a merge block and thus change its fork choice. Thus by the end of the diagram the root shard dominates over \{S1, S2\} and S3. And \{S1, S2\} dominates over S1 and S2.

Validator to Shard Hierarchy Mappings

Shards will be assigned a validator set through the Casper contract. The mapping must preserve three properties: 1) validators cannot guess the shard they are assigned to (preventing DOS attacks), 2) validators that are assigned to a leaf/node must also be assigned to every parent node (mitigating parent shard fork choice hijacking), and 3) "enough" validators/stake must be assigned to the shard. Nodes (as in computers, not tree nodes) can validate blocks without participating in consensus.

Validator Set to Shard Hierarchy Mapping Proposal 1

1) A contract deployer creates a new child shard by proposing a "merge block" that acts as the genesis block for that new child shard. It contains at minimum a new child casper contract along with a new state trie for that child shard. When you fork a new shard, the new shard's validators are initially the same as the parent.

2) A validator joins by sending a "I want to join" transaction to the root shard's Casper contract (stake details TBD). The root Casper contract then delegates them to one of their children Casper contracts, randomly. And so on. At each delegation step, there is also an slight probability to just stop at that level and not go further. Otherwise the validator arrives at a random leaf/shard, and becomes a validator there.

3) We force validator rotation after every X blocks: when this happens, a validator gets kicked out of its current shard. They can rejoin by going through the process in (2).

Changes to the Structure of a Block

Sharding introduces "merge blocks", blocks that are validated across shards in the sharding hierarchy. Merge blocks can only occur along the branch lines of the sharding hierarchy. For example, from the above diagram, we can have a merge block between "S1" and "{S1,S2}"; "S2" and "{S1,S2}"; and "S1", "S2", and "{S1,S2}". But not "S1" and "S2". A "merge block" spans multiple shards and is part of the blockchain of all the constituent shards. Instead of a single state root, each merge block will have multiple state roots (and most importantly multiple Casper contract instances) - one for each shard it merges. Each Casper contract defines the master shard (set) of its children blocks. The master shard (set) chain must not contain cycles.