{"type":"rich","version":"1.0","author_name":"npub1ekvnqhww3aagwuj9t55dgj5y29u8cxdjllfv3vgppt8vc0zljhrs6lnm2u","author_url":"https://nostr.ae/npub1ekvnqhww3aagwuj9t55dgj5y29u8cxdjllfv3vgppt8vc0zljhrs6lnm2u","provider_name":"njump","provider_url":"https://nostr.ae","html":"📅 Original date posted:2020-04-29\n📝 Original message:Hello ZmnSCPxj,\n\n\nOn 29/04/2020 08:56, ZmnSCPxj wrote:\n\u003e It wold be nice to interoperate with JoinMarket, i.e. have a JoinMarket maker that also provides CoinSwap services using the same UTXOs.\n\nA great benefit of a CoinSwap system is that the transactions are\nsteganographic. If equal-output-coinjoins were involved that benefit\nwould be lost. So it would be better if it didn't happen.\n\n\u003e 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).\n\u003e I am uncertain what is the best way to handle multitransaction when considering the mixdepth system.\n\u003e 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.\n\u003e The issue here is:\n\u003e \n\u003e * 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.\n\u003e * 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.\n\u003e \n\u003e I am uncertain which tradeoff is better here, though I am inclined to think the latter is better.\n\nJoinMarket has many mixdepths (5 by default) because it's\nequal-output-coinjoins easily leak change addresses. CoinSwap\ntransactions don't have this flaw because they're steganographic. Such a\nsystem could also be coded to intentionally break the weaker change\noutput heuristics\n(https://en.bitcoin.it/wiki/Privacy#Change_address_detection).\n\nEqual-output-coinjoins and JoinMarket also have a version of the\ncommon-input-ownership-heuristic (CIOH), because its often possible to\nseparate the inputs into sets of their owners of a equal-output-coinjoin\nusing the input amounts. CoinSwap can be combined with something like\nPayJoin or CoinJoinXT, which would genuinely break the CIOH, so such a\nsystem wouldn't have this flaw either.\n\nFor those reasons I've been thinking a CoinSwap system wouldn't need as\nmany mixdepths, maybe it could use two or even just one.\n\nIf so, then it follows that multi-transaction CoinSwaps can be done by\nhaving UTXOs come from the same mixdepth, as long as the inputs that\nshould be separate are not co-spent in the same transaction.\n\nRemember that a passive surveillor of the blockchain doesn't see\nmixdepths at all, they see addresses and transactions, and must use\nheuristics to try to cluster them together. We can break these heuristics.\n\n\n\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\nSomeone who has the ability to write such code should also have the\nawareness to realize that mixing equal-output-coinjoins with coinswaps\ndamages the privacy because it breaks the steganography of coinswaps.\n\nAlso, because CoinSwap is better than equal-output CoinJoin in almost\nevery way, we can expect users (who are takers) to stop using JoinMarket\nand switch over to CoinSwap if the software becomes mature. So such a\nJoinMarket maker won't get many customers, and so there wouldn't be much\npoint writing such maker code.\n\nBut for sure it would be good to reuse code in any eventual\nimplementation. Indeed Waxwing's implementation did:\nhttps://github.com/AdamISZ/CoinSwapCS\n\n\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 In that case, Bob will have to split a UTXO it owns.\n\u003e \n\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 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\nA good way to do it could be for Alice to tell Bob that she wants 10 BTC\nand let Bob figure out on his own how to get that amount, based on the\namounts he already has. If Alice is making a payment she can provide\nthat amount too, but all the other output amounts can be up to Bob.\n\nBob would often still have to split a UTXO he owns, but see below about\nbreaking change address heuristics.\n\n\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 \n\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 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\nIf Bob needs to split a UTXO he'd do that with a change output. And\nbecause we understand change detection heuristics we can intentionally\nbreak them, for example if Bob's UTXO is on a p2sh-p2wpkh address and\nthe CoinSwap address is of that type too (because ECDSA-2P is being\nused) then Bob could make his change output p2wpkh or p2pkh. Then anyone\nusing the script-type-heuristic would think that the CoinSwap address is\nactually change and still belongs to Bob, and that the real change\naddress is actually the payment or CoinSwap address. i.e. the adversary\nwould assume that wallet software only uses one script type, in this\ncase it assumes that Bob's wallet is exclusively p2sh-p2wpkh.\n\n\u003e \n\u003e\u003e -   Multi-transaction CoinSwaps aren't truly an example of a subset-sum\n\u003e\u003e     problem, but \"sparse subset sum\", a related and easier problem.\n\u003e\u003e\n\u003e\u003e     The way its normally formulated, subset sum is about finding a subset\n\u003e\u003e     that adds up to a target value. But in multi-transaction coinswap\n\u003e\u003e     there'd only be three or four CoinSwap outputs, so the problem is\n\u003e\u003e     finding just three or four integers in a big set that add up to the target.\n\u003e\u003e\n\u003e\u003e     You could think of it mathematically that the n-choose-k function is\n\u003e\u003e     near-polynomial when k is near 0 or near n, and the function is\n\u003e\u003e     exponential when k is near n/2.\n\u003e\u003e\n\u003e\u003e     A more promising way to build privacy is to create a situation where an\n\u003e\u003e     adversary would find a huge amount of false positives which are very\n\u003e\u003e     close the amount being sent. So even if the adversary has enough\n\u003e\u003e     computational power to iterate all the amounts it won't help them much\n\u003e\u003e     due to the huge number of false positives.\n\u003e \n\u003e What are your thoughts on creating such possible situations?\n\u003e \n\u003e An idea is to require standard swap amounts, i.e. similar to the standard 100mBTC mixing bin of Wasabi.\n\u003e \n\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\nI think we can get the false positive count up because the n-choose-k\nfunction still gets quite large as k increases.\n\nWe can make a simplified reasonable assumption that outputs on the\nblockchain follow a lognormal distribution. An adversary trying to unmix\na 3-transaction CoinSwap would have to find the sum of every\n3-combination of the relevant outputs. For our case, the sum of three\nlognormal distributions is another lognormal distribution with different\nparameters, it's corresponding frequency distribution would get scaled\nby n-choose-3. This frequency distribution is what the adversary would\nfind when searching, and that distribution would be quite tall because\nof the scaling by n-choose-k. Suppose our CoinSwap is for 4 BTC then the\nadversary would look at their frequency distribution at 4 BTC and find a\npretty big number, i.e. many other combinations of 3 outputs would add\nup to 4 BTC just by chance. That is the false positive rate, and is our\nanonymity set with respect to this attack.\n\nTo work this out precisely we'd need to study the distribution of output\nvalues on the blockchain today, and see how it behaves when summed\ntogether. But the lognormal distribution assumption is probably not too\nfar from the truth, as it appears all the time in economics and finance,\nand there is a clear justification for why. And the scaling by\nn-choose-k would still hold.\n\nAlong with that, some output amounts have very few significant figures\n(e.g. 1 BTC, 0.1 BTC, 0.01 BTC), presumably because the user types just\none number on their keyboard when creating a transaction. We can use\nthat fact to add a bit of privacy by occasionally making one of our\noutputs also be rounded like that."}