Add CoinSwap to JoinMarket

[chris-belcher]

JoinMarket currently creates CoinJoins but there's no reason the incentive model cant also be applied to CoinSwap. In the end, the same yield-generator bots (and patientsendpayments) could announce offers to enter into coinswap as well as coinjoin)

CoinSwap: https://bitcointalk.org/index.php?topic=321228.0
A (very) simplified recap: coinswap is a protocol that improves privacy by trading one set of bitcoins for another, with escrow.

Adlai's thoughts/ideas: https://gist.github.com/adlai/976d308efdb2e886ecb9

In those posts, coinswaps involve only one pair of transactions, meaning transaction amounts could still be correlated to reduce the anonymity set. It shouldn't be too hard to create a protocol involving several transactions whose amounts add up to the desired coinswap amount, which would defeat amount correlation.

A major benefit to coinswaps is that they can be indistinguishable from regular bitcoin transactions. CoinSwaps can be implemented with 2-of-2 multisig (or 2-of-3 with a fake third pubkey) or, with normal p2pubkeyhash addresses using that cryptographic primitive that creates a 2-of-2 multisig contract with normal ECDSA keypairs (I think this is related to tree signatures) which could then make coinswaps use the regular bitcoin addresses. Note that more than 10% of bitcoins are held in p2sh addresses: http://p2sh.info/

[raedah]

Along the same lines of Coin Swap, is the concept of Transaction Cut-through. https://bitcointalk.org/index.php?topic=281848.0 Gmaxwells description uses nlocktime for people to join and supercede transactions that have already been broadcast. But without needing any bitcoin protocol modifications, we could implement this in a similar way by giving the full signed transaction to all parties involved, with instructions to delay the broadcasting of the transaction. Then all parties could wait around for additional parties to join in and expand the transaction for whatever decided interval. If that doesnt happen, or if the signing process gets disturbed, no big deal, because the earlier complete transaction can just be broadcast by any party.

[chris-belcher]

Transaction cutthrough is the issue #218

[chris-belcher]

Imagine if there were offers where the maker says their coinswap inputs did not come from a coinjoin. Then the large crowd of coinswaps would look almost entirely indistinguishable from regular bitcoin transactions. Privacy would be improved without the passive observer even realising, and all bitcoin transactions could be plausibly argued to actually be coinswaps.

In practice this could be done by the taker parsing the maker's inputs to check they don't look like they came from a JoinMarket coinjoin. The maker could send block hashes or block heights to help the taker find the inputs efficiently.

[chris-belcher]

The maker could send block hashes or block heights to help the taker find the inputs efficiently.

This will work for the taker running an SPV wallet where it can just request blocks it needs, however it won't work for a pruned full node. For that, the maker could optionally send the txhex along with the parts of the merkle tree. That should be enough for the taker to prove the maker's input is not a coinjoin.

edit: the pruned full node still has the UTXO set which contains transaction hashes, so just having the txhex is enough since it can be hashed and used to lookup in the UTXO set.

[chris-belcher]

that cryptographic primitive that creates a 2-of-2 multisig contract with normal ECDSA keypairs (I think this is related to tree signatures)

This is actually called ECDSA threshold signatures.
https://eprint.iacr.org/2016/451.pdf (pages 9 to 12)
https://eprint.iacr.org/2016/013.pdf

[chris-belcher]

https://github.com/roasbeef/go-go-gadget-paillier (paillier is required to implement threshold ECDSA)

