Sidechain Fork Mitigation (Epic)

[murerfel]

This epic emerged from #345 - summarizes the results of those discussions and anchors all the tasks created from it.

Specification

Fork detection

• Each validateer should detect forks, even within a parentchain block cycle
• Parentchain block determines finalized sidechain blocks and thus the branch that is valid
  • Needs to be checked at each parentchain block import
• When a fork is detected, a validateer remains on its current branch until finalization by the parentchain
  • This is the 'laziest' approach, minimizes effort (e.g. a 'random' scheme could mean to roll-back and switch branch, but still be wrong in the end)
  • Alternatives: Random choice of branch, stop production, choose the longest branch

Finality

• Parentchain finalizes sidechain blocks
• Extrinsic must be extended to include the sidechain block header, not just the block hash
  • Header contains hash of block payload and hash of parent block
• Parentchain determines order of sidechain block
  • Simple queue, builds order of sidechain blocks - eagerly where possible
  • Queue size in the order of #sidechain blocks per parentchain block ~40
• Logic must be built into the pallet
  • Execution of logic should be O(1) whenever possible
  • Optimize for 'write' or mutation

Roll-back

• Store snapshot of state after each block
  • Need some bookkeeping to easily map a block hash to a snapshot
  • Apply specific snapshot on roll-back
• Transactions are marked 'InBlock' and only removed once finalized
  • For roll-back, see how Substrate does it: Either move 'InBlock' transactions back to 'Ready' or remove entirely from pool

[murerfel]

Also linked to #855 for sidechain finality