Sunday, October 18, 2015

Atomic Cross Chain Transfer, an Overview


Atomic cross chain transfers (or atomic cross chain trading, from here on referred to as ACCT for short) , makes it possible to trustlessly trade between two cryptocurrencies existing on different blockchains. This means that neither of the two parties involved in the trade is at risk of their funds being stolen. The trade either completes with both parties getting the coins that they agreed upon, or the trade fails and both parties get their coins back. The trustless nature of ACCT will eventually have a huge impact on the way cryptocurrencies are traded, as it allows complete strangers with no prior reputation to trade with each other without a third party intermediary.

The first working theoretical implementation of ACCT was first described by Noel Tiernan in this bitcointalk.org thread, and the basic details of the algorithm is described here. In this document, we are specifically interested in discussing ACCT for Bitcoin and Bitcoin derived cryptocurrencies. Bitcoin derived cryptocurrencies are forked off of the Bitcoin Core source code, and examples include Dogecoin, DASH, and Litecoin. Below are the covered topics in this document:

1. ACCT using refund transactions
2. Alternative implementation of ACCT using refund transactions
3. Vulnerabilities of ACCT using refund transactions
4. ACCT using Check Lock Time Verify

1. ACCT using refund transactions

ACCT can be currently implemented by constructing refund transactions. We discuss in detail here one implementation of this method. This implementation is based on Ross Nicoll’s CATE project.

Variables and Terms

AlphaCoin - a bitcoin derived cryptocurrency
BetaCoin - another bitcoin derived cryptocurrency
Initiator – one party of the trade, looking to sell Alpha Coin for Beta Coin.
Responder – the second party involved in the trade, looking to sell Beta Coin for Alpha Coin
X – secret number created by initiator
H(X) – hash of secret X
Privkey i / Pubkey i - private public key pairs belonging to initiator
Privkey r / Pubkey r - private public key pairs belonging to responder
TxAb - initiator's bail in transaction, for the Alpha Coin network
TxAr - initiator's refund transaction, for the Alpha Coin network
TxAp – responder's pay out transaction, for the Alpha Coin network
TxBb - responder's bail in transaction, for the Beta Coin network
TxBr – responder's refund transaction, for the Beta Coin network
TxBp – initiators pay out transaction, for the Beta Coin network
T2 - time till initiator can obtain refund
T1 - time till responder can obtain refund , where T1 < T2

Steps

Step 1.
Initiator creates secret X, and hashes it to create H(X). Initiator also creates two public private key pairs (pubkey i1,i2 / privkey i1,i2). Responder creates two public private key pairs (pubkey r1,r2 / privkey r1,r2).

Step 2.
Initiator shares H(X) and pubkey i’s with responder. Responder shares pubkey r’s with initiator.

Step 3
Initiator creates and keeps secret TxAb, the bail in transaction. The bail in transaction moves initiator's funds into an unspent that can be redeemed with knowledge of secret X and a signature from privkey r1, or it can be redeemed with signature from both privkey i1 and privkey r1.

Step 4.
Responder creates and keeps secret TxBb, his bail in transaction. The bail in transaction moves responder's funds into an unspent that can be redeemed with knowledge of secret X and a signature from privkey i2 or it can be redeemed with signature from privkey i2 and privkey r2.

Step 5.
Initiator creates TxAr, his refund transaction that spends TxAb with signature from privkey i1 and privkey r1 to an address controlled by initiator. TxAr has nLocktime set to some time in the future T2 so is not valid until that time passes. TxAr is sent to responder and the responder sends back TxAr signed with privkey r1. Initiator signs the transaction with privkey i1.

Step 6.
Responder creates refund TxBr, his refund transaction that spends TxBb with signature from privkey i2 and privkey r2. The refund TxBr has nlocktime set to some time in the future T1 (where T2 > T1 ) so is not valid until that time passes. TxBr is sent to initiator and the initiator sends back TxBr signed with privkey i2. Responder signs the transaction with privkey r2.

Step 7.
TxAb is broadcast by initiator.

Step 8.
After confirming TxAb, responder broadcasts TxBb.

Step 9.
Initiator creates payout transaction TxBp that spends TxBb by revealing secret and using privkey i2. Since the secret is now revealed to the responder, the responder creates payout transaciton TxAp that spends TxAb by using the revealed secret X and privkey r1.

