From: Jonas Nick <jonasdnick@gmail.com>
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
Subject: Re: [bitcoin-dev] Design for a CoinSwap implementation for
 massively improving Bitcoin privacy and fungibility
Precedence: list

> [...] 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
>