Weak-subjectivity resistant synchronization

[rphmeier]

Here are our considerations:

• full nodes need to execute all blocks
• full nodes are somewhat limited in reorganization capability
• we don't have warp sync
• it's difficult to evaluate the fork-choice until we've already synced a bunch.
• the Polkadot light client has some kind of protection against weak subjectivity that we want to extend to our parachain.

Let's say we are synchronizing a generalized Substrate chain called Local.

Nodes on Local should attach a little piece of metadata (an inclusion-proof) to every Nth Local block called an "inclusion proof". It's a small state proof of the storage changing for the parachain head. There might be multiple of these blocks.

Light and full polkadot nodes can easily tell you the block hash of the ancestor of the finalized block, so the inclusion proofs will be useful.

Who generates these proofs? Any node at the head of the chain can probably do it. After we import a Polkadot block which updated the Local head, we want a merkle proof of the new storage entry. This is easy to check. We keep a list for every Local block with number % N == 0. These lists can be pruned on finality.

On block import of a Local block LB with number % N == 0, we query inclusion proofs for that block where the Polkadot block within is in the finalized chain. If there are none or the Polkadot block is not finalized, we simply import (for now). This is fine assuming that there is not a larger lag in finality than the client can cope with reorganizations.

[rphmeier]

WIth log2 ancestors (paritytech/substrate#2053):

1. Find latest finalized parachain block hash by querying the relay chain light client
2. Act as a light client of the parachain and use log2 ancestors to find older canonical block hashes
3. make sure sync service is downloading these blocks