TierNolan has proposed two protocols for atomic cross-chain exchange. Today I’ll describe the first one—how it works and how it could be implemented (i.e., with real scripts).

Description

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.

Alice

Alice starts. She generates a random number x and hashes it: H(x). Now she creates two transactions: tx1 and tx2. The first one is for committing her coins into the exchange, while the latter 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 (scriptPubKey for tx1 and scriptSig for tx2) are as follows:

tx1
OP_IF
    2 <pubkey A> <pubkey B> 2 OP_CHECKMULTISIG
OP_ELSE
    <pubkey B> OP_CHECKSIGVERIFY OP_HASH160 <H(x)> OP_EQUAL
OP_ENDIF
tx2
0 <sig A> <sig B> OP_TRUE

tx2 has to be signed by both parties to be valid. Therefore Alice sends it to Bob to have it signed by him. When tx2 is returned, Alice broadcasts tx1 to the network.

Bob

Now Bob continues on the second blockchain by creating the same tx3 and tx4 transactions (with correct keys) and also has tx4 signed by Alice. It’s important that Bob’s tx3 has shorter timeout than tx2. When tx1 is deep enough in the blockchain, he broadcasts tx3.

Redeeming the other party’s coins

When tx3 has enough confirmations, Alice claims its coins with the following scriptSig:

<x> <sig A> OP_FALSE

By this transaction she reveals the value of x, therefore Bob can immediately claim coins in the other blockchain as well.

Trade cancellation

The protocol can be stopped at any moment without any destructive effects.

  1. Before broadcasting tx1 nothing is needed to be done.
  2. If Bob refuses to continue, Alice waits for a timeout and redeems her coins with tx2.
  3. Cancelling after tx3 being in the blockchain is done in a similar way: Bob uses tx4 to redeem his coins and Alice hers with tx2.
  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.

Protocol formalisation

Let’s have two (alt)coins: ATC and BTC. Suppose Alice has an arbitrary amount of ATC and wants to exchange them for BTC and vice versa for Bob (has BTC, wants ATC). For now, transaction fees are neglected.

  1. Alice and Bob exchange their public keys.
  2. Alice generates a cryptographically secure random number x.
  3. Alice creates tx1 committing her ATC with a scriptPubKey of the form as mentioned above.
  4. Alice creates tx2 refunding all ATC from tx1 with a scriptSig of the form as mentioned above. The transaction has a time-lock set to a safely high value.
  5. Alice transmits tx2 to Bob to have it signed by him.
  6. Bob signs and returns tx2.
  7. Alice broadcasts tx1.
  8. Bob creates tx3 committing his BTC with a scriptPubKey as in tx1, but with <pubkey A> and <pubkey B> replaced.
  9. Bob creates tx4 refunding all BTC from tx3 with a scriptSig as in tx2, but with <pubkey A> and <pubkey B> replaced. The transaction has a time-lock set to a safely high value, but at the same time safely lower than in tx2.
  10. Bob transmits tx4 to Alice to have it signed by her.
  11. Alice signs and returns tx4.
  12. When tx1 is placed in the blockchain and has a safe number of confirmations, Bob broadcasts tx3.
  13. When tx3 is placed in the blockchain and has a safe number of confirmations, Alice creates and broadcasts tx5 that redeems all BTC from tx3 with a scriptSig of form <x> <sig A> OP_FALSE.
  14. Bob uses value of x from tx5 to create and broadcast tx6 that redeems all ATC from tx1 with a scriptSig as in tx5, but with <sig A> replaced by <sig B>.

Wanted properties are safety and liveness:

Safety
The protocol never deadlocks and neither party can steal the other party’s coins.
Liveness
There always eventually exists a step each party can do either to make progress within the protocol or to revert its effects.

Proof

Liveness

