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. validationCodeAddr
stores 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, validationCodeAddr
as destination, 0 value and sha3("withdraw") + sig
as 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 depositSERENITY_FORK_BLKNUM
: ????MAX_SHARD_DEPTH
: 4SHARD_CHILD_COUNT
: 3SIGNATURE_COUNT
: 40VALIDATOR_MANAGER_ADDRESS
: ????SIG_GASLIMIT
: 200000SHARD_POW_DIFFICULTY
: 2^36ROOT_SHARD_COLLATOR_REWARD
: 0.1ROOT_SHARD_SIGNER_REWARD
: 0.002SHARD_REWARD_DECAY_FACTOR
: 3We 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
]
Where:
shardId
is the shard ID of the shardprev_state_root
is the previous state root of the shardtx_list_root
is the root hash of the trie holding the transactions included in this shard blockcoinbase
is an address chosen by the creator of the shard headerpost_state_root
is the new state root of the shardreceipt_root
is the root hash of the receipt triechildren
is a list of hashes of shard headers for child shards of this shard (a child of shard i
has 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 presentstate_branch_node
is the sha3 of the post_state_root
concatenated with the state_branch_node
values 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.signatures
is a list of items each of which is either empty or a signaturemixhash
and nonce
are an ethash mixhash+nonce; the ethash mining result must match the SHARD_POW_DIFFICULTY
thresholdFor 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_root
is the current state root for the given shardtx_list_root
points to a set of transactions that is valid and availablecoinbase
is a valid addresspost_state_root
is the resulting state root of executing the transactions referenced by the tx_list_root
on top of the prev_state_root
receipt_root
is the receipt root generated by the executionshardId >= 1 + SHARD_CHILD_COUNT + ... + SHARD_CHILD_COUNT ** (MAX_SHARD_DEPTH-1)
, then the children is an empty listshardId < 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 shardId
is this header's shardId
multiplied by SHARD_CHILD_COUNT
plus (1 + the child's index in the list)state_branch_node
is the hash of the post_state_root
together with the state_branch_node
of each child; if a given child is empty then we take the current state branch node of that shard.0 <= sigIndex < SIGNATURE_COUNT
, let validationCodeAddr
be the result of calling sample(mixhash, shardId, sigIndex)
. A signature is "valid" if calling validationCodeAddr
on 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.