<roasbeef> belcher: https://github.com/roasbeef/go-go-gadget-paillier  :rocket:
<belcher> ty roasbeef 
<roasbeef> belcher: ah gotcha, yeah I'm sure you can find some implemented in Python, ideally backed by Shoup's ultra-fast NTL library
<belcher> whats NTL ?
<belcher> roasbeef is your project really for threshold ECDSA? the readme talks about encryption
<roasbeef> belcher: ultra fast well-tested library for number theory-esque computations: http://www.shoup.net/ntl/ 
<roasbeef> couple it with gmp for extra awesomeness http://www.shoup.net/ntl/doc/tour-intro.html 
<freesatoshinakamurmo> @roasbeef: Ohh this looks like fun
<roasbeef> i've been using both within my master's project, the performance is _very impressive_
<roasbeef> iirc libsecp256k1 also optionally links against GMP to use it's super fast algo for modular inversion
<belcher> so threshold ECDSA requires these paillier homomorphic things
<roasbeef> this version does yeh
<roasbeef> Alice generates half the sig, encrypts it with paillier. Send it over to bob who generates a part of the sig, then encrypts it, and adds it to alice's half using the homomorphic encryption
<roasbeef> Alice gets this part, decrypts it, then can construct the final sig
<roasbeef> the sig is valid over a public key they generated in a distributed manner, they each have 1/2 of the priv key
<roasbeef> before sig generation they generate conjoint randomness ensuring both side have the same output with commitments
<belcher> ahh i see, and the homomorphic part is needed to do ECDSA operations on just parts of the key without revealing them
<roasbeef> yeh this scheme targets that only one side gets the final sig
<belcher> thats okay for what im hoping to do
<adam3us> roasbeef: this is why schnorr sigs... compact multisig is direct/simple without paillier gymnastics in a huge group to avoid overflow :slightly_smiling_face:
<belcher> coinswap with theshold ECDSA instead of bitcoin 2-of-2 multisig
<belcher> so then the addresses just look like normal p2pkh ones
<adam3us> i think technically it is multiparty ecdsa not threshold (or threshold with 2 of 2)
<roasbeef> adam3us: hehe yeah :slightly_smiling_face: this can hold us over till schnorr gets in as they can be done today without any modifications to bitcoin
<adam3us> yup
<roasbeef> yeah two-party ECDSA would be a better term
<belcher> ~90% of all bitcoins transactions are p2pkh so it would provide a big anonymity set :)
<adam3us> i read the paper and had read some paillier & damgard-jurik extension stuff before for other uses.  that paper yikes :slightly_smiling_face:
<roasbeef> you're referring to the princeton paper? yeah that scheme is waaay overly complex
<adam3us> the multiparty ecdsa yes.
<roasbeef> belcher and I are talking about a simpler scheme recently published on the iarc pre-print server
<adam3us> ah then maybe i didnt read that!
<roasbeef> the authors use it to construct ZKCP's using cut-and-choose rather than snarks
<roasbeef> http://eprint.iacr.org/2016/451.pdf 
<adam3us> ic.

[chris-belcher]

Some thoughts on DOS issues. One issue with the scheme from the original posts is that an attacker Alice could at no cost make Carol spend miner fees by getting Carol to repeatedly send coins to the 2of2 and getting them back with the timeout refund transaction.

One way around this could be to make Alice and Carol together create coinjoin refund transactions where Alice's UTXO pays for the miner fee + punishment fee, so it would cost Alice money to DOS like this. This kind of coinjoin refund could be done with SIGHASH_SINGLE|SIGHASH_ANYONECANPAY.

As a reminder: SIGHASH_SINGLE|SIGHASH_ANYONECANPAY signs this one input and its corresponding output. Allows anyone to add or remove other inputs.

Diagram of this coinjoin refund transaction, a coinswap is happening for 1 BTC, the miner fee is 0.01 BTC, the punishment fee that Alice would pay for locking up is 0.02btc

Input	Input Value	->	Output	Output value
UTXO in Alice+Carol 2of2, originally came from Carol	1 btc		Carol's address	1.02 btc
Alice's UTXO (signed with SINGLE/ANYONECANPAY)	0.5 btc		Alice's address	0.47 btc

The total miner fee for this transaction is 0.01btc as expected, Alice's UTXO has paid for that. Also 0.02btc has transferred from Alice's UTXO to Carol's address as the punishment fee.

EDIT: using this would allow Carol to broadcast the transaction and take Alice's money even if no refund transaction happens. Looks like Alice will have to see more of the transaction to make sure her fees only get paid when a refund has to happen, so the above SINGLE|ANYONECANPAY trick isn't good.

[chris-belcher]

My idea above isn't good because Alice can doublespend her UTXO before the timeout which will stop it being used to pay for Carol's miner fee. Alice will still pay a miner fee to do this but a lower one, because she'd be paying for fewer bytes in a block.

[AdamISZ]

Some thoughts on DOS issues. One issue with the scheme from the original posts is that an attacker Alice could at no cost make Carol spend miner fees by getting Carol to repeatedly send coins to the 2of2 and getting them back with the timeout refund transaction.

I am also very concerned about the DOS issue. When the outcome is back-out transactions that leak coinswap behaviour, and especially cost extra funds, it's a whole different ballgame than just "oh my coinjoin didn't go through and (in some cases) someone learnt about a utxo".

[AdamISZ]

Btw, re: 415.pdf, I had a little read through yesterday, and it's cool stuff, I can definitely see the appeal: p2pkh anonymity set via ECDSA-under-Paillier. The construction in the paper is quite a "big deal" though, lots of moving parts, even the use of Paillier itself, not to mention the whole cut and choose part.

[chris-belcher]

Regarding the above DOS problem. Read this post soon after reading this post

It's worth noting that the risk of DOS always exists, if only because the internet might go down and stop communication. My scheme above only shifts this risk from Carol to Alice, and using the punishment fee, aligns the incentives to intentional DOSing by Carol won't happen.

My reasoning for moving the DOS risk from Carol to Alice is that in joinmarket Carol is the maker and Alice the taker, so Carol is long-running and just sits there ready to be attacked.

My above solution didn't work because the Alice can spend her UTXO without permission from Carol.