Notes

If initiator fails to broadcast TxAb in step 7, the exchange has failed and no further steps need to be taken by the responder.

If responder fails to broadcast TxBb in step 8, initiator can redeem TxAb in time T2 using refund transaction TxAr.

At step 9, if initiator fails to get pay out from TxBb before time T1, responder can get refund with TxBr. If responder fails to get pay out from TxAb after time T2 has passed. Initiator can get refund with TxAr

Scripts

TxAb’s output should be a p2sh transaction to the hash of the serialized script outlined below. The reason we use a p2sh transaction is that since Bitcoin Core 10.0, any p2sh transactions are considered standard and will be relayed by 10.0 nodes.

OP_DUP OP_HASH160 [Hash160(pubkey r1)] OP_EQUALVERIFY
OP_CHECKSIGVERIFY
OP_IF
OP_DUP OP_HASH160 [Hash160(pubkey i1)] OP_EQUALVERIFY
OP_CHECKSIG
OP_ELSE
OP_HASH256 [H(x)] OP_EQUAL
OP_ENDIF

Refund transaction TxAr’s script sig will look like below:

[signature from privkey i1] [pubkey i1] 1 [signature from privkey r1] [pubkey r1]
{serialized script}

Pay out transaction TxAp’s script sig will look like below:

[X] 0 [signature from privkey r1] [pubkey r1] {serialized script}

TxBb, TxBr, and TxBp is symmetrical and replaces key pair r1 with i2 and key pair i1 with r2.

2. Alternative Implementation of ACCT using refund transactions

Noel Tiernan describes an alternative implementation, which is also implemented by Matthew Bell in project Mercury. The main advantage of this implementation was that before Bitcoin Core release 10.0.0, not all p2sh scripts were considered standard and were not relayed by nodes. This implementation required the use of only one non standard transaction in the entire ACCT protocol, as opposed to two. Thus this implementation was more likely to be propagated across the entire network.

However with the introduction of Bitcoin Core 10.0.0 on February 2015, rules for standard transactions were relaxed so that all P2SH redemption scripts are considered “standard” and are relayed by the nodes. Thus this alternative implementation no longer has this advantage. Litecoin Core has adapted the 10.0.0 changes since June 2015 with version 10.2.2, and Dogecoin Core as of September 2015 is in the process of adapting the 10.0.0 changes with its beta release of 1.10.

3. Vulnerabilities of ACCT using refund transactions

Extortion using Transaction Malleability

TxAb and TxBb could be mutated , thus making their respectable refund transactions TxAr and TxBr invalid. If refund transaction is invalid, the funds could be forever locked unless you obtain cooperation from your counterparty to resign the refund transaction. A possible attack that can be performed either by the initiator or the responder is to mutate the counterparty's funding transaction, making their refund transaction invalid. Now the attacker is in position to extort money from the counterparty.

There has been progress on several fronts to alleviate the transaction malleability problem in Bitcoin such as strict DER encoding, lowS signature enforcement, and stricter definitions for standard transactions limits mutated transaction from being relayed. However, relay rules do not prevent miners from mining mutated transactions, and do not change the behavior of old clients or clients that do not adhere to the same relay rules as the core protocol.

It is unlikely that the malleability problem will be solved in the near future. BIP 62 outlines all known malleability sources, but it is by no means an exhaustive list, since it is based on heuristics. New malleability sources could be discovered, and could also be created by changes in the protocol. Normalized Transaction ID's have been proposed as a solution, but this proposal is far from obtaining consensus from Core devs and being implemented into Bitcoin. This vulnerability makes it dangerous for ACCT using refund transactions to be deployed in production systems.


Fund Lock Attack

A trivial attack to perform is for the responder to never follow through the bail in transaction broadcast on step 8. This will lock up the initiator’s fund for time T2 without any losses by the responder. The initiator can perform a similar attack although not without locking up his own funds. He can refuse to perform his pay out transaction in step 9, but in this case it will keep responder’s fund locked up for time T1 and keep his own funds locked up for time T2.


Payout Failure

Responder could fail to obtain payout from TxAb before time T2 as in step 8. This could happen for many reasons such as the responder losing private key r, the responder losing access to the internet (DDOS, network failure), or his transaction does not make it into the blockchain (blacklisted by miner, congestion in the blockchain, failure to pay sufficient tx fee). In this case, the initiator would be able to have access to both his own fund and the responder's fund, effectively allowing him to steal responder's funds.

