Coinswaps

Posted by: Adam Gibson | in Bitcoin | 1 year, 11 months ago |

Preamble

Firstly, I am a rubbish salesman, as well as a rubbish blog poster (first post in ~ 10 months!), mentioning this upfront - this is not a pitch for anything and indeed it may be an extremely long post about things that are utterly irrelevant (in the sense that most of what's discussed here is old, and has partly been superseded). But if you are curious about the tricks that can be played with Bitcoin's scripting, especially re: privacy enhancement, but don't have time to master it (join the club), this might prove of interest.

And humour aside, I think there is certainly still a case to be made that these protocols may have a place that they find use.

Summary

This post is an attempt to lead the curious but non-expert reader to the point of understanding what "trustless coin-swap" protocols in Bitcoin (and its variants) exist, how they work, how they differ, and what role they might serve. I've put in some links to relevant background so you can chase things up in more detail if you're interested. As the post progresses, things slowly get more technical so feel free to drop out once you've got the gist from the first 4-ish sections if you get bored.

Bear in mind this is not a complete science; it's still evolving. Also, there is no guarantee of absence of mistakes, I will endeavour to update if they're found.

I want to also note that this post will not discuss Lightning or Tumblebit (see previous post from last year) - both of which are much more complex protocols using something similar to what you see here as a building block. See the section "Aside - HTLC". This is about the low level, simpler idea of "atomically swapping coins".

Atomicity

The etymologists among you will already know that atom comes from Greek and means 'a' -not/un, 'tom' -cut, in other words, not cuttable or divisible. The idea of transactions being atomic in that sense - not being splittable into parts, "all or nothing", is well known in the world of databases. And Bitcoin, being a fancy (or just plain weird) kind of database, the same concept applies. When Alice pays Bob and Charlie in one transaction, they all know that either both Bob and Charlie get paid, or neither. A transaction confirms or it doesn't, it doesn't half-confirm. Quite apart from Alice, Bob or Charlie, the ledger itself needs to make sure money doesn't get created out of thin air, so atomicity is as fundamental as it gets (ask these guys).

When you have atomicity it makes life easier for customers, merchants, software developers ... everyone really. When you don't, life is harder. A good exampe of non-atomic transactions is buying a second hand mobile phone from a web store. You send them money, then they send you the phone. Maybe the phone didn't arrive, oops. Wasn't atomic, so trust and other messy symptoms get involved.

The not-even-a-swap swap; self-"mixing"

Coinbase might ban you for gambling. Send your coins to different addresses ...  but hmm, they're all your addresses. Can Coinbase tell you've done that? Here's a better question: why the heck are you using Coinbase? :)

What you really want is that the coins you give to Coinbase have no connection, on the blockchain, to those you received from inveterategamblers.com. You can't get that exact effect by sending coins to yourself. Although, you can get something close using Coinjoin, but it takes time and money to do it (see: Joinmarket).

The non-atomic swap, aka the mixer

You can give your coins to an online (usually hidden service on Tor) mixer service. They give you back different coins, that is to say, the coins you get back have a different history, not a direct connection to the ones you put in. Coinbase feel better now? Maybe, maybe not.

But the in- and out- phase are not atomic, as discussed. Coins may go in, coins may not go out. Even Bill O'Reilly can explain that.

Atomic swap without privacy features

I've led up to this rather slowly to make sure no one is lost by just jumping in. But this is the heart of the matter and it's the one thing you should make sure to take away, even if you get bored by all the technical stuff after it.

We can use a cryptographic commitment scheme to create atomicity that binds two, independent Bitcoin transactions, as long as we assume Bitcoin basically works (i.e. that transactions cannot be censored, or reversed)

The way to do this for Bitcoin is to use a hash function (say, Bitcoin's HASH160 (which is RIPEMD160 on top of SHA256). Suppose Alice and Bob want to create this atomicity binding two transactions, one created by each. The way to do it is to have one of them - say Alice - make up a random number, \(x\) and hash it, say \(H(x)\). We'll make \(x=\)deadbeef, although the real one needs to be properly random. Then make the scripts on the outputs of the transactions look like:

HASH160 9ecd593e655360e068c597e157651bef911dc597 EQUALVERIFY alicepubkey CHECKSIG

(Alice pays 1BTC into a P2SH address for the above script)

HASH160 9ecd593e655360e068c597e157651bef911dc597 EQUALVERIFY bobpubkey CHECKSIG

(Bob pays 1BTC into a P2SH address for the above script)

This is deliberately oversimplified for now - don't do it!. In English, I hope you can see that this basically means "you can claim these coins ONLY if you can give me an \(x\) such that its hash equals 9ecd..97 and you make a valid signature for the pubkey" (the "make valid signature" part is just the same as a normal transaction; you have to sign it to authorise it; the hash value part is an extra requirement you have to provide).

So in that environment:

What makes the two transactions atomic is that if Alice ever spends her output (claims her coins), she has to PUBLISH \(x\) on the blockchain, which perforce gives Bob the information he needs to spend his coins!

Who said Bitcoin was not for publishing data? ;) So, that's the basic idea. From now on, we go into details:

First, and hence the title of this section, notice that actually publishing transactions spending from scripts like that unambiguously connects the two transactions on the blockchain for anyone scanning/reading it. So a protocol that simply publishes them is not achieving any privacy gain in a meaningful sense; but then, as we shall see, this protocol might not be mainly about privacy. Let's flesh out the protocol.

It's generally accepted that the origin of concept of "atomic swaps" is in this TierNolan post. Unfortunately the thread is a bit of a difficult read, and various alternatives are proposed - the main idea is there but it isn't clear, plus the analysis was done before CLTV/CSV existed. Fortunately Nicolas Dorier recently boiled it down and showed what I believe to be the simplest way to do it on github for me/us. I'll reproduce here:

                                                                                                               

Alice chooses random number \(x\). Makes hash \(H(x)\). Gives Bob \(H(x)\).

  • Alice pays 1 coin to this script (wrapped into a P2SH address, of course), redeemscript1:
IF HASH160 H(x) EQV bobpubkey CHECKSIG ELSE 1000 CHECKLOCKTIMEVERIFY DROP alicepubkey CHECKSIG ENDIF

(In English this, and the next, script pay to "Either one pubkey if you can provide the hash preimage (\(x\)) or the other pubkey after the timeout block". "EQV" is short for OP_EQUALVERIFY . For the timeout part, see bip65 for details on CHECKLOCKTIMEVERIFY. And note there is also this: CHECKSEQUENCEVERIFY.)

  • Alice waits for that transaction to confirm, then tells Bob about it and waits for his side.
  • And Bob pays 1 coin to redeemscript2:
IF HASH160 H(x) EQV alicepubkey CHECKSIG ELSE 950 CHECKLOCKTIMEVERIFY DROP bobpubkey CHECKSIG ENDIF
  • and waits for it to confirm, and tells Alice about it. Now, Alice can spend out of Bob's output (the second one above), because she already knows \(x\).
  • Bob is monitoring that output of course, so when it gets spent he looks at the scriptSig and will see:
alicesignature x 1 redeemscript1
  • (the '1' here can be used to choose the "IF" branch instead of the "ELSE"; there's a better way of doing this, but ignore that for now) ... from which he extracts x, then simply does the same thing to redeem 1 coin from the output Alice created:
bobsignature x 1 redeemscript2

If Alice or Bob don't make those payments and instead back out after blocks 1000/950 respectively, then the other side can likewise back out after that time, getting back their coins.

                                                                                                                                   

An essential part of the logic here is that Bob can spend his timelock backout before Alice (see 950 vs 1000). And if Alice doesn't show the secret to him he should spend using the timelock before Alice's timelock (i.e. between 950 and 1000) to be safe. It's a bit confusing at first, but you can see this as the counterpoint to the fact that Alice has the secret before Bob; so she initiates any spend via the secret branches; so if the first block Bob could spend out of his timeout were later than Alice, Alice could steal both the coins (one via secret, one via timeout) in that intervening period (he'd have no chance winning a race by reading the secret off the blockchain; she'd have sent both out simultaneously).

Now, notice that since the two transaction paths are not connected, there's no reason that they even have to be on the same blockchain. Both blockchains have to support verification of the hash function and prevention of spending before a certain time/block. To keep the assessment simple, just note that it can be done on LTC and BTC (as Nicolas mentioned in his summary).

And indeed this is the obvious application of this protocol: there isn't much point creating disconnected histories on one blockchain (or is there?) if you both use the same secret value \(x\) since that unambiguously links them (\(x\) will perforce be a high-entropy random number and thus completely unique to that tx pair). But being able to swap, say, my BTC for your LTC without either of us trusting each other at all is quite a significant thing to be able to do (in fact, I still remember that the first time I was shown CoinSwap (see next section), apart from being quite bewildered, the only thing I did immediately understand was that this could be done across two different blockchains!).

Aside - the HTLC

Before going on to discuss the privacy enhanced variant, let's observe that the special scriptPubkey, or "redeeming condition", that we brought in in the last section - the "IF HASH THEN THIS PUBKEY SIGNS ELSE AFTER BLOCK N, THIS OTHER PUBKEY SIGNS" to put it crudely, has become known, at least informally, as the "Hashed Timelock Contract" or HTLC; at least, according to this link, although I get the impression the exact definition may change with who you talk to, and the term seems to have originated with the development of the Lightning protocol (please correct that if I'm wrong!). What's probably more important is this - Lightning is not about swapping coins but rather (partly) about routing them through payment channels with multiple hops. The idea of secret-reveal (hash preimage) is there extended - instead of just 2 parties having both transactions dependent on a single secret \(x\), you can thus have a whole chain of them. This can be thought of as spreading the atomicity not just over two transactions, but several. I won't say more here ... this is a huge topic; perhaps this idea might whet your appetite.

Coinswap - with privacy

Back to swapping coins.

Greg Maxwell in 2013 proposed Coinswap, which is different to the "Atomic Cross Chain Swap" as described above, but based on the same core idea of publication-of-secret-enforces-atomicity. As you'll see from the "Motivation", the main difference is that it proposes to actually create extra privacy/fungibility, basically by not publishing the hashed-secret scripts similar to the above, but keeping them as a backout, and prefering to publish a non-secret-containing transaction. It was published before the advent of CHECKLOCKTIMEVERIFY or CHECKSEQUENCEVERIFY , and so used only the existing nLockTime feature in Bitcoin at the time. But also it had a flaw in it, at least as originally laid out (which I've explained here, for those interested). In attempting to modify it using CLTV, I ended up with a structure similar to the previous section, but with another layer.

