Date: Thu, 20 Aug 2020 11:17:07 +0000
To: Chris Belcher <belcher@riseup.net>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <xhRsCejqgUjoLy5hPMHgFcZdiqJsO7TfS0azWhis9-tvSgXodoKe7gN5IXyiVIVqUWSm7FoY-aBUaJCCDgixdWUN4n8EzhQlSNshsQeIFsw=@protonmail.com>
In-Reply-To: <813e51a1-4252-08c0-d42d-5cef32f684bc@riseup.net>
References: <813e51a1-4252-08c0-d42d-5cef32f684bc@riseup.net>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Subject: Re: [bitcoin-dev] Detailed protocol design for routed
	multi-transaction CoinSwap
Precedence: list

Good morning Chris,

Great to see this!

Mostly minor comments.


>
> =3D=3D Direct connections to Alice =3D=3D=3D
>
> 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 partic=
ipant knows the total number of participants.
Thus, in CoinJoin, it is fairly useless to have just one taker and one make=
r, 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 parti=
cipants 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 woul=
d 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, an=
d then demand the final payment and any change as two separate swaps from t=
he final maker.
  * Intermediate makers are likely to not have exact amounts, thus is unlik=
ely 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 =3D=3D more delay in tak=
er responses.


>
> =3D=3D=3D Miner fees =3D=3D=3D
>
> 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 additi=
onal 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 feerat=
e, 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 p=
ays 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=
.


> =3D=3D Contract transaction definitions =3D=3D
>
> 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 l=
argest 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 fo=
rwarding those fees as well, how does that work when there are multiple ver=
sions of the contract transaction?

>
> (Alice+timelock_A OR Bob+hash) =3D 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 p=
ossible to wait indefinitely to spend the UTXO it received.
This is in contrast with absolute timelocks, where after private key turnov=
er, 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 onch=
ain 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 offli=
ne 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 offli=
ne, try a contract transaction broadcast, if it confirms, the taker can wai=
t 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 bas=
ic requirement for private key turnover.
  * On the other hand, the taker has the largest timeout before it can claw=
back the funds, so it would wait for a long time, and at any time in betwee=
n 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 lo=
se.
  * 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 w=
ith the smallest timelock, so it is the least-risk and therefore a maker wh=
o notices its outgoing HTLC has a low timeout might want to just do this an=
yway even if it is unsure if the taker is offline.
  * Participants might want to spend from the UTXO to a new address after p=
rivate key turnover anyway.
    Makers could spend using a low-fee RBF-enabled tx, and when another req=
uest 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.


>
> =3D=3D EC tweak to reduce one round trip =3D=3D
>
> 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 =3D EC privkey generated by maker
> Q =3D q.G =3D EC pubkey published by maker
>
> p =3D nonce generated by taker
> P =3D p.G =3D nonce point calculated by taker
>
> R =3D Q + P =3D pubkey used in bitcoin transaction
> =3D (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 t=
weak to blind this.

In 2p-ECDSA, for two participants M =3D m * G; T =3D t * G, the total key i=
s m * t * G =3D m * T =3D 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 o=
f 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 P2W=
PKHs) tx.

>
> =3D=3D Protocol =3D=3D

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

The protocol looks correct to me.

LOL.

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


>     =3D=3D=3D=3D Retaliation as DOS-resistance =3D=3D=3D=3D
>
>     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 resis=
t
>     DOS because it produces a concrete cost every time a DOS happens.

I agree.

>
>     =3D=3D Analysis of deviations =3D=3D
>
>     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 part=
y'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 proto=
col
>     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 al=
l
>     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 preima=
ge
>     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 preim=
age
>     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: broadca=
st
>     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. T=
he
>     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 w=
ay,
>     because one maker could use it to get another one blacklisted (as wel=
l
>     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