[tracking] Implement the Split and Merge swap.

[mojoX911]

The concept of split/merge swap is described here. https://gist.github.com/chris-belcher/9144bd57a91c194e332fb5ca371d0964#combining-multi-transaction-with-routing

Task

• Add manual utxo selection for swaps.

[danvergara]

#425

@mojoX911 mind if I take this?

[danvergara]

I have a question about the manual utxo selection. How manual the process has to be? I mean, was thinking of providing the user the ability to list available UTXOs and pick them up and then, start coinswap off that. Other option I'm considering is the ability to provide a flag to branch off the swaps if need.

Do you have any expected UX/workflow in mind?

[mojoX911]

Good question. In my head it's a combination of both.

Example workflow:

• User sees a list of all the utxos, with a unique id for each, with which they can select the input utxos.
• A split-number, which distributes the inputs into that many output utxos, with random amount distributions.
• A merge flag, which takes those many utxos and merge them into one output utxo.

Note the the split/merge has to be distributed across the hops. So it's not just only the create_funding_tx for taker that needs to change. The intermediate makes should also be notified accordingly to create their funding transaction as per the split/merge request.

It will be more cost efficient if all the intermediate makers just create singleinput-singleoutput funding txs. And only the last maker of the hop create their funding tx as per the split/merge request.

[danvergara]

Thanks for the quick response and the clarification but I have a couple of questions and comments. You can correct me if I got it wrong.

• User sees a list of all the utxos, with a unique id for each, with which they can select the input utxos.

Yeah, here we're pretty much aligned. I envision an interactive workflow allowing the user to choose UTXOS from a list of Outpoints and their respective values.

$ taker coinswap --amount  1500000000 --makers 3 --interactive

List of UTXOs:

[ ] 635ddfa1456a006ab66f711f7c002e31b262a77283685b589d3e20d4d438647a:3 - 600000000
[x] de55e0488bf765b41570c304a20ac6700a59f99b699f3ffcac6df130024953ad:5 - 800000000
[ ] 7f65f53b0b24c73bbd8678b6867805a7021b3ef38074189beea527d051373531:8 - 100000000
...

• A split-number, which distributes the inputs into that many output utxos, with random amount distributions.

I think we're already here, I think this is what create_funding_txes_random_amounts does. It splits random amount distributions into different outputs for different founding transactions for different addresses belonging to the same maker.

         Alice
(6 BTC) (8 BTC) (1 BTC)
   |       |       |
   |       |       |
   v       v       v
          Bob
(5 BTC) (5 BTC) (5 BTC)
   |       |       |
   |       |       |
   v       v       v
        Charlie
(9 BTC) (5 BTC) (1 BTC)
   |       |       |
   |       |       |
   v       v       v
        Dennis
(7 BTC) (4 BTC) (4 BTC)
   |       |       |
   |       |       |
   v       v       v
         Alice

From my perspective, the branching strategy is more meaningful when the taker only has or chooses a single UTXO and it sends it over to the first maker, hopping they branch off the same amount with multiple UTXOs to avoid amount correlation attacks.

                     Alice
                       (15 BTC)
                          |
                          |
                          v
                         Bob
                        /   \
                       /     \
           <-----------       ----------->
           |                             |
(2 BTC) (2 BTC) (2 BTC)        (3 BTC) (3 BTC) (3 BTC)
    |       |       |             |       |       |
    |       |       |             |       |       |
    v       v       v             v       v       v
        Charlie                       Dennis
(1 BTC) (2 BTC) (3 BTC)       (5 BTC) (3 BTC) (1 BTC)
    |       |       |             |       |       |
    |       |       |             |       |       |
    v       v       v             v       v       v
         Edward                          Fred
 (4 BTC) (1 BTC) (1 BTC)       (4 BTC) (2 BTC) (3 BTC)
    |       |       |             |       |       |
    |       |       |             |       |       |
    v       v       v             v       v       v
          Alice                         Alice

From my opinion, the split-number flag should be used to define how many times the coinswap will branch off. 2 times in the diagram above. So, this indicative is for the first maker along the coinswap. To put it differently, it would mean concurrent paths of makers.

• A merge flag, which takes those many utxos and merge them into one output utxo.

And this is pretty much for the last makers on the coinswap, to gather their UTXOs and send them as inputs to a single output to an address that the taker controls.

          Alice                         Alice
         (9 BTC)                       (6 BTC)
            |                             |
            |                             |
            v                             v
           Bob                         Charlie
 (4 BTC) (3 BTC) (2 BTC)       (1 BTC) (2 BTC) (3 BTC)
    |       |       |             |       |       |
    |       |       |             |       |       |
     \       \       \           /       /       /
      \       \       \         /       /       /
       \       \       \       /       /       /
        >------->-------\     /-------<-------<
                         \   /
                         Alice
                        (15 BTC)

