To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
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>
From: Chris Belcher <belcher@riseup.net>
Autocrypt: addr=belcher@riseup.net; prefer-encrypt=mutual; keydata=
 xsFNBFPk74oBEACzBLjd+Z5z7eimqPuObFTaJCTXP7fgZjgVwt+q94VQ2wM0ctk/Ft9w2A92
 f14T7PiHaVDjHxrcW+6sw2VI2f60T8Tjf+b4701hIybluWL8DntG9BW19bZLmjAj7zkgektl
 YNDUrlYcQq2OEHm/MGk6Ajt2RA56aRKqoz22e+4ZA89gDgamxUAadul7AETSsgqOEUDI0FKR
 FODzoH65w1ien/DLkG1f76jd0XA6AxrESJVO0JzvkTnJGElBcA37rYaMmDi4DhG2MY4u63VE
 8h6DyUXcRhmTZIAj+r+Ht+KMDiuiyQcKywCzzF/7Ui7YxqeAgjm5aPDU2E8X9Qd7cqHQzFM7
 ZCqc9P6ENAk5a0JjHw0d0knApboSvkIJUB0j1xDIS0HaRlfHM4TPdOoDgnaXb7BvDfE+0zSz
 WkvAns9oJV6uWdnz5kllVCjgB/FXO4plyFCHhXikXjm1XuQyL8xV88OqgDFXwVhKrDL9Pknu
 sTchYm3BS2b5Xq1HQqToT3I2gRGTtDzZVZV0izCefJaDp1mf49k2cokDEfw9MroEj4A0Wfht
 0J64pzlBYn/9zor5cZp/EAblLRDK6HKhSZArIiDR1RC7a6s7oTzmfn0suhKDdTzkbTAnDsPi
 Dokl58xoxz+JdYKjzVh98lpcvMPlbZ+LwIsgbdH4KZj7mVOsJwARAQABzR9DaHJpcyBCZWxj
 aGVyIDxmYWxzZUBlbWFpbC5jb20+wsF+BBMBAgAoBQJT5O+KAhsDBQkSzAMABgsJCAcDAgYV
 CAIJCgsEFgIDAQIeAQIXgAAKCRDvc06md/MRKS8jD/9P9fSYSIVjltL9brAMfIu7wJn0H0lX
 TbcuCM2uQitJ3BNxI3c7aq5dEby27u5Ud54otncDJuRPQVDKs6H7t1rInitgJ1MTQ9/aQGFA
 btKcgtVIMFbeClzTTfWr4W7fE45NI7E9EANgk5JfmWh3U+KINYLF5RtqynYocrsP6zOV+G9A
 HCpBemd9TN60CoMLMyMzTHEW1oQffaVAXY8DgthEYO/odWYIod7VTmEm0zU1aSysPqMwPWNm
 8XIl0f8SfKQyZlAU8e1eCFVCenkE44FKC5qQNYc2UxexEYtfCWChTGc4oHKxIyYmTCCefsQF
 LvgwtvlNHRXHSDKSPSNcRcpl8DFpNEKrmMlkJ8Mx+YR05CydlTQ0bI3FBohJC+UHrjD5I3hA
 wJUC1o+yVSOEd+zN3cG1EECIwkEQSmBgG5t/le2RdzfXOdpf9ku2/zoBpq00R54JxUKlfRM7
 OPTv7X+1AKHkxOySdCZwGgvdh2Whuqs4kTvtco00gCFM9fBd5oi1RJuHtxHsj8+/XU15UItb
 jeo96CIlM5YUeoRLPT5mxZYWgYAARFeSFReNq/Tuwq9d8EokUrtAyrPayznliy53UJfWDVzl
 925c0Cz0HWaP2fWj+uFcj/8K0bhptuWJQy0Poht1z3aJC1UjEgr1Xz8I7jeSJmIlA9plcJw2
 k4dhWc7BTQRT5O+KARAAyFxAM28EQwLctr0CrQhYWZfMKzAhCw+EyrUJ+/e4uiAQ4OyXifRr
 ZV6kLRul3WbTB1kpA6wgCShO0N3vw8fFG2Cs6QphVagEH8yfQUroaVxgADYOTLHMOb7INS8r
 KI/uRNmE6bXTX27oaqCEXLMycqYlufad7hr42S/T8zNh5m2vl6T/1Poj2/ormViKwAxM+8qf
 xd8FNI4UKmq2zZE9mZ5PiSIX0qRgM0yCvxV39ex/nhxzouTBvv4Lb1ntplR/bMLrHxsCzhyM
 KDgcX7ApGm+y6YEsOvzw9rRCRuJpE4lth8ShgjTtNTHfklBD6Ztymc7q7bdPWpKOEvO5lDQ6
 q8+KfENv862cOLlWLk7YR2+mHZ1PXGhWC7ggwEkfGJoXo0x8X+zgUKe2+9Jj4yEhfL0IbFYC
 z2J5d+cWVIBktI3xqkwLUZWuAbE3vgYA4h8ztR6l18NTPkiAvpNQEaL4ZRnAx22WdsQ8GlEW
 dyKZBWbLUdNcMmPfGi5FCw2nNvCyN6ktv5mTZE12EqgvpzYcuUGQPIMV9KTlSPum3NLDq8QI
 6grbG8iNNpEBxmCQOKz2/BuYApU2hwt2E44fL8e6CRK3ridcRdqpueg75my6KkOqm8nSiMEc
 /pVIHwdJ9/quiuRaeC/tZWlYPIwDWgb8ZE/g66z35WAguMQ+EwfvgAUAEQEAAcLBZQQYAQIA
 DwUCU+TvigIbDAUJEswDAAAKCRDvc06md/MRKaZwD/9OI3o3gVmst/mGx6hVQry++ht8dFWN
 IiASPBvD3E5EWbqWi6mmqSIOS6CxjU0PncxTBPCXtzxo/WzuHGQg/xtNeQ0T8b2lBScZAw93
 qm1IcHXLUe5w/Tap6YaDmSYCIZAdtbHzYfPW4JK7cmvcjvF8jhTFOBEOFVQkTi19G7caVot0
 +wL1e2DRHDXAe5CinEpaLBlwHeEu/5j6wc3erohUZlK9IbAclj4iZTQbaq3EyqUXl59dBOON
 xmL5edJxzVishIYQGIyA9WP1SylXt+kO82NEqZG2OxdXAlzjuJ8C2pAG+nbLtDo4hcsiN/MA
 aX9/JB7MXclT5ioerF4yNgKEdfq7LmynsTUd8w/Ilyp7AD+BWoujyO94i8h9eKvjf9PvSwxQ
 uAjRpxne7ZJD8vCsMNXBHSbeEK2LiwStHL/w473viXpDD53J6OLxX6a5RummR+rixbMH7dgK
 MJQ7FlyDphm3or6CSkGEir1KA0y1vqQNFtHhguFapAWMDKaJjQQNgvZUmOo6hbZqmvUF1OWc
 d6GA6j3WOUe3fDJXfbq6P9Jmxq64op887dYKsg7xjQq/7KM7wyRcqXXcbBdgvNtVDP+EnzBN
 HyYY/3ms4YIHE5JHxQ9LV4yPcWkYTvb1XpNIFVbrSXAeyGHVNT+SO6olFovbWIC3Az9yesaM
 1aSoTg==