Here is a diagram (taken from here); the participants are "Alice" and "Carol" (no Bob):

coinswapnewbasic

The left hand side is the coins funded by Alice; the right hand side is those funded by Carol.  The transactions at the bottom (TX2, TX3) play a similar role to the ones explained in detail in the previous section, and indeed, they have exactly the same redemption scripts (both "IF hash160 hashval EQV onepubkey checksig ELSE blocktime CLTV (drop) otherpubkey checksig ENDIF"), and just as for the "Atomic swap" design, the L0 must be after the L1, where L0 and L1 are the earliest block height each of Alice and Carol respectively can use that timelock branch to recover coins. The reason L0 must be after L1 is exactly as before.

But what's different here is that, if all goes well, TX2 and TX3 will never be broadcast on the blockchain. Instead, as long as both sides know they can broadcast them - which means both sides have to sign them in advance (they both sign both notice - because the inputs are from 2 of 2 addresses under their joint control), they can choose instead to broadcast TX4 and TX5 as replacements; they still get the same amount of coins, but these transactions have no common \(x\) value, and no custom redeem scripts, so in principle (we'll come to this) they can look like any other p2sh spending transaction on the blockchain, i.e. a snooper may not be able to see either (a) that they are transactions of "coinswap" type or (b) that the two branches are in any way connected.

