On-chain message ordering using Teleporter

[vikinatora]

Context

As stated in #42:

Teleporter by default does not enforce strict ordering, and messages can be delivered in any order. Some dapps may like the strict ordering functionality, and can be done so on chain.

This discussion aims to present two approaches, along with their respective pros and cons. I hope this will stimulate a discussion, dissecting possible solutions, and hopefully, we can converge on a reliable and effective one.

Approach 1 - Ordering on the Messenger layer

Overview

This approach implements the ordering on the Messenger(ITeleporterMessenger) layer. This is a higher-level approach, resulting in abstracting away the complexities away from the users. As long as, the message is sent and delivered using this Messenger, the messages are guaranteed to be delivered to dapps in corect order.

However, it’s a slightly riskier approach(than the 2nd approach) because a bug would compromise all subnets and dapps that use this specific Messenger. Additionally, if this approach is chosen, then the Messenger’s contract address would be different than the standard one between subnets after deployment as byte code will be different, following Nick’s method. This is not an issue as TeleporterRegistry exists, allowing for new Messengers to be deployed. Dapps can decide for themselves which versions of Messenger to allow. Time means that this approach couples origin subnets to have the same Messenger deployed and it must be the one used to send the message because of a validation.

Implementation

The steps below are not an exhaustive list of the changes required. They serve to highlight the main differences with the current Messenger implementation.

Modify Messenger protocol(receiveCrossChainMessage) to feature ordering of messages:

• Add new mapping which tracks latest received message IDs

mapping(bytes32 destinationBlockchainID => uint256 messageID)
        public latestReceivedMessageIDs;

• Add validation for teleporterMessage.messageID

require(latestReceivedMessageIDs + 1 == teleporterMessage.messageID, "Strict ordering of messages is enforced")

• When message is out of order:
  • Add it to receivedFailedMessageHashes so it can be reexecuted using retryMessageExecution
  • Reject it

Issues

Issue 1: When two messages are sent in a quick succession, a reordering of the messages can happen on the relayer layer(f.e because of incentivization). In that case, the messenger contract will receive the message with id 2 before the message with id 1. This blocks the execution of messages with id greater than 2 because 2 won’t be executed as it arrived first.

Possible solutions:

• An additional actor should be monitoring the contract and trying to execute stuck messages when their order has come.
• Messenger layer could reexecute out of sync messages when all preceding messages are delivered. With this approach, we have to think about the gas left edge cases, ultimately leading the implementation to have an additional function for executing messages either way.

Approach 2 - Ordering on the dapp layer

Overview

This approach implements the ordering on the Receiver(ITeleporterReceiver) layer. Less risky approach as risk of bugs is isolated in the dapp contract itself. Additionally, ordering isn’t tied to Messenger layer’s messageID, lowering the security assumptions and trust between the two layers. This way a dapp can have it’s own custom ordering functionality.

Implementation

A possible implementation would have some additional logic inside receiveTeleporterMessage:

• Enforce an id field in each teleporter message (different than messageID because ITeleporterReceiver doesn’t have access to messageID)
• Enforce any custom ordering logic that the dapp’s use case requires

Issues

The real message execution order could be tricked. Let’s take these two messages that are sent in quick succession. Message A is sent by a good actor and Message B by a bad one, looking to take advantage of the dapp’s protocol.

Message A:
{
	messageID: 1
	payload: {
		id: 1,
		data: "something"
		
	}
}

Message B:
{
	messageID: 2
	payload: {
		id: 1,
		data: "something"
	}
}

If for some reason(f.e incentivization) message B arrives to the destination subnet’s dapp before message A, then the dapp can be tricked to believe that B has been sent earlier than A because it doesn’t have access to messageID.

Possible Solution

• Make current messageID and previous messageID accessible on the Receiver Layer by changing signature of receiveTeleporterMessage and modifying Messenger layer’s _handleInitialMessageExecution payload encoding

Note: The reason lastSentMessageID is made accessible is because messageID is an identifier on a subnet level. A dapp could receive message ID 1 and message ID 4 after, and that would be completely fine, as long as the other 2 messages(IDs 2 and 3) were meant to be delivered to other dapps.

function receiveTeleporterMessage(
        bytes32 originBlockchainID,
        address originSenderAddress,
				uint256 messageID,
				uint256 lastSentMesageID,
        bytes calldata message
    ) external;

• Add a field that tracks the latest received message

uint256 latestReceivedMessageID;

• Implement ordering validation inside receiveTeleporterMessage

require(lastSentMesageID == latestReceivedMessageID, "Last sent and last received message IDs don't match")
require(latestReceivedMessageID < messageID, "Strict ordering of messages is enforced")

Note: If we just want to make sure ordering is correct, the 2nd validation isn’t required and can be removed.

• Update latestReceivedMessageID

latestReceivedMessageID = messageID

• In case an out of order message is delivered, it’s up to the dapp to decide how they should handle them.

One approach would be to store them in a field and expose a function that executes them as long as it’s their order. Storing only the message bytes may be an oversimplification but it gets the point across.

mapping(bytes32 messageID => bytes message)
        public outOfOrderMessages;

function retryMessage(uint256 messageID) external;

function receiveTeleporterMessage(
        bytes32 originBlockchainID,
        address originSenderAddress,
				uint256 messageID,
				uint256 lastSentMesageID,
        bytes calldata message
    ) external {
...
	outOfOrderMessages[messageID] = message
...
}

Open questions

• Is there an approach that requires changes only to the Receiver layer while maintining good security assumptions?
• Given the differences in risks and security assumptions, should the users be able to decide which approach to use for their specific use case?

Edit: fixed links not showing up correctly

[cam-schultz]

Hi @vikinatora thank you for opening this discussion! We especially appreciate the detailed consideration of the tradeoffs with each approach.

Our strong preference for message ordering is to do so at the dapp level, rather than at the Teleporter protocol level. For the reasons you mentioned, as well as the increased implementation complexity in the TeleporterMessenger contract (and with that, increased attack/vulnerability surface area), we elected to not have Teleporter guarantee message ordering at the protocol level. Rather, we leave that to dapps built on top of Teleporter to implement if desired.

Your second approach - Ordering on the dapp layer - uses the Teleporter message ID as the sequence number within the dapp. This introduces edge cases with respect to new versions of TeleporterMessenger registered in TeleporterRegistry. Each TeleporterMessenger instance maintains an independent list of message IDs, so these would have to be coordinated at the dapp level.

Rather, we suggest implementing ordering entirely at the dapp level by including a sequence number as part of the Teleporter payload itself. The dapp would therefore have full control over the sequence number generated on the sending side, regardless of which TeleporterMessenger version is being used. As an example, the receiving logic could look something like:

(uint256 sequenceNumber, bytes memory callData) = abi.decode(
    message,
    (uint256, bytes)
 );

require(latestReceivedSequenceNumber + 1 == sequenceNumber, "Strict ordering of messages is enforced");

[vikinatora]

Hey @cam-schultz, thanks for the insightful reply. I didn't consider this Teleporter message ID edge case, so that's another con to that specific approach. I agree with you and it's my belief as well that dapp level ordering is the better approach at the moment.

With that said, our team's going to provide a scope with the changes required to contribute this example to the repository soon.