We want to disprove that one of the parties can perform such an action that the other party cannot perform any action in a finite time. Let’s do an analysis for each step of the protocol.

  1.  
    1. If Alice or Bob refuses to send her public key or she sends an invalid value, the other party can trivially terminate the protocol.
    2. If Alice sends such a public key to which she doesn’t possess a corresponding private key, the protocol stops itself after the step no. 10. In such a case Bob doesn’t continue and trivially terminates the protocol.
    3. If Bob sends such a public key to which he doesn’t possess a corresponding private key, the protocol stops itself after the step no. 5. In such a case Alice doesn’t continue and trivially terminates the protocol.
  2. If Alice doesn’t generate cryptographically secure random number, then the protocol:
    1. stops—Bob can trivially terminate it;
    2. continues, but Alice may lose her coins*.
  3.  
    1. If Alice doesn’t create tx1, Bob trivially terminates the protocol.
    2. If Alice creates other than prescribed transaction, Bob trivially terminates the protocol after the step no. 7.
  4. If Alice doesn’t create tx2 that satisfies given requirements, Bob doesn’t sign it in the step no. 6 and trivially terminates the protocol.
  5. If Alice doesn’t send tx2 to Bob, he can trivially terminate the protocol. If she sends to him anything else than tx2, he trivially terminates the protocol immediately.
  6. If Bob doesn’t sign tx2, Alice trivially terminates the protocol.
  7. If Alice doesn’t broadcast tx1 or if she broadcasts different (conflicting) transaction, Bob trivially terminates the protocol.
  8.  
    1. If Bob doesn’t create tx3, Alice waits for timeout of tx2 and terminates the protocol by broadcasting it.
    2. If Bob creates other than prescribed transaction, Alice terminates the protocol the same way after the step no. 12.
  9. If Bob doesn’t create tx4 that satisfies given requirements, Alice doesn’t sign it in the step no. 11, waits for timeout of tx2 and terminates the protocol by broadcasting it.
  10. If Bob doesn’t send tx4 to Alice or if he sends to her anything else than tx4, she waits for timeout of tx2 and terminates the protocol by broadcasting it.
  11. If Alice doesn’t sign tx4, Bob trivially terminates the protocol.
  12. If Bob doesn’t broadcast tx3 or if he broadcasts different (conflicting) transaction, Alice waits for timeout of tx2 and terminates the protocol by broadcasting it.
  13. If Alice doesn’t claim Bob’s coins before elapsing the timeout of tx4, Bob immediately terminates the protocol by broadcasting it.
  14. If Bob doesn’t claim Alice’s coins as soon as possible, he might lose the coins when timeout of tx2 elapses*.

Cases marked with an asterisk are violating the protocol, but don’t harm the other party, therefore they are not treated as breaking our requirements.

Safety

Protocol is deadlock-free by the previous proof. I’ll show that it’s not possible to wrongfully acquire other party’s coins.

Coins can be claimed only from transactions tx1 and tx3. Therefore, I’ll restate the scriptPubKey form of these transactions:

OP_IF
    2 <pubkey A> <pubkey B> 2 OP_CHECKMULTISIG
OP_ELSE
    <pubkey B> OP_CHECKSIGVERIFY OP_HASH160 <H(x)> OP_EQUAL
OP_ENDIF

This scriptPubKey can be claimed in a transaction by providing such a scriptSig that makes it evaluate as valid. The script consists of two branches. The first (if-branch) is providing a way for refunding the originating user in case of a failed trade. The second (else-branch) is for the other party to claim coins from exchange.

Refund transactions (tx2 and tx4) are signed by the other party only in case of satisfying protocol requirements, particularly the time-lock. Therefore it’s not possible to misuse the first script branch or related transactions.

Claiming transactions (tx5 and tx6) can only come in this order, because only one party initially knows the value of x. When Alice (as the first party that generated x) broadcasts tx5, she has a guarantee that Bob can’t attempt to race condition it with any colliding transaction, because not only the value of x is needed for spending the else branch, but also Alice’s signature. There isn’t any other way for satisfying the else branch.

Analogy also holds for tx6—Bob’s signature plus the x are required for spending the else branch here. Alice is limited by tx2’s time-lock.

How to break the protocol and acquire all coins

If both sides follow the protocol, they can’t get into a situation where one of the trading parties end up with her and the second party’s coins as was shown above. Moreover, only Bob may lose his coins, because coins from Alice can be transferred only if the secret value is given. And the secret is revealed when Alice claims coins from Bob. But if Bob doesn’t claim coins from Alice after this action, Alice can refund them when the lock of her refund transaction expires.

Another possibility comes from generating of x. If it is possible to guess/compute it, it’s easy for Bob to claim Alice’s coins.

Summary

This protocol is very straightforward and minimises overall overhead. Therefore, if it didn’t use non-standard transactions, it would be the candidate number one for use in Coincer.

Implementation

To illustrate the protocol in a practical way, I’m attaching my Ruby script that constructs 3 transactions—tx1, tx2, and tx6—in Bitcoin. The other three transactions are technically identical.

#!/usr/bin/env ruby

