public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
* [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap
@ 2020-08-11 12:05 Chris Belcher
  2020-08-20 11:17 ` ZmnSCPxj
                   ` (2 more replies)
  0 siblings, 3 replies; 24+ messages in thread
From: Chris Belcher @ 2020-08-11 12:05 UTC (permalink / raw)
  To: bitcoin-dev

I'm currently working on implementing CoinSwap (see my other email
"Design for a CoinSwap implementation for massively improving Bitcoin
privacy and fungibility").

CoinSwaps are special because they look just like regular bitcoin
transactions, so they improve the privacy even for people who do not use
them. Once CoinSwap is deployed, anyone attempting surveillance of
bitcoin transactions will be forced to ask themselves the question: how
do we know this transaction wasn't a CoinSwap?

This email contains a detailed design of the first protocol version. It
makes use of the building blocks of multi-transaction CoinSwaps, routed
CoinSwaps, liquidity market, private key handover, and fidelity bonds.
It does not include PayJoin-with-CoinSwap, but that's in the plan to be
added later.

== Routed CoinSwap ==

Diagram of CoinSwaps in the route:

    Alice ====> Bob ====> Charlie ====> Alice

Where (====>) means one CoinSwap. Alice gives coins to Bob, who gives
coins to Charlie, who gives coins to Alice. Alice is the market taker
and she starts with the hash preimage. She chooses the CoinSwap amount
and chooses who the makers will be.

This design has one market taker and two market makers in its route, but
it can easily be extended to any number of makers.

== Multiple transactions ==

Each single CoinSwap is made up of multiple transactions to avoid amount
correlation

          (a0 BTC) --->     (b0 BTC) --->         (c0 BTC) --->
    Alice (a1 BTC) ---> Bob (b1 BTC) ---> Charlie (c1 BTC) ---> Alice
          (a2 BTC) --->     (b2 BTC) --->         (c2 BTC) --->

The arrow (--->) represent funding transactions. The money gets paid to
a 2-of-2 multisig but after the CoinSwap protocol and private key
handover is done they will be controlled by the next party in the route.

This example has 6 regular-sized transactions which use approximately
the same amount of block space as a single JoinMarket coinjoin with 6
parties (1 taker, 5 makers). Yet the privacy provided by this one
CoinSwap would be far far greater. It would not have to be repeated in
the way that Equal-Output CoinJoins must be.

== Direct connections to Alice ===

Only Alice, the taker, knows the entire route, Bob and Charlie just know
their previous and next transactions. Bob and Charlie do not have direct
connections with each other, only with Alice.

Diagram of Tor connections:

    Bob      Charlie
     |       /
     |      /
     |     /
      Alice

When Bob and Charlie communicate, they are actually sending and
receiving messages via Alice who relays them to Charlie or Bob. This
helps hide whether the previous or next counterparty in a CoinSwap route
is a maker or taker.

This doesn't have security issues even in the final steps where private
keys are handed over, because those private keys are always for 2-of-2
multisig and so on their own are never enough to steal money.


=== Miner fees ===

Makers have no incentive to pay any miner fees. They only do
transactions which earn them an income and are willing to wait a very
long time for that to happen. By contrast takers want to create
transactions far more urgently. In JoinMarket we coded a protocol where
the maker could contribute to miner fees, but the market price offered
of that trended towards zero. So the reality is that takers will pay all
the miner fees. Also because makers don't know the taker's time
preference they don't know how much they should pay in miner fees.

The taker will have to set limits on how large the maker's transactions
are, otherwise makers could abuse this by having the taker consolidate
maker's UTXOs for free.

== Funding transaction definitions ==

Funding transactions are those which pay into the 2-of-2 multisig addresses.

Definitions:
I = initial coinswap amount sent by Alice = a0 + a1 + a2
(WA, WB, WC) = Total value of UTXOs being spent by Alice, Bob, Charlie
               respectively. Could be called "wallet Alice", "wallet
               Bob", etc
(B, C) = Coinswap fees paid by Alice and earned by Bob and Charlie.
(M1, M2, M3) = Miner fees of the first, second, third, etc sets of
               funding transactions. Alice will choose what these are
               since she's paying.
multisig(A+B) = A 2of2 multisig output with private keys held by A and B

The value in square parentheses refers to the bitcoin amount.

Alice funding txes
  [WA btc] ---> multisig (Alice+Bob) [I btc]
                change [WA-M1-I btc]
Bob funding txes
  [WB btc] ---> multisig (Bob+Charlie) [I-M2-B btc]
                change [WB-I+B btc]
Charlie funding txes
  [WC btc] ---> multisig (Charlie+Alice) [(I-M2-B)-M3-C btc]
                change [WC-(I-M2-B)+C btc]

Here we've drawn these transactions as single transactions, but they are
actually multiple transactions where the outputs add up some value (e.g.
add up to I in Alice's transactions.)

=== Table of balances before and after a successful CoinSwap ===

If a CoinSwap is successful then all the multisig outputs in the funding
transactions will become controlled unilaterally by one party. We can
calculate how the balances of each party change.

Party   | Before | After
--------|--------|-------------------------------------------
Alice   | WA     | WA-M1-I + (I-M2-B)-M3-C  = WA-M1-M2-M3-B-C
Bob     | WB     | WB-I+B + I               = WB+B
Charlie | WC     | WC-(I-M2-B)+C + I-M2-B   = WC+C

After a successful coinswap, we see Alice's balance goes down by the
miner fees and the coinswap fees. Bob's and Charlie's balance goes up by
their coinswap fees.

== Contract transaction definitions ==

Contract transactions are those which may spend from the 2-of-2 multisig
outputs, they transfer the coins into a contract where the coins can be
spent either by waiting for a timeout or providing a hash preimage
value. Ideally contract transactions will never be broadcast but their
existence keeps all parties honest.

M~ is miner fees, which we treat as a random variable, and ultimately
set by whichever pre-signed RBF tx get mined. When we talk about _the_
contract tx, we actually mean perhaps 20-30 transactions which only
differ by the miner fee and have RBF enabled, so they can be broadcasted
in sequence to get the contract transaction mined regardless of the
demand for block space.

(Alice+timelock_A OR Bob+hash) = Is an output which can be spent
                                 either with Alice's private key
                                 after waiting for a relative
                                 timelock_A, or by Bob's private key by
                                 revealing a hash preimage value

Alice contract tx:
    multisig (Alice+Bob) ---> (Alice+timelock_A OR Bob+hash)
    [I btc]                   [I-M~ btc]
Bob contract tx:
    multisig (Bob+Charlie) ---> (Bob+timelock_B OR Charlie+hash)
    [I-M2-B btc]                [I-M2-B-M~ btc]
Charlie contract tx:
    multisig (Charlie+Alice)  ---> (Charlie+timelock_C OR Alice+hash)
    [(I-M2-B)-M3-C btc]            [(I-M2-B)-M3-C-M~ btc]


=== Table of balances before/after CoinSwap using contracts transactions ===

In this case the parties had to get their money back by broadcasting and
mining the contract transactions and waiting for timeouts.

Party   | Before | After
--------|--------|--------------------------------------------
Alice   | WA     | WA-M1-I + I-M~                   = WA-M1-M~
Bob     | WB     | WB-I+B + I-M2-B-M~               = WB-M2-M~
Charlie | WC     | WC-(I-M2-B)+C + (I-M2-B)-M3-C-M~ = WC-M3-M~

In the timeout failure case, every party pays for their own miner fees.
And nobody earns or spends any coinswap fees. So even for a market maker
its possible for their wallet balance to go down sometimes, although as
we shall see there are anti-DOS features which make this unlikely to
happen often.

A possible attack by a malicious Alice is that she chooses M1 to be very
low (e.g. 1 sat/vbyte) and sets M2 and M3 to be very high (e.g. 1000
sat/vb) and then intentionally aborts, forcing the makers to lose much
more money in miner fees than the attacker. The attack can be used to
waste away Bob's and Charlie's coins on miner fees at little cost to the
malicious taker Alice. So to defend against this attack Bob and Charlie
must refuse to sign a contract transaction if the corresponding funding
transaction pays miner fees greater than Alice's funding transaction.


There can also be a failure case where each party gets their money using
hash preimage values instead of timeouts. Note that each party has to
sweep the output before the timeout expires, so that will cost an
additional miner fee M~.

Party   | Before | After
--------|--------|------------------------------------------------------
Alice   | WA     | WA-M1-I + (I-M2-B)-M3-C-M~ - M~ = WA-M1-M2-M3-B-C-2M~
Bob     | WB     | WB-I+B + I-M~ - M~              = WB+B-2M~
Charlie | WC     | WC-(I-M2-B)+C + I-M2-B-M~ - M~  = WC+C-2M~

In this situation the makers Bob and Charlie earn their CoinSwap fees,
but they pay an additional miner fee twice. Alice pays for all the
funding transaction miner fees, and the CoinSwap fees, and two
additional miner fees. And she had her privacy damaged because the
entire world saw on the blockchain the contract script.

Using the timelock path is like a refund, everyone's coin just comes
back to them. Using the preimage is like the CoinSwap transaction
happened, with the coins being sent ahead one hop. Again note that if
the preimage is used then coinswap fees are paid.

=== Staggered timelocks ===

The timelocks are staggered so that if Alice uses the preimage to take
coins then the right people will also learn the preimage and have enough
time to be able to get their coins back too. Alice starts with knowledge
of the hash preimage so she must have a longest timelock.

== EC tweak to reduce one round trip ==

When two parties are agreeing on a 2-of-2 multisig address, they need to
agree on their public keys. We can avoid one round trip by using the EC
tweak trick.

When Alice, the taker, downloads the entire offer book for the liquidity
market, the offers will also contain a EC public key. Alice can tweak
this to generate a brand new public key for which the maker knows the
private key. This public key will be one of the keys in the 2-of-2
multisig. This feature removes one round trip from the protocol.

    q = EC privkey generated by maker
    Q = q.G = EC pubkey published by maker

    p = nonce generated by taker
    P = p.G = nonce point calculated by taker

    R = Q + P = pubkey used in bitcoin transaction
      = (q + p).G

Taker sends unsigned transaction which pays to multisig using pubkey Q,
and also sends nonce p. The maker can use nonce p to calculate (q + p)
which is the private key of pubkey R.

Taker doesnt know the privkey because they are unable to find q because
of the ECDLP.

Any eavesdropper can see the nonce p and easily calculate the point R
too but Tor communication is encrypted so this isnt a concern.

None of the makers in the route know each other's Q values, so Alice the
taker will generate a nonce p on their behalf and send it over. I
believe this cant be used for any kind of attack, because the signing
maker will always check that the nonce results in the public key
included in the transaction they're signing, and they'll never sign a
transaction not in their interests.


== Protocol ==

This section is the most important part of this document.

Definitions:
fund = all funding txes (remember in this multi-tx protocol there can be
       multiple txes which together make up the funding)
A htlc = all htlc contract txes (fully signed) belonging to party A
A unsign htcl = all unsigned htlc contract txes belonging to party A
                including the nonce point p used to calculate the
                maker's pubkey.
p = nonce point p used in the tweak EC protocol for calculating the
    maker's pubkey
A htlc B/2 = Bob's signature for the 2of2 multisig of the Alice htlc
             contract tx
privA(A+B) = private key generated by Alice in the output
             multisig (Alice+Bob)


 | Alice           | Bob             | Charlie         |
 |=================|=================|=================|
0. A unsign htlc ---->               |                 |
1.               <---- A htlc B/2    |                 |
2. ***** BROADCAST AND MINE ALICE FUNDING TXES ******  |
3. A fund+htlc+p ---->               |                 |
4.                 | B unsign htlc ---->               |
5.                 |               <---- B htlc C/2    |
6. ******* BROADCAST AND MINE BOB FUNDING TXES ******* |
7.                 | B fund+htlc+p ---->               |
8.               <---------------------- C unsign htlc |
9.    C htlc A/2 ---------------------->               |
A. ***** BROADCAST AND MINE CHARLIE FUNDING TXES ***** |
B.               <---------------------- C fund+htlc+p |
C. hash preimage ---------------------->               |
D. hash preimage ---->               |                 |
E.    privA(A+B) ---->               |                 |
F.                 |    privB(B+C) ---->               |
G.               <---------------------- privC(C+A)    |

== Protocol notes ==
0-2 are the steps which setup Alice's funding tx and her contract tx for
    possible refund
4-5 same as 0-2 but for Bob
8-9 same as 0-2 but for Charlie
3,7 is proof to the next party that the previous party has already
    committed miner fees to getting a transaction mined, and therefore
    this isnt a DOS attack. The step also reveals the fully-signed
    contract transaction which the party can use to get their money back
    with a preimage.
C-G is revealing the hash preimage to all, and handing over the private
    keys


== Analysis of aborts ==

We will now discuss aborts, which happen when one party halts the
protocol and doesnt continue. Perhaps they had a power cut, their
internet broke, or they're a malicious attacker wanting to waste time
and money. The other party may try to reestablish a connection for some
time, but eventually must give up.

Number refers to the step number where the abort happened
e.g. step 1 means that the party aborted instead of the action happening
on protocol step 1.

The party name refers to what that party does
e.g. Party1: aborts, Party2/Party3: does a thing in reaction

0. Alice: aborts. Bob/Charlie: do nothing, they havent lost any time or
   money
1. Bob: aborts. Alice: lost no time or money, try with another Bob.
   Charlie: do nothing
2-3. same as 0.
4. Bob: aborts. Charlie: do nothing. Alice: broadcasts her contract tx
   and waits for the timeout, loses time and money on miner fees, she'll
   never coinswap with Bob's fidelity bond again.
5. Charlie: aborts. Alice/Bob: lose nothing, find another Charlie to
   coinswap with.
6. same as 4.
7. similar to 4 but Alice MIGHT not blacklist Bob's fidelity bond,
   because Bob will also have to broadcast his contract tx and will also
   lose time and money.
8. Charlie: aborts. Bob: broadcast his contract transaction and wait for
   the timeout to get his money back, also broadcast Alice's contract
   transaction in retaliation. Alice: waits for the timeout on her htlc
   tx that Bob broadcasted, will never do a coinswap with Charlie's
   fidelity bond again.
9. Alice: aborts. Charlie: do nothing, no money or time lost. Bob:
   broadcast bob contract tx and wait for timeout to get money back,
   comforted by the knowledge that when Alice comes back online she'll
   have to do the same thing and waste the same amount of time and
   money.
A-B. same as 8.
C-E. Alice: aborts. Bob/Charlie: all broadcast their contract txes and
     wait for the timeout to get their money back, or if Charlie knows
     the preimage he uses it to get the money immediately, which Bob can
     read from the blockchain and also use.
F. Bob: aborts. Alice: broadcast Charlie htlc tx and use preimage to get
   money immediately, Alice blacklists Bob's fidelity bond. Charlie:
   broadcast Bob htlc and use preimage to get money immediately.
G. Charlie: aborts. Alice: broadcast Charlie htlc and use preimage to
   get money immediately, Alice blacklists Charlie's fidelity bond. Bob:
   does nothing, already has his privkey.

==== Retaliation as DOS-resistance ====

In some situations (e.g. step 8.) if one maker in the coinswap route is
the victim of a DOS they will retaliate by DOSing the previous maker in
the route. This may seem unnecessary and unfair (after all why waste
even more time and block space) but is actually the best way to resist
DOS because it produces a concrete cost every time a DOS happens.


== Analysis of deviations ==

This section discusses what happens if one party deviates from the
protocol by doing something else, for example broadcasting a htlc
contract tx when they shouldnt have.

The party name refers to what that party does, followed by other party's
reactions to it.
e.g. Party1: does a thing, Party2/Party3: does a thing in reaction

If multiple deviations are possible in a step then they are numbered
e.g. A1 A2 A2 etc


0-2. Alice/Bob/Charlie: nothing else is possible except following the
     protocol or aborting
3. Alice: broadcasts one or more of the A htlc txes. Bob/Charlie/Dennis:
   do nothing, they havent lost any time or money.
4-6. Bob/Charlie: nothing else is possible except following the protocol
     or aborting.
7. Bob: broadcasts one or more of the B htlc txes, Alice: broadcasts all
   her own A htlc txes and waits for the timeout to get her money back.
   Charlie: do nothing
8. Charlie: nothing else is possible except following the protocol or
   aborting.
9. Alice: broadcasts one or more of the A htlc txes. Bob: broadcasts all
   his own A htlc txes and waits for the timeout.
A. same as 8.
B. Charlie: broadcasts one or more of the C htlc txes, Alice/Bob:
   broadcasts all their own htlc txes and waits for the timeout to get
   their money back.
C-E1. Alice: broadcasts all of C htlc txes and uses her knowledge of the
      preimage hash to take the money immediately. Charlie: broadcasts
      all of B htlc txes and reading the hash value from the blockchain,
      uses it to take the money from B htlc immediately. Bob: broadcasts
      all of A htlc txes, and reading hash from the blockchain, uses it
      to take the money from A htlc immediately.
C-E2. Alice: broadcast her own A htlc txes, and after a timeout take the
      money. Bob: broadcast his own B htlc txes and after the timeout
      take their money. Charlie: broadcast his own C htlc txes and after
      the timeout take their money.
F1. Bob: broadcast one or more of A htcl txes and use the hash preimage
    to get the money immediately. He already knows both privkeys of the
    multisig so this is pointless and just damages privacy and wastes
    miner fees. Alice: blacklist Bob's fidelity bond.
F2. Bob: broadcast one or more of the C htlc txes. Charlie: use preimage
    to get his money immediately. Bob's actions were pointless. Alice:
    cant tell whether Bob or Charlie actually broadcasted, so blacklist
    both fidelity bonds.
G1. Charlie: broadcast one or more of B htcl txes and use the hash
    preimage to get the money immediately. He already knows both
    privkeys of the multisig so this is pointless and just damages
    privacy and wastes miner fees. Alice: cant tell whether Bob or
    Charlie actually broadcasted, so blacklist both fidelity bonds.
G2. Charlie: broadcast one or more of the A htlc txes. Alice: broadcast
    the remaining A htlc txes and use preimage to get her money
    immediately. Charlies's actions were pointless. Alice: blacklist
    Charlie's fidelity bond.

The multisig outputs of the funding transactions can stay unspent
indefinitely. However the parties must always be watching the network
and ready to respond with their own sweep using a preimage. This is
because the other party still possesses a fully-signed contract tx. The
parties respond in the same way as in steps C-E1, F2 and G2. Alice's
reaction of blacklisting both fidelity bonds might not be the right way,
because one maker could use it to get another one blacklisted (as well
as themselves).


== Conclusion ==

This document describes the first version of the protocol which
implements multi-transaction Coinswap, routed Coinswap, fidelity bonds,
a liquidity market and private key handover. I describe the protocol and
also analyze aborts of the protocols and deviations from the protocol.



^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap
  2020-08-11 12:05 [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap Chris Belcher
@ 2020-08-20 11:17 ` ZmnSCPxj
  2020-08-20 15:28   ` Nadav Kohen
  2020-08-20 22:15   ` Chris Belcher
  2020-08-24 19:30 ` Antoine Riard
  2020-10-03 10:36 ` [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap appendium Chris Belcher
  2 siblings, 2 replies; 24+ messages in thread
From: ZmnSCPxj @ 2020-08-20 11:17 UTC (permalink / raw)
  To: Chris Belcher, Bitcoin Protocol Discussion

Good morning Chris,

Great to see this!

Mostly minor comments.



>
> == Direct connections to Alice ===
>
> Only Alice, the taker, knows the entire route, Bob and Charlie just know
> their previous and next transactions. Bob and Charlie do not have direct
> connections with each other, only with Alice.
>
> Diagram of Tor connections:
>
> Bob Charlie
> | /
> | /
> | /
> Alice
>
> When Bob and Charlie communicate, they are actually sending and
> receiving messages via Alice who relays them to Charlie or Bob. This
> helps hide whether the previous or next counterparty in a CoinSwap route
> is a maker or taker.
>
> This doesn't have security issues even in the final steps where private
> keys are handed over, because those private keys are always for 2-of-2
> multisig and so on their own are never enough to steal money.

This has a massive advantage over CoinJoin.

In CoinJoin, since all participants sign a single transaction, every participant knows the total number of participants.
Thus, in CoinJoin, it is fairly useless to have just one taker and one maker, the maker knows exactly which output belongs to the taker.
Even if all communications were done via the single paying taker, the maker(s) are shown the final transaction and thus can easily know how many participants there are (by counting the number of equal-valued outputs).

With CoinSwap, in principle no maker has to know how many other makers are in the swap.

Thus it would still be useful to make a single-maker CoinSwap, as that would be difficult, for the maker, to diferentiate from a multi-maker CoinSwap.

There are still a few potential leaks though:

* If paying through a CoinSwap, the cheapest option for the taker would be to send out a single large UTXO (single-output txes) to the first maker, and then demand the final payment and any change as two separate swaps from the final maker.
  * Intermediate makers are likely to not have exact amounts, thus is unlikely to create a single-output tx when forwarding.
  * Thus, the first maker could identify the taker.
* The makers can try timing the communications lag with the taker.
  The general assumption would be that more makers == more delay in taker responses.



>
> === Miner fees ===
>
> Makers have no incentive to pay any miner fees. They only do
> transactions which earn them an income and are willing to wait a very
> long time for that to happen. By contrast takers want to create
> transactions far more urgently. In JoinMarket we coded a protocol where
> the maker could contribute to miner fees, but the market price offered
> of that trended towards zero. So the reality is that takers will pay all
> the miner fees. Also because makers don't know the taker's time
> preference they don't know how much they should pay in miner fees.
>
> The taker will have to set limits on how large the maker's transactions
> are, otherwise makers could abuse this by having the taker consolidate
> maker's UTXOs for free.

Why not have the taker pay for the *first* maker-spent UTXO and have additional maker-spent UTXOs paid for by the maker?
i.e. the taker indicates "swap me 1 BTC in 3 bags of 0.3, 0.3, and 0.4 BTC", and pays for one UTXO spent for each "bag" (thus pays for 3 UTXOs).

Disagreements on feerate can be resolved by having the taker set the feerate, i.e. "the customer is always right".
Thus if the maker *has to* spend two UTXOs to make up the 0.4 BTC bag, it pays for the mining fees for that extra UTXO.
The maker can always reject the swap attempt if it *has to* spend multiple UTXOs and would lose money doing so if the taker demands a too-high feerate.


> == Contract transaction definitions ==
>
> Contract transactions are those which may spend from the 2-of-2 multisig
> outputs, they transfer the coins into a contract where the coins can be
> spent either by waiting for a timeout or providing a hash preimage
> value. Ideally contract transactions will never be broadcast but their
> existence keeps all parties honest.
>
> M~ is miner fees, which we treat as a random variable, and ultimately
> set by whichever pre-signed RBF tx get mined. When we talk about the
> contract tx, we actually mean perhaps 20-30 transactions which only
> differ by the miner fee and have RBF enabled, so they can be broadcasted
> in sequence to get the contract transaction mined regardless of the
> demand for block space.

The highest-fee version could have, in addition, CPFP-anchor outputs, like those being proposed in Lightning, so even if onchain fees rise above the largest fee reservation, it is possible to add even more fees.

Or not.
Hmm.


Another thought: later you describe that miner fees are paid by Alice by forwarding those fees as well, how does that work when there are multiple versions of the contract transaction?

>
> (Alice+timelock_A OR Bob+hash) = Is an output which can be spent
> either with Alice's private key
> after waiting for a relative
> timelock_A, or by Bob's private key by
> revealing a hash preimage value

The rationale for relative timelocks is that it makes private key turnover slightly more useable by ensuring that, after private key turnover, it is possible to wait indefinitely to spend the UTXO it received.
This is in contrast with absolute timelocks, where after private key turnover, it is required to spend received UTXO before the absolute timeout.

The dangers are:

* Until it receives the private key, if either of the incoming or outgoing contract transactions are confirmed, every swap participant (taker or maker) should also broadcast the other contract transaction, and resolve by onchain transactions (with loss of privacy).
* After receiving the private key, if the incoming contract transaction is confirmed, it should spend the resulting contract output.
* It is possible to steal from a participant if that participant goes offline longer than the timeout.
  This may imply that there may have to be some minimum timeout that makers indicate in their advertisements.
  * The taker can detect if the first maker is offline, then if it is offline, try a contract transaction broadcast, if it confirms, the taker can wait for the timeout; if it times out, the taker can clawback the transaction.
    * This appears to be riskless for the taker.
    * Against a similar attack, Lightning requires channel reserves, which means the first hop never gains control of the entire value, which is a basic requirement for private key turnover.
  * On the other hand, the taker has the largest timeout before it can clawback the funds, so it would wait for a long time, and at any time in between the first maker can come online and spend using the hashlock branch.
    * But the taker can just try on the hope it works; it has nothing to lose.
  * This attack seems to be possible only for the taker to mount.
    Other makers on the route cannot know who the other makers are, without cooperation of the taker, who is the only one who knows all the makers.
    * On the other hand, the last maker in the route has an outgoing HTLC with the smallest timelock, so it is the least-risk and therefore a maker who notices its outgoing HTLC has a low timeout might want to just do this anyway even if it is unsure if the taker is offline.
  * Participants might want to spend from the UTXO to a new address after private key turnover anyway.
    Makers could spend using a low-fee RBF-enabled tx, and when another request comes in for another swap, try to build a new funding tx with a higher-fee bump.


> A possible attack by a malicious Alice is that she chooses M1 to be very
> low (e.g. 1 sat/vbyte) and sets M2 and M3 to be very high (e.g. 1000
> sat/vb) and then intentionally aborts, forcing the makers to lose much
> more money in miner fees than the attacker. The attack can be used to
> waste away Bob's and Charlie's coins on miner fees at little cost to the
> malicious taker Alice. So to defend against this attack Bob and Charlie
> must refuse to sign a contract transaction if the corresponding funding
> transaction pays miner fees greater than Alice's funding transaction.

Sorry, I do not follow the logic for this...?

> The timelocks are staggered so that if Alice uses the preimage to take
> coins then the right people will also learn the preimage and have enough
> time to be able to get their coins back too. Alice starts with knowledge
> of the hash preimage so she must have a longest timelock.

More precisely:

* The HTLC outgoing from Alice has the longest timelock.
* The HTLC incoming into Alice has the shortest timelock.

For the makers, they only need to ensure that the incoming timelock is much larger than the outgoing timelock.


>
> == EC tweak to reduce one round trip ==
>
> When two parties are agreeing on a 2-of-2 multisig address, they need to
> agree on their public keys. We can avoid one round trip by using the EC
> tweak trick.
>
> When Alice, the taker, downloads the entire offer book for the liquidity
> market, the offers will also contain a EC public key. Alice can tweak
> this to generate a brand new public key for which the maker knows the
> private key. This public key will be one of the keys in the 2-of-2
> multisig. This feature removes one round trip from the protocol.
>
> q = EC privkey generated by maker
> Q = q.G = EC pubkey published by maker
>
> p = nonce generated by taker
> P = p.G = nonce point calculated by taker
>
> R = Q + P = pubkey used in bitcoin transaction
> = (q + p).G

Whoa whoa whoa whoa.

All this time I was thinking you were going to use 2p-ECDSA for all 2-of-2s.
In which case, the private key generated by the taker would be sufficient tweak to blind this.

In 2p-ECDSA, for two participants M = m * G; T = t * G, the total key is m * t * G = m * T = t * M.

Are you going to use `2 <T> <Q+P> 2 OP_CHECKMULTISIG` instead of 2p-ECDSA?
Note that you cannot usefully hide among Lightning mutual closes, because of the reserve; Lightning mutual closes are very very likely to be spent in a 1-input (that spends from a 2-of-2 P2WSH), 2-output (that pays to two P2WPKHs) tx.

>
> == Protocol ==

> ---8<------

The protocol looks correct to me.

LOL.

Give me a little more time to check it in detail hahaha.



>     ==== Retaliation as DOS-resistance ====
>
>     In some situations (e.g. step 8.) if one maker in the coinswap route is
>     the victim of a DOS they will retaliate by DOSing the previous maker in
>     the route. This may seem unnecessary and unfair (after all why waste
>     even more time and block space) but is actually the best way to resist
>     DOS because it produces a concrete cost every time a DOS happens.

I agree.

>
>     == Analysis of deviations ==
>
>     This section discusses what happens if one party deviates from the
>     protocol by doing something else, for example broadcasting a htlc
>     contract tx when they shouldnt have.
>
>     The party name refers to what that party does, followed by other party's
>     reactions to it.
>     e.g. Party1: does a thing, Party2/Party3: does a thing in reaction
>
>     If multiple deviations are possible in a step then they are numbered
>     e.g. A1 A2 A2 etc
>
>     0-2. Alice/Bob/Charlie: nothing else is possible except following the
>     protocol or aborting
>
> 8.  Alice: broadcasts one or more of the A htlc txes. Bob/Charlie/Dennis:
>     do nothing, they havent lost any time or money.
>     4-6. Bob/Charlie: nothing else is possible except following the protocol
>     or aborting.
>
> 9.  Bob: broadcasts one or more of the B htlc txes, Alice: broadcasts all
>     her own A htlc txes and waits for the timeout to get her money back.
>     Charlie: do nothing
>
> 10.  Charlie: nothing else is possible except following the protocol or
>     aborting.
>
> 11.  Alice: broadcasts one or more of the A htlc txes. Bob: broadcasts all
>     his own A htlc txes and waits for the timeout.
>     A. same as 8.
>     B. Charlie: broadcasts one or more of the C htlc txes, Alice/Bob:
>     broadcasts all their own htlc txes and waits for the timeout to get
>     their money back.
>     C-E1. Alice: broadcasts all of C htlc txes and uses her knowledge of the
>     preimage hash to take the money immediately. Charlie: broadcasts
>     all of B htlc txes and reading the hash value from the blockchain,
>     uses it to take the money from B htlc immediately. Bob: broadcasts
>     all of A htlc txes, and reading hash from the blockchain, uses it
>     to take the money from A htlc immediately.
>     C-E2. Alice: broadcast her own A htlc txes, and after a timeout take the
>     money. Bob: broadcast his own B htlc txes and after the timeout
>     take their money. Charlie: broadcast his own C htlc txes and after
>     the timeout take their money.
>     F1. Bob: broadcast one or more of A htcl txes and use the hash preimage
>     to get the money immediately. He already knows both privkeys of the
>     multisig so this is pointless and just damages privacy and wastes
>     miner fees. Alice: blacklist Bob's fidelity bond.
>     F2. Bob: broadcast one or more of the C htlc txes. Charlie: use preimage
>     to get his money immediately. Bob's actions were pointless. Alice:
>     cant tell whether Bob or Charlie actually broadcasted, so blacklist
>     both fidelity bonds.
>     G1. Charlie: broadcast one or more of B htcl txes and use the hash
>     preimage to get the money immediately. He already knows both
>     privkeys of the multisig so this is pointless and just damages
>     privacy and wastes miner fees. Alice: cant tell whether Bob or
>     Charlie actually broadcasted, so blacklist both fidelity bonds.
>     G2. Charlie: broadcast one or more of the A htlc txes. Alice: broadcast
>     the remaining A htlc txes and use preimage to get her money
>     immediately. Charlies's actions were pointless. Alice: blacklist
>     Charlie's fidelity bond.
>
>     The multisig outputs of the funding transactions can stay unspent
>     indefinitely. However the parties must always be watching the network
>     and ready to respond with their own sweep using a preimage. This is
>     because the other party still possesses a fully-signed contract tx. The
>     parties respond in the same way as in steps C-E1, F2 and G2. Alice's
>     reaction of blacklisting both fidelity bonds might not be the right way,
>     because one maker could use it to get another one blacklisted (as well
>     as themselves).

Looks OK, though note that a participant might try to do so (as pointed out above) in the hope that the next participant is offline.

Thank you very much for your writeup!

Regards,
ZmnSCPxj


^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap
  2020-08-20 11:17 ` ZmnSCPxj
@ 2020-08-20 15:28   ` Nadav Kohen
  2020-08-20 21:38     ` ZmnSCPxj
  2020-08-20 22:15   ` Chris Belcher
  1 sibling, 1 reply; 24+ messages in thread
From: Nadav Kohen @ 2020-08-20 15:28 UTC (permalink / raw)
  To: ZmnSCPxj, Bitcoin Protocol Discussion

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

Hey Chris and all,

Looking good :) I have one major concern though

>    q = EC privkey generated by maker
>    Q = q.G = EC pubkey published by maker
>
>    p = nonce generated by taker
>    P = p.G = nonce point calculated by taker
>
>    R = Q + P = pubkey used in bitcoin transaction
>      = (q + p).G

If I'm understanding this correctly (which I'm not sure I ame), it seems
like the plan is to put R on-chain as the key to an output? As stated this
is completely insecure as Q is known in advance so the taker can always
choose a nonce p but then claim that their nonce point is p.G - Q so that
the key that goes on-chain is (p.G - Q + Q) = p.G allowing them to steal
the funds. If the plan is not to use full-fledged 2-ECDSA (which I think is
actually necessary as I still don't understand how the HTLC signatures are
generated) you have to, at the very least, force the taker to provide a
Zero Knowledge Proof of Knowledge (ZKPoK) of the discrete log to the point
they advertise as their nonce point to avoid this. Alternatively, I think
you can use the following key as is done in MuSig:

R = H(Q || P || Q)*Q + H(Q || P || P)*P

But I still don't see how signatures can be generated for HTLCs from this
key.

Of course all of this complexity more or less goes away once we have
Schnorr signatures and can use MuSig with adaptor signatures.

Best,
Nadav

On Thu, Aug 20, 2020 at 6:17 AM ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Good morning Chris,
>
> Great to see this!
>
> Mostly minor comments.
>
>
>
> >
> > == Direct connections to Alice ===
> >
> > Only Alice, the taker, knows the entire route, Bob and Charlie just know
> > their previous and next transactions. Bob and Charlie do not have direct
> > connections with each other, only with Alice.
> >
> > Diagram of Tor connections:
> >
> > Bob Charlie
> > | /
> > | /
> > | /
> > Alice
> >
> > When Bob and Charlie communicate, they are actually sending and
> > receiving messages via Alice who relays them to Charlie or Bob. This
> > helps hide whether the previous or next counterparty in a CoinSwap route
> > is a maker or taker.
> >
> > This doesn't have security issues even in the final steps where private
> > keys are handed over, because those private keys are always for 2-of-2
> > multisig and so on their own are never enough to steal money.
>
> This has a massive advantage over CoinJoin.
>
> In CoinJoin, since all participants sign a single transaction, every
> participant knows the total number of participants.
> Thus, in CoinJoin, it is fairly useless to have just one taker and one
> maker, the maker knows exactly which output belongs to the taker.
> Even if all communications were done via the single paying taker, the
> maker(s) are shown the final transaction and thus can easily know how many
> participants there are (by counting the number of equal-valued outputs).
>
> With CoinSwap, in principle no maker has to know how many other makers are
> in the swap.
>
> Thus it would still be useful to make a single-maker CoinSwap, as that
> would be difficult, for the maker, to diferentiate from a multi-maker
> CoinSwap.
>
> There are still a few potential leaks though:
>
> * If paying through a CoinSwap, the cheapest option for the taker would be
> to send out a single large UTXO (single-output txes) to the first maker,
> and then demand the final payment and any change as two separate swaps from
> the final maker.
>   * Intermediate makers are likely to not have exact amounts, thus is
> unlikely to create a single-output tx when forwarding.
>   * Thus, the first maker could identify the taker.
> * The makers can try timing the communications lag with the taker.
>   The general assumption would be that more makers == more delay in taker
> responses.
>
>
>
> >
> > === Miner fees ===
> >
> > Makers have no incentive to pay any miner fees. They only do
> > transactions which earn them an income and are willing to wait a very
> > long time for that to happen. By contrast takers want to create
> > transactions far more urgently. In JoinMarket we coded a protocol where
> > the maker could contribute to miner fees, but the market price offered
> > of that trended towards zero. So the reality is that takers will pay all
> > the miner fees. Also because makers don't know the taker's time
> > preference they don't know how much they should pay in miner fees.
> >
> > The taker will have to set limits on how large the maker's transactions
> > are, otherwise makers could abuse this by having the taker consolidate
> > maker's UTXOs for free.
>
> Why not have the taker pay for the *first* maker-spent UTXO and have
> additional maker-spent UTXOs paid for by the maker?
> i.e. the taker indicates "swap me 1 BTC in 3 bags of 0.3, 0.3, and 0.4
> BTC", and pays for one UTXO spent for each "bag" (thus pays for 3 UTXOs).
>
> Disagreements on feerate can be resolved by having the taker set the
> feerate, i.e. "the customer is always right".
> Thus if the maker *has to* spend two UTXOs to make up the 0.4 BTC bag, it
> pays for the mining fees for that extra UTXO.
> The maker can always reject the swap attempt if it *has to* spend multiple
> UTXOs and would lose money doing so if the taker demands a too-high feerate.
>
>
> > == Contract transaction definitions ==
> >
> > Contract transactions are those which may spend from the 2-of-2 multisig
> > outputs, they transfer the coins into a contract where the coins can be
> > spent either by waiting for a timeout or providing a hash preimage
> > value. Ideally contract transactions will never be broadcast but their
> > existence keeps all parties honest.
> >
> > M~ is miner fees, which we treat as a random variable, and ultimately
> > set by whichever pre-signed RBF tx get mined. When we talk about the
> > contract tx, we actually mean perhaps 20-30 transactions which only
> > differ by the miner fee and have RBF enabled, so they can be broadcasted
> > in sequence to get the contract transaction mined regardless of the
> > demand for block space.
>
> The highest-fee version could have, in addition, CPFP-anchor outputs, like
> those being proposed in Lightning, so even if onchain fees rise above the
> largest fee reservation, it is possible to add even more fees.
>
> Or not.
> Hmm.
>
>
> Another thought: later you describe that miner fees are paid by Alice by
> forwarding those fees as well, how does that work when there are multiple
> versions of the contract transaction?
>
> >
> > (Alice+timelock_A OR Bob+hash) = Is an output which can be spent
> > either with Alice's private key
> > after waiting for a relative
> > timelock_A, or by Bob's private key by
> > revealing a hash preimage value
>
> The rationale for relative timelocks is that it makes private key turnover
> slightly more useable by ensuring that, after private key turnover, it is
> possible to wait indefinitely to spend the UTXO it received.
> This is in contrast with absolute timelocks, where after private key
> turnover, it is required to spend received UTXO before the absolute timeout.
>
> The dangers are:
>
> * Until it receives the private key, if either of the incoming or outgoing
> contract transactions are confirmed, every swap participant (taker or
> maker) should also broadcast the other contract transaction, and resolve by
> onchain transactions (with loss of privacy).
> * After receiving the private key, if the incoming contract transaction is
> confirmed, it should spend the resulting contract output.
> * It is possible to steal from a participant if that participant goes
> offline longer than the timeout.
>   This may imply that there may have to be some minimum timeout that
> makers indicate in their advertisements.
>   * The taker can detect if the first maker is offline, then if it is
> offline, try a contract transaction broadcast, if it confirms, the taker
> can wait for the timeout; if it times out, the taker can clawback the
> transaction.
>     * This appears to be riskless for the taker.
>     * Against a similar attack, Lightning requires channel reserves, which
> means the first hop never gains control of the entire value, which is a
> basic requirement for private key turnover.
>   * On the other hand, the taker has the largest timeout before it can
> clawback the funds, so it would wait for a long time, and at any time in
> between the first maker can come online and spend using the hashlock branch.
>     * But the taker can just try on the hope it works; it has nothing to
> lose.
>   * This attack seems to be possible only for the taker to mount.
>     Other makers on the route cannot know who the other makers are,
> without cooperation of the taker, who is the only one who knows all the
> makers.
>     * On the other hand, the last maker in the route has an outgoing HTLC
> with the smallest timelock, so it is the least-risk and therefore a maker
> who notices its outgoing HTLC has a low timeout might want to just do this
> anyway even if it is unsure if the taker is offline.
>   * Participants might want to spend from the UTXO to a new address after
> private key turnover anyway.
>     Makers could spend using a low-fee RBF-enabled tx, and when another
> request comes in for another swap, try to build a new funding tx with a
> higher-fee bump.
>
>
> > A possible attack by a malicious Alice is that she chooses M1 to be very
> > low (e.g. 1 sat/vbyte) and sets M2 and M3 to be very high (e.g. 1000
> > sat/vb) and then intentionally aborts, forcing the makers to lose much
> > more money in miner fees than the attacker. The attack can be used to
> > waste away Bob's and Charlie's coins on miner fees at little cost to the
> > malicious taker Alice. So to defend against this attack Bob and Charlie
> > must refuse to sign a contract transaction if the corresponding funding
> > transaction pays miner fees greater than Alice's funding transaction.
>
> Sorry, I do not follow the logic for this...?
>
> > The timelocks are staggered so that if Alice uses the preimage to take
> > coins then the right people will also learn the preimage and have enough
> > time to be able to get their coins back too. Alice starts with knowledge
> > of the hash preimage so she must have a longest timelock.
>
> More precisely:
>
> * The HTLC outgoing from Alice has the longest timelock.
> * The HTLC incoming into Alice has the shortest timelock.
>
> For the makers, they only need to ensure that the incoming timelock is
> much larger than the outgoing timelock.
>
>
> >
> > == EC tweak to reduce one round trip ==
> >
> > When two parties are agreeing on a 2-of-2 multisig address, they need to
> > agree on their public keys. We can avoid one round trip by using the EC
> > tweak trick.
> >
> > When Alice, the taker, downloads the entire offer book for the liquidity
> > market, the offers will also contain a EC public key. Alice can tweak
> > this to generate a brand new public key for which the maker knows the
> > private key. This public key will be one of the keys in the 2-of-2
> > multisig. This feature removes one round trip from the protocol.
> >
> > q = EC privkey generated by maker
> > Q = q.G = EC pubkey published by maker
> >
> > p = nonce generated by taker
> > P = p.G = nonce point calculated by taker
> >
> > R = Q + P = pubkey used in bitcoin transaction
> > = (q + p).G
>
> Whoa whoa whoa whoa.
>
> All this time I was thinking you were going to use 2p-ECDSA for all
> 2-of-2s.
> In which case, the private key generated by the taker would be sufficient
> tweak to blind this.
>
> In 2p-ECDSA, for two participants M = m * G; T = t * G, the total key is m
> * t * G = m * T = t * M.
>
> Are you going to use `2 <T> <Q+P> 2 OP_CHECKMULTISIG` instead of 2p-ECDSA?
> Note that you cannot usefully hide among Lightning mutual closes, because
> of the reserve; Lightning mutual closes are very very likely to be spent in
> a 1-input (that spends from a 2-of-2 P2WSH), 2-output (that pays to two
> P2WPKHs) tx.
>
> >
> > == Protocol ==
>
> > ---8<------
>
> The protocol looks correct to me.
>
> LOL.
>
> Give me a little more time to check it in detail hahaha.
>
>
>
> >     ==== Retaliation as DOS-resistance ====
> >
> >     In some situations (e.g. step 8.) if one maker in the coinswap route
> is
> >     the victim of a DOS they will retaliate by DOSing the previous maker
> in
> >     the route. This may seem unnecessary and unfair (after all why waste
> >     even more time and block space) but is actually the best way to
> resist
> >     DOS because it produces a concrete cost every time a DOS happens.
>
> I agree.
>
> >
> >     == Analysis of deviations ==
> >
> >     This section discusses what happens if one party deviates from the
> >     protocol by doing something else, for example broadcasting a htlc
> >     contract tx when they shouldnt have.
> >
> >     The party name refers to what that party does, followed by other
> party's
> >     reactions to it.
> >     e.g. Party1: does a thing, Party2/Party3: does a thing in reaction
> >
> >     If multiple deviations are possible in a step then they are numbered
> >     e.g. A1 A2 A2 etc
> >
> >     0-2. Alice/Bob/Charlie: nothing else is possible except following the
> >     protocol or aborting
> >
> > 8.  Alice: broadcasts one or more of the A htlc txes. Bob/Charlie/Dennis:
> >     do nothing, they havent lost any time or money.
> >     4-6. Bob/Charlie: nothing else is possible except following the
> protocol
> >     or aborting.
> >
> > 9.  Bob: broadcasts one or more of the B htlc txes, Alice: broadcasts all
> >     her own A htlc txes and waits for the timeout to get her money back.
> >     Charlie: do nothing
> >
> > 10.  Charlie: nothing else is possible except following the protocol or
> >     aborting.
> >
> > 11.  Alice: broadcasts one or more of the A htlc txes. Bob: broadcasts
> all
> >     his own A htlc txes and waits for the timeout.
> >     A. same as 8.
> >     B. Charlie: broadcasts one or more of the C htlc txes, Alice/Bob:
> >     broadcasts all their own htlc txes and waits for the timeout to get
> >     their money back.
> >     C-E1. Alice: broadcasts all of C htlc txes and uses her knowledge of
> the
> >     preimage hash to take the money immediately. Charlie: broadcasts
> >     all of B htlc txes and reading the hash value from the blockchain,
> >     uses it to take the money from B htlc immediately. Bob: broadcasts
> >     all of A htlc txes, and reading hash from the blockchain, uses it
> >     to take the money from A htlc immediately.
> >     C-E2. Alice: broadcast her own A htlc txes, and after a timeout take
> the
> >     money. Bob: broadcast his own B htlc txes and after the timeout
> >     take their money. Charlie: broadcast his own C htlc txes and after
> >     the timeout take their money.
> >     F1. Bob: broadcast one or more of A htcl txes and use the hash
> preimage
> >     to get the money immediately. He already knows both privkeys of the
> >     multisig so this is pointless and just damages privacy and wastes
> >     miner fees. Alice: blacklist Bob's fidelity bond.
> >     F2. Bob: broadcast one or more of the C htlc txes. Charlie: use
> preimage
> >     to get his money immediately. Bob's actions were pointless. Alice:
> >     cant tell whether Bob or Charlie actually broadcasted, so blacklist
> >     both fidelity bonds.
> >     G1. Charlie: broadcast one or more of B htcl txes and use the hash
> >     preimage to get the money immediately. He already knows both
> >     privkeys of the multisig so this is pointless and just damages
> >     privacy and wastes miner fees. Alice: cant tell whether Bob or
> >     Charlie actually broadcasted, so blacklist both fidelity bonds.
> >     G2. Charlie: broadcast one or more of the A htlc txes. Alice:
> broadcast
> >     the remaining A htlc txes and use preimage to get her money
> >     immediately. Charlies's actions were pointless. Alice: blacklist
> >     Charlie's fidelity bond.
> >
> >     The multisig outputs of the funding transactions can stay unspent
> >     indefinitely. However the parties must always be watching the network
> >     and ready to respond with their own sweep using a preimage. This is
> >     because the other party still possesses a fully-signed contract tx.
> The
> >     parties respond in the same way as in steps C-E1, F2 and G2. Alice's
> >     reaction of blacklisting both fidelity bonds might not be the right
> way,
> >     because one maker could use it to get another one blacklisted (as
> well
> >     as themselves).
>
> Looks OK, though note that a participant might try to do so (as pointed
> out above) in the hope that the next participant is offline.
>
> Thank you very much for your writeup!
>
> Regards,
> ZmnSCPxj
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap
  2020-08-20 15:28   ` Nadav Kohen
@ 2020-08-20 21:38     ` ZmnSCPxj
  2020-08-20 22:37       ` Chris Belcher
  0 siblings, 1 reply; 24+ messages in thread
From: ZmnSCPxj @ 2020-08-20 21:38 UTC (permalink / raw)
  To: Nadav Kohen; +Cc: Bitcoin Protocol Discussion

Good morning Nadav,

> Hey Chris and all,
>
> Looking good :) I have one major concern though
>
> >    q = EC privkey generated by maker
> >    Q = q.G = EC pubkey published by maker
> >
> >    p = nonce generated by taker
> >    P = p.G = nonce point calculated by taker
> >
> >    R = Q + P = pubkey used in bitcoin transaction
> >      = (q + p).G
>
> If I'm understanding this correctly (which I'm not sure I ame), it seems like the plan is to put R on-chain as the key to an output? As stated this is completely insecure as Q is known in advance so the taker can always choose a nonce p but then claim that their nonce point is p.G - Q so that the key that goes on-chain is (p.G - Q + Q) = p.G allowing them to steal the funds.

My reading from this is that nonce `p` has to be given by the taker to the maker outright.
In original post:

> Taker sends unsigned transaction which pays to multisig using pubkey Q,
> and also sends nonce p.

Thus, taker provides a proof-of-knowledge, i.e. the actual `p` scalar itself (not zero-knowledge, but what the maker needs is proof-of-knowledge, and could not care less if the proof is zero-knowledge or not).

On the other hand, I do not see the point of this tweak if you are going to use 2p-ECDSA, since my knowledge is that 2p-ECDSA uses the pubkey that is homomorphic to the product of the private keys.
And that pubkey is already tweaked, by the fresh privkey of the maker (and the maker is buying privacy and wants security of the swap, so is incentivized to generate high-entropy temporary privkeys for the actual swap operation).

Not using 2p-ECDSA of some kind would remove most of the privacy advantages of CoinSwap.
You cannot hide among `2 <A> <B> 2 OP_CHECKMULTISIG` scripts of Lightning, because:

* Lightning channel closes tend to be weeks at least after the funding outpoint creation, whereas CoinSwap envisions hours or days.
* Lightning mutual channel closes have a very high probability of spending to two P2WPKH addresses.

You need to hide among the much larger singlesig anonymity set, which means using a single signature (created multiparty by both participants), not two signatures (one from each participant).

Or is this intended for HTLCs in open-coded SCRIPTs `OP_DUP OP_IF OP_HASH160 <hash> OP_EQUAL <A> OP_ELSE <time> OP_CHECKSEQUENCEVERIFY OP_DROP <B> OP_ENDIF OP_CHECKSIG`?
This provides a slight privacy boost in a case (contract transaction publication) where most of the privacy is lost anyway.

Regards,
ZmnSCPxj


^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap
  2020-08-20 11:17 ` ZmnSCPxj
  2020-08-20 15:28   ` Nadav Kohen
@ 2020-08-20 22:15   ` Chris Belcher
  2020-08-21  4:20     ` ZmnSCPxj
  1 sibling, 1 reply; 24+ messages in thread
From: Chris Belcher @ 2020-08-20 22:15 UTC (permalink / raw)
  To: ZmnSCPxj, Bitcoin Protocol Discussion

Hello ZmnSCPxj,

Thanks for the review. My comments are inline.

On 20/08/2020 12:17, ZmnSCPxj wrote:
> Good morning Chris,
> 
> Great to see this!
> 
> Mostly minor comments.
> 
> 
> 
>>
>> == Direct connections to Alice ===
>>
>> Only Alice, the taker, knows the entire route, Bob and Charlie just know
>> their previous and next transactions. Bob and Charlie do not have direct
>> connections with each other, only with Alice.
>>
>> Diagram of Tor connections:
>>
>> Bob Charlie
>> | /
>> | /
>> | /
>> Alice
>>
>> When Bob and Charlie communicate, they are actually sending and
>> receiving messages via Alice who relays them to Charlie or Bob. This
>> helps hide whether the previous or next counterparty in a CoinSwap route
>> is a maker or taker.
>>
>> This doesn't have security issues even in the final steps where private
>> keys are handed over, because those private keys are always for 2-of-2
>> multisig and so on their own are never enough to steal money.
> 
> This has a massive advantage over CoinJoin.
> 
> In CoinJoin, since all participants sign a single transaction, every participant knows the total number of participants.
> Thus, in CoinJoin, it is fairly useless to have just one taker and one maker, the maker knows exactly which output belongs to the taker.
> Even if all communications were done via the single paying taker, the maker(s) are shown the final transaction and thus can easily know how many participants there are (by counting the number of equal-valued outputs).
> 
> With CoinSwap, in principle no maker has to know how many other makers are in the swap.
> 
> Thus it would still be useful to make a single-maker CoinSwap, as that would be difficult, for the maker, to diferentiate from a multi-maker CoinSwap.

Yes great point.

> There are still a few potential leaks though:
> 
> * If paying through a CoinSwap, the cheapest option for the taker would be to send out a single large UTXO (single-output txes) to the first maker, and then demand the final payment and any change as two separate swaps from the final maker.
>   * Intermediate makers are likely to not have exact amounts, thus is unlikely to create a single-output tx when forwarding.
>   * Thus, the first maker could identify the taker.

Right, so if the taker uses only a single maker then they must have more
than one UTXO.

This leak in the case of a taker spending a single UTXO also happens
when the taker needs to create a branching route. I described this in my
original email "Design for a CoinSwap implementation for massively
improving Bitcoin privacy and fungibility" under the section "Combining
multi-transaction with routing" (the second diagram).

I think this might be unavoidable. If the taker has just one UTXO they'd
be much better off using multiple makers for this reason.


> * The makers can try timing the communications lag with the taker.
>   The general assumption would be that more makers == more delay in taker responses.

Sounds like adding random delays would fix this. The protocol already
involves waiting for a confirmation (average waiting time 10 minutes, at
best) and might involve more confirmations for extra security and
privacy. So adding a random delay of up to 0.5-1 minutes shouldnt cause
too many issues.
Also the Tor network can be pretty laggy so that might add enough noise
anyway.

>>
>> === Miner fees ===
>>
>> Makers have no incentive to pay any miner fees. They only do
>> transactions which earn them an income and are willing to wait a very
>> long time for that to happen. By contrast takers want to create
>> transactions far more urgently. In JoinMarket we coded a protocol where
>> the maker could contribute to miner fees, but the market price offered
>> of that trended towards zero. So the reality is that takers will pay all
>> the miner fees. Also because makers don't know the taker's time
>> preference they don't know how much they should pay in miner fees.
>>
>> The taker will have to set limits on how large the maker's transactions
>> are, otherwise makers could abuse this by having the taker consolidate
>> maker's UTXOs for free.
> 
> Why not have the taker pay for the *first* maker-spent UTXO and have additional maker-spent UTXOs paid for by the maker?
> i.e. the taker indicates "swap me 1 BTC in 3 bags of 0.3, 0.3, and 0.4 BTC", and pays for one UTXO spent for each "bag" (thus pays for 3 UTXOs).
> 
> Disagreements on feerate can be resolved by having the taker set the feerate, i.e. "the customer is always right".
> Thus if the maker *has to* spend two UTXOs to make up the 0.4 BTC bag, it pays for the mining fees for that extra UTXO.
> The maker can always reject the swap attempt if it *has to* spend multiple UTXOs and would lose money doing so if the taker demands a too-high feerate.

Having the taker pay for just one UTXO will have an unfortunate side
effect of resulting in the maker's money being split up into a large
number of UTXOs, because every CoinSwap they take part in has an
incentive to increase their UTXO count by one. At the start of
JoinMarket this was an issue where then a taker wanting to CoinJoin a
large would come along and the result would be a huge CoinJoin
transaction with many many small inputs. Perhaps the taker could pay for
2-3 UTXOs to counteract this. (Of course the exact number would be
configurable by the taker user, but defaults usually don't get changed).

I'm still not convinced with having makers contribute to miner fees. In
JoinMarket we tried to get makers to contribute a little to miner fees
and simply they never did in any meaningful way. The market has spoken.
In terms of incentives makers are happy to wait a very long time, if we
assume they're just HODLers then even if they earn a few thousand
satoshis that's good.

>> == Contract transaction definitions ==
>>
>> Contract transactions are those which may spend from the 2-of-2 multisig
>> outputs, they transfer the coins into a contract where the coins can be
>> spent either by waiting for a timeout or providing a hash preimage
>> value. Ideally contract transactions will never be broadcast but their
>> existence keeps all parties honest.
>>
>> M~ is miner fees, which we treat as a random variable, and ultimately
>> set by whichever pre-signed RBF tx get mined. When we talk about the
>> contract tx, we actually mean perhaps 20-30 transactions which only
>> differ by the miner fee and have RBF enabled, so they can be broadcasted
>> in sequence to get the contract transaction mined regardless of the
>> demand for block space.
> 
> The highest-fee version could have, in addition, CPFP-anchor outputs, like those being proposed in Lightning, so even if onchain fees rise above the largest fee reservation, it is possible to add even more fees.
> 
> Or not.
> Hmm.

I think RBF transactions are better because they ultimately use less
block space than CPFP.

There seems to be very little cost in signing many additional
precomputed RBF transactions. So the taker and makers could sign
transactions all the way up to 10000 sat/vbyte. I think this doesn't
apply to Lightning, because bandwidth seems to be more constrained
there: even a tiny micropayment for 1 satoshi would require 10x or 100x
more bandwidth if every lightning htlc used precomputed RBF.

> Another thought: later you describe that miner fees are paid by Alice by forwarding those fees as well, how does that work when there are multiple versions of the contract transaction?

Alice only pays the miner fees for the funding transactions, not the
contract transaction. The miner fees for the contract transactions are
taken from the contract balance. The contract transactions are 1-input
1-output, and whoever ends up with the money will be the one who paid
the miner fee.

>> (Alice+timelock_A OR Bob+hash) = Is an output which can be spent
>> either with Alice's private key
>> after waiting for a relative
>> timelock_A, or by Bob's private key by
>> revealing a hash preimage value
> 
> The rationale for relative timelocks is that it makes private key turnover slightly more useable by ensuring that, after private key turnover, it is possible to wait indefinitely to spend the UTXO it received.
> This is in contrast with absolute timelocks, where after private key turnover, it is required to spend received UTXO before the absolute timeout.
> 
> The dangers are:
> 
> * Until it receives the private key, if either of the incoming or outgoing contract transactions are confirmed, every swap participant (taker or maker) should also broadcast the other contract transaction, and resolve by onchain transactions (with loss of privacy).
> * After receiving the private key, if the incoming contract transaction is confirmed, it should spend the resulting contract output.
> * It is possible to steal from a participant if that participant goes offline longer than the timeout.
>   This may imply that there may have to be some minimum timeout that makers indicate in their advertisements.
>   * The taker can detect if the first maker is offline, then if it is offline, try a contract transaction broadcast, if it confirms, the taker can wait for the timeout; if it times out, the taker can clawback the transaction.
>     * This appears to be riskless for the taker.
>     * Against a similar attack, Lightning requires channel reserves, which means the first hop never gains control of the entire value, which is a basic requirement for private key turnover.
>   * On the other hand, the taker has the largest timeout before it can clawback the funds, so it would wait for a long time, and at any time in between the first maker can come online and spend using the hashlock branch.
>     * But the taker can just try on the hope it works; it has nothing to lose.
>   * This attack seems to be possible only for the taker to mount.
>     Other makers on the route cannot know who the other makers are, without cooperation of the taker, who is the only one who knows all the makers.
>     * On the other hand, the last maker in the route has an outgoing HTLC with the smallest timelock, so it is the least-risk and therefore a maker who notices its outgoing HTLC has a low timeout might want to just do this anyway even if it is unsure if the taker is offline.

Every off-chain protocol like this has the livelyness requirement. Each
party must always be watching the chain and be ready to broadcast
something in response. I'm not sure how any of this relates to the
choice of relative vs absolute time locks.

You're right that attempting such an move by the taker is riskless, but
its not costless. The taker sets up the entire CoinSwap protocol because
they wanted more privacy; but if the taker broadcasts the Alice contract
transaction and waits for the timeout, then all they've achieved is
spent miner fees, got their own coin back and draw attention to it with
the unusual HTLC script. They've achieved no benefit from what I see, so
they won't do this. Any taker or maker who attempts anything like this
will be spending miner fees.

I also envision that makers will run their own personal "watchtowers",
similar to watchtowers in the lightning world, which would watch the
blockchain and be ready to broadcast a transaction. In terms of
incentives, makers are HODLers and we can expect them to protect their
stash very carefully by running perhaps multiple redundant watchtowers
in multiple locations and multiple networks. Therefore a taker noticing
that a maker's .onion is down does not imply that all the maker's
watchtowers are down.

Of course we will choose the timelocks to be long enough so that
everyone has enough time to broadcast a transaction in response, even in
times of congested mempools.

>   * Participants might want to spend from the UTXO to a new address after private key turnover anyway.
>     Makers could spend using a low-fee RBF-enabled tx, and when another request comes in for another swap, try to build a new funding tx with a higher-fee bump.

I don't think this will happen very often. It's spending money on block
space for not much benefit. If the maker ever decides to shut down their
maker they can transfer all their coins in HTLCs to single-sig
transactions exclusively controlled by them, but in normal operation I
doubt it will happen.


>> A possible attack by a malicious Alice is that she chooses M1 to be very
>> low (e.g. 1 sat/vbyte) and sets M2 and M3 to be very high (e.g. 1000
>> sat/vb) and then intentionally aborts, forcing the makers to lose much
>> more money in miner fees than the attacker. The attack can be used to
>> waste away Bob's and Charlie's coins on miner fees at little cost to the
>> malicious taker Alice. So to defend against this attack Bob and Charlie
>> must refuse to sign a contract transaction if the corresponding funding
>> transaction pays miner fees greater than Alice's funding transaction.
> 
> Sorry, I do not follow the logic for this...?

I'll try to explain again with an example, hopefully it clarifies.

Recall the table of balances before/after CoinSwap using contracts
transactions:

Party   | Before | After
--------|--------|--------------------------------------------
Alice   | WA     | WA-M1-I + I-MA~                  = WA-M1-MA~
Bob     | WB     | WB-I+B + I-M2-B-MB~              = WB-M2-MB~


What the table says is that if the CoinSwap results in the HTLC
transactions being mined and the locktime branch being used, then both
Alice and Bob will see their wallet balance fall by two miner fees (in
Alice's case the miner fee of the Alice funding transaction plus the
miner fee of the Alice contract transaction).

The attack I describe works because Alice chooses both MA~ and MB~. The
attack is that Alice chooses MA~ to be a very low value (e.g. 1 sat/vb)
and chooses MB~ to be a very high value (e.g. 1000 sat/vb). Then Alice
intentionally sabotages the CoinSwap and forces it to go to the timeout
case, what happens is that Bob's wallet balance falls by much more than
Alice's, because MB~ > MA~. So this is a DOS attack: Alice can waste
Bob's resources without wasting much of her own.

>> The timelocks are staggered so that if Alice uses the preimage to take
>> coins then the right people will also learn the preimage and have enough
>> time to be able to get their coins back too. Alice starts with knowledge
>> of the hash preimage so she must have a longest timelock.
> 
> More precisely:
> 
> * The HTLC outgoing from Alice has the longest timelock.
> * The HTLC incoming into Alice has the shortest timelock.
> 
> For the makers, they only need to ensure that the incoming timelock is much larger than the outgoing timelock.

Agreed.

Perhaps I chose confusing terminology, "Alice contract transaction"
means the transaction which pays money to Alice after a timeout. The
text you quoted is confusingly written, and it would've been better to
write: "Alice starts with knowledge of the hash preimage so the Alice
contract transaction must have a longest timelock."

>> == EC tweak to reduce one round trip ==
>>
>> When two parties are agreeing on a 2-of-2 multisig address, they need to
>> agree on their public keys. We can avoid one round trip by using the EC
>> tweak trick.
>>
>> When Alice, the taker, downloads the entire offer book for the liquidity
>> market, the offers will also contain a EC public key. Alice can tweak
>> this to generate a brand new public key for which the maker knows the
>> private key. This public key will be one of the keys in the 2-of-2
>> multisig. This feature removes one round trip from the protocol.
>>
>> q = EC privkey generated by maker
>> Q = q.G = EC pubkey published by maker
>>
>> p = nonce generated by taker
>> P = p.G = nonce point calculated by taker
>>
>> R = Q + P = pubkey used in bitcoin transaction
>> = (q + p).G
> 
> Whoa whoa whoa whoa.
> 
> All this time I was thinking you were going to use 2p-ECDSA for all 2-of-2s.
> In which case, the private key generated by the taker would be sufficient tweak to blind this.
> 
> In 2p-ECDSA, for two participants M = m * G; T = t * G, the total key is m * t * G = m * T = t * M.
> 
> Are you going to use `2 <T> <Q+P> 2 OP_CHECKMULTISIG` instead of 2p-ECDSA?
> Note that you cannot usefully hide among Lightning mutual closes, because of the reserve; Lightning mutual closes are very very likely to be spent in a 1-input (that spends from a 2-of-2 P2WSH), 2-output (that pays to two P2WPKHs) tx.

Yes, I intend for 2p-ECDSA to be used eventually, but for the first
version I'll only implement regular multisigs with OP_CHECKMULTISIG.
Once all the other details of this protocol are implemented correctly
and mostly-bug-free then 2p-ECDSA can be added. It can be added in the
protocol steps 0-1, 3-5 and 7-9.

This document also doesn't talk about PayJoin-with-CoinSwap, but that
can be added later too.

>>
>>     == Analysis of deviations ==
>>
>>     This section discusses what happens if one party deviates from the
>>     protocol by doing something else, for example broadcasting a htlc
>>     contract tx when they shouldnt have.
>>
>>     The party name refers to what that party does, followed by other party's
>>     reactions to it.
>>     e.g. Party1: does a thing, Party2/Party3: does a thing in reaction
>>
>>     If multiple deviations are possible in a step then they are numbered
>>     e.g. A1 A2 A2 etc
>>
>>     0-2. Alice/Bob/Charlie: nothing else is possible except following the
>>     protocol or aborting
>>
>> 8.  Alice: broadcasts one or more of the A htlc txes. Bob/Charlie/Dennis:
>>     do nothing, they havent lost any time or money.
>>     4-6. Bob/Charlie: nothing else is possible except following the protocol
>>     or aborting.
>>
>> 9.  Bob: broadcasts one or more of the B htlc txes, Alice: broadcasts all
>>     her own A htlc txes and waits for the timeout to get her money back.
>>     Charlie: do nothing
>>
>> 10.  Charlie: nothing else is possible except following the protocol or
>>     aborting.
>>
>> 11.  Alice: broadcasts one or more of the A htlc txes. Bob: broadcasts all
>>     his own A htlc txes and waits for the timeout.
>>     A. same as 8.
>>     B. Charlie: broadcasts one or more of the C htlc txes, Alice/Bob:
>>     broadcasts all their own htlc txes and waits for the timeout to get
>>     their money back.
>>     C-E1. Alice: broadcasts all of C htlc txes and uses her knowledge of the
>>     preimage hash to take the money immediately. Charlie: broadcasts
>>     all of B htlc txes and reading the hash value from the blockchain,
>>     uses it to take the money from B htlc immediately. Bob: broadcasts
>>     all of A htlc txes, and reading hash from the blockchain, uses it
>>     to take the money from A htlc immediately.
>>     C-E2. Alice: broadcast her own A htlc txes, and after a timeout take the
>>     money. Bob: broadcast his own B htlc txes and after the timeout
>>     take their money. Charlie: broadcast his own C htlc txes and after
>>     the timeout take their money.
>>     F1. Bob: broadcast one or more of A htcl txes and use the hash preimage
>>     to get the money immediately. He already knows both privkeys of the
>>     multisig so this is pointless and just damages privacy and wastes
>>     miner fees. Alice: blacklist Bob's fidelity bond.
>>     F2. Bob: broadcast one or more of the C htlc txes. Charlie: use preimage
>>     to get his money immediately. Bob's actions were pointless. Alice:
>>     cant tell whether Bob or Charlie actually broadcasted, so blacklist
>>     both fidelity bonds.
>>     G1. Charlie: broadcast one or more of B htcl txes and use the hash
>>     preimage to get the money immediately. He already knows both
>>     privkeys of the multisig so this is pointless and just damages
>>     privacy and wastes miner fees. Alice: cant tell whether Bob or
>>     Charlie actually broadcasted, so blacklist both fidelity bonds.
>>     G2. Charlie: broadcast one or more of the A htlc txes. Alice: broadcast
>>     the remaining A htlc txes and use preimage to get her money
>>     immediately. Charlies's actions were pointless. Alice: blacklist
>>     Charlie's fidelity bond.
>>
>>     The multisig outputs of the funding transactions can stay unspent
>>     indefinitely. However the parties must always be watching the network
>>     and ready to respond with their own sweep using a preimage. This is
>>     because the other party still possesses a fully-signed contract tx. The
>>     parties respond in the same way as in steps C-E1, F2 and G2. Alice's
>>     reaction of blacklisting both fidelity bonds might not be the right way,
>>     because one maker could use it to get another one blacklisted (as well
>>     as themselves).
> 
> Looks OK, though note that a participant might try to do so (as pointed out above) in the hope that the next participant is offline.

I really hope that everyone (the makers at least) is running multiple
redundant watchtowers, so that anyone attempting this attack just wastes
money on miner fees and achieves nothing.


^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap
  2020-08-20 21:38     ` ZmnSCPxj
@ 2020-08-20 22:37       ` Chris Belcher
  0 siblings, 0 replies; 24+ messages in thread
From: Chris Belcher @ 2020-08-20 22:37 UTC (permalink / raw)
  To: ZmnSCPxj, Nadav Kohen; +Cc: Bitcoin Protocol Discussion

Hello Nadav and ZmnSCPxj,

On 20/08/2020 22:38, ZmnSCPxj wrote:
> Good morning Nadav,
> 
>> Hey Chris and all,
>>
>> Looking good :) I have one major concern though
>>
>>>     q = EC privkey generated by maker
>>>     Q = q.G = EC pubkey published by maker
>>>
>>>     p = nonce generated by taker
>>>     P = p.G = nonce point calculated by taker
>>>
>>>     R = Q + P = pubkey used in bitcoin transaction
>>>       = (q + p).G
>>
>> If I'm understanding this correctly (which I'm not sure I ame), it seems like the plan is to put R on-chain as the key to an output? As stated this is completely insecure as Q is known in advance so the taker can always choose a nonce p but then claim that their nonce point is p.G - Q so that the key that goes on-chain is (p.G - Q + Q) = p.G allowing them to steal the funds.
> 
> My reading from this is that nonce `p` has to be given by the taker to the maker outright.
> In original post:
> 
>> Taker sends unsigned transaction which pays to multisig using pubkey Q,
>> and also sends nonce p.
> 
> Thus, taker provides a proof-of-knowledge, i.e. the actual `p` scalar itself (not zero-knowledge, but what the maker needs is proof-of-knowledge, and could not care less if the proof is zero-knowledge or not).

