[bridge] Bootstrapping the Relayer : learn from on-chain data which transfers from L1-->L2 still need to be completed.

[apenzk]

Warning

This issue describes a similar approach to #871 and thus it is recommended to discuss at the other issue !

Is your feature request related to a problem? Please describe.

The relayer can go offline or crash. It needs to automatically understand from where it should start with sending messages to the target chains, i.e. what is the lowest nonce for which the transfer is not complete.

The relayer MUST ONLY rely on the chains and itself. No other trust assumptions should be utilized.

Several complications:

• Complete-messages to the target chain for bridge transfers may fail, get lost, or other. Hence we cannot rely on delivery.
• The relayer may loose local memory.
• The relayer may have to be replaced.
• The relayer MUST not forget a single transfer.
• The relayer MUST deliver eventually all transfers.
• The solution MUST consider our finality criterias on L1 isL1final and on L2 isL2final.

Describe the solution you'd like

• The source chain maintains a list (e.g. hash map) of bridgeTransfer identifiers, e.g. L1L2BridgeTransferIds.
• The source chain maintains a list of L1L2nonces that increments for every added L1L2BridgeTransferId. There is a map with L1L2nonce --> L1L2BridgerTransferId
• The target chain maintains a list (e.g. hash map) of bridge Transfer identifiers, e.g. L1L2BriedgeTransferIds.
• The relayer loads FINAL L1L2BridgeTransferIds_fromL1 and keeps reading events from L1 to keep the list up to date. I.e. the relayer MUST only consider events that have isL1final==true.
• The relayer loads the final L1L2BridgeTransferIds_fromL2 and keeps reading events from L2 to keep the list up to date.

To enable restart with a brand new relayer, unaware of any state the following options come to mind:

1. Start at Genesis: The relayer has to compare the finalized L1L2BridgeTransferIds list from L1 with the submitted (included in a L2block) L1L2BridgeTransferIds list from L2 . Start at genesis time of Movement Network.
2. Start at configurable L2_height: Do 1) but use a closer date for start, e.g. tnow-2 days.. a bit more risky to miss bridge transfers.
3. Relayer records checkpoints in regular intervals: The relayer records in regular interval (e.g. once per 30min) on-L2-chain the highest L1L2nonce for which all previous transfers are completed and FINALZED on L2. While the relayer updates on-L2-chain these checkpoints (cheap because not frequent), the relayer finds out off-chain through some efficient algorithm what is the lowest L1L2nonce for which every transfer with lower nonce number is completed and finalized. (This solution has an unresolved problem: Checkout the investigation below)
4. Trustless but this is unnecessary: in-contract finding the right nonce: In regular intervals the relayer sends a bootstrap transaction. The bootstrap transaction runs an algorithm that checks what is the highest completed and FINALIZED (is this doable?) transfer below which all transfers (L1L2nonces) are completed.

To be investigated

• On L2 the relayer SHOULD consider all events, including those that are NOT final. What are the implications of this?
• If L2 reorgs, option 3. above is flawed as the relayer checkpoint update should not pass. Any ideas?