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 EE62CC016F for ; Fri, 1 May 2020 07:17:29 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by fraxinus.osuosl.org (Postfix) with ESMTP id DD3048901B for ; Fri, 1 May 2020 07:17:29 +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 7FxET5F89_wh for ; Fri, 1 May 2020 07:17:27 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mail-40132.protonmail.ch (mail-40132.protonmail.ch [185.70.40.132]) by fraxinus.osuosl.org (Postfix) with ESMTPS id DCBEC89014 for ; Fri, 1 May 2020 07:17:26 +0000 (UTC) Date: Fri, 01 May 2020 07:17:19 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com; s=protonmail; t=1588317443; bh=2ePvisYx1pHaHZPh08NJuYObbakQpwAVsbQfxWcAVeA=; h=Date:To:From:Cc:Reply-To:Subject:In-Reply-To:References:From; b=OumYOKOW70eEg+loM5hvwbZ18qo/grzzL+WCp9mrkpIGciAJDDBRqxpXPq8w9/H31 Tyiio6C0zpfLLuITEKgf7/La8MrvQs4yAvM3y4ryfssxCk/KKq4ZKA1cjwnbweEa7h DGxEvtSRI9rxMC5KJyY2XCVd2u5JmniDrlzFBRDA= To: Chris Belcher From: ZmnSCPxj Reply-To: ZmnSCPxj Message-ID: In-Reply-To: <25848910-24ca-8b49-ad20-39afae2a856b@riseup.net> References: <-_xRcjb8H_0Bck71k4VkeukEBgHT-03ikLTIdyTG2P0rt0T_mvN4b4FejmWobwnAUCGNaDpFQlPc3TMwlml1gjnZ1lwSumeEYQpXSyijND0=@protonmail.com> <0e1c0287-617c-976c-9fd4-16683881d5d5@riseup.net> <25848910-24ca-8b49-ad20-39afae2a856b@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: Fri, 01 May 2020 07:17:30 -0000 Good morning CB, > > This "as long as the inputs that should be separate are not co-spent" i= s precisely 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= CoinSwap 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 a= nd your customer wants to get a UTXO that is larger than any you have on ha= nd, 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 = 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? > > (I imagine this would make coin selection even harder, but I am not a m= athematician 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 e= lse? > > That somebody else does not know that information. > > Instead, that somebody else must always assume that any coins it got fr= om the same CoinSwap operation must not be safely mergeable (though they ca= n still be used in the same swap together). > > Coins received via receive addresses would also not be mergeable with a= ny other coins, except coins to the same address (because coins in the same= address already leak that they are owned by the same owner). > > Yes I guess you're right. This part about mixdepths requires further > thought. > > CoinSwap can be combined with some kind of CoinJoin (most likely > something similar to PayJoin or CoinJoinXT). That should help with the > reasoning about co-spending inputs and mixdepths, because other inputs > that are not owned by the taker will often be co-spent anyway. > > Regarding coins which mustn't be co-spent being coinswapped to somebody > else, ideally that coinswap maker will receive coins from unrelated > takers too, so will merge their coins along with those as well. Also the > fact that a coinswap happened means there are two transactions between > the taker's-inputs-which-mustnt-be-merged and them actually being merged. One of those transactions (the second one) will be a 1-input 1-output tx (i= t moves the coin from bilateral control to unilateral control of Bob), whic= h chain analysis already knows to be a self-transfer. The first transaction will also usually be a 1-input 1-output tx as well (i= t moves the coin from unilateral of Alice to bilateral control) if you did = not do any splitting or merging before providing the coin into the swap (fo= r example if this comes from the taker, and the taker knows all the coins i= t wants to swap cannot be safely merged together). If chain analysis keeps the heuristic "1-input 1-output is a self-payment b= ecause srsly who has an exact amount for a payment Bitcoin is volatile lol"= , then the resulting coins still are not safe to merge, because chain analy= sis will "pass through" the swap operation and if the two coins are later m= erged then they still end up *correctly* concluding the original coins were= owned by the same owner. Using a PayJoin construction for the second tx would help, but if the recei= ving end does not have a spare UTXO it can merge with (e.g. all its liquidi= ty got tied up in the swap) then there might not be an opportunity to PayJo= in. There is also little that can be done about the first transaction, in case = it ends up being a 1-input 1-output. Suppose Alice the taker has a 1 BTC output and a 1 BTC output *and no other= coins*, both of which it cannot safely merge, and it has to pay 1.2 BTC to= Carol. Alice then has to CoinSwap them to Bob the maker, requesting a 1.2 BTC outp= ut going to Carol and the rest in whatever loose change Bob has. Alice then has to use two 1-input 1-output txes for each of its 1 BTC outpu= ts (because it cannot merge them together) to put them into bilateral contr= ol. Then Bob claims them from bilateral control with 1-input 1-output txes as w= ell (it cannot merge them together, because that might break Alice privacy,= and Bob might not have any other spare coins it can merge with the incomin= g funds). Now, even if Bob PayJoins the second tx for both 1 BTC outputs, it still ca= nnot merge the resulting joined coins together, because the "spent-together= " analysis would still tie those coins as being owned by the same owner, it= is simply that the surveillor will think the owner owns more coins than it= actually does, but the two 1 BTC TXOs that Alice used to own are still ana= lyzed as being owned by the same owner if they are ever merged. What Alice could do, to "merge" its 1BTC coins together, would be to swap o= nly one of the 1BTC coins first, for a single 1BTC coin as well. Then presumably the incoming 1BTC coin has no linkage with the coin Alice s= wapped out (Alice hopes), then Alice could spend that new 1BTC coin with th= e old one it could not merge with the coin it swapped out. (Actually Alice does not need to do that as it is the customer after all, b= ut maybe Bob the maker has to do that sometimes, in case it finds there are= too many cannot-spend-together constraints in its pool of UTXOs and it is = getting harder to select coins --- but if so, who does Bob the maker swap *= with*? If Bob can encounter that problem, then maybe other makers will also have t= hat problem as well!) (the above can be done by PayJoining with the unswapped coin on either the = first or second transaction in the swap as well; the idea is more general.) > > Great point on the receive addresses coins. Another use case of > mixdepths is to stop incoming payments from two different sources being > linked together. We could eliminate mixdepths entirely and just use "cannot merge with X" co= nstraints. When the wallet sees an incoming payment, it just marks it as "cannot merge= with" all other coins it owns, unless they have the same address. This prevents any linkage at all and is maximally private. On a CoinSwap, the incoming coins are marked as "cannot merge with" to each= other in the same CoinSwap operation, but not with any other coins it owns= . Maybe? It might be easier for the user to understand as well, and reduces scope fo= r mistakes in using mixdepths. For example, I might have a sensitive source of funds (e.g. from all the ra= nsomware I have been writing) and put them in one mixdepth, then after a fe= w months I forgot which mixdepth I put those in and accidentally use it for= my on-the-books salary. > > > > 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 th= e change from splitting for the same CoinSwap, e.g. if Bob has only 9 BTC a= nd 1 BTC coins and Alice wants a 6 BTC / 3 BTC / 1 BTC split, then Bob cann= ot 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 th= e > > > 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= 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 fo= r herself prior to storing in cold storage. > > And if Alice wants to use a single swap to pay to multiple targets at o= nce, 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). > > (We could constrain it such that Alice can make only one payment per Co= inSwap, 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 amoun= t, all of my old coins are owned by Alice now." > > - "Oh, Alice specified an exact value for one of the outputs, that on= e is no longer owned by Alice but the rest are owned by Alice." > > - "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." > > > > 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 e= lse --- or Alice specifies all of them. > > Again, the maker might be an active surveillor, thus we should reduce i= nformation leaks to the maker as much as we can. > > Yep great point. > > A benefit of Alice not specifying any amounts is that Bob is able to > improve privacy and reduce costs by creating fewer change outputs. A > downside is that this leaks Alice's intentions (self-mix vs payment) to B= ob. > > A solution could be to add randomness. Have Alice randomly specify > payment amounts with some probability even if she is only self-mixing. > > Although this doesn't solve everything, because Alice not specifying any > amounts implies self-mixing. But at least specifying some amounts > doesn't imply a payment. I think that maybe it would be a better policy for Alice to always just giv= e a specified payment amount at all times. Of course, a sufficiently motivated Bob could always just do statistical an= alysis on the payment amount (e.g. if it is not equivalent to some round nu= mber of United States Green Historical Commemoration Papers, it is unlikely= to be a payment but instead a random amount that Alice had to provide on a= self-payment). So ..... Anyway, slightly unrelated, maybe we can simply have Alice specify a single= payment amount always, as an unremovable part of the protocol. I proposed "private key turnover" here: https://github.com/AdamISZ/CoinSwap= CS/issues/53 Basically, after exchanging the swap secret, it is now safe to give your sh= are of bilateral control to your swap partner, so you can just turn over th= at private key to the swap partner. For clarity: * Alice owns a 1 BTC coin it wants to swap with a 1 BTC coin from Bob. * Alice sends its 1 BTC coin to bilateral control (Alice temporary key and = Bob temporary key). * Backoffs and confirmations and etc etc are needed, we all know how to d= o CoinSwap safely, I elide those details here. * Bob sends its 1 BTC to bilateral control (Alice 2nd temporary key and Bob= 2nd temporary key). * Alice and Bob complete the CoinSwap protocol and now both know the swap s= ecret X, and have to claim the bilateral control before some future blockhe= ight L. * Alice can send its Alice temporary key to Bob, so that Bob can change the= second transaction as it likes. * Bob can merge it with a coin it happens to have, without having to coor= dinate signing with Alice (i.e. it gets PayJoin on the second tx for free). * If Bob the maker gets another swap request, it can spend directly from = the bilateral control address to another bilateral control address with a d= ifferent taker, reducing blockchain footprint. * Bob can fee bump using RBF instead of CPFP. * Bob can also now send its Bob 2nd temporary key to Alice, for similar adv= antages for Alice. It does require that both Alice and Bob respect the timeout --- the bilater= al outputs have to be spent before the timeout, else the timelock branches = come into play. But Alice and Bob, after private key turnover, need not *immediately* broad= cast the claiming transactions --- they can wait a little time for opportun= ities to change the claiming transaction, for example if they get an incomi= ng payment they could assume that the recently-concluded swap is safe to me= rge with the new incoming coin and they can CPFP the incoming payment on th= e mempool with their existing coin, or Bob the maker might get another cust= omer and Bob can cut-through from one swap to the next, reducing 4 transact= ions for 2 swaps to just 3 transactions (and if it can continuously chain c= ustomers that way, in the long run Bob on average has 1 transaction per swa= p, halving the block space usage needed for CoinSwap). This increases complication of the implementation, but you potentially get = an improvement in blockchain space for popular makers, with an asymptote of= 50% reduction, so it is probably worth implementing. Thus, if Alice wants to multipay, she could just sum up all the outgoing va= lues, then specify the sum to Bob. Then it can modify the second transaction to pay multiple destinations (sin= ce it has the private keys to remake that). Of course, all the outgoing payments are now linked together.... but I supp= ose you can warn the user of Alice of such. It would probably be best for both Alice and Bob to always change the desti= nation address as well after private key turnover. > > Okay, from what little I understand it seems that "even if sparse subse= t sum is easier than subset sum, it is still hard, so it probably will not = matter in practice", would that be a fair takeaway? > > Not exactly. Here's another summary: > > Suppose Alice has V bitcoins and mixes them with multi-transaction > CoinSwap, she receives transactions with amounts (w_0, w_1, w_2....) > which add up to V. > > Privacy relying on the (sparse) subset sum problem works by making it > computationally infeasible for an adversary to search the entire > blockchain for sets of transactions (w_0, w_1, w_2....) which add up to > V. I believe aiming for this kind of privacy isn't practical due to > block space considerations and others. > > Privacy relying on false positives does not make any search > computationally infeasible, it works by having a large number of other > sets of transactions (w_0, w_1, w_2....) which add up to V just by > chance. Then the transactions received by Alice's will have a big crowd > to hide in. I believe this is practical because the numbers are > proportional to the n-choose-k function which can still be very large. Hmm. So let us return to our example of Alice who owns a 1 BTC coin and a 1 BTC = coin. Now suppose we find, by false-positive-statistics, that 2 BTC subset sums a= re rare but, say, 1.5 BTC subset sums are significantly more common. So what Alice should do, if it wants to send 1.2 BTC to Carol via a CoinSwa= p with maker Bob, would be to split one of her 1 BTC coins to a 0.5 BTC and= 0.5 BTC coin. Then it takes the remaining 1 BTC coin and one of the 0.5 BTC and offers th= em in a CoinSwap to maker Bob, specifying a payment amount of 1.2 BTC. It seems to me, however, that this is not much different from just specifyi= ng a set of standardized swap amounts. The initial standards can be derived from false-positive-statistics, but on= ce SwapMarket starts to become popular, then the actual statistics of the c= hain becomes skewed towards those standard swap amounts. This makes it even wiser to also use those standard swap amounts, because o= f the larger anonymity sets. Regards, ZmnSCPxj