Transfer Batching

[LayneHaber]

Summary

Moving to Nomad comes with a large increase in gas costs on a per-transfer basis. We can reduce these costs by creating a batch of transfers and sending a merkle root representing this batch across chains. This will heavily alter the data passed across nomad, and merits separate ConnextRouter / ConnextMessage contracts rather than using the same BridgeRouter / BridgeMessage contracts.

Motivation

The current cost for a transfer is ~540K gas, which is already expensive, and using nomad for a single transfer increases the gas to ~810K (not including the nomad-specific transactions). This is too expensive of a tax to add on each transfer, and it is important to bring this cost down.

Proposed Solution

Batching the transactions that are handled by nomad has the advantage of amortizing the costs to dispatch and handle a message as well as the cost of minting / burning assets (as it is done on a per-asset basis within the batch instead of on a per-transfer basis).

You can batch these transfers in a couple of ways:

1. Merkle Tree: Leaves are generated from the hash of the transfer data and inserted into a tree. At some point when the batch is "full" (as defined by reaching the maximum number of assets permitted in the batch), the root is ready to be dispatched through the nomad system.

2. Onion Hash: The onion accumulates one transfer at a time, with each layer concatenating to the one before it: onion_n = Hash(onion_n-1 + message). When you are peeling layers off the hash, there is a strong LIFO ordering requirement.

In both of these models, you use the nomad messaging system to send a 32 byte hash to the destination domain as well as information about the assets included in that hash when the batch is "full" (as defined by reaching the maximum number of assets permitted in the batch). The TokenRegistry would permit the ConnextRouter to mint the batch amounts for each of the transactions when the data is reconciled, and process can prove the inclusion of a given transfer in the data. This flow is illustrated using merkle trees below:

In a few points, this boils down to:

• User calls xcall to enqueue a crosschain transfer.

  • A leaf including all user-supplied parameters is added to an onchain merkle-root representing the batch
  • The amount for the batch is incremented by asset

• At some point when the “batch is full” (heuristic can be flexible — time-based, asset-capped, etc.) the NXTP routers will call dispatch , which will kick off the sending via nomad. The message sent should include:

  • The merkle root of transfers. Each leaf should contain all the hash of the information passed to nxtp:
    • to
    • destinationDomain
    • originDomain
    • callData (for destination domain calls)
    • sender (origin domain msg.sender)
  • The amount, asset to mint/account for with each batch
  • The recipient
  • A type to indicate if this is an NXTP transfer or not

  When the message is sent across the nomad channel, the bridge should call reconcile which pushes the batch merkle root to the Connext

• At any point after xcall is called, routers can call execute .

  • If this is called before reconcile (i.e. before the root is onchain), they are providing “fast-liquidity” and to be reimbursed they will have to process the transaction
  • If this is called after reconcile routers are acting as relayers to swap into the adopted asset and execute any calldata on the destination domain

• Once reconcile is called (via the handle method on the BridgeRouter), then the router can call process to reveal the leaf information and get reimbursed if they provided fast liquidity

Bridge{Router,Message} vs. Connext{Router,Message}

In an ideal world, the Connext.sol contract would be responsible for only:

• Integration interface (specifically for executing crosschain calls, but not managing crosschain state)
• Executing crosschain data calls
• Managing asset complexity
• Providing fast-liquidity layer

while the Bridge{Router,Message} contract would be responsible for:

• Custodying user funds
• Minting / burning representational tokens
• Managing representational tokens
• Parsing and forwarding messages across chains

However, overriding the existing Bridge{Router,Message} contracts with the new message structure would fundamentally break the existing user flows. A good compromise is to turn the existing Connext.sol into a connext-specific router contract with minting permissions, which are managed via the TokenRegistry.

In this model the ConnextRouter is responsible for:

• Custodying user funds
• Providing fast liquidity
• Integration experience
• Managing asset complexity
• Integration interface (specifically for executing crosschain calls, but not managing crosschain state)
• Parsing messages

while nomad components retain responsibility for:

• Handling token representations
• Managing mint/burn permissions
• Forwarding messages across chains

Eventually we could move towards deprecating the BridgeRouter in favor of a consolidated interface.

Merkle vs. Onion

While onion hash does contain its size better (no tree stored onchain, can always be a 32 byte hash), the strong ordering requirement means one transaction can block an entire batch. This is a likely pain point, so these costs justify using the more expensive and flexible merkle tree.