Note that initiator does not face the same risk if he fails to redeem TxBb before time T1, as long as he does not reveal secret X. If initiator fails to redeem TxBb before time T1. Responder can use refund transaction TxBr to redeem TxBb , but responder has no access to TxAb. However, if initiator reveals secret X (for example, TxBp is broadcast onto the network but does not make it into any blocks before time T1), the responder would be able to have access to both his own fund and the initiator's fund.

Double Spend Attack

As with any cryptocurrency transactions involving two parties, there is an opportunity for a double spend attack. This can happen if the victim does not wait for sufficient confirmations , or an attacker has access to sufficient mining power.

If the initiator can convince the responder that TxAb occurred when in didn’t, and the responder publishes TxBb, the imitator can steal from the responder by spending TxBb using TxBp and than double spending the inputs of TxAb. Likewise, if the responder can convince the initiator that TxBb occurred when it didn’t, and the responder publishes TxBp, the responder can steal from the initiator by spending TxAb using TxAp and than double spending the inputs of TxBb.

4. ACCT using Check Lock Time Verify (CLTV)

OP_CHECKLOCKTIMEVERIFY is a new op code in the works that Bitcoin Core devs will be looking to deploy with a soft fork in the near future. It is described here in BIP 65. The op code allows us to create transactions that can be spent in different ways depending on the nLockTime of the spending transaction.

ACCT using CLTV is superior in that it does not have the transaction malleability issues of ACCT using refund transactions (it does however have the same other vulnerabilities discussed in the previous section). Additionally, all transaction signing occurs on the blockchain, and the trading parties only need to exchange the hashed secret and their public keys in order for the trade to take place.

Steps

Step1.
Initiator creates secret X, and hashes it to create H(X). Initiator also creates public private key pair (pubkey i1,i2 / privkey i2,i2). Responder creates public private key pair (pubkey r1,r2 / privkey r1,r2).

Step 2.
Initiator shares H(X) and pubkey i2 with responder. Responder shares pubkey r1 with intiator.

Step 3.
Initiator creates TxAb. TxAb can be redeemed after time T2 with privkey i1. At any time TxAb can redeemed with signature from privkey r1 and reveal of secret X. Initiator broadcasts TxAb onto the network.

Step 4.
Responder confirms TxAb. Responder creates TxBb. TxBb can be redeemed after T1 time with privkey r2. At any time TxBb can be redeemed with signature fom privkey i2 and reveal of secret X. Responder broadcasts TxBb onto the network.

Step 5.
Initiator creates TxBp which spends TxBb using privkey i2 and secret X. With the revealed secret, responder can create TxAp which spends TxAb with privkey r1 and secret X.

Notes

If initiator fails to broadcast TxAb in step 3, the exchange has failed and no steps need to be taken by the responder.

If responder fails to broadcast TxBb in step 4, initiator can create refund transaction TxAr which redeems TxAb after time T2 using privkey i1.

If initiator fails to spend TxBb on step 5 before time T1, responder can create refund transaction TxBr after time T1 using privkey r2. If responder fails to spend TxAb before time T2, initiator can use TxAr to get refund from TxAb.


Script


TxAb’s output should be a pay to script hash transaction to the hash of the serialized script outlined below.

OP_IF
[T2] CHECKLOCKTIMEVERIFY OP_DROP OP_DUP OP_HASH160 [Hash160(pubkey i1)]
OP_EQUALVERIFY OP_CHECKSIG

OP_ELSE
OP_DUP OP_HASH160 [Hash160(pubkey r1)] OP_EQUALVERIFY OP_CHECKSIGVERIFY OP_DUP
OP_HASH160 H(X) OP_EQUAL
OP_ENDIF

The refund transaction TxAr has nLockTime > T2 and the input script is

[signature from privkey i1] [pubkey i1] 1 {serialized script}

The payout transaction TxAp has nLockTime < T2 and the input script is

[x] [signature from privkey r1] [pubkey r1] 0 {serialized script}

TxBb, TxBr, and TxBp is symmetrical and replaces key pairs i1 with r2 and key pairs r1 with i2