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}