Date: Fri, 01 May 2020 07:17:19 +0000
To: Chris Belcher <belcher@riseup.net>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <MCKbq9k8bMWTqHyAAjWGhqNdwTZ1ELa5gmsnNQ3HgrtRu1ATsskYfyyT__X_L3c8AXHFI0bJfiPnGf_Y76I7P7BubGWKsFCJiejB6mAfwUQ=@protonmail.com>
In-Reply-To: <25848910-24ca-8b49-ad20-39afae2a856b@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>
 <gAyc5MFCEkCjjdLSx_fKF-9MVnI4Zl6-BQ7Y-Q2_JNFYE2tQbCC1Js5YfE9RnPE_RPoVx57H0tWA-dpJ5SM7KP52DxTzHRdx6IF_pWjIh7A=@protonmail.com>
 <25848910-24ca-8b49-ad20-39afae2a856b@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,

> > This "as long as the inputs that should be separate are not co-spent" i=
s precisely 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=
 CoinSwap 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 a=
nd your customer wants to get a UTXO that is larger than any you have on ha=
nd, 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 =
have some relational entry which says "you cannot merge coin A and coin B" =
which 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 m=
athematician 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 e=
lse?
> > That somebody else does not know that information.
> > Instead, that somebody else must always assume that any coins it got fr=
om the same CoinSwap operation must not be safely mergeable (though they ca=
n still be used in the same swap together).
> > Coins received via receive addresses would also not be mergeable with a=
ny other coins, except coins to the same address (because coins in the same=
 address already leak that they are owned by the same owner).
>
> Yes I guess you're right. This part about mixdepths requires further
> thought.
>
> CoinSwap can be combined with some kind of CoinJoin (most likely
> something similar to PayJoin or CoinJoinXT). That should help with the
> reasoning about co-spending inputs and mixdepths, because other inputs
> that are not owned by the taker will often be co-spent anyway.
>
> Regarding coins which mustn't be co-spent being coinswapped to somebody
> else, ideally that coinswap maker will receive coins from unrelated
> takers too, so will merge their coins along with those as well. Also the
> fact that a coinswap happened means there are two transactions between
> the taker's-inputs-which-mustnt-be-merged and them actually being merged.

One of those transactions (the second one) will be a 1-input 1-output tx (i=
t moves the coin from bilateral control to unilateral control of Bob), whic=
h chain analysis already knows to be a self-transfer.
The first transaction will also usually be a 1-input 1-output tx as well (i=
t moves the coin from unilateral of Alice to bilateral control) if you did =
not do any splitting or merging before providing the coin into the swap (fo=
r example if this comes from the taker, and the taker knows all the coins i=
t wants to swap cannot be safely merged together).

If chain analysis keeps the heuristic "1-input 1-output is a self-payment b=
ecause srsly who has an exact amount for a payment Bitcoin is volatile lol"=
, then the resulting coins still are not safe to merge, because chain analy=
sis will "pass through" the swap operation and if the two coins are later m=
erged then they still end up *correctly* concluding the original coins were=
 owned by the same owner.

Using a PayJoin construction for the second tx would help, but if the recei=
ving end does not have a spare UTXO it can merge with (e.g. all its liquidi=
ty got tied up in the swap) then there might not be an opportunity to PayJo=
in.

There is also little that can be done about the first transaction, in case =
it ends up being a 1-input 1-output.

Suppose Alice the taker has a 1 BTC output and a 1 BTC output *and no other=
 coins*, both of which it cannot safely merge, and it has to pay 1.2 BTC to=
 Carol.
Alice then has to CoinSwap them to Bob the maker, requesting a 1.2 BTC outp=
ut going to Carol and the rest in whatever loose change Bob has.
Alice then has to use two 1-input 1-output txes for each of its 1 BTC outpu=
ts (because it cannot merge them together) to put them into bilateral contr=
ol.
Then Bob claims them from bilateral control with 1-input 1-output txes as w=
ell (it cannot merge them together, because that might break Alice privacy,=
 and Bob might not have any other spare coins it can merge with the incomin=
g funds).

Now, even if Bob PayJoins the second tx for both 1 BTC outputs, it still ca=
nnot merge the resulting joined coins together, because the "spent-together=
" analysis would still tie those coins as being owned by the same owner, it=
 is simply that the surveillor will think the owner owns more coins than it=
 actually does, but the two 1 BTC TXOs that Alice used to own are still ana=
lyzed as being owned by the same owner if they are ever merged.

What Alice could do, to "merge" its 1BTC coins together, would be to swap o=
nly one of the 1BTC coins first, for a single 1BTC coin as well.
Then presumably the incoming 1BTC coin has no linkage with the coin Alice s=
wapped out (Alice hopes), then Alice could spend that new 1BTC coin with th=
e old one it could not merge with the coin it swapped out.
(Actually Alice does not need to do that as it is the customer after all, b=
ut maybe Bob the maker has to do that sometimes, in case it finds there are=
 too many cannot-spend-together constraints in its pool of UTXOs and it is =
getting harder to select coins --- but if so, who does Bob the maker swap *=
with*?
If Bob can encounter that problem, then maybe other makers will also have t=
hat problem as well!)

(the above can be done by PayJoining with the unswapped coin on either the =
first or second transaction in the swap as well; the idea is more general.)

>
> Great point on the receive addresses coins. Another use case of
> mixdepths is to stop incoming payments from two different sources being
> linked together.

We could eliminate mixdepths entirely and just use "cannot merge with X" co=
nstraints.

When the wallet sees an incoming payment, it just marks it as "cannot merge=
 with" all other coins it owns, unless they have the same address.
This prevents any linkage at all and is maximally private.

On a CoinSwap, the incoming coins are marked as "cannot merge with" to each=
 other in the same CoinSwap operation, but not with any other coins it owns=
