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

[ZmnSCPxj]

Good morning CB,


> Chain analysis doesn't in fact know that 1-input-1-output transfers are
> self-transfers, this is merely a heuristic that can be flawed. For
> example I accept donations in bitcoin and a surprising number of them
> are 1-input-1-output or multi-input-1-output, presumably the donators
> did it for privacy reasons or cost reasons.

A heuristic need not be perfect to be effective, and I am quite sure that, outside of donation, most 1-output transfers will be self-transfers.

Indeed, the old cliche of donating tainted/stolen funds is most likely a cliche for a reason.
Perhaps you are a beneficiary of some movie hero who has stolen the money from a villain who acquired wealth by immoral means.

Unlike change heuristics, misleading the 1-output heuristic is difficult; whoever got control of the single output is either yourself, or somebody who swapped coins with you.


> Also I believe many people
> use 1-input-1-output transactions for funding Lightning channels.

Yes, Lightning helps privacy, that is correct.

However, do note that Lightning channels tend to be long-lived, meaning it will be a large number of blocks that such a TXO will be unspent.
Due to the timeout on CoinSwap, the fund needs to be claimed quickly, in much shorter time than a typical Lightning channel.
This can help narrow down payment heuristics.

>
> Although even so, your argument suggests that its better for at least
> some of the time for Alice and Bob to create 2-output transactions and
> mess with the change output detection heuristics to try to get chain
> analyzers to assign the wrong output as change.

Yes, I agree.

> If the receiving end doesn't have a suitable UTXO for a PayJoin then
> they won't get the CoinSwap deal. The liquidity market is a free market,
> takers are the maker's customers and they have a wide choice. In such a
> case the maker would have been outcompeted by other makers which do have
> extra UTXOs.

PayJoin might not buy you as much as you think.

So Alice has two coins it does not want to CoinJoin for unknown reasons:


    Salary as  ---> Alice
     teacher

    LiveJasmin ---> Alice
     payout

Alice swaps them to Bob, who PayJoins the incoming funds.
Since Bob has been operating for a long time, its coins have a varied and storied history.

    WannaCry  ----> Bob  ----+
                             |
                             |
    Salary as  ---> Alice ---+--> Bob
     teacher

    LiveJasmin ---> Alice ---+--> Bob
     payout                  |
                             |
    ex-JoinMarket -> Bob ----+
     maker

Alice does *not* want Bob to join those two Bob-owned coins, still, because chain analysis would not only implicate her in WannaCry, but also as a LiveJasmin model ***and*** (gasp!) a JoinMarket money launderer (I am being facetious here).

And since the swap has completed, Bob controls those coins.
If another taker comes along, offering a high fee for a big swap, and Bob *has to* merge those two coins (that ultimately got history from Alice) in order to cover what the taker is requesting (because the taker has to make a big single payout to some other party, so needs a single large UTXO, not two small ones), what do you think Bob will do?
In a free market where the takers have wide choice, do you think Bob will economically-rationally help protect the secret life of Alice when not doing so would let Bob earn more coins?

Now of course, it would seem very unlikely that Alice the teacher is the hacker behind WannaCry *and* a LiveJasmin model *and* a money launderer, so no problem, right?
It just makes surveillors looks like fools right?
Except that Bob could have skipped the PayJoin step and just merged those four coins in a single transaction later, and the conclusion of surveillors would still be the same, for much the same effect, at reduced blockspace (spend in a single transaction instead of 3).

So I think it is better if Bob actually avoids small merges of a two or three or four coins, and should do the occasional mass merge of large numbers of coins.
This leads to better misleading of surveillors, and is incentive compatible since it reduces blockspace usage for Bob to do the occasional mass merge rather than PayJoining at every swap.

> Your discussion with Alice having two UTXOs she doesn't want to co-spend
> is definitely interesting. Perhaps also another way to solve is for
> Alice to spend her UTXOs in 2-output transactions and mess with the
> change output detection heuristics, say CoinSwapping 0.5 BTC from one
> coin and 0.7 BTC from the other, with the total 1.2 BTC going to Carol.

That seems to be a good idea indeed, and significantly better than relying on PayJoin to obscure the history of coins.