Note the the split/merge has to be distributed across the hops. So it's not just only the create_funding_tx for taker that needs to change. The intermediate makes should also be notified accordingly to create their funding transaction as per the split/merge request.

I don't agree with this statement. Correct me if I'm wrong, but from my perspective, the merge indication is only for the last makers in the route and the split/branch flag is for the first maker and the branches mean concurrent path of takers. Or am I getting it wrong?

It will be more cost efficient if all the intermediate makers just create singleinput-singleoutput funding txs. And only the last maker of the hop create their funding tx as per the split/merge request.

When it comes to this one, isn't this susceptible to amount correlation attacks? I mean, singleinputs-singleoutputs txs wouldn't mean sending the same amount every hop making it easier for chain analysts to trace back the original transaction? Well, this approach could trick chain analysts into thinking that the last hop was the one before the very last one, but still.

Let me know your thoughts and again thanks for the quick and detailed response @mojoX911

[mojoX911]

Yeah, here we're pretty much aligned. I envision an interactive workflow allowing the user to choose UTXOS from a list of Outpoints and their respective values.

This is even better than my idea of choosing by index number. Yes, an interactive flow will be perfect.

I think we're already here, I think this is what create_funding_txes_random_amounts does. It splits random amount distributions into different outputs for different founding transactions for different addresses belonging to the same maker.

Yes, you are correct. This is already possible.

From my perspective, the branching strategy is more meaningful when the taker only has or chooses a single UTXO

Yes, but we can generalize the logic also. Why cannot I branch off 5 utxos into 10? 1-to-many branching is then just the special case of selecting only one utxo in input.

From my opinion, the split-number flag should be used to define how many times the coinswap will branch off. 2 times in the diagram above. So, this indicative is for the first maker along the coinswap. To put it differently, it would mean concurrent paths of makers.

yes, could be, my concern is it should be intuitive for the users to choose this properly to determine the "shape of the swap". If you take in the above diagram, split number 2 is giving 6 outputs. So no. of output = split_number * maker parallel paths. I think its simpler to make the split_number = Total output chunks a swap client will receive at the end. So the above diagram will be a split_number = 6. This is something we need to decide. I am open to other opinions also.

And this is pretty much for the last makers on the coinswap, to gather their UTXOs and send them as inputs to a single output to an address that the taker controls.

Yes. Thats it.

I don't agree with this statement. Correct me if I'm wrong, but from my perspective, the merge indication is only for the last makers in the route and the split/branch flag is for the first maker and the branches mean concurrent path of takers. Or am I getting it wrong?

You are right. I framed it wrong. This applies if we control the internal hops' concurrent paths too. All this info will have to be conveyed to the makers.

When it comes to this one, isn't this susceptible to amount correlation attacks?

Yes, and we are in a constant tradeoff between amount-correlation and cost-of-swap. Doing this kind of split paths increases the swap cost in multiple of split_number.

We can put this as an extra flag for the user to choose. Privacy Mode and Efficiency Mode. In privacy mode user defines how many internal hop splits, and in efficiency mode its the single utxo variant.

As mentioned in #427 there will be randomization in the maker fees and tx fees. That will create some randomness. But still >1 utxos will always be better in terms of privacy.

Also note, there's two ways of doing splits. Multiple utxos in the same tx, or multiple independent txs. 2nd option has more resistance against amount-correlations and also its more costly

We need to hit a balance here, max correlation resistance within reasonable costs.

[danvergara]

Split and Merge Proposal

With all the information gathered, I think it's time for a proposal, before any change in the code.

Scenario 1 - simplest use case

This is the simplest scenario, from the user perspective where nothing changes.

$ taker coinswap --amount 1500000000 --makers 2

        Alice
(6 BTC) (8 BTC) (1 BTC)
   |       |       |
   |       |       |
   v       v       v
          Bob
(5 BTC) (5 BTC) (5 BTC)
   |       |       |
   |       |       |
   v       v       v
        Charlie
(9 BTC) (5 BTC) (1 BTC)
   |       |       |
   |       |       |
   v       v       v
         Alice

This where we are today.

Scenario 2 - Efficiency Mode

In this scenario, the --efficiency-mode is added to make singleinput-singleoutput funding txs. The default behavior is the Privacy Mode.

$ taker coinswap --amount 1500000000 --makers 2 --efficiency-mode

        Alice
(6 BTC) (8 BTC) (1 BTC)
    |      |      |
    |      |      |
     \     |     /
        v  v   v
          Bob
         15 BTC
           | 
           |
           v
        Charlie
        15 BTC
           |
           |
           v 
         Alice

Scenario 3 - Branching