.

Maybe?

It might be easier for the user to understand as well, and reduces scope fo=
r mistakes in using mixdepths.
For example, I might have a sensitive source of funds (e.g. from all the ra=
nsomware I have been writing) and put them in one mixdepth, then after a fe=
w months I forgot which mixdepth I put those in and accidentally use it for=
 my on-the-books salary.


> > > > 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 th=
e change from splitting for the same CoinSwap, e.g. if Bob has only 9 BTC a=
nd 1 BTC coins and Alice wants a 6 BTC / 3 BTC / 1 BTC split, then Bob cann=
ot 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 th=
e
> > > 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=
 better 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 o=
nce, that implies Alice has to have the ability to indicate the outputs it =
wants to Bob, and it would imply as well that Alice has to obfuscate which =
of those outputs have amounts that actually matter (by always insisting on =
what the output amounts must be, rather than insisting on N output amounts =
and letting Bob handle the rest).
> > (We could constrain it such that Alice can make only one payment per Co=
inSwap, 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 amoun=
t, all of my old coins are owned by Alice now."
> > -   "Oh, Alice specified an exact value for one of the outputs, that on=
e is no longer owned by Alice but the rest are owned by Alice."
> > -   "Oh, Alice specified exact values for two of the outputs, those two=
 are definitely 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 e=
lse --- or Alice specifies all of them.
> > Again, the maker might be an active surveillor, thus we should reduce i=
nformation leaks to the maker as much as we can.
>
> Yep great point.
>
> A benefit of Alice not specifying any amounts is that Bob is able to
> improve privacy and reduce costs by creating fewer change outputs. A
> downside is that this leaks Alice's intentions (self-mix vs payment) to B=
ob.
>
> A solution could be to add randomness. Have Alice randomly specify
> payment amounts with some probability even if she is only self-mixing.
>
> Although this doesn't solve everything, because Alice not specifying any
> amounts implies self-mixing. But at least specifying some amounts
> doesn't imply a payment.

I think that maybe it would be a better policy for Alice to always just giv=
e a specified payment amount at all times.
Of course, a sufficiently motivated Bob could always just do statistical an=
alysis on the payment amount (e.g. if it is not equivalent to some round nu=
mber of United States Green Historical Commemoration Papers, it is unlikely=
 to be a payment but instead a random amount that Alice had to provide on a=
 self-payment).
So .....


Anyway, slightly unrelated, maybe we can simply have Alice specify a single=
 payment amount always, as an unremovable part of the protocol.

I proposed "private key turnover" here: https://github.com/AdamISZ/CoinSwap=
CS/issues/53
Basically, after exchanging the swap secret, it is now safe to give your sh=
are of bilateral control to your swap partner, so you can just turn over th=
at private key to the swap partner.
For clarity:

* Alice owns a 1 BTC coin it wants to swap with a 1 BTC coin from Bob.
* Alice sends its 1 BTC coin to bilateral control (Alice temporary key and =
Bob temporary key).
  * Backoffs and confirmations and etc etc are needed, we all know how to d=
o CoinSwap safely, I elide those details here.
* Bob sends its 1 BTC to bilateral control (Alice 2nd temporary key and Bob=
 2nd temporary key).
* Alice and Bob complete the CoinSwap protocol and now both know the swap s=
ecret X, and have to claim the bilateral control before some future blockhe=
ight L.
* Alice can send its Alice temporary key to Bob, so that Bob can change the=
 second transaction as it likes.
  * Bob can merge it with a coin it happens to have, without having to coor=
dinate signing with Alice (i.e. it gets PayJoin on the second tx for free).
  * If Bob the maker gets another swap request, it can spend directly from =
the bilateral control address to another bilateral control address with a d=
ifferent taker, reducing blockchain footprint.
  * Bob can fee bump using RBF instead of CPFP.
* Bob can also now send its Bob 2nd temporary key to Alice, for similar adv=
antages for Alice.

It does require that both Alice and Bob respect the timeout --- the bilater=
al outputs have to be spent before the timeout, else the timelock branches =
come into play.
But Alice and Bob, after private key turnover, need not *immediately* broad=
cast the claiming transactions --- they can wait a little time for opportun=
ities to change the claiming transaction, for example if they get an incomi=
ng payment they could assume that the recently-concluded swap is safe to me=
rge with the new incoming coin and they can CPFP the incoming payment on th=
e mempool with their existing coin, or Bob the maker might get another cust=
omer and Bob can cut-through from one swap to the next, reducing 4 transact=
ions for 2 swaps to just 3 transactions (and if it can continuously chain c=
ustomers that way, in the long run Bob on average has 1 transaction per swa=
p, halving the block space usage needed for CoinSwap).

This increases complication of the implementation, but you potentially get =
an improvement in blockchain space for popular makers, with an asymptote of=
 50% reduction, so it is probably worth implementing.


Thus, if Alice wants to multipay, she could just sum up all the outgoing va=
lues, then specify the sum to Bob.
Then it can modify the second transaction to pay multiple destinations (sin=
ce it has the private keys to remake that).
Of course, all the outgoing payments are now linked together.... but I supp=
ose you can warn the user of Alice of such.

It would probably be best for both Alice and Bob to always change the desti=
nation address as well after private key turnover.


> > Okay, from what little I understand it seems that "even if sparse subse=
t 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 a=
re 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 CoinSwa=
p 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 th=
em 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 specifyi=
ng a set of standardized swap amounts.

The initial standards can be derived from false-positive-statistics, but on=
ce SwapMarket starts to become popular, then the actual statistics of the c=
hain becomes skewed towards those standard swap amounts.
This makes it even wiser to also use those standard swap amounts, because o=
f the larger anonymity sets.

Regards,
ZmnSCPxj