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 217B4C0172 for ; Wed, 29 Apr 2020 07:56:29 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by silver.osuosl.org (Postfix) with ESMTP id 0C91822D55 for ; Wed, 29 Apr 2020 07:56:29 +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 u7xCYKHIyq6d for ; Wed, 29 Apr 2020 07:56:26 +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 F0FCE227E1 for ; Wed, 29 Apr 2020 07:56:25 +0000 (UTC) Date: Wed, 29 Apr 2020 07:56:16 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com; s=protonmail; t=1588146983; bh=5FKj4SkEfCJE2LVizeu/Wdamn7gVkyQhCwIYUqMs6cE=; h=Date:To:From:Reply-To:Subject:In-Reply-To:References:From; b=UwVM0coeh0xYNPpuzdW/lkKiKVgVGKUKwckgXqA8Ut1R4njipYnvAF4rtlar6vOn+ cZVDQZlrTnUNzH+Tih2Nl5QqCMWP40g1xfnYBy+FFjcTRjOP+TPP/8v7qYcTCjSMRd wYtmApUuMwwtgLKsaE03T4rMyL+VotTs7Na921Hg= To: Chris Belcher , Bitcoin Protocol Discussion From: ZmnSCPxj Reply-To: ZmnSCPxj Message-ID: In-Reply-To: <0e1c0287-617c-976c-9fd4-16683881d5d5@riseup.net> 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 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: Wed, 29 Apr 2020 07:56:29 -0000 Good morning CB, I have been thinking about CoinSwap for a good while as well. Here are some very unorganized thoughts. It wold be nice to interoperate with JoinMarket, i.e. have a JoinMarket mak= er that also provides CoinSwap services using the same UTXOs. However, this requires us to retain compatibility with the JoinMarket walle= t structure, which is divided into mixdepths, with the rule that UTXOs in d= ifferent mixdepths cannot be spent together in the same onchain UTXO (to mo= ve across mixdepths you have to do a send, and sending out is always done b= y a single CoinJoin round with multiple makers). I am uncertain what is the best way to handle multitransaction when conside= ring the mixdepth system. My instinct is that if you are doing multitransaction (whether as taker or = maker) then each transaction in the swap *has to* come from a different mix= depth. The issue here is: * If all the UTXOs in the multitransaction swap come from the same mixdepth= , then a surveillor who is monitoring that mixdepth gets a good hint in sol= ving the sparse subset sum problem. * On the other hand, if all the UTXOs in the multitransaction swap come fro= m different mixdepths, then a surveillor who has solved the sparse subset s= um problem now has the hint that the different mixdepths are really owned b= y the same JoinMarket user. I am uncertain which tradeoff is better here, though I am inclined to think= the latter is better. Attempting to completely detach a market-for-CoinSwap from JoinMarket seems= to be impossible to my mind: the protocols are known, implementations open= , and someone will inevitably write code for a single piece of software tha= t can operate as both a JoinMarket maker *and* a maker for a market-for-Coi= nSwap (to increase their market, so to speak), so it might be better to jus= t add CoinSwap to JoinMarket in the first place. > A couple of thoughts on multi-transaction coinswaps: > > - Users should never split up a single UTXO before doing a coinswap, > instead they should send the one UTXO to a coinswap address and get b= ack > multiple UTXOs. > > For example, this 1-to-3 TXO coinswap (The symbol ----> means bitcoin > > > transaction). > > AliceA (10 BTC) ----> CoinSwap AddressA ----> BobA (10 BTC) > > BobB (3 BTC) ----> CoinSwap AddressB ----> AliceB (6 BTC) > > BobC (2 BTC) ----> CoinSwap AddressC ----> AliceC (3 BTC) > > BobD (5 BTC) ----> CoinSwap AddressD ----> AliceD (1 BTC) > > > Note that the Bob-to-Alice set of transactions add up to 10 BTC, the > entire CoinSwap is swapping the same amount. > > Or written another way: > > Alice TXO (10 BTC) ----> Coinswap Protocol ----> Alice TXO1 (6 BTC) > > ----> Alice TXO2 (3 BTC) > > ----> Alice TXO3 (1 BTC) > 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 the change= 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 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. > - It's helpful if any CoinSwap app is actually used for spending rather > than just mixing back to yourself. That will help avoid the problem o= f > users inadvertently co-spending all their coinswap outputs in the sam= e > transaction. > An example of Alice paying for a VPN anonymously: > > Alice TXO (10 BTC) ---> Coinswap Protocol ---> VPN Payment (0.1 BTC) > > ---> Change1 (6 BTC) > > ---> Change2 (3 BTC) > > ---> Change3 (0.9 BTC) > > > > In this case Alice will never accidentally merge all her TXOs together, > because the VPN Payment TXO doesn't belong to her. Also this could > improve privacy because unlike in normal transaction the VPN provider > might not be able to figure out the lower bound of Alice's balance (10 > BTC in this case). This is a good idea, akin to the rule in JoinMarket that all outgoing spend= s are done through a CoinJoin. Of course, if a surveillor ***does*** solve the sparse subset sum, then the= CoinSwap Protocol part looks exactly like a Bitcoin transaction, with a "m= ain" paying output and a "change" output, and the same techniques that work= with current Bitcoin txes work with "CoinSwap Protocol" virtual transactio= ns. It seems to me that, in a system of makers and takers, even if the maker 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, so th= at the maker at least does not differentiate between the case that the take= r 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* ta= rget desired amount, regardless of whether the taker wants to pay a specifi= c value, or the taker wants to just mix its coins. > - Multi-transaction CoinSwaps aren't truly an example of a subset-sum > problem, but "sparse subset sum", a related and easier problem. > > The way its normally formulated, subset sum is about finding a subset > 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 the t= arget. > > 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 where = an > adversary would find a huge amount of false positives which are very > close the amount being sent. So even if the adversary has enough > computational power to iterate all the amounts it won't help them muc= h > 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 standard 1= 00mBTC mixing bin of Wasabi. As well, one could randomly select some existing 1-input 1-output txes in t= he mempool and/or recent blocks, sum them, and swap for the same sum, to fo= rce at least one false positive, but the surveillor could protect against t= his by removing the earliest match (the one it saw in the mempool first, or= onchain). Regards, ZmnSCPxj