From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from hemlock.osuosl.org (smtp2.osuosl.org [140.211.166.133]) by lists.linuxfoundation.org (Postfix) with ESMTP id 38099C0175 for ; Mon, 4 May 2020 08:28:51 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by hemlock.osuosl.org (Postfix) with ESMTP id 1D2D88804A for ; Mon, 4 May 2020 08:28:51 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from hemlock.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id kIj9fSu2cRS2 for ; Mon, 4 May 2020 08:28:47 +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 hemlock.osuosl.org (Postfix) with ESMTPS id 2589987FEA for ; Mon, 4 May 2020 08:28:47 +0000 (UTC) Date: Mon, 04 May 2020 08:28:41 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com; s=protonmail; t=1588580923; bh=awCA2DebqQZxQodSHZ/qcqzCby+zlQyMU44XvPUSRfo=; h=Date:To:From:Cc:Reply-To:Subject:In-Reply-To:References:From; b=fBgqgwzWbEwpPjzixPO/RIQZVRJ7rvXnqImMK5edQdV/Vc9HmbBnh1EYUqVJIyWWj O0EbOqe3hA6IlmFYUMBvmoLsICqvIXy6nDNAnQ58zNcMcdZjOYsrSeZjz7qERPBTEg mGXY1r+F7ucAkeEeMaPacEjf2WIJHxenosTupPU8= To: Chris Belcher From: ZmnSCPxj Reply-To: ZmnSCPxj Message-ID: In-Reply-To: <5e5ed1c3-085e-2137-5368-4e605e79b5bf@riseup.net> References: <-_xRcjb8H_0Bck71k4VkeukEBgHT-03ikLTIdyTG2P0rt0T_mvN4b4FejmWobwnAUCGNaDpFQlPc3TMwlml1gjnZ1lwSumeEYQpXSyijND0=@protonmail.com> <0e1c0287-617c-976c-9fd4-16683881d5d5@riseup.net> <25848910-24ca-8b49-ad20-39afae2a856b@riseup.net> <5e5ed1c3-085e-2137-5368-4e605e79b5bf@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: Mon, 04 May 2020 08:28:51 -0000 Good morning CB, > Chain analysis doesn't in fact know that 1-input-1-output transfers are > self-transfers, this is merely a heuristic that can be flawed. For > example I accept donations in bitcoin and a surprising number of them > are 1-input-1-output or multi-input-1-output, presumably the donators > did it for privacy reasons or cost reasons. A heuristic need not be perfect to be effective, and I am quite sure that, = outside of donation, most 1-output transfers will be self-transfers. Indeed, the old cliche of donating tainted/stolen funds is most likely a cl= iche for a reason. Perhaps you are a beneficiary of some movie hero who has stolen the money f= rom a villain who acquired wealth by immoral means. Unlike change heuristics, misleading the 1-output heuristic is difficult; w= hoever got control of the single output is either yourself, or somebody who= swapped coins with you. > Also I believe many people > use 1-input-1-output transactions for funding Lightning channels. Yes, Lightning helps privacy, that is correct. However, do note that Lightning channels tend to be long-lived, meaning it = will be a large number of blocks that such a TXO will be unspent. Due to the timeout on CoinSwap, the fund needs to be claimed quickly, in mu= ch shorter time than a typical Lightning channel. This can help narrow down payment heuristics. > > Although even so, your argument suggests that its better for at least > some of the time for Alice and Bob to create 2-output transactions and > mess with the change output detection heuristics to try to get chain > analyzers to assign the wrong output as change. Yes, I agree. > If the receiving end doesn't have a suitable UTXO for a PayJoin then > they won't get the CoinSwap deal. The liquidity market is a free market, > takers are the maker's customers and they have a wide choice. In such a > case the maker would have been outcompeted by other makers which do have > extra UTXOs. PayJoin might not buy you as much as you think. So Alice has two coins it does not want to CoinJoin for unknown reasons: Salary as ---> Alice teacher LiveJasmin ---> Alice payout Alice swaps them to Bob, who PayJoins the incoming funds. Since Bob has been operating for a long time, its coins have a varied and s= toried history. WannaCry ----> Bob ----+ | | Salary as ---> Alice ---+--> Bob teacher LiveJasmin ---> Alice ---+--> Bob payout | | ex-JoinMarket -> Bob ----+ maker Alice does *not* want Bob to join those two Bob-owned coins, still, because= chain analysis would not only implicate her in WannaCry, but also as a Liv= eJasmin model ***and*** (gasp!) a JoinMarket money launderer (I am being fa= cetious here). And since the swap has completed, Bob controls those coins. If another taker comes along, offering a high fee for a big swap, and Bob *= has to* merge those two coins (that ultimately got history from Alice) in o= rder to cover what the taker is requesting (because the taker has to make a= big single payout to some other party, so needs a single large UTXO, not t= wo small ones), what do you think Bob will do? In a free market where the takers have wide choice, do you think Bob will e= conomically-rationally help protect the secret life of Alice when not doing= so would let Bob earn more coins? Now of course, it would seem very unlikely that Alice the teacher is the ha= cker behind WannaCry *and* a LiveJasmin model *and* a money launderer, so n= o problem, right? It just makes surveillors looks like fools right? Except that Bob could have skipped the PayJoin step and just merged those f= our coins in a single transaction later, and the conclusion of surveillors = would still be the same, for much the same effect, at reduced blockspace (s= pend in a single transaction instead of 3). So I think it is better if Bob actually avoids small merges of a two or thr= ee or four coins, and should do the occasional mass merge of large numbers = of coins. This leads to better misleading of surveillors, and is incentive compatible= since it reduces blockspace usage for Bob to do the occasional mass merge = rather than PayJoining at every swap. > Your discussion with Alice having two UTXOs she doesn't want to co-spend > is definitely interesting. Perhaps also another way to solve is for > Alice to spend her UTXOs in 2-output transactions and mess with the > change output detection heuristics, say CoinSwapping 0.5 BTC from one > coin and 0.7 BTC from the other, with the total 1.2 BTC going to Carol. That seems to be a good idea indeed, and significantly better than relying = on PayJoin to obscure the history of coins. Of course, doing change-output-heuristic-breaking means splitting up coins,= increasing the number of UTXOs. But that combines well with Bob the maker periodically merging many small c= oins. > Of course if Alice specified an amount when she was actually > self-mixing, it would be easy for her to come up with a random value > that was close to some round number, either in BTC or another currency. Yes, and I suggest this is always be done, as part of the protocol. > Private key turnover is a great idea. It could also help with the > earlier problem of 1-input-1-output transactions being markers, because > when the coins in 2-of-2 multisigs are spent they may end up being spent > in a wider variety of ways. Indeed. It gets a few features "for free", at the cost of greater complexity at the= simple "I only want to swap once, then forget about the coins for a while"= case. * It gets PayJoin at the second transaction for free. * It lets Bob the maker cut-through for a new taker. * It reduces the cost on Bob to merge large numbers of coins at once. * It lets Alice the taker cut-through for a new maker if she wants to do mu= lti-round swaps (though note the objection "Value-based Directionality" in = my writeup https://zmnscpxj.github.io/bitcoin/multiswap.html ; though count= ernote that if CoinSwaps are as hard to identify as my naive understanding = of your math suggests, this should be a relatively minimal problem). > > > > > Okay, from what little I understand it seems that "even if sparse s= ubset 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 othe= r > > > 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 cro= wd > > > 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 su= ms are 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 Coi= nSwap 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 offer= s them 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 spec= ifying a set of standardized swap amounts. > > The initial standards can be derived from false-positive-statistics, bu= t once SwapMarket starts to become popular, then the actual statistics of t= he chain becomes skewed towards those standard swap amounts. > > This makes it even wiser to also use those standard swap amounts, becau= se of the larger anonymity sets. > > It's very unlikely for the 2 BTC subset sum to be uncommon but 1.5 BTC > to be common, because they are very close in value, and these functions > seem to end up being smooth and slowly-varying, at least in my brief > tests. It might be a concern when comparing 2 BTC to 20 BTC or 200 BTC. If it is as smooth and naturally-occurring as you suggest, then it seems to= me as well that the distribution of CoinSwap values will be just as smooth= and naturally-occurring, so my naive understanding is still "even if spars= e subset sum is easier than subset sum, it is still hard, so it probably wi= ll not matter in practice". People will mix due to receiving some amount. That amount will be sampled from some naturally-occurring distribution. Thus, CoinSwap values will be sampled from the same naturally-occurring dis= tribution. People will mix due to having to send some amount they do not want to be tr= acked to them. That amount will be sampled from some naturally-occurring distribution. Thus, CoinSwap values will be sampled from the same naturally-occurring dis= tribution. ....I think? Maybe? Regards, ZmnSCPxj