Support fees

[AdamISZ]

I expect it will not be too hard to do this, at least in a dumb way, but it interacts awkwardly with backouts.

(EDIT I think the below is all wrong; will come back to it later)

(In the following paragraph, "bf" = bitcoin transaction fee and "cf" = coinswap fee):
(The diagram at the bottom of this may help in thinking).
The simplest way to do it is to have the TX0 and TX1 amounts be different; e.g. Carol deposits 1btc to TX1, Alice deposits 1btc + bf x 4 + cf to TX0. The two paths are: Alice -> TX0 -> TX4 (Carol), and Carol -> TX1 -> TX5(Alice). So for the first of those, Carol receives 1 + bf x 2 + cf and for the second, Alice receives 1 - bf x2. The net balance is: Carol is up by cf, and Alice is down by 4 x bf + cf.

It should be coded to allow negative values for cf, just in case that turns out to be a viable idea.

This as mentioned above is the "dumb" way, because it ignores backouts. What is tricky there is that it is not known in advance which of TX2/TX3 will be the source of each sides backouts, and they must be signed and entirely fixed in advance. This is why a more persistent-identity, client/server model is more attractive, to reduce these nasty backouts to the minimum. Now, TX2 is fixed to spend the same output as TX0, and TX3 likewise for TX1. One approach is to ensure that whichever backout Alice redeems, she does not gain money, e.g. TX2 out value = TX3 out value = 1btc in the above example; this would burn the coinswap fees to miner fees and give Alice negative incentive to cheat, but would leave Carol with the same amount she put in, losing nothing. I think this might be the best and simplest compromise to start with.

This is explicitly not included in the 0.0.1 milestone, perhaps it suits a 0.1 milestone (first version usable on mainnet), but up for debate.

Other non-dumb ways to address the interaction of fees with backouts may well exist, but I'd lean against over-complicating the protocol because of it; it's already complicated enough! There is already some discussion over at JoinMarket-Org/joinmarket#335

[AdamISZ]

(edit: adding link to sketch diagram, it may help to understand.)

OK after several attempts at thinking about this, I think I have a workable solution with minimal changes to the proposed protocol. Discussion below takes as starting point the diagram at the bottom of https://github.com/AdamISZ/CoinSwapCS/blob/master/docs/coinswap_new.pdf , as usual.

So the main goal is to prevent Carol losing any funds if Alice is malicious.

I think this also addresses amount correlation, at least partially, but will keep thinking about it.

So, rather as above:

• cf = coinswap fee
• bf = an amount representing the approximate cost of a bitcoin transaction with one input
• Δ - an offset amount used by Carol for amount ambiguation
• (Edited to add): '1' here is the nominal amount of the swap in BTC; can be replaced with arbitrary 'x'

Remember that we don't know in advance which of TX2 or TX3 will be used by Alice in any backout; and moreover, Alice can choose which. So the TX2 and TX3 outputs more or less have to be the same, or at least, it's pointless to create a different one such that one is more advantageous to a malicious Alice, as she will always pick that one in that case.

