ETH-specific message delivery protocol

[tomusdrw]

Neither #318 nor #215 delivery protocol is suitable for ETH Mainnet. They both require Substrate storage proofs, which in turn need a full header + state root for verification. The goal is to make a delivery-protocol that is going to be quite specific to Ethereum, and will not require any extra builtin contracts nor excessive data to provide alongside the proof. We also need to cater for Ethereum's low bandwidth and gas price fluctuations, so that the incentivisation mechanism is robust for the relayers to do their job. The bridge builds on top of #323
Each constant in the issue (i.e. 2x or 1/2) is subject to discussion.

Substrate -> ETH

The proposal is to create a substrate pallet that will be responsible for:

1. Keeping track of current ETH block weight and gas price required for last relay (minimal gas price).
2. Queueing up outbound messages (ordered by the fee) and producing a hash (sha256 hashing) of messages that can be relayed in the next batch which does not exceed 1/2 of the current block weight.
3. The hash of all messages in "block" is put into the MMR for efficient verification on the ETH chain.

Structures

/// A batch of messages to relay to the ETH chain.
/// `min(max_gas_price)` of all messages should be at least 2x of the minimal gas price 
/// `sum(gas_limit)` should be at most `1/2` of last gas block limit
struct MessagesBlock {
  /// A block number on substrate chain this `MessagesBlock` is generated in.
  substrate_block_number: U256,
  /// the `messages_hash` of the previous block, to make sure we didn't skip any.
  parent_messages_hash: Hash,
  /// A list of messages to deliver to ETH chain.
  messages: Vec<Message>,
  /// Hash of all messages in this block.
  /// This thing is part of the MMR.
  // messages_hash: Hash, // this can be computed from `messages`
}

/// A single message being relayed.
struct Message {
  /// maximal gas price the sender is willing to pay
  max_gas_price: U256,
  /// maximal amount of gas the call will utilize
  gas_limit: U256, 
  /// A sender of the message
  sender: AccountId/Vec<u8>,
  /// A message itself (the interpretation of this is outside of the scope of this issue)
  payload: Vec<u8>, 
}

Substrate pallet (Substrate side)

decl_storage! {
  MessagesByHash: map Hash => Message;
  MessagesOrdered: Vec<(GasPrice, GasLimit, Hash)>;
  RecentGasPrice: GasPrice;
  RecentBlockLimit: GasLimit;
  LastSentMessages: MessagesBlock;
  /// This requires price oracle to calculate the fees.
  RecentEthToDotRate: Perbill;
}

decl_module! {
  /// Add a new message to relay to ETH side.
  /// This may drop some lower-gas price messages from the pool.
  /// The message can only get in if `max_gas_price > 2 * RecentGasPrice`
  /// This locks a fee of `max_gas_price * gas_limit * RecentEthToDotRate`.
  fn add_message(origin, Message);

  /// Replace a previous (unsent) message with a message with higher gas price.
  /// Note it's fine for a sender to have multiple messages in the queue, but they are always ordered by `gas_price` (no nonce).
  fn replace_message(origin, Hash, Message);

  /// Called by the relayer node to prove delivery & dispatch of the previous messages block.
 //// Contains event proof of the ETH side, which contains  all required info.
  /// This updates `RecentGasPrice` and `RecentBlockGasLimit`. May trigger events
  /// regarding dispatch.
  /// It should pay the fees to the relayer. The amount we pay the relayer for each transaction is:
  /// `(max_gas_price - RecentGasPrice) * gas_limit / 2`
  /// The rest is returned to the sender.
  fn confirm_dispatch(EventProof);
}

At the end of every block (or maybe in on_initialize of the next block):

1. If LastSetMessages is not empty or MessagesOrdered is empty we do nothing. (note we may consider having up to 2 (or more) message blocks pending)
2. We take (remove) up to RecentBlockLimit / 2 messages from the MessagesOrdered. (removed from MessagesByHash as well).
3. We calculate the hash of these messages and form a block.
4. We update LastSentMessages value with the MessagesBlock data.

The idea is that the pallet will serve as a simple messages queue, ordered by the gas price the sender is willing to pay. The senders are expected to declare a gas price high enough (2x or more) so that we can be sure that it's possible for relayers to actually cover the costs on the ETH side. Since we track RecentGasPrice, which indicates the actual gas price the relayer had to use to get to the block, we can return the overpayed fee to the sender, but at the same we reward the relayer for not simply paying the highest possible fee (they also earn the difference between gas_limit and actual used_gas).

If the senders see that messages are not getting through, they can simply replace them with ones that pay higher fee - that way the relayers can decide to relay a block even below their profitability point, just to be able to unlock the next block.

Note that without any buffering, we may only start relaying the next MessageBlock if the previous one is on-chain and is confirmed to be final. This adds quite a lot of delay between messages, so a more sophisticated mechanism is most likely required.

Solidity contract (ETH side)

A relay calls the contract and passes the next MessagesBlock. The contract then:

1. Verifies that parent_messages_hash matches the last-received one storage in the state.
2. Verifies that messages_hash matches the one we have in the MMR for substrate_block_number.
3. Verifies the MMR proof.
4. Takes messages one by one and dispatches them.
5. Produces an event containing (MessagesHash, GasPriceOfTheTransaction, BlockGasLimit, Vec<DispatchSuccesful>)

ETH -> Substrate

This side seems a bit easier on the first sight. We might consider just generating ETH events in the contract and then have each event contain a separate message that get's relayed in-order (increasing nonce) to the substrate side. This scheme should be more alike #318, where each message (event) has:

(LaneId, Nonce (in-lane), EthSender, Payload)

The delivery is confirmed on the entire Lane and the confirmation releases the fee, locked on the ETH side. To trustlessly confirm delivery we need to make the lane state part of the MMR as well (A merkle-tree of lane statuses, with root hash placed in the MMR). I haven't thought exactly how we can propagate fee information from Substrate -> ETH yet, but I imagine this could happen through a system-generated (substrate's root account as a sender) messages transferred via Substrate -> ETH delivery protocol for instance (which would just update Solidity contract).

[tomusdrw]

I've realised that relayers can increase gas price requirements arbitrary, so instead I propose a slight alteration.

We add ExpectedRelayTime, which is for instance a moving average of the difference between delivery confirmation and message block creation time. Instead of paying the relayer (max_gas_price - RecentGasPrice) * gas_limit / 2 the price component is unlocked linearly if the ExpectedRelayTime is exceeded. (Assume all ops are saturating) I.e.:

let relay_time_factor = min(1, (RelayTime - ExpectedRelayTime) / ExpectedRelayTime); // how much delayed are we? 0-1
(0.5 * max_gas_price + 0.5 * max_gas_price * relay_time_factor - RecentGasPrice) * gas_limit / 2

That way, relayers are incentivised to look for a smaller GasPrice within ExpectedRelayTime to get any profit. The incentivisation scheme most likely needs a lot of fine-tuning and way more analysis though, since long-term if the gas price stabilises there is little incentive for the relayers to actually take part, so a small fee might be required to be payed even if we stabilise at the optimal gas price.

[tomusdrw]

Closing, since the ETH bridge is being worked as W3F Grant in polkadot-ethereum repositry. Happy to re-open if the outlook changes.