Yes this looks right. In hindsight my text could be clarified by
changing the relevant lines to:

    p = nonce generated by taker, sent to maker
    P = p.G = nonce point calculated by taker

    R = Q + P = pubkey used in bitcoin transaction, calculated by taker
      = (q + p).G = same pubkey, calculated by maker


I don't think the key subtraction attack described by Nadav will work
here...?


> On the other hand, I do not see the point of this tweak if you are going to use 2p-ECDSA, since my knowledge is that 2p-ECDSA uses the pubkey that is homomorphic to the product of the private keys.
> And that pubkey is already tweaked, by the fresh privkey of the maker (and the maker is buying privacy and wants security of the swap, so is incentivized to generate high-entropy temporary privkeys for the actual swap operation).
> 
> Not using 2p-ECDSA of some kind would remove most of the privacy advantages of CoinSwap.
> You cannot hide among `2 <A> <B> 2 OP_CHECKMULTISIG` scripts of Lightning, because:
> 
> * Lightning channel closes tend to be weeks at least after the funding outpoint creation, whereas CoinSwap envisions hours or days.
> * Lightning mutual channel closes have a very high probability of spending to two P2WPKH addresses.
> 
> You need to hide among the much larger singlesig anonymity set, which means using a single signature (created multiparty by both participants), not two signatures (one from each participant).
> 
> Or is this intended for HTLCs in open-coded SCRIPTs `OP_DUP OP_IF OP_HASH160 <hash> OP_EQUAL <A> OP_ELSE <time> OP_CHECKSEQUENCEVERIFY OP_DROP <B> OP_ENDIF OP_CHECKSIG`?
> This provides a slight privacy boost in a case (contract transaction publication) where most of the privacy is lost anyway.

I completely agree that 2of2 multisigs made with OP_CHECKMULTISIG are
lacking in terms of privacy, and that 2p-ECDSA is much better. However
this whole protocol is quite complicated and I thought it would be a
good move to first implement it with OP_CHECKMULTISIG, to get all the
other details right (miner fees, coinswap fees, private key handover,
contract transactions, tor hidden services, watchtowers, etc etc) and
then add 2p-ECDSA later. Of course in that case all this tweaking of
public keys would be superseded by the 2p-ECDSA protocol.