The main idea is: add a second output to the backout transactions TX2/TX3, redeemable by Carol only (let's say p2pkh for simplicity). This allows Carol to always receive more from the backout than Alice, most importantly allowing Carol never to lose funds in case of backout/failure.

The secondary idea is the use of a "blinding" Δ amount by Carol, as already mentioned above.

Here is a proposed transaction "matrix":

Funding transactions; note the code already randomises the output order, for simplicity we assume output 0 is the 2/2 funding utxo:

TX0

Input	Input Value	->	Output	Output value
(From wallet)	1 + cf + bf x 4 + (wallet selection)		2_2_AC	1 + cf + bf x 3
			(to wallet)	(change amount)

TX1

Input	Input Value	->	Output	Output value
(From wallet)	Δ + 1 + cf + bf x 4 + (wallet selection)		2_2_CB	Δ + 1 + cf + bf x 3
			(to wallet)	(change amount)

Next pair are the cooperative outputs; TX4 goes to Carol, TX5 goes to Alice; note there is an open issue to add pseudo change address here, #17 . This could be additional to this basic structure.

TX4

Input	Input Value	->	Output	Output value
TX0:0	1 + cf + bf x 3		Carol only	1 + cf + bf x 2

TX5

Input	Input Value	->	Output	Output value
TX1:0	Δ + 1 + cf + bf x 3		Alice only	1
			Carol only	Δ + cf + bf x 2

The backout transactions; they must as mentioned above have the same output amounts, but here we add an additional Carol only output

TX2

Input	Input Value	->	Output	Output value
TX0:0	1 + cf + bf x 3		(Carol, secret) or (Alice, timeout)	1 + bf
			Carol only	cf + bf

TX3

Input	Input Value	->	Output	Output value
TX1:0	Δ + 1 + cf + bf x 3		(Alice, secret) or (Carol, timeout)	1 + bf
			Carol only	Δ + cf + bf

Accounting

Carol inputs Δ + 1 + cf + bf x 3. In cooperative case she received back (Δ + cf + bf x 2 from TX5) + (1 + cf + bf x 2 from TX4), for a net gain of (cf + bf). In recovery case she receives back (1+ bf from TX2 or TX3), and (Δ + cf x 2 + bf x 2 from both), for a net gain of (cf). However she needs to redeem that backout, so it's actually (cf - bf) gain realistically.

Alice inputs 1 + cf + bf x 4. In cooperative case she received back (1 from TX5) for a net payment of cf + bf x 4. In recovery case she receives back (1+ bf from TX2 or TX3) for a net payment of cf + bf x 3; however she also needs to pay 1 bf to redeem the backout transaction (usually), so it's basically the same cost (cf + bf x 4) (without the privacy boost).

Amount correlation, privacy issues

The use of a blinding Δ is a help if I've got this right so far. The main TX4/TX5 outputs can be pretty obfuscated with the use of that; you could split them up with fake changes. You could also make delta whatever makes it most obfuscated.

The idea that TX5 can have an output to both Alice and Carol doesn't seem to be a problem; Alice can take that utxo knowing it has no connection to her history.

Carols cf + bf output from TX2 is going to be small; but by design should be spendable to an output of cf (doesn't have the time priority requirement that the other custom redeem script output has).

[fivepiece]

I can't see an issue with the acconting, and I think it's fine to include the output to carol. If anything it asserts honest intentions by alice, and if she's the one making contact then it might be fair.
I didn't look into carol trying to game the amounts in her favor, but otoh a cf and bf can be checked to be "sane" (by looking at tx size) and delta's amount is up to alice to consider.

Let's assume an honest coinswap, TX4 and TX5 are relayed.

amount = x
delta = d

tx4out:0 = x + cf + 2bf
tx5out:1 = d + cf + 2bf

TX5's input is TX1, so

tx1out:0 = d + x + cf +3bf

And TX4's is TX0, so

tx0out:0 = x + cf + 3bf

And:

tx1out:0 = tx0out:0 + d
d = tx1out:0 - tx0out:0

Rest of this is wrong, next comments

`tx1out:0 - bf = tx5out:1`
`bf = tx1out:0 - tx5out:1`
`tx4out:0 = tx5out:1 + x`
`x = tx5out:1 - tx4out:0`
tx0out:0 = (tx5out:1 - tx4out:0) + cf + 3(tx1out:0 - tx5out:1)
tx0out:0 = -2*tx5out:1 - tx4out:0 + cf + 3tx1out:0
cf = tx0out:0 + 2*tx5out:1 + tx4out:0 - 3*tx1out:0
so maybe this is "trackable"?
`x == tx5out:0 && x == (tx5out:1 - tx4out:0) && x == ...`

Wrong ^

These are just some "lines on a napking", hopefully I didn't confuse the algebra altogether.. sorry if I did and please point it out.
if it makes sense, I'm trying to figure out what introducing "delta" means for a spy.

[AdamISZ]

If anything it asserts honest intentions by alice, and if she's the one making contact then it might be fair.

Yes, the whole design is based on: (1) the assumption that Alice sees Carol's service as being valuable and paying for it, (2) a perception of a difference with the Coinjoin case; that because of the backouts, it'll be far more difficult to create a 100% trustless case (it's hard enough in joinmarket!), and that there will have to some rough assessment of reputation by at least one side to gain confidence that backout will not occur. Hence trying to create a setup where Alice pays for the service, and Carol doesn't need to trust Alice at all not to be malicious. That leaves Alice needing to make a reputation decision about Carol, although the worst that happens is she loses a small chunk of fees and time.

W.r.t the tracking:

I think there may be a mistake in the indices of the "And" section, but the gist of it is your:

x == tx5out:0 && x == (tx5out:1 - tx4out:0) && x == ...

This isn't exactly correct according to the above tables? I think it's rather:

x == tx5out:0 && x == (tx4out:0 - tx5out:1 + d) && x == ..

so assuming you know d (as you point out, it's the difference between tx1:0 and tx0:0 out, although remember, the tx0/1 outs are randomized so you have to know which one is the non-change), you can generate a potential match on a pair of transactions with that equality.

I guess this is roughly what I expected. Let's assume timing correlation is put aside (see #18), and the analyst has to analyse basically all p2sh transactions; he can compare pairwise and generate a list of possible d values .. given each one, he can try to find matches on other pairs with similar output sizes such that the above x check works. He has to try different tx0/1 outs (mentioned above). It sounds very hard (fair amount of combinatorial blow up), especially if you have to tune tolerances, if we use somewhat randomised bitcoin fees (i.e. we don't force the value of bf to be exactly equal for each transaction). Adding pseudo change addresses won't change much except perhaps on tx5 side since you have to run the matching algo against subsets of the outputs.

[fivepiece]

amount = x
delta = d

tx4out:0 = x + cf + 2bf
tx5out:1 = d + cf + 2bf

TX5's input is TX1, so

tx1out:0 = d + x + cf +3bf

And TX4's is TX0, so

tx0out:0 = x + cf + 3bf

And:

tx1out:0 = tx0out:0 + d
d = tx1out:0 - tx0out:0

tx1out:0 - bf = tx5out:1 - x
bf + x = tx1out:0 - tx5out:1

tx4out:0 = tx5out:1 + x
d - x = tx5out:1 - tx4out:0

so,

x = tx4out:0 - tx5out:1 - tx1out:0 + tx0out:0
bf = 2*tx1out:0 - tx4out:0 - tx0out:0

finally,
cf = -( d + x + 3bf )
cf = -( d + 2bf )
cf = -( x + bf )
cf = -( tx4out:0 - tx5out:1 - tx1out:0 + tx0out:0 + 2*tx1out:0 - tx4out:0 - tx0out:0`
cf = -( - tx5out:1 + tx1out:0 - tx4out:0 )
cf = tx5out:1 + tx4out:0 - tx1out:0

As discussed in #coinswap, this is going to be very hard even if this time I got it right.
The question is really which of the values used in the coinswap are advertised by carol for some spy to see, and if it's possible to unconver coinswaps using that knowledge alone.
The introduction of d isn't a problem:
<waxwing> without d the input/output pair is basically the same within tolerance

As the fee protocol is ironed out, we'll get a better idea on what's possible.

[AdamISZ]

The question is really which of the values used in the coinswap are advertised by carol for some spy to see, and if it's possible to unconver coinswaps using that knowledge alone.

Yes. I think

• bf can be taken as a given to be (a) easily predictable (let's say it's ~ the priority fee for a 1 or 2 input tx) roughly, but impossible to know down to the satoshi.
• d can be assumed private to the specific Alice/Carol parties; it will be shared only in private, and new for each proposed CoinSwap.
• cf is the difficult one; Carol has to advertise her fees somehow, but avoid giving it out to any interested party if possible. I doubt it'll be possible to do better than merely somewhat randomise the fee offer for each proposed swap, at least not without yet more nasty complexity.

Re:

The introduction of d isn't a problem:

Well but that's a funny way to put it; it's intended to solve a problem :) Without it, the two pairs of transactions are trivially linked.

Re the calculation, I think the last line, for cf, misses a bf, I think it's:

cf = tx5out:1 + tx4out:0 - tx1out:0 - bf

[fivepiece]

It's missing a lot more :)
I'll retract any concerns for now. I'm pretty convinced this works now.

[AdamISZ]

A point noted from the process of testing this setup:

• Alice does not have a defence against losing ~ 1*cf in this model - specifically because we have Alice broadcast TX0 first, and if Carol decides not to do anything after TX0 confirms, Alice is forced to recover via TX2, which gives Carol unconditionally the coinswap fee output (cf + bf in the above).

This is suboptimal, but may still be practical, but only in a situation where one leans a bit on reputation, and losing a coinswap fee once wouldn't be much of an issue (you just move to a better provider of the service), because it's so small. But, someone willing to pay a large fee (e.g. 0.5-1% on a large amount), let's say that the market requires it, has to assess it significantly differently than if it didn't have this drawback.

[AdamISZ]

Above plan implemented in merge at cd39b5c

Closing this based on it being a task towards a milestone, but feel free to keep discussing it (the last comment above does seem like a meaningful drawback). Or just start another issue.

[AdamISZ]

Reopening, just realised it wasn't part of the milestone. And it's nicer to keep continuity of discussion.

[AdamISZ]

Documentation of the above has been added in docs/fees.md

[AdamISZ]

At the risk of flip-flopping, I'm going to close this now as it's both implemented in the code, and documented, issue can be reopened or new issue opened if there are specific problems with it.

[chris-belcher]

Copypasting this here

I think the blinding amount thing can be broken. In the cooperative case, Alice receives an output of 1 btc, the same tx has another output going to Carol for Delta btc. The adversary can calculate 1 + Delta btc and search the blockchain for transactions where 1 + Delta btc is the output value, which would be carol's funding tx1, therefore unmixing the coinswap.

[AdamISZ]

Yes, I agree. As I noted in the second comment:
"I think this also addresses amount correlation, at least partially, but will keep thinking about it."

In other words, I wasn't really convinced, but it seemed like adding a delta was a net benefit.

At some point later, I decided that it was not really useful except as a weak obfuscation, probably through similar logic, although I forget; but I didn't write it down anywhere.

Thanks for writing it here now -> it doesn't solve amount correlation.