Multihop

[LayneHaber]

Motivation

It is important to allow the same payment to be routed through multiple chains (i.e. A→C, C→B instead of A→B) to allow the user to take advantage of better pricing throughout the transfer lifecycle.

However, it is important that the user does not get saddled with assets on the intermediary chain and the routers do not get saddled with assets on a chain they do not support.

Considerations

• It is important to not introduce any additional round trip messaging. This imposes stricter liveness requirements for routers, which are quite onerous.
• It is important to ensure the user never ends up on the intermediary chain. This should never happen, as the hop will always be router to router.
• The fulfill condition must be the same for each leg of the transfer. On fulfilling, both routers are incentivized to play nice unless they are the ones who are left holding the bag. Additionally, they would have to wait until the transfer expired to attempt any double dipping. See Removing Collaborative Cancellations #758 .
• When routers submit bids, they should submit both direct and indirect bids (i.e. I can satisfy the A->B route OR I can satisfy the A->C / C -> B leg of the route). Ideally, each router should only submit indirect bids when they cannot satisfy the direct bid. However, it may be desirable (though more complex) to submit a direct bid if you can and your cheapest indirect bid.
• Users cannot specify a receivingChainId (as this will be unknown at the time of preparation), but instead must specify a destinationChainId.

Key Questions

• Should routers submit the start -> intermediary indirect bid, the intermediary -> final indirect bid, or their cheapest of both?

Potential Solutions

MultihopConditionInterpreter
Pros:

• Easily fits into existing frameworks

Cons:

• Requires the user to specify in advance if they will use a multihop transaction

Open Questions:

• User signatures are only great UX when they happen through the wallet natively, and they're also problematic for contract integrations. Could a hash of the route + secret be used instead?

struct Route {
  address router;
  uint256 chainId;
  address assetId;
}

struct MultihopConditionData {
  bytes32 lock;
  Route[2] route; // [A->B, B->C]
}

contract MultihopConditionInterpreter is IConditionInterpreter {
  // Tx data would have to specify an origin and a destination chain
  // The `conditionData` in the tx should specify a hashlock, and have
  // empty placeholders for a `receiver` and `chainId`
  function shouldPrepare(
    TransactionData calldata txData,
    uint256 transactionManagerChainId
  ) external pure returns (bool, Balance[]) {
    // Decode the Route

    // If this is the origin chain, then there should only be the hashlock 
    // in the conditionData to allow the auctioneer to assign the Route

    // Otherwise, a full route should be supplied. Validate all balances.
 }

  function shouldFulfill(
    TransactionData calldata txData,
    bytes calldata unlockData,
    uint256 transactionManagerChainId
  ) external pure returns (bool, Balance[]) {
    // In all cases, check that the user signed the full route and provided
    // the correct secret.

    // If on the origin chain, the Route cannot be verified against the
    // conditionData. In this case, it is okay to validate the secret only
    // as the user would only stand to get rugged and *must* provide it
    // correctly. Though it does mean the full signed packet must be
    // provided in the unlockData

    // Use the route information and the current `chainId` to determine how
    // balances should be disbursed
  }

  // Called prior to executing cancel
  function shouldCancel(
    TransactionData calldata txData,
    bytes calldata unlockData,
    uint256 transactionManagerChainId
  ) external pure returns (bool, Balance[]) {
    // Use the route information and the current `chainId` to determine how
    // balances should be disbursed
  }
}

[jakekidd]

Requires the user to specify in advance if they will use a multihop transaction

Why? Why does the user care if it's a multihop or not? We can just obfuscate determination of whether it's a multihop by carrying out that calculation on the backend in auctions. (See below)

When routers submit bids, they should submit both direct and indirect bids (i.e. I can satisfy the A->B route OR I can satisfy the A->C / C -> B leg of the route). Ideally, each router should only submit indirect bids when they cannot satisfy the direct bid. However, it may be desirable (though more complex) to submit a direct bid if you can and your cheapest indirect bid.

I really like this solution. Routers can make only 1 direct and 1 indirect bid per auction. Given that the routers are sort of "making a bet" in terms of which indirect bid they choose (e.g. "should I indirect bid for A -> C or A -> D? Are there more routers that have C -> B or D -> B?")

To assist this process, there could be an off-chain "routing table" on each router. Like, in the background, a router can examine the network of liq and index it regularly. So when the "A -> B" tx comes along, it can say "oh, I go from A -> C, or A -> D, but there is a lot more liquidity in the network for going from C -> B".

This enables the router to confidently respond to an "A -> B" auction request by making the bid for the "A -> C", knowing that many others can tack on the bid for "B -> C". The auctioneer can easily calculate the best bid sum from there, assign it to those routers, and package it into a multihop transfer for the user. The user will see it's a multihop and sign if they're cool with that.

Also, a routing table mechanism would be necessary to keep auctions fast. Would suck for auctioneer to ask for "A -> B" only for every router to start thinking and scanning every liq route in the network.

Also also, with VAMMs it's actually possible that a multihop might be a better deal than a standard transfer! Huge.

