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 B836EC016E for ; Fri, 19 Jun 2020 15:31:29 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by silver.osuosl.org (Postfix) with ESMTP id A65A62052C for ; Fri, 19 Jun 2020 15:31: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 lV0ioU5uvh27 for ; Fri, 19 Jun 2020 15:31:24 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mail-ed1-f49.google.com (mail-ed1-f49.google.com [209.85.208.49]) by silver.osuosl.org (Postfix) with ESMTPS id 0756F2052B for ; Fri, 19 Jun 2020 15:31:24 +0000 (UTC) Received: by mail-ed1-f49.google.com with SMTP id m21so7894541eds.13 for ; Fri, 19 Jun 2020 08:31:23 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:subject:to:references:autocrypt:message-id:date:user-agent :mime-version:in-reply-to:content-language:content-transfer-encoding; bh=KkJXxYr+fhFrAdwwpkr8gpRbIwKhHB6FgHH6gVEt9U8=; b=g+9zFF2A2K/21TDqhznjmIuSkTydA5t7UlWsOwebZIn9UStEbA6df0voU5Id/0WQIi hhpjKCTa5emvrp4Dz2N14GR8HsECI1Vp9kuY3yb/0uysG5ms5uIbNpldjdS/RHN7MxdC CgJ2a4pMZLweXiHNyRMjIwRt1lo1EUKdu4iYxjpoautlW3X9waCahE8eIAAWrOqalpPp mI2pv+VLN3zy0c5/H9Lq+kp+v2ETLBaCkcQgEqL4at6pjQbWLKtNS1xXT5Hu5311WCeK j/xCQlVSlQRL3Wk41ousIux5fiDAQ8kZrYgjLPRRlzupPfvSCXPiw3uRJjd9/zqFW5sS iHNQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:subject:to:references:autocrypt:message-id :date:user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=KkJXxYr+fhFrAdwwpkr8gpRbIwKhHB6FgHH6gVEt9U8=; b=QGST8nqE46EvbhEuU0kRc/I8Lu4KbKmXxJ/J32V+VZbVEwkdh8k7uPgojd1wvQR2pZ S5b8tEH84kkCIpHkA4uPfZi8VPTTAUTqnoYGGRu2BUX5VWF0YT+WCiyGsm0P6qLEA/96 cuoDD1LvaxgzTTxozuddTdPHi37yU+DWX6YIIgScy6rrsCE59vz1JXH/UXwHVMO85oyb jZ7mFG3+5frrucM3I5UL+JOJwEi6yCsRkVEvoEx77cK1Fhg5lgvFUfT9CMBKTt3/D5vS Pc8lx4bUN7vuqe/1SoWU9n/yWi599MmiN91XUCk3mpB19+Ty3AYNHY8Fcjk/NxjdrEhx D89g== X-Gm-Message-State: AOAM5304CmuG003rOSQv+TWaeH8ph650UlpjLhXtcENhZKVTbPHCh6Rd M3j0h4OUcnSNc7M/VykE2ASJUuxNes0= X-Google-Smtp-Source: ABdhPJw7OAnNfkXxLAdL3ftUFpgly1GdtXdInFJ7DitamJh48rBE51mdk9Amm9EgHOgYW2fIAu7Bmw== X-Received: by 2002:aa7:d0c5:: with SMTP id u5mr3809046edo.51.1592580681226; Fri, 19 Jun 2020 08:31:21 -0700 (PDT) Received: from [10.12.10.3] ([185.107.95.212]) by smtp.googlemail.com with ESMTPSA id n35sm5194428edc.11.2020.06.19.08.31.19 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 19 Jun 2020 08:31:20 -0700 (PDT) From: Jonas Nick X-Google-Original-From: Jonas Nick To: bitcoin-dev@lists.linuxfoundation.org References: <82d90d57-ad07-fc7d-4aca-2b227ac2068d@riseup.net> Autocrypt: addr=jonasd.nick@gmail.com; prefer-encrypt=mutual; keydata= mQINBFQ2o3oBEACv5N5WajlYk+i/4B8FmniipCB4biIKg38spMNt1EYM6RzTu+hbOrVOlJW8 fq/ih+dvlpreGxRPQlX4jr75kwoJCykd3geywTUl3KPLeJ/JRQJ8fVkine4Wr5qB5Jwo3+wt inDVooaaF32Y0HolNacXVzT1x9uwn83Bz/ifg+iGATn/e1Si3ga/ytY5wYDzFz6aUDRW8ulu DcG8ARMAgtzmi66EuyQyIWwSyoWFU8wJ98slU9LKuTu23r6HdxFuV+P2H1omJm+z8cd4QBMj I23uHst0Wx1MyTeVhZCnQAghyasA3oopwzqRf5wwECAui1oZhr59R4R1DHJjn0PeWZXBSnOo XPQ1ERjz4nQrODiIDEabD5DClPHZ1bte0tswm1aYBtD8/me9ck+SJdoH5r0DJrXCTtNl1XG1 9TTUINQe0eaQUOTakZmVaneCeSrw/pKOknkzudOCNCbmngKa2oJQOynrdsBuoigIYY+NQdot fk1nJljrBzyTh4sFktbHyA24x/hCykMX6FnIQxDnsGR+S3I+vzADBLBBMQQtZsUA+xnvPu4l 6You5SZMVhgprQy38bKybeIGxSZtmPNtBf8ouKhAUpbIfOaq6BoP4EtueXk/vyieFxXiIkbF N6b3pjhkG7wVG17HqCqeVeHz1ZAQJUPcqDQAPaelBf38RXPbeQARAQABtCJKb25hcyBOaWNr IDxqb25hc2Qubmlja0BnbWFpbC5jb20+iQI/BBMBAgApAhsDBwsJCAcDAgEGFQgCCQoLBBYC AwECHgECF4AFAlu1I0QFCQtA5soACgkQsacOT43NA2Y5zA/9G1kt1ECa6zPhpEBV5iqD1omt ABdrZSxD8gBsZOMt2nLE1f4J0Oqy9LfMzKFzC8Kyd7usu6HVA8XM3fjVgqi+cDlEhaE+RqFi FVJjai7Fo1EqQGoD8QKTHDpGMNAmkfiQI7yc7OOxJ7X/nRpI8EnUsHG0slw3ieG6krrwLMfi rdJz5xA3P0tjdz/gRsG1IkwaB1bWnrIyh4oS9MiTSO1GZzHdRrhYZPFnJa7XiQsDWTvtTf4o fkbDAxqsKSqJhh99Gl79dXjJ1X9c6YfmxdOWuHZwtpJRgTFXSavaojkjPdnx4/f8lsgQg0tI BEaZnfroAvJCkYCqxNAPS5pSCaRaZbm+eoBl9848eFQztds/xfG3xIpn6VaOSdDNCD0+kSiO LrqghKLN3nPWOfCU0zPlkFuNsWX0ALvAJj6UKGbvMRfR6uj5NPZuHbA2FK9/1pOfKLjm6bHI 2HtXeS5B0+eoAjHzoF9w/2DM4+DLU8Qbn63CpDZ3dodqK3Z7PHLv9oiiCVUFxia0J9YUZJru 1jFHc3BA/Ado4LSxjyUbG0kDQjddvBEmQIkW5c2VrkczYv8gCOLwiUF+RPqc8PxGRs5I5SqJ RzcEN9nIaFcP5MTPrabbkXKLw6ZhHqc3J85qMOLoxThP5SCWM7I1SwLYIGgcWGFtL27U9IXe /wzNH4aerKe5Ag0EWVExqgEQAL1iVOraDIRX7bI1bres6PsbkNwz56OqIRbfSACch82x4NAK Jd9Gdabhv7mjX9bUGBwH79YUjpxOo2nh8Sp48SYThe9lWOmU6wo2T1ZyzuhoQp8jRtcll59Q o2zbfQdWt8DdRhCNzma/qjhDaAOveKa13jtXasVVqR4UdK2ZG/nIRQhPDslYq+hutV/7kTrd sk12GETBOrUQDh5WLbG5AbKGK/CQ3kXZWvyhSVD2I20ze18qsMrL88shgx+Tf0S9H+snQNQi WsB8DVe/VQj7nfam+LTVoIWpYOgTW+Y7/bU+UylMyFNUlFBykAguSCZ1JTSCxM2W9Q6zOf8u v9N+ht5TpTPiXvbx4mTA9UWu4Mksa7deqwy59MViuqRgBQwcH6WYgT202PYbMQzpxQSPBO4v N7e/ScVpAlfTT52ygwURb89+A4LQzF0tKWsRC5ZON5FfVbLg1NMplECOr1gPpruUNlbNbLOY nVd6nu1j/vLKvYiQL/BzoHJ4X5EvRm7BhktgdCuE5ce7eaNUGZKd9kUHNqhznKV+PeYCI78E ARAYNORbD09V+40wBtv5+VYPv9XMBBVYqofMOFIPbt0pT4ssbhH8UMnQcZbrtzOPxE6405Hy pT3gA85CSSpZXm3ziFdKodNyaYtb+eHwIGUQaC3pl3AdP8IpgVQL8K8CYNNhABEBAAGJBHIE GAEIACYWIQQ2xxo3ydmIveglCNmxpw5Pjc0DZgIbAgUCXRpChwUJBapEXQJAwXQgBBkBCAAd FiEES7uEWm9aZaad+uwjSGHb8mISNgUFAllRMaoACgkQSGHb8mISNgUtRg//aeCXBTyQ4mp/ 3szzL9qmK9zDwPtfUpEro98R/ekBTCYnnxEEv2g2Y8OTLcPc1iL2JWY4kfObBUZW6M78+qcz EF/GNTBkOVgczTWroN7U8j4IcXpcuqjwMtlL76EzGmI1DAa6UcOr/lAtOsOZrcxN19kGtBbo njU6PeZrzTqMujxCSoR5tt4gdMk204d6+5BmJXcB6usr85L4DDAXGmrUXRycmXMgZT1+8yzm hIEcpEB6yctoqRQgwF0nGCquJrxumtpMg1PnRvh9bJa1v+KmKfCNJptXPJh5zmp4tVzB6W0S dkKxEloiy7K/UDOVeOtdhI2FcoujC/gRjbTU0UTSW0MPuM4I+Z+lfPCZzwlYWLAgybfIL9FK d5hVF1Xcz7Hommqdx0vN3TYnoAIbxDV+gqkzVVHRPLk6BAK7Nwl64BiTx9wZYAKwf4jXl632 JDxFH8yrNfnnTwYOmaHgsxGWx6WePVuvQDvWGisVqMy3uvNm8+4/8hMqI1FjTtBLfM4RkMTE bIzJnqg/iPduzIKf9PIxR8wnYr1j8WJxq6dGuMzRI332UmWFORkgbs+SZnZ2Zwex0aaeQhZP 1/ZvwnjUvdVtxm96hAUZWeN13W6plEF14m7TYzkCfheWEAEtnSKhyLx+zgleXjlFnMnCMPBj PvbU/xJxYukdg2Dtcv0CoBoJELGnDk+NzQNm4F0QAKK/tTaWwfnI5mvdAd1vIbeR2LCzNau7 Q1+oDW+GHInAlq7jhdDe/gQYrRnuyIvdV/4xQMPs5XN/HNdF0ejyo5rAPY/EihpiiKoOdkwa 7lnzdt9TakBLhoSDThjKGTfMhwiXmTp2a107fisjmzhynwn/UU2amrZU0E22mSkR/VpqaLlw B3/vhwQKUUgm6oKAQWlLFqP63mJr/s/TfL0qdS8Oe8IMNXI8Qb7lTgpTd6QHkiUWVKLGZqPk BXXyWnTZNt/IvHgO73iox5cVEO31SRyyNmZ9mPoGacVUpuEfZK83USioHhv9lpEB/lDcbzaO FOHW8Bnd0dSpV3KDM+a2Axa1qp9DQ5l1wr7Zew0vH7Ua/NRECWIZ6Kmk+9ESfQ+N5zCGuUQh gmLq7Q307NA0127lh38ishw0bmopVugBxzxOjLS+DdwwcHVzUQswAuccHiukVuyWzh/dvH4W mf+z8dG0iyh9c474jHt3kcouuo9cUv+oD8bup7HUpKWGkaBSCqtjKqDEf1ldOQrJaoHOmikH jhTkneKwpx6GWlPMHf6fT+irDS4M5Hd2N+fR1G82FiubTOLZnC2IfpgSYf2MTwuxjYDNJ44N gh9qScMcKl9ZWrxvdMInNKwd4XvDhSDC2WdqzDLa+9a+Z5wQrBFHXH3XLf3SKrQ9TVJuKp1x 63owuQINBFlRMd4BEADB+3Vb1kfonWBHtzlQ2P0lVfNMI3zntc0w0zkPqgfA+RYp/O790abf MtEcVt2OBW5Y6Iut+Y4SaN/zKEx72UnrOtS25z81I0XmJiKjGKayeR0hfiJLJFvROT9O/Bus CNoccI0V14OMvmfqGJNwvBgR9RI47Not5ZmCDwAjFCg22tumSLsZIyuTgd7WR5kzrmESfXj+ SpbUg+D+mOmU4A5b1KUHiWtMOdgOHTkAEZsig4hiec/sfIEngityK2Fsre/Xrd+uEUlmRuKR Y9+H5xyHBz3m8DjF+oDGXTyMijcWk8AOtoJ0KeZaCaCSVE7IEk0jltQ87448Zv+IljNh5Uuj U9H/NH0sNRp3yMUkj68dheCMIPHJAFs8vxGHBq+/qRydvAFVTeKtBBv/Vr07C/YjPWam8PXC PX2g0w7iX2LXMSKKzIJJgxeLteBhXc0rMeZaEzvv+1RWYRQyywgtXhwszry4xxYPvV6UdDe3 gK6Q4mAVjxVgVbYR7W+ibl6gFsmftC2WcNiRjOP4M1HRa/tRc5yV9TKrZcLawIIDOMaz5ZyH +KsC+gdO+La9NL86+GCM5dBVBrYvUMfsaM6njtjZipbV5nwWHwSWXZ32p1R6fFzA0vs+wlSg szJJp7sidEK2NIyVQMTr5cC0Mt+tzZOaUaa6x52tkdvmbE6n/AsN3QARAQABiQI8BBgBCAAm FiEENscaN8nZiL3oJQjZsacOT43NA2YCGwwFAl0aQqQFCQWqREYACgkQsacOT43NA2aG8RAA hrZkJS+kWwooSueh67hafKciCidlycZNixxtks8kwnYMCWF7z11EyRdqAGqIHr0zVuAnmVNO 8wr+b/x/pgR0XpjzdfCJ3inNh3GLwwD+CRafkq8U3Xd+xvFQTBeFMsC+h8A45MNhBsL7IAWq 7wkSb9dyqGKVhb4Wac0aYEbSGMu/P5BFkLw1li3E61ik7yh/x46s5FaddwbwF0P51S3fVQE+ 1Iu86LlrLTgkLkZxbK8cm1XxBirRxwIInf+RU/xQOl62V5L/ySiJHRGjSg89WXgpiLzjR1gf zFM8zEv4R1sE+nIw5GsaKxXUAxMyGZ6K1EFp31crZBnbZ0fhFqiyHphhH4zeF+nR/PZgsHtB Efd2obbJ15uG7oHUBg1xnx6CVzKoH6k6HLlkpiw6TP+KvvLCZ9sGrxfjeJm/PBXOVEC+HUH8 Ha3u4A2Je0YWHs361qz3PBnzgzAva0fRJFv0GvOEgGMj7GTOgWn1crWiUSCoNchwiH5ajVBV 7FcWq3e7Dgp1q56j6igE4rRBsPPA1/iCU9mB6vvI1ieMVKXfzBtiL/DYn6ytpBf+gO5nxDLf 2bOtlx4htC2wGl90Pp/8/+mWBCWFvJMnBCld+G2b4Fv+g9Mr/7tlxBdomevSI7qXcOUJ4v0x Fp3434+dc5TFz4zcLJtqhMF1McajtWw02z8= Message-ID: <5cdc9a4a-6382-6b1f-fb34-58fa3f5eece0@gmail.com> Date: Fri, 19 Jun 2020 15:33:09 +0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.9.0 MIME-Version: 1.0 In-Reply-To: <82d90d57-ad07-fc7d-4aca-2b227ac2068d@riseup.net> Content-Type: text/plain; charset=utf-8 Content-Language: en-US-large Content-Transfer-Encoding: 7bit X-Mailman-Approved-At: Fri, 19 Jun 2020 15:44:03 +0000 Subject: Re: [bitcoin-dev] Design for a CoinSwap implementation for massively improving Bitcoin privacy and fungibility 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, 19 Jun 2020 15:31:29 -0000 > [...] we can use 2-party ECDSA to create 2-of-2 multisignature addresses that > look the same as regular single-signature addresses[2]. Even the old-style > p2pkh addresses starting with 1 can be CoinSwap addresses. Probably worth considering that p2pkh, p2wpkh and p2sh are vulnerable to the (well-known) birthday attack with 2^80 operations on average if they encode a multisig policy [0]. This is a large number but not the security margin we are used to. It is possible to reduce the feasibility of the attack by requiring 2^80 interactions instead of purely offline operations. This works by adding a commitment round for all public keys involved in the policy. Now in order to test whether a public key results in a collision, the attacker must first engage in a commitment protocol with that public key. The "Fast Secure Two-Party ECDSA Signing" protocol by Lindell [1] already has such a commitment round (for reasons unrelated to Bitcoin). For example, the Gotham City two-party ECDSA wallet [2] has this security model because it builds on the Lindell scheme and uses p2sh-p2wpkh. [0] https://bitcoin.stackexchange.com/questions/54841/birthday-attack-on-p2sh [1] https://eprint.iacr.org/2017/552.pdf [2] https://github.com/KZen-networks/gotham-city On 5/25/20 1:21 PM, Chris Belcher via bitcoin-dev wrote: > === Abstract === > > Imagine a future where a user Alice has bitcoins and wants to send them > with maximal privacy, so she creates a special kind of transaction. For > anyone looking at the blockchain her transaction appears completely > normal with her coins seemingly going from address A to address B. But > in reality her coins end up in address Z which is entirely unconnected > to either A or B. > > Now imagine another user, Carol, who isn't too bothered by privacy and > sends her bitcoin using a regular wallet which exists today. But because > Carol's transaction looks exactly the same as Alice's, anybody analyzing > the blockchain must now deal with the possibility that Carol's > transaction actually sent her coins to a totally unconnected address. So > Carol's privacy is improved even though she didn't change her behaviour, > and perhaps had never even heard of this software. > > In a world where advertisers, social media and other companies want to > collect all of Alice's and Carol's data, such privacy improvement would > be incredibly valuable. And also the doubt added to every transaction > would greatly boost the fungibility of bitcoin and so make it a better > form of money. > > This undetectable privacy can be developed today by implementing > CoinSwap, although by itself that isn't enough. There must be many > building blocks which together make a good system. The software could be > standalone as a kind of bitcoin mixing app, but it could also be a > library that existing wallets can implement allowing their users to send > Bitcoin transactions with much greater privacy. > > == CoinSwap == > > Like CoinJoin, CoinSwap was invented in 2013 by Greg Maxwell[1]. Unlike > CoinJoin it is relatively complicated to implement and so far has not > been deployed. But the idea holds great promise, and fixes many of the > problems of some kinds of CoinJoins. CoinSwap is the next step for > on-chain bitcoin privacy. > > CoinSwap is a way of trading one coin for another coin in a > non-custodial way. It is closely related to the idea of an atomic swap. > Alice and Bob can trade coins with each other by first sending to a > CoinSwap address and having those coins then sent to Bob: > > Alice's Address 1 ----> CoinSwap Address 1 ----> Bob's Address 1 > > An entirely separate set of transactions gives Bob's coins to Alice in > return: > > Bob's Address 2 ----> CoinSwap Address 2 ----> Alice's Address 2 > > Where the symbol ----> is a bitcoin transaction. > > Privacy is improved because an observer of the blockchain cannot link > Alice's Address 1 to Alice's Address 2, as there is no transaction > between them. Alice's Address 2 could either be an address in Alice's > wallet, or the address of someone else she wants to transfer money to. > CoinSwap therefore breaks the transaction graph heuristic, which is the > assumption that if a transaction A -> B is seen then the ownership of > funds actually went from A to B. > > CoinSwap doesnt break any of bitcoin's assumptions or features like an > auditable supply or pruning. It can be built on today's bitcoin without > any new soft forks. > > CoinSwap can't improve privacy much on its own, so it requires other > building block to create a truly private system. > > === ECDSA-2P === > > The original CoinSwap idea uses 2-of-2 multisig. We can get a slightly > bigger anonymity set by using 2-of-3 multisigs with a fake third public > key. For a much greater anonymity set we can use 2-party ECDSA to create > 2-of-2 multisignature addresses that look the same as regular > single-signature addresses[2]. Even the old-style p2pkh addresses > starting with 1 can be CoinSwap addresses. > > Because the transactions blend in with the rest of bitcoin, an > application based on CoinSwap would provide much more privacy than the > existing equal-output coinjoin apps (JoinMarket, Wasabi Wallet and > Samourai Wallet's Whirlpool). CoinSwaps would also be cheaper for the > same amount of privacy, as CoinJoin users usually create multiple > CoinJoins to get effective privacy, for example JoinMarket's tumbler > script does between 7-12 coinjoins (which are bigger than regular > transactions too) when run with default parameters. > > Schnorr signatures with Musig provide a much easier way to create > invisible 2-of-2 multisig, but it is not as suitable for CoinSwap. This > is because the anonymity set for ECDSA would be much greater. All > addresses today are ECDSA, and none are schnorr. We'd have to wait for > schnorr to be added to bitcoin and then wait for users to adopt it. We > see with segwit that even after nearly 3 years that segwit adoption is > only about 60%, and segwit actually has a sizeable financial incentive > for adoption via lower fees. Schnorr when used for single-sig doesn't > have such an incentive, as Schnorr single-sig costs the same size as > today's p2wpkh, so we can expect adoption to be even slower. (Of course > there is an incentive for multisig transactions, but most transactions > are single-sig). As schnorr adoption increases this CoinSwap system > could start to use it, but for a long time I suspect it will mostly be > using ECDSA for a greater anonymity set. > > === Liquidity market === > > We can create a liquidity market for CoinSwap very similar to how > JoinMarket works for CoinJoins. In our example above Alice would be a > market taker and Bob would be a market maker. The taker Alice pays a fee > to the maker Bob in return for choosing the amount of a CoinSwap and > when it happens. This allows an excellent user experience because Alice > can create CoinSwaps for any size she wants, at any time she wants. > Right now in JoinMarket there is liquidity to create CoinJoins of sizes > up to about 200 BTC, and we can expect a similar kind of thing with > CoinSwap. > > > === Multi-transaction CoinSwaps to avoid amount correlation === > > This CoinSwap is vulnerable to amount correlation: > > AliceA (15 BTC) ----> CoinSwap AddressA ----> BobA (15 BTC) > BobB (15 BTC) ----> CoinSwap AddressB ----> AliceB (15 BTC) > > Where AliceA, AliceB are addresses belonging to Alice. BobA, BobB are > addresses belonging to Bob. If an adversary starts tracking at address > AliceA they could unmix this CoinSwap easily by searching the entire > blockchain for other transactions with amounts close to 15 BTC, which > would lead them to address AliceB. We can beat this amount correlation > attack by creating multi-transaction CoinSwaps. For example: > > AliceA (15 BTC) ----> CoinSwap AddressA ----> BobA (15 BTC) > > BobB (7 BTC) ----> CoinSwap AddressB ----> AliceB (7 BTC) > BobC (5 BTC) ----> CoinSwap AddressC ----> AliceC (5 BTC) > BobD (3 BTC) ----> CoinSwap AddressD ----> AliceD (3 BTC) > > Now in the multi-transaction CoinSwap, the market taker Alice has given > 10 BTC and got back three transactions which add up to the same amount, > but nowhere on the blockchain is there an output where Alice received > exactly 15 BTC. > > === Routing CoinSwaps to avoid a single points of trust === > > In the original CoinSwap idea there are only two parties Alice and Bob, > so when they CoinSwap Bob will know exactly where the Alice's coins > went. This means Bob is a single point of failure in Alice's privacy, > and Alice must trust him not to spy on her. > > To spread out and decentralize the trust, we can create CoinSwaps where > Alice's payment is routed through many Bobs. > > AliceA ====> Bob ====> Charlie ====> Dennis ====> AliceB > > Where the symbol ====> means one CoinSwap. In this situation Alice will > be a market taker in the liquidity market, and all the other entities > (Bob, Charlie, Dennis) will be market makers. Only Alice will know the > entire route, and the makers will only know the previous and next > bitcoin addresses along the route. > > This could be made to work by Alice handling almost everything about the > CoinSwap on the other maker's behalf. The makers wouldn't have TCP > connections between each other, but only to Alice, and she would relay > CoinSwap-relevant information between them. The other makers are not > aware whether their incoming coins came from Alice herself or the > previous maker in Alice's route. > > > === Combining multi-transaction with routing === > > Routing and multi-transaction must be combined to get both benefits. If > Alice owns multiple UTXOs (of value 6 BTC, 8 BTC and 1 BTC) then this is > easy with this configuration: > > Alice > (6 BTC) (8 BTC) (1 BTC) > | | | > | | | > v v v > Bob > (5 BTC) (5 BTC) (5 BTC) > | | | > | | | > v v v > Charlie > (9 BTC) (5 BTC) (1 BTC) > | | | > | | | > v v v > Dennis > (7 BTC) (4 BTC) (4 BTC) > | | | > | | | > v v v > Alice > > Where the downward arrow symbol is a single CoinSwap hash-time-locked > contract. Each hop uses multiple transactions so no maker (Bob, Charlie, > Dennis) is able to use amount correlation to find addresses not directly > related to them, but at each hop the total value adds up to the same > amount 15 BTC. And all 3 makers must collude in order to track the > source and destination of the bitcoins. > > If Alice starts with only a single UTXO then the above configuration is > still vulnerable to amount correlation. One of the later makers (e.g. > Dennis) knows that the total coinswap amount is 15 BTC, and could search > the blockchain to find Alice's single UTXO. In such a situation Alice > must use a branching configuration: > > Alice > (15 BTC) > | > | > v > Bob > / \ > / \ > <----------- -----------> > | | > (2 BTC) (2 BTC) (2 BTC) (3 BTC) (3 BTC) (3 BTC) > | | > | | > v v > Charlie Dennis > (1 BTC) (2 BTC) (3 BTC) (5 BTC) (3 BTC) (1 BTC) > | | | | | | > | | | | | | > v v v v v v > Edward Fred > (4 BTC) (1 BTC) (1 BTC) (4 BTC) (2 BTC) (1 BTC) > | | | | | | > | | | | | | > v v v v v v > Alice Alice > > In this diagram, Alice sends 15 BTC to Bob via CoinSwap who sends 6 BTC > on to Charlie and the remaining 9 BTC to Dennis. Charlie and Dennis do a > CoinSwap with Edward and Fred who forward the coins to Alice. None of > the makers except Bob know the full 15 BTC amount and so can't search > the blockchain backwards for Alice's initial UTXO. Because of multiple > transactions Bob cannot look forward to search for the amounts he sent 6 > BTC and 9 BTC. A minimum of 3 makers in this example need to collude to > know the source and destination of the coins. > > Another configuration is branch merging, which Alice would find useful > if she has two or more UTXOs for which there must not be evidence that > they're owned by the same entity, and so they must not be spent together > in the same transaction. > > Alice Alice > (9 BTC) (6 BTC) > | | > | | > v v > Bob Charlie > (4 BTC) (3 BTC) (2 BTC) (1 BTC) (2 BTC) (3 BTC) > | | | | | | > | | | | | | > \ \ \ / / / > \ \ \ / / / > \ \ \ / / / > >------->-------\ /-------<-------< > \ / > Alice > (15 BTC) > > In this diagram Alice sends the two UTXOs (9 BTC and 6 BTC) to two > different makers, who forward it onto Alice. Because the two UTXOs have > been transferred to different makers they will likely never be co-spent. > > These complex multi-transaction routed coinswaps are only for the > highest threat models where the makers themselves are adversaries. In > practice most users would probably choose to use just one or two hops. > > > === Breaking change output and wallet fingerprinting heuristics === > > Equal-output CoinJoins easily leak change addresses (unless they are > sweeps with no change). CoinSwap doesn't have this flaw which allows us > to break some of the weaker change output heuristics[3]. > > For example address reuse. If an output address has been reused it is > very likely to be a payment output, not a change output. In a CoinSwap > application we can break this heuristic by having makers randomly with > some probability send their change to an address they've used before. > That will make the heuristics think that the real change address is > actually the payment address, and the real payment is actually the > change, and could result in an analyzer of the blockchain grouping the > payment address inside the maker's own wallet cluster. > > Another great heuristic to break is the script type heuristic. If the > maker's input are all in p2sh-p2wpkh addresses, and their payment > address is also of type p2sh-p2wpkh, then the maker could with some > probability set the change address to a different type such as p2wpkh. > This could trick a chain analyzer in a similar way. > > === Fidelity bonds === > > Anybody can enter the CoinSwap market as a maker, so there is a danger > of sybil attacks. This is when an adversary deploys huge numbers of > maker bots. If the taker Alice chooses maker bots which are all > controlled by the same person then that person can deanonymize Alice's > transaction by tracking the coins along the route. > > A solution to this is fidelity bonds. This is a mechanism where bitcoin > value is deliberately sacrificed to make a cryptographic identity > expensive to obtain. The sacrifice is done in a way that can be proven > to a third party. One way to create a fidelity bond is to lock up > bitcoins in a time-locked address. We can code the taker bots to behave > in a way that creates market pressure for maker bot operators to publish > fidelity bonds. These fidelity bonds can be created anonymously by > anyone who owns bitcoin. > > Fidelity bonds are a genuine sacrifice which can't be faked, they can be > compared to proof-of-work which backs bitcoin mining. Then for a sybil > attacker to be successful they would have to lock up a huge value in > bitcoin for a long time. I've previously analyzed fidelity bonds for > JoinMarket[4], and using realistic numbers I calculate that such a > system would require about 55000 BTC (around 500 million USD at today's > price) to be locked up for 6 months in time-locked addresses. This is a > huge amount and provides strong sybil resistance. > > ==== Who goes first ==== > > Fidelity bonds also solve the "who goes first" problem in CoinSwap. > > This problem happens because either Alice or Bob must broadcast their > funding transaction first, but if the other side halts the protocol then > they can cause Alice or Bob's to waste time and miner fees as they're > forced to use the contract transactions to get their money back. This is > a DOS attack. If a malicious CoinSwapper could keep halting the protocol > they could stop an honest user from doing a CoinSwap indefinitely. > Fidelity bonds solve this by having the fidelity bond holder go second. > If the fidelity bond holder halts the protocol then their fidelity bond > can be avoid by the user in all later CoinSwaps. And the malicious > CoinSwapper could pack the orderbook with their sybils without > sacrificing a lot of value for fidelity bonds. > > As a concrete example, Alice is a taker and Bob is a maker. Bob > publishes a fidelity bond. Alice "goes first" by sending her coins into > a 2-of-2 multisig between her and Bob. When Bob sees the transaction is > confirmed he broadcasts his own transactions into another 2-of-2 > multisig. If Bob is actually malicious and halts the protocol then he > will cost Alice some time and money, but Alice will refuse to ever > CoinSwap with Bob's fidelity bond again. > > If DOS becomes a big problem even with fidelity bonds, then its possible > to have Alice request a "DOS proof" from Bob before broadcasting, which > is a set of data containing transactions, merkle proofs and signatures > which are a contract where Bob promises to broadcast his own transaction > if Alice does so first. If Alice gets DOSed then she can share this DOS > proof publicly. The proof will have enough information to convince > anyone else that the DOS really happened, and it means that nobody else > will ever CoinSwap with Bob's fidelity bond either (or at least assign > some kind of ban score to lower the probability). I doubt it will come > to this so I haven't expanded the idea much, but theres a longer writeup > in the reference[5]. > > === Private key handover === > > The original proposal for CoinSwap involved four transactions. Two to > pay into the multisig addresses and two to pay out. We can do better > than this with private key handover[6]. This is an observation that once > the CoinSwap preimage is revealed, Alice and Bob don't have to sign each > other's multisig spend, instead they could hand over their private key > to the other party. The other party will know both keys of the 2-of-2 > multisig and therefore have unilateral control of the coins. Although > they would still need to watch the chain and respond in case a > hash-time-locked contract transaction is broadcasted. > > As well as saving block space, it also improves privacy because the > coins could stay unspent for a long time, potentially indefinitely. > While in the original coinswap proposal an analyst of the chain would > always see a funding transaction followed closely in time by a > settlement transaction, and this could be used as a fingerprint. > > We can go even further than private key handover using a scheme called > SAS: Succinct Atomic Swap[7]. This scheme uses adapter signatures[8] to > create a similar outcome to CoinSwap-with-private-key-handover, but only > one party in the CoinSwap must watch and respond to blockchain events > until they spend the coin. The other party just gets unilateral control > of their coins without needing to watch and respond. > > > === PayJoin with CoinSwap === > > CoinSwap can be combined with CoinJoin. In original CoinSwap, Alice > might pay into a CoinSwap address with a regular transaction spending > multiple of her own inputs: > > AliceInputA (1 BTC) ----> CoinSwap Address (3 BTC) > AliceInputB (2 BTC) > > This leaks information that all of those inputs are owned by the same > person. We can make this example transaction a CoinJoin by involving > Bob's inputs too. CoinJoin requires interaction but because Alice and > Bob are already interacting to follow the CoinSwap protocol, so it's not > too hard to have them interact a bit more to do a CoinJoin too. The > CoinJoin transaction which funds the CoinSwap address would look like this: > > AliceInputA (1 BTC) ----> CoinSwap Address (7 BTC) > AliceInputB (2 BTC) > BobInputA (4 BTC) > > Alice's and Bob's inputs are both spent in a same transaction, which > breaks the common-input-ownership heuristic. This form of CoinJoin is > most similar to the PayJoin protocol or CoinJoinXT protocol. As with the > rest of this design, this protocol does not have any special patterns > and so is indistinguishable from any regular bitcoin transaction. > > To make this work Bob the maker needs to provide two unrelated UTXOs, > one that is CoinSwapped and the other CoinJoined. > > ==== Using decoy UTXOs to protecting from leaks ==== > > If Bob the maker was just handing out inputs for CoinJoins to any Alice > who asked, then malicious Alice's could constantly poll Bob to learn his > UTXO and then halt the protocol. Malicious Alice could learn all of > Bob's UTXOs and easily unmix future CoinSwaps by watching their future > spends. > > To defend against this attack we have Bob maintain a list of "decoy > UTXOs", which are UTXOs that Bob found by scanning recent blocks. Then > when creating the CoinJoin, Bob doesn't just send his own input but > sends perhaps 50 or 100 other inputs which don't belong to him. For the > protocol to continue Alice must partially-sign many CoinJoin > transactions; one for each of those inputs, and send them back to Bob. > Then Bob can sign the transaction which contains his genuine input and > broadcast it. If Alice is actually a malicious spy she won't learn Bob's > input for sure but will only know 100 other inputs, the majority of > which have nothing to do with Bob. By the time malicious Alice learns > Bob's true UTXO its already too late because its been spent and Alice is > locked into the CoinSwap protocol, requiring time, miner fees and > CoinSwap fees to get out. > > This method of decoy UTXOs has already been written about in the > original PayJoin designs from 2018[9][10]. > > === Creating a communication network using federated message boards === > > Right now JoinMarket uses public IRC networks for communication. This is > subpar for a number of reasons, and we can do better. > > I propose that there be a small number of volunteer-operated HTTP > servers run on Tor hidden services. Their URLs are included in the > CoinSwap software by default. They can be called message board servers. > Makers are also servers run on hidden services, and to advertise > themselves they connect to these message board servers to post the > makers own .onion address. To protect from spam, makers must provide a > fidelity bond before being allowed to write to the HTTP server. > > Takers connect to all these HTTP message boards and download the list of > all known maker .onion addresses. They connect to each maker's onion to > obtain parameters like offered coinswap fee and maximum coinswap size. > This is equivalent to downloading the orderbook on JoinMarket. Once > takers have chosen which makers they'll do a CoinSwap with, they > communicate with those maker again directly through their .onion address > to transmit the data needed to create CoinSwaps. > > These HTTP message board servers can be run quite cheaply, which is > required as they'd be volunteer run. They shouldn't require much > bandwidth or disk space, as they are well-protected from spam with the > fidelity bond requirement. The system can also tolerate temporary > downtimes so the servers don't need to be too reliable either. It's easy > to imagine the volunteers running them on a raspberry pi in their own > home. These message board servers are similar in some ways to the DNS > seeds used by Bitcoin Core to find its first peers on bitcoin's p2p > network. If the volunteers ever lose interest or disappear, then the > community of users could find new volunteer operators and add those URLs > to the default list. > > In order to censor a maker, _all_ the message board servers would have > to co-operate to censor him. If censorship is happening on a large scale > (for example if the message board servers only display sybil makers run > by themselves) then takers could also notice a drop in the total value > of all fidelity bonds. > > > == How are CoinSwap and Lightning Network different? == > > CoinSwap and Lightning Network have many similarities, so it's natural > to ask why are they different, and why do we need a CoinSwap system at > all if we already have Lightning? > > === CoinSwap can be adopted unilaterally and is on-chain === > > Today we see some centralized exchange not supporting so-called > ``privacy altcoins'' because of regulatory compliance concerns. We also > see some exchanges frowning upon or blocking CoinJoin transaction they > detect[11]. (There is some debate over whether the exchanges really > blocked transactions because they were CoinJoin, but the principle > remains that equal-output CoinJoins are inherently visible as such). > It's possible that those exchanges will never adopt Lightning because of > its privacy features. > > Such a refusal would simply not be possible with CoinSwap, because it is > fundamentally an on-chain technology. CoinSwap users pay to bitcoin > addresses, not Lightning invoices. Anybody who accepts bitcoin today > will accept CoinSwap. And because CoinSwap transactions can be made > indistinguishable from regular transactions, it would be very difficult > to even determine whether they got paid via a CoinSwap or not. So > CoinSwap is not a replacement for Lightning, instead it is a replacement > for on-chain privacy technology such as equal-output CoinJoins which are > implemented today in JoinMarket, Wasabi Wallet and Samourai Wallet. > Ideally this design, if implemented, would be possible to include into > the many already-existing bitcoin wallets, and so the CoinSwaps would be > accessible to everyone. > > This feature of CoinSwap will in turn help Lightning Network, because > those censoring exchanges won't be able to stop transactions with > undetectable privacy no matter what they do. When they realize this > they'll likely just implement Lightning Network anyway regardless of the > privacy. > > Bitcoin needs on-chain privacy as well, otherwise the bad privacy can > leak into layer-2 solutions. > > === Different ways of solving liquidity === > > Lightning Network cannot support large payment amounts. Liquidity in > payment channels on the Lightning network is a scarce resource. Nodes > which relay lightning payments always take care that a payment does not > exhaust their liquidity. Users of Lightning today must often be aware of > inbound liquidity, outbound liquidity and channel rebalancing. There > even exist services today which sell Lightning liquidity. > > This CoinSwap design solves its liquidity problem in a completely > different way. Because of the liquidity market similar to JoinMarket, > all the required liquidity is always available. There are never any > concerns about exhausting channel capacity or a route not being found, > because such liquidity is simply purchased from the liquidity market > right before it is used. > > It is still early days for Lightning, and liquidity has been a known > issue since the start. Many people are confident that the liquidity > issue will be improved. Yet it seems hard to imagine that Lightning > Network will ever reliably route payments of 200 BTC to any node in the > network (and it doesn't have to to be successful), yet on JoinMarket > today as I write these words there are offers to create CoinJoins with > amounts up to around 200 BTC. We can expect similar large amounts to be > sendable in CoinSwap. The liquidity market as a solution is known to > work and has been working for years. > > === Sybil resistance === > > CoinSwap can support fidelity bonds and so can be made much more > resistant to sybil attacks. We saw in the earlier section that realistic > numbers from JoinMarket imply a sybil attacker would have to lock up > hundreds of millions of USD worth of bitcoin to successfully deanonymize > users. > > It's difficult to compare this to the cost of a sybil attack in > Lightning network as such attacks are hard to analyze. For example, the > attacker needs to convince users to route payments through the > attacker's own nodes, and maybe they could do this, but putting numbers > on it is hard. Even so it is very likely that the true cost is much less > than 500 million USD locked up for months because Lightning nodes can be > set up for not more than the cost of hardware and payment channel > capacity, while CoinSwap makers would require expensive fidelity bond > sacrifices. > > As this CoinSwap design would cost much more sybil attack, its privacy > would be much greater in this respect. > > > == How are CoinSwap, PayJoin and PaySwap different? == > > PayJoin can also be indistinguishable from regular bitcoin transaction, > so why don't we all just that and not go further? > > The answer is the threat models. PayJoin works by having the customer > and merchant together co-operate to increase both their privacy. It > works if the adversary of both of them is a passive observer of the > blockchain. > > PayJoin doesnt help a customer at all if the user's adversary is the > merchant. This situation happens all the time today, for example > exchanges spying on their customers. CoinSwap can help in this > situation, as it doesn't assume or require that the second party is your > friend. The same argument applies to PaySwap. > > Obviously PayJoin and PaySwap are still very useful, but they operate > under different threat models. > > > == Conclusion == > > CoinSwap is a promising privacy protocol because it breaks the > transaction graph heuristic, but it cant work on its own. In order to > create a truly private system of sending transactions which would > improve bitcoin's fungibility, CoinSwap must be combined with a couple > of other building blocks: > > * ECDSA-2P > * Liquidity market > * Routed CoinSwaps > * Multi-transaction CoinSwaps > * Breaking change output heuristics > * Fidelity bonds > * PayJoin with CoinSwap > * Federated message boards protected from spam with fidelity bonds > > CoinSwap transactions could be made to look just like any other regular > bitcoin transaction, with no distinguishing fingerprint. This would make > them invisible. > > I intend to create this CoinSwap software. It will be almost completely > decentralized and available for all to use for free. The design is > published here for review. If you want to help support development I > accept donations at https://bitcoinprivacy.me/coinswap-donations > > > == References == > > - [1] "CoinSwap: Transaction graph disjoint trustless trading" > https://bitcointalk.org/index.php?topic=321228.0 > > - [2] > http://diyhpl.us/wiki/transcripts/scalingbitcoin/tokyo-2018/scriptless-ecdsa/ > > - [3] https://en.bitcoin.it/wiki/Privacy#Change_address_detection > > - [4] "Design for improving JoinMarket's resistance to sybil attacks > using fidelity bonds" > https://gist.github.com/chris-belcher/18ea0e6acdb885a2bfbdee43dcd6b5af/ > > - [5] https://github.com/AdamISZ/CoinSwapCS/issues/50 > > - [6] https://github.com/AdamISZ/CoinSwapCS/issues/53 > > - [7] > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-May/017846.html > > - [8] > https://github.com/ElementsProject/scriptless-scripts/blob/master/md/atomic-swap.md > > - [9] > https://blockstream.com/2018/08/08/en-improving-privacy-using-pay-to-endpoint/ > > - [10] https://medium.com/@nopara73/pay-to-endpoint-56eb05d3cac6 > > - [11] > https://cointelegraph.com/news/binance-returns-frozen-btc-after-user-promises-not-to-use-coinjoin > > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >