From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from silver.osuosl.org (smtp3.osuosl.org [140.211.166.136]) by lists.linuxfoundation.org (Postfix) with ESMTP id C6AA1C0881 for ; Sat, 28 Dec 2019 23:25:17 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by silver.osuosl.org (Postfix) with ESMTP id BCFDC203DB for ; Sat, 28 Dec 2019 23:25:17 +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 t33Y1lmKsdpQ for ; Sat, 28 Dec 2019 23:25:15 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mail-40135.protonmail.ch (mail-40135.protonmail.ch [185.70.40.135]) by silver.osuosl.org (Postfix) with ESMTPS id CDE42203D7 for ; Sat, 28 Dec 2019 23:25:14 +0000 (UTC) Date: Sat, 28 Dec 2019 23:25:07 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com; s=default; t=1577575511; bh=iB0KG24dPX5W7/8115rXuGSUyftcdLDlRaqeF7sDaR8=; h=Date:To:From:Reply-To:Subject:In-Reply-To:References:Feedback-ID: From; b=dkRYQpMCh2QhtIPhufLVaSZnBaPqWjnBG3wk+1rY/G1hFghPSn4p/Rf37qQqN98YW +z3m5gjZIK+EP4ArpFWCpyY1atttOm2igJ9G3BwjRnv5Y8Z95PPJTlzq+sDyU08tl7 6mrvKRtffRZLReIAoqSMpsNKqy8jPYCbzJ0ZS/Ws= To: nopara73 , Bitcoin Protocol Discussion From: ZmnSCPxj Reply-To: ZmnSCPxj Message-ID: In-Reply-To: References: Feedback-ID: el4j0RWPRERue64lIQeq9Y2FP-mdB86tFqjmrJyEPR9VAtMovPEo9tvgA0CrTsSHJeeyPXqnoAu6DN-R04uJUg==:Ext:ProtonMail MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Subject: Re: [bitcoin-dev] Non-equal value CoinJoins. Opinions. 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: Sat, 28 Dec 2019 23:25:17 -0000 Good morning Adam, > The CashFusion research came out of the Bitcoin Cash camp, thus this prob= ably went under the radar of many of you. I would like to ask your opinions= on the research's claim that, if non-equal value coinjoins can be really r= elied on for privacy or not. > > (Btw, there were also similar ideas in the Knapsack paper in 2017:=C2= =A0https://www.comsys.rwth-aachen.de/fileadmin/papers/2017/2017-maurer-trus= tcom-coinjoin.pdf=C2=A0)=C2=A0 > > https://github.com/cashshuffle/spec/blob/master/CASHFUSION.md#avoiding-am= ount-linkages-through-combinatorics=C2=A0=C2=A0 > > I copy the most relevant paragraphs here: > > =C2=A0 ---------BEGIN QUOTE ---------=C2=A0 > =C2=A0 > > Consider a transaction where 10 people have each brought 10 inputs of arb= itary amounts in the neighborhood of ~0.1 BCH. One input might be 0.0377104= 9 BCH; the next might be 0.24881232 BCH, etc. All parties have chosen to co= nsolidate their coins, so the transaction has 10 outputs of around 1 BCH. S= o the transaction has 100 inputs, and 10 outputs. The first output might be= 0.91128495, the next could be 1.79783710, etc. > > Now, there are 100!/(10!)^10 ~=3D 10^92 ways to partition the inputs into= a list of 10 sets of 10 inputs, but only a tiny fraction of these partitio= ns will produce the precise output list. So, how many ways produce this exa= ct output list? We can estimate with some napkin math. First, recognize tha= t for each partitioning, each output will typically land in a range of ~10^= 8 discrete possibilities (around 1 BCH wide, with a 0.00000001 BCH resoluti= on). The first 9 outputs all have this range of possibilities, and the last= will be constrained by the others. So, the 10^92 possibilies will land som= ewhere within a 9-dimensional grid that cointains (10^8)^9=3D10^72 possible= distinct sites, one site which is our actual output list. Since we are stu= ffing 10^92 possibilties into a grid that contains only 10^72 sites, then t= his means on average, each site will have 10^20 possibilities. > > Based on the example above, we can see that not only are there a huge num= ber of partitions, but that even with a fast algorithm that could find matc= hing partitions, it would produce around 10^20 possible valid configuration= s. With 10^20 possibilities, there is essentially no linkage. The Cash Fusi= on scheme actually extends this obfuscation even further. Not only can play= ers bring many inputs, they can also have multiple outputs. > > ---------END QUOTE --------- > -- It seems to me that most users will not have nearly the same output of "aro= und 1 BTC" anyway if you deploy this on a real live mainnet, and if your ma= th requires that you have "around 1 BTC" outputs per user. you might as wel= l just use equal-valued CoinJoins, where the equal-valued outputs at least = are completely unlinked from the inputs. Indeed, the change outputs of an equal-valued CoinJoin would have similar a= nalyses to CashFusion, since the same analysis "around 1 BTC" can be perfor= med with the CoinJoin change outputs "around 0 BTC". * You can always transform a CashFusion transaction whose outputs are "arou= nd 1 BTC" to a CoinJoin transaction with equal-valued outputs and some chan= ge outputs, with the equal-valued outputs having equal value to the smalles= t CashFusion output. * e.g. if you have a CashFusion transaction with outputs 1.0, 1.1, 0.99, y= ou could transform that to a CoinJoin with 0.99, 0.99, 0.99, 0.01, 0.11 out= puts. * Conversely, you can transform an equal-valued CoinJoin transaction to a C= ashFusion transaction using the same technique. * That implies that the change outputs of an equal-valued CoinJoin have the= same linkability as the outputs of the equivalent CashFusion transaction. * At least with equal-valued CoinJoin, the equal-valued outputs have 0 link= ability with inputs (at least with only that transaction in isolation). The same cannot be said of CashFusion, because the value involved is just= in a single UTXO. Regards, ZmnSCPxj