In this scenario is where the branching comes in. --branches flag is added to define how many times the coinswap will branch off after the first hop. More granular control will be defined later on the proposal. In this context, the --makers flag means the number the depth of the coinswap and the --branches the width.

$ taker coinswap --amount 1500000000 --makers 3 --branches 2

                        Alice
                       (15 BTC)
                          |
                          |
                          v
                         Bob
                        /   \
                       /     \
           <-----------       ----------->
           |                             |
(2 BTC) (2 BTC) (2 BTC)        (3 BTC) (3 BTC) (3 BTC)
    |       |       |             |       |       |
    |       |       |             |       |       |
    v       v       v             v       v       v
        Charlie                       Dennis
(1 BTC) (2 BTC) (3 BTC)       (5 BTC) (3 BTC) (1 BTC)
    |       |       |             |       |       |
    |       |       |             |       |       |
    v       v       v             v       v       v
         Edward                          Fred
 (4 BTC) (1 BTC) (1 BTC)       (4 BTC) (2 BTC) (3 BTC)
    |       |       |             |       |       |
    |       |       |             |       |       |
    v       v       v             v       v       v
          Alice                         Alice

Scenario 4 - Merging

$ taker coinswap --amount 1500000000 --makers 3 --merge

In this scenario, the --merge flag is added to make sure the taker receive single input transactions at the end of the coinswap. More granular control will be added in the next scenario.

          Alice                         Alice
         (9 BTC)                       (6 BTC)
            |                             |
            |                             |
            v                             v
           Bob                         Charlie
 (4 BTC) (3 BTC) (2 BTC)       (1 BTC) (2 BTC) (3 BTC)
    |       |       |             |       |       |
    |       |       |             |       |       |
     \       \       \           /       /       /
      \       \       \         /       /       /
       \       \       \       /       /       /
        >------->-------\     /-------<-------<
                         \   /
                         Alice
                        (15 BTC)

Scenario 5 - Branching and Merging combined

In this scenario both branching and merging are used combined, this means, the coinswap will branch off x times, and at the end the makers will send singleoutput transactions back to the taker.

$ taker coinswap --amount 1500000000 --makers 3 --branches 2 --merge

                      Alice
                       (15 BTC)
                          |
                          |
                          v
                         Bob
                        /   \
                       /     \
           <-----------       ----------->
           |                             |
(2 BTC) (2 BTC) (2 BTC)        (3 BTC) (3 BTC) (3 BTC)
    |       |       |             |       |       |
    |       |       |             |       |       |
    v       v       v             v       v       v
        Charlie                       Dennis
(1 BTC) (2 BTC) (3 BTC)       (5 BTC) (3 BTC) (1 BTC)
    |       |       |             |       |       |
    |       |       |             |       |       |
    v       v       v             v       v       v
         Edward                          Fred
 (4 BTC) (3 BTC) (2 BTC)       (1 BTC) (2 BTC) (3 BTC)
    |       |       |             |       |       |
    |       |       |             |       |       |
     \       \       \           /       /       /
      \       \       \         /       /       /
       \       \       \       /       /       /
        >------->-------\     /-------<-------<
                         \   /
                         Alice
                        (15 BTC)

Scenario 6 - Interactive

In this case, the --interactive flag is added and an interactive menu is displayed to the user so they can pick the desired UTXOs to be swapped. After picking up the UTXOs (and some validations) the normal workflow will continue.

$ taker coinswap --amount  1500000000 --makers 3 --branches 2 --interactive

List of UTXOs:

[x] 635ddfa1456a006ab66f711f7c002e31b262a77283685b589d3e20d4d438647a:3 - 600000000
[x] de55e0488bf765b41570c304a20ac6700a59f99b699f3ffcac6df130024953ad:5 - 800000000
[x] 7f65f53b0b24c73bbd8678b6867805a7021b3ef38074189beea527d051373531:8 - 100000000
...

                        Alice
                (6 BTC)(8 BTC)(1 BTC)
                    |     |     |
                    |     |     |
                    v     v     v
                         Bob
                        /   \
                       /     \
           <-----------       ----------->
           |                             |
(2 BTC) (2 BTC) (2 BTC)        (3 BTC) (3 BTC) (3 BTC)
    |       |       |             |       |       |
    |       |       |             |       |       |
    v       v       v             v       v       v
        Charlie                       Dennis
(1 BTC) (2 BTC) (3 BTC)       (5 BTC) (3 BTC) (1 BTC)
    |       |       |             |       |       |
    |       |       |             |       |       |
    v       v       v             v       v       v
         Edward                          Fred
 (4 BTC) (1 BTC) (1 BTC)       (4 BTC) (2 BTC) (3 BTC)
    |       |       |             |       |       |
    |       |       |             |       |       |
    v       v       v             v       v       v
          Alice                         Alice