^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap
  2020-08-20 22:15   ` Chris Belcher
@ 2020-08-21  4:20     ` ZmnSCPxj
  2020-08-21  9:47       ` Chris Belcher
  0 siblings, 1 reply; 24+ messages in thread
From: ZmnSCPxj @ 2020-08-21  4:20 UTC (permalink / raw)
  To: Chris Belcher; +Cc: Bitcoin Protocol Discussion

Good morning,



> Right, so if the taker uses only a single maker then they must have more
> than one UTXO.

Spending one UTXO is fine, it is generating a transaction that has one output that is problematic.

What needs to happen is that this single UTXO is spent to two outputs: the CoinSwap 2-of-2 and the change output.
This is because intermediate makers will have very high likelihood of generating such a pattern (it is unlikely they have an exact amount that a taker would require of them), and the occassional maker might have a very large UTXO that it can use for similar purposes.

One thing a taker can do would be to multipath its CoinSwap, i.e. it spends any number of UTXOs and creates two outputs, which are actually two separate CoinSwap 2-of-2s to different makers.
As each maker is unaware of the other, this should be similar to the case where the maker is an intermediate hop and is getting its incoming HTLC from another maker, which is unlikely to have a precise amount and will thus have a transaction that has two outputs, the 2-of-2 CoinSwap and the change.

>
> This leak in the case of a taker spending a single UTXO also happens
> when the taker needs to create a branching route. I described this in my
> original email "Design for a CoinSwap implementation for massively
> improving Bitcoin privacy and fungibility" under the section "Combining
> multi-transaction with routing" (the second diagram).
>
> I think this might be unavoidable. If the taker has just one UTXO they'd
> be much better off using multiple makers for this reason.
>
> > -   The makers can try timing the communications lag with the taker.
> >     The general assumption would be that more makers == more delay in taker responses.
> >
>
> Sounds like adding random delays would fix this. The protocol already
> involves waiting for a confirmation (average waiting time 10 minutes, at
> best) and might involve more confirmations for extra security and
> privacy. So adding a random delay of up to 0.5-1 minutes shouldnt cause
> too many issues.
> Also the Tor network can be pretty laggy so that might add enough noise
> anyway.

Indeed, this seems a bit of a long shot for the surveilling maker.

> > > === Miner fees ===
> > > Makers have no incentive to pay any miner fees. They only do
> > > transactions which earn them an income and are willing to wait a very
> > > long time for that to happen. By contrast takers want to create
> > > transactions far more urgently. In JoinMarket we coded a protocol where
> > > the maker could contribute to miner fees, but the market price offered
> > > of that trended towards zero. So the reality is that takers will pay all
> > > the miner fees. Also because makers don't know the taker's time
> > > preference they don't know how much they should pay in miner fees.
> > > The taker will have to set limits on how large the maker's transactions
> > > are, otherwise makers could abuse this by having the taker consolidate
> > > maker's UTXOs for free.
> >
> > Why not have the taker pay for the first maker-spent UTXO and have additional maker-spent UTXOs paid for by the maker?
> > i.e. the taker indicates "swap me 1 BTC in 3 bags of 0.3, 0.3, and 0.4 BTC", and pays for one UTXO spent for each "bag" (thus pays for 3 UTXOs).
> > Disagreements on feerate can be resolved by having the taker set the feerate, i.e. "the customer is always right".
> > Thus if the maker has to spend two UTXOs to make up the 0.4 BTC bag, it pays for the mining fees for that extra UTXO.
> > The maker can always reject the swap attempt if it has to spend multiple UTXOs and would lose money doing so if the taker demands a too-high feerate.
>
> Having the taker pay for just one UTXO will have an unfortunate side
> effect of resulting in the maker's money being split up into a large
> number of UTXOs, because every CoinSwap they take part in has an
> incentive to increase their UTXO count by one. At the start of
> JoinMarket this was an issue where then a taker wanting to CoinJoin a
> large would come along and the result would be a huge CoinJoin
> transaction with many many small inputs. Perhaps the taker could pay for
> 2-3 UTXOs to counteract this. (Of course the exact number would be
> configurable by the taker user, but defaults usually don't get changed).
>
> I'm still not convinced with having makers contribute to miner fees. In
> JoinMarket we tried to get makers to contribute a little to miner fees
> and simply they never did in any meaningful way. The market has spoken.
> In terms of incentives makers are happy to wait a very long time, if we
> assume they're just HODLers then even if they earn a few thousand
> satoshis that's good.
>
> > > == Contract transaction definitions ==
> > > Contract transactions are those which may spend from the 2-of-2 multisig
> > > outputs, they transfer the coins into a contract where the coins can be
> > > spent either by waiting for a timeout or providing a hash preimage
> > > value. Ideally contract transactions will never be broadcast but their
> > > existence keeps all parties honest.
> > > M~ is miner fees, which we treat as a random variable, and ultimately
> > > set by whichever pre-signed RBF tx get mined. When we talk about the
> > > contract tx, we actually mean perhaps 20-30 transactions which only
> > > differ by the miner fee and have RBF enabled, so they can be broadcasted
> > > in sequence to get the contract transaction mined regardless of the
> > > demand for block space.
> >
> > The highest-fee version could have, in addition, CPFP-anchor outputs, like those being proposed in Lightning, so even if onchain fees rise above the largest fee reservation, it is possible to add even more fees.
> > Or not.
> > Hmm.
>
> I think RBF transactions are better because they ultimately use less
> block space than CPFP.
>
> There seems to be very little cost in signing many additional
> precomputed RBF transactions. So the taker and makers could sign
> transactions all the way up to 10000 sat/vbyte. I think this doesn't
> apply to Lightning, because bandwidth seems to be more constrained
> there: even a tiny micropayment for 1 satoshi would require 10x or 100x
> more bandwidth if every lightning htlc used precomputed RBF.

I was wondering if it would be a good idea actually if the **largest** fee RBF transaction had additional CPFP anchor outputs, not saying to replace the entire group of RBF transactions entirely.

This is just in case of a very sudden increase in feerates that goes beyond the largest that was prepared beforehand.
"You cannot predict the feerates future" is becoming something of a mantra over in Lightning, though I guess a "big enough" spread of RBF transactions would work in practice >99% of the time.


> > Another thought: later you describe that miner fees are paid by Alice by forwarding those fees as well, how does that work when there are multiple versions of the contract transaction?
>
> Alice only pays the miner fees for the funding transactions, not the
> contract transaction. The miner fees for the contract transactions are
> taken from the contract balance. The contract transactions are 1-input
> 1-output, and whoever ends up with the money will be the one who paid
> the miner fee.

Okay, that is much clearer.

> > > (Alice+timelock_A OR Bob+hash) = Is an output which can be spent
> > > either with Alice's private key
> > > after waiting for a relative
> > > timelock_A, or by Bob's private key by
> > > revealing a hash preimage value
> >
> > The rationale for relative timelocks is that it makes private key turnover slightly more useable by ensuring that, after private key turnover, it is possible to wait indefinitely to spend the UTXO it received.
> > This is in contrast with absolute timelocks, where after private key turnover, it is required to spend received UTXO before the absolute timeout.
> > The dangers are:
> >
> > -   Until it receives the private key, if either of the incoming or outgoing contract transactions are confirmed, every swap participant (taker or maker) should also broadcast the other contract transaction, and resolve by onchain transactions (with loss of privacy).
> > -   After receiving the private key, if the incoming contract transaction is confirmed, it should spend the resulting contract output.
> > -   It is possible to steal from a participant if that participant goes offline longer than the timeout.
> >     This may imply that there may have to be some minimum timeout that makers indicate in their advertisements.
> >     -   The taker can detect if the first maker is offline, then if it is offline, try a contract transaction broadcast, if it confirms, the taker can wait for the timeout; if it times out, the taker can clawback the transaction.
> >         -   This appears to be riskless for the taker.
> >         -   Against a similar attack, Lightning requires channel reserves, which means the first hop never gains control of the entire value, which is a basic requirement for private key turnover.
> >     -   On the other hand, the taker has the largest timeout before it can clawback the funds, so it would wait for a long time, and at any time in between the first maker can come online and spend using the hashlock branch.
> >         -   But the taker can just try on the hope it works; it has nothing to lose.
> >     -   This attack seems to be possible only for the taker to mount.
> >         Other makers on the route cannot know who the other makers are, without cooperation of the taker, who is the only one who knows all the makers.
> >         -   On the other hand, the last maker in the route has an outgoing HTLC with the smallest timelock, so it is the least-risk and therefore a maker who notices its outgoing HTLC has a low timeout might want to just do this anyway even if it is unsure if the taker is offline.
>
> Every off-chain protocol like this has the livelyness requirement. Each
> party must always be watching the chain and be ready to broadcast
> something in response. I'm not sure how any of this relates to the
> choice of relative vs absolute time locks.

Absolute timelocks mean that you can set a timer where you put your node to sleep without risk of loss of funds (basically, once the absolute timelocks have resolved, you can forget about CoinSwaps).
But I think the ability to spend at any time would be better, and getting 100% online 144 blocks a day, 2016 blocks a retargeting period is becoming more and more feasible.

>
> You're right that attempting such an move by the taker is riskless, but
> its not costless. The taker sets up the entire CoinSwap protocol because
> they wanted more privacy; but if the taker broadcasts the Alice contract
> transaction and waits for the timeout, then all they've achieved is
> spent miner fees, got their own coin back and draw attention to it with
> the unusual HTLC script. They've achieved no benefit from what I see, so
> they won't do this. Any taker or maker who attempts anything like this
> will be spending miner fees.

They would be spending miner fees *from the funds being stolen*, thus still costless.

In particular, let us imagine a simple 1-maker swap.

* The taker and the maker complete the swap.
* The taker now has possession of:
  * The private key for its incoming HTLC.
  * The pre-signed contract transaction for its outgoing HTLC.
* The taker spends from its incoming HTLC using the private key.
  * The maker ignores this, because this is just normal operation.
  * Fees paid for this is not an **additional** cost, because a taker that wants to put its freshly-private funds into cold storage will do this anyway.
  * The taker gets a fresh, private coin from this incoming HTLC, so it gets the privacy it paid for.
* The taker waits for the incoming-HTLC-spend to confirm.
* The taker broadcasts the pre-signed contract transaction, in the hope that the maker is offline.
  * The fees paid for this are from the contract transaction that the taker is trying to steal.
    Even if the theft attempt fails, the taker has already gotten its private money out, and is thus not risking anything.
  * Semantically, the outgoing HTLC is already "owned" by the maker (the maker has private key to it).
    * Thus, the taker commits an action that the maker pays fees for!
  * The maker cannot react except to spend via the hashlock branch.
    In particular, because the taker-incoming (maker-outgoing) UTXO is already spent, it cannot retaliate by also broadcasting the contract transaction of the taker-incoming (maker-outgoing) HTLC.
* The theft succeeds (the timelock passes) because the maker happens to be offline for that long.
  * This is "free money" to the taker, who has already gotten what it paid for --- private money in cold storage --- from the CoinSwap.
  * Even if the stolen fund reveals the contract, the taker can re-acquire privacy for the funds it stole for free, by paying for --- wait for it --- another CoinSwap for its swag.

Using an absolute timelock (implemented by a `nLockTime` tx directly off the 2-of-2, ***not*** `OP_CHECKLOCKTIMEVERIFY`), plus a Scriptless Script 2p-ECDSA (again implemented by a tx directly off the 2-of-2) instead of a hashlock, seems to avoid this, I think, at the cost of reducing the utility of private key turnover by having a deadline where the private key *has to* be used.
This is because there is no contract transaction that is share-owned by both participants in the swap.
Instead there are two distinct transactions with separate ownerships: a timeout tx (that is owned by the participant paying for the HTLC/PTLC) and a claim tx (that is owned by the participant accepting the HTLC/PTLC).

> > -   Participants might want to spend from the UTXO to a new address after private key turnover anyway.
> >     Makers could spend using a low-fee RBF-enabled tx, and when another request comes in for another swap, try to build a new funding tx with a higher-fee bump.
> >
>
> I don't think this will happen very often. It's spending money on block
> space for not much benefit. If the maker ever decides to shut down their
> maker they can transfer all their coins in HTLCs to single-sig
> transactions exclusively controlled by them, but in normal operation I
> doubt it will happen.

Accidents can happen (e.g. somebody trips over the power cord of the maker hardware), so hedging this somewhat might give a useful safety net.

>
> The attack I describe works because Alice chooses both MA~ and MB~. The
> attack is that Alice chooses MA~ to be a very low value (e.g. 1 sat/vb)
> and chooses MB~ to be a very high value (e.g. 1000 sat/vb). Then Alice
> intentionally sabotages the CoinSwap and forces it to go to the timeout
> case, what happens is that Bob's wallet balance falls by much more than
> Alice's, because MB~ > MA~. So this is a DOS attack: Alice can waste
> Bob's resources without wasting much of her own.

Ah, right, that is clearer.

> > > == EC tweak to reduce one round trip ==
> > > When two parties are agreeing on a 2-of-2 multisig address, they need to
> > > agree on their public keys. We can avoid one round trip by using the EC
> > > tweak trick.
> > > When Alice, the taker, downloads the entire offer book for the liquidity
> > > market, the offers will also contain a EC public key. Alice can tweak
> > > this to generate a brand new public key for which the maker knows the
> > > private key. This public key will be one of the keys in the 2-of-2
> > > multisig. This feature removes one round trip from the protocol.
> > > q = EC privkey generated by maker
> > > Q = q.G = EC pubkey published by maker
> > > p = nonce generated by taker
> > > P = p.G = nonce point calculated by taker
> > > R = Q + P = pubkey used in bitcoin transaction
> > > = (q + p).G
> >
> > Whoa whoa whoa whoa.
> > All this time I was thinking you were going to use 2p-ECDSA for all 2-of-2s.
> > In which case, the private key generated by the taker would be sufficient tweak to blind this.
> > In 2p-ECDSA, for two participants M = m * G; T = t * G, the total key is m * t * G = m * T = t * M.
> > Are you going to use `2 <T> <Q+P> 2 OP_CHECKMULTISIG` instead of 2p-ECDSA?
> > Note that you cannot usefully hide among Lightning mutual closes, because of the reserve; Lightning mutual closes are very very likely to be spent in a 1-input (that spends from a 2-of-2 P2WSH), 2-output (that pays to two P2WPKHs) tx.
>
> Yes, I intend for 2p-ECDSA to be used eventually, but for the first
> version I'll only implement regular multisigs with OP_CHECKMULTISIG.
> Once all the other details of this protocol are implemented correctly
> and mostly-bug-free then 2p-ECDSA can be added. It can be added in the
> protocol steps 0-1, 3-5 and 7-9.

Okay, that is clearer.

I think 2p-ECDSA should be first priority after getting a decent alpha version.

> This document also doesn't talk about PayJoin-with-CoinSwap, but that
> can be added later too.

2p-ECDSA with Scriptless Script potentially gives a lot more privacy than any PayJoin IMO, due simply to the much larger anonymity set, and there are enough chain-analysis-heuristic-breaking shenanigans we can implement with plain CoinSwap, I think.


Regards,
ZmnSCPxj


^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap
  2020-08-21  4:20     ` ZmnSCPxj
@ 2020-08-21  9:47       ` Chris Belcher
  2020-08-22  1:09         ` ZmnSCPxj
  0 siblings, 1 reply; 24+ messages in thread
From: Chris Belcher @ 2020-08-21  9:47 UTC (permalink / raw)
  To: ZmnSCPxj; +Cc: Bitcoin Protocol Discussion

Hello,

On 21/08/2020 05:20, ZmnSCPxj wrote:
> Good morning,
> 
> 
> 
>> Right, so if the taker uses only a single maker then they must have more
>> than one UTXO.
> 
> Spending one UTXO is fine, it is generating a transaction that has one output that is problematic.
> 
> What needs to happen is that this single UTXO is spent to two outputs: the CoinSwap 2-of-2 and the change output.
> This is because intermediate makers will have very high likelihood of generating such a pattern (it is unlikely they have an exact amount that a taker would require of them), and the occassional maker might have a very large UTXO that it can use for similar purposes.
> 
> One thing a taker can do would be to multipath its CoinSwap, i.e. it spends any number of UTXOs and creates two outputs, which are actually two separate CoinSwap 2-of-2s to different makers.
> As each maker is unaware of the other, this should be similar to the case where the maker is an intermediate hop and is getting its incoming HTLC from another maker, which is unlikely to have a precise amount and will thus have a transaction that has two outputs, the 2-of-2 CoinSwap and the change.

Agreed.
I write about multipath CoinSwap routes in the original design document,
under "Combining multi-transaction with routing"


