Date: Mon, 04 May 2020 08:28:41 +0000
To: Chris Belcher <belcher@riseup.net>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <fCI9QUCx0irTdZQdFEooMeQK3lx0PO6S6JDhu8hIi6tCRXXqAKfHlVtlY5K6jS9KdYY_3IWCE5MiAhjwmdbm0vqzrmt1HAfu2qZVh0dCXOw=@protonmail.com>
In-Reply-To: <5e5ed1c3-085e-2137-5368-4e605e79b5bf@riseup.net>
References: <CALmj_sWCA6S_4bnmLetvLuzNhv=PfQvLnX3zVEZwsRtgzA=yqw@mail.gmail.com>
 <-_xRcjb8H_0Bck71k4VkeukEBgHT-03ikLTIdyTG2P0rt0T_mvN4b4FejmWobwnAUCGNaDpFQlPc3TMwlml1gjnZ1lwSumeEYQpXSyijND0=@protonmail.com>
 <0e1c0287-617c-976c-9fd4-16683881d5d5@riseup.net>
 <muQZ5QzVScvrjDkpZg1pWQMPFekgn_yqaro1i-JBZWCowA4HhybWFi3e5clygh5EIeLIa7jlykipA5nAxpiuLXK0-5SE3wEXXOTVwMlPAVU=@protonmail.com>
 <ed482ed6-a79b-e20c-5356-8be4345333f5@riseup.net>
 <gAyc5MFCEkCjjdLSx_fKF-9MVnI4Zl6-BQ7Y-Q2_JNFYE2tQbCC1Js5YfE9RnPE_RPoVx57H0tWA-dpJ5SM7KP52DxTzHRdx6IF_pWjIh7A=@protonmail.com>
 <25848910-24ca-8b49-ad20-39afae2a856b@riseup.net>
 <MCKbq9k8bMWTqHyAAjWGhqNdwTZ1ELa5gmsnNQ3HgrtRu1ATsskYfyyT__X_L3c8AXHFI0bJfiPnGf_Y76I7P7BubGWKsFCJiejB6mAfwUQ=@protonmail.com>
 <5e5ed1c3-085e-2137-5368-4e605e79b5bf@riseup.net>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Fwd: (Semi)Traceless 2-party coinjoin off-chain
	protocol using schnorr signatures
Precedence: list

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 cl=
iche for a reason.
Perhaps you are a beneficiary of some movie hero who has stolen the money f=
rom a villain who acquired wealth by immoral means.

Unlike change heuristics, misleading the 1-output heuristic is difficult; w=
hoever 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 mu=
ch 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 s=
toried 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 Liv=
eJasmin model ***and*** (gasp!) a JoinMarket money launderer (I am being fa=
cetious 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 o=
rder 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 t=
wo small ones), what do you think Bob will do?
In a free market where the takers have wide choice, do you think Bob will e=
conomically-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 ha=
cker behind WannaCry *and* a LiveJasmin model *and* a money launderer, so n=
o problem, right?
It just makes surveillors looks like fools right?
Except that Bob could have skipped the PayJoin step and just merged those f=
our coins in a single transaction later, and the conclusion of surveillors =
would still be the same, for much the same effect, at reduced blockspace (s=
pend in a single transaction instead of 3).

So I think it is better if Bob actually avoids small merges of a two or thr=
ee 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 c=
oins.

> 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 mu=
lti-round swaps (though note the objection "Value-based Directionality" in =
my writeup https://zmnscpxj.github.io/bitcoin/multiswap.html ; though count=
ernote 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 s=
ubset 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 othe=
r
> > > 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 cro=
wd
> > > 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 su=
ms 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 Coi=
nSwap 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 offer=
s 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 spec=
ifying a set of standardized swap amounts.
> > The initial standards can be derived from false-positive-statistics, bu=
t once SwapMarket starts to become popular, then the actual statistics of t=
he chain becomes skewed towards those standard swap amounts.
> > This makes it even wiser to also use those standard swap amounts, becau=
se 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 spars=
e subset sum is easier than subset sum, it is still hard, so it probably wi=
ll 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 dis=
tribution.

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

....I think?  Maybe?

Regards,
ZmnSCPxj