Date: Wed, 29 Apr 2020 07:56:16 +0000
To: Chris Belcher <belcher@riseup.net>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <muQZ5QzVScvrjDkpZg1pWQMPFekgn_yqaro1i-JBZWCowA4HhybWFi3e5clygh5EIeLIa7jlykipA5nAxpiuLXK0-5SE3wEXXOTVwMlPAVU=@protonmail.com>
In-Reply-To: <0e1c0287-617c-976c-9fd4-16683881d5d5@riseup.net>
References: <CALmj_sWCA6S_4bnmLetvLuzNhv=PfQvLnX3zVEZwsRtgzA=yqw@mail.gmail.com>
 <CALmj_sVwLG82_pCEnc-mdT-Cf+cPitpL59AruBbvyYLjaYoZ2Q@mail.gmail.com>
 <mRCFEsXTvivO-I7sBdoTbqV0RsnX9vdGGORqzJBGYWXd1Xqis-oBNtEFaCEWIt3g9ARrvNeqH3l6sWSH4uQdcj5ps5WAmaEbEUvb9Znk9Rw=@protonmail.com>
 <CALmj_sUuw8JkodDemnq4qkapWD28vpojKD3bmkiVYm3Cp76+NQ@mail.gmail.com>
 <-_xRcjb8H_0Bck71k4VkeukEBgHT-03ikLTIdyTG2P0rt0T_mvN4b4FejmWobwnAUCGNaDpFQlPc3TMwlml1gjnZ1lwSumeEYQpXSyijND0=@protonmail.com>
 <0e1c0287-617c-976c-9fd4-16683881d5d5@riseup.net>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Subject: Re: [bitcoin-dev] Fwd: (Semi)Traceless 2-party coinjoin off-chain
	protocol using schnorr signatures
Precedence: list

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 mak=
er that also provides CoinSwap services using the same UTXOs.
However, this requires us to retain compatibility with the JoinMarket walle=
t structure, which is divided into mixdepths, with the rule that UTXOs in d=
ifferent mixdepths cannot be spent together in the same onchain UTXO (to mo=
ve across mixdepths you have to do a send, and sending out is always done b=
y a single CoinJoin round with multiple makers).

I am uncertain what is the best way to handle multitransaction when conside=
ring 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 mix=
depth.
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 sol=
ving the sparse subset sum problem.
* On the other hand, if all the UTXOs in the multitransaction swap come fro=
m different mixdepths, then a surveillor who has solved the sparse subset s=
um problem now has the hint that the different mixdepths are really owned b=
y 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 tha=
t can operate as both a JoinMarket maker *and* a maker for a market-for-Coi=
nSwap (to increase their market, so to speak), so it might be better to jus=
t 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 b=
ack
>     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 o=
f
>     users inadvertently co-spending all their coinswap outputs in the sam=
e
>     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 spend=
s 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 "m=
ain" paying output and a "change" output, and the same techniques that work=
 with current Bitcoin txes work with "CoinSwap Protocol" virtual transactio=
ns.

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 th=
at the maker at least does not differentiate between the case that the take=
r 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* ta=
rget desired amount, regardless of whether the taker wants to pay a specifi=
c 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 t=
arget.
>
>     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 muc=
h
>     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 1=
00mBTC mixing bin of Wasabi.

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

Regards,
ZmnSCPxj