TierNolan has proposed two protocols for atomic cross-chain exchange. I have already introduced his first one and I was about to do almost the same also with the second one so that it would be possible to easily compare them. However, in the end I found out that this protocol isn’t atomic.

My original description of the protocol

Alice wants to exchange her ATC for some BTC and Bob wants to exchange his BTC for some ATC. They settle on a trade and send each other their public keys for this purpose. The protocol has two phases: transactions preparation and transactions propagation.

Alice

Alice starts. She generates a random number x, hashes it: H(x), and sends the hash to Bob. Now she creates three transactions: tx1, tx2, and tx3. The first one is for committing her coins into the exchange, the second one for claiming coins by the other party, and the last one is for refunding the coins in case of trade cancellation and is time-locked so it cannot be used until the timeout elapses. Scripts are as follows:

tx1: scriptPubKey
2 <pubkey A> <pubkey B> 2 OP_CHECKMULTISIG
tx2&tx3: scriptSig
0 <sig A> <sig B>
tx2: scriptPubKey
OP_HASH160 <H(x)> OP_EQUALVERIFY OP_DUP OP_HASH160 <H(pubkey B)> OP_EQUALVERIFY OP_CHECKSIG
tx3: scriptPubKey
OP_DUP OP_HASH160 <H(pubkey A)> OP_EQUALVERIFY OP_CHECKSIG

tx2 and tx3 have to be signed by both parties to be valid. Therefore Alice sends tx3 and half-signed tx2 to Bob. Bob signs both of them and returns tx3 to Alice.

Bob

Meanwhile Bob creates his three transactions: tx4, tx5, and tx6. Their purpose is analogical: the first one commits his coins into the exchange, the second one is for claiming coins by Alice, and the last one again for refunding the coins in case of cancelled trade.

tx4
Output 0 & its scriptPubKey

This output takes the full amount of coins.

2 <pubkey A> <pubkey B> 2 OP_CHECKMULTISIG
Output 1 & its scriptPubKey

This output is of zero value.

OP_HASH160 <H(x)> OP_EQUALVERIFY 2 <pubkey A> <pubkey B> 2 OP_CHECKMULTISIG
tx5

This transaction (allowing Alice to claim Bob’s coins) spends both outputs of tx4. Its output is a simple pay-to-pubkey-hash.

input 0 (tx4/0): scriptSig
0 <sig A> <sig B>
input 1 (tx4/1): scriptSig
0 <sig A> <sig B> x
scriptPubKey
OP_DUP OP_HASH160 <H(pubkey A)> OP_EQUALVERIFY OP_CHECKSIG
tx6

This refunding transaction spends only the first of the outputs of tx4. scriptSig is the same as in tx5. Output is also a pay-to-pubkey-hash.

scriptPubKey
OP_DUP OP_HASH160 <H(pubkey B)> OP_EQUALVERIFY OP_CHECKSIG

tx5 and tx6 have to be again signed by both parties to be valid. Therefore Bob sends tx6 and half-signed tx5 to Alice. Alice signs both of them and returns tx6 to Bob.

Protocol execution

Now, when all transactions are ready, they can be broadcast to the networks.

Coins commitments

Alice starts by broadcasting tx1. [Here is the point of lost atomicity.] When it gets deep enough into the blockchain, Bob broadcasts tx4.

Coins claims

When tx4 is deep enough in its blockchain, Alice claims its outputs with tx5. By that moment Bob finally knows the value of x so he broadcasts tx2.

As tx5 uses a standard script (e.g., pay-to-pubkey-hash) in its scriptPubKey, nothing special has to be done by Alice to redeem it. But tx2 outputs to a special script, which has to be redeemed by a transaction (tx7) with this scriptSig:

<sig B> <pubkey B> <x>

Trade cancellation

If the protocol was atomic, it could be stopped at any moment without any destructive effects, i.e., like this:

  1. In the first phase, nothing is broadcast so nothing has to be done.
  2. If Bob doesn’t broadcast tx4, Alice waits for a timeout and redeems her coins with tx3.
  3. If Alice doesn’t claim coins from tx4, Bob waits for a timeout and redeems his coins with tx6 (and Alice hers with tx3).
  4. When Alice claims Bob’s coins, it’s no more possible to revert the trade, but since then it can be finalised without any interaction between parties.

Why the protocol isn’t atomic

Because Bob holds tx2 fully signed since the first phase. As soon as tx1 gets into the blockchain, Bob can broadcast tx2. He can’t redeem it, because he doesn’t know the value of x, but he prevents Alice from refunding her coins via tx3, because the output of tx1 is already spent.

There seems to be one possible solution to this: tx1 should look very like tx4 (similarly for tx2-tx5 and tx3-tx6).

Summary

Although there is a fix, this protocol is too complicated and has even other issues anyway. For example in case of trade cancellation the protocol leaves one unspendable output (tx4/1) in the blockchain, therefore irreversibly contributing to UTXO bloating. (With the fix it’s even worse.) And it still requires non-standard transaction scripts. (And I’m not going to talk about some suboptimal scripts.)

Therefore, I wasn’t (and I am still not) going to use this protocol in Coincer or anyhow build a solution upon its scripts. Still, I wanted to make clear why it can’t be used so that nobody runs into problems by blindly using it, because in the original thread on bitcointalk this issue wasn’t mentioned (although it seems that TierNolan has already spotted it).