Date: Thu, 30 Apr 2020 08:54:28 +0000
To: Chris Belcher <belcher@riseup.net>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <gAyc5MFCEkCjjdLSx_fKF-9MVnI4Zl6-BQ7Y-Q2_JNFYE2tQbCC1Js5YfE9RnPE_RPoVx57H0tWA-dpJ5SM7KP52DxTzHRdx6IF_pWjIh7A=@protonmail.com>
In-Reply-To: <ed482ed6-a79b-e20c-5356-8be4345333f5@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>
 <muQZ5QzVScvrjDkpZg1pWQMPFekgn_yqaro1i-JBZWCowA4HhybWFi3e5clygh5EIeLIa7jlykipA5nAxpiuLXK0-5SE3wEXXOTVwMlPAVU=@protonmail.com>
 <ed482ed6-a79b-e20c-5356-8be4345333f5@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,


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

Would the ZeroLink proposal of separating a receiving (pre-mix) wallet from=
 a sending (post-mix) wallet apply, thus having two implicit mixdepths (the=
 receiving mixdepth and the sending mixdepth)?
Or would imposing the rule "all sends must be via CoinSwap" be sufficient (=
and follow the ZeroLink rule in spirit)?

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

This "as long as the inputs that should be separate are not co-spent" is pr=
ecisely what mixdepths protect against, which is why I think *some* kind of=
 mixdepth facility will still matter in CoinSwap.

Still, you have convinced me that, for the purpose of multi-transaction Coi=
nSwap where you do not merge any of your coins, it is immaterial if the sub=
-transactions come from the same mixdepth or not.
And if you have to merge your coins (for instance, if you are a maker and y=
our customer wants to get a UTXO that is larger than any you have on hand, =
you have to merge your coins), you just have to ensure they are in the same=
 mixdepth.

Of course, you *could* be proposing some other construct --- perhaps you ha=
ve some relational entry which says "you cannot merge coin A and coin B" wh=
ich allows you to merge A C D or B C E, but not A B?
(I imagine this would make coin selection even harder, but I am not a mathe=
matician and there may be some trivial solution to this.)

Now --- if you have two coins that cannot be merged in the same onchain tx,=
 what happens when you swap them in a multi-tx CoinSwap with somebody else?
That somebody else does not know that information.
Instead, that somebody else must always assume that any coins it got from t=
he same CoinSwap operation must not be safely mergeable (though they can st=
ill be used in the same swap together).

Coins received via receive addresses would also not be mergeable with any o=
ther coins, except coins to the same address (because coins in the same add=
ress already leak that they are owned by the same owner).

>
> 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 s=
eems 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-C=
oinSwap (to increase their market, so to speak), so it might be better to j=
ust 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.

An unscrupulous possible maker might not value the privacy of its customers=
 (indeed makers are a privacy attack vector, which requires something like =
fidelity bonds like you suggested before to protect against), and takers mi=
ght not want to do possibly-computationally-expensive blockchain analysis t=
o evaluate whether a particular maker values privacy.
An unscrupulous maker might thus earn more than a more scrupulous maker can=
, at least during the transition from JoinMarket to SwapMarket, and get a g=
reater share of the future SwapMarket available liquidity due to their incr=
eased earnings during the transition.

Against this we should remember that software that does two things is four =
times as complicated as software that does one thing, so hopefully your pro=
jected transition from JoinMarket to SwapMarket will be fast enough that su=
ch a combined Join/SwapMarket maker software does not arise fast enough to =
matter.


> 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 wan=
t 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 ch=
ange 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 s=
plit its own 9 BTC coin then swap.
> > Or in terms of mixdepths, Bob can split within a mixdepth but each outg=
oing 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.

This leaks to Bob whether Alice is making a payment or not; it would be bet=
ter for the privacy of Alice for Alice to *always* mention *some* "payment =
amount", even if this is not actually a payment and Alice is just mixing fo=
r herself prior to storing in cold storage.
And if Alice wants to use a single swap to pay to multiple targets at once,=
 that implies Alice has to have the ability to indicate the outputs it want=
s to Bob, and it would imply as well that Alice has to obfuscate which of t=
hose outputs have amounts that actually *matter* (by always insisting on wh=
at the output amounts must be, rather than insisting on N output amounts an=
d letting Bob handle the rest).
(We *could* constrain it such that Alice can make only one payment per Coin=
Swap, so that Alice only gives one "target" amount and one "total" amount, =
but that implies even bigger blockspace utilization, sigh.)

Otherwise, Bob can get information:

* "Oh, Alice did not specify any of the outputs, just the total amount, all=
 of my old coins are owned by Alice now."
* "Oh, Alice specified an exact value for one of the outputs, that one is n=
o longer owned by Alice but the rest are owned by Alice."
* "Oh, Alice specified exact values for two of the outputs, those two are d=
efinitely no longer owned by Alice but the rest are owned by Alice."

The conclusion here is either Alice never specifies any of the outputs --- =
in which case Alice cannot use a CoinSwap to pay directly to somebody else =
--- or Alice specifies all of them.

Again, the maker might be an active surveillor, thus we should reduce infor=
mation leaks to the maker as much as we can.

>
> 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 C=
oinSwap Protocol part looks exactly like a Bitcoin transaction, with a "mai=
n" paying output and a "change" output, and the same techniques that work w=
ith current Bitcoin txes work with "CoinSwap Protocol" virtual transactions=
.
> > It seems to me that, in a system of makers and takers, even if the make=
r 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, s=
o 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 speci=
fic 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-s=
um
> > >     problem, but "sparse subset sum", a related and easier problem.
> > >     The way its normally formulated, subset sum is about finding a su=
bset
> > >     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 t=
he 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 wh=
ere an
> > >     adversary would find a huge amount of false positives which are v=
ery
> > >     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 standa=
rd 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, t=
o force at least one false positive, but the surveillor could protect again=
st 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.

Okay, from what little I understand it seems that "even if sparse subset su=
m is easier than subset sum, it is still hard, so it probably will not matt=
er in practice", would that be a fair takeaway?

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

I agree.

Regards,
ZmnSCPxj