Message-ID: <25848910-24ca-8b49-ad20-39afae2a856b@riseup.net>
Date: Thu, 30 Apr 2020 18:18:03 +0100
MIME-Version: 1.0
In-Reply-To: <gAyc5MFCEkCjjdLSx_fKF-9MVnI4Zl6-BQ7Y-Q2_JNFYE2tQbCC1Js5YfE9RnPE_RPoVx57H0tWA-dpJ5SM7KP52DxTzHRdx6IF_pWjIh7A=@protonmail.com>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 7bit
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

Hello ZmnSCPxj,

On 30/04/2020 09:54, ZmnSCPxj wrote:
> 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 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.

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

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

>>
>> 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 CoinSwap Protocol part looks exactly like a Bitcoin transaction, with a "main" paying output and a "change" output, and the same techniques that work with current Bitcoin txes work with "CoinSwap Protocol" virtual transactions.
>>> It seems to me that, in a system of makers and takers, even if the maker 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, so 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 specific 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-sum
>>>>     problem, but "sparse subset sum", a related and easier problem.
>>>>     The way its normally formulated, subset sum is about finding a subset
>>>>     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 the 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 where an
>>>>     adversary would find a huge amount of false positives which are very
>>>>     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 standard 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, to force at least one false positive, but the surveillor could protect against 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 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.


Regards
CB