To: ZmnSCPxj <ZmnSCPxj@protonmail.com>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
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>
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: <ed482ed6-a79b-e20c-5356-8be4345333f5@riseup.net>
Date: Wed, 29 Apr 2020 16:06:01 +0100
MIME-Version: 1.0
In-Reply-To: <muQZ5QzVScvrjDkpZg1pWQMPFekgn_yqaro1i-JBZWCowA4HhybWFi3e5clygh5EIeLIa7jlykipA5nAxpiuLXK0-5SE3wEXXOTVwMlPAVU=@protonmail.com>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Subject: Re: [bitcoin-dev] Fwd: (Semi)Traceless 2-party coinjoin off-chain
 protocol using schnorr signatures
Precedence: list

Hello ZmnSCPxj,


On 29/04/2020 08:56, ZmnSCPxj wrote:
> It wold be nice to interoperate with JoinMarket, i.e. have a JoinMarket maker that also provides CoinSwap services using the same UTXOs.

A great benefit of a CoinSwap system is that the transactions are
steganographic. If equal-output-coinjoins were involved that benefit
would be lost. So it would be better if it didn't happen.

> However, this requires us to retain compatibility with the JoinMarket wallet structure, which is divided into mixdepths, with the rule that UTXOs in different mixdepths cannot be spent together in the same onchain UTXO (to move across mixdepths you have to do a send, and sending out is always done by a single CoinJoin round with multiple makers).
> I am uncertain what is the best way to handle multitransaction when considering the mixdepth system.
> My instinct is that if you are doing multitransaction (whether as taker or maker) then each transaction in the swap *has to* come from a different mixdepth.
> The issue here is:
> 
> * If all the UTXOs in the multitransaction swap come from the same mixdepth, then a surveillor who is monitoring that mixdepth gets a good hint in solving the sparse subset sum problem.
> * On the other hand, if all the UTXOs in the multitransaction swap come from different mixdepths, then a surveillor who has solved the sparse subset sum problem now has the hint that the different mixdepths are really owned by the same JoinMarket user.
> 
> I am uncertain which tradeoff is better here, though I am inclined to think the latter is better.

JoinMarket has many mixdepths (5 by default) because it's
equal-output-coinjoins easily leak change addresses. CoinSwap
transactions don't have this flaw because they're steganographic. Such a
system could also be coded to intentionally break the weaker change
output heuristics
(https://en.bitcoin.it/wiki/Privacy#Change_address_detection).

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.

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.

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 seems 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-CoinSwap (to increase their market, so to speak), so it might be better to just 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.

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

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.

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.