[bridge] Replay protection on L2

[apenzk]

Problem

This considers a transfer from L1 --> L2.

The relayer may (maliciously or by accident) complete a transfer on the target chain (L1) twice. This needs to be prevented, as it constitutes a double spend.

Background

MIP-58: Trusted-Relayer focused Bridge Design

Solution

Transfers are identified on the source chain (L2) in the Move contract by L1L2bridgeTransferId. The native bridge contract on the target chain MUST keep a list L1L2bridgeTransferIds and the contract MUST check if the requested completion of a transfer by the relayer has been already previously completed.

Recommendations

DO NOT use bridgeTransferId. It should be crystal clear from the code that this is an L1-->L2 transfer.

[franck44]

A transfer initiated on L1 is identified by a tuple: $d=(receiver, sender, amount, nonce)$.
Each new transfer gets a fresh nonce, so every tuple is unique.

If the relayer is trusted, it is going to relay the transfer details $d$ to the L2.

To ensure that a transfer $d$ is not completed (or processed) more than once on the L2, we have to:

• store the status of a transfer: completed/notcompleted
• when we complete a transfer $d$, set the status of $d$ to completed
• add a pre-condition to complete (mint on L2/unlock on L1): can only be executed if $d$ is not completed. (otherwise aborts.)

We can hash the tuple $d$ to get a compact representation $d^{\sharp}$ of the transfer.
A collision-free hash function ensures that for any two transfers $d_1$ and $d_2$ we have

$$d_1 = d_2 \iff d_1^{\sharp} = d_2^{\sharp}\mathpunct.$$

So on the L2 (or L1 in the other direction), instead of storing a map from (or a set of) transfer details $d$ to statuses $bool$, we may use a map from hashes to status (hash map, or a set).

The complete function pseudo code can be as follows:

// Transfer statuses
TransferStatusMap: map<u256, bool> // if we use a map, Initially empty
TransferStatusSet: set<u256> // if we use a set, initially empty

function complete(receiver, sender, amount, nonce: u256) 
// pre-condition:  
requires TransferStatusMap(hash(receiver, sender, amount, nonce)) == false // if we use a map
requires hash(receiver, sender, amount, nonce) not in TransferStatusSet // if we use a set
{
   // perform the transfer (Mint on L2, unlock on L1
   ...
   // update status: add hash of transfer to status map (or set)
   TransferStatusMap := TransferStatusMap + (hash(receiver, sender, amount, nonce) => true)
   // or
   TransferStatusSet := TransferStatusSet + { hash(receiver, sender, amount, nonce) } 
}

Note

With the assumption that the nonce uniquely identifies the transfer details, we do not need a hash but can use the nonce directly as the key in the map.

This way we simplify the complete function:

// Transfer statuses
TransferStatusMap: map<u256, bool> // if we use a map, Initially empty
TransferStatusSet: set<u256> // if we use a set, initially empty

function complete(..., nonce: u256) 
// pre-condition:  
requires TransferStatusMap(nonce) == false // if we use a map
requires nonce not in TransferStatusSet // if we use a set
{
   // perform the transfer (Mint on L2, unlock on L1
   ...
   // update status: add hash of transfer to status map (or set)
   TransferStatusMap := TransferStatusMap + (nonce => true)
   // or
   TransferStatusSet := TransferStatusSet + { nonce } 
}