[jakekidd]

Should routers submit the start -> intermediary indirect bid, the intermediary -> final indirect bid, or their cheapest of both?

With what I wrote above, routers should only bid their "start -> intermediary" first. We're talking about auctions NATS messaging here so any other router that has an "intermediary -> final" that sees the first router's bid is now able to toss in that indirect bid.

[LayneHaber]

This adds a lot of latency, as all routers are waiting for others to bid. Also, ideally the bids submitted aren't interdependent.

In general though, agree there could be a lot of improvements in the offchain pieces about how an auctioneer selects the right bids and types of transfers. Once we establish this is possible though, this discussion should mostly center around the contract changes required to implement the type of transfer.

[jakekidd]

This adds a lot of latency, as all routers are waiting for others to bid. Also, ideally the bids submitted aren't interdependent.

Ah, but I guess we could have it so it goes both ways - routers can bid to be the endpoint or the starting point or somewhere in between, regardless of whether the other points already have bids.

[jakekidd]

Requires the user to specify in advance if they will use a multihop transaction

Okay so, above I asked why this is the case - it's clear to me now that the data structure for multihop that needs to be signed is different from the standard 1-step route.

What if we make it so the route the user signs could either be a 2+step or 1-step route? Make the Multihop path length variable, and that way we can deconstruct the signed data in fulfill regardless of whether it's a multihop transfer? I.e. every transfer will include MultihopConditionData

The problem with the above is that multihop requires a secret, right? There are some use-cases that don't allow for a secret (or it's really incovenient).

I propose that instead of having the user say ahead of time whether it's a multihop, we have the user say ahead of time whether it can't be a multihop (as easy as attaching a boolean).

In fulfill if it's a transfer that can't be a multihop then we'd expect the secret to be "0x0" and the route array to only be 1 step in length.

[jakekidd]

Based on some notes from @LayneHaber , think this solution has some issues too? If so, look at the comment below this one that builds on the base proposed case

[LayneHaber]

Problem being the same mentioned in the Outstanding Questions section of #754 -- if we do this, we require every interpreter to duplicate the logic. There should be better solutions to this problem.

[jakekidd]

So I guess if the above solutions don't actually work (due to a blind spot) we need to solve the problem of how a user knows they need to specify something is a multihop transfer ahead of time.

This means the user needs to make a sort-of routing table of their own - but oriented towards a specific route. If thy didn't make a routing table, then I mean, sure, they could look and see that there's no routers that can do A -> B at the moment and say "okay, let's submit a multihop and hope that they figure it out / find a way in auctions to do it and still be within my slippage range". But what if there is no possible route? User just has to wait 3 days for expiry. Not great UX.

So yeah, just something to keep in mind with this solution. Totally doable, but we need to note that additional work will need to be done in the SDK to determine whether a transfer is possible both as a direct transfer and a multihop one

[LayneHaber]

User just has to wait 3 days for expiry.

With the contract upgrades the expiry times should come down significantly, see #758

I think we should do everything we can to keep the user ignorant of the route finding mechanics. An important piece of this upgrade is that the SDK should become as lightweight as possible, with it also being completely optional to implement (i.e. you only use subgraphs and contracts and have the same experience).

[jakekidd]

I think we should do everything we can to keep the user ignorant of the route finding mechanics.

Okay, so it's okay if a user does a prepare and then they find out a route isn't possible, so they have to wait for 12 hours ish (expiry)?

I guess at the very least we could make a (verifiable) endpoint for getting whether a route is viable.

[ArjunBhuptani]

(Terminology note: assume that in a multihop transaction, when I say router n, n refers to the specific hop on a given path. Example: user -> router 1 -> router 2 -> user).

After thinking through this extensively today, I'm becoming convinced that there's actually no way to simultaneously have the following properties:

1. No additional offchain coordination (unidirectional flow of info from routers to auctioneer and no direct comms between routers)
2. Guaranteeing a full path (i.e. user funds cannot just get sent and get stuck somewhere and/or the path is predefined).
3. Transfer from router 1 -> router 2 is noncustodial.

This is because, in order for (3) to be the case, router 2 must either (a) know that the funds have already been locked up onchain, or (b) have a signature from router 1 allowing them to claim funds in the future. This leads us to a weird outcome:

• The only possible way to do (b) is for router 1 to communicate with router 2 directly, which violates (1) above.
• The only possible way to do (a) is for router 1 to submit their tx onchain and for router 2 to detect this. However, there is no way for router 1 to know as part of their signed bid that router 2 will be selected for the second hop, and having a prespecified second hop counterparty also now imposes a new liveness condition for router 2.

If we're forced to give up one of the properties above, it seems to me like the property to give up is (2). Giving up (1) would lead to a massive increase in complexity which means many more failure modes. Giving up (3) means that routers now have no incentive to do any multihop transfers, which lands us right back where we started.

Additionally, if we give up (2), we no longer prespecify router 2 in a multihop path. While this means that a user's funds could theoretically get stuck somewhere, it removes the liveness condition for any router that would be a second hop on a multihop path. It also means that we can largely use existing mechanisms/flow for doing the multihop transfer, rather than having to write custom code.

