Shard fast sync protocol

[hwwhww]

The previous fast sync procedure for simulation is a lazy simplified approach. Thanks to @vbuterin, the new approach applies more verifications of the recent collations and more reliable.

Wire protocol message

0x08 GetShardData

[+0x08: collationHash: B_32] Request for the shard chain state snapshot which contains collationHash of the required collation.

0x09 ShardData

[+0x09: stateSnapshot: B, collation: Collation] Reply to GetShardData. Reply must contain the compressed state snapshot and the head collation of the given state.

Shard fast sync algorithm

• Assuming that the main chain has already been synchronized
• The Fast sync requester broadcasts a GetShardData request, which indicates a collation hash collationHash as the head collation required state on shard chain. Note that the collationHash is a pivot point collation. e.g., it can be the 100th ancestor of the head collation on validator manager contract, so it's more reliable then the head collation since the pivot point collation is supposed to be finalized.
• Assuming the required depth between head collation and pivot point collation is PIVOT_DEPTH; default value is 100. The pivot point is head - 100 collations.
• On receiving GetShardData message:
  • Check if collationHash exists in this shard
  • Send a ShardData message which contains:
    • the compressed state with collationHash as head collation
    • the collation of collationHash
• On receiving ShardData message:
  1. Get state from snapshot
  2. Verify if the collation is correct:
     • Check the validator manager contract:
       • collation.header.hash equals the record on validator manager contract
       • collation.header.score equals the record on validator manager contract
  3. Verify if the state is correct
     • The state root equals collationHeader.postStateRoot
  4. Verify if the given state is reliable enough
     • The head collation score on the validator manager contract is greater than collation.header.score plus PIVOT_DEPTH
  5. Apply the given collation and state
• The fast sync requester downloads the collation headers and bodies of the following collations

[hwwhww]

There's a new design: #26