It sounds nice having this extra layer, but it makes analysis much more tricky. The first tricky thing is that you must completely sign the backout transactions TX2 and TX3 before you even broadcast the funding transactions TX0,1. This is because, if you just broadcast TX0 immediately, you have locked your funds into a 2 of 2 address with your counterparty, and they are under no obligation to do anything at that point (or they could die or disappear etc.). This is clearly not riskless. Hence TX2/TX3 signing, completely, first. And whilst this is a very smart solution, it brings up a major issue (see next section).

There's a lot of detail that can't be covered here. If you happen to be interested please do some review of the material in the documentation folder in my CoinSwapCS repo. For example, there is an attempt to iterate all backout cases for each side. However, see the last two sections of this post first.

Here's an example of two transactions representing two sides backing out via TX2 and TX3 (an example of a bunch of tests I've been doing on testnet): https://www.blocktrail.com/tBTC/tx/ec432451317b03064cfcf3ce5c26a2e71f30f8ae83a6f6f63f7b1ba0c4739dc8?txinIdx=0 and https://www.blocktrail.com/tBTC/tx/c14c14fa37a57ba3ddf716fb8d960ac3ccdb9bc049b744002efed2c771454664 ; these are links directly to the final transactions that redeem the outputs of TX2 and TX3; you can trace back and see TX0,1 and TX2,3 and notice that the amounts are a bit more complicated than you expect, due to the fees arrangements outlined in the docs. But in any case you can see the redeem scripts basically follow the logic above - you can see the secret value \(x\) (it's 14 bytes) on both sides, and you also see a little extra feature around OP_DEPTH.

Advantages

This document is trying to very briefly survey the ideas, because I think they might be important, rather than advertise any one as particularly good, but at least somewhere here I should record why CoinSwap as described above might be interesting: basically it's about anonymity set, in other words, the size of the crowd you can hide in. IF (big if!) a protocol like that can hide in all of the p2sh users by only spending coins from 2 of 2 or 2 of 3, it provides something very much not provided by things like coinjoin.

The other advantage is transaction size. The level of fungibility achieved per byte on the blockchain should be high, although it's difficult to quantify.

