[bitcoin-dev] Design for a CoinSwap implementation for massively improving Bitcoin privacy and fungibility

[bitcoin-dev] Design for a CoinSwap implementation for massively improving Bitcoin privacy and fungibility

[Chris Belcher]

=== 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

Re: [bitcoin-dev] Design for a CoinSwap implementation for massively improving Bitcoin privacy and fungibility

[Ruben Somsen]

[-- Attachment #1: Type: text/plain, Size: 35167 bytes --]

Hey Chris,

Excellent write-up. I learned a few new things while reading this
(particularly how to overcome the heuristics for address reuse and address
types), so thank you for that.

I have a few thoughts about how what you wrote relates to Succinct Atomic
Swaps (SAS)[0]. Perhaps it's useful.

>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

This may perhaps be counter-intuitive, but SAS doesn't actually require
multisig for one of the two outputs, so a single key will suffice. ECDSA is
a signing algorithm that doesn't support single key multisig (at least not
without 2p-ECDSA), but notice how for the non-timelocked SAS output we
never actually have to sign anything together with the other party. We swap
one of the two keys, and the final owner will create a signature completely
on their own. No multisig required, which means we can simply use MuSig,
even today without Schnorr.

Of course the other output will still have to be a 2-of-2, for which you
rightly note 2p-ECDSA could be considered. It may also be interesting to
combine a swap with the opening of a Lightning channel. E.g. Alice and Bob
want to open a channel with 1 BTC each, but Alice funds it in her entirety
with 2 BTC, and Bob gives 1 BTC to Alice in a swap. This makes it difficult
to tell Bob entered the Lightning Network, especially if the channel is
opened in a state that isn't perfectly balanced. And Alice will gain an
uncorrelated single key output.

As a side note, we could use the same MuSig observation on 2-of-2 outputs
that need multisig by turning the script into (A & B) OR MuSig(A,B), which
would shave off quite a few bytes by allowing single sig spending once the
private key is handed over, but this would also make the output stick out
like a sore thumb... Only useful if privacy is not a concern.

>=== Multi-transaction CoinSwaps to avoid amount correlation ===

This can apply cleanly to SAS, and can even be done without passing on any
extra secrets by generating a sharedSecret (Diffie-Hellman key exchange).

Non-timelocked:
CoinSwap AddressB = aliceSecret + bobSecret
CoinSwap AddressC = aliceSecret + bobSecret + hash(sharedSecret,0)*G
CoinSwap AddressD  = aliceSecret + bobSecret + hash(sharedSecret,1)*G

The above is MuSig compatible (single key outputs), there are no timelocks
to worry about, and the addresses cannot be linked on-chain.

>they would still need to watch the chain and respond in case a
hash-time-locked contract transaction is broadcasted

Small detail, but it should be noted that this would require the atomic
swap to be set up in a specific way with relative timelocks.

>=== PayJoin with CoinSwap ===

While it's probably clear how to do it on the timelocked side of SAS, I
believe PayJoin can also be applied to the non-timelocked side. This does
require adding a transaction that undoes the PayJoin in case the swap gets
aborted, which means MuSig can't be used. Everything else stays the same:
only one tx if successful, and no timelock (= instant settlement). I can
explain it in detail, if it happens to catch your interest.

Cheers,
Ruben


[0]  Succinct Atomic Swaps (SAS)
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-May/017846.html

On Mon, May 25, 2020 at 3:21 PM Chris Belcher via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> 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
>

