Xud: Batching swaps

[sangaman]

This is an offshoot of discussion in #654. From @offerm

Consider that the taker order is matched with 3 different maker orders.
How many communications we will do between the peers:
for each orders:

• 2 packets on XUD (deal request, response)
• 4 packets on LNDBTC (setup the HTLC)
• 4 packets on LNDLTC (setup the HTLC)
• 4 packets on LNDLTC (resolve the HTLC)
• 4 packets on LNDBTC (resolve the HTLC
• 1 packet on XUD (error/complete)

19 packets for a swap operation. We have 3 of them so we have a total of 57
packets.

If we do the aggregation we will only need 19 packets as we setup all the 3
orders together and we swap all the amounts together.

I think that the benefit of batching packets on the xud side alone is minimal, given that it doesn't change the number of trips between peers a swap must make before being executed. Batching on the lnd side might be a different story, although I'm also not sure there because we're still able to setup HTLCs for multiple swaps in parallel.

Would batching mean that multiple swaps would share the same rHash? The concern for me there would be that by combining payments, we increase the total payment size which could make it harder to find a single route that can support the entire amount.

[offerm]

@sangaman please consider parallel swap between different peers and parallel swaps for orders of a peer.
Also the use of the same rHash for all orders of the same peer.

This is somehow related to capacity checking,

Suggest you describe how you plan to handle this so we can discuss.

[sangaman]

I'm not quite sure. Do you happen to know if lnd would have any issues handling multiple payments that use the same preimage? If so, we might need to batch then to handle things like all-or-nothing orders. Otherwise, I'm thinking there's not much of a benefit from batching swaps at all and that this should not be a priority.

If you're not sure I can do some research.

[kilrau]

The status quo on "batching swaps": 2 things were supposed to be done

1. Execute swaps for matches with multiple orders in parallel: https://github.com/ExchangeUnion/xud/issues/654 - merged (https://github.com/ExchangeUnion/xud/pull/800)
2. Combining packets from xud, lnd, raiden for multiple swaps (multiple order matches) with the same peer (this issue)

Something for you? @erkarl

[erkarl]

@sangaman
Just to clarify...

Taker order is 15000 SAT for X exchange rate. There are maker orders of 5000 + 5000 + 5000 SAT with the same exchange rate AND by the same peer. Before the swap executes xud will detect that batching these 3 orders is an option. As a result there will only be 1 swap instead of 3, reducing the amount of packets from 57 to 19.

[sangaman]

I'm thinking about this and I think that's the right idea, but I'm still questioning whether this is a worthwhile effort. I'm thinking the complexity would be significant - it would change the flow for how swaps are handled and we'd have to deal with combining multiple orders in a single swap.

The benefits seem slim to me, these packets are small and they're already being sent in parallel. As for combining the swaps, that may actually be a negative. Larger swaps are more likely to fail due to no sufficient route existing (at least until AMP, although even with that we could succeed on a subset of the swaps if we don't combine them). There's also the reality that a larger swap is more vulnerable to the "free option" problem and one solution is actually to split orders down into multiple, smaller swaps.

[kilrau]

@sangaman
Just to clarify...

Taker order is 15000 SAT for X exchange rate. There are maker orders of 5000 + 5000 + 5000 SAT with the same exchange rate AND by the same peer. Before the swap executes xud will detect that batching these 3 orders is an option. As a result there will only be 1 swap instead of 3, reducing the amount of packets from 57 to 19.

Correct, apart from exchange rate of these 3 orders can be different.

[kilrau]

I'm thinking about this and I think that's the right idea, but I'm still questioning whether this is a worthwhile effort. I'm thinking the complexity would be significant - it would change the flow for how swaps are handled and we'd have to deal with combining multiple orders in a single swap.

The benefits seem slim to me, these packets are small and they're already being sent in parallel. As for combining the swaps, that may actually be a negative. Larger swaps are more likely to fail due to no sufficient route existing (at least until AMP, although even with that we could succeed on a subset of the swaps if we don't combine them). There's also the reality that a larger swap is more vulnerable to the "free option" problem and one solution is actually to split orders down into multiple, smaller swaps.

Very valid concerns. Your take? @erkarl @offerm @moshababo

[erkarl]

I'm thinking the complexity would be significant - it would change the flow for how swaps are handled and we'd have to deal with combining multiple orders in a single swap.

That was my rough conclusion when looking into the code as well.

The benefits seem slim to me, these packets are small and they're already being sent in parallel. As for combining the swaps, that may actually be a negative. Larger swaps are more likely to fail due to no sufficient route existing (at least until AMP, although even with that we could succeed on a subset of the swaps if we don't combine them).

Don't think the liquidity of the routes will be a problem as the early adopters/exchanges will have solid direct channels.

There's also the reality that a larger swap is more vulnerable to the "free option" problem and one solution is actually to split orders down into multiple, smaller swaps.

Good point. It's definitely something that could mitigate the issue.

@kilrau I'm going to remove the top priority label as we discuss this further (feel free to add it back if you think otherwise).

[kilrau]

I think we can postpone this until multipath payments on LN and Raiden are usable and stable. This could still take a while.