Optimistic scheme support in Beefy interactive protocol

[hackfisher]

https://github.com/darwinia-network/darwinia-bridge-sol/pull/38#discussion_r654230826

Need draft design spec and protocol before implementation

[hujw77]

Using Fee market to incentive relayer interact the protocol. See https://github.com/darwinia-network/darwinia-common/issues/776

[hackfisher]

Using Fee market to incentive relayer interact the protocol. See darwinia-network/darwinia-common#776

Different with the relayer fee market on the source chain, Optimistic scheme mentioned here is a sub protocol of beefy on target chain which need extra detail design.

[hackfisher]

In this document, describe some optimistic schema we need notice:

https://hackmd.io/ohOt4jAPT8uu-soJXHUq0Q#Optimistic-scheme

A protocol with competing initialization transactions for a given statement $S_n$ is only required whenever

1. the designated relayer for $S_n$ times out on the initialization transaction or submits a malicious statement $S'_n$
2. the designated relayer for $S_n$ times submits a valid initialization transaction, but times out on the finalization transaction

Malicious statement are expensive to detect since the full fault proof might need to include all grandpa sigs.

Currently, we simple take the strategy to slash the relayer who didn't do finalization transaction in time. or do finalization wrong.

For those initialization transaction the light client require, but no relayer do initialization transaction. we might require to take following actions. But I think it is unnecessary since other relayers will also help do it.

The only root cause for not doing it is due to the lack of incentive, or relay on demand design. Relayer fee market will help resolve the first one, and for relay on demand design, following actions are useful to optimize the gas rather than providing competing initialization transactions.

Assuming that these costly situations are rare, we can take an optimistic approach where on the Polkadot side, we already commit to the relayer for $Sn$ much earlier and include their identity in the statement $S{n-k}$, where $k$ is a tradeoff between the minimum distance between Polkadot blocks that we relay and the number of backup relayers, and the range of statements for which we must pre-commit to designated relayers.

This would then allocate a mutex for $Sn$ for a block range within which the smart contract will only accept initialization transactions from the pre-elected relayer. If and once the relayer chosen in $S{n-k}$ times out on the initialisation transaction for $Sn$, the relayer for statement $S{n-k+1}$ (who was elected for relaying statement $S_{n+1}$) attains the mutex for $S_n$ on the initialization transaction and submits this initialization transaction instead.

This scheme can be iterated for up to $k-1$ failures, at which point we must revert to a protocol with competing initialization transactions. As such, $k$ increases the number of backup relayers we can have to remain within the optimistic scheme, but thus also increases the impact a sequence of colluding designated relayers can have.

[^designation-motivation]: The motivation for having a designation procedure is that the second transaction will be very expensive, yet we will only refund one single relayer for sending it