{"type":"rich","version":"1.0","author_name":"npub1g5zswf6y48f7fy90jf3tlcuwdmjn8znhzaa4vkmtxaeskca8hpss23ms3l","author_url":"https://nostr.ae/npub1g5zswf6y48f7fy90jf3tlcuwdmjn8znhzaa4vkmtxaeskca8hpss23ms3l","provider_name":"njump","provider_url":"https://nostr.ae","html":"📅 Original date posted:2020-04-30\n📝 Original message:Good morning CB,\n\n\n\u003e Equal-output-coinjoins and JoinMarket also have a version of the\n\u003e common-input-ownership-heuristic (CIOH), because its often possible to\n\u003e separate the inputs into sets of their owners of a equal-output-coinjoin\n\u003e using the input amounts. CoinSwap can be combined with something like\n\u003e PayJoin or CoinJoinXT, which would genuinely break the CIOH, so such a\n\u003e system wouldn't have this flaw either.\n\u003e\n\u003e For those reasons I've been thinking a CoinSwap system wouldn't need as\n\u003e many mixdepths, maybe it could use two or even just one.\n\nWould 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)?\nOr would imposing the rule \"all sends must be via CoinSwap\" be sufficient (and follow the ZeroLink rule in spirit)?\n\n\u003e If so, then it follows that multi-transaction CoinSwaps can be done by\n\u003e having UTXOs come from the same mixdepth, as long as the inputs that\n\u003e should be separate are not co-spent in the same transaction.\n\nThis \"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.\n\nStill, 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.\nAnd 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.\n\nOf 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?\n(I imagine this would make coin selection even harder, but I am not a mathematician and there may be some trivial solution to this.)\n\nNow --- 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?\nThat somebody else does not know that information.\nInstead, 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).\n\nCoins 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).\n\n\u003e\n\u003e Remember that a passive surveillor of the blockchain doesn't see\n\u003e mixdepths at all, they see addresses and transactions, and must use\n\u003e heuristics to try to cluster them together. We can break these heuristics.\n\u003e\n\u003e \u003e 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.\n\u003e\n\u003e Someone who has the ability to write such code should also have the\n\u003e awareness to realize that mixing equal-output-coinjoins with coinswaps\n\u003e damages the privacy because it breaks the steganography of coinswaps.\n\u003e\n\u003e Also, because CoinSwap is better than equal-output CoinJoin in almost\n\u003e every way, we can expect users (who are takers) to stop using JoinMarket\n\u003e and switch over to CoinSwap if the software becomes mature. So such a\n\u003e JoinMarket maker won't get many customers, and so there wouldn't be much\n\u003e point writing such maker code.\n\nAn 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 might not want to do possibly-computationally-expensive blockchain analysis to evaluate whether a particular maker values privacy.\nAn unscrupulous maker might thus earn more than a more scrupulous maker can, at least during the transition from JoinMarket to SwapMarket, and get a greater share of the future SwapMarket available liquidity due to their increased earnings during the transition.\n\nAgainst this we should remember that software that does two things is four times as complicated as software that does one thing, so hopefully your projected transition from JoinMarket to SwapMarket will be fast enough that such a combined Join/SwapMarket maker software does not arise fast enough to matter.\n\n\n\u003e But for sure it would be good to reuse code in any eventual\n\u003e implementation. Indeed Waxwing's implementation did:\n\u003e https://github.com/AdamISZ/CoinSwapCS\n\u003e\n\u003e \u003e 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.\n\u003e \u003e In that case, Bob will have to split a UTXO it owns.\n\u003e \u003e 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.\n\u003e \u003e Or in terms of mixdepths, Bob can split within a mixdepth but each outgoing UTXO in the same swap should be from different mixdepths.\n\u003e\n\u003e A good way to do it could be for Alice to tell Bob that she wants 10 BTC\n\u003e and let Bob figure out on his own how to get that amount, based on the\n\u003e amounts he already has. If Alice is making a payment she can provide\n\u003e that amount too, but all the other output amounts can be up to Bob.\n\nThis 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.\nAnd 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).\n(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.)\n\nOtherwise, Bob can get information:\n\n* \"Oh, Alice did not specify any of the outputs, just the total amount, all of my old coins are owned by Alice now.\"\n* \"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.\"\n* \"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.\"\n\nThe 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.\n\nAgain, the maker might be an active surveillor, thus we should reduce information leaks to the maker as much as we can.\n\n\u003e\n\u003e Bob would often still have to split a UTXO he owns, but see below about\n\u003e breaking change address heuristics.\n\u003e\n\u003e \u003e 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.\n\u003e \u003e 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.\n\u003e \u003e 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.\n\u003e\n\u003e If Bob needs to split a UTXO he'd do that with a change output. And\n\u003e because we understand change detection heuristics we can intentionally\n\u003e break them, for example if Bob's UTXO is on a p2sh-p2wpkh address and\n\u003e the CoinSwap address is of that type too (because ECDSA-2P is being\n\u003e used) then Bob could make his change output p2wpkh or p2pkh. Then anyone\n\u003e using the script-type-heuristic would think that the CoinSwap address is\n\u003e actually change and still belongs to Bob, and that the real change\n\u003e address is actually the payment or CoinSwap address. i.e. the adversary\n\u003e would assume that wallet software only uses one script type, in this\n\u003e case it assumes that Bob's wallet is exclusively p2sh-p2wpkh.\n\u003e\n\u003e \u003e \u003e -   Multi-transaction CoinSwaps aren't truly an example of a subset-sum\n\u003e \u003e \u003e     problem, but \"sparse subset sum\", a related and easier problem.\n\u003e \u003e \u003e     The way its normally formulated, subset sum is about finding a subset\n\u003e \u003e \u003e     that adds up to a target value. But in multi-transaction coinswap\n\u003e \u003e \u003e     there'd only be three or four CoinSwap outputs, so the problem is\n\u003e \u003e \u003e     finding just three or four integers in a big set that add up to the target.\n\u003e \u003e \u003e     You could think of it mathematically that the n-choose-k function is\n\u003e \u003e \u003e     near-polynomial when k is near 0 or near n, and the function is\n\u003e \u003e \u003e     exponential when k is near n/2.\n\u003e \u003e \u003e     A more promising way to build privacy is to create a situation where an\n\u003e \u003e \u003e     adversary would find a huge amount of false positives which are very\n\u003e \u003e \u003e     close the amount being sent. So even if the adversary has enough\n\u003e \u003e \u003e     computational power to iterate all the amounts it won't help them much\n\u003e \u003e \u003e     due to the huge number of false positives.\n\u003e \u003e \u003e\n\u003e \u003e\n\u003e \u003e What are your thoughts on creating such possible situations?\n\u003e \u003e An idea is to require standard swap amounts, i.e. similar to the standard 100mBTC mixing bin of Wasabi.\n\u003e \u003e 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).\n\u003e\n\u003e I think we can get the false positive count up because the n-choose-k\n\u003e function still gets quite large as k increases.\n\u003e\n\u003e We can make a simplified reasonable assumption that outputs on the\n\u003e blockchain follow a lognormal distribution. An adversary trying to unmix\n\u003e a 3-transaction CoinSwap would have to find the sum of every\n\u003e 3-combination of the relevant outputs. For our case, the sum of three\n\u003e lognormal distributions is another lognormal distribution with different\n\u003e parameters, it's corresponding frequency distribution would get scaled\n\u003e by n-choose-3. This frequency distribution is what the adversary would\n\u003e find when searching, and that distribution would be quite tall because\n\u003e of the scaling by n-choose-k. Suppose our CoinSwap is for 4 BTC then the\n\u003e adversary would look at their frequency distribution at 4 BTC and find a\n\u003e pretty big number, i.e. many other combinations of 3 outputs would add\n\u003e up to 4 BTC just by chance. That is the false positive rate, and is our\n\u003e anonymity set with respect to this attack.\n\u003e\n\u003e To work this out precisely we'd need to study the distribution of output\n\u003e values on the blockchain today, and see how it behaves when summed\n\u003e together. But the lognormal distribution assumption is probably not too\n\u003e far from the truth, as it appears all the time in economics and finance,\n\u003e and there is a clear justification for why. And the scaling by\n\u003e n-choose-k would still hold.\n\nOkay, 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?\n\n\u003e\n\u003e Along with that, some output amounts have very few significant figures\n\u003e (e.g. 1 BTC, 0.1 BTC, 0.01 BTC), presumably because the user types just\n\u003e one number on their keyboard when creating a transaction. We can use\n\u003e that fact to add a bit of privacy by occasionally making one of our\n\u003e outputs also be rounded like that.\n\nI agree.\n\nRegards,\nZmnSCPxj"}