>>>> === Miner fees ===
>>>> Makers have no incentive to pay any miner fees. They only do
>>>> transactions which earn them an income and are willing to wait a very
>>>> long time for that to happen. By contrast takers want to create
>>>> transactions far more urgently. In JoinMarket we coded a protocol where
>>>> the maker could contribute to miner fees, but the market price offered
>>>> of that trended towards zero. So the reality is that takers will pay all
>>>> the miner fees. Also because makers don't know the taker's time
>>>> preference they don't know how much they should pay in miner fees.
>>>> The taker will have to set limits on how large the maker's transactions
>>>> are, otherwise makers could abuse this by having the taker consolidate
>>>> maker's UTXOs for free.
>>>
>>> Why not have the taker pay for the first maker-spent UTXO and have additional maker-spent UTXOs paid for by the maker?
>>> i.e. the taker indicates "swap me 1 BTC in 3 bags of 0.3, 0.3, and 0.4 BTC", and pays for one UTXO spent for each "bag" (thus pays for 3 UTXOs).
>>> Disagreements on feerate can be resolved by having the taker set the feerate, i.e. "the customer is always right".
>>> Thus if the maker has to spend two UTXOs to make up the 0.4 BTC bag, it pays for the mining fees for that extra UTXO.
>>> The maker can always reject the swap attempt if it has to spend multiple UTXOs and would lose money doing so if the taker demands a too-high feerate.
>>
>> Having the taker pay for just one UTXO will have an unfortunate side
>> effect of resulting in the maker's money being split up into a large
>> number of UTXOs, because every CoinSwap they take part in has an
>> incentive to increase their UTXO count by one. At the start of
>> JoinMarket this was an issue where then a taker wanting to CoinJoin a
>> large would come along and the result would be a huge CoinJoin
>> transaction with many many small inputs. Perhaps the taker could pay for
>> 2-3 UTXOs to counteract this. (Of course the exact number would be
>> configurable by the taker user, but defaults usually don't get changed).
>>
>> I'm still not convinced with having makers contribute to miner fees. In
>> JoinMarket we tried to get makers to contribute a little to miner fees
>> and simply they never did in any meaningful way. The market has spoken.
>> In terms of incentives makers are happy to wait a very long time, if we
>> assume they're just HODLers then even if they earn a few thousand
>> satoshis that's good.
>>
>>>> == Contract transaction definitions ==
>>>> Contract transactions are those which may spend from the 2-of-2 multisig
>>>> outputs, they transfer the coins into a contract where the coins can be
>>>> spent either by waiting for a timeout or providing a hash preimage
>>>> value. Ideally contract transactions will never be broadcast but their
>>>> existence keeps all parties honest.
>>>> M~ is miner fees, which we treat as a random variable, and ultimately
>>>> set by whichever pre-signed RBF tx get mined. When we talk about the
>>>> contract tx, we actually mean perhaps 20-30 transactions which only
>>>> differ by the miner fee and have RBF enabled, so they can be broadcasted
>>>> in sequence to get the contract transaction mined regardless of the
>>>> demand for block space.
>>>
>>> The highest-fee version could have, in addition, CPFP-anchor outputs, like those being proposed in Lightning, so even if onchain fees rise above the largest fee reservation, it is possible to add even more fees.
>>> Or not.
>>> Hmm.
>>
>> I think RBF transactions are better because they ultimately use less
>> block space than CPFP.
>>
>> There seems to be very little cost in signing many additional
>> precomputed RBF transactions. So the taker and makers could sign
>> transactions all the way up to 10000 sat/vbyte. I think this doesn't
>> apply to Lightning, because bandwidth seems to be more constrained
>> there: even a tiny micropayment for 1 satoshi would require 10x or 100x
>> more bandwidth if every lightning htlc used precomputed RBF.
> 
> I was wondering if it would be a good idea actually if the **largest** fee RBF transaction had additional CPFP anchor outputs, not saying to replace the entire group of RBF transactions entirely.
> 
> This is just in case of a very sudden increase in feerates that goes beyond the largest that was prepared beforehand.
> "You cannot predict the feerates future" is becoming something of a mantra over in Lightning, though I guess a "big enough" spread of RBF transactions would work in practice >99% of the time.

Got it. I agree having a CPFP anchor output on the largest fee RBF is a
good idea then.

> 
>>>> (Alice+timelock_A OR Bob+hash) = Is an output which can be spent
>>>> either with Alice's private key
>>>> after waiting for a relative
>>>> timelock_A, or by Bob's private key by
>>>> revealing a hash preimage value
>>>
>>> The rationale for relative timelocks is that it makes private key turnover slightly more useable by ensuring that, after private key turnover, it is possible to wait indefinitely to spend the UTXO it received.
>>> This is in contrast with absolute timelocks, where after private key turnover, it is required to spend received UTXO before the absolute timeout.
>>> The dangers are:
>>>
>>> -   Until it receives the private key, if either of the incoming or outgoing contract transactions are confirmed, every swap participant (taker or maker) should also broadcast the other contract transaction, and resolve by onchain transactions (with loss of privacy).
>>> -   After receiving the private key, if the incoming contract transaction is confirmed, it should spend the resulting contract output.
>>> -   It is possible to steal from a participant if that participant goes offline longer than the timeout.
>>>     This may imply that there may have to be some minimum timeout that makers indicate in their advertisements.
>>>     -   The taker can detect if the first maker is offline, then if it is offline, try a contract transaction broadcast, if it confirms, the taker can wait for the timeout; if it times out, the taker can clawback the transaction.
>>>         -   This appears to be riskless for the taker.
>>>         -   Against a similar attack, Lightning requires channel reserves, which means the first hop never gains control of the entire value, which is a basic requirement for private key turnover.
>>>     -   On the other hand, the taker has the largest timeout before it can clawback the funds, so it would wait for a long time, and at any time in between the first maker can come online and spend using the hashlock branch.
>>>         -   But the taker can just try on the hope it works; it has nothing to lose.
>>>     -   This attack seems to be possible only for the taker to mount.
>>>         Other makers on the route cannot know who the other makers are, without cooperation of the taker, who is the only one who knows all the makers.
>>>         -   On the other hand, the last maker in the route has an outgoing HTLC with the smallest timelock, so it is the least-risk and therefore a maker who notices its outgoing HTLC has a low timeout might want to just do this anyway even if it is unsure if the taker is offline.
>>
>> Every off-chain protocol like this has the livelyness requirement. Each
>> party must always be watching the chain and be ready to broadcast
>> something in response. I'm not sure how any of this relates to the
>> choice of relative vs absolute time locks.
> 
> Absolute timelocks mean that you can set a timer where you put your node to sleep without risk of loss of funds (basically, once the absolute timelocks have resolved, you can forget about CoinSwaps).
> But I think the ability to spend at any time would be better, and getting 100% online 144 blocks a day, 2016 blocks a retargeting period is becoming more and more feasible.

You can always put your node to sleep as a maker, and your watchtowers
will protect you.

What do you mean by the point about 100% online nodes getting more
feasible? Many bitcoin nodes have been always-on for years, I think I
missed something.

>> You're right that attempting such an move by the taker is riskless, but
>> its not costless. The taker sets up the entire CoinSwap protocol because
>> they wanted more privacy; but if the taker broadcasts the Alice contract
>> transaction and waits for the timeout, then all they've achieved is
>> spent miner fees, got their own coin back and draw attention to it with
>> the unusual HTLC script. They've achieved no benefit from what I see, so
>> they won't do this. Any taker or maker who attempts anything like this
>> will be spending miner fees.
> 
> They would be spending miner fees *from the funds being stolen*, thus still costless.
> 
> In particular, let us imagine a simple 1-maker swap.
> 
> * The taker and the maker complete the swap.
> * The taker now has possession of:
>   * The private key for its incoming HTLC.
>   * The pre-signed contract transaction for its outgoing HTLC.
> * The taker spends from its incoming HTLC using the private key.
>   * The maker ignores this, because this is just normal operation.
>   * Fees paid for this is not an **additional** cost, because a taker that wants to put its freshly-private funds into cold storage will do this anyway.
>   * The taker gets a fresh, private coin from this incoming HTLC, so it gets the privacy it paid for.
> * The taker waits for the incoming-HTLC-spend to confirm.
> * The taker broadcasts the pre-signed contract transaction, in the hope that the maker is offline.
>   * The fees paid for this are from the contract transaction that the taker is trying to steal.
>     Even if the theft attempt fails, the taker has already gotten its private money out, and is thus not risking anything.
>   * Semantically, the outgoing HTLC is already "owned" by the maker (the maker has private key to it).
>     * Thus, the taker commits an action that the maker pays fees for!
>   * The maker cannot react except to spend via the hashlock branch.
>     In particular, because the taker-incoming (maker-outgoing) UTXO is already spent, it cannot retaliate by also broadcasting the contract transaction of the taker-incoming (maker-outgoing) HTLC.
> * The theft succeeds (the timelock passes) because the maker happens to be offline for that long.
>   * This is "free money" to the taker, who has already gotten what it paid for --- private money in cold storage --- from the CoinSwap.
>   * Even if the stolen fund reveals the contract, the taker can re-acquire privacy for the funds it stole for free, by paying for --- wait for it --- another CoinSwap for its swag.

Yep you're right, I get it.

The biggest defense against theft will have to be multiple redundant
watchtowers. But as you say the attack is riskless and costless for the
taker to attempt, so they might try anyway even if the probability of
success is very low.

If this attack becomes widespread then it effectively breaks the
property that maker's coins remain unspent indefinitely. It seems like
that would lead to makers increasing their CoinSwap fees because they
know they'll always have to spend a bit of miner fees afterwards.

Hopefully the success rate for this attack can be low enough that
taker's human niceness will stop them trying. But for sure this is a
concerning problem.

> Using an absolute timelock (implemented by a `nLockTime` tx directly off the 2-of-2, ***not*** `OP_CHECKLOCKTIMEVERIFY`), plus a Scriptless Script 2p-ECDSA (again implemented by a tx directly off the 2-of-2) instead of a hashlock, seems to avoid this, I think, at the cost of reducing the utility of private key turnover by having a deadline where the private key *has to* be used.
> This is because there is no contract transaction that is share-owned by both participants in the swap.
> Instead there are two distinct transactions with separate ownerships: a timeout tx (that is owned by the participant paying for the HTLC/PTLC) and a claim tx (that is owned by the participant accepting the HTLC/PTLC).

A downside of using absolute timelocks is that it combines the two time
periods: the time period where a watchtower must respond and the time
period under which private keys must be used.

So for example if the absolute timelock is set to 3 weeks, that means
the maker has 3 weeks to spend their coins using the private keys which
is a nice long period. However if the CoinSwaps fails with the timeout
case then the maker has to wait 3 weeks to get their coins back, which
is a long time.

We can go the other extreme and set the absolute timelock to be 2 days.
Then the maker only has to wait 2 days in the unfortunate event that
their coinswap fails with the timeout case. But it means they must use
their private keys to spend coins within the short period of 2 days(!)

Though this still might be worth it to solve the riskless/costless
stealing attempts.


>>> -   Participants might want to spend from the UTXO to a new address after private key turnover anyway.
>>>     Makers could spend using a low-fee RBF-enabled tx, and when another request comes in for another swap, try to build a new funding tx with a higher-fee bump.
>>>
>>
>> I don't think this will happen very often. It's spending money on block
>> space for not much benefit. If the maker ever decides to shut down their
>> maker they can transfer all their coins in HTLCs to single-sig
>> transactions exclusively controlled by them, but in normal operation I
>> doubt it will happen.
> 
> Accidents can happen (e.g. somebody trips over the power cord of the maker hardware), so hedging this somewhat might give a useful safety net.

Right, but taking out the maker hardware isn't enough for funds to be
stolen, all the watchtowers would need to be taken out too.


>>>> == EC tweak to reduce one round trip ==
>>>> When two parties are agreeing on a 2-of-2 multisig address, they need to
>>>> agree on their public keys. We can avoid one round trip by using the EC
>>>> tweak trick.
>>>> When Alice, the taker, downloads the entire offer book for the liquidity
>>>> market, the offers will also contain a EC public key. Alice can tweak
>>>> this to generate a brand new public key for which the maker knows the
>>>> private key. This public key will be one of the keys in the 2-of-2
>>>> multisig. This feature removes one round trip from the protocol.
>>>> q = EC privkey generated by maker
>>>> Q = q.G = EC pubkey published by maker
>>>> p = nonce generated by taker
>>>> P = p.G = nonce point calculated by taker
>>>> R = Q + P = pubkey used in bitcoin transaction
>>>> = (q + p).G
>>>
>>> Whoa whoa whoa whoa.
>>> All this time I was thinking you were going to use 2p-ECDSA for all 2-of-2s.
>>> In which case, the private key generated by the taker would be sufficient tweak to blind this.
>>> In 2p-ECDSA, for two participants M = m * G; T = t * G, the total key is m * t * G = m * T = t * M.
>>> Are you going to use `2 <T> <Q+P> 2 OP_CHECKMULTISIG` instead of 2p-ECDSA?
>>> Note that you cannot usefully hide among Lightning mutual closes, because of the reserve; Lightning mutual closes are very very likely to be spent in a 1-input (that spends from a 2-of-2 P2WSH), 2-output (that pays to two P2WPKHs) tx.
>>
>> Yes, I intend for 2p-ECDSA to be used eventually, but for the first
>> version I'll only implement regular multisigs with OP_CHECKMULTISIG.
>> Once all the other details of this protocol are implemented correctly
>> and mostly-bug-free then 2p-ECDSA can be added. It can be added in the
>> protocol steps 0-1, 3-5 and 7-9.
> 
> Okay, that is clearer.
> 
> I think 2p-ECDSA should be first priority after getting a decent alpha version.
> 
>> This document also doesn't talk about PayJoin-with-CoinSwap, but that
>> can be added later too.
> 
> 2p-ECDSA with Scriptless Script potentially gives a lot more privacy than any PayJoin IMO, due simply to the much larger anonymity set, and there are enough chain-analysis-heuristic-breaking shenanigans we can implement with plain CoinSwap, I think.

I completely agree.


Regards
CB


^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap
  2020-08-21  9:47       ` Chris Belcher
@ 2020-08-22  1:09         ` ZmnSCPxj
  0 siblings, 0 replies; 24+ messages in thread
From: ZmnSCPxj @ 2020-08-22  1:09 UTC (permalink / raw)
  To: Chris Belcher; +Cc: Bitcoin Protocol Discussion

Good morning Chris,


> > Absolute timelocks mean that you can set a timer where you put your node to sleep without risk of loss of funds (basically, once the absolute timelocks have resolved, you can forget about CoinSwaps).
> > But I think the ability to spend at any time would be better, and getting 100% online 144 blocks a day, 2016 blocks a retargeting period is becoming more and more feasible.
>
> You can always put your node to sleep as a maker, and your watchtowers
> will protect you.

Assuming you have multiple watchtowers, yes.

It would be best if watchtowers for CoinSwap and watchtowers for Lightning could be the same thing, and ideally, a watchtower would not even know if what it was watching were a Lightning channel or a CoinSwap until an attack happens.

>
> What do you mean by the point about 100% online nodes getting more
> feasible? Many bitcoin nodes have been always-on for years, I think I
> missed something.

Not all locations on Earth make it easy to be 100% online.
However, as the technology of you puny humans advance, it becomes more and more possible for a random point on Earth to be 100% online.

> > > You're right that attempting such an move by the taker is riskless, but
> > > its not costless. The taker sets up the entire CoinSwap protocol because
> > > they wanted more privacy; but if the taker broadcasts the Alice contract
> > > transaction and waits for the timeout, then all they've achieved is
> > > spent miner fees, got their own coin back and draw attention to it with
> > > the unusual HTLC script. They've achieved no benefit from what I see, so
> > > they won't do this. Any taker or maker who attempts anything like this
> > > will be spending miner fees.
> >
> > They would be spending miner fees from the funds being stolen, thus still costless.
> > In particular, let us imagine a simple 1-maker swap.
> >
> > -   The taker and the maker complete the swap.
> > -   The taker now has possession of:
> >     -   The private key for its incoming HTLC.
> >     -   The pre-signed contract transaction for its outgoing HTLC.
> > -   The taker spends from its incoming HTLC using the private key.
> >     -   The maker ignores this, because this is just normal operation.
> >     -   Fees paid for this is not an additional cost, because a taker that wants to put its freshly-private funds into cold storage will do this anyway.
> >     -   The taker gets a fresh, private coin from this incoming HTLC, so it gets the privacy it paid for.
> > -   The taker waits for the incoming-HTLC-spend to confirm.
> > -   The taker broadcasts the pre-signed contract transaction, in the hope that the maker is offline.
> >     -   The fees paid for this are from the contract transaction that the taker is trying to steal.
> >         Even if the theft attempt fails, the taker has already gotten its private money out, and is thus not risking anything.
> >
> >     -   Semantically, the outgoing HTLC is already "owned" by the maker (the maker has private key to it).
> >         -   Thus, the taker commits an action that the maker pays fees for!
> >     -   The maker cannot react except to spend via the hashlock branch.
> >         In particular, because the taker-incoming (maker-outgoing) UTXO is already spent, it cannot retaliate by also broadcasting the contract transaction of the taker-incoming (maker-outgoing) HTLC.
> >
> > -   The theft succeeds (the timelock passes) because the maker happens to be offline for that long.
> >     -   This is "free money" to the taker, who has already gotten what it paid for --- private money in cold storage --- from the CoinSwap.
> >     -   Even if the stolen fund reveals the contract, the taker can re-acquire privacy for the funds it stole for free, by paying for --- wait for it --- another CoinSwap for its swag.
>
> Yep you're right, I get it.
>
> The biggest defense against theft will have to be multiple redundant
> watchtowers. But as you say the attack is riskless and costless for the
> taker to attempt, so they might try anyway even if the probability of
> success is very low.
>
> If this attack becomes widespread then it effectively breaks the
> property that maker's coins remain unspent indefinitely. It seems like
> that would lead to makers increasing their CoinSwap fees because they
> know they'll always have to spend a bit of miner fees afterwards.
>
> Hopefully the success rate for this attack can be low enough that
> taker's human niceness will stop them trying. But for sure this is a
> concerning problem.

Indeed.

We also cannot use succinct atomic swaps because their asymmetry makes them unroutable --- you can only use it for single-maker swaps.
This makes it obvious to the maker that you have only a single maker.

> > Using an absolute timelock (implemented by a `nLockTime` tx directly off the 2-of-2, not `OP_CHECKLOCKTIMEVERIFY`), plus a Scriptless Script 2p-ECDSA (again implemented by a tx directly off the 2-of-2) instead of a hashlock, seems to avoid this, I think, at the cost of reducing the utility of private key turnover by having a deadline where the private key has to be used.
> > This is because there is no contract transaction that is share-owned by both participants in the swap.
> > Instead there are two distinct transactions with separate ownerships: a timeout tx (that is owned by the participant paying for the HTLC/PTLC) and a claim tx (that is owned by the participant accepting the HTLC/PTLC).
>
> A downside of using absolute timelocks is that it combines the two time
> periods: the time period where a watchtower must respond and the time
> period under which private keys must be used.
>
> So for example if the absolute timelock is set to 3 weeks, that means
> the maker has 3 weeks to spend their coins using the private keys which
> is a nice long period. However if the CoinSwaps fails with the timeout
> case then the maker has to wait 3 weeks to get their coins back, which
> is a long time.
>
> We can go the other extreme and set the absolute timelock to be 2 days.
> Then the maker only has to wait 2 days in the unfortunate event that
> their coinswap fails with the timeout case. But it means they must use
> their private keys to spend coins within the short period of 2 days(!)
>
> Though this still might be worth it to solve the riskless/costless
> stealing attempts.

Yes.
Note that this only works if you dive into Scriptless Script 2p-ECDSA/Schnorr immediately.

It also makes watchtowers for Lightning inherently incompatible with watchtowers for CoinSwaps using absolute timelocks.

A watchtower guarding for CoinSwaps using absolute timelocks would:

* Need to know the funding outpoint it is guarding.
  * Watchtowers for Lightning (and contract-transaction-based CoinSwap) do *not* need to know this, they just need to know a transaction ID that, if confirmed, they will broadcast *another* transaction.
* Need to watch *blockheight*.
  * Watchtowers for Lightning (and contract-transaction-based CoinSwap) only check for transactions matching txids they are watching for.

In particular the first point is a massive privacy lose.
Lightning watchtowers can have the txid they are watching for in the clear, and the transaction they will broadcast in reaction to the watched txid being confirmed is encrypted using a key derived from the transaction with the given txid, and thus do not learn which funding outpoint it is protecting until an attack occurs, which is very good for privacy.

(even if the maker were to run private watchtowers of their own rather than using some public watchtower service, if the private watchtower is hacked it contains information that can be used to identify funding outpoints, thus making them targets.
Thus, it is best if watchtowers, whether public or private, do not contain any privacy-damaging information, to reduce the attack surface on privacy.)

A way to make watchtowers for absolute-timelock CoinSwap also have the same interface (i.e. "Watch for this txid, if it appears onchain broadcast this transaction") as Lightning watchtowers would be to have the timeout tx pay out to a `OP_IF <1 day> OP_CHECKSEQUENCEVERIFY OP_DROP <taker> OP_ELSE <revocationkey> OP_ENDIF OP_CHECKSIGVERIFY`.
The revocation key would be the same private key that is turned over at the end of the CoinSwap.
So, if the absolute timelock expires and the other participant broadcasts the timeout tx, the maker still has an opportunity to revoke that output, for one additional day.

Then, at the end of the CoinSwap where the private key is turned over, the maker can hand the txid of the timeout tx, plus an encrypted transaction that spends from the revocation branch of the timeout tx back to the maker and a tip to the watchtower, to the watchtower, who remains unaware what the funding txo is (it only gets a txid and an encrypted blob, so gets no information).
The same interface can be used by Lightning Poon-Dryja (it is sub-optimal, but usable, for Decker-Russell-Osuntokun), and the watchtower would not even learn if it was watching for a Lightning channel or for a CoinSwap.

Then, if the maker were holding on to the funding outpoint of its incoming HTLC in the hope another taker arrives for its services, and then some silly human trips over the maker hardware power cord, and the condition is not fixed by the timeout, it can still be privately protected by watchtowers.

This comes at the cost of even worse UX if something goes wrong with the swap: an increased timeout.


Regards,
ZmnSCPxj


^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap
  2020-08-11 12:05 [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap Chris Belcher
  2020-08-20 11:17 ` ZmnSCPxj
@ 2020-08-24 19:30 ` Antoine Riard
  2020-08-25  3:16   ` ZmnSCPxj
  2020-08-29 22:03   ` Chris Belcher
  2020-10-03 10:36 ` [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap appendium Chris Belcher
  2 siblings, 2 replies; 24+ messages in thread
From: Antoine Riard @ 2020-08-24 19:30 UTC (permalink / raw)
  To: Chris Belcher, Bitcoin Protocol Discussion

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

Hello Chris,

I think you might have vulnerability issues with the current design.

With regards to the fee model for contract transactions, AFAICT timely
confirmation is a fund safety matter for an intermediate hop. Between the
offchain preimage reveal phase and the offchain private key handover phase,
the next hop can broadcast your outgoing contract transactions, thus
forcing you to claim quickly backward as you can't assume previous hop will
honestly cooperate to achieve the private key handover. This means that
your range of pre-signed RBF-transactions must theoretically have for fee
upper bound the maximum of the contested balance, as game-theory side, it's
rational to you to burn your balance instead of letting your counterparty
claim it after timelock expiration, in face of mempool congestion. Where
the issue dwells is that this fee is pre-committed and not cancelled when
the balance change of ownership by the outgoing hop learning the preimage
of the haslock output. Thus the previous hop is free to broadcast the
highest-fee RBF-transactions and burn your balance, as for him, his balance
is now encoded in the output of the contract transactions on the previous
link, for which he knows the preimage.

Note, I think this is independent of picking up either relative or absolute
timelocks as what matters is the block delta between two links. Of course
you can increase this delta to be week-lengthy and thus decrease the need
for a compelling fee but a) you may force quickly close with contract
transactions if the private key handover doesn't happen soon, you don't
want to be caught by surprise by congestion so you would close far behind
delta period expiration like half of it, and b) you increase the time-value
of makers funds in case of faulty hop, thus logically increasing the maker
fee and making the cost of the system higher in average. I guess a better
solution would be to use dual-anchor outputs has spec'ed out by Lightning,
it lets the party who has a balance at stake unilaterally increase feerate
with a CPFP. The CPFP is obviously a higher blockchain cost but a) it's a
safety mechanism for a worst-case scenario, 99% of the time they won't be
committed, b) you might use this CPFP to aggregate change outputs or other
opportunistically side-usage.

With regards to the preimage release phase, I think you might have a
pinning scenario. The victim would be an intermediate hop, targeted by a
malicious taker. The preimage isn't revealed offchain to this victim hop. A
low-feerate version of the outgoing contract transaction is broadcast and
not going to confirm, assuming a bit of congestion. As preimage is known,
the malicious taker can directly attach a high-fee, low-feerate child
transaction and thus prevent any replacement of the pinned parent by a
honest broadcast of a high-fee RBF-transaction under BIP 125 rules. At the
same time, the malicious taker broadcasts the contract tx on the previous
link and gets it confirmed. At relative timelock expiration, malicious
taker claims back the funds. When the pinned transaction spending the
outgoing link gets evicted (either by replacing child by a higher feerate
or waiting for mempool expiration after 2 weeks), taker gets it confirmed
this time and claims output through hashlock. Given the relative timelock
blocking the victim, there is not even a race.

I guess restraining the contract transaction to one and only one version
would overcome this attack. A honest intermediate hop, as soon as seeing a
relative timelock triggered backward would immediately broadcast the
outgoing link contract tx or if it's already in network mempools broadcast
a higher-feerate child. As you don't have valid multiple contract
transactions, an attacker can't obstruct you to propagate the correct
child, as you are not blind about the parent txid.

Lastly, one downside of using relative timelocks, in case of one downstream
link failure, it forces every other upstream hops to go onchain to protect
against this kind of pinning scenario. And this would be a privacy
breakdown, as a maker would be able to provoke one, thus constraining every
upstream hops to go onchain with the same hash and revealing the CoinSwap
route.

Let me know if I reviewed the correct transactions circuit model or
misunderstood associated semantic. I might be completely wrong, coming from
a LN perspective.

Cheers,
Antoine

Le mar. 11 août 2020 à 13:06, Chris Belcher via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> a écrit :

> I'm currently working on implementing CoinSwap (see my other email
> "Design for a CoinSwap implementation for massively improving Bitcoin
> privacy and fungibility").
>
> CoinSwaps are special because they look just like regular bitcoin
> transactions, so they improve the privacy even for people who do not use
> them. Once CoinSwap is deployed, anyone attempting surveillance of
> bitcoin transactions will be forced to ask themselves the question: how
> do we know this transaction wasn't a CoinSwap?
>
> This email contains a detailed design of the first protocol version. It
> makes use of the building blocks of multi-transaction CoinSwaps, routed
> CoinSwaps, liquidity market, private key handover, and fidelity bonds.
> It does not include PayJoin-with-CoinSwap, but that's in the plan to be
> added later.
>
> == Routed CoinSwap ==
>
> Diagram of CoinSwaps in the route:
>
>     Alice ====> Bob ====> Charlie ====> Alice
>
> Where (====>) means one CoinSwap. Alice gives coins to Bob, who gives
> coins to Charlie, who gives coins to Alice. Alice is the market taker
> and she starts with the hash preimage. She chooses the CoinSwap amount
> and chooses who the makers will be.
>
> This design has one market taker and two market makers in its route, but
> it can easily be extended to any number of makers.
>
> == Multiple transactions ==
>
> Each single CoinSwap is made up of multiple transactions to avoid amount
> correlation
>
>           (a0 BTC) --->     (b0 BTC) --->         (c0 BTC) --->
>     Alice (a1 BTC) ---> Bob (b1 BTC) ---> Charlie (c1 BTC) ---> Alice
>           (a2 BTC) --->     (b2 BTC) --->         (c2 BTC) --->
>
> The arrow (--->) represent funding transactions. The money gets paid to
> a 2-of-2 multisig but after the CoinSwap protocol and private key
> handover is done they will be controlled by the next party in the route.
>
> This example has 6 regular-sized transactions which use approximately
> the same amount of block space as a single JoinMarket coinjoin with 6
> parties (1 taker, 5 makers). Yet the privacy provided by this one
> CoinSwap would be far far greater. It would not have to be repeated in
> the way that Equal-Output CoinJoins must be.
>
> == Direct connections to Alice ===
>
> Only Alice, the taker, knows the entire route, Bob and Charlie just know
> their previous and next transactions. Bob and Charlie do not have direct
> connections with each other, only with Alice.
>
> Diagram of Tor connections:
>
>     Bob      Charlie
>      |       /
>      |      /
>      |     /
>       Alice
>
> When Bob and Charlie communicate, they are actually sending and
> receiving messages via Alice who relays them to Charlie or Bob. This
> helps hide whether the previous or next counterparty in a CoinSwap route
> is a maker or taker.
>
> This doesn't have security issues even in the final steps where private
> keys are handed over, because those private keys are always for 2-of-2
> multisig and so on their own are never enough to steal money.
>
>
> === Miner fees ===
>
> Makers have no incentive to pay any miner fees. They only do
> transactions which earn them an income and are willing to wait a very
> long time for that to happen. By contrast takers want to create
> transactions far more urgently. In JoinMarket we coded a protocol where
> the maker could contribute to miner fees, but the market price offered
> of that trended towards zero. So the reality is that takers will pay all
> the miner fees. Also because makers don't know the taker's time
> preference they don't know how much they should pay in miner fees.
>
> The taker will have to set limits on how large the maker's transactions
> are, otherwise makers could abuse this by having the taker consolidate
> maker's UTXOs for free.
>
> == Funding transaction definitions ==
>
> Funding transactions are those which pay into the 2-of-2 multisig
> addresses.
>
> Definitions:
> I = initial coinswap amount sent by Alice = a0 + a1 + a2
> (WA, WB, WC) = Total value of UTXOs being spent by Alice, Bob, Charlie
>                respectively. Could be called "wallet Alice", "wallet
>                Bob", etc
> (B, C) = Coinswap fees paid by Alice and earned by Bob and Charlie.
> (M1, M2, M3) = Miner fees of the first, second, third, etc sets of
>                funding transactions. Alice will choose what these are
>                since she's paying.
> multisig(A+B) = A 2of2 multisig output with private keys held by A and B
>
> The value in square parentheses refers to the bitcoin amount.
>
> Alice funding txes
>   [WA btc] ---> multisig (Alice+Bob) [I btc]
>                 change [WA-M1-I btc]
> Bob funding txes
>   [WB btc] ---> multisig (Bob+Charlie) [I-M2-B btc]
>                 change [WB-I+B btc]
> Charlie funding txes
>   [WC btc] ---> multisig (Charlie+Alice) [(I-M2-B)-M3-C btc]
>                 change [WC-(I-M2-B)+C btc]
>
> Here we've drawn these transactions as single transactions, but they are
> actually multiple transactions where the outputs add up some value (e.g.
> add up to I in Alice's transactions.)
>
> === Table of balances before and after a successful CoinSwap ===
>
> If a CoinSwap is successful then all the multisig outputs in the funding
> transactions will become controlled unilaterally by one party. We can
> calculate how the balances of each party change.
>
> Party   | Before | After
> --------|--------|-------------------------------------------
> Alice   | WA     | WA-M1-I + (I-M2-B)-M3-C  = WA-M1-M2-M3-B-C
> Bob     | WB     | WB-I+B + I               = WB+B
> Charlie | WC     | WC-(I-M2-B)+C + I-M2-B   = WC+C
>
> After a successful coinswap, we see Alice's balance goes down by the
> miner fees and the coinswap fees. Bob's and Charlie's balance goes up by
> their coinswap fees.
>
> == Contract transaction definitions ==
>
> Contract transactions are those which may spend from the 2-of-2 multisig
> outputs, they transfer the coins into a contract where the coins can be
> spent either by waiting for a timeout or providing a hash preimage
> value. Ideally contract transactions will never be broadcast but their
> existence keeps all parties honest.
>
> M~ is miner fees, which we treat as a random variable, and ultimately
> set by whichever pre-signed RBF tx get mined. When we talk about _the_
> contract tx, we actually mean perhaps 20-30 transactions which only
> differ by the miner fee and have RBF enabled, so they can be broadcasted
> in sequence to get the contract transaction mined regardless of the
> demand for block space.
>
> (Alice+timelock_A OR Bob+hash) = Is an output which can be spent
>                                  either with Alice's private key
>                                  after waiting for a relative
>                                  timelock_A, or by Bob's private key by
>                                  revealing a hash preimage value
>
> Alice contract tx:
>     multisig (Alice+Bob) ---> (Alice+timelock_A OR Bob+hash)
>     [I btc]                   [I-M~ btc]
> Bob contract tx:
>     multisig (Bob+Charlie) ---> (Bob+timelock_B OR Charlie+hash)
>     [I-M2-B btc]                [I-M2-B-M~ btc]
> Charlie contract tx:
>     multisig (Charlie+Alice)  ---> (Charlie+timelock_C OR Alice+hash)
>     [(I-M2-B)-M3-C btc]            [(I-M2-B)-M3-C-M~ btc]
>
>
> === Table of balances before/after CoinSwap using contracts transactions
> ===
>
> In this case the parties had to get their money back by broadcasting and
> mining the contract transactions and waiting for timeouts.
>
> Party   | Before | After
> --------|--------|--------------------------------------------
> Alice   | WA     | WA-M1-I + I-M~                   = WA-M1-M~
> Bob     | WB     | WB-I+B + I-M2-B-M~               = WB-M2-M~
> Charlie | WC     | WC-(I-M2-B)+C + (I-M2-B)-M3-C-M~ = WC-M3-M~
>
> In the timeout failure case, every party pays for their own miner fees.
> And nobody earns or spends any coinswap fees. So even for a market maker
> its possible for their wallet balance to go down sometimes, although as
> we shall see there are anti-DOS features which make this unlikely to
> happen often.
>
> A possible attack by a malicious Alice is that she chooses M1 to be very
> low (e.g. 1 sat/vbyte) and sets M2 and M3 to be very high (e.g. 1000
> sat/vb) and then intentionally aborts, forcing the makers to lose much
> more money in miner fees than the attacker. The attack can be used to
> waste away Bob's and Charlie's coins on miner fees at little cost to the
> malicious taker Alice. So to defend against this attack Bob and Charlie
> must refuse to sign a contract transaction if the corresponding funding
> transaction pays miner fees greater than Alice's funding transaction.
>
>
> There can also be a failure case where each party gets their money using
> hash preimage values instead of timeouts. Note that each party has to
> sweep the output before the timeout expires, so that will cost an
> additional miner fee M~.
>
> Party   | Before | After
> --------|--------|------------------------------------------------------
> Alice   | WA     | WA-M1-I + (I-M2-B)-M3-C-M~ - M~ = WA-M1-M2-M3-B-C-2M~
> Bob     | WB     | WB-I+B + I-M~ - M~              = WB+B-2M~
> Charlie | WC     | WC-(I-M2-B)+C + I-M2-B-M~ - M~  = WC+C-2M~
>
> In this situation the makers Bob and Charlie earn their CoinSwap fees,
> but they pay an additional miner fee twice. Alice pays for all the
> funding transaction miner fees, and the CoinSwap fees, and two
> additional miner fees. And she had her privacy damaged because the
> entire world saw on the blockchain the contract script.
>
> Using the timelock path is like a refund, everyone's coin just comes
> back to them. Using the preimage is like the CoinSwap transaction
> happened, with the coins being sent ahead one hop. Again note that if
> the preimage is used then coinswap fees are paid.
>
> === Staggered timelocks ===
>
> The timelocks are staggered so that if Alice uses the preimage to take
> coins then the right people will also learn the preimage and have enough
> time to be able to get their coins back too. Alice starts with knowledge
> of the hash preimage so she must have a longest timelock.
>
> == EC tweak to reduce one round trip ==
>
> When two parties are agreeing on a 2-of-2 multisig address, they need to
> agree on their public keys. We can avoid one round trip by using the EC
> tweak trick.
>
> When Alice, the taker, downloads the entire offer book for the liquidity
> market, the offers will also contain a EC public key. Alice can tweak
> this to generate a brand new public key for which the maker knows the
> private key. This public key will be one of the keys in the 2-of-2
> multisig. This feature removes one round trip from the protocol.
>
>     q = EC privkey generated by maker
>     Q = q.G = EC pubkey published by maker
>
>     p = nonce generated by taker
>     P = p.G = nonce point calculated by taker
>
>     R = Q + P = pubkey used in bitcoin transaction
>       = (q + p).G
>
> Taker sends unsigned transaction which pays to multisig using pubkey Q,
> and also sends nonce p. The maker can use nonce p to calculate (q + p)
> which is the private key of pubkey R.
>
> Taker doesnt know the privkey because they are unable to find q because
> of the ECDLP.
>
> Any eavesdropper can see the nonce p and easily calculate the point R
> too but Tor communication is encrypted so this isnt a concern.
>
> None of the makers in the route know each other's Q values, so Alice the
> taker will generate a nonce p on their behalf and send it over. I
> believe this cant be used for any kind of attack, because the signing
> maker will always check that the nonce results in the public key
> included in the transaction they're signing, and they'll never sign a
> transaction not in their interests.
>
>
> == Protocol ==
>
> This section is the most important part of this document.
>
> Definitions:
> fund = all funding txes (remember in this multi-tx protocol there can be
>        multiple txes which together make up the funding)
> A htlc = all htlc contract txes (fully signed) belonging to party A
> A unsign htcl = all unsigned htlc contract txes belonging to party A
>                 including the nonce point p used to calculate the
>                 maker's pubkey.
> p = nonce point p used in the tweak EC protocol for calculating the
>     maker's pubkey
> A htlc B/2 = Bob's signature for the 2of2 multisig of the Alice htlc
>              contract tx
> privA(A+B) = private key generated by Alice in the output
>              multisig (Alice+Bob)
>
>
>  | Alice           | Bob             | Charlie         |
>  |=================|=================|=================|
> 0. A unsign htlc ---->               |                 |
> 1.               <---- A htlc B/2    |                 |
> 2. ***** BROADCAST AND MINE ALICE FUNDING TXES ******  |
> 3. A fund+htlc+p ---->               |                 |
> 4.                 | B unsign htlc ---->               |
> 5.                 |               <---- B htlc C/2    |
> 6. ******* BROADCAST AND MINE BOB FUNDING TXES ******* |
> 7.                 | B fund+htlc+p ---->               |
> 8.               <---------------------- C unsign htlc |
> 9.    C htlc A/2 ---------------------->               |
> A. ***** BROADCAST AND MINE CHARLIE FUNDING TXES ***** |
> B.               <---------------------- C fund+htlc+p |
> C. hash preimage ---------------------->               |
> D. hash preimage ---->               |                 |
> E.    privA(A+B) ---->               |                 |
> F.                 |    privB(B+C) ---->               |
> G.               <---------------------- privC(C+A)    |
>
> == Protocol notes ==
> 0-2 are the steps which setup Alice's funding tx and her contract tx for
>     possible refund
> 4-5 same as 0-2 but for Bob
> 8-9 same as 0-2 but for Charlie
> 3,7 is proof to the next party that the previous party has already
>     committed miner fees to getting a transaction mined, and therefore
>     this isnt a DOS attack. The step also reveals the fully-signed
>     contract transaction which the party can use to get their money back
>     with a preimage.
> C-G is revealing the hash preimage to all, and handing over the private
>     keys
>
>
> == Analysis of aborts ==
>
> We will now discuss aborts, which happen when one party halts the
> protocol and doesnt continue. Perhaps they had a power cut, their
> internet broke, or they're a malicious attacker wanting to waste time
> and money. The other party may try to reestablish a connection for some
> time, but eventually must give up.
>
> Number refers to the step number where the abort happened
> e.g. step 1 means that the party aborted instead of the action happening
> on protocol step 1.
>
> The party name refers to what that party does
> e.g. Party1: aborts, Party2/Party3: does a thing in reaction
>
> 0. Alice: aborts. Bob/Charlie: do nothing, they havent lost any time or
>    money
> 1. Bob: aborts. Alice: lost no time or money, try with another Bob.
>    Charlie: do nothing
> 2-3. same as 0.
> 4. Bob: aborts. Charlie: do nothing. Alice: broadcasts her contract tx
>    and waits for the timeout, loses time and money on miner fees, she'll
>    never coinswap with Bob's fidelity bond again.
> 5. Charlie: aborts. Alice/Bob: lose nothing, find another Charlie to
>    coinswap with.
> 6. same as 4.
> 7. similar to 4 but Alice MIGHT not blacklist Bob's fidelity bond,
>    because Bob will also have to broadcast his contract tx and will also
>    lose time and money.
> 8. Charlie: aborts. Bob: broadcast his contract transaction and wait for
>    the timeout to get his money back, also broadcast Alice's contract
>    transaction in retaliation. Alice: waits for the timeout on her htlc
>    tx that Bob broadcasted, will never do a coinswap with Charlie's
>    fidelity bond again.
> 9. Alice: aborts. Charlie: do nothing, no money or time lost. Bob:
>    broadcast bob contract tx and wait for timeout to get money back,
>    comforted by the knowledge that when Alice comes back online she'll
>    have to do the same thing and waste the same amount of time and
>    money.
> A-B. same as 8.
> C-E. Alice: aborts. Bob/Charlie: all broadcast their contract txes and
>      wait for the timeout to get their money back, or if Charlie knows
>      the preimage he uses it to get the money immediately, which Bob can
>      read from the blockchain and also use.
> F. Bob: aborts. Alice: broadcast Charlie htlc tx and use preimage to get
>    money immediately, Alice blacklists Bob's fidelity bond. Charlie:
>    broadcast Bob htlc and use preimage to get money immediately.
> G. Charlie: aborts. Alice: broadcast Charlie htlc and use preimage to
>    get money immediately, Alice blacklists Charlie's fidelity bond. Bob:
>    does nothing, already has his privkey.
>
> ==== Retaliation as DOS-resistance ====
>
> In some situations (e.g. step 8.) if one maker in the coinswap route is
> the victim of a DOS they will retaliate by DOSing the previous maker in
> the route. This may seem unnecessary and unfair (after all why waste
> even more time and block space) but is actually the best way to resist
> DOS because it produces a concrete cost every time a DOS happens.
>
>
> == Analysis of deviations ==
>
> This section discusses what happens if one party deviates from the
> protocol by doing something else, for example broadcasting a htlc
> contract tx when they shouldnt have.
>
> The party name refers to what that party does, followed by other party's
> reactions to it.
> e.g. Party1: does a thing, Party2/Party3: does a thing in reaction
>
> If multiple deviations are possible in a step then they are numbered
> e.g. A1 A2 A2 etc
>
>
> 0-2. Alice/Bob/Charlie: nothing else is possible except following the
>      protocol or aborting
> 3. Alice: broadcasts one or more of the A htlc txes. Bob/Charlie/Dennis:
>    do nothing, they havent lost any time or money.
> 4-6. Bob/Charlie: nothing else is possible except following the protocol
>      or aborting.
> 7. Bob: broadcasts one or more of the B htlc txes, Alice: broadcasts all
>    her own A htlc txes and waits for the timeout to get her money back.
>    Charlie: do nothing
> 8. Charlie: nothing else is possible except following the protocol or
>    aborting.
> 9. Alice: broadcasts one or more of the A htlc txes. Bob: broadcasts all
>    his own A htlc txes and waits for the timeout.
> A. same as 8.
> B. Charlie: broadcasts one or more of the C htlc txes, Alice/Bob:
>    broadcasts all their own htlc txes and waits for the timeout to get
>    their money back.
> C-E1. Alice: broadcasts all of C htlc txes and uses her knowledge of the
>       preimage hash to take the money immediately. Charlie: broadcasts
>       all of B htlc txes and reading the hash value from the blockchain,
>       uses it to take the money from B htlc immediately. Bob: broadcasts
>       all of A htlc txes, and reading hash from the blockchain, uses it
>       to take the money from A htlc immediately.
> C-E2. Alice: broadcast her own A htlc txes, and after a timeout take the
>       money. Bob: broadcast his own B htlc txes and after the timeout
>       take their money. Charlie: broadcast his own C htlc txes and after
>       the timeout take their money.
> F1. Bob: broadcast one or more of A htcl txes and use the hash preimage
>     to get the money immediately. He already knows both privkeys of the
>     multisig so this is pointless and just damages privacy and wastes
>     miner fees. Alice: blacklist Bob's fidelity bond.
> F2. Bob: broadcast one or more of the C htlc txes. Charlie: use preimage
>     to get his money immediately. Bob's actions were pointless. Alice:
>     cant tell whether Bob or Charlie actually broadcasted, so blacklist
>     both fidelity bonds.
> G1. Charlie: broadcast one or more of B htcl txes and use the hash
>     preimage to get the money immediately. He already knows both
>     privkeys of the multisig so this is pointless and just damages
>     privacy and wastes miner fees. Alice: cant tell whether Bob or
>     Charlie actually broadcasted, so blacklist both fidelity bonds.
> G2. Charlie: broadcast one or more of the A htlc txes. Alice: broadcast
>     the remaining A htlc txes and use preimage to get her money
>     immediately. Charlies's actions were pointless. Alice: blacklist
>     Charlie's fidelity bond.
>
> The multisig outputs of the funding transactions can stay unspent
> indefinitely. However the parties must always be watching the network
> and ready to respond with their own sweep using a preimage. This is
> because the other party still possesses a fully-signed contract tx. The
> parties respond in the same way as in steps C-E1, F2 and G2. Alice's
> reaction of blacklisting both fidelity bonds might not be the right way,
> because one maker could use it to get another one blacklisted (as well
> as themselves).
>
>
> == Conclusion ==
>
> This document describes the first version of the protocol which
> implements multi-transaction Coinswap, routed Coinswap, fidelity bonds,
> a liquidity market and private key handover. I describe the protocol and
> also analyze aborts of the protocols and deviations from the protocol.
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap
  2020-08-24 19:30 ` Antoine Riard
@ 2020-08-25  3:16   ` ZmnSCPxj
  2020-09-03  9:00     ` Chris Belcher
  2020-09-05  1:10     ` Antoine Riard
  2020-08-29 22:03   ` Chris Belcher
  1 sibling, 2 replies; 24+ messages in thread
From: ZmnSCPxj @ 2020-08-25  3:16 UTC (permalink / raw)
  To: Antoine Riard, Bitcoin Protocol Discussion


Good morning Antoine,


> Note, I think this is independent of picking up either relative or absolute timelocks as what matters is the block delta between two links.

I believe it is quite dependent on relative locktimes.
Relative locktimes *require* a contract transaction to kick off the relative locktime period.
On the other hand, with Scriptless Script (which we know how to do with 2p-ECDSA only, i.e. doable pre-Taproot), absolute locktimes do not need a contract transaction.

With absolute locktimes + Scriptless SCript, in a single onchain PTLC, one participant holds a completely-signed timelock transaction while the other participant holds a completely-signed pointlock transaction.
This can be arranged by having one side offer partial signatures for the transaction of the other, and once completing the signature, not sharing it with the other until we are ready to actually broadcast the transaction of our own volition.
There is no transaction that both participants hold in completely-signed form.

This should remove most of the shenanigans possible, and makes the 30xRBF safe for any range of fees.
I think.

Since for each PTLC a participant holds only its "own" transaction, it is possible for a participant to define its range of fees for the RBF versions of the transaction it owns, without negotiation with the other participant.
Since the fee involved is deducted from its own transaction, each participant can define this range of RBFed fees and impose it on the partial signatures it gets from the other participant.

--

Private key turnover is still useful even in an absolute-timelock world.

If we need to bump up the block delta between links, it might be impractical to have the total delta of a multi-hop swap be too long at the taker.

As a concrete example, suppose A is a taker who wants to route over makers B and C.
However, B and C require a CLTV delta of 1 week.

If A wants to route "directly" A->B->C->A, then if something bad happens, it could be looking at having its funds locked for two weeks.

To reduce this risk, A can instead first swap A->B->A, then when that completes, A->C->A.
This limits its funding lockup to 1 week.

Private key turnover is useful since as soon as the A->B->A swap completes, it can directly fund the A->C->A swap from the B-side funding transaction of the A->B->A swap.

         |   A->B->A         |    A->C->A           |
         :                   :                      :
      A -:->funding A&B--> B :                      :
         :                   :                      :
      B -:->funding A&B -----:--> funding A&C --> C :
         :                   :                      :
         :                   :C-> funding A&C ------:-> to-cold  A -->
         :                   :                      :

This increases the number of transactions by 1 per swap beyond the first, compared to a direct routing A->B->C->A, but this may be worth it for A if the timelocks involved are too big for A.

With 2p-ECDSA, a funding A&C looks exactly the same as a to-cold A, so B is unable to reliably determine if it is the last hop in the route.

Without private key turnover, A would have:

                      **NO** private key turnover!

         |   A->B->A         |    A->C->A                      |
         :                   :                                 :
      A -:->funding A&B--> B :                                 :
         :                   :                                 :
      B -:->funding A&B -----:--> claim A -> funding A&C --> C :
         :                   :                                 :
         :                   :           C-> funding A&C ------:-> to-cold  A -->
         :                   :                                 :

So if timelock-deltas are possibly-high (to reduce the probability of the MAD-HTLC argument, and other attacks, succeeding), takers might prefer to route by completing one swap first before starting the next one, and private key turnover is useful by reducing blockspace required by each hop.

For reference, this is how it looks like with a single A->B->C->A swap with private key turnover:

         |   A->B->C->A      |
         :                   :
      A -:->funding A&B--> B :
         :                   :
      B -:->funding B&C -> C :
         :                   :
      C -:->funding A&C -----:-> to-cold A -->
         :                   :

This is still smaller than in the A->B->A, A->C->A with private key turnover, by one funding tx per hop.
However, A risks a much higher timelock (twice the timelock).
Thus, A might prefer a lower timelock in exchange for paying for an additional transaction.

Regards,
ZmnSCPxj


^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap
  2020-08-24 19:30 ` Antoine Riard
  2020-08-25  3:16   ` ZmnSCPxj
@ 2020-08-29 22:03   ` Chris Belcher
  2020-08-30 13:38     ` ZmnSCPxj
  2020-09-05  1:07     ` Antoine Riard
  1 sibling, 2 replies; 24+ messages in thread
From: Chris Belcher @ 2020-08-29 22:03 UTC (permalink / raw)
  To: Antoine Riard, Bitcoin Protocol Discussion

Hello Antoine,

Thanks for the very useful insights.

It seems having just one contract transaction which includes anchor
outputs in the style already used by Lightning is one way to fix both
these vulnerabilities.

For the first attack, the other side cannot burn the entire balance
because they only have access to the small amount of satoshi of the
anchor output, and to add miner fees they must add their own inputs. So
they'd burn their own coins to miner fees, not the coins in the contract.

For the second attack, the other side cannot do transaction pinning
because there is only one contract transaction, and all the protections
already developed for use with Lightning apply here as well, such as
CPFP carve out.


Another possible fix for both vulnerabilities is to separate the
timelock and hashlock cases into two separate transactions as described
by ZmnSCPxj in a recent email to this list. This comes at the cost of
breaking private key handover allowing coins to remain unspent indefinitely.

Another possible fix for the second attack, is to encumber the output
with a `1 OP_CSV` which stops that output being spent while unconfirmed.
This seems to be the simplest way if your aim is to only fix the second
attack.


These are all the possible fixes I can think of.

Regards
Chris

On 24/08/2020 20:30, Antoine Riard wrote:
> Hello Chris,
> 
> I think you might have vulnerability issues with the current design.
> 
> With regards to the fee model for contract transactions, AFAICT timely
> confirmation is a fund safety matter for an intermediate hop. Between the
> offchain preimage reveal phase and the offchain private key handover phase,
> the next hop can broadcast your outgoing contract transactions, thus
> forcing you to claim quickly backward as you can't assume previous hop will
> honestly cooperate to achieve the private key handover. This means that
> your range of pre-signed RBF-transactions must theoretically have for fee
> upper bound the maximum of the contested balance, as game-theory side, it's
> rational to you to burn your balance instead of letting your counterparty
> claim it after timelock expiration, in face of mempool congestion. Where
> the issue dwells is that this fee is pre-committed and not cancelled when
> the balance change of ownership by the outgoing hop learning the preimage
> of the haslock output. Thus the previous hop is free to broadcast the
> highest-fee RBF-transactions and burn your balance, as for him, his balance
> is now encoded in the output of the contract transactions on the previous
> link, for which he knows the preimage.
> 
> Note, I think this is independent of picking up either relative or absolute
> timelocks as what matters is the block delta between two links. Of course
> you can increase this delta to be week-lengthy and thus decrease the need
> for a compelling fee but a) you may force quickly close with contract
> transactions if the private key handover doesn't happen soon, you don't
> want to be caught by surprise by congestion so you would close far behind
> delta period expiration like half of it, and b) you increase the time-value
> of makers funds in case of faulty hop, thus logically increasing the maker
> fee and making the cost of the system higher in average. I guess a better
> solution would be to use dual-anchor outputs has spec'ed out by Lightning,
> it lets the party who has a balance at stake unilaterally increase feerate
> with a CPFP. The CPFP is obviously a higher blockchain cost but a) it's a
> safety mechanism for a worst-case scenario, 99% of the time they won't be
> committed, b) you might use this CPFP to aggregate change outputs or other
> opportunistically side-usage.
> 
> With regards to the preimage release phase, I think you might have a
> pinning scenario. The victim would be an intermediate hop, targeted by a
> malicious taker. The preimage isn't revealed offchain to this victim hop. A
> low-feerate version of the outgoing contract transaction is broadcast and
> not going to confirm, assuming a bit of congestion. As preimage is known,
> the malicious taker can directly attach a high-fee, low-feerate child
> transaction and thus prevent any replacement of the pinned parent by a
> honest broadcast of a high-fee RBF-transaction under BIP 125 rules. At the
> same time, the malicious taker broadcasts the contract tx on the previous
> link and gets it confirmed. At relative timelock expiration, malicious
> taker claims back the funds. When the pinned transaction spending the
> outgoing link gets evicted (either by replacing child by a higher feerate
> or waiting for mempool expiration after 2 weeks), taker gets it confirmed
> this time and claims output through hashlock. Given the relative timelock
> blocking the victim, there is not even a race.
> 
> I guess restraining the contract transaction to one and only one version
> would overcome this attack. A honest intermediate hop, as soon as seeing a
> relative timelock triggered backward would immediately broadcast the
> outgoing link contract tx or if it's already in network mempools broadcast
> a higher-feerate child. As you don't have valid multiple contract
> transactions, an attacker can't obstruct you to propagate the correct
> child, as you are not blind about the parent txid.
> 
> Lastly, one downside of using relative timelocks, in case of one downstream
> link failure, it forces every other upstream hops to go onchain to protect
> against this kind of pinning scenario. And this would be a privacy
> breakdown, as a maker would be able to provoke one, thus constraining every
> upstream hops to go onchain with the same hash and revealing the CoinSwap
> route.
> 
> Let me know if I reviewed the correct transactions circuit model or
> misunderstood associated semantic. I might be completely wrong, coming from
> a LN perspective.
> 
> Cheers,
> Antoine
> 
> Le mar. 11 août 2020 à 13:06, Chris Belcher via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> a écrit :
> 
>> I'm currently working on implementing CoinSwap (see my other email
>> "Design for a CoinSwap implementation for massively improving Bitcoin
>> privacy and fungibility").
>>
>> CoinSwaps are special because they look just like regular bitcoin
>> transactions, so they improve the privacy even for people who do not use
>> them. Once CoinSwap is deployed, anyone attempting surveillance of
>> bitcoin transactions will be forced to ask themselves the question: how
>> do we know this transaction wasn't a CoinSwap?
>>
>> This email contains a detailed design of the first protocol version. It
>> makes use of the building blocks of multi-transaction CoinSwaps, routed
>> CoinSwaps, liquidity market, private key handover, and fidelity bonds.
>> It does not include PayJoin-with-CoinSwap, but that's in the plan to be
>> added later.
>>
>> == Routed CoinSwap ==
>>
>> Diagram of CoinSwaps in the route:
>>
>>     Alice ====> Bob ====> Charlie ====> Alice
>>
>> Where (====>) means one CoinSwap. Alice gives coins to Bob, who gives
>> coins to Charlie, who gives coins to Alice. Alice is the market taker
>> and she starts with the hash preimage. She chooses the CoinSwap amount
>> and chooses who the makers will be.
>>
>> This design has one market taker and two market makers in its route, but
>> it can easily be extended to any number of makers.
>>
>> == Multiple transactions ==
>>
>> Each single CoinSwap is made up of multiple transactions to avoid amount
>> correlation
>>
>>           (a0 BTC) --->     (b0 BTC) --->         (c0 BTC) --->
>>     Alice (a1 BTC) ---> Bob (b1 BTC) ---> Charlie (c1 BTC) ---> Alice
>>           (a2 BTC) --->     (b2 BTC) --->         (c2 BTC) --->
>>
>> The arrow (--->) represent funding transactions. The money gets paid to
>> a 2-of-2 multisig but after the CoinSwap protocol and private key
>> handover is done they will be controlled by the next party in the route.
>>
>> This example has 6 regular-sized transactions which use approximately
>> the same amount of block space as a single JoinMarket coinjoin with 6
>> parties (1 taker, 5 makers). Yet the privacy provided by this one
>> CoinSwap would be far far greater. It would not have to be repeated in
>> the way that Equal-Output CoinJoins must be.
>>
>> == Direct connections to Alice ===
>>
>> Only Alice, the taker, knows the entire route, Bob and Charlie just know
>> their previous and next transactions. Bob and Charlie do not have direct
>> connections with each other, only with Alice.
>>
>> Diagram of Tor connections:
>>
>>     Bob      Charlie
>>      |       /
>>      |      /
>>      |     /
>>       Alice
>>
>> When Bob and Charlie communicate, they are actually sending and
>> receiving messages via Alice who relays them to Charlie or Bob. This
>> helps hide whether the previous or next counterparty in a CoinSwap route
>> is a maker or taker.
>>
>> This doesn't have security issues even in the final steps where private
>> keys are handed over, because those private keys are always for 2-of-2
>> multisig and so on their own are never enough to steal money.
>>
>>
>> === Miner fees ===
>>
>> Makers have no incentive to pay any miner fees. They only do
>> transactions which earn them an income and are willing to wait a very
>> long time for that to happen. By contrast takers want to create
>> transactions far more urgently. In JoinMarket we coded a protocol where
>> the maker could contribute to miner fees, but the market price offered
>> of that trended towards zero. So the reality is that takers will pay all
>> the miner fees. Also because makers don't know the taker's time
>> preference they don't know how much they should pay in miner fees.
>>
>> The taker will have to set limits on how large the maker's transactions
>> are, otherwise makers could abuse this by having the taker consolidate
>> maker's UTXOs for free.
>>
>> == Funding transaction definitions ==
>>
>> Funding transactions are those which pay into the 2-of-2 multisig
>> addresses.
>>
>> Definitions:
>> I = initial coinswap amount sent by Alice = a0 + a1 + a2
>> (WA, WB, WC) = Total value of UTXOs being spent by Alice, Bob, Charlie
>>                respectively. Could be called "wallet Alice", "wallet
>>                Bob", etc
>> (B, C) = Coinswap fees paid by Alice and earned by Bob and Charlie.
>> (M1, M2, M3) = Miner fees of the first, second, third, etc sets of
>>                funding transactions. Alice will choose what these are
>>                since she's paying.
>> multisig(A+B) = A 2of2 multisig output with private keys held by A and B
>>
>> The value in square parentheses refers to the bitcoin amount.
>>
>> Alice funding txes
>>   [WA btc] ---> multisig (Alice+Bob) [I btc]
>>                 change [WA-M1-I btc]
>> Bob funding txes
>>   [WB btc] ---> multisig (Bob+Charlie) [I-M2-B btc]
>>                 change [WB-I+B btc]
>> Charlie funding txes
>>   [WC btc] ---> multisig (Charlie+Alice) [(I-M2-B)-M3-C btc]
>>                 change [WC-(I-M2-B)+C btc]
>>
>> Here we've drawn these transactions as single transactions, but they are
>> actually multiple transactions where the outputs add up some value (e.g.
>> add up to I in Alice's transactions.)
>>
>> === Table of balances before and after a successful CoinSwap ===
>>
>> If a CoinSwap is successful then all the multisig outputs in the funding
>> transactions will become controlled unilaterally by one party. We can
>> calculate how the balances of each party change.
>>
>> Party   | Before | After
>> --------|--------|-------------------------------------------
>> Alice   | WA     | WA-M1-I + (I-M2-B)-M3-C  = WA-M1-M2-M3-B-C
>> Bob     | WB     | WB-I+B + I               = WB+B
>> Charlie | WC     | WC-(I-M2-B)+C + I-M2-B   = WC+C
>>
>> After a successful coinswap, we see Alice's balance goes down by the
>> miner fees and the coinswap fees. Bob's and Charlie's balance goes up by
>> their coinswap fees.
>>
>> == Contract transaction definitions ==
>>
>> Contract transactions are those which may spend from the 2-of-2 multisig
>> outputs, they transfer the coins into a contract where the coins can be
>> spent either by waiting for a timeout or providing a hash preimage
>> value. Ideally contract transactions will never be broadcast but their
>> existence keeps all parties honest.
>>
>> M~ is miner fees, which we treat as a random variable, and ultimately
>> set by whichever pre-signed RBF tx get mined. When we talk about _the_
>> contract tx, we actually mean perhaps 20-30 transactions which only
>> differ by the miner fee and have RBF enabled, so they can be broadcasted
>> in sequence to get the contract transaction mined regardless of the
>> demand for block space.
>>
>> (Alice+timelock_A OR Bob+hash) = Is an output which can be spent
>>                                  either with Alice's private key
>>                                  after waiting for a relative
>>                                  timelock_A, or by Bob's private key by
>>                                  revealing a hash preimage value
>>
>> Alice contract tx:
>>     multisig (Alice+Bob) ---> (Alice+timelock_A OR Bob+hash)
>>     [I btc]                   [I-M~ btc]
>> Bob contract tx:
>>     multisig (Bob+Charlie) ---> (Bob+timelock_B OR Charlie+hash)
>>     [I-M2-B btc]                [I-M2-B-M~ btc]
>> Charlie contract tx:
>>     multisig (Charlie+Alice)  ---> (Charlie+timelock_C OR Alice+hash)
>>     [(I-M2-B)-M3-C btc]            [(I-M2-B)-M3-C-M~ btc]
>>
>>
>> === Table of balances before/after CoinSwap using contracts transactions
>> ===
>>
>> In this case the parties had to get their money back by broadcasting and
>> mining the contract transactions and waiting for timeouts.
>>
>> Party   | Before | After
>> --------|--------|--------------------------------------------
>> Alice   | WA     | WA-M1-I + I-M~                   = WA-M1-M~
>> Bob     | WB     | WB-I+B + I-M2-B-M~               = WB-M2-M~
>> Charlie | WC     | WC-(I-M2-B)+C + (I-M2-B)-M3-C-M~ = WC-M3-M~
>>
>> In the timeout failure case, every party pays for their own miner fees.
>> And nobody earns or spends any coinswap fees. So even for a market maker
>> its possible for their wallet balance to go down sometimes, although as
>> we shall see there are anti-DOS features which make this unlikely to
>> happen often.
>>
>> A possible attack by a malicious Alice is that she chooses M1 to be very
>> low (e.g. 1 sat/vbyte) and sets M2 and M3 to be very high (e.g. 1000
>> sat/vb) and then intentionally aborts, forcing the makers to lose much
>> more money in miner fees than the attacker. The attack can be used to
>> waste away Bob's and Charlie's coins on miner fees at little cost to the
>> malicious taker Alice. So to defend against this attack Bob and Charlie
>> must refuse to sign a contract transaction if the corresponding funding
>> transaction pays miner fees greater than Alice's funding transaction.
>>
>>
>> There can also be a failure case where each party gets their money using
>> hash preimage values instead of timeouts. Note that each party has to
>> sweep the output before the timeout expires, so that will cost an
>> additional miner fee M~.
>>
>> Party   | Before | After
>> --------|--------|------------------------------------------------------
>> Alice   | WA     | WA-M1-I + (I-M2-B)-M3-C-M~ - M~ = WA-M1-M2-M3-B-C-2M~
>> Bob     | WB     | WB-I+B + I-M~ - M~              = WB+B-2M~
>> Charlie | WC     | WC-(I-M2-B)+C + I-M2-B-M~ - M~  = WC+C-2M~
>>
>> In this situation the makers Bob and Charlie earn their CoinSwap fees,
>> but they pay an additional miner fee twice. Alice pays for all the
>> funding transaction miner fees, and the CoinSwap fees, and two
>> additional miner fees. And she had her privacy damaged because the
>> entire world saw on the blockchain the contract script.
>>
>> Using the timelock path is like a refund, everyone's coin just comes
>> back to them. Using the preimage is like the CoinSwap transaction
>> happened, with the coins being sent ahead one hop. Again note that if
>> the preimage is used then coinswap fees are paid.
>>
>> === Staggered timelocks ===
>>
>> The timelocks are staggered so that if Alice uses the preimage to take
>> coins then the right people will also learn the preimage and have enough
>> time to be able to get their coins back too. Alice starts with knowledge
>> of the hash preimage so she must have a longest timelock.
>>
>> == EC tweak to reduce one round trip ==
>>
>> When two parties are agreeing on a 2-of-2 multisig address, they need to
>> agree on their public keys. We can avoid one round trip by using the EC
>> tweak trick.
>>
>> When Alice, the taker, downloads the entire offer book for the liquidity
>> market, the offers will also contain a EC public key. Alice can tweak
>> this to generate a brand new public key for which the maker knows the
>> private key. This public key will be one of the keys in the 2-of-2
>> multisig. This feature removes one round trip from the protocol.
>>
>>     q = EC privkey generated by maker
>>     Q = q.G = EC pubkey published by maker
>>
>>     p = nonce generated by taker
>>     P = p.G = nonce point calculated by taker
>>
>>     R = Q + P = pubkey used in bitcoin transaction
>>       = (q + p).G
>>
>> Taker sends unsigned transaction which pays to multisig using pubkey Q,
>> and also sends nonce p. The maker can use nonce p to calculate (q + p)
>> which is the private key of pubkey R.
>>
>> Taker doesnt know the privkey because they are unable to find q because
>> of the ECDLP.
>>
>> Any eavesdropper can see the nonce p and easily calculate the point R
>> too but Tor communication is encrypted so this isnt a concern.
>>
>> None of the makers in the route know each other's Q values, so Alice the
>> taker will generate a nonce p on their behalf and send it over. I
>> believe this cant be used for any kind of attack, because the signing
>> maker will always check that the nonce results in the public key
>> included in the transaction they're signing, and they'll never sign a
>> transaction not in their interests.
>>
>>
>> == Protocol ==
>>
>> This section is the most important part of this document.
>>
>> Definitions:
>> fund = all funding txes (remember in this multi-tx protocol there can be
>>        multiple txes which together make up the funding)
>> A htlc = all htlc contract txes (fully signed) belonging to party A
>> A unsign htcl = all unsigned htlc contract txes belonging to party A
>>                 including the nonce point p used to calculate the
>>                 maker's pubkey.
>> p = nonce point p used in the tweak EC protocol for calculating the
>>     maker's pubkey
>> A htlc B/2 = Bob's signature for the 2of2 multisig of the Alice htlc
>>              contract tx
>> privA(A+B) = private key generated by Alice in the output
>>              multisig (Alice+Bob)
>>
>>
>>  | Alice           | Bob             | Charlie         |
>>  |=================|=================|=================|
>> 0. A unsign htlc ---->               |                 |
>> 1.               <---- A htlc B/2    |                 |
>> 2. ***** BROADCAST AND MINE ALICE FUNDING TXES ******  |
>> 3. A fund+htlc+p ---->               |                 |
>> 4.                 | B unsign htlc ---->               |
>> 5.                 |               <---- B htlc C/2    |
>> 6. ******* BROADCAST AND MINE BOB FUNDING TXES ******* |
>> 7.                 | B fund+htlc+p ---->               |
>> 8.               <---------------------- C unsign htlc |
>> 9.    C htlc A/2 ---------------------->               |
>> A. ***** BROADCAST AND MINE CHARLIE FUNDING TXES ***** |
>> B.               <---------------------- C fund+htlc+p |
>> C. hash preimage ---------------------->               |
>> D. hash preimage ---->               |                 |
>> E.    privA(A+B) ---->               |                 |
>> F.                 |    privB(B+C) ---->               |
>> G.               <---------------------- privC(C+A)    |
>>
>> == Protocol notes ==
>> 0-2 are the steps which setup Alice's funding tx and her contract tx for
>>     possible refund
>> 4-5 same as 0-2 but for Bob
>> 8-9 same as 0-2 but for Charlie
>> 3,7 is proof to the next party that the previous party has already
>>     committed miner fees to getting a transaction mined, and therefore
>>     this isnt a DOS attack. The step also reveals the fully-signed
>>     contract transaction which the party can use to get their money back
>>     with a preimage.
>> C-G is revealing the hash preimage to all, and handing over the private
>>     keys
>>
>>
>> == Analysis of aborts ==
>>
>> We will now discuss aborts, which happen when one party halts the
>> protocol and doesnt continue. Perhaps they had a power cut, their
>> internet broke, or they're a malicious attacker wanting to waste time
>> and money. The other party may try to reestablish a connection for some
>> time, but eventually must give up.
>>
>> Number refers to the step number where the abort happened
>> e.g. step 1 means that the party aborted instead of the action happening
>> on protocol step 1.
>>
>> The party name refers to what that party does
>> e.g. Party1: aborts, Party2/Party3: does a thing in reaction
>>
>> 0. Alice: aborts. Bob/Charlie: do nothing, they havent lost any time or
>>    money
>> 1. Bob: aborts. Alice: lost no time or money, try with another Bob.
>>    Charlie: do nothing
>> 2-3. same as 0.
>> 4. Bob: aborts. Charlie: do nothing. Alice: broadcasts her contract tx
>>    and waits for the timeout, loses time and money on miner fees, she'll
>>    never coinswap with Bob's fidelity bond again.
>> 5. Charlie: aborts. Alice/Bob: lose nothing, find another Charlie to
>>    coinswap with.
>> 6. same as 4.
>> 7. similar to 4 but Alice MIGHT not blacklist Bob's fidelity bond,
>>    because Bob will also have to broadcast his contract tx and will also
>>    lose time and money.
>> 8. Charlie: aborts. Bob: broadcast his contract transaction and wait for
>>    the timeout to get his money back, also broadcast Alice's contract
>>    transaction in retaliation. Alice: waits for the timeout on her htlc
>>    tx that Bob broadcasted, will never do a coinswap with Charlie's
>>    fidelity bond again.
>> 9. Alice: aborts. Charlie: do nothing, no money or time lost. Bob:
>>    broadcast bob contract tx and wait for timeout to get money back,
>>    comforted by the knowledge that when Alice comes back online she'll
>>    have to do the same thing and waste the same amount of time and
>>    money.
>> A-B. same as 8.
>> C-E. Alice: aborts. Bob/Charlie: all broadcast their contract txes and
>>      wait for the timeout to get their money back, or if Charlie knows
>>      the preimage he uses it to get the money immediately, which Bob can
>>      read from the blockchain and also use.
>> F. Bob: aborts. Alice: broadcast Charlie htlc tx and use preimage to get
>>    money immediately, Alice blacklists Bob's fidelity bond. Charlie:
>>    broadcast Bob htlc and use preimage to get money immediately.
>> G. Charlie: aborts. Alice: broadcast Charlie htlc and use preimage to
>>    get money immediately, Alice blacklists Charlie's fidelity bond. Bob:
>>    does nothing, already has his privkey.
>>
>> ==== Retaliation as DOS-resistance ====
>>
>> In some situations (e.g. step 8.) if one maker in the coinswap route is
>> the victim of a DOS they will retaliate by DOSing the previous maker in
>> the route. This may seem unnecessary and unfair (after all why waste
>> even more time and block space) but is actually the best way to resist
>> DOS because it produces a concrete cost every time a DOS happens.
>>
>>
>> == Analysis of deviations ==
>>
>> This section discusses what happens if one party deviates from the
>> protocol by doing something else, for example broadcasting a htlc
>> contract tx when they shouldnt have.
>>
>> The party name refers to what that party does, followed by other party's
>> reactions to it.
>> e.g. Party1: does a thing, Party2/Party3: does a thing in reaction
>>
>> If multiple deviations are possible in a step then they are numbered
>> e.g. A1 A2 A2 etc
>>
>>
>> 0-2. Alice/Bob/Charlie: nothing else is possible except following the
>>      protocol or aborting
>> 3. Alice: broadcasts one or more of the A htlc txes. Bob/Charlie/Dennis:
>>    do nothing, they havent lost any time or money.
>> 4-6. Bob/Charlie: nothing else is possible except following the protocol
>>      or aborting.
>> 7. Bob: broadcasts one or more of the B htlc txes, Alice: broadcasts all
>>    her own A htlc txes and waits for the timeout to get her money back.
>>    Charlie: do nothing
>> 8. Charlie: nothing else is possible except following the protocol or
>>    aborting.
>> 9. Alice: broadcasts one or more of the A htlc txes. Bob: broadcasts all
>>    his own A htlc txes and waits for the timeout.
>> A. same as 8.
>> B. Charlie: broadcasts one or more of the C htlc txes, Alice/Bob:
>>    broadcasts all their own htlc txes and waits for the timeout to get
>>    their money back.
>> C-E1. Alice: broadcasts all of C htlc txes and uses her knowledge of the
>>       preimage hash to take the money immediately. Charlie: broadcasts
>>       all of B htlc txes and reading the hash value from the blockchain,
>>       uses it to take the money from B htlc immediately. Bob: broadcasts
>>       all of A htlc txes, and reading hash from the blockchain, uses it
>>       to take the money from A htlc immediately.
>> C-E2. Alice: broadcast her own A htlc txes, and after a timeout take the
>>       money. Bob: broadcast his own B htlc txes and after the timeout
>>       take their money. Charlie: broadcast his own C htlc txes and after
>>       the timeout take their money.
>> F1. Bob: broadcast one or more of A htcl txes and use the hash preimage
>>     to get the money immediately. He already knows both privkeys of the
>>     multisig so this is pointless and just damages privacy and wastes
>>     miner fees. Alice: blacklist Bob's fidelity bond.
>> F2. Bob: broadcast one or more of the C htlc txes. Charlie: use preimage
>>     to get his money immediately. Bob's actions were pointless. Alice:
>>     cant tell whether Bob or Charlie actually broadcasted, so blacklist
>>     both fidelity bonds.
>> G1. Charlie: broadcast one or more of B htcl txes and use the hash
>>     preimage to get the money immediately. He already knows both
>>     privkeys of the multisig so this is pointless and just damages
>>     privacy and wastes miner fees. Alice: cant tell whether Bob or
>>     Charlie actually broadcasted, so blacklist both fidelity bonds.
>> G2. Charlie: broadcast one or more of the A htlc txes. Alice: broadcast
>>     the remaining A htlc txes and use preimage to get her money
>>     immediately. Charlies's actions were pointless. Alice: blacklist
>>     Charlie's fidelity bond.
>>
>> The multisig outputs of the funding transactions can stay unspent
>> indefinitely. However the parties must always be watching the network
>> and ready to respond with their own sweep using a preimage. This is
>> because the other party still possesses a fully-signed contract tx. The
>> parties respond in the same way as in steps C-E1, F2 and G2. Alice's
>> reaction of blacklisting both fidelity bonds might not be the right way,
>> because one maker could use it to get another one blacklisted (as well
>> as themselves).
>>
>>
>> == Conclusion ==
>>
>> This document describes the first version of the protocol which
>> implements multi-transaction Coinswap, routed Coinswap, fidelity bonds,
>> a liquidity market and private key handover. I describe the protocol and
>> also analyze aborts of the protocols and deviations from the protocol.
>>
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
> 


^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap
  2020-08-29 22:03   ` Chris Belcher
@ 2020-08-30 13:38     ` ZmnSCPxj
  2020-09-05  1:07     ` Antoine Riard
  1 sibling, 0 replies; 24+ messages in thread
From: ZmnSCPxj @ 2020-08-30 13:38 UTC (permalink / raw)
  To: Chris Belcher, Bitcoin Protocol Discussion

Good morning Chris,

> It seems having just one contract transaction which includes anchor
> outputs in the style already used by Lightning is one way to fix both
> these vulnerabilities.
>
> For the first attack, the other side cannot burn the entire balance
> because they only have access to the small amount of satoshi of the
> anchor output, and to add miner fees they must add their own inputs. So
> they'd burn their own coins to miner fees, not the coins in the contract.

Minimum output size is 547 sats, so anchor outputs are that amount at minimum.
A P2SH-P2WPKH output costs something like ~130 vbytes to spend, at 1.000 sat/vbyte that is only ~130 sats to spend a 547 sat anchor output, an opportunistic camper could collect from a few swaps it would have done anyway (e.g. as a passive popular maker?) and broadcast the contract txes of those swaps and then spend the anchor outputs together to get a few sats in a not-so-dusty UTXO, getting (547 - 130) sat per input minus the cost of creating a new tiny output.
Assuming the camper has already claimed its side of the swap in order to put it in cold, this is basically a tiny but free amount of extra money, and if small CoinJoins in JoinMarket are any indication, the 547 sats minus fee to spend it minus fee to create (amortized among the multiple contract txes) new UTXO might be comparable to the actual maker fee.

Since this camping attack is done after the CoinSwap, the maker fidelity bond is a weak protection against this.
The maker can keep around contract transactions indefinitely, and if standard wallets assume they can leave the coins in the same UTXO indefinitely, the contract transactions remain valid indefinitely, including up to fidelity bond timeout.
When the fidelity bond times out, the maker has to destroy its identity anyway, so it could opportunistically wait for a low-fee period after fidelity-bond timeout (we currently get low fee periods once a week, for example, so the camper can wait for at most a week to do this) to publish all still-valid contract transactions, and spend all the anchor outputs including the fidelity bond at the minimum feerate, getting a slightly larger fidelity bond fund, then CoinSwap it to honest makers to clean it, then make a new fidelity bond.
And if one of the takers happens to not be watching for contract tx timeout, it can potentially get free money, again, from the inattention.

(I call it a "camper attack" since the attacking CoinSwap participant waits around in a single place (maker fidelity bond) and snipes passing contract transactions to extract value from them when opportunity (low fee rate) is good, like a camper.)

To protect against this, we should force contract txes to signal RBF, make contract txes min-relay=feerate (requires CPFP package relay at base layer tho), and during low-fee periods we should collect outputs whose private key have been turned over to us, paying at a feerate slightly higher than 547 sat / 130 vbyte fee rate (at which point it becomes uneconomical for campers to mount their sniping attack as they would lose the anchor output amount to fees anyway).

In fact the wallet can do that all the time, and if prevailing fees are above the 547 / 130 rate it will not confirm and the wallet that wants to spend its funds *now* can sign a new RBF tx at higher feerate to replace it.

Low fees, who would have thought that would enable an attack vector....

Regards,
ZmnSCPxj


^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap
  2020-08-25  3:16   ` ZmnSCPxj
@ 2020-09-03  9:00     ` Chris Belcher
  2020-09-03  9:45       ` ZmnSCPxj
  2020-09-05  1:10     ` Antoine Riard
  1 sibling, 1 reply; 24+ messages in thread
From: Chris Belcher @ 2020-09-03  9:00 UTC (permalink / raw)
  To: ZmnSCPxj, Antoine Riard, Bitcoin Protocol Discussion

Hello ZmnSCPxj,


On 25/08/2020 04:16, ZmnSCPxj wrote:
> 
> Good morning Antoine,
> 
> 
>> Note, I think this is independent of picking up either relative or absolute timelocks as what matters is the block delta between two links.
> 
> I believe it is quite dependent on relative locktimes.
> Relative locktimes *require* a contract transaction to kick off the relative locktime period.
> On the other hand, with Scriptless Script (which we know how to do with 2p-ECDSA only, i.e. doable pre-Taproot), absolute locktimes do not need a contract transaction.
> 
> With absolute locktimes + Scriptless SCript, in a single onchain PTLC, one participant holds a completely-signed timelock transaction while the other participant holds a completely-signed pointlock transaction.
> This can be arranged by having one side offer partial signatures for the transaction of the other, and once completing the signature, not sharing it with the other until we are ready to actually broadcast the transaction of our own volition.
> There is no transaction that both participants hold in completely-signed form.
> 
> This should remove most of the shenanigans possible, and makes the 30xRBF safe for any range of fees.
> I think.
> 
> Since for each PTLC a participant holds only its "own" transaction, it is possible for a participant to define its range of fees for the RBF versions of the transaction it owns, without negotiation with the other participant.
> Since the fee involved is deducted from its own transaction, each participant can define this range of RBFed fees and impose it on the partial signatures it gets from the other participant.
> 
> --
> 
> Private key turnover is still useful even in an absolute-timelock world.
> 
> If we need to bump up the block delta between links, it might be impractical to have the total delta of a multi-hop swap be too long at the taker.
> 
> As a concrete example, suppose A is a taker who wants to route over makers B and C.
> However, B and C require a CLTV delta of 1 week.
> 
> If A wants to route "directly" A->B->C->A, then if something bad happens, it could be looking at having its funds locked for two weeks.
> 
> To reduce this risk, A can instead first swap A->B->A, then when that completes, A->C->A.
> This limits its funding lockup to 1 week.
> 
> Private key turnover is useful since as soon as the A->B->A swap completes, it can directly fund the A->C->A swap from the B-side funding transaction of the A->B->A swap.
> 
>          |   A->B->A         |    A->C->A           |
>          :                   :                      :
>       A -:->funding A&B--> B :                      :
>          :                   :                      :
>       B -:->funding A&B -----:--> funding A&C --> C :
>          :                   :                      :
>          :                   :C-> funding A&C ------:-> to-cold  A -->
>          :                   :                      :
> 
> This increases the number of transactions by 1 per swap beyond the first, compared to a direct routing A->B->C->A, but this may be worth it for A if the timelocks involved are too big for A.
> 
> With 2p-ECDSA, a funding A&C looks exactly the same as a to-cold A, so B is unable to reliably determine if it is the last hop in the route.
> 
> Without private key turnover, A would have:
> 
>                       **NO** private key turnover!
> 
>          |   A->B->A         |    A->C->A                      |
>          :                   :                                 :
>       A -:->funding A&B--> B :                                 :
>          :                   :                                 :
>       B -:->funding A&B -----:--> claim A -> funding A&C --> C :
>          :                   :                                 :
>          :                   :           C-> funding A&C ------:-> to-cold  A -->
>          :                   :                                 :
> 
> So if timelock-deltas are possibly-high (to reduce the probability of the MAD-HTLC argument, and other attacks, succeeding), takers might prefer to route by completing one swap first before starting the next one, and private key turnover is useful by reducing blockspace required by each hop.
> 
> For reference, this is how it looks like with a single A->B->C->A swap with private key turnover:
> 
>          |   A->B->C->A      |
>          :                   :
>       A -:->funding A&B--> B :
>          :                   :
>       B -:->funding B&C -> C :
>          :                   :
>       C -:->funding A&C -----:-> to-cold A -->
>          :                   :
> 
> This is still smaller than in the A->B->A, A->C->A with private key turnover, by one funding tx per hop.
> However, A risks a much higher timelock (twice the timelock).
> Thus, A might prefer a lower timelock in exchange for paying for an additional transaction.
> 
> Regards,
> ZmnSCPxj
> 


Separating the timelock and hashlock cases into two separate
transactions is a nice way to solve many of these problems.

A big downside is that it really ruins the property of allowing coins to
remain unspent indefinitely. That has privacy implications: if a coin
remains unspent for longer than 2 weeks (or another short locktime) then
for sure the transaction was not a CoinSwap, and so the anonymity set of
the CoinSwap system would be far smaller For this reason I'm pretty
desperate to solve the vulnerability without losing the coins remaining
unspent indefinitely feature.

We need to solve the vulnerability you found, which I'll call the
riskless theft attempt problem. So what do you think of this solution:


== Building block 1: A, B and C having different contract txes ==

In the original proposal each CoinSwap peer has the same contract
transaction, and either side can broadcast it whenever they like. This
actually isn't necessary. We can have a contract transaction
fully-signed but only known to one peer, with a possibly-different
transaction transaction fully-signed and only known to the other peer.

Obviously for the CoinSwap to work both contract transactions must have
the same hash-time-locked contract, but they can differ in other ways.

== Building block 2: collateral payments ==

The riskless theft attempt problem happens because the previous owner of
the coins knows the fully-signed contract transaction and can broadcast
it at no cost to themselves. So to solve the problem we add a cost.

There is a 2of2 multisig made up of Bob's and Charlie's keys. The
associated contract transaction known to Bob must now also have one of
Bob's single-sig inputs. The outputs are such that some of the money
from Bob's input now ends up in the HTLC output. The result is that
after the CoinSwap if Bob broadcasts his contract transaction but fails
to take the money from the HTLC output, then Bob will have lost money.

I'm calling this idea collateral payments, by analogy with collateral
used for loans. A collateral is someone valuable a debtor puts on the
table, and if they don't repay the loan then they lose the collateral
(presumably the creditor sells it to repay the loan).

Here is a diagram of the contract transaction known to Bob:

    multisig (B+C) [I btc]---> (B+timelock_B OR C+hash) [I+K-M~ btc]
    collateral(B)  [J btc]     (Bob)                    [J-K btc]

where:
    I = CoinSwap amount
    J = Value of Bob's collateral input
    K = Value that Bob loses if he broadcasts his contract tx but doesnt
get the money
    M~ = miner fee (random variable)

The value K is something that can be set by the protocol, and made high
enough so that doing a riskless theft attempt is not worth it. Probably
the value of K will be quite small because the odds of a riskless
payment attempt succeeding is very small (assuming the makers all use
multiple redundant watchtowers). Mostly likely K will be smaller than
M~, so if the collateral is lost to Bob then the miners will the ones to
gain, rather than Charlie.

The other contract transaction, known only to Charlie, does not contain
a collateral input or collateral value (K), because Charlie can't do a
riskless theft attempt to Bob.

If Bob ever spends his collateral input in another transaction, then his
contract transaction will become invalid. However Bob will only be
harming himself, so he'll never do this.

I think this might be a fruitful idea, and soon I'll modify my earlier
detailed design to include it, and see if it can be made to work with no
weird edge cases or attacks.



=== Appendix: Brief historical note about separate contract txes ===

Separating hash- and time-lock branches into different transactions as
in ZmnSCPxj's design is actually very similar to the way the original
2013 CoinSwap design worked:
https://bitcointalk.org/index.php?topic=321228.0

The timelock branch was a transaction locked with nLockTime. And the
hashlock branch is another transaction spending to an output requiring
Carol's public key + hash preimage.

However Adam Gibson in 2017 found a vulnerability to this:
https://github.com/AdamISZ/CoinSwapCS/blob/master/docs/coinswap_tweak.md

The vulnerability is that even though Carol doesn't know the hash
preimage, she can still broadcast the hashlock transaction, which sends
the coins _into_ the hashlock contract, and that invalidates Alice's
timelock transaction. Carol is the only one who can spend the coins but
she doesn't know the hash preimage. The protocol then degenerates to the
MAD (mutually assured destruction) case because the coins are locked
forever.

Adam Gibson's fix was to include the hashlock and timelock branches into
the same transaction known to both peers, which is exactly the design I
used and for which all these vulnerabilities were found.

I realize now there is another way to solve the vulnerability, which is
to include a (Alice pubkey + OP_CLTV timelock) in Carol's contract
transaction. This means that if Carol broadcasts her contract tx (called
TX_2 in the text) without knowing the preimage then Alice can still get
her money back after a timeout, breaking the MAD situation. The crucial
part making this work is that Alice won't know the fully-signed Carol
contract transaction, and so won't be able to unilaterally broadcast it.
I believe this fix makes the scheme equivalent to ZmnSCPxj's idea of
separated transactions, but without scriptless scripts (and so the
scheme is less useful)


Kind regards
CB


^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap
  2020-09-03  9:00     ` Chris Belcher
@ 2020-09-03  9:45       ` ZmnSCPxj
  2020-09-03 10:50         ` Chris Belcher
  0 siblings, 1 reply; 24+ messages in thread
From: ZmnSCPxj @ 2020-09-03  9:45 UTC (permalink / raw)
  To: Chris Belcher; +Cc: Bitcoin Protocol Discussion

Good morning Chris,

> A big downside is that it really ruins the property of allowing coins to
> remain unspent indefinitely. That has privacy implications: if a coin
> remains unspent for longer than 2 weeks (or another short locktime) then
> for sure the transaction was not a CoinSwap, and so the anonymity set of
> the CoinSwap system would be far smaller For this reason I'm pretty
> desperate to solve the vulnerability without losing the coins remaining
> unspent indefinitely feature.

Ah, right.... accept no small privacy leaks!

>
> We need to solve the vulnerability you found, which I'll call the
> riskless theft attempt problem. So what do you think of this solution:
>
> == Building block 1: A, B and C having different contract txes ==
>
> In the original proposal each CoinSwap peer has the same contract
> transaction, and either side can broadcast it whenever they like. This
> actually isn't necessary. We can have a contract transaction
> fully-signed but only known to one peer, with a possibly-different
> transaction transaction fully-signed and only known to the other peer.
>
> Obviously for the CoinSwap to work both contract transactions must have
> the same hash-time-locked contract, but they can differ in other ways.
>
> == Building block 2: collateral payments ==
>
> The riskless theft attempt problem happens because the previous owner of
> the coins knows the fully-signed contract transaction and can broadcast
> it at no cost to themselves. So to solve the problem we add a cost.
>
> There is a 2of2 multisig made up of Bob's and Charlie's keys. The
> associated contract transaction known to Bob must now also have one of
> Bob's single-sig inputs. The outputs are such that some of the money
> from Bob's input now ends up in the HTLC output. The result is that
> after the CoinSwap if Bob broadcasts his contract transaction but fails
> to take the money from the HTLC output, then Bob will have lost money.

Just to be clear:

* B is the one who originally funded the HTLC, and owns the timelock.
* C is the one who will accept the HTLC, and owns the hashlock.

> I'm calling this idea collateral payments, by analogy with collateral
> used for loans. A collateral is someone valuable a debtor puts on the
> table, and if they don't repay the loan then they lose the collateral
> (presumably the creditor sells it to repay the loan).
>
> Here is a diagram of the contract transaction known to Bob:
>
> multisig (B+C) [I btc]---> (B+timelock_B OR C+hash) [I+K-M~ btc]
>
>     collateral(B)  [J btc]     (Bob)                    [J-K btc]
>
>
> where:
> I = CoinSwap amount
> J = Value of Bob's collateral input
> K = Value that Bob loses if he broadcasts his contract tx but doesnt
> get the money
> M~ = miner fee (random variable)
>
> The value K is something that can be set by the protocol, and made high
> enough so that doing a riskless theft attempt is not worth it. Probably
> the value of K will be quite small because the odds of a riskless
> payment attempt succeeding is very small (assuming the makers all use
> multiple redundant watchtowers). Mostly likely K will be smaller than
> M~, so if the collateral is lost to Bob then the miners will the ones to
> gain, rather than Charlie.

This seems a great solution!

Since B is the one offering HTLCs, the taker of a CoinSwap sequence can be B as well.
This means, the taker has to have *some* collateral input, of at least value K, that it cannot swap (because if it tried to swap that amount, it would be unable to provide a collateral as well).

How much does C need to know about the B collateralized contract transaction?
At the minimum, it has to know the output pays out to the correct contract, so it seems to me it has to know the entire B collateralized contract transaction, meaning it learns another input of B ("collateral(B)") that is not otherwise involved in the CoinSwap.
This is important, again, if B is a taker, as it means an unrelated input of B is now learned by C as having the same ownership as B.

A fresh maker that is given its starting funds in a single UTXO needs to split up its funds to make at least one collateral input it can use.

Of note is that the B output also serves as a point for CPFPing this transaction, thus only one version of the B collateralized contract transaction needs to be made, and the B collateralized contract transaction can be at or close to the minimum relay feerate and later CPFPed.

In terms of onchain analysis heuristics, it looks like the B output is change, while the B+C contract output is the send-out, I think, for most cases.
In case of a protocol abort, this heuristic is misled, since both outputs become owned by B due to the protocol abort.
In case of a protocol completion, this heuristic is accurate, since the B+C contract output will be claimed by C, but we do not expect this transaction to be confirmed onchain after protocol completion anyway (it effectively donates K to C or miners), so this is fine.

> The other contract transaction, known only to Charlie, does not contain
> a collateral input or collateral value (K), because Charlie can't do a
> riskless theft attempt to Bob.

Because it has a single output only, the C contract transaction needs to have RBFed versions.

> If Bob ever spends his collateral input in another transaction, then his
> contract transaction will become invalid. However Bob will only be
> harming himself, so he'll never do this.

At least until B gets its own incoming funds in the swap, at which point the collateral input can be used for other purposes (and effectively "releases" the lease of B on that output).

Since C knows the collateral input (it has to, in order to verify the B collateralized contract transaction is correct), it can monitor the collateral input for spendedness, and stop watching for the B collateralized contract transaction in its watchtower(s) if the collateral input is deeply spent.
The B collateralized contract transaction is invalidated if the collateral input is spent, and then only C can spend the funding outpoint at that point, so it can remove that from the watchtower.
This can be significant if C is using a for-pay watchtower that supports deletion of watches, which I believe is planned for watchtowers as well, and reduces the operating cost of C.


Regards,
ZmnSCPxj


^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap
  2020-09-03  9:45       ` ZmnSCPxj
@ 2020-09-03 10:50         ` Chris Belcher
  2020-09-03 23:39           ` ZmnSCPxj
  0 siblings, 1 reply; 24+ messages in thread
From: Chris Belcher @ 2020-09-03 10:50 UTC (permalink / raw)
  To: ZmnSCPxj; +Cc: Bitcoin Protocol Discussion

Hello ZmnSCPxj,

On 03/09/2020 10:45, ZmnSCPxj wrote:
> Good morning Chris,
> 
>> A big downside is that it really ruins the property of allowing coins to
>> remain unspent indefinitely. That has privacy implications: if a coin
>> remains unspent for longer than 2 weeks (or another short locktime) then
>> for sure the transaction was not a CoinSwap, and so the anonymity set of
>> the CoinSwap system would be far smaller For this reason I'm pretty
>> desperate to solve the vulnerability without losing the coins remaining
>> unspent indefinitely feature.
> 
> Ah, right.... accept no small privacy leaks!

I'd argue its not even a small leak. A huge amount of coins remain
unspent for weeks, months and years, and it would be great to add them
to our CoinSwap anonymity set. And also have them benefit from
CoinSwap's anonymity set even if they didn't use CoinSwap.

> This seems a great solution!
> 
> Since B is the one offering HTLCs, the taker of a CoinSwap sequence can be B as well.
> This means, the taker has to have *some* collateral input, of at least value K, that it cannot swap (because if it tried to swap that amount, it would be unable to provide a collateral as well).
> 
> How much does C need to know about the B collateralized contract transaction?
> At the minimum, it has to know the output pays out to the correct contract, so it seems to me it has to know the entire B collateralized contract transaction, meaning it learns another input of B ("collateral(B)") that is not otherwise involved in the CoinSwap.
> This is important, again, if B is a taker, as it means an unrelated input of B is now learned by C as having the same ownership as B.

Yes, in fact that's why in my example I talk about a CoinSwap between
two makers Bob and Charlie. Makers can be reasonably expected to own
multiple UTXOs, but takers cannot. As you say because collateral
payments breaks the ability of takers to sweep their entire wallet
through CoinSwap.

Happily, I think takers themselves don't need to use collateral
payments. Here's an argument to why:

Riskless theft attempts by the taker who no longer controls the coins
actually isnt riskless or costless: Because it reduces the privacy of
the previously-owned coins. If a taker genuinely wanted good privacy
(Which, after all, they're paying for via miner fees and CoinSwap fees)
then they would benefit if the coins they no longer own remain unspent
for a long time, because it increases their anonymity set by making them
hide among a greater crowd of coins which also don't get spent for a
long time.
Assuming that all peers, especially makers, deploy multiple redundant
watchtowers then we can assume the success rate of such a theft attempt
is very low. Because of the very low payoff, and privacy benefit of
leaving coins unspent, then it can be argued that taker software which
attempts such theft will never get popular.

Of course this privacy argument only applies to takers, and if the
CoinSwap contract is between two makers as part of a multi-transaction
CoinSwap then it doesn't apply. So a maker-to-maker CoinSwap must use
collateral payments.

== Leak of first hop ==
Collateral inputs only applying to maker-maker CoinSwaps adds an
additional information leak, which is that makers can now tell whether
their previous peer was a taker or maker, based on whether they used a
collateral input or not.

This should be okay because the first maker doesn't know the final
destination of the coins. This is similar to Tor, where this information
is already leaked, for example when the user connects to a Tor bridge.
The operator of the Tor bridge knows that everyone connecting to it is
not a Tor relay node but an actual user. The operator of the tor bridge
still has no idea where the user's internet traffic goes. Our situation
is actually better than Tor, because in Tor the final relay always knows
that they are an exit node, while the final maker in a CoinSwap might
not know that.

Also, if the taker does happen to own an extra UTXO, they may choose to
use a collateral input anyway, just to pretend that they're a maker.


Regards
CB


^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap
  2020-09-03 10:50         ` Chris Belcher
@ 2020-09-03 23:39           ` ZmnSCPxj
  2020-09-05  2:45             ` ZmnSCPxj
  0 siblings, 1 reply; 24+ messages in thread
From: ZmnSCPxj @ 2020-09-03 23:39 UTC (permalink / raw)
  To: Chris Belcher; +Cc: Bitcoin Protocol Discussion

Good morning Chris,


> > This seems a great solution!
> > Since B is the one offering HTLCs, the taker of a CoinSwap sequence can be B as well.
> > This means, the taker has to have some collateral input, of at least value K, that it cannot swap (because if it tried to swap that amount, it would be unable to provide a collateral as well).
> > How much does C need to know about the B collateralized contract transaction?
> > At the minimum, it has to know the output pays out to the correct contract, so it seems to me it has to know the entire B collateralized contract transaction, meaning it learns another input of B ("collateral(B)") that is not otherwise involved in the CoinSwap.
> > This is important, again, if B is a taker, as it means an unrelated input of B is now learned by C as having the same ownership as B.
>
> Yes, in fact that's why in my example I talk about a CoinSwap between
> two makers Bob and Charlie. Makers can be reasonably expected to own
> multiple UTXOs, but takers cannot. As you say because collateral
> payments breaks the ability of takers to sweep their entire wallet
> through CoinSwap.
>
> Happily, I think takers themselves don't need to use collateral
> payments. Here's an argument to why:
>
> Riskless theft attempts by the taker who no longer controls the coins
> actually isnt riskless or costless: Because it reduces the privacy of
> the previously-owned coins. If a taker genuinely wanted good privacy
> (Which, after all, they're paying for via miner fees and CoinSwap fees)
> then they would benefit if the coins they no longer own remain unspent
> for a long time, because it increases their anonymity set by making them
> hide among a greater crowd of coins which also don't get spent for a
> long time.

Hmmm.

The attack can only be mounted after protocol completion.
Thus, at that point, makers have made money, and takers have paid.
And taker is now in possession of a coin unlinked with its original coin, which is what it paid for.

However, if the taker considers the maker fee it has already paid as a sunk cost, then it would still be rational of them to mount this attack (sunk costs should be ignored).
From this point-of-view, it is possible to do so with only a *subsequent* potential gain, and still no downside.

For example, suppose the taker has already performed an "honest" CoinSwap.
Then, it is now in possession of a UTXO that is not linked with its income stream.
It can then perform another CoinSwap, and *then* perform the attack.
This reveals that the UTXO it provided is involved in a CoinSwap due to publication of the contract transaction, which is not a loss in this case since the UTXO it put in was not linked to its income stream already, via a previous non-attacked CoinSwap.

A taker might rationally consider doing riskless costless theft with its already-delinked coins if it assesses that some maker is not sufficiently online and with insufficient watchtowers (both operating expenditures!) that it has some probability of success times amount it has to seed the theft, versus the fee of that maker plus miner fees.

In response, a maker that is forced to accept a sweeping taker will raise its fee, so as to disincentivize this attack using already-delinked coins.

Hmmm.

In addition, post-Scriptless-Script, assuming relative-locktime-use is "normalized" as proposed in https://lists.linuxfoundation.org/pipermail/lightning-dev/2020-January/002412.html , then the "contract transaction" and its timelock-path-transaction look exactly the same as ordinary (P2SH-)P2WPKH single-input-single-output transactions, thus in that case the taker does ***not*** lose any privacy.
This removes whatever protection you can get from contract transaction blackmail.

--

The above suggests to me that you still want the collateralized contract transaction from the taker as well.

A sweeping taker can split its funds in half, swapping one half (and using the remainder for collateral input), then after that swap, using the already-swapped coins for the collateral input of the remaining unswapped coins.
This leaks information: you are now linking a post-mix coin with a pre-mix coin, not onchain (if you do not mount an attack, which you probably will not) but you *do* reveal this information to the maker (one input is from the funding tx that is pre-mix, the collateral input is from the post-mix coin).

The only protection here is that the maker is unaware of the fact that your input coin is pre-mix and your collateral input is post-mix, so it can be hard for a maker to *use* this information.


However, it might be possible to prevent the maker from learning the collateral input at all.

If my understanding of BIP-143 is correct, inputs are hashed separately (`hashPrevouts`) from outputs (`hashOutputs`).
Bob can provide the `hashPrevouts` as an opaque hash, while providing a decommitment of `hashOutputs` to show that the outputs of the collateralized contract transaction are correct, which is all that Charlie really needs to know.

Bob is incentivized to provide the correct `hashPrevouts`, because if it provides an incorrect `hashPrevouts` it cannot get a signature for a transaction it can use in case of a protocol abort, thus potentially losing its money in case of a protocol abort.
Conversely, Charlie does not care *where* Bob gets the funds that goes into its contract output come from, it only cares that the Bob collateralized contract output is I+K.
It loses nothing to sign that transaction, and it would prefer that transaction since its own contract output is only I.

This solution is mildly "unclean" as it depends on the details of the sighash algorithm, though, and is not proposed seriously.
Hopefully nobody will change the sighash algorithm anytime soon.........

In addition, it complicates reusing Lightning watchtowers.
Lightning watchtowers currently trigger on txid (i.e. it would have triggered on the txid of the B collateralized contract tx), but watching this needs to trigger on the spend of a txo, since it is not possible to prove that a specific `hashPrevouts` etc. goes with a specific txid without revealing the whole tx (which is precisely what we are trying to avoid), as both are hashes.
Watchtowers may need to be entrusted with privkeys, or need to wait for `SIGHASH_ANYPREVOUT` so that the exact txid of the B collateralized contract tx does not need to be fixed at signing time, thus this solution is undesirable as well.

Regards,
ZmnSCPxj


^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap
  2020-08-29 22:03   ` Chris Belcher
  2020-08-30 13:38     ` ZmnSCPxj
@ 2020-09-05  1:07     ` Antoine Riard
  2020-09-06  3:06       ` seid Mohammed
  1 sibling, 1 reply; 24+ messages in thread
From: Antoine Riard @ 2020-09-05  1:07 UTC (permalink / raw)
  To: Chris Belcher; +Cc: Bitcoin Protocol Discussion

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

Hi Chris,

I forgot to underscore that contract transaction output must be grieved by
at least a CSV of 1. Otherwise, a malicious counterparty can occupy with
garbage both the timelock-or-preimage output and its own anchor output thus
blocking you to use the bumping capability of your own anchor ouput.

A part of this, I think it works.

> Another possible fix for both vulnerabilities is to separate the
> timelock and hashlock cases into two separate transactions as described
> by ZmnSCPxj in a recent email to this list. This comes at the cost of
> breaking private key handover allowing coins to remain unspent
indefinitely.

This works too assuming these second-stage transactions aren't malleable at
all (e.g SIGASH_SINGLE). Other ways you can increase their feerate/absolute
fee and you're back to the initial situation.

Beyond note also that anchors-on-second-stage are more risky here, as
otherwise your counterparty can again attach a low-feerate child. In case
of concurrent broadcast (assuming you haven't achieved to claim the output
before timelock expiration due to network outage/mempool-congestion) you
might not see your counterparty version. I.e, your local mempool has the
timelock tx and the rest of the network the hashlock and your CPFP bump
won't propagate as being an orphan.

So you're left with a RBF-range, which is mostly okay minus a theoretical
concern : a party guessing the odds to lose the balance are high can
broadcast/send out-of-band the highest-fee bound to miners thus
incentivizing them to censor a honest, low-fee  preimage tx. A
"nothing-at-stake-for-genuinely-evil-counterparty" issue.

> Another possible fix for the second attack, is to encumber the output
> with a `1 OP_CSV` which stops that output being spent while unconfirmed.
> This seems to be the simplest way if your aim is to only fix the second
> attack.

Yes you don't package fee malleability so an honest party can always
unilaterally bump the feerate and override concurrent bids.


That said, I would lean towards anchors and thus unileratel fee bumping.
Feerate interactivity among a multi-party protocol should be seen as an
oracle to leak the full-node of a participant. By sending a range of
conflicting transactions with different feerates to a set of network
mempools I could theoretically observe variations in the protocol feerate
announced.

I would recommend you to have a look on this paper, if it's not done yet :
https://arxiv.org/pdf/2007.00764.pdf, the first one analyzing privacy
holistically across Bitcoin layers.

Cheers,

Antoine

Le sam. 29 août 2020 à 18:03, Chris Belcher <belcher@riseup.net> a écrit :

> Hello Antoine,
>
> Thanks for the very useful insights.
>
> It seems having just one contract transaction which includes anchor
> outputs in the style already used by Lightning is one way to fix both
> these vulnerabilities.
>
> For the first attack, the other side cannot burn the entire balance
> because they only have access to the small amount of satoshi of the
> anchor output, and to add miner fees they must add their own inputs. So
> they'd burn their own coins to miner fees, not the coins in the contract.
>
> For the second attack, the other side cannot do transaction pinning
> because there is only one contract transaction, and all the protections
> already developed for use with Lightning apply here as well, such as
> CPFP carve out.
>
>
> Another possible fix for both vulnerabilities is to separate the
> timelock and hashlock cases into two separate transactions as described
> by ZmnSCPxj in a recent email to this list. This comes at the cost of
> breaking private key handover allowing coins to remain unspent
> indefinitely.
>
> Another possible fix for the second attack, is to encumber the output
> with a `1 OP_CSV` which stops that output being spent while unconfirmed.
> This seems to be the simplest way if your aim is to only fix the second
> attack.
>
>
> These are all the possible fixes I can think of.
>
> Regards
> Chris
>
> On 24/08/2020 20:30, Antoine Riard wrote:
> > Hello Chris,
> >
> > I think you might have vulnerability issues with the current design.
> >
> > With regards to the fee model for contract transactions, AFAICT timely
> > confirmation is a fund safety matter for an intermediate hop. Between the
> > offchain preimage reveal phase and the offchain private key handover
> phase,
> > the next hop can broadcast your outgoing contract transactions, thus
> > forcing you to claim quickly backward as you can't assume previous hop
> will
> > honestly cooperate to achieve the private key handover. This means that
> > your range of pre-signed RBF-transactions must theoretically have for fee
> > upper bound the maximum of the contested balance, as game-theory side,
> it's
> > rational to you to burn your balance instead of letting your counterparty
> > claim it after timelock expiration, in face of mempool congestion. Where
> > the issue dwells is that this fee is pre-committed and not cancelled when
> > the balance change of ownership by the outgoing hop learning the preimage
> > of the haslock output. Thus the previous hop is free to broadcast the
> > highest-fee RBF-transactions and burn your balance, as for him, his
> balance
> > is now encoded in the output of the contract transactions on the previous
> > link, for which he knows the preimage.
> >
> > Note, I think this is independent of picking up either relative or
> absolute
> > timelocks as what matters is the block delta between two links. Of course
> > you can increase this delta to be week-lengthy and thus decrease the need
> > for a compelling fee but a) you may force quickly close with contract
> > transactions if the private key handover doesn't happen soon, you don't
> > want to be caught by surprise by congestion so you would close far behind
> > delta period expiration like half of it, and b) you increase the
> time-value
> > of makers funds in case of faulty hop, thus logically increasing the
> maker
> > fee and making the cost of the system higher in average. I guess a better
> > solution would be to use dual-anchor outputs has spec'ed out by
> Lightning,
> > it lets the party who has a balance at stake unilaterally increase
> feerate
> > with a CPFP. The CPFP is obviously a higher blockchain cost but a) it's a
> > safety mechanism for a worst-case scenario, 99% of the time they won't be
> > committed, b) you might use this CPFP to aggregate change outputs or
> other
> > opportunistically side-usage.
> >
> > With regards to the preimage release phase, I think you might have a
> > pinning scenario. The victim would be an intermediate hop, targeted by a
> > malicious taker. The preimage isn't revealed offchain to this victim
> hop. A
> > low-feerate version of the outgoing contract transaction is broadcast and
> > not going to confirm, assuming a bit of congestion. As preimage is known,
> > the malicious taker can directly attach a high-fee, low-feerate child
> > transaction and thus prevent any replacement of the pinned parent by a
> > honest broadcast of a high-fee RBF-transaction under BIP 125 rules. At
> the
> > same time, the malicious taker broadcasts the contract tx on the previous
> > link and gets it confirmed. At relative timelock expiration, malicious
> > taker claims back the funds. When the pinned transaction spending the
> > outgoing link gets evicted (either by replacing child by a higher feerate
> > or waiting for mempool expiration after 2 weeks), taker gets it confirmed
> > this time and claims output through hashlock. Given the relative timelock
> > blocking the victim, there is not even a race.
> >
> > I guess restraining the contract transaction to one and only one version
> > would overcome this attack. A honest intermediate hop, as soon as seeing
> a
> > relative timelock triggered backward would immediately broadcast the
> > outgoing link contract tx or if it's already in network mempools
> broadcast
> > a higher-feerate child. As you don't have valid multiple contract
> > transactions, an attacker can't obstruct you to propagate the correct
> > child, as you are not blind about the parent txid.
> >
> > Lastly, one downside of using relative timelocks, in case of one
> downstream
> > link failure, it forces every other upstream hops to go onchain to
> protect
> > against this kind of pinning scenario. And this would be a privacy
> > breakdown, as a maker would be able to provoke one, thus constraining
> every
> > upstream hops to go onchain with the same hash and revealing the CoinSwap
> > route.
> >
> > Let me know if I reviewed the correct transactions circuit model or
> > misunderstood associated semantic. I might be completely wrong, coming
> from
> > a LN perspective.
> >
> > Cheers,
> > Antoine
> >
> > Le mar. 11 août 2020 à 13:06, Chris Belcher via bitcoin-dev <
> > bitcoin-dev@lists.linuxfoundation.org> a écrit :
> >
> >> I'm currently working on implementing CoinSwap (see my other email
> >> "Design for a CoinSwap implementation for massively improving Bitcoin
> >> privacy and fungibility").
> >>
> >> CoinSwaps are special because they look just like regular bitcoin
> >> transactions, so they improve the privacy even for people who do not use
> >> them. Once CoinSwap is deployed, anyone attempting surveillance of
> >> bitcoin transactions will be forced to ask themselves the question: how
> >> do we know this transaction wasn't a CoinSwap?
> >>
> >> This email contains a detailed design of the first protocol version. It
> >> makes use of the building blocks of multi-transaction CoinSwaps, routed
> >> CoinSwaps, liquidity market, private key handover, and fidelity bonds.
> >> It does not include PayJoin-with-CoinSwap, but that's in the plan to be
> >> added later.
> >>
> >> == Routed CoinSwap ==
> >>
> >> Diagram of CoinSwaps in the route:
> >>
> >>     Alice ====> Bob ====> Charlie ====> Alice
> >>
> >> Where (====>) means one CoinSwap. Alice gives coins to Bob, who gives
> >> coins to Charlie, who gives coins to Alice. Alice is the market taker
> >> and she starts with the hash preimage. She chooses the CoinSwap amount
> >> and chooses who the makers will be.
> >>
> >> This design has one market taker and two market makers in its route, but
> >> it can easily be extended to any number of makers.
> >>
> >> == Multiple transactions ==
> >>
> >> Each single CoinSwap is made up of multiple transactions to avoid amount
> >> correlation
> >>
> >>           (a0 BTC) --->     (b0 BTC) --->         (c0 BTC) --->
> >>     Alice (a1 BTC) ---> Bob (b1 BTC) ---> Charlie (c1 BTC) ---> Alice
> >>           (a2 BTC) --->     (b2 BTC) --->         (c2 BTC) --->
> >>
> >> The arrow (--->) represent funding transactions. The money gets paid to
> >> a 2-of-2 multisig but after the CoinSwap protocol and private key
> >> handover is done they will be controlled by the next party in the route.
> >>
> >> This example has 6 regular-sized transactions which use approximately
> >> the same amount of block space as a single JoinMarket coinjoin with 6
> >> parties (1 taker, 5 makers). Yet the privacy provided by this one
> >> CoinSwap would be far far greater. It would not have to be repeated in
> >> the way that Equal-Output CoinJoins must be.
> >>
> >> == Direct connections to Alice ===
> >>
> >> Only Alice, the taker, knows the entire route, Bob and Charlie just know
> >> their previous and next transactions. Bob and Charlie do not have direct
> >> connections with each other, only with Alice.
> >>
> >> Diagram of Tor connections:
> >>
> >>     Bob      Charlie
> >>      |       /
> >>      |      /
> >>      |     /
> >>       Alice
> >>
> >> When Bob and Charlie communicate, they are actually sending and
> >> receiving messages via Alice who relays them to Charlie or Bob. This
> >> helps hide whether the previous or next counterparty in a CoinSwap route
> >> is a maker or taker.
> >>
> >> This doesn't have security issues even in the final steps where private
> >> keys are handed over, because those private keys are always for 2-of-2
> >> multisig and so on their own are never enough to steal money.
> >>
> >>
> >> === Miner fees ===
> >>
> >> Makers have no incentive to pay any miner fees. They only do
> >> transactions which earn them an income and are willing to wait a very
> >> long time for that to happen. By contrast takers want to create
> >> transactions far more urgently. In JoinMarket we coded a protocol where
> >> the maker could contribute to miner fees, but the market price offered
> >> of that trended towards zero. So the reality is that takers will pay all
> >> the miner fees. Also because makers don't know the taker's time
> >> preference they don't know how much they should pay in miner fees.
> >>
> >> The taker will have to set limits on how large the maker's transactions
> >> are, otherwise makers could abuse this by having the taker consolidate
> >> maker's UTXOs for free.
> >>
> >> == Funding transaction definitions ==
> >>
> >> Funding transactions are those which pay into the 2-of-2 multisig
> >> addresses.
> >>
> >> Definitions:
> >> I = initial coinswap amount sent by Alice = a0 + a1 + a2
> >> (WA, WB, WC) = Total value of UTXOs being spent by Alice, Bob, Charlie
> >>                respectively. Could be called "wallet Alice", "wallet
> >>                Bob", etc
> >> (B, C) = Coinswap fees paid by Alice and earned by Bob and Charlie.
> >> (M1, M2, M3) = Miner fees of the first, second, third, etc sets of
> >>                funding transactions. Alice will choose what these are
> >>                since she's paying.
> >> multisig(A+B) = A 2of2 multisig output with private keys held by A and B
> >>
> >> The value in square parentheses refers to the bitcoin amount.
> >>
> >> Alice funding txes
> >>   [WA btc] ---> multisig (Alice+Bob) [I btc]
> >>                 change [WA-M1-I btc]
> >> Bob funding txes
> >>   [WB btc] ---> multisig (Bob+Charlie) [I-M2-B btc]
> >>                 change [WB-I+B btc]
> >> Charlie funding txes
> >>   [WC btc] ---> multisig (Charlie+Alice) [(I-M2-B)-M3-C btc]
> >>                 change [WC-(I-M2-B)+C btc]
> >>
> >> Here we've drawn these transactions as single transactions, but they are
> >> actually multiple transactions where the outputs add up some value (e.g.
> >> add up to I in Alice's transactions.)
> >>
> >> === Table of balances before and after a successful CoinSwap ===
> >>
> >> If a CoinSwap is successful then all the multisig outputs in the funding
> >> transactions will become controlled unilaterally by one party. We can
> >> calculate how the balances of each party change.
> >>
> >> Party   | Before | After
> >> --------|--------|-------------------------------------------
> >> Alice   | WA     | WA-M1-I + (I-M2-B)-M3-C  = WA-M1-M2-M3-B-C
> >> Bob     | WB     | WB-I+B + I               = WB+B
> >> Charlie | WC     | WC-(I-M2-B)+C + I-M2-B   = WC+C
> >>
> >> After a successful coinswap, we see Alice's balance goes down by the
> >> miner fees and the coinswap fees. Bob's and Charlie's balance goes up by
> >> their coinswap fees.
> >>
> >> == Contract transaction definitions ==
> >>
> >> Contract transactions are those which may spend from the 2-of-2 multisig
> >> outputs, they transfer the coins into a contract where the coins can be
> >> spent either by waiting for a timeout or providing a hash preimage
> >> value. Ideally contract transactions will never be broadcast but their
> >> existence keeps all parties honest.
> >>
> >> M~ is miner fees, which we treat as a random variable, and ultimately
> >> set by whichever pre-signed RBF tx get mined. When we talk about _the_
> >> contract tx, we actually mean perhaps 20-30 transactions which only
> >> differ by the miner fee and have RBF enabled, so they can be broadcasted
> >> in sequence to get the contract transaction mined regardless of the
> >> demand for block space.
> >>
> >> (Alice+timelock_A OR Bob+hash) = Is an output which can be spent
> >>                                  either with Alice's private key
> >>                                  after waiting for a relative
> >>                                  timelock_A, or by Bob's private key by
> >>                                  revealing a hash preimage value
> >>
> >> Alice contract tx:
> >>     multisig (Alice+Bob) ---> (Alice+timelock_A OR Bob+hash)
> >>     [I btc]                   [I-M~ btc]
> >> Bob contract tx:
> >>     multisig (Bob+Charlie) ---> (Bob+timelock_B OR Charlie+hash)
> >>     [I-M2-B btc]                [I-M2-B-M~ btc]
> >> Charlie contract tx:
> >>     multisig (Charlie+Alice)  ---> (Charlie+timelock_C OR Alice+hash)
> >>     [(I-M2-B)-M3-C btc]            [(I-M2-B)-M3-C-M~ btc]
> >>
> >>
> >> === Table of balances before/after CoinSwap using contracts transactions
> >> ===
> >>
> >> In this case the parties had to get their money back by broadcasting and
> >> mining the contract transactions and waiting for timeouts.
> >>
> >> Party   | Before | After
> >> --------|--------|--------------------------------------------
> >> Alice   | WA     | WA-M1-I + I-M~                   = WA-M1-M~
> >> Bob     | WB     | WB-I+B + I-M2-B-M~               = WB-M2-M~
> >> Charlie | WC     | WC-(I-M2-B)+C + (I-M2-B)-M3-C-M~ = WC-M3-M~
> >>
> >> In the timeout failure case, every party pays for their own miner fees.
> >> And nobody earns or spends any coinswap fees. So even for a market maker
> >> its possible for their wallet balance to go down sometimes, although as
> >> we shall see there are anti-DOS features which make this unlikely to
> >> happen often.
> >>
> >> A possible attack by a malicious Alice is that she chooses M1 to be very
> >> low (e.g. 1 sat/vbyte) and sets M2 and M3 to be very high (e.g. 1000
> >> sat/vb) and then intentionally aborts, forcing the makers to lose much
> >> more money in miner fees than the attacker. The attack can be used to
> >> waste away Bob's and Charlie's coins on miner fees at little cost to the
> >> malicious taker Alice. So to defend against this attack Bob and Charlie
> >> must refuse to sign a contract transaction if the corresponding funding
> >> transaction pays miner fees greater than Alice's funding transaction.
> >>
> >>
> >> There can also be a failure case where each party gets their money using
> >> hash preimage values instead of timeouts. Note that each party has to
> >> sweep the output before the timeout expires, so that will cost an
> >> additional miner fee M~.
> >>
> >> Party   | Before | After
> >> --------|--------|------------------------------------------------------
> >> Alice   | WA     | WA-M1-I + (I-M2-B)-M3-C-M~ - M~ = WA-M1-M2-M3-B-C-2M~
> >> Bob     | WB     | WB-I+B + I-M~ - M~              = WB+B-2M~
> >> Charlie | WC     | WC-(I-M2-B)+C + I-M2-B-M~ - M~  = WC+C-2M~
> >>
> >> In this situation the makers Bob and Charlie earn their CoinSwap fees,
> >> but they pay an additional miner fee twice. Alice pays for all the
> >> funding transaction miner fees, and the CoinSwap fees, and two
> >> additional miner fees. And she had her privacy damaged because the
> >> entire world saw on the blockchain the contract script.
> >>
> >> Using the timelock path is like a refund, everyone's coin just comes
> >> back to them. Using the preimage is like the CoinSwap transaction
> >> happened, with the coins being sent ahead one hop. Again note that if
> >> the preimage is used then coinswap fees are paid.
> >>
> >> === Staggered timelocks ===
> >>
> >> The timelocks are staggered so that if Alice uses the preimage to take
> >> coins then the right people will also learn the preimage and have enough
> >> time to be able to get their coins back too. Alice starts with knowledge
> >> of the hash preimage so she must have a longest timelock.
> >>
> >> == EC tweak to reduce one round trip ==
> >>
> >> When two parties are agreeing on a 2-of-2 multisig address, they need to
> >> agree on their public keys. We can avoid one round trip by using the EC
> >> tweak trick.
> >>
> >> When Alice, the taker, downloads the entire offer book for the liquidity
> >> market, the offers will also contain a EC public key. Alice can tweak
> >> this to generate a brand new public key for which the maker knows the
> >> private key. This public key will be one of the keys in the 2-of-2
> >> multisig. This feature removes one round trip from the protocol.
> >>
> >>     q = EC privkey generated by maker
> >>     Q = q.G = EC pubkey published by maker
> >>
> >>     p = nonce generated by taker
> >>     P = p.G = nonce point calculated by taker
> >>
> >>     R = Q + P = pubkey used in bitcoin transaction
> >>       = (q + p).G
> >>
> >> Taker sends unsigned transaction which pays to multisig using pubkey Q,
> >> and also sends nonce p. The maker can use nonce p to calculate (q + p)
> >> which is the private key of pubkey R.
> >>
> >> Taker doesnt know the privkey because they are unable to find q because
> >> of the ECDLP.
> >>
> >> Any eavesdropper can see the nonce p and easily calculate the point R
> >> too but Tor communication is encrypted so this isnt a concern.
> >>
> >> None of the makers in the route know each other's Q values, so Alice the
> >> taker will generate a nonce p on their behalf and send it over. I
> >> believe this cant be used for any kind of attack, because the signing
> >> maker will always check that the nonce results in the public key
> >> included in the transaction they're signing, and they'll never sign a
> >> transaction not in their interests.
> >>
> >>
> >> == Protocol ==
> >>
> >> This section is the most important part of this document.
> >>
> >> Definitions:
> >> fund = all funding txes (remember in this multi-tx protocol there can be
> >>        multiple txes which together make up the funding)
> >> A htlc = all htlc contract txes (fully signed) belonging to party A
> >> A unsign htcl = all unsigned htlc contract txes belonging to party A
> >>                 including the nonce point p used to calculate the
> >>                 maker's pubkey.
> >> p = nonce point p used in the tweak EC protocol for calculating the
> >>     maker's pubkey
> >> A htlc B/2 = Bob's signature for the 2of2 multisig of the Alice htlc
> >>              contract tx
> >> privA(A+B) = private key generated by Alice in the output
> >>              multisig (Alice+Bob)
> >>
> >>
> >>  | Alice           | Bob             | Charlie         |
> >>  |=================|=================|=================|
> >> 0. A unsign htlc ---->               |                 |
> >> 1.               <---- A htlc B/2    |                 |
> >> 2. ***** BROADCAST AND MINE ALICE FUNDING TXES ******  |
> >> 3. A fund+htlc+p ---->               |                 |
> >> 4.                 | B unsign htlc ---->               |
> >> 5.                 |               <---- B htlc C/2    |
> >> 6. ******* BROADCAST AND MINE BOB FUNDING TXES ******* |
> >> 7.                 | B fund+htlc+p ---->               |
> >> 8.               <---------------------- C unsign htlc |
> >> 9.    C htlc A/2 ---------------------->               |
> >> A. ***** BROADCAST AND MINE CHARLIE FUNDING TXES ***** |
> >> B.               <---------------------- C fund+htlc+p |
> >> C. hash preimage ---------------------->               |
> >> D. hash preimage ---->               |                 |
> >> E.    privA(A+B) ---->               |                 |
> >> F.                 |    privB(B+C) ---->               |
> >> G.               <---------------------- privC(C+A)    |
> >>
> >> == Protocol notes ==
> >> 0-2 are the steps which setup Alice's funding tx and her contract tx for
> >>     possible refund
> >> 4-5 same as 0-2 but for Bob
> >> 8-9 same as 0-2 but for Charlie
> >> 3,7 is proof to the next party that the previous party has already
> >>     committed miner fees to getting a transaction mined, and therefore
> >>     this isnt a DOS attack. The step also reveals the fully-signed
> >>     contract transaction which the party can use to get their money back
> >>     with a preimage.
> >> C-G is revealing the hash preimage to all, and handing over the private
> >>     keys
> >>
> >>
> >> == Analysis of aborts ==
> >>
> >> We will now discuss aborts, which happen when one party halts the
> >> protocol and doesnt continue. Perhaps they had a power cut, their
> >> internet broke, or they're a malicious attacker wanting to waste time
> >> and money. The other party may try to reestablish a connection for some
> >> time, but eventually must give up.
> >>
> >> Number refers to the step number where the abort happened
> >> e.g. step 1 means that the party aborted instead of the action happening
> >> on protocol step 1.
> >>
> >> The party name refers to what that party does
> >> e.g. Party1: aborts, Party2/Party3: does a thing in reaction
> >>
> >> 0. Alice: aborts. Bob/Charlie: do nothing, they havent lost any time or
> >>    money
> >> 1. Bob: aborts. Alice: lost no time or money, try with another Bob.
> >>    Charlie: do nothing
> >> 2-3. same as 0.
> >> 4. Bob: aborts. Charlie: do nothing. Alice: broadcasts her contract tx
> >>    and waits for the timeout, loses time and money on miner fees, she'll
> >>    never coinswap with Bob's fidelity bond again.
> >> 5. Charlie: aborts. Alice/Bob: lose nothing, find another Charlie to
> >>    coinswap with.
> >> 6. same as 4.
> >> 7. similar to 4 but Alice MIGHT not blacklist Bob's fidelity bond,
> >>    because Bob will also have to broadcast his contract tx and will also
> >>    lose time and money.
> >> 8. Charlie: aborts. Bob: broadcast his contract transaction and wait for
> >>    the timeout to get his money back, also broadcast Alice's contract
> >>    transaction in retaliation. Alice: waits for the timeout on her htlc
> >>    tx that Bob broadcasted, will never do a coinswap with Charlie's
> >>    fidelity bond again.
> >> 9. Alice: aborts. Charlie: do nothing, no money or time lost. Bob:
> >>    broadcast bob contract tx and wait for timeout to get money back,
> >>    comforted by the knowledge that when Alice comes back online she'll
> >>    have to do the same thing and waste the same amount of time and
> >>    money.
> >> A-B. same as 8.
> >> C-E. Alice: aborts. Bob/Charlie: all broadcast their contract txes and
> >>      wait for the timeout to get their money back, or if Charlie knows
> >>      the preimage he uses it to get the money immediately, which Bob can
> >>      read from the blockchain and also use.
> >> F. Bob: aborts. Alice: broadcast Charlie htlc tx and use preimage to get
> >>    money immediately, Alice blacklists Bob's fidelity bond. Charlie:
> >>    broadcast Bob htlc and use preimage to get money immediately.
> >> G. Charlie: aborts. Alice: broadcast Charlie htlc and use preimage to
> >>    get money immediately, Alice blacklists Charlie's fidelity bond. Bob:
> >>    does nothing, already has his privkey.
> >>
> >> ==== Retaliation as DOS-resistance ====
> >>
> >> In some situations (e.g. step 8.) if one maker in the coinswap route is
> >> the victim of a DOS they will retaliate by DOSing the previous maker in
> >> the route. This may seem unnecessary and unfair (after all why waste
> >> even more time and block space) but is actually the best way to resist
> >> DOS because it produces a concrete cost every time a DOS happens.
> >>
> >>
> >> == Analysis of deviations ==
> >>
> >> This section discusses what happens if one party deviates from the
> >> protocol by doing something else, for example broadcasting a htlc
> >> contract tx when they shouldnt have.
> >>
> >> The party name refers to what that party does, followed by other party's
> >> reactions to it.
> >> e.g. Party1: does a thing, Party2/Party3: does a thing in reaction
> >>
> >> If multiple deviations are possible in a step then they are numbered
> >> e.g. A1 A2 A2 etc
> >>
> >>
> >> 0-2. Alice/Bob/Charlie: nothing else is possible except following the
> >>      protocol or aborting
> >> 3. Alice: broadcasts one or more of the A htlc txes. Bob/Charlie/Dennis:
> >>    do nothing, they havent lost any time or money.
> >> 4-6. Bob/Charlie: nothing else is possible except following the protocol
> >>      or aborting.
> >> 7. Bob: broadcasts one or more of the B htlc txes, Alice: broadcasts all
> >>    her own A htlc txes and waits for the timeout to get her money back.
> >>    Charlie: do nothing
> >> 8. Charlie: nothing else is possible except following the protocol or
> >>    aborting.
> >> 9. Alice: broadcasts one or more of the A htlc txes. Bob: broadcasts all
> >>    his own A htlc txes and waits for the timeout.
> >> A. same as 8.
> >> B. Charlie: broadcasts one or more of the C htlc txes, Alice/Bob:
> >>    broadcasts all their own htlc txes and waits for the timeout to get
> >>    their money back.
> >> C-E1. Alice: broadcasts all of C htlc txes and uses her knowledge of the
> >>       preimage hash to take the money immediately. Charlie: broadcasts
> >>       all of B htlc txes and reading the hash value from the blockchain,
> >>       uses it to take the money from B htlc immediately. Bob: broadcasts
> >>       all of A htlc txes, and reading hash from the blockchain, uses it
> >>       to take the money from A htlc immediately.
> >> C-E2. Alice: broadcast her own A htlc txes, and after a timeout take the
> >>       money. Bob: broadcast his own B htlc txes and after the timeout
> >>       take their money. Charlie: broadcast his own C htlc txes and after
> >>       the timeout take their money.
> >> F1. Bob: broadcast one or more of A htcl txes and use the hash preimage
> >>     to get the money immediately. He already knows both privkeys of the
> >>     multisig so this is pointless and just damages privacy and wastes
> >>     miner fees. Alice: blacklist Bob's fidelity bond.
> >> F2. Bob: broadcast one or more of the C htlc txes. Charlie: use preimage
> >>     to get his money immediately. Bob's actions were pointless. Alice:
> >>     cant tell whether Bob or Charlie actually broadcasted, so blacklist
> >>     both fidelity bonds.
> >> G1. Charlie: broadcast one or more of B htcl txes and use the hash
> >>     preimage to get the money immediately. He already knows both
> >>     privkeys of the multisig so this is pointless and just damages
> >>     privacy and wastes miner fees. Alice: cant tell whether Bob or
> >>     Charlie actually broadcasted, so blacklist both fidelity bonds.
> >> G2. Charlie: broadcast one or more of the A htlc txes. Alice: broadcast
> >>     the remaining A htlc txes and use preimage to get her money
> >>     immediately. Charlies's actions were pointless. Alice: blacklist
> >>     Charlie's fidelity bond.
> >>
> >> The multisig outputs of the funding transactions can stay unspent
> >> indefinitely. However the parties must always be watching the network
> >> and ready to respond with their own sweep using a preimage. This is
> >> because the other party still possesses a fully-signed contract tx. The
> >> parties respond in the same way as in steps C-E1, F2 and G2. Alice's
> >> reaction of blacklisting both fidelity bonds might not be the right way,
> >> because one maker could use it to get another one blacklisted (as well
> >> as themselves).
> >>
> >>
> >> == Conclusion ==
> >>
> >> This document describes the first version of the protocol which
> >> implements multi-transaction Coinswap, routed Coinswap, fidelity bonds,
> >> a liquidity market and private key handover. I describe the protocol and
> >> also analyze aborts of the protocols and deviations from the protocol.
> >>
> >> _______________________________________________
> >> bitcoin-dev mailing list
> >> bitcoin-dev@lists.linuxfoundation.org
> >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> >>
> >
>

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

^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap
  2020-08-25  3:16   ` ZmnSCPxj
  2020-09-03  9:00     ` Chris Belcher
@ 2020-09-05  1:10     ` Antoine Riard
  2020-09-05  2:29       ` ZmnSCPxj
  1 sibling, 1 reply; 24+ messages in thread
From: Antoine Riard @ 2020-09-05  1:10 UTC (permalink / raw)
  To: ZmnSCPxj; +Cc: Bitcoin Protocol Discussion

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

Hi Zeeman,

I think one of the general problems for any participant in an
interdependent chain of contracts like Lightning or CoinSwap is to avoid a
disequilibrium in its local HTLC ledger. Concretely sending forward more
than you receive backward. W.r.t, timelocks delta aim to enforce order of
events, namely that a forward contract must be terminated before any
backward contract to avoid a discrepancy in settlement. Order of events can
be enforced by a) absolute timelocks and thus linearized on the same scale
by blockchain ticks or b) by a counterparty to two relative-time locked
contracts which observe the broadcast of the backward transaction and thus
manually trigger the kickoff of forward timelock by broadcasting the
corresponding transaction.

With this rough model in mind, pinning an absolute or relative timelocked
transaction produce the same effect, i.e breaking contracts settlement
order.

> This can be arranged by having one side offer partial signatures for the
transaction of the other, and once completing the signature, not sharing it
with the other until we are ready to actually broadcast the transaction of
our own volition.
> There is no transaction that both participants hold in completely-signed
form

I don't think that's different from the current model where you have either
a valid HTLC-timeout or HTLC-Sucess tx to solve a HTLC output but never
full witness material to build both ?

I see a theoretical issue with RBF-range, if you're likely to lose the
balance, you can broadcast your highest-RBF version thus incentivizing
miners to censor counterparty claim tx. Kind of a "nothing at stake" issue.
As of today, you have to take this fee out of your pocket if you want to
incentivize miners to act so, not promising a fee from an ongoing disputed
balance.

> Private key turnover is still useful even in an absolute-timelock world.

The way I understand the either-HTLC-or-private-key-turnover construction
in CoinSwap is for the HTLC to serve as a security backup in case the
cooperative key turnover fails. Lightning don't have this model as you
don't switch funding transaction ownership.

> To reduce this risk, A can instead first swap A->B->A, then when that
completes, A->C->A.
This limits its funding lockup to 1 week.

Okay I think I understand your point. So by intermediating the chain with
the taker you ensure that in case of previous hop failure, taker funds are
only timelocked for the delta of this faulting hop not the whole route. But
still not anchoring onchain the next route segment means that any moment
the next maker can exit from the proposed position ?

That's interesting, so a) you require all takers to lock their funds
onchain before initiating the whole routing and you will pay more in
service fees or b) you only lock them step by step but you increase risk of
next hop default and thus latency. Roughly.

It might be an interesting construction to explore on its own, minus the
downside of producing weird spend patterns due to next hop maker bidding
with another party.

Cheers,

Antoine

Le lun. 24 août 2020 à 23:16, ZmnSCPxj <ZmnSCPxj@protonmail.com> a écrit :

>
> Good morning Antoine,
>
>
> > Note, I think this is independent of picking up either relative or
> absolute timelocks as what matters is the block delta between two links.
>
> I believe it is quite dependent on relative locktimes.
> Relative locktimes *require* a contract transaction to kick off the
> relative locktime period.
> On the other hand, with Scriptless Script (which we know how to do with
> 2p-ECDSA only, i.e. doable pre-Taproot), absolute locktimes do not need a
> contract transaction.
>
> With absolute locktimes + Scriptless SCript, in a single onchain PTLC, one
> participant holds a completely-signed timelock transaction while the other
> participant holds a completely-signed pointlock transaction.
> This can be arranged by having one side offer partial signatures for the
> transaction of the other, and once completing the signature, not sharing it
> with the other until we are ready to actually broadcast the transaction of
> our own volition.
> There is no transaction that both participants hold in completely-signed
> form.
>
> This should remove most of the shenanigans possible, and makes the 30xRBF
> safe for any range of fees.
> I think.
>
> Since for each PTLC a participant holds only its "own" transaction, it is
> possible for a participant to define its range of fees for the RBF versions
> of the transaction it owns, without negotiation with the other participant.
> Since the fee involved is deducted from its own transaction, each
> participant can define this range of RBFed fees and impose it on the
> partial signatures it gets from the other participant.
>
> --
>
> Private key turnover is still useful even in an absolute-timelock world.
>
> If we need to bump up the block delta between links, it might be
> impractical to have the total delta of a multi-hop swap be too long at the
> taker.
>
> As a concrete example, suppose A is a taker who wants to route over makers
> B and C.
> However, B and C require a CLTV delta of 1 week.
>
> If A wants to route "directly" A->B->C->A, then if something bad happens,
> it could be looking at having its funds locked for two weeks.
>
> To reduce this risk, A can instead first swap A->B->A, then when that
> completes, A->C->A.
> This limits its funding lockup to 1 week.
>
> Private key turnover is useful since as soon as the A->B->A swap
> completes, it can directly fund the A->C->A swap from the B-side funding
> transaction of the A->B->A swap.
>
>          |   A->B->A         |    A->C->A           |
>          :                   :                      :
>       A -:->funding A&B--> B :                      :
>          :                   :                      :
>       B -:->funding A&B -----:--> funding A&C --> C :
>          :                   :                      :
>          :                   :C-> funding A&C ------:-> to-cold  A -->
>          :                   :                      :
>
> This increases the number of transactions by 1 per swap beyond the first,
> compared to a direct routing A->B->C->A, but this may be worth it for A if
> the timelocks involved are too big for A.
>
> With 2p-ECDSA, a funding A&C looks exactly the same as a to-cold A, so B
> is unable to reliably determine if it is the last hop in the route.
>
> Without private key turnover, A would have:
>
>                       **NO** private key turnover!
>
>          |   A->B->A         |    A->C->A                      |
>          :                   :                                 :
>       A -:->funding A&B--> B :                                 :
>          :                   :                                 :
>       B -:->funding A&B -----:--> claim A -> funding A&C --> C :
>          :                   :                                 :
>          :                   :           C-> funding A&C ------:->
> to-cold  A -->
>          :                   :                                 :
>
> So if timelock-deltas are possibly-high (to reduce the probability of the
> MAD-HTLC argument, and other attacks, succeeding), takers might prefer to
> route by completing one swap first before starting the next one, and
> private key turnover is useful by reducing blockspace required by each hop.
>
> For reference, this is how it looks like with a single A->B->C->A swap
> with private key turnover:
>
>          |   A->B->C->A      |
>          :                   :
>       A -:->funding A&B--> B :
>          :                   :
>       B -:->funding B&C -> C :
>          :                   :
>       C -:->funding A&C -----:-> to-cold A -->
>          :                   :
>
> This is still smaller than in the A->B->A, A->C->A with private key
> turnover, by one funding tx per hop.
> However, A risks a much higher timelock (twice the timelock).
> Thus, A might prefer a lower timelock in exchange for paying for an
> additional transaction.
>
> Regards,
> ZmnSCPxj
>

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

^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap
  2020-09-05  1:10     ` Antoine Riard
@ 2020-09-05  2:29       ` ZmnSCPxj
  0 siblings, 0 replies; 24+ messages in thread
From: ZmnSCPxj @ 2020-09-05  2:29 UTC (permalink / raw)
  To: Antoine Riard; +Cc: Bitcoin Protocol Discussion

Good morning Antoine,


> > This can be arranged by having one side offer partial signatures for the transaction of the other, and once completing the signature, not sharing it with the other until we are ready to actually broadcast the transaction of our own volition.
> > There is no transaction that both participants hold in completely-signed form
>
> I don't think that's different from the current model where you have either a valid HTLC-timeout or HTLC-Sucess tx to solve a HTLC output but never full witness material to build both ?

It is different in that the current (actually, now *previous*) model looks like this:


    funding out ->  contract tx -->  HTLC-timeout
                                         OR
                                     HTLC-success


Whereas what I am describing looks like this:

    funding out ->  HTLC-timeout
                        OR
                    HTLC-success

The attack being described has to do with the fact that, after private key turnover (i.e. after hash-lock resolution), the contract tx can be used to at least annoy the supposed new owner of the funding out, since the contract tx deducts fees from its input to pay for itself.
And at the end of the swap (after private key turnover) the one who funded the funding outpoint (and swapped its control for this outpoint already, for a different outpoint) can at least try to broadcast the contract tx for a *chance* that the HTLC-timeout becomes valid and it can steal the coin even after taking the swapped coin on the other side of the swap.


Chris recently described a different technique, which has different contract txes, with the contract tx held by the offerrer of the HTLC (who can otherwise later annoy the acceptor of the HTLC once the HTLC has been hash-resolved) costing the offerrer of the HTLC some coins if it is published after swap completion.


> > To reduce this risk, A can instead first swap A->B->A, then when that completes, A->C->A.
> This limits its funding lockup to 1 week.
>
> Okay I think I understand your point. So by intermediating the chain with the taker you ensure that in case of previous hop failure, taker funds are only timelocked for the delta of this faulting hop not the whole route. But still not anchoring onchain the next route segment means that any moment the next maker can exit from the proposed position ?
>
> That's interesting, so a) you require all takers to lock their funds onchain before initiating the whole routing and you will pay more in service fees or b) you only lock them step by step but you increase risk of next hop default and thus latency. Roughly.
>  
> It might be an interesting construction to explore on its own, minus the downside of producing weird spend patterns due to next hop maker bidding with another party.
>

Correct, a taker can pay higher fees for lots of smaller swaps that reduce its lockup risk, or pay less (with similar privacy bought) but with greater total lockup risk.

Regards,
ZmnSCPxj


^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap
  2020-09-03 23:39           ` ZmnSCPxj
@ 2020-09-05  2:45             ` ZmnSCPxj
  0 siblings, 0 replies; 24+ messages in thread
From: ZmnSCPxj @ 2020-09-05  2:45 UTC (permalink / raw)
  To: ZmnSCPxj, Bitcoin Protocol Discussion

Good morning Chris, and probably also Lightningers,

> However, it might be possible to prevent the maker from learning the collateral input at all.
>
> If my understanding of BIP-143 is correct, inputs are hashed separately (`hashPrevouts`) from outputs (`hashOutputs`).
> Bob can provide the `hashPrevouts` as an opaque hash, while providing a decommitment of `hashOutputs` to show that the outputs of the collateralized contract transaction are correct, which is all that Charlie really needs to know.
>
> Bob is incentivized to provide the correct `hashPrevouts`, because if it provides an incorrect `hashPrevouts` it cannot get a signature for a transaction it can use in case of a protocol abort, thus potentially losing its money in case of a protocol abort.
> Conversely, Charlie does not care where Bob gets the funds that goes into its contract output come from, it only cares that the Bob collateralized contract output is I+K.
> It loses nothing to sign that transaction, and it would prefer that transaction since its own contract output is only I.
>
> This solution is mildly "unclean" as it depends on the details of the sighash algorithm, though, and is not proposed seriously.
> Hopefully nobody will change the sighash algorithm anytime soon.........
>
> In addition, it complicates reusing Lightning watchtowers.
> Lightning watchtowers currently trigger on txid (i.e. it would have triggered on the txid of the B collateralized contract tx), but watching this needs to trigger on the spend of a txo, since it is not possible to prove that a specific `hashPrevouts` etc. goes with a specific txid without revealing the whole tx (which is precisely what we are trying to avoid), as both are hashes.
> Watchtowers may need to be entrusted with privkeys, or need to wait for `SIGHASH_ANYPREVOUT` so that the exact txid of the B collateralized contract tx does not need to be fixed at signing time, thus this solution is undesirable as well.

On the other hand, when considering Decker-Russell-Osuntokun, the `(halftxid, encrypted_blob)` approach to watchtowers simply does not work.
Watchtowers are simpler in Decker-Russell-Osuntoku if and only if the watchtower knows the funding outpoint, therefore knows which channel it is watching *before* an attack on the channel occurs, and is less private.

I have argued before that we should instead use `(sighash[0:15], encrypted_blob)` rather than `(txid[0:15], encrypted_blob)`.
This makes Decker-Russell-Osuntokun blobs indistinguishable from Poon-Dryja blobs, and the watchtower is not even made aware what the commitment type of the channel is until an actual attack occurs.

If watchtowers use `(sighash[0:15], encrypted_blob)` instead, the proposal to hide the collateral input behind `hashPrevouts` would be workable, as Charlie knows the entire sighash of the B collateralized contract transaction even if it does not know the txid.
This also does not reveal the funding outpoint, or whether it is watching a Poon-Dryja channel, a Decker-Russell-Osuntokun channel, or a CoinSwap.

--

Even if we propose that CoinSwap makers should run their own watchtowers rather than hire a public watchtower, it's safer for a CoinSwap maker to have watchtowers that are unaware of exactly *what* they are watching.
If the watchtowers are aware of the funding outputs they are watching, then every additional watchtower a maker creates increases the attack surface on the privacy of the maker, as the funding outputs becoming known allows the maker hodlings to be derived.

If watchtowers only get a partial sighash, then the information that they contain are not sufficient by themselves to determine what coins are owned by the maker, thus every additional watchtower is no longer a potential attack vector on the privacy of the maker.

So this is off-topic, but anyway, we should probably move to using `sighash[0:15]` instead of `txid[0:15]` for watchtowers.


Regards,
ZmnSCPxj


^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap
  2020-09-05  1:07     ` Antoine Riard
@ 2020-09-06  3:06       ` seid Mohammed
  0 siblings, 0 replies; 24+ messages in thread
From: seid Mohammed @ 2020-09-06  3:06 UTC (permalink / raw)
  To: Antoine Riard, Bitcoin Protocol Discussion

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

subscribe pls https://www.youtube.com/channel/UCcRPSO-n2HgolBFKzW3re4Q

On Saturday, September 5, 2020, Antoine Riard via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hi Chris,
>
> I forgot to underscore that contract transaction output must be grieved by
> at least a CSV of 1. Otherwise, a malicious counterparty can occupy with
> garbage both the timelock-or-preimage output and its own anchor output thus
> blocking you to use the bumping capability of your own anchor ouput.
>
> A part of this, I think it works.
>
> > Another possible fix for both vulnerabilities is to separate the
> > timelock and hashlock cases into two separate transactions as described
> > by ZmnSCPxj in a recent email to this list. This comes at the cost of
> > breaking private key handover allowing coins to remain unspent
> indefinitely.
>
> This works too assuming these second-stage transactions aren't malleable
> at all (e.g SIGASH_SINGLE). Other ways you can increase their
> feerate/absolute fee and you're back to the initial situation.
>
> Beyond note also that anchors-on-second-stage are more risky here, as
> otherwise your counterparty can again attach a low-feerate child. In case
> of concurrent broadcast (assuming you haven't achieved to claim the output
> before timelock expiration due to network outage/mempool-congestion) you
> might not see your counterparty version. I.e, your local mempool has the
> timelock tx and the rest of the network the hashlock and your CPFP bump
> won't propagate as being an orphan.
>
> So you're left with a RBF-range, which is mostly okay minus a theoretical
> concern : a party guessing the odds to lose the balance are high can
> broadcast/send out-of-band the highest-fee bound to miners thus
> incentivizing them to censor a honest, low-fee  preimage tx. A
> "nothing-at-stake-for-genuinely-evil-counterparty" issue.
>
> > Another possible fix for the second attack, is to encumber the output
> > with a `1 OP_CSV` which stops that output being spent while unconfirmed.
> > This seems to be the simplest way if your aim is to only fix the second
> > attack.
>
> Yes you don't package fee malleability so an honest party can always
> unilaterally bump the feerate and override concurrent bids.
>
>
> That said, I would lean towards anchors and thus unileratel fee bumping.
> Feerate interactivity among a multi-party protocol should be seen as an
> oracle to leak the full-node of a participant. By sending a range of
> conflicting transactions with different feerates to a set of network
> mempools I could theoretically observe variations in the protocol feerate
> announced.
>
> I would recommend you to have a look on this paper, if it's not done yet :
> https://arxiv.org/pdf/2007.00764.pdf, the first one analyzing privacy
> holistically across Bitcoin layers.
>
> Cheers,
>
> Antoine
>
> Le sam. 29 août 2020 à 18:03, Chris Belcher <belcher@riseup.net> a écrit :
>
>> Hello Antoine,
>>
>> Thanks for the very useful insights.
>>
>> It seems having just one contract transaction which includes anchor
>> outputs in the style already used by Lightning is one way to fix both
>> these vulnerabilities.
>>
>> For the first attack, the other side cannot burn the entire balance
>> because they only have access to the small amount of satoshi of the
>> anchor output, and to add miner fees they must add their own inputs. So
>> they'd burn their own coins to miner fees, not the coins in the contract.
>>
>> For the second attack, the other side cannot do transaction pinning
>> because there is only one contract transaction, and all the protections
>> already developed for use with Lightning apply here as well, such as
>> CPFP carve out.
>>
>>
>> Another possible fix for both vulnerabilities is to separate the
>> timelock and hashlock cases into two separate transactions as described
>> by ZmnSCPxj in a recent email to this list. This comes at the cost of
>> breaking private key handover allowing coins to remain unspent
>> indefinitely.
>>
>> Another possible fix for the second attack, is to encumber the output
>> with a `1 OP_CSV` which stops that output being spent while unconfirmed.
>> This seems to be the simplest way if your aim is to only fix the second
>> attack.
>>
>>
>> These are all the possible fixes I can think of.
>>
>> Regards
>> Chris
>>
>> On 24/08/2020 20:30, Antoine Riard wrote:
>> > Hello Chris,
>> >
>> > I think you might have vulnerability issues with the current design.
>> >
>> > With regards to the fee model for contract transactions, AFAICT timely
>> > confirmation is a fund safety matter for an intermediate hop. Between
>> the
>> > offchain preimage reveal phase and the offchain private key handover
>> phase,
>> > the next hop can broadcast your outgoing contract transactions, thus
>> > forcing you to claim quickly backward as you can't assume previous hop
>> will
>> > honestly cooperate to achieve the private key handover. This means that
>> > your range of pre-signed RBF-transactions must theoretically have for
>> fee
>> > upper bound the maximum of the contested balance, as game-theory side,
>> it's
>> > rational to you to burn your balance instead of letting your
>> counterparty
>> > claim it after timelock expiration, in face of mempool congestion. Where
>> > the issue dwells is that this fee is pre-committed and not cancelled
>> when
>> > the balance change of ownership by the outgoing hop learning the
>> preimage
>> > of the haslock output. Thus the previous hop is free to broadcast the
>> > highest-fee RBF-transactions and burn your balance, as for him, his
>> balance
>> > is now encoded in the output of the contract transactions on the
>> previous
>> > link, for which he knows the preimage.
>> >
>> > Note, I think this is independent of picking up either relative or
>> absolute
>> > timelocks as what matters is the block delta between two links. Of
>> course
>> > you can increase this delta to be week-lengthy and thus decrease the
>> need
>> > for a compelling fee but a) you may force quickly close with contract
>> > transactions if the private key handover doesn't happen soon, you don't
>> > want to be caught by surprise by congestion so you would close far
>> behind
>> > delta period expiration like half of it, and b) you increase the
>> time-value
>> > of makers funds in case of faulty hop, thus logically increasing the
>> maker
>> > fee and making the cost of the system higher in average. I guess a
>> better
>> > solution would be to use dual-anchor outputs has spec'ed out by
>> Lightning,
>> > it lets the party who has a balance at stake unilaterally increase
>> feerate
>> > with a CPFP. The CPFP is obviously a higher blockchain cost but a) it's
>> a
>> > safety mechanism for a worst-case scenario, 99% of the time they won't
>> be
>> > committed, b) you might use this CPFP to aggregate change outputs or
>> other
>> > opportunistically side-usage.
>> >
>> > With regards to the preimage release phase, I think you might have a
>> > pinning scenario. The victim would be an intermediate hop, targeted by a
>> > malicious taker. The preimage isn't revealed offchain to this victim
>> hop. A
>> > low-feerate version of the outgoing contract transaction is broadcast
>> and
>> > not going to confirm, assuming a bit of congestion. As preimage is
>> known,
>> > the malicious taker can directly attach a high-fee, low-feerate child
>> > transaction and thus prevent any replacement of the pinned parent by a
>> > honest broadcast of a high-fee RBF-transaction under BIP 125 rules. At
>> the
>> > same time, the malicious taker broadcasts the contract tx on the
>> previous
>> > link and gets it confirmed. At relative timelock expiration, malicious
>> > taker claims back the funds. When the pinned transaction spending the
>> > outgoing link gets evicted (either by replacing child by a higher
>> feerate
>> > or waiting for mempool expiration after 2 weeks), taker gets it
>> confirmed
>> > this time and claims output through hashlock. Given the relative
>> timelock
>> > blocking the victim, there is not even a race.
>> >
>> > I guess restraining the contract transaction to one and only one version
>> > would overcome this attack. A honest intermediate hop, as soon as
>> seeing a
>> > relative timelock triggered backward would immediately broadcast the
>> > outgoing link contract tx or if it's already in network mempools
>> broadcast
>> > a higher-feerate child. As you don't have valid multiple contract
>> > transactions, an attacker can't obstruct you to propagate the correct
>> > child, as you are not blind about the parent txid.
>> >
>> > Lastly, one downside of using relative timelocks, in case of one
>> downstream
>> > link failure, it forces every other upstream hops to go onchain to
>> protect
>> > against this kind of pinning scenario. And this would be a privacy
>> > breakdown, as a maker would be able to provoke one, thus constraining
>> every
>> > upstream hops to go onchain with the same hash and revealing the
>> CoinSwap
>> > route.
>> >
>> > Let me know if I reviewed the correct transactions circuit model or
>> > misunderstood associated semantic. I might be completely wrong, coming
>> from
>> > a LN perspective.
>> >
>> > Cheers,
>> > Antoine
>> >
>> > Le mar. 11 août 2020 à 13:06, Chris Belcher via bitcoin-dev <
>> > bitcoin-dev@lists.linuxfoundation.org> a écrit :
>> >
>> >> I'm currently working on implementing CoinSwap (see my other email
>> >> "Design for a CoinSwap implementation for massively improving Bitcoin
>> >> privacy and fungibility").
>> >>
>> >> CoinSwaps are special because they look just like regular bitcoin
>> >> transactions, so they improve the privacy even for people who do not
>> use
>> >> them. Once CoinSwap is deployed, anyone attempting surveillance of
>> >> bitcoin transactions will be forced to ask themselves the question: how
>> >> do we know this transaction wasn't a CoinSwap?
>> >>
>> >> This email contains a detailed design of the first protocol version. It
>> >> makes use of the building blocks of multi-transaction CoinSwaps, routed
>> >> CoinSwaps, liquidity market, private key handover, and fidelity bonds.
>> >> It does not include PayJoin-with-CoinSwap, but that's in the plan to be
>> >> added later.
>> >>
>> >> == Routed CoinSwap ==
>> >>
>> >> Diagram of CoinSwaps in the route:
>> >>
>> >>     Alice ====> Bob ====> Charlie ====> Alice
>> >>
>> >> Where (====>) means one CoinSwap. Alice gives coins to Bob, who gives
>> >> coins to Charlie, who gives coins to Alice. Alice is the market taker
>> >> and she starts with the hash preimage. She chooses the CoinSwap amount
>> >> and chooses who the makers will be.
>> >>
>> >> This design has one market taker and two market makers in its route,
>> but
>> >> it can easily be extended to any number of makers.
>> >>
>> >> == Multiple transactions ==
>> >>
>> >> Each single CoinSwap is made up of multiple transactions to avoid
>> amount
>> >> correlation
>> >>
>> >>           (a0 BTC) --->     (b0 BTC) --->         (c0 BTC) --->
>> >>     Alice (a1 BTC) ---> Bob (b1 BTC) ---> Charlie (c1 BTC) ---> Alice
>> >>           (a2 BTC) --->     (b2 BTC) --->         (c2 BTC) --->
>> >>
>> >> The arrow (--->) represent funding transactions. The money gets paid to
>> >> a 2-of-2 multisig but after the CoinSwap protocol and private key
>> >> handover is done they will be controlled by the next party in the
>> route.
>> >>
>> >> This example has 6 regular-sized transactions which use approximately
>> >> the same amount of block space as a single JoinMarket coinjoin with 6
>> >> parties (1 taker, 5 makers). Yet the privacy provided by this one
>> >> CoinSwap would be far far greater. It would not have to be repeated in
>> >> the way that Equal-Output CoinJoins must be.
>> >>
>> >> == Direct connections to Alice ===
>> >>
>> >> Only Alice, the taker, knows the entire route, Bob and Charlie just
>> know
>> >> their previous and next transactions. Bob and Charlie do not have
>> direct
>> >> connections with each other, only with Alice.
>> >>
>> >> Diagram of Tor connections:
>> >>
>> >>     Bob      Charlie
>> >>      |       /
>> >>      |      /
>> >>      |     /
>> >>       Alice
>> >>
>> >> When Bob and Charlie communicate, they are actually sending and
>> >> receiving messages via Alice who relays them to Charlie or Bob. This
>> >> helps hide whether the previous or next counterparty in a CoinSwap
>> route
>> >> is a maker or taker.
>> >>
>> >> This doesn't have security issues even in the final steps where private
>> >> keys are handed over, because those private keys are always for 2-of-2
>> >> multisig and so on their own are never enough to steal money.
>> >>
>> >>
>> >> === Miner fees ===
>> >>
>> >> Makers have no incentive to pay any miner fees. They only do
>> >> transactions which earn them an income and are willing to wait a very
>> >> long time for that to happen. By contrast takers want to create
>> >> transactions far more urgently. In JoinMarket we coded a protocol where
>> >> the maker could contribute to miner fees, but the market price offered
>> >> of that trended towards zero. So the reality is that takers will pay
>> all
>> >> the miner fees. Also because makers don't know the taker's time
>> >> preference they don't know how much they should pay in miner fees.
>> >>
>> >> The taker will have to set limits on how large the maker's transactions
>> >> are, otherwise makers could abuse this by having the taker consolidate
>> >> maker's UTXOs for free.
>> >>
>> >> == Funding transaction definitions ==
>> >>
>> >> Funding transactions are those which pay into the 2-of-2 multisig
>> >> addresses.
>> >>
>> >> Definitions:
>> >> I = initial coinswap amount sent by Alice = a0 + a1 + a2
>> >> (WA, WB, WC) = Total value of UTXOs being spent by Alice, Bob, Charlie
>> >>                respectively. Could be called "wallet Alice", "wallet
>> >>                Bob", etc
>> >> (B, C) = Coinswap fees paid by Alice and earned by Bob and Charlie.
>> >> (M1, M2, M3) = Miner fees of the first, second, third, etc sets of
>> >>                funding transactions. Alice will choose what these are
>> >>                since she's paying.
>> >> multisig(A+B) = A 2of2 multisig output with private keys held by A and
>> B
>> >>
>> >> The value in square parentheses refers to the bitcoin amount.
>> >>
>> >> Alice funding txes
>> >>   [WA btc] ---> multisig (Alice+Bob) [I btc]
>> >>                 change [WA-M1-I btc]
>> >> Bob funding txes
>> >>   [WB btc] ---> multisig (Bob+Charlie) [I-M2-B btc]
>> >>                 change [WB-I+B btc]
>> >> Charlie funding txes
>> >>   [WC btc] ---> multisig (Charlie+Alice) [(I-M2-B)-M3-C btc]
>> >>                 change [WC-(I-M2-B)+C btc]
>> >>
>> >> Here we've drawn these transactions as single transactions, but they
>> are
>> >> actually multiple transactions where the outputs add up some value
>> (e.g.
>> >> add up to I in Alice's transactions.)
>> >>
>> >> === Table of balances before and after a successful CoinSwap ===
>> >>
>> >> If a CoinSwap is successful then all the multisig outputs in the
>> funding
>> >> transactions will become controlled unilaterally by one party. We can
>> >> calculate how the balances of each party change.
>> >>
>> >> Party   | Before | After
>> >> --------|--------|-------------------------------------------
>> >> Alice   | WA     | WA-M1-I + (I-M2-B)-M3-C  = WA-M1-M2-M3-B-C
>> >> Bob     | WB     | WB-I+B + I               = WB+B
>> >> Charlie | WC     | WC-(I-M2-B)+C + I-M2-B   = WC+C
>> >>
>> >> After a successful coinswap, we see Alice's balance goes down by the
>> >> miner fees and the coinswap fees. Bob's and Charlie's balance goes up
>> by
>> >> their coinswap fees.
>> >>
>> >> == Contract transaction definitions ==
>> >>
>> >> Contract transactions are those which may spend from the 2-of-2
>> multisig
>> >> outputs, they transfer the coins into a contract where the coins can be
>> >> spent either by waiting for a timeout or providing a hash preimage
>> >> value. Ideally contract transactions will never be broadcast but their
>> >> existence keeps all parties honest.
>> >>
>> >> M~ is miner fees, which we treat as a random variable, and ultimately
>> >> set by whichever pre-signed RBF tx get mined. When we talk about _the_
>> >> contract tx, we actually mean perhaps 20-30 transactions which only
>> >> differ by the miner fee and have RBF enabled, so they can be
>> broadcasted
>> >> in sequence to get the contract transaction mined regardless of the
>> >> demand for block space.
>> >>
>> >> (Alice+timelock_A OR Bob+hash) = Is an output which can be spent
>> >>                                  either with Alice's private key
>> >>                                  after waiting for a relative
>> >>                                  timelock_A, or by Bob's private key by
>> >>                                  revealing a hash preimage value
>> >>
>> >> Alice contract tx:
>> >>     multisig (Alice+Bob) ---> (Alice+timelock_A OR Bob+hash)
>> >>     [I btc]                   [I-M~ btc]
>> >> Bob contract tx:
>> >>     multisig (Bob+Charlie) ---> (Bob+timelock_B OR Charlie+hash)
>> >>     [I-M2-B btc]                [I-M2-B-M~ btc]
>> >> Charlie contract tx:
>> >>     multisig (Charlie+Alice)  ---> (Charlie+timelock_C OR Alice+hash)
>> >>     [(I-M2-B)-M3-C btc]            [(I-M2-B)-M3-C-M~ btc]
>> >>
>> >>
>> >> === Table of balances before/after CoinSwap using contracts
>> transactions
>> >> ===
>> >>
>> >> In this case the parties had to get their money back by broadcasting
>> and
>> >> mining the contract transactions and waiting for timeouts.
>> >>
>> >> Party   | Before | After
>> >> --------|--------|--------------------------------------------
>> >> Alice   | WA     | WA-M1-I + I-M~                   = WA-M1-M~
>> >> Bob     | WB     | WB-I+B + I-M2-B-M~               = WB-M2-M~
>> >> Charlie | WC     | WC-(I-M2-B)+C + (I-M2-B)-M3-C-M~ = WC-M3-M~
>> >>
>> >> In the timeout failure case, every party pays for their own miner fees.
>> >> And nobody earns or spends any coinswap fees. So even for a market
>> maker
>> >> its possible for their wallet balance to go down sometimes, although as
>> >> we shall see there are anti-DOS features which make this unlikely to
>> >> happen often.
>> >>
>> >> A possible attack by a malicious Alice is that she chooses M1 to be
>> very
>> >> low (e.g. 1 sat/vbyte) and sets M2 and M3 to be very high (e.g. 1000
>> >> sat/vb) and then intentionally aborts, forcing the makers to lose much
>> >> more money in miner fees than the attacker. The attack can be used to
>> >> waste away Bob's and Charlie's coins on miner fees at little cost to
>> the
>> >> malicious taker Alice. So to defend against this attack Bob and Charlie
>> >> must refuse to sign a contract transaction if the corresponding funding
>> >> transaction pays miner fees greater than Alice's funding transaction.
>> >>
>> >>
>> >> There can also be a failure case where each party gets their money
>> using
>> >> hash preimage values instead of timeouts. Note that each party has to
>> >> sweep the output before the timeout expires, so that will cost an
>> >> additional miner fee M~.
>> >>
>> >> Party   | Before | After
>> >> --------|--------|------------------------------------------
>> ------------
>> >> Alice   | WA     | WA-M1-I + (I-M2-B)-M3-C-M~ - M~ =
>> WA-M1-M2-M3-B-C-2M~
>> >> Bob     | WB     | WB-I+B + I-M~ - M~              = WB+B-2M~
>> >> Charlie | WC     | WC-(I-M2-B)+C + I-M2-B-M~ - M~  = WC+C-2M~
>> >>
>> >> In this situation the makers Bob and Charlie earn their CoinSwap fees,
>> >> but they pay an additional miner fee twice. Alice pays for all the
>> >> funding transaction miner fees, and the CoinSwap fees, and two
>> >> additional miner fees. And she had her privacy damaged because the
>> >> entire world saw on the blockchain the contract script.
>> >>
>> >> Using the timelock path is like a refund, everyone's coin just comes
>> >> back to them. Using the preimage is like the CoinSwap transaction
>> >> happened, with the coins being sent ahead one hop. Again note that if
>> >> the preimage is used then coinswap fees are paid.
>> >>
>> >> === Staggered timelocks ===
>> >>
>> >> The timelocks are staggered so that if Alice uses the preimage to take
>> >> coins then the right people will also learn the preimage and have
>> enough
>> >> time to be able to get their coins back too. Alice starts with
>> knowledge
>> >> of the hash preimage so she must have a longest timelock.
>> >>
>> >> == EC tweak to reduce one round trip ==
>> >>
>> >> When two parties are agreeing on a 2-of-2 multisig address, they need
>> to
>> >> agree on their public keys. We can avoid one round trip by using the EC
>> >> tweak trick.
>> >>
>> >> When Alice, the taker, downloads the entire offer book for the
>> liquidity
>> >> market, the offers will also contain a EC public key. Alice can tweak
>> >> this to generate a brand new public key for which the maker knows the
>> >> private key. This public key will be one of the keys in the 2-of-2
>> >> multisig. This feature removes one round trip from the protocol.
>> >>
>> >>     q = EC privkey generated by maker
>> >>     Q = q.G = EC pubkey published by maker
>> >>
>> >>     p = nonce generated by taker
>> >>     P = p.G = nonce point calculated by taker
>> >>
>> >>     R = Q + P = pubkey used in bitcoin transaction
>> >>       = (q + p).G
>> >>
>> >> Taker sends unsigned transaction which pays to multisig using pubkey Q,
>> >> and also sends nonce p. The maker can use nonce p to calculate (q + p)
>> >> which is the private key of pubkey R.
>> >>
>> >> Taker doesnt know the privkey because they are unable to find q because
>> >> of the ECDLP.
>> >>
>> >> Any eavesdropper can see the nonce p and easily calculate the point R
>> >> too but Tor communication is encrypted so this isnt a concern.
>> >>
>> >> None of the makers in the route know each other's Q values, so Alice
>> the
>> >> taker will generate a nonce p on their behalf and send it over. I
>> >> believe this cant be used for any kind of attack, because the signing
>> >> maker will always check that the nonce results in the public key
>> >> included in the transaction they're signing, and they'll never sign a
>> >> transaction not in their interests.
>> >>
>> >>
>> >> == Protocol ==
>> >>
>> >> This section is the most important part of this document.
>> >>
>> >> Definitions:
>> >> fund = all funding txes (remember in this multi-tx protocol there can
>> be
>> >>        multiple txes which together make up the funding)
>> >> A htlc = all htlc contract txes (fully signed) belonging to party A
>> >> A unsign htcl = all unsigned htlc contract txes belonging to party A
>> >>                 including the nonce point p used to calculate the
>> >>                 maker's pubkey.
>> >> p = nonce point p used in the tweak EC protocol for calculating the
>> >>     maker's pubkey
>> >> A htlc B/2 = Bob's signature for the 2of2 multisig of the Alice htlc
>> >>              contract tx
>> >> privA(A+B) = private key generated by Alice in the output
>> >>              multisig (Alice+Bob)
>> >>
>> >>
>> >>  | Alice           | Bob             | Charlie         |
>> >>  |=================|=================|=================|
>> >> 0. A unsign htlc ---->               |                 |
>> >> 1.               <---- A htlc B/2    |                 |
>> >> 2. ***** BROADCAST AND MINE ALICE FUNDING TXES ******  |
>> >> 3. A fund+htlc+p ---->               |                 |
>> >> 4.                 | B unsign htlc ---->               |
>> >> 5.                 |               <---- B htlc C/2    |
>> >> 6. ******* BROADCAST AND MINE BOB FUNDING TXES ******* |
>> >> 7.                 | B fund+htlc+p ---->               |
>> >> 8.               <---------------------- C unsign htlc |
>> >> 9.    C htlc A/2 ---------------------->               |
>> >> A. ***** BROADCAST AND MINE CHARLIE FUNDING TXES ***** |
>> >> B.               <---------------------- C fund+htlc+p |
>> >> C. hash preimage ---------------------->               |
>> >> D. hash preimage ---->               |                 |
>> >> E.    privA(A+B) ---->               |                 |
>> >> F.                 |    privB(B+C) ---->               |
>> >> G.               <---------------------- privC(C+A)    |
>> >>
>> >> == Protocol notes ==
>> >> 0-2 are the steps which setup Alice's funding tx and her contract tx
>> for
>> >>     possible refund
>> >> 4-5 same as 0-2 but for Bob
>> >> 8-9 same as 0-2 but for Charlie
>> >> 3,7 is proof to the next party that the previous party has already
>> >>     committed miner fees to getting a transaction mined, and therefore
>> >>     this isnt a DOS attack. The step also reveals the fully-signed
>> >>     contract transaction which the party can use to get their money
>> back
>> >>     with a preimage.
>> >> C-G is revealing the hash preimage to all, and handing over the private
>> >>     keys
>> >>
>> >>
>> >> == Analysis of aborts ==
>> >>
>> >> We will now discuss aborts, which happen when one party halts the
>> >> protocol and doesnt continue. Perhaps they had a power cut, their
>> >> internet broke, or they're a malicious attacker wanting to waste time
>> >> and money. The other party may try to reestablish a connection for some
>> >> time, but eventually must give up.
>> >>
>> >> Number refers to the step number where the abort happened
>> >> e.g. step 1 means that the party aborted instead of the action
>> happening
>> >> on protocol step 1.
>> >>
>> >> The party name refers to what that party does
>> >> e.g. Party1: aborts, Party2/Party3: does a thing in reaction
>> >>
>> >> 0. Alice: aborts. Bob/Charlie: do nothing, they havent lost any time or
>> >>    money
>> >> 1. Bob: aborts. Alice: lost no time or money, try with another Bob.
>> >>    Charlie: do nothing
>> >> 2-3. same as 0.
>> >> 4. Bob: aborts. Charlie: do nothing. Alice: broadcasts her contract tx
>> >>    and waits for the timeout, loses time and money on miner fees,
>> she'll
>> >>    never coinswap with Bob's fidelity bond again.
>> >> 5. Charlie: aborts. Alice/Bob: lose nothing, find another Charlie to
>> >>    coinswap with.
>> >> 6. same as 4.
>> >> 7. similar to 4 but Alice MIGHT not blacklist Bob's fidelity bond,
>> >>    because Bob will also have to broadcast his contract tx and will
>> also
>> >>    lose time and money.
>> >> 8. Charlie: aborts. Bob: broadcast his contract transaction and wait
>> for
>> >>    the timeout to get his money back, also broadcast Alice's contract
>> >>    transaction in retaliation. Alice: waits for the timeout on her htlc
>> >>    tx that Bob broadcasted, will never do a coinswap with Charlie's
>> >>    fidelity bond again.
>> >> 9. Alice: aborts. Charlie: do nothing, no money or time lost. Bob:
>> >>    broadcast bob contract tx and wait for timeout to get money back,
>> >>    comforted by the knowledge that when Alice comes back online she'll
>> >>    have to do the same thing and waste the same amount of time and
>> >>    money.
>> >> A-B. same as 8.
>> >> C-E. Alice: aborts. Bob/Charlie: all broadcast their contract txes and
>> >>      wait for the timeout to get their money back, or if Charlie knows
>> >>      the preimage he uses it to get the money immediately, which Bob
>> can
>> >>      read from the blockchain and also use.
>> >> F. Bob: aborts. Alice: broadcast Charlie htlc tx and use preimage to
>> get
>> >>    money immediately, Alice blacklists Bob's fidelity bond. Charlie:
>> >>    broadcast Bob htlc and use preimage to get money immediately.
>> >> G. Charlie: aborts. Alice: broadcast Charlie htlc and use preimage to
>> >>    get money immediately, Alice blacklists Charlie's fidelity bond.
>> Bob:
>> >>    does nothing, already has his privkey.
>> >>
>> >> ==== Retaliation as DOS-resistance ====
>> >>
>> >> In some situations (e.g. step 8.) if one maker in the coinswap route is
>> >> the victim of a DOS they will retaliate by DOSing the previous maker in
>> >> the route. This may seem unnecessary and unfair (after all why waste
>> >> even more time and block space) but is actually the best way to resist
>> >> DOS because it produces a concrete cost every time a DOS happens.
>> >>
>> >>
>> >> == Analysis of deviations ==
>> >>
>> >> This section discusses what happens if one party deviates from the
>> >> protocol by doing something else, for example broadcasting a htlc
>> >> contract tx when they shouldnt have.
>> >>
>> >> The party name refers to what that party does, followed by other
>> party's
>> >> reactions to it.
>> >> e.g. Party1: does a thing, Party2/Party3: does a thing in reaction
>> >>
>> >> If multiple deviations are possible in a step then they are numbered
>> >> e.g. A1 A2 A2 etc
>> >>
>> >>
>> >> 0-2. Alice/Bob/Charlie: nothing else is possible except following the
>> >>      protocol or aborting
>> >> 3. Alice: broadcasts one or more of the A htlc txes.
>> Bob/Charlie/Dennis:
>> >>    do nothing, they havent lost any time or money.
>> >> 4-6. Bob/Charlie: nothing else is possible except following the
>> protocol
>> >>      or aborting.
>> >> 7. Bob: broadcasts one or more of the B htlc txes, Alice: broadcasts
>> all
>> >>    her own A htlc txes and waits for the timeout to get her money back.
>> >>    Charlie: do nothing
>> >> 8. Charlie: nothing else is possible except following the protocol or
>> >>    aborting.
>> >> 9. Alice: broadcasts one or more of the A htlc txes. Bob: broadcasts
>> all
>> >>    his own A htlc txes and waits for the timeout.
>> >> A. same as 8.
>> >> B. Charlie: broadcasts one or more of the C htlc txes, Alice/Bob:
>> >>    broadcasts all their own htlc txes and waits for the timeout to get
>> >>    their money back.
>> >> C-E1. Alice: broadcasts all of C htlc txes and uses her knowledge of
>> the
>> >>       preimage hash to take the money immediately. Charlie: broadcasts
>> >>       all of B htlc txes and reading the hash value from the
>> blockchain,
>> >>       uses it to take the money from B htlc immediately. Bob:
>> broadcasts
>> >>       all of A htlc txes, and reading hash from the blockchain, uses it
>> >>       to take the money from A htlc immediately.
>> >> C-E2. Alice: broadcast her own A htlc txes, and after a timeout take
>> the
>> >>       money. Bob: broadcast his own B htlc txes and after the timeout
>> >>       take their money. Charlie: broadcast his own C htlc txes and
>> after
>> >>       the timeout take their money.
>> >> F1. Bob: broadcast one or more of A htcl txes and use the hash preimage
>> >>     to get the money immediately. He already knows both privkeys of the
>> >>     multisig so this is pointless and just damages privacy and wastes
>> >>     miner fees. Alice: blacklist Bob's fidelity bond.
>> >> F2. Bob: broadcast one or more of the C htlc txes. Charlie: use
>> preimage
>> >>     to get his money immediately. Bob's actions were pointless. Alice:
>> >>     cant tell whether Bob or Charlie actually broadcasted, so blacklist
>> >>     both fidelity bonds.
>> >> G1. Charlie: broadcast one or more of B htcl txes and use the hash
>> >>     preimage to get the money immediately. He already knows both
>> >>     privkeys of the multisig so this is pointless and just damages
>> >>     privacy and wastes miner fees. Alice: cant tell whether Bob or
>> >>     Charlie actually broadcasted, so blacklist both fidelity bonds.
>> >> G2. Charlie: broadcast one or more of the A htlc txes. Alice: broadcast
>> >>     the remaining A htlc txes and use preimage to get her money
>> >>     immediately. Charlies's actions were pointless. Alice: blacklist
>> >>     Charlie's fidelity bond.
>> >>
>> >> The multisig outputs of the funding transactions can stay unspent
>> >> indefinitely. However the parties must always be watching the network
>> >> and ready to respond with their own sweep using a preimage. This is
>> >> because the other party still possesses a fully-signed contract tx. The
>> >> parties respond in the same way as in steps C-E1, F2 and G2. Alice's
>> >> reaction of blacklisting both fidelity bonds might not be the right
>> way,
>> >> because one maker could use it to get another one blacklisted (as well
>> >> as themselves).
>> >>
>> >>
>> >> == Conclusion ==
>> >>
>> >> This document describes the first version of the protocol which
>> >> implements multi-transaction Coinswap, routed Coinswap, fidelity bonds,
>> >> a liquidity market and private key handover. I describe the protocol
>> and
>> >> also analyze aborts of the protocols and deviations from the protocol.
>> >>
>> >> _______________________________________________
>> >> bitcoin-dev mailing list
>> >> bitcoin-dev@lists.linuxfoundation.org
>> >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>> >>
>> >
>>
>

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

^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap appendium
  2020-08-11 12:05 [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap Chris Belcher
  2020-08-20 11:17 ` ZmnSCPxj
  2020-08-24 19:30 ` Antoine Riard
@ 2020-10-03 10:36 ` Chris Belcher
  2020-10-03 13:31   ` ZmnSCPxj
  2 siblings, 1 reply; 24+ messages in thread
From: Chris Belcher @ 2020-10-03 10:36 UTC (permalink / raw)
  To: bitcoin-dev

Hello list,

This email is an appendium or modification of the earlier CoinSwap
protocol published on this list. It is intended to fix the problems
found in review. (Original email quoted here too)


On 11/08/2020 13:05, Chris Belcher via bitcoin-dev wrote:
> I'm currently working on implementing CoinSwap (see my other email
> "Design for a CoinSwap implementation for massively improving Bitcoin
> privacy and fungibility").
> 
> CoinSwaps are special because they look just like regular bitcoin
> transactions, so they improve the privacy even for people who do not use
> them. Once CoinSwap is deployed, anyone attempting surveillance of
> bitcoin transactions will be forced to ask themselves the question: how
> do we know this transaction wasn't a CoinSwap?
> 
> This email contains a detailed design of the first protocol version. It
> makes use of the building blocks of multi-transaction CoinSwaps, routed
> CoinSwaps, liquidity market, private key handover, and fidelity bonds.
> It does not include PayJoin-with-CoinSwap, but that's in the plan to be
> added later.
> 
> == Routed CoinSwap ==
> 
> Diagram of CoinSwaps in the route:
> 
>     Alice ====> Bob ====> Charlie ====> Alice
> 
> Where (====>) means one CoinSwap. Alice gives coins to Bob, who gives
> coins to Charlie, who gives coins to Alice. Alice is the market taker
> and she starts with the hash preimage. She chooses the CoinSwap amount
> and chooses who the makers will be.
> 
> This design has one market taker and two market makers in its route, but
> it can easily be extended to any number of makers.
> 
> == Multiple transactions ==
> 
> Each single CoinSwap is made up of multiple transactions to avoid amount
> correlation
> 
>           (a0 BTC) --->     (b0 BTC) --->         (c0 BTC) --->
>     Alice (a1 BTC) ---> Bob (b1 BTC) ---> Charlie (c1 BTC) ---> Alice
>           (a2 BTC) --->     (b2 BTC) --->         (c2 BTC) --->
> 
> The arrow (--->) represent funding transactions. The money gets paid to
> a 2-of-2 multisig but after the CoinSwap protocol and private key
> handover is done they will be controlled by the next party in the route.
> 
> This example has 6 regular-sized transactions which use approximately
> the same amount of block space as a single JoinMarket coinjoin with 6
> parties (1 taker, 5 makers). Yet the privacy provided by this one
> CoinSwap would be far far greater. It would not have to be repeated in
> the way that Equal-Output CoinJoins must be.
> 
> == Direct connections to Alice ===
> 
> Only Alice, the taker, knows the entire route, Bob and Charlie just know
> their previous and next transactions. Bob and Charlie do not have direct
> connections with each other, only with Alice.
> 
> Diagram of Tor connections:
> 
>     Bob      Charlie
>      |       /
>      |      /
>      |     /
>       Alice
> 
> When Bob and Charlie communicate, they are actually sending and
> receiving messages via Alice who relays them to Charlie or Bob. This
> helps hide whether the previous or next counterparty in a CoinSwap route
> is a maker or taker.
> 
> This doesn't have security issues even in the final steps where private
> keys are handed over, because those private keys are always for 2-of-2
> multisig and so on their own are never enough to steal money.
> 
> 
> === Miner fees ===
> 
> Makers have no incentive to pay any miner fees. They only do
> transactions which earn them an income and are willing to wait a very
> long time for that to happen. By contrast takers want to create
> transactions far more urgently. In JoinMarket we coded a protocol where
> the maker could contribute to miner fees, but the market price offered
> of that trended towards zero. So the reality is that takers will pay all
> the miner fees. Also because makers don't know the taker's time
> preference they don't know how much they should pay in miner fees.
> 
> The taker will have to set limits on how large the maker's transactions
> are, otherwise makers could abuse this by having the taker consolidate
> maker's UTXOs for free.
> 
> == Funding transaction definitions ==
> 
> Funding transactions are those which pay into the 2-of-2 multisig addresses.
> 
> Definitions:
> I = initial coinswap amount sent by Alice = a0 + a1 + a2
> (WA, WB, WC) = Total value of UTXOs being spent by Alice, Bob, Charlie
>                respectively. Could be called "wallet Alice", "wallet
>                Bob", etc
> (B, C) = Coinswap fees paid by Alice and earned by Bob and Charlie.
> (M1, M2, M3) = Miner fees of the first, second, third, etc sets of
>                funding transactions. Alice will choose what these are
>                since she's paying.
> multisig(A+B) = A 2of2 multisig output with private keys held by A and B
> 
> The value in square parentheses refers to the bitcoin amount.
> 
> Alice funding txes
>   [WA btc] ---> multisig (Alice+Bob) [I btc]
>                 change [WA-M1-I btc]
> Bob funding txes
>   [WB btc] ---> multisig (Bob+Charlie) [I-M2-B btc]
>                 change [WB-I+B btc]
> Charlie funding txes
>   [WC btc] ---> multisig (Charlie+Alice) [(I-M2-B)-M3-C btc]
>                 change [WC-(I-M2-B)+C btc]
> 
> Here we've drawn these transactions as single transactions, but they are
> actually multiple transactions where the outputs add up some value (e.g.
> add up to I in Alice's transactions.)
> 
> === Table of balances before and after a successful CoinSwap ===
> 
> If a CoinSwap is successful then all the multisig outputs in the funding
> transactions will become controlled unilaterally by one party. We can
> calculate how the balances of each party change.
> 
> Party   | Before | After
> --------|--------|-------------------------------------------
> Alice   | WA     | WA-M1-I + (I-M2-B)-M3-C  = WA-M1-M2-M3-B-C
> Bob     | WB     | WB-I+B + I               = WB+B
> Charlie | WC     | WC-(I-M2-B)+C + I-M2-B   = WC+C
> 
> After a successful coinswap, we see Alice's balance goes down by the
> miner fees and the coinswap fees. Bob's and Charlie's balance goes up by
> their coinswap fees.
> 
> == Contract transaction definitions ==
> 
> Contract transactions are those which may spend from the 2-of-2 multisig
> outputs, they transfer the coins into a contract where the coins can be
> spent either by waiting for a timeout or providing a hash preimage
> value. Ideally contract transactions will never be broadcast but their
> existence keeps all parties honest.
> 
> M~ is miner fees, which we treat as a random variable, and ultimately
> set by whichever pre-signed RBF tx get mined. When we talk about _the_
> contract tx, we actually mean perhaps 20-30 transactions which only
> differ by the miner fee and have RBF enabled, so they can be broadcasted
> in sequence to get the contract transaction mined regardless of the
> demand for block space.
> 
> (Alice+timelock_A OR Bob+hash) = Is an output which can be spent
>                                  either with Alice's private key
>                                  after waiting for a relative
>                                  timelock_A, or by Bob's private key by
>                                  revealing a hash preimage value
> 
> Alice contract tx:
>     multisig (Alice+Bob) ---> (Alice+timelock_A OR Bob+hash)
>     [I btc]                   [I-M~ btc]
> Bob contract tx:
>     multisig (Bob+Charlie) ---> (Bob+timelock_B OR Charlie+hash)
>     [I-M2-B btc]                [I-M2-B-M~ btc]
> Charlie contract tx:
>     multisig (Charlie+Alice)  ---> (Charlie+timelock_C OR Alice+hash)
>     [(I-M2-B)-M3-C btc]            [(I-M2-B)-M3-C-M~ btc]
> 
> 
> === Table of balances before/after CoinSwap using contracts transactions ===
> 
> In this case the parties had to get their money back by broadcasting and
> mining the contract transactions and waiting for timeouts.
> 
> Party   | Before | After
> --------|--------|--------------------------------------------
> Alice   | WA     | WA-M1-I + I-M~                   = WA-M1-M~
> Bob     | WB     | WB-I+B + I-M2-B-M~               = WB-M2-M~
> Charlie | WC     | WC-(I-M2-B)+C + (I-M2-B)-M3-C-M~ = WC-M3-M~
> 
> In the timeout failure case, every party pays for their own miner fees.
> And nobody earns or spends any coinswap fees. So even for a market maker
> its possible for their wallet balance to go down sometimes, although as
> we shall see there are anti-DOS features which make this unlikely to
> happen often.
> 
> A possible attack by a malicious Alice is that she chooses M1 to be very
> low (e.g. 1 sat/vbyte) and sets M2 and M3 to be very high (e.g. 1000
> sat/vb) and then intentionally aborts, forcing the makers to lose much
> more money in miner fees than the attacker. The attack can be used to
> waste away Bob's and Charlie's coins on miner fees at little cost to the
> malicious taker Alice. So to defend against this attack Bob and Charlie
> must refuse to sign a contract transaction if the corresponding funding
> transaction pays miner fees greater than Alice's funding transaction.
> 
> 
> There can also be a failure case where each party gets their money using
> hash preimage values instead of timeouts. Note that each party has to
> sweep the output before the timeout expires, so that will cost an
> additional miner fee M~.
> 
> Party   | Before | After
> --------|--------|------------------------------------------------------
> Alice   | WA     | WA-M1-I + (I-M2-B)-M3-C-M~ - M~ = WA-M1-M2-M3-B-C-2M~
> Bob     | WB     | WB-I+B + I-M~ - M~              = WB+B-2M~
> Charlie | WC     | WC-(I-M2-B)+C + I-M2-B-M~ - M~  = WC+C-2M~
> 
> In this situation the makers Bob and Charlie earn their CoinSwap fees,
> but they pay an additional miner fee twice. Alice pays for all the
> funding transaction miner fees, and the CoinSwap fees, and two
> additional miner fees. And she had her privacy damaged because the
> entire world saw on the blockchain the contract script.
> 
> Using the timelock path is like a refund, everyone's coin just comes
> back to them. Using the preimage is like the CoinSwap transaction
> happened, with the coins being sent ahead one hop. Again note that if
> the preimage is used then coinswap fees are paid.
> 
> === Staggered timelocks ===
> 
> The timelocks are staggered so that if Alice uses the preimage to take
> coins then the right people will also learn the preimage and have enough
> time to be able to get their coins back too. Alice starts with knowledge
> of the hash preimage so she must have a longest timelock.
> 
> == EC tweak to reduce one round trip ==
> 
> When two parties are agreeing on a 2-of-2 multisig address, they need to
> agree on their public keys. We can avoid one round trip by using the EC
> tweak trick.
> 
> When Alice, the taker, downloads the entire offer book for the liquidity
> market, the offers will also contain a EC public key. Alice can tweak
> this to generate a brand new public key for which the maker knows the
> private key. This public key will be one of the keys in the 2-of-2
> multisig. This feature removes one round trip from the protocol.
> 
>     q = EC privkey generated by maker
>     Q = q.G = EC pubkey published by maker
> 
>     p = nonce generated by taker
>     P = p.G = nonce point calculated by taker
> 
>     R = Q + P = pubkey used in bitcoin transaction
>       = (q + p).G
> 
> Taker sends unsigned transaction which pays to multisig using pubkey Q,
> and also sends nonce p. The maker can use nonce p to calculate (q + p)
> which is the private key of pubkey R.
> 
> Taker doesnt know the privkey because they are unable to find q because
> of the ECDLP.
> 
> Any eavesdropper can see the nonce p and easily calculate the point R
> too but Tor communication is encrypted so this isnt a concern.
> 
> None of the makers in the route know each other's Q values, so Alice the
> taker will generate a nonce p on their behalf and send it over. I
> believe this cant be used for any kind of attack, because the signing
> maker will always check that the nonce results in the public key
> included in the transaction they're signing, and they'll never sign a
> transaction not in their interests.
> 
> 
> == Protocol ==
> 
> This section is the most important part of this document.
> 
> Definitions:
> fund = all funding txes (remember in this multi-tx protocol there can be
>        multiple txes which together make up the funding)
> A htlc = all htlc contract txes (fully signed) belonging to party A
> A unsign htcl = all unsigned htlc contract txes belonging to party A
>                 including the nonce point p used to calculate the
>                 maker's pubkey.
> p = nonce point p used in the tweak EC protocol for calculating the
>     maker's pubkey
> A htlc B/2 = Bob's signature for the 2of2 multisig of the Alice htlc
>              contract tx
> privA(A+B) = private key generated by Alice in the output
>              multisig (Alice+Bob)
> 
> 
>  | Alice           | Bob             | Charlie         |
>  |=================|=================|=================|
> 0. A unsign htlc ---->               |                 |
> 1.               <---- A htlc B/2    |                 |
> 2. ***** BROADCAST AND MINE ALICE FUNDING TXES ******  |
> 3. A fund+htlc+p ---->               |                 |
> 4.                 | B unsign htlc ---->               |
> 5.                 |               <---- B htlc C/2    |
> 6. ******* BROADCAST AND MINE BOB FUNDING TXES ******* |
> 7.                 | B fund+htlc+p ---->               |
> 8.               <---------------------- C unsign htlc |
> 9.    C htlc A/2 ---------------------->               |
> A. ***** BROADCAST AND MINE CHARLIE FUNDING TXES ***** |
> B.               <---------------------- C fund+htlc+p |
> C. hash preimage ---------------------->               |
> D. hash preimage ---->               |                 |
> E.    privA(A+B) ---->               |                 |
> F.                 |    privB(B+C) ---->               |
> G.               <---------------------- privC(C+A)    |
> 
> == Protocol notes ==
> 0-2 are the steps which setup Alice's funding tx and her contract tx for
>     possible refund
> 4-5 same as 0-2 but for Bob
> 8-9 same as 0-2 but for Charlie
> 3,7 is proof to the next party that the previous party has already
>     committed miner fees to getting a transaction mined, and therefore
>     this isnt a DOS attack. The step also reveals the fully-signed
>     contract transaction which the party can use to get their money back
>     with a preimage.
> C-G is revealing the hash preimage to all, and handing over the private
>     keys
> 
> 
> == Analysis of aborts ==
> 
> We will now discuss aborts, which happen when one party halts the
> protocol and doesnt continue. Perhaps they had a power cut, their
> internet broke, or they're a malicious attacker wanting to waste time
> and money. The other party may try to reestablish a connection for some
> time, but eventually must give up.
> 
> Number refers to the step number where the abort happened
> e.g. step 1 means that the party aborted instead of the action happening
> on protocol step 1.
> 
> The party name refers to what that party does
> e.g. Party1: aborts, Party2/Party3: does a thing in reaction
> 
> 0. Alice: aborts. Bob/Charlie: do nothing, they havent lost any time or
>    money
> 1. Bob: aborts. Alice: lost no time or money, try with another Bob.
>    Charlie: do nothing
> 2-3. same as 0.
> 4. Bob: aborts. Charlie: do nothing. Alice: broadcasts her contract tx
>    and waits for the timeout, loses time and money on miner fees, she'll
>    never coinswap with Bob's fidelity bond again.
> 5. Charlie: aborts. Alice/Bob: lose nothing, find another Charlie to
>    coinswap with.
> 6. same as 4.
> 7. similar to 4 but Alice MIGHT not blacklist Bob's fidelity bond,
>    because Bob will also have to broadcast his contract tx and will also
>    lose time and money.
> 8. Charlie: aborts. Bob: broadcast his contract transaction and wait for
>    the timeout to get his money back, also broadcast Alice's contract
>    transaction in retaliation. Alice: waits for the timeout on her htlc
>    tx that Bob broadcasted, will never do a coinswap with Charlie's
>    fidelity bond again.
> 9. Alice: aborts. Charlie: do nothing, no money or time lost. Bob:
>    broadcast bob contract tx and wait for timeout to get money back,
>    comforted by the knowledge that when Alice comes back online she'll
>    have to do the same thing and waste the same amount of time and
>    money.
> A-B. same as 8.
> C-E. Alice: aborts. Bob/Charlie: all broadcast their contract txes and
>      wait for the timeout to get their money back, or if Charlie knows
>      the preimage he uses it to get the money immediately, which Bob can
>      read from the blockchain and also use.
> F. Bob: aborts. Alice: broadcast Charlie htlc tx and use preimage to get
>    money immediately, Alice blacklists Bob's fidelity bond. Charlie:
>    broadcast Bob htlc and use preimage to get money immediately.
> G. Charlie: aborts. Alice: broadcast Charlie htlc and use preimage to
>    get money immediately, Alice blacklists Charlie's fidelity bond. Bob:
>    does nothing, already has his privkey.
> 
> ==== Retaliation as DOS-resistance ====
> 
> In some situations (e.g. step 8.) if one maker in the coinswap route is
> the victim of a DOS they will retaliate by DOSing the previous maker in
> the route. This may seem unnecessary and unfair (after all why waste
> even more time and block space) but is actually the best way to resist
> DOS because it produces a concrete cost every time a DOS happens.
> 
> 
> == Analysis of deviations ==
> 
> This section discusses what happens if one party deviates from the
> protocol by doing something else, for example broadcasting a htlc
> contract tx when they shouldnt have.
> 
> The party name refers to what that party does, followed by other party's
> reactions to it.
> e.g. Party1: does a thing, Party2/Party3: does a thing in reaction
> 
> If multiple deviations are possible in a step then they are numbered
> e.g. A1 A2 A2 etc
> 
> 
> 0-2. Alice/Bob/Charlie: nothing else is possible except following the
>      protocol or aborting
> 3. Alice: broadcasts one or more of the A htlc txes. Bob/Charlie/Dennis:
>    do nothing, they havent lost any time or money.
> 4-6. Bob/Charlie: nothing else is possible except following the protocol
>      or aborting.
> 7. Bob: broadcasts one or more of the B htlc txes, Alice: broadcasts all
>    her own A htlc txes and waits for the timeout to get her money back.
>    Charlie: do nothing
> 8. Charlie: nothing else is possible except following the protocol or
>    aborting.
> 9. Alice: broadcasts one or more of the A htlc txes. Bob: broadcasts all
>    his own A htlc txes and waits for the timeout.
> A. same as 8.
> B. Charlie: broadcasts one or more of the C htlc txes, Alice/Bob:
>    broadcasts all their own htlc txes and waits for the timeout to get
>    their money back.
> C-E1. Alice: broadcasts all of C htlc txes and uses her knowledge of the
>       preimage hash to take the money immediately. Charlie: broadcasts
>       all of B htlc txes and reading the hash value from the blockchain,
>       uses it to take the money from B htlc immediately. Bob: broadcasts
>       all of A htlc txes, and reading hash from the blockchain, uses it
>       to take the money from A htlc immediately.
> C-E2. Alice: broadcast her own A htlc txes, and after a timeout take the
>       money. Bob: broadcast his own B htlc txes and after the timeout
>       take their money. Charlie: broadcast his own C htlc txes and after
>       the timeout take their money.
> F1. Bob: broadcast one or more of A htcl txes and use the hash preimage
>     to get the money immediately. He already knows both privkeys of the
>     multisig so this is pointless and just damages privacy and wastes
>     miner fees. Alice: blacklist Bob's fidelity bond.
> F2. Bob: broadcast one or more of the C htlc txes. Charlie: use preimage
>     to get his money immediately. Bob's actions were pointless. Alice:
>     cant tell whether Bob or Charlie actually broadcasted, so blacklist
>     both fidelity bonds.
> G1. Charlie: broadcast one or more of B htcl txes and use the hash
>     preimage to get the money immediately. He already knows both
>     privkeys of the multisig so this is pointless and just damages
>     privacy and wastes miner fees. Alice: cant tell whether Bob or
>     Charlie actually broadcasted, so blacklist both fidelity bonds.
> G2. Charlie: broadcast one or more of the A htlc txes. Alice: broadcast
>     the remaining A htlc txes and use preimage to get her money
>     immediately. Charlies's actions were pointless. Alice: blacklist
>     Charlie's fidelity bond.
> 
> The multisig outputs of the funding transactions can stay unspent
> indefinitely. However the parties must always be watching the network
> and ready to respond with their own sweep using a preimage. This is
> because the other party still possesses a fully-signed contract tx. The
> parties respond in the same way as in steps C-E1, F2 and G2. Alice's
> reaction of blacklisting both fidelity bonds might not be the right way,
> because one maker could use it to get another one blacklisted (as well
> as themselves).
> 
> 
> == Conclusion ==
> 
> This document describes the first version of the protocol which
> implements multi-transaction Coinswap, routed Coinswap, fidelity bonds,
> a liquidity market and private key handover. I describe the protocol and
> also analyze aborts of the protocols and deviations from the protocol.
> 
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> 

== Miner fees ==
RBF is used on contract transactions as before, so each contract
transaction actually has many different versions each with a different
miner fee.

A possible vulnerability of using RBF is transaction pinning (see
https://bitcoinops.org/en/topics/transaction-pinning/). We solve this
issue by encumbering hashlock outputs with `1 OP_CSV`, so that it is not
possible to do CPFP on a contract transaction.

Another possible vulnerability (called post-coinswap-fee-burning) is
that after a successful CoinSwap, the party which no longer controls the
coins can still broadcast a high-fee RBF contract transaction in order
to burn coins to miner fees. This might be used by a malicious taker to
waste away the balance of a maker (the malicious taker might be another
maker who in the liquidity market is in competition with the victim
maker, and is using this exploit to attack their competitor).

=== Collateral payments ===
The post-coinswap-theft-attempt is an attack done after a CoinSwap is
finished. It works by the sender broadcasting their contract transaction
of the coins which no longer belong to him, they hope that the timeout
will expire and that they can sweep the coins. Their theft attempt is
very unlikely to actually succeed because of multiple redundant
watchtowers who will immediately spend the coins with the hashlock
branch, but the thief still might try because the attempt is essentially
riskless and costless.

Collateral payments are used to avoid this problem by making the theft
attempt not costless. (Although the cost is best kept very small,
corresponding to the risk of success being very low). (see
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-September/018151.html)

Post-coinswap-theft-attempts are already not costless for the taker,
because broadcasting the contract transactions damages privacy, which
the taker by construction wants to improve and has actually already paid
for. Privacy is reduced either by revealing the contract on-chain or by
reducing anonymity sets by having the coins spent immediately or very
soon). Therefore takers dont require collateral payments in this
protocol and this allows a taker to fully-spend their entire wallet in
one set of CoinSwaps (i.e. a sweep transaction with no change).

Collateral payments also solve the vulnerability of
post-coinswap-fee-burning for maker-maker CoinSwaps, because the miner
fee is taken from the collateral input and single-sig change, and not
from the CoinSwap contract.

==== Post-CoinSwap-fee-burning for takers ====
Collateral payments stop the post-coinswap-fee-burning attack but only
for makers, as takers dont use collateral payments.

However takers are unique in the way that takers pay CoinSwap fees. So
for a taker to attack a maker via post-coinswap-fee-burning they first
need to pay CoinSwap fees. So we just have makers refuse to sign RBF
transactions paying a fee higher than the CoinSwap fee they earn. (Or
perhaps a constant factor, for example a maker imposes the condition
that the RBF miner fee can only be 5x or 10x the CoinSwap fee).


== Funding transaction definitions ==
Same as in the v1 design doc.


== Contract transaction definitions ==
In the v1 design each party in a CoinSwap possessed the _same_ contract
transaction. This is no longer the case, and each party might know
slightly different versions, perhaps differing by miner fees or whether
a collateral payment is used.

As before the value in square parentheses refers to bitcoin amount. The
value in the round parentheses refers to script.

Contract transactions have this notation based on who knows them:
    contract tx for the Alice-Bob multisig, known only to Alice
  = contract tx Alice-Bob/Alice
  = contract tx AB/A

=== Contract txes known by receiver ===
These are contract transactions known by the receiver of coins from the
multisig. They are pretty much the same as in v1, except with added `1
OP_CSV` to the hashlock (not included here for clarity).

Alice-Bob/Bob contract tx:
    multisig (Alice+Bob) ---> (Alice+timelock_A OR Bob+hash)
    [I btc]                   [I-M~ btc]

Bob-Charlie/Charlie contract tx:
    multisig (Bob+Charlie) ---> (Bob+timelock_B OR Charlie+hash)
    [I-M2-B btc]                [I-M2-B-M~ btc]

Charlie-Alice/Alice contract tx:
    multisig (Charlie+Alice) ---> (Charlie+timelock_C OR Alice+hash)
    [(I-M2-B)-M3-C btc]           [(I-M2-B)-M3-C-M~ btc]

=== Table of balances before and after a coinswap resolved with contract
txes known to recievers ===
If a CoinSwap is resolved with contract txes known to receivers, then
that means the parties had to get their money back by broadcasting and
mining the contract transactions, and spending the output using their
knowledge of the hash preimage. Each party has to spend the output
before the timeout expires, so that costs an additional miner fee M~.

Party   | Before | After
--------|--------|-------------------------------------------
Alice   | WA     | WA-M1-I + (I-M2-B)-M3-C-M~ - M~ = WA-M1-M2-M3-B-C-2M~
Bob     | WB     | WB-I+B + I-M~ - M~              = WB+B-2M~
Charlie | WC     | WC-(I-M2-B)+C + I-M2-B-M~ - M~  = WC+C-2M~

The makers earn their CoinSwap fees but pay an additional miner fee
twice, so they are incentivized to avoid this outcome compared to the
success case where they just earn their fees. Alice is incentivized to
avoid this outcome because she would pay for miner fees and coinswap
fees, and not get any privacy in return.

=== Contract txes known by the sender ===
The maker's contract transaction must include a collateral payment.

definitions:
    Jb, Jc = value of a maker's (Bob, Charlie) collateral input
    K = collateral amount, which a maker loses if he broadcasts his
contract tx but doesnt get the money using the hash preimage

Alice-Bob/Alice contract tx:
    multisig (Alice+Bob) ---> (Alice+timelock_A OR Bob+hash)
             [I btc]          [I-M~ btc]

Bob-Charlie/Bob contract tx:
    multisig  (Bob+Charlie) ---> (Bob+timelock_B OR Charlie+hash)
              [I-M2-B btc]       [I-M2-B+K btc]
    singlesig (Bob)              (Bob)
              [Jb btc]           [Jb-K-M~ btc]

Charlie-Alice/Charlie contract tx:
    multisig  (Charlie+Alice)     ---> (Charlie+timelockC OR Alice+hash)
              [(I-M2-B)-M3-C btc]      [(I-M2-B)-M3-C+K btc]
    singlesig (Charlie)                (Charlie)
              [Jc btc]                 [Jc-K-M~ btc]

=== Table of balances before and after a coinswap resolved with contract
txes known to senders ===
If a coinswap is resolved with contract txes known to senders, then that
means the parties had to get their money back by broadcasting and mining
the contract transactions, and spending the output by waiting for the
timeout.

Party   |Before | After
--------|-------|-------------------------------------------
Alice   | WA    |WA-M1-I + I-M~                            = WA-M1-M~
Bob     | WB+Jb |WB-I+B + I-M2-B+K + Jb-K-M~               = WB+Jb-M2-M~
Charlie | WC+Jc |WC-(I-M2-B)+C + (I-M2-B)-M3-C+K + Jc-K-M~ = WC+Jc-M3-M~

Everyone gets their money back and pays for their own miner fees. And
the CoinSwap didn't happen, which is crappy considering money was lost
in miner fees but part of the point of fidelity bonds is to stop this
happening too much.

=== Table of balances before and after a successful CoinSwap but with
one post-CoinSwap-theft-attempt ===
Here the CoinSwap has succeeded but one maker (Bob in this case) does a
post-coinswap-theft-attempt, which fails, because the next party
(Charlie) uses the hash preimage to spend the coins. Most coins can
remain unspent on-chain because of private-key-handover, but the
Bob-Charlie/Bob contract transaction was broadcast and mined.

Party   | Before | After
--------|--------|-------------------------------------------
Alice   | WA     | WA-M1-I + (I-M2-B)-M3-C  = WA-M1-M2-M3-B-C
Bob     | WB+Jb  | WB-I+B + Jb-K-M~ + I     = WB+Jb+B-K-M~
Charlie | WC     | WC-(I-M2-B)+C + I-M2-B+K = WC+C+K

As we see, Alice's outcome is the same as in the success case. Compared
to the success case, Bob loses K bitcoins and an extra miner fee while
Charlie gains K bitcoins.

Looking at these equations, I realize that the incentives against
post-coinswap-theft-attempt still work even if we set K = 0, because the
extra miner fee paid by Bob could be enough disincentive.


== Protocol ==
Definitions:
    A fund = Alice's funding tx
    AB/A us htlc = unsigned contract tx for the A-B multisig, where the
        fully-signed version is only meant to be known by A
    AB/A htlc B/2 = Bob's signature for contract tx for the A-B
        multisig, where the fully-signed version is only meant to be
        known by A
    p = nonce point p used in the tweak EC protocol for calculating the
        maker's pubkey, used to avoid one round trip
    privA(A+B) = private key generated by Alice in the A-B multisig

 | Alice           | Bob             | Charlie         |
 |=================|=================|=================|
0.  AB/A us htlc ---->               |                 |
1.               <---- AB/A htlc B/2 |                 |
2.    ***** BROADCAST AND MINE ALICE FUNDING TX *****  |
3.    A fund + p ---->               |                 |
4.               <---- AB/B us htlc  |                 |
5. AB/B htlc A/2 ---->               |                 |
6.                 |  BC/B us htlc ---->               |
7.                 |               <---- BC/B htlc C/2 |
8.    ***** BROADCAST AND MINE BOB FUNDING TX *****    |
9.                 |    B fund + p ---->               |
A.                 |               <---- BC/C us htlc  |
B.                 | BC/C htlc B/2 ---->               |
C.               <---------------------- CA/C us htlc  |
D. CA/C htlc A/2 ---------------------->               |
E.   ***** BROADCAST AND MINE CHARLIE FUNDING TX ***** |
F.               <---------------------- C fund + p    |
G.  CA/A us htlc ---------------------->               |
H.               <---------------------- CA/A htlc C/2 |
I. hash preimage ---------------------->               |
J. hash preimage ---->               |                 |
K.    privA(A+B) ---->               |                 |
L.                 |    privB(B+C) ---->               |
M.               <---------------------- privC(C+A)    |

=== Protocol notes ===
0-2. Alice sets up her funding tx and contract tx for possible refund
     with timeout
3.   Alice convinces Bob that their multisig is funded, and therefore
     this whole thing isnt a DOS
4-5. Bob obtains his contract tx for the A-B multisig
6-8. Same as 0-2 but for Bob
9.   Same as 3. but for Bob/Charlie
A-B. Same as 4-5 but for Charlie
C-E. Same as 0-2 and 6-8 but for Charlie
F.   Same as 3 and 9 but for Charlie/Alice
G-H. Same as 4-5 or A-B but for Alice
H.   After this step every party's coins are locked up in multisig, and
     they can all get the coins back after the timeout, or if they know
     the hash preimage they can get different coins immediately.
I-J. Reveal preimages to everyone, making the coins do an off-chain hop
     ahead by one step.
K-M. Reveal private keys to each other. The incentive to do this is to
     save on miner fees, and improve privacy.

=== Analysis of aborts ===
Aborts are when one party halts the protocol (i.e. they had a power cut,
or they are a DOS attacker). Here we analyze how the other parties react.

As in v1, the number refers to the step number where the abort happened.

0. Alice: aborts. Bob/Charlie: do nothing, they havent lost any time or
   money.
1. Bob: aborts. Alice: lost no time or money, try with another Bob.
   Charlie: do nothing
2-3. Same as 0.
4. Bob: aborts. Charlie: do nothing. Alice: broadcasts contract tx AB/A
   and waits for the timeout, loses time and money on miner fees, she'll
   never coinswap with Bob's fidelity bond again.
5. Same as 0.
6. Same as 4.
7. Charlie: aborts. Alice/Bob: lose nothing, find another Charlie to
   coinswap with.
8. Same as 4.
9. Similar to 4 but Alice MIGHT not blacklist Bob's fidelity bond,
   because Bob will also have to broadcast his contract tx BC/B and will
   also lose time and money. Alice could take Bob's collateral from
   transaction BC/B, but the value K is small and Alice must spend time
   and miner fees on her funding transaction, so this isn't a way to DOS
   for free.
A. Charlie: aborts. Bob: broadcast his contract tx BC/B and wait for the
   timeout to get his money back, also broadcast Alice's contract
   transaction AB/B in retaliation. Alice: waits for the timeout on her
   contract tx that Bob broadcasted, will never do a coinswap with
   Charlie's fidelity bond again.
B. Same as 9.
C. Same as A.
D. Alice: aborts. Charlie: do nothing, no money or time lost. Bob:
   broadcast BC/B contract tx and wait for timeout to get money back,
   comforted by the knowledge that when Alice comes back online she'll
   have to do the same thing and waste the same amount of time and
   money.
E. Same as A.
F. Similar to A. but Alice MIGHT not blacklist Charlie's fidelity bond,
   because Charlie will also have to broadcast his contract tx CA/C and
   will also lose time and money.
G. Alice: aborts. Bob/Charlie: all broadcast their contract txes and
   wait for the timeout to get their money back.
H. Same as F.
I-K. Similar to G, but if Charlie knows the hash preimage he can use his
     contract tx to get the money immediately instead of waiting for the
     timeout. Bob can read that preimage from the blockchain and use it
     to also get his money immediately.
L. Bob: aborts. Alice: hopefully get Charlie's privkey, but if not then
   broadcast CA/A and use preimage to get money immediately, and never
   coinswap with Bob's fidelity bond again. Charlie: broadcast BC/C and
   use preimage to get money immediately.
M. Charlie: aborts. Alice: broadcast CA/A and use preimage to get money
   immediately, and never coinswap with Charlie's fidelity bond again.
   Bob: do nothing, already has Alice's privkey.

== Analysis of deviations ==

Deviations are when one party does something other than what's in the
protocol, for example broadcasting a contract transaction when they
shouldnt have.

The party name refers to what that party does, followed by other party's
reactions to it.
e.g. Party1: does a thing, Party2/Party3: does a thing in reaction.

If multiple deviations are possible in a step then they are numbered.
e.g. 5(1) 5(2) 5(3)


0-2. Alice/Bob/Charlie: nothing else is possible except following the
protocol
     or aborting.
3. Alice: broadcasts one or more of the AB/A contract txes. Bob/Charlie:
   do nothing, they havent lost any time or money.
4. Bob/Charlie: nothing else is possible except following the protocol
   or aborting.
5. Same as 3.
6. Bob: broadcasts one or more of the AB/B contract txes. Alice:
   broadcasts the remaining contract txes and waits for the timeout to
   get her money back, and never coinswaps with Bob's fidelity bond
   again. Charlie: do nothing.
7. Charlie: nothing else is possible except following the protocol or
   aborting.
8. Same as 6.
9(1). Same as 6.
9(2). Bob: broadcast BC/B contract txes. Alice: broadcast her AB/A
      contract tx and wait for the timeout to get her money back, and
      never coinswaps with Bob's fidelity bond again. Charlie: do
      nothing.
A. Charlie: broadcast BC/C contract tx. Bob: wait for the timeout to get
   his money back, also broadcast Alice's contract transaction AB/B in
   retaliation. Alice: waits for the timeout on her contract tx that Bob
   broadcasted, will never do a coinswap with Charlie's fidelity bond
   again.
B. Same as 9(1). and 9(2).
C. Same as A.
D. Alice: broadcast AB/A contract tx. Bob: broadcast his own BC/B
   contract tx and wait for the timeout to get his money back. Charlie:
   do nothing
E. Same as A.
F. Charlie: broadcast CA/C contract tx. Alice: broadcast her AB/A
   contract tx and wait for the timeout to get her money back, never do
   a coinswap with Charlie's fidelity bond again. Bob: broadcast his
   BC/B contract tx and wait for the timeout to get his money back.
G. Same as D. except Charlie must also broadcast his CA/C contract tx
   and wait for the timeout.
H. Same as F.
I-K(1). Alice: broadcast AB/A contract txes. Bob: broadcast BC/B
        contract txes and wait for the timeout, or use the hash preimage
        if he knows it. Charlie: broadcast CA/A contract txes and wait
        for timeout, or use hash preimage if known.
I-K(2). Alice: broadcast CA/A contract txes. Bob: broadcast AB/B and
        wait for the timeout, or use the hash preimage if its known.
        Charlie: broadcast BC/C and wait for timeout, or use the hash
        preimage if known.
I-K(3). Alice: broadcast both AB/A and CA/A contract txes. Bob:
        broadcast BC/B contract tx and wait for the timeout, or use the
        hash preimage if its known. Charlie: broadcast BC/C if Bob
        hasn't broadcast his, and wait for the timeout, or use the hash
        preimage if known.
L. Similar to I-K(n), Bob can broadcast one or both the sets of contract
   txes he knows. The other parties broadcast the remaining ones and
   either use the timeout or hash preimage value. Alice bans Bob's
   fidelity bond.
M. Same as L. but Charlie broadcasting. Alice bans Charlie's fidelity
   bond.


Unlike the v1 protocol, each CoinSwap party knows a different version of
the contract transactions, so the taker Alice always knows which maker
broadcast a certain set of contract transactions, and so can always ban
the correct fidelity bond.


== Conclusion ==
This document modifies the earlier version 1 detailed protocol design
for multi-transaction CoinSwap. It has each CoinSwap party knowing a
slightly different version of the contract transactions. It also uses
collateral payments. These features are both used to fix attacks found
during review of the v1 protocol.





^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap appendium
  2020-10-03 10:36 ` [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap appendium Chris Belcher
@ 2020-10-03 13:31   ` ZmnSCPxj
  0 siblings, 0 replies; 24+ messages in thread
From: ZmnSCPxj @ 2020-10-03 13:31 UTC (permalink / raw)
  To: Chris Belcher, Bitcoin Protocol Discussion

Good morning Chris,

>
> Looking at these equations, I realize that the incentives against
> post-coinswap-theft-attempt still work even if we set K = 0, because the
> extra miner fee paid by Bob could be enough disincentive.

This made me pause for a moment, but on reflection, is correct.

The important difference here relative to v1 is that the mining fee for the collateralized contract transaction is deducted from the `Jb` input provided by Bob.


>     Unlike the v1 protocol, each CoinSwap party knows a different version of
>     the contract transactions, so the taker Alice always knows which maker
>     broadcast a certain set of contract transactions, and so can always ban
>     the correct fidelity bond.

Great observation, and an excellent property to have.

Will go think about this more.

Regards,
ZmnSCPxj


^ permalink raw reply	[flat|nested] 24+ messages in thread

end of thread, other threads:[~2020-10-03 13:32 UTC | newest]

Thread overview: 24+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-08-11 12:05 [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap Chris Belcher
2020-08-20 11:17 ` ZmnSCPxj
2020-08-20 15:28   ` Nadav Kohen
2020-08-20 21:38     ` ZmnSCPxj
2020-08-20 22:37       ` Chris Belcher
2020-08-20 22:15   ` Chris Belcher
2020-08-21  4:20     ` ZmnSCPxj
2020-08-21  9:47       ` Chris Belcher
2020-08-22  1:09         ` ZmnSCPxj
2020-08-24 19:30 ` Antoine Riard
2020-08-25  3:16   ` ZmnSCPxj
2020-09-03  9:00     ` Chris Belcher
2020-09-03  9:45       ` ZmnSCPxj
2020-09-03 10:50         ` Chris Belcher
2020-09-03 23:39           ` ZmnSCPxj
2020-09-05  2:45             ` ZmnSCPxj
2020-09-05  1:10     ` Antoine Riard
2020-09-05  2:29       ` ZmnSCPxj
2020-08-29 22:03   ` Chris Belcher
2020-08-30 13:38     ` ZmnSCPxj
2020-09-05  1:07     ` Antoine Riard
2020-09-06  3:06       ` seid Mohammed
2020-10-03 10:36 ` [bitcoin-dev] Detailed protocol design for routed multi-transaction CoinSwap appendium Chris Belcher
2020-10-03 13:31   ` ZmnSCPxj

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox