We assume that at address
VALIDATOR_MANAGER_ADDRESS (on the existing "main shard") there exists a contract that manages an active "validator set", and supports the following functions:
deposit(address validationCodeAddr, address returnAddr) returns uint256: adds a validator to the validator set, with the validator's size being the
msg.value(ie. amount of ETH deposited) in the function call. Returns the validator index.
validationCodeAddrstores the address of the validation code; the function fails if this address's code has not been purity-verified.
withdraw(uint256 validatorIndex, bytes sig) returns bool: verifies that the signature is correct (ie. a call with 200000 gas,
validationCodeAddras destination, 0 value and
sha3("withdraw") + sigas data returns 1)
sample(bytes32 seed, uint256 shardId, uint256 sigIndex) returns uint256: uses the seed to pseudorandomly select a signer from the validator set. Chance of being selected should be proportional to the validator's deposit
We first define a "shard header" as an RLP list with the following values:
[ shardId: uint256, prev_state_root: bytes32, tx_list_root: bytes32, coinbase: address, post_state_root: bytes32, receipt_root: bytes32, children: [ child1_hash: bytes32, ... child[SHARD_CHILD_COUNT]hash: bytes32 ], state_branch_node: bytes32, signatures: [ sig1: bytes, ... sig[SIGNATURE_COUNT]: bytes ], mixhash: bytes32, nonce: uint64 ]
shardIdis the shard ID of the shard
prev_state_rootis the previous state root of the shard
tx_list_rootis the root hash of the trie holding the transactions included in this shard block
coinbaseis an address chosen by the creator of the shard header
post_state_rootis the new state root of the shard
receipt_rootis the root hash of the receipt trie
childrenis a list of hashes of shard headers for child shards of this shard (a child of shard
ihas children with IDs
i * SHARD_CHILD_COUNT + 1 ... (i+1) * SHARD_CHILD_COUNT). Each hash can also be the hash of the empty string if no shard header for that child is present
state_branch_nodeis the sha3 of the
post_state_rootconcatenated with the
state_branch_nodevalues for each child (ie.
sha3(post_state_root ++ child1.state_branch_node ++ .. ++ childn.state_branch_node)). If the depth of a shard is equal to
MAX_SHARD_DEPTH(a shard has depth 0 if it has no parents, otherwise the depth is 1 plus the depth of its parent), then this list MUST have length 0.
signaturesis a list of items each of which is either empty or a signature
nonceare an ethash mixhash+nonce; the ethash mining result must match the
For blocks where
block.number >= SERENITY_FORK_BLKNUM, the block header's extra data must be either a locally valid shard header for shard 0 or the empty string. We define the "current state branch root" as being the
state_branch_node of shard 0 for the most recent block that had a shard header, the "current state branch node" of any shard as being the state branch node that is in the tree whose root is the state branch root, and the "current state root" of any shard as being the state root that is in the tree whose root is the state branch root.
If there has not yet been a shard header, then we assume the current state root of a shard is the genesis state root of that shard (this is a protocol parameter), and we can use this to derive the starting state branch nodes for every shard, including the starting state root.
We define a shard header as "locally valid" if:
prev_state_rootis the current state root for the given shard
tx_list_rootpoints to a set of transactions that is valid and available
coinbaseis a valid address
post_state_rootis the resulting state root of executing the transactions referenced by the
tx_list_rooton top of the
receipt_rootis the receipt root generated by the execution
shardId >= 1 + SHARD_CHILD_COUNT + ... + SHARD_CHILD_COUNT ** (MAX_SHARD_DEPTH-1), then the children is an empty list
shardId < 1 + SHARD_CHILD_COUNT + ... + SHARD_CHILD_COUNT ** (MAX_SHARD_DEPTH-1), then each entry in the children list is either an empty string, or a hash whose preimage is available, and whose
shardIdis this header's
SHARD_CHILD_COUNTplus (1 + the child's index in the list)
state_branch_nodeis the hash of the
post_state_roottogether with the
state_branch_nodeof each child; if a given child is empty then we take the current state branch node of that shard.
0 <= sigIndex < SIGNATURE_COUNT, let
validationCodeAddrbe the result of calling
sample(mixhash, shardId, sigIndex). A signature is "valid" if calling
validationCodeAddron the main shard with 200000 gas, 0 value, the mixhash concatenated with the sigIndex'th signature as input data gives output 1. All signatures must be valid or empty, and at least 3/4 of them must be valid.
Note that there exist two classes of participants in this scheme:
We expect collators to only create shard headers that satisfy all of the above criteria except the second last, as well as only including locally valid shard headers as children. We expect signers to only sign shard headers that satisfy all of the above criteria except the second last, as well as only signing headers that include locally valid shard headers as children. Even though the minimum threshold for a collation is 2**32, we expect shard signers to maintain private difficulty thresholds so that on average one shard header produced per shard matches their private threshold; this ensures that shard signers usually agree on which shard header to sign.
Claim: if most signers are honest, then the entire shard tree should be valid, in the sense that every shard header in the tree is locally valid, with 100% minus negligible probability.
Currently, the coinbase of a block is rewarded with 5 ether, plus extra ether for uncle and nephew rewards, as part of the "block finalization function". Here, we also have a finalization function for each shard, though the logic is different:
coinbase(ie. shard collator) by
ROOT_SHARD_COLLATOR_REWARD / SHARD_REWARD_DECAY_FACTOR ** shard_depth
ROOT_SHARD_SIGNER_REWARD / SHARD_REWARD_DECAY_FACTOR ** shard_depth
The above proposal does NOT include the following highly important features:
The intention is for both to be resolved at the "chain governance" layer. That is, we introduce a contract on the current shard where anyone can burn their ether, and agree to include the ETH in the genesis state of the shard that they want it transferred to. We also make a promise that future hard forks will add the ability to move ETH between shards, as well as adding fault recovery mechanisms (see here for some details), and during a future hard fork we would do a "reset" where for every shard on which there has been a fault we reset its state to the last known valid available state of that shard, so any successful attack on a shard can only accomplish the task of shutting it down until the next fork, not stealing any ETH or causing any invalid state changes.
This allows for a quick and dirty form of medium-security proof of stake sharding in a way that achieves exponential scaling through separation of concerns between block proposers and collators, and thereby increases throughput by ~100x without too many changes to the protocol or software architecture. The intention would be to replace it in the next hardfork with a design that adds in erasure coded data availability proofs, fraud proofs, and the formal requirement for block proposers and validators to reject collations that are not valid at the transactional level, even if they have the requisite number of signatures. Additionally, this model does not support movement of ETH between shards; it is the intention that the next hardfork after this will.
The shard tree structure ensures that no participant in the system needs to deal with more than
SHARD_CHILD_COUNT * SIGNATURE_COUNT signatures; with 3 children and 40 signatures, multiplied by 200000 gas per signature, this gives an upper limit of 24 million gas, though in practice we expect many signatures to be much smaller than the maximum.