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 CC1FCC0175 for ; Fri, 24 Apr 2020 01:34:58 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by hemlock.osuosl.org (Postfix) with ESMTP id C52A9886E5 for ; Fri, 24 Apr 2020 01:34:58 +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 Bb58A5tWziZx for ; Fri, 24 Apr 2020 01:34:57 +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 D5E40886E4 for ; Fri, 24 Apr 2020 01:34:56 +0000 (UTC) Date: Fri, 24 Apr 2020 01:34:51 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com; s=protonmail; t=1587692092; bh=1aC+x6i9QXXorH2C0ylQvec0hM9/qW2IwT61Q7bVVU0=; h=Date:To:From:Cc:Reply-To:Subject:In-Reply-To:References:From; b=ML7CfIfx+8UyW9KXPWoEZcMxqb1MzPtoOIhGqZFBRqqwosf3QdV9Jo5IabEJK7EQ4 /n0+Cyc9N7QT5AC/TOF9+Xw8Si1vwgwYQ5qbLAsIM9PnbWCEks1Ge8B31Aqc3PLzy2 bvcot7c1Z841jM5xdI5T+h11vS6uIvSmrQnPIf1A= To: German Luna From: ZmnSCPxj Reply-To: ZmnSCPxj Message-ID: <-_xRcjb8H_0Bck71k4VkeukEBgHT-03ikLTIdyTG2P0rt0T_mvN4b4FejmWobwnAUCGNaDpFQlPc3TMwlml1gjnZ1lwSumeEYQpXSyijND0=@protonmail.com> In-Reply-To: References: 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, 24 Apr 2020 01:34:59 -0000 Good morning Germ=C3=A1n, > With regards to trying to tackle the problem of value-based correlations,= wouldn't it be possible to try to model the solution after the equal-sum-s= ubset problem (np complete problem)( https://www.cs.mcgill.ca/~lyepre/pdf/a= ssignment2-solutions/subsetSumNPCompleteness.pdf=C2=A0 )?=C2=A0 > That is, a pair of individuals with a set of UTXOs that both add up to si= milar if not equal value perform a swap of similar-(total)value sets. In th= is way the values of the UTXOs can be broken up essentially at random (foll= owing some nominal distribution so that it doesn't stand out; e.g.=C2=A0htt= ps://en.wikipedia.org/wiki/Benford%27s_law), but swapped=C2=A0in conjunctio= n and decorrelated by using different keys=C2=A0+ randomized locktimes. There are a number of issues to simply modeling this to the subset-sum prob= lem. * There is a practical limit to the number of UTXOs you would be willing to= receive in the swap. * Every UTXO you receive increases the potential fee you have to pay to s= pend them, meaning you would strongly dislike receiving 100 UTXOs that sum = up to 1mBTC. * Thus, a practical blockchain analyst can bound the size of the sets inv= olved, and the problem becomes less than NP in practice. * If you have a single UTXO and split it, then swap, anyone looking at the = history can conjecture that the split involved is part of a CoinSwap. * The split is now a hint on how the subset sums can be tried. * If after the CoinSwap you spend the UTXOs you received in a single transa= ction, then you just published the solution to the subset sum for your adve= rsary. * This ties in even further to the "practical limit on the number of UTXO= s". * Because it is not safe to spend the UTXOs from a single CoinSwap toge= ther, you want to have fewer, larger UTXOs for more flexibility in spending= later. I believe belcher and waxwing and nopara73 have been working far longer on = privacy tech, and you should try to get in contact with them as well, they = may know of other issues (or solutions to the above problems). Regards, ZmnSCPxj