One way to repair this is for Carol to require Alice to send bitcoins to a 2of2 address with Alice and Carol's pubkeys, then use that UTXO to create the coinjoin refund transaction with miner fee + punishment fee. And Alice can't doublespend this UTXO without Carol's permission. Then same as above if Alice DOSes then Carol can broadcast the transaction which gives her the punishment fee and pays for the miner fee. The downside is this would require Carol and Alice to set up yet another refund transaction.

Another way to repair is similar, instead of sending to a 2of2 multisig, Alice sends to an address with this script:

IF
    2 <Alice's pubkey> <Carol's pubkey> OP_CHECKMULTISIG
ELSE
    T0 OP_CHECKSEQUENCEVERIFY DROP
    <Alice's pubkey> CHECKSIG
ENDIF

Which would again mean Alice can't doublespend the UTXO because of the 2of2, except after a timeout T0 where she can spend it on her own.

This would save miner fees since fewer transactions are made. Note that these anti-DOS punishment scripts don't have to be private for coinswap to work so it's okay to have the redeemscript visible to everyone on the blockchain.

---

Edit: Here are diagrams similar that might help with understanding

Alice wants to do a coinswap of 1btc, each transaction costs 0.01btc in miner fees, Carol's punishment fee is 0.02btc. Alice also has a UTXO of value 0.5 btc to pay for any fees or punishment.

Alice asks Carol for a public key and creates a transaction, which creates a deposit UXTO.

Input	Input value	->	Output	Output value
Alice's UTXO	0.51 btc		Alice+Carol 2of2 Multisig OR timeout + Alice	0.5 btc

Once that has N confirmations, Alice and Carol create the 2of2 (step 0 in the diagram) and create this refund transaction.

Input	Input Value	->	Output	Output value
UTXO in Alice+Carol 2of2 coinswap escrow, originally came from Carol	1 btc		Carol's address	1.02 btc
Alice+Carol 2o2 Multisig OR csv + Alice	0.5 btc		Alice's address	0.47 btc

Alice can't doublespend the deposit UTXO to invalidate the refund transaction because it requires Carol's signature too. If Carol disappears or is evil then after the timeout Alice can get her money back (although it costs her miner fees). The deposit UTXO is separate from the rest of the coinswap and doesn't require any privacy, so it's okay to have the redeemscript visible to everyone on the blockchain.

[chris-belcher]

The above idea of still has the problem that Alice could be DOS'd by Carol. Someone who wanted to attack joinmarket could fill up the orderbook with their own evil Carols who send out the public keys for the deposit UTXO and then never sign, costing Alice miner fees each time. The DOSer could do this at no cost to themselves.

So here's one possible idea to remedy this.

Before sending bitcoins to create the deposit UTXO, Alice asks Carol for her earlier public keys. Alice will look on the blockchain to find the scripts Alice+Carol 2o2 Multisig OR csv + Alice and from there will know how many earlier coinswaps Carol successfully took part in. This costs (some) money to fake and would at least provide a rate-limiter on the evil Carol's DOS described above.

This is essentially using reputation gained from past deals. Using reputation always has a centralizing effect, we should avoid this by coding Alice to choose a random Carol 2 or 3 times without taking into account reputation, and then if Alice has been scammed those times choose a Carol based on reputation.

---

Now this coinswap scheme is becoming quite complicated, slow (must wait for confirmations), with a lesser user experience (Alice must have a UTXO separated from her other bitcoins to pay for the deposit) and requires a more complicated backup scheme (mnemonic seed isn't enough to backup, the other's pubkeys must also be saved). So it might be good to remind ourselves why coinswap is interesting:

• Coinswap works with today's bitcoin and cannot be blocked by any centralized miners

• A successful coinswap requires far less blockchain space than coinjoin to get the same privacy

• Coinswap with Paillier would be indistinguishable from regular bitcoin payments so would be great for fungibility because in theory any p2pkh address could be a coinswap.

[AdamISZ]

Wrt #335 (comment) , I see you refer to "step 0 in the diagram", but the original proposal is incorrect (afaik), and imo it's specifically necessary to remove the approach of having separate refund (timelocked) transactions, as per my gist + diagrams. (Although it's entirely likely there are other approaches).

(Additional note: gist is https://gist.github.com/AdamISZ/350bb4038834019eb0c06ec69446aec9 and I linked it in the original coinswap thread, but it's a bit of a necro, no replies yet).

W.r.t the general discussion in the two comments above, yes, I both agree with the potential advantages, and also agree (I think I said above) that DOS is an entirely different character of issue here. I'm inclined to having something like you're edging towards above (with "This is essentially using reputation gained from past deals." etc.), i.e. Carol as more of a server/persistent identity, and Alices as clients/customers. To fully solve the much more substantial DOS issues here (cf coinjoin which is much more fitting a "lazy, opportunistic" approach) may be possible with a more sophisticated refund approach, but it's already very complicated.