Return-Path: Received: from silver.osuosl.org (smtp3.osuosl.org [140.211.166.136]) by lists.linuxfoundation.org (Postfix) with ESMTP id 61155C016F for ; Thu, 30 Apr 2020 08:54:39 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by silver.osuosl.org (Postfix) with ESMTP id 3B5C320380 for ; Thu, 30 Apr 2020 08:54:39 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from silver.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id dzAeLS4FFzgU for ; Thu, 30 Apr 2020 08:54:35 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mail-40130.protonmail.ch (mail-40130.protonmail.ch [185.70.40.130]) by silver.osuosl.org (Postfix) with ESMTPS id 87D3820002 for ; Thu, 30 Apr 2020 08:54:35 +0000 (UTC) Date: Thu, 30 Apr 2020 08:54:28 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com; s=protonmail; t=1588236872; bh=iUWbQjCLxMqDq8F0Lp27Y40awCiSLXKMomX4OH9f86M=; h=Date:To:From:Cc:Reply-To:Subject:In-Reply-To:References:From; b=b7u3LPi7JRJRk83q0mYaVg1CsXNXGTOGuYauUbKvkDWOl9Z64N30jJfpv+bgn4qPI I2xTRCO5IENILBxDb9oMg4z9pzfejErby+7hVkKi4k0s9uqEqEp739aT6oyrSx9ipz 16EJD1H8w339MBFNq0v3AmT8tOWeNCGGdjKSozNU= To: Chris Belcher From: ZmnSCPxj Reply-To: ZmnSCPxj Message-ID: In-Reply-To: References: <-_xRcjb8H_0Bck71k4VkeukEBgHT-03ikLTIdyTG2P0rt0T_mvN4b4FejmWobwnAUCGNaDpFQlPc3TMwlml1gjnZ1lwSumeEYQpXSyijND0=@protonmail.com> <0e1c0287-617c-976c-9fd4-16683881d5d5@riseup.net> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Cc: Bitcoin Protocol Discussion 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: Thu, 30 Apr 2020 08:54:39 -0000 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 pr= ecisely 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 Coi= nSwap 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 y= our 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 ha= ve some relational entry which says "you cannot merge coin A and coin B" wh= ich 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 mathe= matician 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 t= he same CoinSwap operation must not be safely mergeable (though they can st= ill be used in the same swap together). Coins received via receive addresses would also not be mergeable with any o= ther coins, except coins to the same address (because coins in the same add= ress already leak that they are owned by the same owner). > > 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 s= eems 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-C= oinSwap (to increase their market, so to speak), so it might be better to j= ust 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. An 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 mi= ght not want to do possibly-computationally-expensive blockchain analysis t= o evaluate whether a particular maker values privacy. An unscrupulous maker might thus earn more than a more scrupulous maker can= , at least during the transition from JoinMarket to SwapMarket, and get a g= reater share of the future SwapMarket available liquidity due to their incr= eased earnings during the transition. Against this we should remember that software that does two things is four = times as complicated as software that does one thing, so hopefully your pro= jected transition from JoinMarket to SwapMarket will be fast enough that su= ch a combined Join/SwapMarket maker software does not arise fast enough to = matter. > 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 wan= t 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 ch= ange 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 s= plit its own 9 BTC coin then swap. > > Or in terms of mixdepths, Bob can split within a mixdepth but each outg= oing 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 bet= ter 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 fo= r 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 want= s to Bob, and it would imply as well that Alice has to obfuscate which of t= hose outputs have amounts that actually *matter* (by always insisting on wh= at the output amounts must be, rather than insisting on N output amounts an= d letting Bob handle the rest). (We *could* constrain it such that Alice can make only one payment per Coin= Swap, 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 n= o longer owned by Alice but the rest are owned by Alice." * "Oh, Alice specified exact values for two of the outputs, those two are d= efinitely 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 infor= mation leaks to the maker as much as we can. > > 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 C= oinSwap Protocol part looks exactly like a Bitcoin transaction, with a "mai= n" paying output and a "change" output, and the same techniques that work w= ith current Bitcoin txes work with "CoinSwap Protocol" virtual transactions= . > > It seems to me that, in a system of makers and takers, even if the make= r 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, s= o 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 speci= fic 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-s= um > > > problem, but "sparse subset sum", a related and easier problem. > > > The way its normally formulated, subset sum is about finding a su= bset > > > 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 t= he 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 wh= ere an > > > adversary would find a huge amount of false positives which are v= ery > > > 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 standa= rd 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, t= o force at least one false positive, but the surveillor could protect again= st 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 su= m is easier than subset sum, it is still hard, so it probably will not matt= er in practice", would that be a fair takeaway? > > 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. I agree. Regards, ZmnSCPxj