But, these advantages do not obtain if (a) you are forced into backout transactions and/or (b) there is trivial correlation on amount, or time such that an observer can easily re-link the two paths.

Finally, an independent advantage to the others - certainly if comparing with Coinjoin - is that this, like the previous non-private version, is entirely possible to do between different blockchains, albeit the complexity disadvantage of making it private carries over there too.

Malleability rears its head

For the CoinSwap (privacy) design mentioned above, a nasty issue arises in the preparation of the backouts you don't intend to spend (if the other side cooperates). To create them you must give the txid of your initial spending transaction (in the diagrams, TX0 and TX1) to your counterparty; that's part of the transaction template; and ask them to sign. If after you do this, you broadcast say TX0, but then your counterparty is malicious (or a miner is) and TX0 is malleated to a different txid, your backout transaction has become useless; it's got a signature on an input that doesn't, and can't exist.

What kind of malleability are we talking about here? A miner can push a high-S signature onto the chain; these are non-standard but valid (post BIP66 activation). But see BIP62 for some examples of other ways malleability can be achieved via the exact construction of the "scriptSig" (technical name for the data provided by the spender to redeem the coins; for normal addresses it's just (ecdsa signature, ecdsa pubkey), but it can have other things in it). One example is adding opcodes like OP_NOP8 which are there for future upgrades and literally just do nothing to the script. But their presence as a single extra byte completely changes the txid of the transaction (remember that's a key property of hash functions). And again BIP62 shows us there are several possible sources of this kind of malleability.

Things *could* still go fine if such a malleation occurs by a 3rd party, if your counterparty cooperates; but they could also hold you up and e.g. demand half your coins (worst case scenario, but .. ouch! that's not what we're here for...).

BIP141 Segwit solves this problem, of course, because its specific purpose is to remove txid malleability. In the absence of segwit, there are ideas about how one can get round this partially by means of arranging it so that no one *knows* which TX being broadcast is actually your TX0, so it would take huge resources to deliberately attack you. But these ideas are a bit fragile, if still somewhat interesting.

Also note that no such malleability issue can arise with the much simpler "atomic swap" idea that was discussed first, because there is no separate backout path that has to be signed in advance to be safe.

Another privacy tweak appears impossible for now

One thing that would be cool is to take the first of the two above versions (the "Atomic Swap") but somehow tweak it so that the secret values \(x\) appearing in the two broadcast spends were different. But they'd have to still be inextricably linked in that: when Alice spends with \(x\), Bob knows he can spend with \(y\), even though to an outside observer \(x\) and \(y\) were completely random and unrelated. This would at least extend the anonymity set to everyone doing such swaps, instead of creating an immediate link. Suppose that our hash function \(H\) obeyed  \(H(a+b) = H(a) + H(b)\); then Alice could privately share \(b\) with Bob, along with \(H(a)\), and Bob's transaction could output to \(H(a)+H(b)\) without him knowing \(a\) in advance (as previously he did not know \(x\)).Then when Alice paid to her output, exposing \(a\), he can add \(a+b\) to find the necessary secret to redeem his output. But on the blockchain the secrets shown are \(a\) on one side, and \(a+b\) on the other, which have no publically evident connection (remember \(b\) was transmitted privately).

Unfortunately hash functions don't behave like that. Elliptic curve points do; \(aG + bG = (a+b)G\) and so the reader can easily see that the above mechanism would work fine if we replaced \(H\) with the operation of elliptic curve point scalar multiplication, i.e. the function that converts a private key to a public one. But this is no good for Bitcoin Script, because EC operations like that are not available within it. So no dice for now, although it could be the basis for interesting ideas in future. By the way I was informed (by Andrew Poelstra) that this exact line of thought has been gone through somewhere on the Lightning mailing list, although I haven't chased up the link.

Conclusions

  • These are pretty old concepts (2012-2014); but they're not easy to implement or use, which probably explains their lack of use
  • The core concept (see "HTLC") continues to be very interesting, powerful and makes up a part of the more modern/complex/potentially powerful ideas like Lightning/Tumblebit
  • There is still a case to be made for possible usability of both the Atomic Cross Chain Swap (a very simple protocol that allows trustless exchange across blockchains) and the CoinSwap (more complex but potentially adding fungibility) either on same chain Bitcoin or across chains.
  • An advantage of Coinswap over Coinjoin is a potentially bigger anonymity set (a lot more could be said)
  • The privacy focused Coinswap has a very serious malleability problem without Segwit (there's a complex and somewhat fragile, partial solution)

Congratulations (commiserations?) if you got this far. If you feel so inclined have chat with me on freenode (user waxwing) about all this weird stuff (or any bitcoin type place, really). I would reenable comments but I'd need captchas first, sorry (bots!).

Current rating: 5