[-- Attachment #2: Type: text/html, Size: 41181 bytes --]

Re: [bitcoin-dev] Design for a CoinSwap implementation for massively improving Bitcoin privacy and fungibility

[ZmnSCPxj]

Good morning Ruben and Chris,

> >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
>
> This may perhaps be counter-intuitive, but SAS doesn't actually require multisig for one of the two outputs, so a single key will suffice. ECDSA is a signing algorithm that doesn't support single key multisig (at least not without 2p-ECDSA), but notice how for the non-timelocked SAS output we never actually have to sign anything together with the other party. We swap one of the two keys, and the final owner will create a signature completely on their own. No multisig required, which means we can simply use MuSig, even today without Schnorr.

Just to be clear, you mean we can use the MuSig key-combination protocol for the non-timelocked SAS output, but (of course) not the signing protocol which is inherently Schnorr.

Then knowledge of both of the original private keys is enough to derive the single combined private key.

> Of course the other output will still have to be a 2-of-2, for which you rightly note 2p-ECDSA could be considered. It may also be interesting to combine a swap with the opening of a Lightning channel. E.g. Alice and Bob want to open a channel with 1 BTC each, but Alice funds it in her entirety with 2 BTC, and Bob gives 1 BTC to Alice in a swap. This makes it difficult to tell Bob entered the Lightning Network, especially if the channel is opened in a state that isn't perfectly balanced. And Alice will gain an uncorrelated single key output.

Dual-funding could be done by a single-funding Lightning open followed by an onchain-to-offchain swap.
Though the onchain swap would have to be done, at least currently, with hashes.

> >=== PayJoin with CoinSwap ===
>
> While it's probably clear how to do it on the timelocked side of SAS, I believe PayJoin can also be applied to the non-timelocked side. This does require adding a transaction that undoes the PayJoin in case the swap gets aborted, which means MuSig can't be used. Everything else stays the same: only one tx if successful, and no timelock (= instant settlement). I can explain it in detail, if it happens to catch your interest.

I am not in fact convinced that PayJoin-with-CoinSwap adds *that* much privacy.

These transactions:

             +---+  +---+
    Alice ---|   |--|   |--- Bob
    Alice ---|   |  |   |
      Bob ---|   |  +---+
             +---+

Are not really much different in coin ownership analysis from these:

             +---+    +---+
    Alice ---|   |----|   |--- Bob
    Alice ---|   | +--|   |
             +---+ |  +---+
      Bob ---------+

The latter is possible due to private key handover, the intermediate output becomes owned solely by Bob and Bob can add many more inputs to that second transaction unilaterally for even greater confusion to chain analysis, basically private key handover gets us PayJoin for free.
It also removes the need for Bob to reveal additional UTXOs to Alice during the swap protocol; yes PoDLE mitigates the privacy probing attack that Alice can mount on Bob, but it is helpful to remember this is "only" a mitigation.

Now of course things are different if Alice is paying some exact amount to Carol, and Alice wants to dissociate her funds from the payment.
The difference is then:

             +---+    +---+
    Alice ---|   |----|   |--- Bob
    Alice ---|   |--+ |   |
      Bob ---|   |  | +---+
             +---+  +--------- Alice Change

             +---+    +---+
      Bob ---|   |----|   |--- Carol
             |   |--+ +---+
             +---+  |
                    +--------- Bob Change

Versus:

             +---+    +---+
    Alice ---|   |----|   |--- Bob
    Alice ---|   | +--|   |
             +---+ |  +---+
      Bob ---------+

             +---+    +---+
      Bob ---|   |----|   |--- Carol
             |   |--+ |   |--- Alice Change
             +---+  | +---+
                    +--------- Bob Change

In the above, with PayJoin on the first-layer transaction, the Alice Change is correlated with Alice and Bob inputs, whereas with the PayJoin on the second the Alice change is correlated with Bob inputs and Carol outputs.

But if Alice, using commodity CoinSwap wallets, always has a policy that all sends are via CoinSwap (a reasonable policy, similar to the policy in JoinMarket of ensuring that all spends out of the wallet are via CoinJoin), then the above two trees are not much different for Alice in practice.
The Alice Change will be swapped with some other maker anyway when it gets spent, so what it correlates with will not be much of a problem for Alice.
At the same time, with PayJoin on the second-layer transaction (possible due to private key turnover, which is an inherent part of the SAS protocol):

* Bob does not have to reveal any other coins it owns to Alice other than what it is directly swapping, removing a privacy probe vector.
* Bob can unilaterally combine more than one input to the second transaction going to Bob, which further increases the uncertainty of clustering around the inputs from Alice than just adding *one* input.

---

A thing I have been trying to work out is whether SAS can be done with more than one participant, like in [S6](https://joinmarket.me/blog/blog/multiparty-s6/).

So far, I have not figured out a way to make it multiparty (multihop?).
Because the secret being transported is a private key that protects a specific UTXO, it seems it is not possible to safely use the same secret across more than two parties.
Perhaps others have come ideas?

Regards,
ZmnSCPxj

Re: [bitcoin-dev] Design for a CoinSwap implementation for massively improving Bitcoin privacy and fungibility

[Ruben Somsen]

[-- Attachment #1: Type: text/plain, Size: 7418 bytes --]

Hi ZmnSCPxj,

>Just to be clear, you mean we can use the MuSig key-combination protocol
for the non-timelocked SAS output, but (of course) not the signing protocol
which is inherently Schnorr. Then knowledge of both of the original private
keys is enough to derive the single combined private key.

That's correct.

>basically private key handover gets us PayJoin for free

That assumes there will be a second transaction. With SAS I believe we can
avoid that, and make it look like this:

             +---+
    Alice ---|   |--- Bob
    Alice ---|   |
      Bob ---|   |
             +---+

This is basically what I was trying to explain in my previous email: "I
believe PayJoin can also be applied to the non-timelocked side. This does
require adding a transaction that undoes the PayJoin in case the swap gets
aborted, which means MuSig can't be used. Everything else stays the same:
only one tx if successful, and no timelock (= instant settlement)"

I don't have a strong opinion on whether it is actually useful to combine
CoinSwap with PayJoin.

>A thing I have been trying to work out is whether SAS can be done with
more than one participant, like in S6

S6 requires timelocks for each output in order to function, so I doubt it
can be made to work with SAS.

I've also tried applying SAS to partially blind swaps and ran into
likability issues, though it's less clear to me whether there is some
fundamental reason why it couldn't work there.

Cheers,
Ruben

On Sun, May 31, 2020 at 4:31 AM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:

> Good morning Ruben and Chris,
>
> > >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
> >
> > This may perhaps be counter-intuitive, but SAS doesn't actually require
> multisig for one of the two outputs, so a single key will suffice. ECDSA is
> a signing algorithm that doesn't support single key multisig (at least not
> without 2p-ECDSA), but notice how for the non-timelocked SAS output we
> never actually have to sign anything together with the other party. We swap
> one of the two keys, and the final owner will create a signature completely
> on their own. No multisig required, which means we can simply use MuSig,
> even today without Schnorr.
>
> Just to be clear, you mean we can use the MuSig key-combination protocol
> for the non-timelocked SAS output, but (of course) not the signing protocol
> which is inherently Schnorr.
>
> Then knowledge of both of the original private keys is enough to derive
> the single combined private key.
>
> > Of course the other output will still have to be a 2-of-2, for which you
> rightly note 2p-ECDSA could be considered. It may also be interesting to
> combine a swap with the opening of a Lightning channel. E.g. Alice and Bob
> want to open a channel with 1 BTC each, but Alice funds it in her entirety
> with 2 BTC, and Bob gives 1 BTC to Alice in a swap. This makes it difficult
> to tell Bob entered the Lightning Network, especially if the channel is
> opened in a state that isn't perfectly balanced. And Alice will gain an
> uncorrelated single key output.
>
> Dual-funding could be done by a single-funding Lightning open followed by
> an onchain-to-offchain swap.
> Though the onchain swap would have to be done, at least currently, with
> hashes.
>
> > >=== PayJoin with CoinSwap ===
> >
> > While it's probably clear how to do it on the timelocked side of SAS, I
> believe PayJoin can also be applied to the non-timelocked side. This does
> require adding a transaction that undoes the PayJoin in case the swap gets
> aborted, which means MuSig can't be used. Everything else stays the same:
> only one tx if successful, and no timelock (= instant settlement). I can
> explain it in detail, if it happens to catch your interest.
>
> I am not in fact convinced that PayJoin-with-CoinSwap adds *that* much
> privacy.
>
> These transactions:
>
>              +---+  +---+
>     Alice ---|   |--|   |--- Bob
>     Alice ---|   |  |   |
>       Bob ---|   |  +---+
>              +---+
>
> Are not really much different in coin ownership analysis from these:
>
>              +---+    +---+
>     Alice ---|   |----|   |--- Bob
>     Alice ---|   | +--|   |
>              +---+ |  +---+
>       Bob ---------+
>
> The latter is possible due to private key handover, the intermediate
> output becomes owned solely by Bob and Bob can add many more inputs to that
> second transaction unilaterally for even greater confusion to chain
> analysis, basically private key handover gets us PayJoin for free.
> It also removes the need for Bob to reveal additional UTXOs to Alice
> during the swap protocol; yes PoDLE mitigates the privacy probing attack
> that Alice can mount on Bob, but it is helpful to remember this is "only" a
> mitigation.
>
> Now of course things are different if Alice is paying some exact amount to
> Carol, and Alice wants to dissociate her funds from the payment.
> The difference is then:
>
>              +---+    +---+
>     Alice ---|   |----|   |--- Bob
>     Alice ---|   |--+ |   |
>       Bob ---|   |  | +---+
>              +---+  +--------- Alice Change
>
>              +---+    +---+
>       Bob ---|   |----|   |--- Carol
>              |   |--+ +---+
>              +---+  |
>                     +--------- Bob Change
>
> Versus:
>
>              +---+    +---+
>     Alice ---|   |----|   |--- Bob
>     Alice ---|   | +--|   |
>              +---+ |  +---+
>       Bob ---------+
>
>              +---+    +---+
>       Bob ---|   |----|   |--- Carol
>              |   |--+ |   |--- Alice Change
>              +---+  | +---+
>                     +--------- Bob Change
>
> In the above, with PayJoin on the first-layer transaction, the Alice
> Change is correlated with Alice and Bob inputs, whereas with the PayJoin on
> the second the Alice change is correlated with Bob inputs and Carol outputs.
>
> But if Alice, using commodity CoinSwap wallets, always has a policy that
> all sends are via CoinSwap (a reasonable policy, similar to the policy in
> JoinMarket of ensuring that all spends out of the wallet are via CoinJoin),
> then the above two trees are not much different for Alice in practice.
> The Alice Change will be swapped with some other maker anyway when it gets
> spent, so what it correlates with will not be much of a problem for Alice.
> At the same time, with PayJoin on the second-layer transaction (possible
> due to private key turnover, which is an inherent part of the SAS protocol):
>
> * Bob does not have to reveal any other coins it owns to Alice other than
> what it is directly swapping, removing a privacy probe vector.
> * Bob can unilaterally combine more than one input to the second
> transaction going to Bob, which further increases the uncertainty of
> clustering around the inputs from Alice than just adding *one* input.
>
> ---
>
> A thing I have been trying to work out is whether SAS can be done with
> more than one participant, like in [S6](
> https://joinmarket.me/blog/blog/multiparty-s6/).
>
> So far, I have not figured out a way to make it multiparty (multihop?).
> Because the secret being transported is a private key that protects a
> specific UTXO, it seems it is not possible to safely use the same secret
> across more than two parties.
> Perhaps others have come ideas?
>
> Regards,
> ZmnSCPxj
>

[-- Attachment #2: Type: text/html, Size: 8629 bytes --]

Re: [bitcoin-dev] Design for a CoinSwap implementation for massively improving Bitcoin privacy and fungibility

[ZmnSCPxj]

Good morning Ruben,


>
> That assumes there will be a second transaction. With SAS I believe we can avoid that, and make it look like this:
>
>              +---+
>     Alice ---|   |--- Bob
>     Alice ---|   |
>       Bob ---|   |
>              +---+

If Alice is paying to a non-SAS aware payee that just provides an onchain address (i.e. all current payees today), then the 2-of-2 output it gets from the swap (both of whose keys it learns at the end of the swap) is **not** the payee onchain address.
And it cannot just hand over both private keys, because the payee will still want unambiguous ownership of the entire UTXO.
So it needs a second transaction anyway.
(with Schnorr then Alice and payee Carol can act as a single entity/taker to Bob, a la Lightning Nodelets using Composable MuSig, but that is a pretty big increase in protocol complexity)

If Alice does not want to store the remote-generated privkey as well, and use only an HD key, then it also has to make the second transaction.
Alice might want to provide the same assurances as current wallets that memorizing a 12-word or so mnemonic is sufficient backup for all the funds (other than funds currently being swapped), and so would not want to leave any funds in a 2-of-2.

If Bob is operating as a maker, then it also cannot directly use the 2-of-2 output it gets from the swap, and has to make a new 2-of-2 output, for the *next* taker that arrives to request its services.

So there is always going to be a second transaction in a SwapMarket system, I think.


What SAS / private key turnover gets us is that there is not a *third* transaction to move from a 1-of-1 to the next address that makers and takers will be moving anyway, and that the protocol does not have to add communication provisions for special things like adding maker inputs or specifying all destination addresses for the second stage and so on, because those can be done unilaterally once the private key is turned over.


> >A thing I have been trying to work out is whether SAS can be done with more than one participant, like in S6
>
> S6 requires timelocks for each output in order to function, so I doubt it can be made to work with SAS.

Hmmm right right.

Naively it seems both chaining SAS/private key turnover to multiple makers, and a multi-maker S6 augmented with private key turnover, would result in the same number of transactions onchain, but I probably have to go draw some diagrams or something first.

But S6 has the mild advantage that all the funding transactions paying to 2-of-2s *can* appear on the same block, whereas chaining swaps will have a particular order of when the transactions appear onchain, which might be used to derive the order of swaps.
On the other hand, funds claiming in S6 is also ordered in time, so someone paying attention to the mempool could guess as well the order of swaps.


Regards,
ZmnSCPxj

Re: [bitcoin-dev] Design for a CoinSwap implementation for massively improving Bitcoin privacy and fungibility

[Ruben Somsen]

[-- Attachment #1: Type: text/plain, Size: 3479 bytes --]

Hi ZmnSCPxj,

>If Alice is paying to a non-SAS aware payee

Yeah, I agree that this use case is not possible without a third
transaction (preferably from the timelocked side, in the case of SAS). My
point was merely that you can swap and simultaneously merge some of your
outputs into the post-swap non-timelocked output, though perhaps that is
not very useful.

Cheers,
Ruben



On Mon, Jun 1, 2020 at 4:34 AM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:

> Good morning Ruben,
>
>
> >
> > That assumes there will be a second transaction. With SAS I believe we
> can avoid that, and make it look like this:
> >
> >              +---+
> >     Alice ---|   |--- Bob
> >     Alice ---|   |
> >       Bob ---|   |
> >              +---+
>
> If Alice is paying to a non-SAS aware payee that just provides an onchain
> address (i.e. all current payees today), then the 2-of-2 output it gets
> from the swap (both of whose keys it learns at the end of the swap) is
> **not** the payee onchain address.
> And it cannot just hand over both private keys, because the payee will
> still want unambiguous ownership of the entire UTXO.
> So it needs a second transaction anyway.
> (with Schnorr then Alice and payee Carol can act as a single entity/taker
> to Bob, a la Lightning Nodelets using Composable MuSig, but that is a
> pretty big increase in protocol complexity)
>
> If Alice does not want to store the remote-generated privkey as well, and
> use only an HD key, then it also has to make the second transaction.
> Alice might want to provide the same assurances as current wallets that
> memorizing a 12-word or so mnemonic is sufficient backup for all the funds
> (other than funds currently being swapped), and so would not want to leave
> any funds in a 2-of-2.
>
> If Bob is operating as a maker, then it also cannot directly use the
> 2-of-2 output it gets from the swap, and has to make a new 2-of-2 output,
> for the *next* taker that arrives to request its services.
>
> So there is always going to be a second transaction in a SwapMarket
> system, I think.
>
>
> What SAS / private key turnover gets us is that there is not a *third*
> transaction to move from a 1-of-1 to the next address that makers and
> takers will be moving anyway, and that the protocol does not have to add
> communication provisions for special things like adding maker inputs or
> specifying all destination addresses for the second stage and so on,
> because those can be done unilaterally once the private key is turned over.
>
>
> > >A thing I have been trying to work out is whether SAS can be done with
> more than one participant, like in S6
> >
> > S6 requires timelocks for each output in order to function, so I doubt
> it can be made to work with SAS.
>
> Hmmm right right.
>
> Naively it seems both chaining SAS/private key turnover to multiple
> makers, and a multi-maker S6 augmented with private key turnover, would
> result in the same number of transactions onchain, but I probably have to
> go draw some diagrams or something first.
>
> But S6 has the mild advantage that all the funding transactions paying to
> 2-of-2s *can* appear on the same block, whereas chaining swaps will have a
> particular order of when the transactions appear onchain, which might be
> used to derive the order of swaps.
> On the other hand, funds claiming in S6 is also ordered in time, so
> someone paying attention to the mempool could guess as well the order of
> swaps.
>
>
> Regards,
> ZmnSCPxj
>

[-- Attachment #2: Type: text/html, Size: 4020 bytes --]

Re: [bitcoin-dev] Design for a CoinSwap implementation for massively improving Bitcoin privacy and fungibility

[Chris Belcher]

Hello ZmnSCPxj,

On 31/05/2020 03:30, ZmnSCPxj via bitcoin-dev wrote:
> Good morning Ruben and Chris,

> I am not in fact convinced that PayJoin-with-CoinSwap adds *that* much privacy.
> 
> These transactions:
> 
>              +---+  +---+
>     Alice ---|   |--|   |--- Bob
>     Alice ---|   |  |   |
>       Bob ---|   |  +---+
>              +---+
> 
> Are not really much different in coin ownership analysis from these:
> 
>              +---+    +---+
>     Alice ---|   |----|   |--- Bob
>     Alice ---|   | +--|   |
>              +---+ |  +---+
>       Bob ---------+

The main benefit of PayJoin-with-CoinSwap is it breaks the
common-input-ownership heuristic, which is a major widely used
heuristic. It would be a big win if that heuristic could be broken.

PayJoin-with-CoinSwap would be useful if Alice is trying to recover some
privacy which was previously degraded, for example if she is spending
from a reused address or from an address linked to her identity. If she
does a PayJoin with the reused address then some other economic entity
would have his activity linked with Alice's.

Just the fact that PayJoin-with-CoinSwap exists would improve privacy
for people who don't use it, for example if someone buys bitcoin from an
exchange that knows their identity and then co-spends it with other
coins they obtained another way. The fact that PayJoin exists means an
adversary cannot assume for sure that this user really owns that other
address which was co-spent. This doesn't apply for regular CoinSwap,
which only ever breaks the transaction graph heuristic, so in our
example the destination the coins are sent *to* would be uncertain, but
that the co-spent inputs are owned by the same person would be certain
in a world where PayJoin didn't exist.

> It also removes the need for Bob to reveal additional UTXOs to Alice during the swap protocol; yes PoDLE mitigates the privacy probing attack that Alice can mount on Bob, but it is helpful to remember this is "only" a mitigation.

Opening up the possibility of spying for free is a real downside for
PayJoin-with-CoinSwap. Using decoy UTXOs as described in my design
document, rather than PoDLE, seems like a better way of resisting these
attacks. This is because at the cost of a little bit more bandwidth and
CPU its possible to make the probability of an attacker successfully
guessing the maker's real UTXOs to be as low as you want.

> But S6 has the mild advantage that all the funding transactions paying to 2-of-2s *can* appear on the same block, whereas chaining swaps will have a particular order of when the transactions appear onchain, which might be used to derive the order of swaps.
On the other hand, funds claiming in S6 is also ordered in time, so
someone paying attention to the mempool could guess as well the order of
swaps.

I think this is wrong, and that it's possible for the funding
transactions of chained/routed swaps to all be in the same block as well.

In CoinSwap it's possible to get DOS'd without the other side spending
money if you broadcast your funding transaction first and the other side
simply disappears. You'd get your money back but you have to waste time
and spend miner fees. The other side didn't spend money to do this, not
even miner fees.

From the point of view of us as a maker in the route, we know we won't
get DOS'd like this for free if we only broadcast our funding
transaction once we've seen the other side's funding transaction being
broadcast first. This should work as long as the two transactions have a
similar fee rate. There might be an attack involving hash power: If the
other side has a small amount of hash power and mines only their funding
transaction in a manner similar to a finney attack, then our funding
transaction should get mined very soon afterwards by another miner and
the protocol will continue as normal. If the other side has knowledge of
the preimage and uses it to do CPFP and take the money, then we can
learn that preimage and do our own CPFP to get our money back too.

So in a routed coinswap setup it should be possible for Alice the taker
to broadcast her funding transaction first, which will lead to all the
makers broadcasting their funding transactions as well once they see the
other side has broadcast first. Then it would be possible for all those
funding transactions to be confirmed in the same block.

I hope I haven't missed anything, because if this doesn't work and each
maker must wait for confirmations, then the UX of routed CoinSwap would
degrade: a CoinSwap route of 5 makers would require at least 5 blocks to
be mined.

Of course this setup can leak the ordering of the routes because the
funding transaction would appear in the mempool in that order, but this
could be beaten if some Alices choose to intentionally spread out the
funding transaction broadcasts among multiple blocks for privacy reasons.

An interesting tangent could be to see if it's possible to make private
key handover work with S6. A nice side-effect of private key handover is
that the transfer of possession of the coins happens off-chain, so then
paying attention to the mempool won't help an adversary much.


Regards,
Chris Belcher

Re: [bitcoin-dev] Design for a CoinSwap implementation for massively improving Bitcoin privacy and fungibility

[ZmnSCPxj]

Good morning Chris,

> > Good morning Ruben and Chris,
>
> > I am not in fact convinced that PayJoin-with-CoinSwap adds that much privacy.
> > These transactions:
> >
> >              +---+  +---+
> >     Alice ---|   |--|   |--- Bob
> >     Alice ---|   |  |   |
> >       Bob ---|   |  +---+
> >              +---+
> >
> >
> > Are not really much different in coin ownership analysis from these:
> >
> >              +---+    +---+
> >     Alice ---|   |----|   |--- Bob
> >     Alice ---|   | +--|   |
> >              +---+ |  +---+
> >       Bob ---------+
> >
>
> The main benefit of PayJoin-with-CoinSwap is it breaks the
> common-input-ownership heuristic, which is a major widely used
> heuristic. It would be a big win if that heuristic could be broken.
>
> PayJoin-with-CoinSwap would be useful if Alice is trying to recover some
> privacy which was previously degraded, for example if she is spending
> from a reused address or from an address linked to her identity. If she
> does a PayJoin with the reused address then some other economic entity
> would have his activity linked with Alice's.
>
> Just the fact that PayJoin-with-CoinSwap exists would improve privacy
> for people who don't use it, for example if someone buys bitcoin from an
> exchange that knows their identity and then co-spends it with other
> coins they obtained another way. The fact that PayJoin exists means an
> adversary cannot assume for sure that this user really owns that other
> address which was co-spent. This doesn't apply for regular CoinSwap,
> which only ever breaks the transaction graph heuristic, so in our
> example the destination the coins are sent to would be uncertain, but
> that the co-spent inputs are owned by the same person would be certain
> in a world where PayJoin didn't exist.

Alice can do PayJoin with a payee Carol that supports normal PayJoin, for similar overall results.

Though I suppose there is a mild advantage still with supporting it on the funding tx of the first transaction, as you noted.

> > But S6 has the mild advantage that all the funding transactions paying to 2-of-2s can appear on the same block, whereas chaining swaps will have a particular order of when the transactions appear onchain, which might be used to derive the order of swaps.
>
> On the other hand, funds claiming in S6 is also ordered in time, so
> someone paying attention to the mempool could guess as well the order of
> swaps.
>
> I think this is wrong, and that it's possible for the funding
> transactions of chained/routed swaps to all be in the same block as well.
>
> In CoinSwap it's possible to get DOS'd without the other side spending
> money if you broadcast your funding transaction first and the other side
> simply disappears. You'd get your money back but you have to waste time
> and spend miner fees. The other side didn't spend money to do this, not
> even miner fees.
>
> From the point of view of us as a maker in the route, we know we won't
> get DOS'd like this for free if we only broadcast our funding
> transaction once we've seen the other side's funding transaction being
> broadcast first. This should work as long as the two transactions have a
> similar fee rate. There might be an attack involving hash power: If the
> other side has a small amount of hash power and mines only their funding
> transaction in a manner similar to a finney attack, then our funding
> transaction should get mined very soon afterwards by another miner and
> the protocol will continue as normal. If the other side has knowledge of
> the preimage and uses it to do CPFP and take the money, then we can
> learn that preimage and do our own CPFP to get our money back too.

How about RBF?

A taker Alice can broadcast the funding tx spending its own funds.
The funding tx spends funds controlled unilaterally by Alice.
Alice can sign a replacement transaction for those funds, spending them to an address with unilateral control, and making the funding tx output with all the obligations attached never get confirmed in the first place.

The chances may be small --- Bob can certainly monitor for Alice broadcasting a replacement and counter-broadcast its own replacement --- but the risk still exists.
TANSTAAGM (There Aint No Such Thing As A Global Mempool) also means Alice could arrange the replacement by other means, such as not using the RBF-enabled flag, broadcasting the self-paying replacement near miner nodes, and broadcasting the CoinSwap-expected funding tx near the Bob fullnode; Bob fullnode will then reject attempts to replace it, but miners will also reject the CoinSwap-expected funding tx and it will not confirm anyway.


With the pre-SAS 4-tx setup, this potentially allows Alice to steal the funds of Bob; after Alice gets its funding-tx-replacement confirmed together with the Bob honest-funding-tx, Alice can use the contract transaction and publish the preimage to take the Bob funds.
Since the Alice-side funding tx has been replaced, knowledge of the hash preimage will not help Bob any: the Alice funding tx has been replaced and Bob cannot use the preimage to claim it (it does not exist).


With SAS Alice cannot outright steal the Bob funds, but the Bob funds will now be locked in a 2-of-2 and Alice can take it hostage (either Bob gives up on the funds, i.e. donates its value to all HODLers, or Bob gives most of the value to Alice).


For the avoidance of theft, it is probably better for Bob to wait for Alice-side funding tx to confirm, probably deeply because reorgs suck.

This at least makes it costly to perform this attack; you have to lock more of your funds longer in order to induce a competitor to lock its funds.


Come to think of it, the same issue probably holds for S6 as well, the funding tx with the longest timelock has to confirm first before the next is even broadcast, bleah.


> An interesting tangent could be to see if it's possible to make private
> key handover work with S6. A nice side-effect of private key handover is
> that the transfer of possession of the coins happens off-chain, so then
> paying attention to the mempool won't help an adversary much.

It certainly seems quite possible; each participant in S6 has a fixed "previous" and "next" participant.

Of course, this requires a secure tunnel, and my understanding of your plan for SwapMarket is that the taker Alice serves as the broadcast medium between all makers and itself.
So, in an S6 sequence of Alice -> Bob1 -> Bob2 -> Alice, after Alice provides the preimage, Bob2 encrypts the private key being handed over in an asymmetric encryption that only Alice can open (e.g. using some known pubkey of Alice, there are many to choose from), Bob1 similarly encrypts its privkey for Bob2, and Alice encrypts the private key to Bob1, and Alice can then broadcast all those data to all participants, and only the correct participant will be able to decrypt it.

---

On another privacy-related note, S6 mildly leaks to each maker its position in the route, via the timelocks.
Each Bob has to know the timelocks it is offered and which it will offer to the next participant, and the timelocks will be larger the further away that Bob is from the Alice taker.
This is a mild privacy leak, one that seems unremovable to me.
(It also exists in Lightning Network as well: we suggest the use of "shadow routes" to artificially increase the distance of forwarding nodes, as a mitigation.)

Regards,
ZmnSCPxj

Re: [bitcoin-dev] Design for a CoinSwap implementation for massively improving Bitcoin privacy and fungibility

[ZmnSCPxj]

Good morning Chris again,


> For the avoidance of theft, it is probably better for Bob to wait for Alice-side funding tx to confirm, probably deeply because reorgs suck.


Over in Lightning-land, we have a concept called "irrevocably committed".
This is a state where a newly-created contract can no longer be cancelled, by publishing an older state.
In Lightning, there is a short timeframe where a new state, and its directly previous state, are both still valid, until the previous state is revoked.
Only once the previous state (that does not contain the contract) has been revoked, and only the latest state is valid, can a forwarding node actually forward the payment.


This is roughly equivalent to the funding tx for the CoinSwap being confirmed.
Until a transaction is confirmed, the UTXOs it spends (i.e. the previous state) can still be validly spent by other alternate transactions.


Regards,
ZmnSCPxj

Re: [bitcoin-dev] Design for a CoinSwap implementation for massively improving Bitcoin privacy and fungibility

[ZmnSCPxj]

Good morning yet again Chris,

> > For the avoidance of theft, it is probably better for Bob to wait for Alice-side funding tx to confirm, probably deeply because reorgs suck.

I realized that the *other* improvement I proposed in the [CoinSwapCS issue](https://github.com/AdamISZ/CoinSwapCS/issues/53) would help with this.
Specifically, `nLockTime`-protected Backouts.

Suppose we have an S6 route as so, with Alice as taker and Bob1 and Bob2 as makers:

    Alice -> Bob1 -> Bob2 -> Alice

We assume here that Bob1 and Bob2 directly talk to Alice and that if Bob1 wants to talk to Bob2 it is done via Alice, so in the below if we say "Bob1 sends to Bob2" we imply that this is done via Alice.

1.  Alice solicits fresh pubkeys from Bob1 and Bob2.
2.  Alice gives timeouts L1 and L2 to Bob1, and L2 and L3 to Bob2, such that L1 > L2 > L3, as well as negotiated amount, fees, etc.
3.  Alice creates (but does NOT sign) a funding tx paying to Alice && Bob1 and gives the txid to Bob1.
4.  Bob1 creates and signs a tx spending from the Alice funding tx and paying to Alice, with `nLockTime = L1`, and gives the signature to Alice.
5.  Bob1 creates (but does NOT sign) a funding tx paying to Bob1 && Bob2 and gives the txid to Bob2.
6.  Bob2 creates and signs a tx spending from the Bob1 funding tx and paying to Bob1, with `nLockTime = L2`, and gives the signature to Bob1.
7.  Bob2 creates (but does NOT sign) a funding tx paying to Bob2 && Alice and gives the txid to Alice.
8.  Alice creates and signs a tx spending from the Bob2 funding tx and paying to Bob2, with `nLockTime = L3`, and gives the signature to Bob2.
9.  Alice signals everyone to sign their respecting funding txes and broadcast them.

The rest of the CoinSwap protocol executes as normal once the funding txes are deeply confirmed.
The only thing that Bob1 (resp. Bob2) needs to wait for is that the signatures for the incoming HTLC / PTLC have been received before forwarding to the next hop.
This allows all funding txes to be confirmed in the same block, or even in some suitable random order (by having Alice send the signal out at different times/blocks to different makers).

The `nLockTime`d backout transactions are sufficient to allow everyone to recover their funds unilaterally in case one of the other funding txes do not confirm.

A similar technique can be done for SAS as well, but this removes the lack of encumbrance in the LTC-side output of SAS, which removes the advantage of having an otherwise unencumbered output.

In effect, the above creates Spilman unidirectional payment channels along the route, bringing the fiddly timing details offchain where it is less visible to observers.

--

However, note that this still allows a form of griefing attack.
Basically, Alice can induce Bob1 and Bob2 to lock their funds for some time, by completing the above ritual, but not signing and broadcasting its own funding tx.
Bob1 and Bob2 will have been induced to lock their funds for L2 and L3, respectively, while Alice only has to RBF away its own funding tx.

Alice might do this if it is actually another maker and it wants to take out its competitors Bob1 and Bob2, reducing their available liquidity for a time and cornering the SwapMarket.


This can be mitigated by replacing step 9 with:

9.  Alice gives its signed funding tx to Bob1.
10.  Bob1 gives its signed funding tx to Bob2.
11.  Bob2 gives its signed funding tx to Alice.
12.  Alice signals everyone to broadcast their funding txes.

Then Bob1 (resp. Bob2) can monitor the mempool/blockchain and check as well if its outgoing funding tx has been broadcast/confirmed, and if so broadcast the incoming funding tx.
Or better, if Bob1 (resp. Bob2) does not receive the Alice signal fast enough, it will broadcast its incoming funding tx anyway.

This is only a mitigation: Alice could have pre-prepared a replacement to the funding tx that it broadcasts near miners just before it signals Bob1 and Bob2 to broadcast all transactions.

For full protection against griefing attacks, Bob1 (resp. Bob2) have to wait for the incoming funding tx to be confirmed deeply before broadcasting its outgoing funding tx as well.

Regards,
ZmnSCPxj

Re: [bitcoin-dev] Design for a CoinSwap implementation for massively improving Bitcoin privacy and fungibility

[Chris Belcher]

Good day ZmnSCPxj,

>>> But S6 has the mild advantage that all the funding transactions paying to 2-of-2s can appear on the same block, whereas chaining swaps will have a particular order of when the transactions appear onchain, which might be used to derive the order of swaps.
>>
>> On the other hand, funds claiming in S6 is also ordered in time, so
>> someone paying attention to the mempool could guess as well the order of
>> swaps.
>>
>> I think this is wrong, and that it's possible for the funding
>> transactions of chained/routed swaps to all be in the same block as well.
>>
>> In CoinSwap it's possible to get DOS'd without the other side spending
>> money if you broadcast your funding transaction first and the other side
>> simply disappears. You'd get your money back but you have to waste time
>> and spend miner fees. The other side didn't spend money to do this, not
>> even miner fees.
>>
>> From the point of view of us as a maker in the route, we know we won't
>> get DOS'd like this for free if we only broadcast our funding
>> transaction once we've seen the other side's funding transaction being
>> broadcast first. This should work as long as the two transactions have a
>> similar fee rate. There might be an attack involving hash power: If the
>> other side has a small amount of hash power and mines only their funding
>> transaction in a manner similar to a finney attack, then our funding
>> transaction should get mined very soon afterwards by another miner and
>> the protocol will continue as normal. If the other side has knowledge of
>> the preimage and uses it to do CPFP and take the money, then we can
>> learn that preimage and do our own CPFP to get our money back too.
> 
> How about RBF?
> 
> A taker Alice can broadcast the funding tx spending its own funds.
> The funding tx spends funds controlled unilaterally by Alice.
> Alice can sign a replacement transaction for those funds, spending them to an address with unilateral control, and making the funding tx output with all the obligations attached never get confirmed in the first place.
> 
> The chances may be small --- Bob can certainly monitor for Alice broadcasting a replacement and counter-broadcast its own replacement --- but the risk still exists.
> TANSTAAGM (There Aint No Such Thing As A Global Mempool) also means Alice could arrange the replacement by other means, such as not using the RBF-enabled flag, broadcasting the self-paying replacement near miner nodes, and broadcasting the CoinSwap-expected funding tx near the Bob fullnode; Bob fullnode will then reject attempts to replace it, but miners will also reject the CoinSwap-expected funding tx and it will not confirm anyway.
> 
> 
> With the pre-SAS 4-tx setup, this potentially allows Alice to steal the funds of Bob; after Alice gets its funding-tx-replacement confirmed together with the Bob honest-funding-tx, Alice can use the contract transaction and publish the preimage to take the Bob funds.
> Since the Alice-side funding tx has been replaced, knowledge of the hash preimage will not help Bob any: the Alice funding tx has been replaced and Bob cannot use the preimage to claim it (it does not exist).
> 
> 
> With SAS Alice cannot outright steal the Bob funds, but the Bob funds will now be locked in a 2-of-2 and Alice can take it hostage (either Bob gives up on the funds, i.e. donates its value to all HODLers, or Bob gives most of the value to Alice).
> 
> 
> For the avoidance of theft, it is probably better for Bob to wait for Alice-side funding tx to confirm, probably deeply because reorgs suck.
> 
> This at least makes it costly to perform this attack; you have to lock more of your funds longer in order to induce a competitor to lock its funds.
> 
> 
> Come to think of it, the same issue probably holds for S6 as well, the funding tx with the longest timelock has to confirm first before the next is even broadcast, bleah.

Your RBF observation actually blows my idea out of the water. Not just
because of RBF but because of an attack by a miner.

Supposing that Alice starts with knowledge of the hash preimage, if she
uses RBF to make her funding transaction never confirm but allows Bob's
funding transaction to confirm, then Alice can use her preimage to take
the money from Bob's funding transaction. Bob will learn the value of
the preimage but it won't be much good to him because Alice's funding
transaction isn't valid anymore. Alice will get money from her funding
transaction and also money from Bob's funding transaction.

Because of this attack, it's pretty clear that a CoinSwap peer who
starts _without_ knowledge of the preimage must wait for the other
side's funding transaction to actually confirm, perhaps even with
multiple confirmations if they fear that the other side has access to
hashpower. For example, a miner could play the role of Alice and use
this attack to almost-risklessly steal Bob's coins using a finney attack.

That also seems to mean that a N-party routed CoinSwap requires at least
N blocks to be mined for all the funding transactions to be mined, which
is a slight setback for user experience. (Although even with today's
existing privacy tech, users must hang around waiting for coinjoins to
be signed, or waiting for multiple coinjoins to be confirmed.
Blockchains are inherently slow and we can't get around that.)


>>> For the avoidance of theft, it is probably better for Bob to wait for Alice-side funding tx to confirm, probably deeply because reorgs suck.
> 
> I realized that the *other* improvement I proposed in the [CoinSwapCS issue](https://github.com/AdamISZ/CoinSwapCS/issues/53) would help with this.
> Specifically, `nLockTime`-protected Backouts.
> 
> Suppose we have an S6 route as so, with Alice as taker and Bob1 and Bob2 as makers:
> 
>     Alice -> Bob1 -> Bob2 -> Alice
> 
> We assume here that Bob1 and Bob2 directly talk to Alice and that if Bob1 wants to talk to Bob2 it is done via Alice, so in the below if we say "Bob1 sends to Bob2" we imply that this is done via Alice.
> 
> 1.  Alice solicits fresh pubkeys from Bob1 and Bob2.
> 2.  Alice gives timeouts L1 and L2 to Bob1, and L2 and L3 to Bob2, such that L1 > L2 > L3, as well as negotiated amount, fees, etc.
> 3.  Alice creates (but does NOT sign) a funding tx paying to Alice && Bob1 and gives the txid to Bob1.
> 4.  Bob1 creates and signs a tx spending from the Alice funding tx and paying to Alice, with `nLockTime = L1`, and gives the signature to Alice.
> 5.  Bob1 creates (but does NOT sign) a funding tx paying to Bob1 && Bob2 and gives the txid to Bob2.
> 6.  Bob2 creates and signs a tx spending from the Bob1 funding tx and paying to Bob1, with `nLockTime = L2`, and gives the signature to Bob1.
> 7.  Bob2 creates (but does NOT sign) a funding tx paying to Bob2 && Alice and gives the txid to Alice.
> 8.  Alice creates and signs a tx spending from the Bob2 funding tx and paying to Bob2, with `nLockTime = L3`, and gives the signature to Bob2.
> 9.  Alice signals everyone to sign their respecting funding txes and broadcast them.
> 
> The rest of the CoinSwap protocol executes as normal once the funding txes are deeply confirmed.
> The only thing that Bob1 (resp. Bob2) needs to wait for is that the signatures for the incoming HTLC / PTLC have been received before forwarding to the next hop.
> This allows all funding txes to be confirmed in the same block, or even in some suitable random order (by having Alice send the signal out at different times/blocks to different makers).
> 
> The `nLockTime`d backout transactions are sufficient to allow everyone to recover their funds unilaterally in case one of the other funding txes do not confirm.
> 
> A similar technique can be done for SAS as well, but this removes the lack of encumbrance in the LTC-side output of SAS, which removes the advantage of having an otherwise unencumbered output.
> 
> In effect, the above creates Spilman unidirectional payment channels along the route, bringing the fiddly timing details offchain where it is less visible to observers.

I think I'm having trouble understanding this, does it work like this:

Say we're in the 2-party coinswap case (Alice and Bob)

We have Alice's funding transaction:
   Alice UTXO ---> 2of2 multisig (Alice+Bob)

And we have the regular contract transaction
   2of2 multisig (Alice+Bob) ---> Alice+timelock1 OR Bob+hashlock

And you propose a second pre-signed transaction?
   2of2 multisig (Alice+Bob) ---> Bob+timelock2

Where timelock2 > timelock1

If that's the protocol, then it's vulnerable to an attack. Once the
preimage is revealed we should be in a situation where Bob can
unilaterally get his coins back by broadcasting the regular contract
transaction and using the preimage to immediately get his coins. That
means Alice will be happy to hand over her private key, just to save
miner fees and improve privacy. But if the second pre-signed transaction
exists then Alice could do an attack where she broadcasts it and gets it
mined (perhaps more successfully if she has some hashpower). Once it's
mined then the regular contract transaction becomes invalid and Bob
can't get his money, in other words Bob doesn't have unilateral control
over those coins.

Re: [bitcoin-dev] Design for a CoinSwap implementation for massively improving Bitcoin privacy and fungibility

[ZmnSCPxj]

Good morning Chris,

> I think I'm having trouble understanding this, does it work like this:
>
> Say we're in the 2-party coinswap case (Alice and Bob)
>
> We have Alice's funding transaction:
> Alice UTXO ---> 2of2 multisig (Alice+Bob)
>
> And we have the regular contract transaction
> 2of2 multisig (Alice+Bob) ---> Alice+timelock1 OR Bob+hashlock
>
> And you propose a second pre-signed transaction?
> 2of2 multisig (Alice+Bob) ---> Bob+timelock2

No, it is:

2of2 multisig (Alice+Bob) --(nLockTime=locktime1)-> Alice

The timelock is  imposed as a `nLockTime`, not as an `OP_CLTV` (so not in the output of the tx, but part of the tx), and the backout returns the funds to Alice, not sends it to Bob.
This transaction is created *before* the contract transaction.

The order is:

* Create (but not sign) Alice funding tx (Alice --> Alice+Bob).
* Create and sign Alice backout transaction (Alice+Bob -(nLockTime=locktime1)-> Alice).
* Create (but not sign) Bob funding tx (Bob --> Alice+Bob+sharedSecret).
* Create and sign Bob backout transaction (Alice+Bob+sharedSecret -(nLocktime=locktime2)-> Bob) where timelock2 < timelock1.
* Sign and broadcast funding txes.
  * At this point, even if Bob funding tx is confirmed but Alice funding tx is not, Bob can recover funds with the backout, but Alice cannot steal the funds (since there is no hashlock branch at this point).
* When Alice funding tx is confirmed, create and sign contract transaction (Alice+Bob --> Alice+timelock1 OR Bob+hashlock).
* When Bob funding tx is confirmed and Bob has received the Alice contract transaction, create and sign Bob contract transaction (Alice+Bob+sharedSecret --> Bob+timelock2 OR Alice+hashlock).
* Continue as normal.

In effect, the backout transaction creates a temporary Spilman unidirectional time-bound channel.
We just reuse the same timelock on the HTLC we expect to instantiate, as the time bound of the Spilman channel; the timelock exists anyway, we might as well reuse it for the Spilman.

Creation of the contract tx invalidates the backout tx (the backout tx is `nLockTime`d, the contract tx has no such encumbrance), but the backout allows Alice and Bob to fund their txes simultaneously without risk of race loss.
However, they do still have to wait for (deep) confirmation before signing contract transactions, and Bob has to wait for the incoming contract transaction as well before it signs its outgoing contract transaction.

The protocol is trivially extendable with more than one Bob.

The insight basically is that we can split CoinSwap into a "channel establishment" phase and "HTLC forwarding" phase followed by "HTLC resolution" and "private key handover".
HTLC forwarding and HTLC resolution are "done offchain" in the channels, and channel establishment can be done in any order, including reverse.

Indeed, the Spilman channel need not have the same timelock as the HTLC it will eventually host: it could have a shorter timelock, since the contract transaction has no `nLockTime` it can be instantiated (with loss of privacy due to the nonstandard script) before the Spilman timeout.

Regards,
ZmnSCPxj

Re: [bitcoin-dev] Design for a CoinSwap implementation for massively improving Bitcoin privacy and fungibility

[ZmnSCPxj]

Good morning again Chris,

I am uncertain if you are aware, but some years ago somebody claimed that 2p-ECDSA could use Scriptless Script as well over on lightning-dev.

* https://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180426/fe978423/attachment-0001.pdf
* https://lists.linuxfoundation.org/pipermail/lightning-dev/2018-April/001221.html

I cannot claim to follow the math enough to say it is actually secure, but the idea does exist.

If this is sufficiently secure, we can fold the Spilman backout into the scriptless script swap as well.

* Alice creates secret keypairs A[0] = a[0] * G, A[1] = a[1] * G
* Bob creates secret keypairs B[0] = b[0] * G, B[1] = b[1] * G
* Alice creates (but does not sign) funding from Alice -> A[0] && B[0]
* Bob provides partial signature for A[0] && B[0] -(nLockTime=locktime1)-> Alice to Alice and Alice completes this signature and stashes it.
* Bob creates (but does not sign) funding from Bob -> A[1] && B[1]
* Alice provides partial signature for A[1] && B[1] -(nLockTime=lockTime2)-> Bob to Bob and Bob completes this signature and stashes it.
* Alice and Bob sign and broadcast their funding transactions.
  * This can safely be done in any order; Bob will refuse to continue with the protocol until it sees Alice funding is confirmed, and will abort if locktime2 is too near.
* Alice waits for Bob funding tx to confirm.
* Alice provides a 2p-ECDSA adaptor signature for A[1] && B[1] --> Alice; the adaptor signature, when completed, reveals the secret a[0] to Bob.
* Bob waits for Alice funding tx to confirm.
* Bob provides the partial signature for the given adaptor signature for A[1] && B[1] --> Alice and  Alice completes this signature and stashes it.
* Alice gives a[0] outright to Bob.
* Bob gives b[1] outright to Alice.
* Alice spends the A[1] && B[1] output before locktime2.
* Bob spends the A[0] && B[0] output before locktime1.

I also pointed out the griefing problem in Lightning also applies to SwapMarket.
Bob can limit the griefing problem by requiring that locktime2 <= now + 12, and requiring that locktime1 >= now + 60.
This means that Alice has to lock its funds for 10 hours if it forces Bob to lock its funds for 2 hours, making it undesirable as an attack on competing makers.
This does prevent chaining (no maker is going to accept the outgoing), but if Alice wants chaining it can always use the private key handed over to immediately start a funding tx with another Bob.

(This is not a good solution for griefing in the Lightning Network since channels are intended to be reused there, whereas the Spilman channels in CoinSwap exist only to allow funding transactions to confirm in any order onchain, and are used only for the specific swap; in Lightning the forwarding node has an incentive to release the incoming HTLC immediately instead of imposing the incoming wait time since the funding can be reused for a different payment, but in CoinSwap it cannot be reused anyway, so it could just let the incoming timelock lapse instead of releasing that encumbrance as would be done in Lightning.)

Regards,
ZmnSCPxj

Re: [bitcoin-dev] Design for a CoinSwap implementation for massively improving Bitcoin privacy and fungibility

[ZmnSCPxj]

Good morning a third time Chris,

Now unrelated to the funding order, but one of the reasons why timeliness is desirable for CoinSwap is that if possible, we want to ensure that sends from a user wallet are not correlatable with receives into that wallet.
Thus, there is the strong suggestion that before sending to a payee, the user wallet should swap, then use the swapped funds to pay the payee, i.e. swap-on-pay.
JoinMarket does this in `sendpayment.py`, for example, and this is the recommended way to perform payments out of the JoinMarket wallet.

Let me propose an alternative: swap-on-receive+swap-on-change.

ZeroLink already suggests that wallets maintain two internal wallets: a pre-mix wallet and a post-mix wallet.
With swap-on-receive, when the user wants a receive address, the wallet gets it from the pre-mix wallet address.
Then, when wallet notices any unspent funds on any pre-mix wallet address, the wallet automatically swaps it into the post-mix wallet.
This is swap-on-receive.
Long-term HODLing goes into post-mix wallet addresses.

Then, when sending, the wallet selects from the post-mix wallet coins, and spends those coins directly into the payee address.
If there is no exact amount, it has to have change.
The change output does *not* go to the pre-mix or post-mix wallet address.
Instead, it goes to a 2-of-2 funding outpoint for a new swap immediately.

This lets the payee receive its funds quickly, as soon as the transaction confirms, without waiting for the CoinSwap to complete.
Of course, the user now has to be online to *fully* receive funds (the user cannot spend the funds until it is in the post-mix wallet).

Regards,
ZmnSCPxj

Re: [bitcoin-dev] Design for a CoinSwap implementation for massively improving Bitcoin privacy and fungibility

[Chris Belcher]

Good morning ZmnSCPxj,

On 06/06/2020 02:40, ZmnSCPxj wrote:
> Good morning Chris,
> 
>> I think I'm having trouble understanding this, does it work like this:
>>
>> Say we're in the 2-party coinswap case (Alice and Bob)
>>
>> We have Alice's funding transaction:
>> Alice UTXO ---> 2of2 multisig (Alice+Bob)
>>
>> And we have the regular contract transaction
>> 2of2 multisig (Alice+Bob) ---> Alice+timelock1 OR Bob+hashlock
>>
>> And you propose a second pre-signed transaction?
>> 2of2 multisig (Alice+Bob) ---> Bob+timelock2
> 
> No, it is:
> 
> 2of2 multisig (Alice+Bob) --(nLockTime=locktime1)-> Alice
> 
> The timelock is  imposed as a `nLockTime`, not as an `OP_CLTV` (so not in the output of the tx, but part of the tx), and the backout returns the funds to Alice, not sends it to Bob.
> This transaction is created *before* the contract transaction.
> 
> The order is:
> 
> * Create (but not sign) Alice funding tx (Alice --> Alice+Bob).
> * Create and sign Alice backout transaction (Alice+Bob -(nLockTime=locktime1)-> Alice).
> * Create (but not sign) Bob funding tx (Bob --> Alice+Bob+sharedSecret).
> * Create and sign Bob backout transaction (Alice+Bob+sharedSecret -(nLocktime=locktime2)-> Bob) where timelock2 < timelock1.
> * Sign and broadcast funding txes.
>   * At this point, even if Bob funding tx is confirmed but Alice funding tx is not, Bob can recover funds with the backout, but Alice cannot steal the funds (since there is no hashlock branch at this point).
> * When Alice funding tx is confirmed, create and sign contract transaction (Alice+Bob --> Alice+timelock1 OR Bob+hashlock).
> * When Bob funding tx is confirmed and Bob has received the Alice contract transaction, create and sign Bob contract transaction (Alice+Bob+sharedSecret --> Bob+timelock2 OR Alice+hashlock).
> * Continue as normal.
> 
> In effect, the backout transaction creates a temporary Spilman unidirectional time-bound channel.
> We just reuse the same timelock on the HTLC we expect to instantiate, as the time bound of the Spilman channel; the timelock exists anyway, we might as well reuse it for the Spilman.
> 
> Creation of the contract tx invalidates the backout tx (the backout tx is `nLockTime`d, the contract tx has no such encumbrance), but the backout allows Alice and Bob to fund their txes simultaneously without risk of race loss.
> However, they do still have to wait for (deep) confirmation before signing contract transactions, and Bob has to wait for the incoming contract transaction as well before it signs its outgoing contract transaction.
> 
> The protocol is trivially extendable with more than one Bob.
> 
> The insight basically is that we can split CoinSwap into a "channel establishment" phase and "HTLC forwarding" phase followed by "HTLC resolution" and "private key handover".
> HTLC forwarding and HTLC resolution are "done offchain" in the channels, and channel establishment can be done in any order, including reverse.
> 
> Indeed, the Spilman channel need not have the same timelock as the HTLC it will eventually host: it could have a shorter timelock, since the contract transaction has no `nLockTime` it can be instantiated (with loss of privacy due to the nonstandard script) before the Spilman timeout.
> 
> Regards,
> ZmnSCPxj
> 

Thanks for the explanation. I understand now, and I understand how this
makes it possible for all funding transactions in a coinswap route to be
confirmed in the same block.

However, I think this also breaks private key handover. Here's why:

Recall that in a Alice/Bob coinswap we have two funding transactions
(Alice --> multisig(Alice, Bob) and Bob --> multisig(Bob,Alice)), and
two contract transactions (multisig(Alice, Bob) -->
Alice+OP_CSV_timelock OR Bob+hashlock and multisig(Bob,Alice -->
Bob+OP_CSV_timelock OR Alice+hashlock). After the hashlock preimage
becomes known to all then Alice and Bob give their multisig privkey to
the other party.

Bob now has both privkeys in the multisig(Alice,Bob) so he can sign any
transaction he wants spending from it, but the contract transaction
still exists. So until Bob actually spends from the multisig he must
always be watching the blockchain, and if Alice broadcasts the contract
transaction then Bob must immediately spend from it using the hash
preimage branch. If Bob waits too long and the OP_CSV timelock value
passes then Alice can steal Bob's money by spending with that path. The
OP_CSV timelock only starts ticking when the contract transaction
actually confirms, and this is crucial for making privkey handover
practical because it means the coins in the multisig can stay unspent
indefinitely.

However, I think this does not apply to the scheme you described which
uses nLockTime, because after the privkeys are handed over Alice's
backout transaction (Alice+Bob -(nLockTime=locktime1)-> Alice) still
exists, and Alice could broadcast it. Once locktime1 passes then Alice
can steal Bob's coins by broadcasting even though Bob holds both
privkeys to that multisig. And using relative nLockTime doesn't help
either because its timelock will start ticking down from when the
funding transaction is confirmed, not when the contract transaction is
confirmed, and so the coins in the multisig cant remain unspent
indefinitely.

So fundamentally I think privkey handover gets broken here because it
requires relative timelocks. And those the relative timelocks need to
start ticking down only after a contract transaction is confirmed.


> I am uncertain if you are aware, but some years ago somebody claimed that 2p-ECDSA could use Scriptless Script as well over on lightning-dev.

I was aware. In such a scheme we'd still require the other building
blocks like fidelity bonds, multi-transaction and routing. So I was
thinking to code the project using the simplest hash-time-locked
contracts and once it all works we can add things like ECDSA-2P
scriptless scripts or schnorr signatures when they get added. Making the
Spilman channel scheme work with that is an interesting idea, thanks for
the thought.

> Let me propose an alternative: swap-on-receive+swap-on-change.

That's an interesting point, thanks for the thought. This scheme might
not be appropriate for every threat model and use case.
For example, if someone wants to use bitcoin just as a foreign currency
for its privacy and censorship-resistant properties. So for example if
they want to pay for a VPN anonymously, so they buy bitcoins and
immediately send all of them to the VPN merchant. The swap-on-receive
wouldn't be appropriate for them because they'll be doing a coinswap
straight away to the VPN merchant. So perhaps this plan could be an
optional mode of operation (which may or may not be the default). The
scheme obviously is useful when bitcoin is being used more as a
day-to-day money.


Regards
CB

Re: [bitcoin-dev] Design for a CoinSwap implementation for massively improving Bitcoin privacy and fungibility

[ZmnSCPxj]

Good morning Chris,

> > Let me propose an alternative: swap-on-receive+swap-on-change.
>
> That's an interesting point, thanks for the thought. This scheme might
> not be appropriate for every threat model and use case.
> For example, if someone wants to use bitcoin just as a foreign currency
> for its privacy and censorship-resistant properties. So for example if
> they want to pay for a VPN anonymously, so they buy bitcoins and
> immediately send all of them to the VPN merchant. The swap-on-receive
> wouldn't be appropriate for them because they'll be doing a coinswap
> straight away to the VPN merchant. So perhaps this plan could be an
> optional mode of operation (which may or may not be the default). The
> scheme obviously is useful when bitcoin is being used more as a
> day-to-day money.


No, I think you misunderstand my proposal.

If the user is doing swap-on-receive, the user already has an anonymous UTXO, they can just transfer it directly in full to the VPN without using a CoinSwap.

The number of CoinSwaps involved is the same: one.

So the difference is:

* swap-on-receive:
  * I get some coins from an exchange, giving them my contact information and bank information and all the places I have ever inhabited in my entire existence and an unfertilized egg sample and an archive of my diary and let them invasively scan my cognitive substrate.
  * I send the coins to my CoinSwap wallet.
  * The CoinSwap wallet automaticaly CoinSwaps the coins into a new UTXO.
    * One CoinSwap.
  * I tell the CoinSwap wallet to send it all to the VPN.
    * My CoinSwap wallet knows my coins are already cleaned, so it creates a plain 1-input 1-output transaction directly to the VPN address.

* swap-on-pay:
  * I get some coins from an exchange, giving them my contact information and bank information and all the places I have ever inhabited in my entire existence and an unfertilized egg sample and an archive of my diary and let them invasively scan my cognitive substrate.
  * I send the coins to my CoinSwap wallet.
  * I tell the CoinSwap wallet to send it all to the VPN.
    * My CoinSwap wallet automatically arranges a CoinSwap into the VPN address.
      * One CoinSwap.

So in both cases the same expected number of CoinSwaps is done, i.e. one.

Note that there are still details like how much onchain fees are and how much CoinSwap maker fees are and etc etc but they exist for both flows anyway.
So I would still be buying slightly more than my target amount, and if there is any change I could just designate it to be added to the mining fees or a donation to ZmnSCPxj, because ZmnSCPxj is so awesome.

What swap-on-receive+swap-on-change instead does is just amortize the timing of the CoinSwaps, so that you CoinSwap as soon as you receive, instead of as soon as you have to pay, so that sending payments is as fast as non-CoinSwap onchain wallets.


Regards,
ZmnSCPxj

Re: [bitcoin-dev] Design for a CoinSwap implementation for massively improving Bitcoin privacy and fungibility

[Chris Belcher]

Hello ZmnSCPxj,

On 10/06/2020 11:58, ZmnSCPxj wrote:
> Good morning Chris,
> 
>>> Let me propose an alternative: swap-on-receive+swap-on-change.
>>
>> That's an interesting point, thanks for the thought. This scheme might
>> not be appropriate for every threat model and use case.
>> For example, if someone wants to use bitcoin just as a foreign currency
>> for its privacy and censorship-resistant properties. So for example if
>> they want to pay for a VPN anonymously, so they buy bitcoins and
>> immediately send all of them to the VPN merchant. The swap-on-receive
>> wouldn't be appropriate for them because they'll be doing a coinswap
>> straight away to the VPN merchant. So perhaps this plan could be an
>> optional mode of operation (which may or may not be the default). The
>> scheme obviously is useful when bitcoin is being used more as a
>> day-to-day money.
> 
> 
> No, I think you misunderstand my proposal.
> 
> If the user is doing swap-on-receive, the user already has an anonymous UTXO, they can just transfer it directly in full to the VPN without using a CoinSwap.
> 
> The number of CoinSwaps involved is the same: one.
> 
> So the difference is:
> 
> * swap-on-receive:
>   * I get some coins from an exchange, giving them my contact information and bank information and all the places I have ever inhabited in my entire existence and an unfertilized egg sample and an archive of my diary and let them invasively scan my cognitive substrate.
>   * I send the coins to my CoinSwap wallet.
>   * The CoinSwap wallet automaticaly CoinSwaps the coins into a new UTXO.
>     * One CoinSwap.
>   * I tell the CoinSwap wallet to send it all to the VPN.
>     * My CoinSwap wallet knows my coins are already cleaned, so it creates a plain 1-input 1-output transaction directly to the VPN address.
> 
> * swap-on-pay:
>   * I get some coins from an exchange, giving them my contact information and bank information and all the places I have ever inhabited in my entire existence and an unfertilized egg sample and an archive of my diary and let them invasively scan my cognitive substrate.
>   * I send the coins to my CoinSwap wallet.
>   * I tell the CoinSwap wallet to send it all to the VPN.
>     * My CoinSwap wallet automatically arranges a CoinSwap into the VPN address.
>       * One CoinSwap.
> 
> So in both cases the same expected number of CoinSwaps is done, i.e. one.
> 
> Note that there are still details like how much onchain fees are and how much CoinSwap maker fees are and etc etc but they exist for both flows anyway.
> So I would still be buying slightly more than my target amount, and if there is any change I could just designate it to be added to the mining fees or a donation to ZmnSCPxj, because ZmnSCPxj is so awesome.
> 
> What swap-on-receive+swap-on-change instead does is just amortize the timing of the CoinSwaps, so that you CoinSwap as soon as you receive, instead of as soon as you have to pay, so that sending payments is as fast as non-CoinSwap onchain wallets.
> 
> 
> Regards,
> ZmnSCPxj
> 

Right, I get it. Good explanation.

In your swap-on-receive example the exchange also can't tell how long
your coins remain unspent in your wallet, which they could in
swap-on-pay. This is very useful information for an exchange because it
tells them about what hodlers are doing, and they might trade against
them. (e.g. opening big short positions right after they see many long
term hodl'd coins being moved)

Re: [bitcoin-dev] Design for a CoinSwap implementation for massively improving Bitcoin privacy and fungibility

[Mr. Lee Chiffre]

>
> === 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
>






Great work Chris and you have my respects for your contributions to
Bitcoin. A concern I have with bitcoin is scalability and privacy. Both
are important. The reasons people bash on Monero is also the same issue
Bitcoin has. The very large transaction size to achieve acceptable privacy
on a distributed financial network. Im not shilling Monero here. I am only
saying that bitcoin transactions with similar privacy properties are at
least equally as large as Monero transactions. Coinjoin on Monero can be
compared to ring signatures in Monero from the view of using decoys to
help conceal the source. From this proposal is this to say that
transactions will be at least 12 times larger in size to achieve the
property of privacy that bitcoin is currently missing?

Another thing to consider is that if coinswaps cannot be sent as a payment
then a coinswap needs to take place after every transaction to keep the
privacy and unlinkability from your other bitcoin transactions.

I always thought that CoinSwap would be and is a very much needed thing
that needs developed. The ability to swap coins with other people in a
trustless way and way that is not linkable to the public blockchain. But
how can this be scalable at all with the multiple branches and layers?
This is a good idea in theory but my concern would be the scalability
issues this creates.

Do you have any comments on this?
Thank you


-- 
lee.chiffre@secmail.pro
PGP 97F0C3AE985A191DA0556BCAA82529E2025BDE35

Re: [bitcoin-dev] Design for a CoinSwap implementation for massively improving Bitcoin privacy and fungibility

[Mr. Lee Chiffre]

> Coinjoin on Monero can be
> compared to ring signatures in Monero from the view of using decoys to
> help conceal the source. From this proposal is this to say that
> transactions will be at least 12 times larger in size to achieve the
> property of privacy that bitcoin is currently missing?
>


This was a typo. Coinjoin on BITCOIN, can be compared to ring signatures
in Monero form the view of using decoys to help conceal the source.


The same thing that makes monero transactions large and a scalability
concern is the same thing that bitcoin suffers from with using privacy
focused transactions.

Re: [bitcoin-dev] Design for a CoinSwap implementation for massively improving Bitcoin privacy and fungibility

[ZmnSCPxj]

Good morning Mr. Lee,


> > === 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
> >
>
> Great work Chris and you have my respects for your contributions to
> Bitcoin. A concern I have with bitcoin is scalability and privacy. Both
> are important. The reasons people bash on Monero is also the same issue
> Bitcoin has. The very large transaction size to achieve acceptable privacy
> on a distributed financial network. Im not shilling Monero here. I am only
> saying that bitcoin transactions with similar privacy properties are at
> least equally as large as Monero transactions. Coinjoin on Monero can be
> compared to ring signatures in Monero from the view of using decoys to
> help conceal the source. From this proposal is this to say that
> transactions will be at least 12 times larger in size to achieve the
> property of privacy that bitcoin is currently missing?

CoinSwap lets you buy privacy at whatever rate is manageable for you.
You can buy a simple non-routed non-multitransaction CoinSwap, for example, instead of larger sections like the above, depending on your privacy needs.
Even doing a non-routed non-multitransaction CoinSwap would help fungibility of those doing more complex setups, because the tiny CoinSwaps you make are made of "the same things" that the more complex CoinSwaps are made of.

>
> Another thing to consider is that if coinswaps cannot be sent as a payment
> then a coinswap needs to take place after every transaction to keep the
> privacy and unlinkability from your other bitcoin transactions.
>
> I always thought that CoinSwap would be and is a very much needed thing
> that needs developed. The ability to swap coins with other people in a
> trustless way and way that is not linkable to the public blockchain. But
> how can this be scalable at all with the multiple branches and layers?
> This is a good idea in theory but my concern would be the scalability
> issues this creates.
>
> Do you have any comments on this?
> Thank you

Overall, multiple mixing techniques cover a wide range of cost and privacy.

* PayJoins are cheap and almost free (you are coordinating with only one other participant who is strongly incentivized to cooperate with you, and making a single overall tx) but buys you only a small dollop of privacy (transaction can be misinterpreted by chain analysis, but probabilistic analysis can be "reasonably accurate" for a few transactions).
* Equal-valued CoinJoins are slightly more expensive than PayJoins but give a good amount of privacy (you are coordinating with multiple participants, and probably paying coordination/participation fees, but *which* output is yours will give probabilistic analysis a run for its money, although it is obvious that you *did* participate in a CoinJoin).
* CoinSwaps are a good bit more expensive than equal-valud CoinJoins but give a significant amount of privacy for their cost (you are coordinating with multiple participants and paying coordination/participation fees *and* you run the risk of getting your funds timelocked in case of network communications problems or active hacking attempts, but it is hard for chain analysis to even *realize* that a CoinSwap even occurred, i.e. it is steganographic).

Chris argues that CoinSwap gives better privacy:cost ratios than equal-valued CoinJoins, you can wait and see if he gives more supporting arguments regarding this, but overall the various mixing tech exists to give choice on how much privacy you buy.

Regards,
ZmnSCPxj

Re: [bitcoin-dev] Design for a CoinSwap implementation for massively improving Bitcoin privacy and fungibility

[Chris Belcher]

Hello Lee,

Thanks for the review.

On 10/06/2020 01:43, Mr. Lee Chiffre wrote:
> 
>>
>> === 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
>>
> 
> 
> 
> 
> 
> 
> Great work Chris and you have my respects for your contributions to
> Bitcoin. A concern I have with bitcoin is scalability and privacy. Both
> are important. The reasons people bash on Monero is also the same issue
> Bitcoin has. The very large transaction size to achieve acceptable privacy
> on a distributed financial network. Im not shilling Monero here. I am only
> saying that bitcoin transactions with similar privacy properties are at
> least equally as large as Monero transactions. Coinjoin on Monero can be
> compared to ring signatures in Monero from the view of using decoys to
> help conceal the source. From this proposal is this to say that
> transactions will be at least 12 times larger in size to achieve the
> property of privacy that bitcoin is currently missing?
> 
> Another thing to consider is that if coinswaps cannot be sent as a payment
> then a coinswap needs to take place after every transaction to keep the
> privacy and unlinkability from your other bitcoin transactions.
> 
> I always thought that CoinSwap would be and is a very much needed thing
> that needs developed. The ability to swap coins with other people in a
> trustless way and way that is not linkable to the public blockchain. But
> how can this be scalable at all with the multiple branches and layers?
> This is a good idea in theory but my concern would be the scalability
> issues this creates.
> 
> Do you have any comments on this?
> Thank you
> 

You are right to be concerned about scalability.

Here's a few of my thoughts on this:

An issue with Monero (or any cryptocurrency based on the ring signature
input signing scheme) isn't just that transactions are bigger in bytes.
Monero full nodes can't know when a TXO has been spent, so pruning is
impossible in Monero and the list of TXOs perpetually grows, this is
unlike in bitcoin where full nodes know if a UTXO has been spent and so
can delete it in pruning. The storage space needed for Bitcoin's UTXO
set sometimes actually gets smaller.

Note that Monero software actually has a feature called "pruning" so
sometimes the terminology gets confused when people say "wait, Monero
_does_ have pruning". But this pruning doesn't do the same thing as
Bitcoin's pruning, the disk space still grows as O(TXOcount) which is
much faster compared to Bitcoin's O(UTXOcount).

And when designing this CoinSwap system I've been careful to make sure
it doesn't break pruning (or other resources saving features, for
example CoinSwap can be made to work with the blocksonly feature of
Bitcoin Core). So bitcoin-with-CoinSwap's scalability isnt anywhere near
as bad as Monero's.

You're right to talk about decoys. Decoys are not a good way to obtain
privacy because they can be broken by repeated interactions.. I really
like this talk about why decoys are not a good solution to privacy in
many cases:

talk: https://www.youtube.com/watch?v=YgtF7psIKWg&feature=youtu.be&t=3701
transcript:
https://tokyo2018.scalingbitcoin.org/transcript/tokyo2018/how-much-privacy-is-enough

Equal-output CoinJoins also work with decoys. Like in JoinMarket you
could analyze those CoinJoins to say that the inputs and outputs of the
makers in a CoinJoin are actually just decoys. Fixed-denomination
CoinJoins like in Wasabi or Samourai also use much more block space
because of the reduced divisibility, for example Wasabi coinjoins can
only be done with about 0.1 BTC, so if you want to mix 1 BTC then you
have to do 10 such CoinJoins, costing 10 times the block space.

CoinSwap doesn't work by adding decoys, it improves privacy in the same
way as Lightning: by moving information off-chain.

You could perhaps analyze CoinSwap as using decoys if you say that the
decoys are almost every other bitcoin transaction happening on the
blockchain, and that can be almost as big as you want. One full block
has about 3000 outputs, so if you wait a day between the CoinSwap
funding and spending transactions then that's 144*3000 = 432000 decoys
(this calculation is simplified, but it's a good starting point). If
CoinJoin or Monero transactions had that many decoys they would be
hundreds of MB each.


Because CoinSwap transactions can look exactly the same as regular
transactions, they would improve the privacy of users even if they don't
use CoinSwap.

So on twitter sometimes I see people talking about "making every spend a
CoinJoin". The suggestion would be very costly in block space, and isn't
necessary for CoinSwap. I think perhaps 5% of transactions being
CoinSwaps or PayJoin-with-CoinSwap (as long as they were spread roughly
equally across the economy) would be enough to destroy the transaction
graph heuristic and common-input-ownership heuristic. Then anyone
analyzing the blockchain couldn't be sure when they see coins going from
address A to B that the ownership actually went from A to B, or that if
they see multiple inputs they don't know whether those inputs are
actually owned by the same entity.

Also, CoinSwaps could be used as payment. For example take this 1-hop
CoinSwap where Alice owns 10 BTC and wants to deposit 5 BTC into her
exchange account.

      (3 BTC) -->     (5 BTC) --> Exchange
Alice (1 BTC) --> Bob (4 BTC) --> Alice change1
      (6 BTC) -->     (1 BTC) --> Alice change2

So on the last hop Alice sends 5 BTC as payment to the exchange (to
deposit) and the remaining outputs go back to Alice as change. The
exchange can't see Alice's UTXOs that she just spent, and also can't see
Alice's change outputs.


Additionally, even in the example you use where 12 times as much block
space is used as normal, this is still cheaper than Equal-Output
Coinjoins. For example with JoinMarket a single CoinJoin is
approximately 12 times bigger than a regular bitcoin transaction, and to
get good privacy using JoinMarket's tumbler algorithm the user typically
creates 7-15 of those CoinJoins. And even then those CoinJoins are very
obvious and don't improve the privacy of people who don't use them,
meaning we have to advocate the expensive and impractical slogan "make
every spend a CoinJoin". And they also don't provide as much privacy as
CoinSwap would, because their anonymity set is smaller than CoinSwap's.


Finally, we know that blockchains don't scale, and so its widely
expected that most day-to-day bitcoin transactions will happen off-chain
on something like Lightning network, which also brings us privacy.
CoinSwap then is mostly useful for the situations where on-chain
transfers are still needed, and also because good on-chain privacy is
necessary for Lightning to really be private, because otherwise the
on-chain channel UTXOs can be tracked.

Re: [bitcoin-dev] Design for a CoinSwap implementation for massively improving Bitcoin privacy and fungibility

[Jonas Nick]

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