Of course, doing change-output-heuristic-breaking means splitting up coins, increasing the number of UTXOs.
But that combines well with Bob the maker periodically merging many small coins.

> Of course if Alice specified an amount when she was actually
> self-mixing, it would be easy for her to come up with a random value
> that was close to some round number, either in BTC or another currency.

Yes, and I suggest this is always be done, as part of the protocol.


> Private key turnover is a great idea. It could also help with the
> earlier problem of 1-input-1-output transactions being markers, because
> when the coins in 2-of-2 multisigs are spent they may end up being spent
> in a wider variety of ways.

Indeed.
It gets a few features "for free", at the cost of greater complexity at the simple "I only want to swap once, then forget about the coins for a while" case.

* It gets PayJoin at the second transaction for free.
* It lets Bob the maker cut-through for a new taker.
* It reduces the cost on Bob to merge large numbers of coins at once.
* It lets Alice the taker cut-through for a new maker if she wants to do multi-round swaps (though note the objection "Value-based Directionality" in my writeup https://zmnscpxj.github.io/bitcoin/multiswap.html ; though counternote that if CoinSwaps are as hard to identify as my naive understanding of your math suggests, this should be a relatively minimal problem).

>
> > > > Okay, from what little I understand it seems that "even if sparse subset sum is easier than subset sum, it is still hard, so it probably will not matter in practice", would that be a fair takeaway?
> > >
> > > Not exactly. Here's another summary:
> > > Suppose Alice has V bitcoins and mixes them with multi-transaction
> > > CoinSwap, she receives transactions with amounts (w_0, w_1, w_2....)
> > > which add up to V.
> > > Privacy relying on the (sparse) subset sum problem works by making it
> > > computationally infeasible for an adversary to search the entire
> > > blockchain for sets of transactions (w_0, w_1, w_2....) which add up to
> > > V. I believe aiming for this kind of privacy isn't practical due to
> > > block space considerations and others.
> > > Privacy relying on false positives does not make any search
> > > computationally infeasible, it works by having a large number of other
> > > sets of transactions (w_0, w_1, w_2....) which add up to V just by
> > > chance. Then the transactions received by Alice's will have a big crowd
> > > to hide in. I believe this is practical because the numbers are
> > > proportional to the n-choose-k function which can still be very large.
> >
> > Hmm.
> > So let us return to our example of Alice who owns a 1 BTC coin and a 1 BTC coin.
> > Now suppose we find, by false-positive-statistics, that 2 BTC subset sums are rare but, say, 1.5 BTC subset sums are significantly more common.
> > So what Alice should do, if it wants to send 1.2 BTC to Carol via a CoinSwap with maker Bob, would be to split one of her 1 BTC coins to a 0.5 BTC and 0.5 BTC coin.
> > Then it takes the remaining 1 BTC coin and one of the 0.5 BTC and offers them in a CoinSwap to maker Bob, specifying a payment amount of 1.2 BTC.
> > It seems to me, however, that this is not much different from just specifying a set of standardized swap amounts.
> > The initial standards can be derived from false-positive-statistics, but once SwapMarket starts to become popular, then the actual statistics of the chain becomes skewed towards those standard swap amounts.
> > This makes it even wiser to also use those standard swap amounts, because of the larger anonymity sets.
>
> It's very unlikely for the 2 BTC subset sum to be uncommon but 1.5 BTC
> to be common, because they are very close in value, and these functions
> seem to end up being smooth and slowly-varying, at least in my brief
> tests. It might be a concern when comparing 2 BTC to 20 BTC or 200 BTC.

If it is as smooth and naturally-occurring as you suggest, then it seems to me as well that the distribution of CoinSwap values will be just as smooth and naturally-occurring, so my naive understanding is still "even if sparse subset sum is easier than subset sum, it is still hard, so it probably will not matter in practice".

People will mix due to receiving some amount.
That amount will be sampled from some naturally-occurring distribution.
Thus, CoinSwap values will be sampled from the same naturally-occurring distribution.

People will mix due to having to send some amount they do not want to be tracked to them.
That amount will be sampled from some naturally-occurring distribution.
Thus, CoinSwap values will be sampled from the same naturally-occurring distribution.

....I think?  Maybe?

Regards,
ZmnSCPxj