Test Cases

Note: Not complete list!

// ========= Connext.t.sol =========

// Should add leaf to root and update batch asset information on xcall
function testXcall() public {}

// Should send to destination domain when full + clear existing batch information
function testDispatch() public {}

// Should handle information from remote routers properly. 
// - should mint batch amounts
// - should update incoming root
function testHandleMessage() public {}

// Should execute fast
function testExecuteFast() public {}

// Should execute slow
function testExecuteSlow() public {}

// Should fail to execute if already executed in slow case
function testDuplicateExecuteRevertSlow() public {}

// Should fail to execute if already executed and fast case
function testDuplicateExecuteRevertFast() public {}

// Should fail to execute if leaf is not in root
function testExecuteRevertNotIncluded() public {}

// ========= ConnextMessage.t.sol =========

// Should properly format message
function testFormatMessage() public {}

// Should properly extract token ids in batch
function testGetBatchTokens() public {}

// Should properly extract amounts in batch
function testGetBatchAmounts() public {}

// Should properly assert types
function testTypeAsset() public {}

Outstanding Questions

• Using the merkle root seems like were just adding a root on top of a root, is there a way to move this lower in the stack?
• What is the best way to mint the assets in a batch? In the v0 implementation, this is done in a for-loop which is annoying. Find relevant code here.
• What is the best message structure for the batch? In the v0 implementation, it included the 32-byte batch root as well as TokenId[3], amount[3]. Is there a better interface for this? Find relevant code here and here.
• What changes are required on the TokenRegistry to allow both the BridgeRouter and ConnextRouter to mint?

Tasks

Piggybacking off of v0 implementation found here.

• Convert Connext.sol to a nomad router
• Add in minting/burning capabilities to Connext.sol
• Add minting permissions to TokenRegistry for Connext.sol. Should be able to have both Connext.sol and BridgeRouter.sol as minters
• Remove unnecessary backwards-compatible code from BridgeMessage.sol, rename to ConnextMessage.sol
• Update all existing tests
• Unit test coverage

[LayneHaber]

Note:

If we can get the costs for a single transfer down to what they are now (~500K for full flow, including getting router reimbursed) I am willing to abandon this entire discussion. I just do not know if that is feasible without destroying readability

[LayneHaber]

Also, ideally the batching would be something marginally more elegant than "have you tried passing a merkle root into the merkle root"

[jakekidd]

hahaha had the same thought and it was legit tripping me out today reading this

[jakekidd]

almost feel like we should do the onion hash just to mix things up a lil

[jakekidd]

Where's that spreadsheet you had that showed how much this reduced costs by? @LayneHaber

[LayneHaber]

Here it is

[LayneHaber]

Update:

By combining Connext.sol and the BridgeRouter.sol functionality, we were able to drop the gas by 100K. We can move the stable swap logic onto the same contract, and likely reduce the gas by another 120K (60K for xcall and execute each). With these reductions, we bring the cost into the same ballpark as the batched transactions which means we don't need to include batching!!! 🎉 🎉 (gas cost sheet linked in comment above has updated numbers).

If we were to batch (and keep these improvements), we would be able to drop the cost much further, but batching introduces significant complexity to the protocol:

Charging fees
In the batching implementation, there would need to be one or two batch-level functions. It is unclear how to charge for these, and who should ultimately be responsible for paying. The network could subsidize these transactions, but it quickly becomes unsustainable.

Submitting the batch
Deciding when to submit a batch is also non-trivial, and involves navigating a tradeoff between cost and user experience. One option is to dispatch batches over nomad periodically on a fixed schedule. The advantage here is that if you are using the slow liquidity path, you know exactly how long it will take to execute on the receiving chain (max timeout = batch timeout + optimistic timeout). Unfortunately, submitting batches before they have at least 10 transfers in them is more expensive per-transfer than not batching at all. Another alternative is to wait until the batch has at least 10 transfers, then dispatching it. This will always be cheaper than the non-batched transfers, but has some disadvantages. First, it is never clear to those using the slow liquidity path when their batch will be dispatched. Additionally, it is not always easy to fill a batch as they always have to be in the same asset, origin, domain set.

While a decent tradeoff could be made by finding a combination of the periodic schedule and full batches, it makes charging fees much less predictable.

Archiving this discussion.