Revisiting the Lattice model of Sharding
We started thinking of sharding as this lattice model. Eventually we realized problems which are summarized there in comments.
There was an alternate tree proposal that solves the worst of the problems, but eliminates some of the features.
The two models have been compared and discussed.
Tree model is being implemented now. Funds can be passed between shards by a clever system explained that I'll summarize briefly. Funds are locked up in a depository in the parent shard. Those funds back new rev that are minted in the child shard. Validators of the child watch the parent in order to ensure all child rev are fully backed and vice versa. I'm not totally clear on this, but I assume code mobility works similarly.
Also, there is a nebulous plan to implement lattice at the leaves in the future. I don't know when or what that plan is.
Multi Parent Proposal
My first idea slightly generalizes the tree and may reclaim some benefits of the lattice model.
We begin with the tree model as it stands now. The problem is that to move funds etc between two shards that are far apart in the tree requires several hops which increases both time and cost consensus.
Imagine that we now create a new child shard that has not just one but two parents. There is a depository in each parent, and a single mint that will mint rev backed in either parent's depository. Now rev can be transferred in a mere two hops by routing through the common child regardless of proximity of the two parent shards in the tree. That reclaims at least one benefit of the lattice model (and, I guess, makes the tree more of a graph now).
The validators in a child will be subset of validators from the parents (more precisely, the union of subsets from each parent so that both parents are represented). Validators may want to validate all the way to root via all possible paths. While there are now multiple paths to root, we avoid the unbounded growth of the original lattice problem. The number of paths to root will never increase once a shard if formed.
This technique has limitations in the sense that if the child shard has ten total rev (9 from parent A and 1 from parent B), not all of the rev can be withdrawn to parent A. In cases where the deposits in each parent are large compared to the amount that is actually moved out of the shard, this will matter little. In any case, a few solutions are possible.
1. Ensure that the funds deposited in each parent are equal by not allowing transfers up or down until a transfer of a corresponding amount is made in the other parent with an orderbook matching style algorithm.
2. Allow deposits from either parent and withdrawals on a first come first served basis up to the amount backed in either parent.
Prime Shards Proposal
My second idea generalizes the two-parent idea further to multi-parent, and may re-invent the original lattice idea. I also use different nomenclature here.
Instead of a root shard, we have countably many root shards, and instead of calling them "root" we call them "prime". Prime shards can form independently at any time without coordinating or communicating with any other shard. The only thing that must happen to create a prime shard is that a non-empty set of validators must agree on a genesis block and bond their stake. Each prime shard has it's own independent token. Composite shards can then form over any non-empty set of subshards. Shards whose set of subshards is empty were already named the primes (We could even call the trivial shard that has no validators the identity shard). A composite shard has its own token which is backed by rev in a depository in each of the subshards, which we may as well call factor shards. I don't know whether requiring 1:1 backing makes sense. Surely the value of the tokens in each prime shard will float just as ETH and BCH do now. So composites may need to establish a conversion from each factor token at genesis.
Validators in prime shards will likely be interested in validating at least some composites that build upon it (it's "multiples"). But they need not do so. If only some prime validators choose to validate a particular multiple, they can gossip the relevant merge blocks back to their peers in the prime and the remaining validators can sign without validating the foreign transactions, just as they would if they don't validate all the way to root in the current tree proposal. On the other hand if only a small number of prime validators are interested in a particular multiple, their peers in the prime can simply ignore the proposed merge block. This sounds like collusion because it is, but in this case it's just the majority validators colluding to say, "We aren't intereted enough in that multiple to justify the cost of validating it." It's just like saying, "Dude, we like you and we like hanging out with you, we're jut not interested in cliff-jumping with you." The minority validators are welcome to form the composite of the remaining prime factors, and it is likely (certainly?) more economically feasible to do so.
Validators could also join composite shards directly without validating any of the prime factors, although not from genesis. They would have to first join the composite as a non-validator and earn some tokens, then later stake to become validator. It's likely that occasionally composite shards would significantly exceed their factors in popularity. A composite that started for a small interest group could later host a killer dapp which overshadows the original purpose (Think mt gox turning from card game to bitcoin or yamaha turning from pianos to motorcycles). In extreme cases, all (or all but one) prime factors could cease to exist turning the composite into a prime.
Composites with repeated factors may make sense in POW blockchains where there is no concept of finality. Composite shard ABB may require 3 block confirmations in A but 6 in B. Not sure that retains any meaning in casper though. And in no case (that I can think of atm) would a composite with a single repeated prime factor make sense.
The more I think about it, the more this sounds like the original lattice model, but I haven't previously seen my argument about validators having the option of validating the composite shards. I look forward to feedback on these ideas.