From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from fraxinus.osuosl.org (smtp4.osuosl.org [140.211.166.137]) by lists.linuxfoundation.org (Postfix) with ESMTP id 2C933C0172 for ; Wed, 29 Apr 2020 15:06:06 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by fraxinus.osuosl.org (Postfix) with ESMTP id 21FB486AB0 for ; Wed, 29 Apr 2020 15:06:06 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from fraxinus.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 6nF-boEfQ4ys for ; Wed, 29 Apr 2020 15:06:05 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mx1.riseup.net (mx1.riseup.net [198.252.153.129]) by fraxinus.osuosl.org (Postfix) with ESMTPS id 0179786AA5 for ; Wed, 29 Apr 2020 15:06:04 +0000 (UTC) Received: from bell.riseup.net (unknown [10.0.1.178]) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (Client CN "*.riseup.net", Issuer "Sectigo RSA Domain Validation Secure Server CA" (not verified)) by mx1.riseup.net (Postfix) with ESMTPS id 49C1zw3rd0zFfxj; Wed, 29 Apr 2020 08:06:04 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=riseup.net; s=squak; t=1588172764; bh=sa9+uLwRTGZKD7wMs2TlQ+379KWMn2RuRcoqBvbfvqA=; h=Subject:To:References:From:Date:In-Reply-To:From; b=ssAyfMx+6Q2rB6HeWW1o5fDxoguc2rq63vBiuNUcpJcqNjxNOdys0GT6vgSnxBgL/ YUq2aNRvPcaOoQC/we/ZYMUKm8QVcb1ZObmOhFYTO38BUfba0LUIt4CUBSk9w3d9PT SpNDAqE+X0OwoPxGR30i93XrPWyKoKmH6iQWn0JY= X-Riseup-User-ID: A67F65C3822A54DCCA710DD0D42AD1C92AC8F7DB04C01F92259E5EAD9D4B52B1 Received: from [127.0.0.1] (localhost [127.0.0.1]) by bell.riseup.net (Postfix) with ESMTPSA id 49C1zv5znDzJr8D; Wed, 29 Apr 2020 08:06:03 -0700 (PDT) To: ZmnSCPxj , Bitcoin Protocol Discussion References: <-_xRcjb8H_0Bck71k4VkeukEBgHT-03ikLTIdyTG2P0rt0T_mvN4b4FejmWobwnAUCGNaDpFQlPc3TMwlml1gjnZ1lwSumeEYQpXSyijND0=@protonmail.com> <0e1c0287-617c-976c-9fd4-16683881d5d5@riseup.net> From: Chris Belcher 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: Date: Wed, 29 Apr 2020 16:06:01 +0100 MIME-Version: 1.0 In-Reply-To: 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 X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 29 Apr 2020 15:06:06 -0000 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.