require 'rubygems'
require 'bitcoin'
require 'digest'
require 'securerandom'

Bitcoin.network = :testnet3

# generate x, key of A and B
x = SecureRandom.random_bytes(16)
key_a = Bitcoin::generate_key
key_b = Bitcoin::generate_key

key_a = Bitcoin::Key.new key_a[0], key_a[1]
pubkey_a = key_a.pub_compressed
key_a = Bitcoin.open_key(key_a.priv)

key_b = Bitcoin::Key.new key_b[0], key_b[1]
pubkey_b = key_b.pub_compressed
key_b = Bitcoin.open_key(key_b.priv)

include Bitcoin::Builder

# fetch the tx from a file in binary form and parse it
prev_tx = Bitcoin::P::Tx.from_file('tx.bin')

# the number of the output we want to use
prev_out_index = 0

# the key needed to sign an input that spends the previous output
key = Bitcoin::Key.from_base58('cSQHwFgXS6D4w1b9FykfRt4NwXjoYuJfWa8HytzmizPZRse1ZNXV')
pubkey = key.pub
key = Bitcoin.open_key(key.priv)

## TX1
tx1 = Bitcoin::P::Tx.new

# add the input
tx1.add_in Bitcoin::P::TxIn.new(prev_tx.binary_hash, prev_out_index, 0)

# add a change output
tx1.add_out Bitcoin::P::TxOut.value_to_address(49_0000_0000, 'muxV42VtkHAEmgxVSzTXn9sBGprKZDk7fq')

# add an output locking coins into a trade
tx1.add_out Bitcoin::P::TxOut.new(1_0000_0000, Bitcoin::Script.binary_from_string("OP_IF 2 #{pubkey_a} #{pubkey_b} 2 OP_CHECKMULTISIG OP_ELSE #{pubkey_b} OP_CHECKSIGVERIFY OP_HASH160 #{Digest::RMD160.hexdigest(Digest::SHA256.digest(x))} OP_EQUAL OP_ENDIF"))

# sign
sig = Bitcoin.sign_data(key, tx1.signature_hash_for_input(0, prev_tx))
tx1.in[0].script_sig = Bitcoin::Script.to_signature_pubkey_script(sig, [pubkey].pack("H*"))

# ready to use
#puts tx1.to_payload.unpack('H*')[0]  # tx in hex
#puts tx1.to_json                     # parsed tx in json

## TX2
tx2 = Bitcoin::P::Tx.new

# add the input
tx2.add_in Bitcoin::P::TxIn.new(tx1.binary_hash, 1, 0)

# add an output
tx2.add_out Bitcoin::P::TxOut.value_to_address(1_0000_0000, 'muxV42VtkHAEmgxVSzTXn9sBGprKZDk7fq')

# lock the transaction for 24 hours into the future from now
tx2.lock_time = Time.now.to_i + 3600*24

# sign
sig_a = Bitcoin.sign_data(key_a, tx2.signature_hash_for_input(0, tx1))
sig_b = Bitcoin.sign_data(key_b, tx2.signature_hash_for_input(0, tx1))
tx2.in[0].script_sig = Bitcoin::Script.to_multisig_script_sig(sig_a, sig_b) + [Bitcoin::Script::OP_2].pack('C*') + [Bitcoin::Script::OP_TRUE].pack('C*')

# ready to use
#puts tx2.to_payload.unpack('H*')[0]  # tx in hex
#puts tx2.to_json                     # parsed tx in json

## TX6
tx6 = Bitcoin::P::Tx.new

# add the input
tx6.add_in Bitcoin::P::TxIn.new(tx1.binary_hash, 1, 0)

# add an output
tx6.add_out Bitcoin::P::TxOut.value_to_address(1_0000_0000, 'muxV42VtkHAEmgxVSzTXn9sBGprKZDk7fq')

# sign
sig = Bitcoin.sign_data(key_b, tx6.signature_hash_for_input(0, tx1))
buf = Bitcoin::Script::pack_pushdata(x.unpack('H*')[0].htb)
buf += Bitcoin::Script::pack_pushdata(sig + [Bitcoin::Script::SIGHASH_TYPE[:all]].pack("C"))
buf += [Bitcoin::Script::OP_FALSE].pack('C*')
tx6.in[0].script_sig = buf

# ready to use
#puts tx6.to_payload.unpack('H*')[0]  # tx in hex
#puts tx6.to_json                     # parsed tx in json

Script licence: Public Domain