Proposed multihop flow

Instead of needing any custom code, the flow would look like the following:

1. User calls prepare on origin chain (with unspecified router, as is normal in auctionless) with a recipient (could be user)
2. Routers see the transaction and begin bidding. Similar to @LayneHaber's proposal above, routers can submit both direct and indirect bids.
3. Auctioneer finds that there are unfortunately no bids that allow for a transaction directly from origin to destination within a certain price/slippage tolerance. Instead, auctioneer chooses a bid from router 1 that sends the transfer to an intermediary chain - @jakekidd long term we can probably use your above suggestions here by having the auctioneer keep a routing table to figure out which chains are most likely best connected to a given receiving chain. To start with, this could just be Polygon (since that's the most well connected/liquid atm).
4. Router 1's bid is sent to chain which calls prepare on the intermediary chain but with user's recipient (with unspecified router, similar to (1)).
5. Now, the transaction just goes through the normal process to get prepared on the destination chain. The only exception to this is that router 2 MUST make sure to include the full multihop path as part of their prepare on the destination chain.
6. To fulfill, the user signs a message that includes both routers in the path, such that the correct router can unlock funds on each chain.

The great thing about this model is that there are pretty much 0 contract changes needed that are specific to multihop except for needing a path on the destination chain prepare.

Note again that it is possible for the transfer to get trapped on the intermediary chain. However, this is probably ok because:

• The user would already have been "stuck" on the origin chain if no router was able to complete their tx.
• The user's tx is being sent to a more liquid/connected chain, which means that they are now more likely to get routed than their origin anyway.

[jakekidd]

The user's tx is being sent to a more liquid/connected chain, which means that they are now more likely to get routed than their origin anyway.

Good point, but maybe we could add an additional flow for "re-auctioning" this transfer?

It seems like bad UX if it got stuck and we were just like "oh well, sorry it didn't make it all the way!" Like, what if the user has never even heard of the intermediary chain lol.

Don't get me wrong, I see your argument and agree with your choice of (2) above, but I'm wondering if it'd be possible to have a way to get things unstuck by re-auctioning off the transfer based on Router 1's sender prepare on the intermediary chain. Maybe we shorten the expiry for Router 2 to do prepare on destination chain? hmmm

[ArjunBhuptani]

Good point, but maybe we could add an additional flow for "re-auctioning" this transfer?

Can you explain what you mean by "re-auctioning" the transfer?

The transfer that router 1 makes is absolutely going through the auction process again - it's basically just a normal transfer from the perspective of the network. (Shortening expiry will definitely be needed regardless here bc you need to decrement expiry for every hop)

[LayneHaber]

I think this will require contract changes to play nicely with #754 because we use the chainId context and the information provided within the transaction data to evaluate if funds should held onchain (for routers) or transferred out (for users).

The contract changes could be fairly simple, let me try to outline them below:

• The TransactionData / RoutingData would be updated with the following:

struct RoutingData {
  uint256 chainId; // chain for router <> router transfer
  address assetId; // asset for router <> router transfer
  uint256 amount;
  address router;
}

// User must always sign the final route for sending chain verification
struct SignedRoute {
  RoutingData[] route;
  bytes calldata signature;
}

struct TransactionData {
  ...
  RoutingData[] route;
  uint256 originChainId; // replaces sending chain id, must be invariant and specified by user
  uint256 destinationChainId; // replaces receiving chain id, must be invariant and specified by user
  address originAssetId;
  address destinationAssetId;
}

• In the TransactionManager you can add additional logic around the added chain context:

function prepare(PrepareArgs args) {
  ...
  if (chainId == TransactionData.originChainId) {
    // This is a user
  } else if (chainId == TransactionData.destinationChainId) {
    // This is the router on intermediary -> destination hop.
    // Must use the user's predetermined destination assets
    
    // The router here must put the full route onchain to verify users
    // signature. If they don't they will ultimately be out of pocket.
  } else {
    // This is the router on sending -> intermediary hop, they will put the
    // router information for *this hop only* onchain.
    
    // Enforce that the route length is 1 (i.e. this is a multihop transaction)
    
    // Enforce this is the intermediary chain id + handle router lock up
  }
}

function fulfill(FulfillArgs args, SignedRoute) {
  if (chainId == TransactionData.originChainId) {
    // This is a final router
  } else if (chainId == TransactionData.destinationChainId) {
    // This is a user
  } else {
    // This is the router on intermediary -> destination hop fulfilling from the router on
    // sending -> intermediary hop. At this point in the transfer, you don't have the full
    // route stored onchain, but similar to multipath, you can rely on what the user signed
    // since they will have to sign correctly to claim funds on the destination chain
  }
}

Some remaining questions I have:

• How can we flag onchain that the transaction should not have nested multihops? Do we need to enforce this onchain? I'm afraid if we don't we will introduce special-case code.

[LayneHaber]

Archiving, no longer relevant