[bitcoin-dev] Fwd: (Semi)Traceless 2-party coinjoin off-chain protocol using schnorr signatures

[ZmnSCPxj]

Good morning CB,

I have been thinking about CoinSwap for a good while as well.

Here are some very unorganized thoughts.

It wold be nice to interoperate with JoinMarket, i.e. have a JoinMarket maker that also provides CoinSwap services using the same UTXOs.
However, this requires us to retain compatibility with the JoinMarket wallet structure, which is divided into mixdepths, with the rule that UTXOs in different mixdepths cannot be spent together in the same onchain UTXO (to move across mixdepths you have to do a send, and sending out is always done by a single CoinJoin round with multiple makers).

I am uncertain what is the best way to handle multitransaction when considering the mixdepth system.
My instinct is that if you are doing multitransaction (whether as taker or maker) then each transaction in the swap *has to* come from a different mixdepth.
The issue here is:

* If all the UTXOs in the multitransaction swap come from the same mixdepth, then a surveillor who is monitoring that mixdepth gets a good hint in solving the sparse subset sum problem.
* On the other hand, if all the UTXOs in the multitransaction swap come from different mixdepths, then a surveillor who has solved the sparse subset sum problem now has the hint that the different mixdepths are really owned by the same JoinMarket user.

I am uncertain which tradeoff is better here, though I am inclined to think the latter is better.


Attempting to completely detach a market-for-CoinSwap from JoinMarket seems to be impossible to my mind: the protocols are known, implementations open, and someone will inevitably write code for a single piece of software that can operate as both a JoinMarket maker *and* a maker for a market-for-CoinSwap (to increase their market, so to speak), so it might be better to just add CoinSwap to JoinMarket in the first place.


> A couple of thoughts on multi-transaction coinswaps:
>
> -   Users should never split up a single UTXO before doing a coinswap,
>     instead they should send the one UTXO to a coinswap address and get back
>     multiple UTXOs.
>
>     For example, this 1-to-3 TXO coinswap (The symbol ----> means bitcoin
>
>
> transaction).
>
> AliceA (10 BTC) ----> CoinSwap AddressA ----> BobA (10 BTC)
>
> BobB (3 BTC) ----> CoinSwap AddressB ----> AliceB (6 BTC)
>
>     BobC (2 BTC) ----> CoinSwap AddressC ----> AliceC (3 BTC)
>
>     BobD (5 BTC) ----> CoinSwap AddressD ----> AliceD (1 BTC)
>
>
> Note that the Bob-to-Alice set of transactions add up to 10 BTC, the
> entire CoinSwap is swapping the same amount.
>
> Or written another way:
>
> Alice TXO (10 BTC) ----> Coinswap Protocol ----> Alice TXO1 (6 BTC)
>
>                                                ----> Alice TXO2 (3 BTC)
>
>                                                ----> Alice TXO3 (1 BTC)
>

Assuming Alice is the taker, and Bob is the maker, then Alice might want a specific coin value (or set of such) that Bob does not have.
In that case, Bob will have to split a UTXO it owns.

We could constrain it so that Bob at least is not allowed to use the change from splitting for the same CoinSwap, e.g. if Bob has only 9 BTC and 1 BTC coins and Alice wants a 6 BTC / 3 BTC / 1 BTC split, then Bob cannot split its own 9 BTC coin then swap.
Or in terms of mixdepths, Bob can split within a mixdepth but each outgoing UTXO in the same swap should be from different mixdepths.



> -   It's helpful if any CoinSwap app is actually used for spending rather
>     than just mixing back to yourself. That will help avoid the problem of
>     users inadvertently co-spending all their coinswap outputs in the same
>     transaction.
>     An example of Alice paying for a VPN anonymously:
>
>     Alice TXO (10 BTC) ---> Coinswap Protocol ---> VPN Payment (0.1 BTC)
>
>                                                 ---> Change1 (6 BTC)
>
>                                                 ---> Change2 (3 BTC)
>
>                                                 ---> Change3 (0.9 BTC)
>
>
>
> In this case Alice will never accidentally merge all her TXOs together,
> because the VPN Payment TXO doesn't belong to her. Also this could
> improve privacy because unlike in normal transaction the VPN provider
> might not be able to figure out the lower bound of Alice's balance (10
> BTC in this case).

This is a good idea, akin to the rule in JoinMarket that all outgoing spends are done through a CoinJoin.

Of course, if a surveillor ***does*** solve the sparse subset sum, then the CoinSwap Protocol part looks exactly like a Bitcoin transaction, with a "main" paying output and a "change" output, and the same techniques that work with current Bitcoin txes work with "CoinSwap Protocol" virtual transactions.

It seems to me that, in a system of makers and takers, even if the maker is really just paying the taker(s) to do CoinSwaps to mix back to itself, it should still "require" some output amount that really goes to itself, so that the maker at least does not differentiate between the case that the taker is paying to itself vs the case that the taker is paying someone else via a CoinSwap.
That is, the protocol should still require that the taker specify *some* target desired amount, regardless of whether the taker wants to pay a specific value, or the taker wants to just mix its coins.


> -   Multi-transaction CoinSwaps aren't truly an example of a subset-sum
>     problem, but "sparse subset sum", a related and easier problem.
>
>     The way its normally formulated, subset sum is about finding a subset
>     that adds up to a target value. But in multi-transaction coinswap
>     there'd only be three or four CoinSwap outputs, so the problem is
>     finding just three or four integers in a big set that add up to the target.
>
>     You could think of it mathematically that the n-choose-k function is
>     near-polynomial when k is near 0 or near n, and the function is
>     exponential when k is near n/2.
>
>     A more promising way to build privacy is to create a situation where an
>     adversary would find a huge amount of false positives which are very
>     close the amount being sent. So even if the adversary has enough
>     computational power to iterate all the amounts it won't help them much
>     due to the huge number of false positives.

What are your thoughts on creating such possible situations?

An idea is to require standard swap amounts, i.e. similar to the standard 100mBTC mixing bin of Wasabi.

As well, one could randomly select some existing 1-input 1-output txes in the mempool and/or recent blocks, sum them, and swap for the same sum, to force at least one false positive, but the surveillor could protect against this by removing the earliest match (the one it saw in the mempool first, or onchain).

Regards,
ZmnSCPxj