Tree vs Lattice Models for Namespaces/Sharding
This is a summary of the discussions that happened among various members centering around the consensus team during the Boulder conference. Most of the discussion can be summarized through a pro/con table for the tree (see Namespace/Sharding Proposal) and lattice (see Powerset shards) models.
| Tree | Lattice |
|---|---|
| Atomic transactions can be done speculatively. | Atomic transactions require finality on the block that "sends code" before the process starts. |
| No receipt tracking is involved. | Requires some kind of receipt tracking scheme to prevent code from being received multiple times. |
| If the higher shard does not like the gas price it is being offered, it can simply reject the merge block. | How gas prices will be handled when "receiving code" is unknown. An example fix that I do not recommend is having rev/gas conversion rates fixed across all namespaces. |
| If you are interested in validating a region A, validation is just a single path to root. | If you are interested in validating a region A, there is potentially an exponentially large number of namespaces you need to cover. In practice, the lattice is will be sparse. |
Blocks on lower shards can take longer to finalize. In specific, to finalize a block A on a lower shard either of the following need to happen: 1) The lower shard validators must produce and finalize a merge block that includes A in its history with a higher shard that chains to produce a merge block with the top | Finalization on lower shards does not depend on finalization in higher shards. |
Note that the tree being discussed here is not the one from Nash's orthogonal proposal where nodes in the tree track resources allocated to subtrees. Nash's proposal allows uniting multiple blockchains into a tree, but does not guarantee that any code executed on one chain did so properly. Therefore, the distributed purse design using zero-knowledge proofs that works in the models above would not work, because names can be forged and balances inflated in a low-security node; in order to move value from one node to another, a contract has to interact with a parent node to track the movement of that value.
Outcome of April 27th meeting:
Tree of arbitrary depth with a lattice on the leaves. Transactions at the top will be expensive, so there will be a tradeoff between wanting to be at the top (have to validate a lot) versus being lower in the chain (faster and tighter interactions).
Creating a lattice at the leaves implies that one will need to bring watchers or able to invite validators.
We provide an initial set of nodes - a frame to the tree.
Update: As of June 13th, we will be deferring the implementation of lattices in the shards. Please reference: Shards in RChain for a description of the functionality planned for Mercury.