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

[Chris Belcher <belcher@riseup.net>]

Hello ZmnSCPxj,

>>> This "as long as the inputs that should be separate are not co-spent" is 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 and your 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 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 mathematician 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 the same CoinSwap operation must not be safely mergeable (though they can still be used in the same swap together).
>>> Coins received via receive addresses would also not be mergeable with any 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 (it moves the coin from bilateral control to unilateral control of Bob), which chain analysis already knows to be a self-transfer.
> The first transaction will also usually be a 1-input 1-output tx as well (it 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 (for example if this comes from the taker, and the taker knows all the coins it wants to swap cannot be safely merged together).
> 
> If chain analysis keeps the heuristic "1-input 1-output is a self-payment because 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 analysis will "pass through" the swap operation and if the two coins are later merged 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 receiving end does not have a spare UTXO it can merge with (e.g. all its liquidity got tied up in the swap) then there might not be an opportunity to PayJoin.
> 
> 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 output 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 outputs (because it cannot merge them together) to put them into bilateral control.
> Then Bob claims them from bilateral control with 1-input 1-output txes as well (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 incoming funds).
> 
> Now, even if Bob PayJoins the second tx for both 1 BTC outputs, it still cannot 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 analyzed 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 only 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 swapped out (Alice hopes), then Alice could spend that new 1BTC coin with the 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, but 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 that 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.)

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. Also I believe many people
use 1-input-1-output transactions for funding Lightning channels.

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.

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.

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.


>>>>> 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.
>>>
>>> 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 for 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 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 CoinSwap, 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 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 else --- or Alice specifies all of them.
>>> Again, the maker might be an active surveillor, thus we should reduce information 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 Bob.
>>
>> 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 give a specified payment amount at all times.
> Of course, a sufficiently motivated Bob could always just do statistical analysis on the payment amount (e.g. if it is not equivalent to some round number 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/CoinSwapCS/issues/53
> Basically, after exchanging the swap secret, it is now safe to give your share of bilateral control to your swap partner, so you can just turn over that 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 do 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 secret X, and have to claim the bilateral control before some future blockheight 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 coordinate 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 different 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 advantages for Alice.
> 
> It does require that both Alice and Bob respect the timeout --- the bilateral 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* broadcast the claiming transactions --- they can wait a little time for opportunities to change the claiming transaction, for example if they get an incoming payment they could assume that the recently-concluded swap is safe to merge with the new incoming coin and they can CPFP the incoming payment on the mempool with their existing coin, or Bob the maker might get another customer and Bob can cut-through from one swap to the next, reducing 4 transactions for 2 swaps to just 3 transactions (and if it can continuously chain customers that way, in the long run Bob on average has 1 transaction per swap, 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 values, then specify the sum to Bob.
> Then it can modify the second transaction to pay multiple destinations (since it has the private keys to remake that).
> Of course, all the outgoing payments are now linked together.... but I suppose you can warn the user of Alice of such.
> 
> It would probably be best for both Alice and Bob to always change the destination address as well after private key turnover.

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.

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.


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


Regards
CB