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

[Chris Belcher <belcher@riseup.net>]

Hello ZmnSCPxj,


On 29/04/2020 08:56, ZmnSCPxj wrote:
> It wold be nice to interoperate with JoinMarket, i.e. have a JoinMarket maker that also provides CoinSwap services using the same UTXOs.

A great benefit of a CoinSwap system is that the transactions are
steganographic. If equal-output-coinjoins were involved that benefit
would be lost. So it would be better if it didn't happen.

> 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.

JoinMarket has many mixdepths (5 by default) because it's
equal-output-coinjoins easily leak change addresses. CoinSwap
transactions don't have this flaw because they're steganographic. Such a
system could also be coded to intentionally break the weaker change
output heuristics
(https://en.bitcoin.it/wiki/Privacy#Change_address_detection).

Equal-output-coinjoins and JoinMarket also have a version of the
common-input-ownership-heuristic (CIOH), because its often possible to
separate the inputs into sets of their owners of a equal-output-coinjoin
using the input amounts. CoinSwap can be combined with something like
PayJoin or CoinJoinXT, which would genuinely break the CIOH, so such a
system wouldn't have this flaw either.

For those reasons I've been thinking a CoinSwap system wouldn't need as
many mixdepths, maybe it could use two or even just one.

If so, then it follows that multi-transaction CoinSwaps can be done by
having UTXOs come from the same mixdepth, as long as the inputs that
should be separate are not co-spent in the same transaction.

Remember that a passive surveillor of the blockchain doesn't see
mixdepths at all, they see addresses and transactions, and must use
heuristics to try to cluster them together. We can break these heuristics.


> 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.

Someone who has the ability to write such code should also have the
awareness to realize that mixing equal-output-coinjoins with coinswaps
damages the privacy because it breaks the steganography of coinswaps.

Also, because CoinSwap is better than equal-output CoinJoin in almost
every way, we can expect users (who are takers) to stop using JoinMarket
and switch over to CoinSwap if the software becomes mature. So such a
JoinMarket maker won't get many customers, and so there wouldn't be much
point writing such maker code.

But for sure it would be good to reuse code in any eventual
implementation. Indeed Waxwing's implementation did:
https://github.com/AdamISZ/CoinSwapCS

> 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.

A good way to do it could be for Alice to tell Bob that she wants 10 BTC
and let Bob figure out on his own how to get that amount, based on the
amounts he already has. If Alice is making a payment she can provide
that amount too, but all the other output amounts can be up to Bob.

Bob would often still have to split a UTXO he owns, but see below about
breaking change address heuristics.

> 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.

If Bob needs to split a UTXO he'd do that with a change output. And
because we understand change detection heuristics we can intentionally
break them, for example if Bob's UTXO is on a p2sh-p2wpkh address and
the CoinSwap address is of that type too (because ECDSA-2P is being
used) then Bob could make his change output p2wpkh or p2pkh. Then anyone
using the script-type-heuristic would think that the CoinSwap address is
actually change and still belongs to Bob, and that the real change
address is actually the payment or CoinSwap address. i.e. the adversary
would assume that wallet software only uses one script type, in this
case it assumes that Bob's wallet is exclusively p2sh-p2wpkh.

> 
>> -   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).

I think we can get the false positive count up because the n-choose-k
function still gets quite large as k increases.

We can make a simplified reasonable assumption that outputs on the
blockchain follow a lognormal distribution. An adversary trying to unmix
a 3-transaction CoinSwap would have to find the sum of every
3-combination of the relevant outputs. For our case, the sum of three
lognormal distributions is another lognormal distribution with different
parameters, it's corresponding frequency distribution would get scaled
by n-choose-3. This frequency distribution is what the adversary would
find when searching, and that distribution would be quite tall because
of the scaling by n-choose-k. Suppose our CoinSwap is for 4 BTC then the
adversary would look at their frequency distribution at 4 BTC and find a
pretty big number, i.e. many other combinations of 3 outputs would add
up to 4 BTC just by chance. That is the false positive rate, and is our
anonymity set with respect to this attack.

To work this out precisely we'd need to study the distribution of output
values on the blockchain today, and see how it behaves when summed
together. But the lognormal distribution assumption is probably not too
far from the truth, as it appears all the time in economics and finance,
and there is a clear justification for why. And the scaling by
n-choose-k would still hold.

Along with that, some output amounts have very few significant figures
(e.g. 1 BTC, 0.1 BTC, 0.01 BTC), presumably because the user types just
one number on their keyboard when creating a transaction. We can use
that fact to add a bit of privacy by occasionally making one of our
outputs also be rounded like that.