Atomic Cross-Chain Exchange

Cryptocurrencies are great for decentralised payments. Once you have bitcoin you can pay arbitrary destinations without the need to trust in, or get the approval of, any third party.

But what about if you want to exchange your bitcoin for something else, say another cryptocurrency?

This normally means registering with a third party exchange service, and trusting that third party service not to lose your funds during the exchange. It's not ideal, and doesn't really fit with the whole decentralised thing!

It turns out that proper atomic exchange between two cryptocurrencies isn't fundamentally hard, as long as you have the right building blocks, and this is something that I think should then be standardised across different cryptocurrencies.

One true blockchain?

So I'm going to talk about cryptocurrency exchange mechanisms, but some might question the need for multiple cryptocurrencies in the first place.

For example, Bitcoin has been described as 'the TCP/IP of money', with an implication that any other functionality we need can be built on top of the Bitcoin protocol (and blockchain) just as the modern internet is built on top of TCP/IP, without the need for alternative cryptocurrency implementations or blockchains.

So I should state from the outset that I don't agree with this point of view.

I think that using separate blockchains can make things more robust, efficient, and scalable, and opens up the possibility for a lot of innovation that just couldn't happen with Bitcoin alone.

This is kind of related to whether or not you think 'proof of stake' can be made to work, but that's a discussion for another time.

In any case, my point of view is that a world with multiple cryptocurrencies is here to stay. It's important to be able to work with multiple cryptocurrencies effectively and exchanging value between currencies is an essential part of this.

Third party exchange services

The mechanism being used overwhelmingly for this, right now, is exchange through third party exchange sites.

Exchange sites are pretty essential, first of all, as a way to get hold of some initial cryptocurrency, e.g. to exchange fiat cash to bitcoin, but some of these sites also support other cryptocurrencies, and will then also permit you to exchange directly between supported coins. (Some popular sites that do this are currently btc-e and cryptsy).

If you have some units of one currency (say bitcoin) and want to exchange this to some other currency (such as litecoin) and you do a bunch of internet searches and read some relevant forums, you'll most likely be directed to exchange sites like these.

Exchange through an exchange site

To use one of these sites you'll need an account set up, and there'll be some kind of registration process for this.

On some sites you'll need to provide some personal documents in order to get this account. This is to protect the site from potential issues with financial regulation, and may not be necessary if you are only trading between cryptocurrencies. (This isn't currently necessary for a basic account on either btc-e or cryptsy, for example.)

Once you have an account, the next step is to deposit the funds you wish to trade, into this account. This means paying coins into an address controlled by the exchange site.

So you hand over complete control of these funds to the exchange site at this point, and you trust the exchange to act appropriately, and in particular not to lose or steal the funds.

Once you have funds in your account you can make trade offers against a shared offer book. The site takes care of offer matching, and after offers have been matched successfully with offers from other users of the site, you'll end up with funds in your account in the target denomination, and you can now withdraw these funds once again to an address you control.

Problems with this setup

This is actually all quite convenient, in practice. But it doesn't seem like the right way to set this up.

The main problem, I think, is the need for trust.

You have to trust the company behind the exchange site to be honest, obviously, and hope they don't just run away with your funds.

But honesty is not sufficient. You also have to trust the company to implement the exchange robustly and effectively, and make sure that the exchange goes through correctly. You have to hope that the site isn't hacked, or defrauded by a dishonest employee, and that the company doesn't fall afoul of some regulatory issue and have their accounts frozen and data store seized.

History is full of cases where this doesn't work out, culminating in the spectacular collapse of MTGox.

Another problem is that you can only exchange through an exchange site if it supports the pair of currencies you wish to exchange. Before exchange support is added for new currencies people often use direct exchanges through forums to buy and sell units of the currency.

One of the cool things about Bitcoin is that it is decentralised. So if everything is set up correctly, you don't depend on support from, or need to trust, some third party service. What I'd like to see is a similar decentralised and trustless mechanism as a basis for the exchange process.

Focus on direct exchange

We'll simplify the problem by ignoring the whole offer matching side of things, and focus on the actual exchange of funds.

In other words, let's assume we have two parties who have already (somehow) found each other and agreed to exchange a fixed amount of one currency for a fixed amount of another currency. This is really the fundamental part of the exchange process, I think, and if we can solve this basic exchange mechanism it feels like we should be able to build things like offer books and matching back in around this (in the same way as other services are built on top of fundamental bitcoin payment operations).

Approaches to direct exchange

There are a number of ways we can then approach this core exchange problem.

One possibility is to split the exchange into a whole bunch of smaller exchanges, to be performed one after another.

The idea is that if we wait until each smaller exchange is completed, before moving on to the next, then we can only ever lose the funds in one smaller exchange. So this reduces the total amount that can be stolen by either party, but at the expense of a lot of additional hassle and transaction fees.

Another possibility is to use multisig transactions and a third party escrow agent.

With '2 of 3 multisig' (for example) we can set up a payment that's redeemable by any 2 out of 3 signing agents, where the signing agents are the two exchanging parties and the additional escrow agent.

With this approach the escrow agent can effectively arbitrate individual payments and decide whether the payment should go through or be refunded, based on some confirmation of the corresponding counterpayment on another blockchain.

There are still potential issues with this, such as the possibility for an escrow agent to collaborate with one of the exchanging parties to defraud the other, and while each of these approaches can improve the situation, I think, neither provide an ideal solution.

The best approach, if possible, will be to use some kind of linked transaction mechanism to implement an atomic exchange across separate blockchains.

Atomic exchange

'Atomic' in this case means that it either happens, or it doesn't. So an atomic exchange should either fully complete, or be cancelled, with the money ending up back where it started. In particular, it shouldn't be possible for half of the exchange to go through and one party end up with all the money.

One example of an atomic exchange algorithm is described on the Bitcoin wiki, as follows:

A picks a random number x

A creates TX1: "Pay w BTC to [B's public key] if (x for H(x) known and signed by B) or (signed by A & B)"

A creates TX2: "Pay w BTC from TX1 to [A's public key], locked 48 hours in the future, signed by A"

A sends TX2 to B

B signs TX2 and returns to A

1) A submits TX1 to the network

B creates TX3: "Pay v alt-coins to [A-public-key] if (x for H(x) known and signed by A) or (signed by A & B)"

B creates TX4: "Pay v alt-coins from TX3 to [B's public key], locked 24 hours in the future, signed by B"

B sends TX4 to A

A signs TX4 and sends back to B

2) B submits TX3 to the network

3) A spends TX3 giving x

4) B spends TX1 using x

This is atomic (with timeout). If the process is halted, it can be reversed no matter when it is stopped.

Before 1: Nothing public has been broadcast, so nothing happens

Between 1 & 2: A can use refund transaction after 72 hours to get his money back

Between 2 & 3: B can get refund after 24 hours. A has 24 more hours to get his refund

After 3: Transaction is completed by 2 - A must spend his new coin within 24 hours or B can claim the refund and keep his coins - B must spend his new coin within 72 hours or A can claim the refund and keep his coins

For safety, both should complete the process with lots of time until the deadlines.

H(x) indicates the cryptographic hash of the random number x, and the idea is that this is a 'one way' hash.

(If we know x then we should be able to easily generate H(x), but if we don't know x it shouldn't be possible to reverse the hashing function and obtain either x, or some other value which also hashes to H(x).)

The 24 and 72 hours timeouts written are chosen fairly arbitrarily, I think, with the purpose of emphasising robustness with respect to some idea of worst case potential blockchain reorganisations. Much smaller timeouts should also work, and, just as with payment confirmations, you can choose how careful you want to be, in practice, based on how much money is actually at stake.

So there are some rules to follow, and the idea is that, as long as each party follows the rules for their side of the exchange, it shouldn't be possible for the other side to cheat and get all the money.

Note that there's no guarantee that the exchange will complete, however. There's nothing to force B to actually continue with the exchange after A has submitted TX1, for example. So B can choose to lock up the A's bitcoin for the relevant timeout period, at no cost to themselves.

As with offer books and trade matching, I think that this can be addressed by building some other stuff on top of the base exchange mechanism, e.g. as part of some external 'reputation' mechanism, and a guarantee that neither side can lose their funds is certainly an improvement on existing mechanisms.

If this all works correctly I think this can serve as quite a good basis for cross currency exchange.

But can we make this work?

Payment and refund transactions

Unfortunately, there's a problem with this exchange process in the current version of Bitcoin (0.9.3).

Notice how linked pairs of transactions are constructed on each side of the exchange?

In each case there's one initial transaction (TX1 or TX3), and then a second refund transaction (TX2 or TX4). If everything goes to plan then TX2 and TX4 don't need to be used, but these transactions are designed to enable each party to get their funds back, in the case where the other party fails to complete.

But this refund mechanism doesn't quite work out. :(

Transaction malleability

The problem is transaction malleability.

Transaction malleability is an issue with the way that Bitcoin signs transactions, where transactions can be modified slightly, without changing the transaction behaviour, but resulting in a different transaction ID.

Each of those refund transactions refers back to a base transaction, and in Bitcoin this is done by Bitcoin transaction ID. (More specifically, what each refund transaction actually does is to spend the output of it's base transaction, and Bitcoin output specifications are made by transaction ID.)

In the atomic exchange process, the party making each payment should only make their payment if they are sure that they have a valid refund transaction in hand. So TX2 and TX4 must each be signed by the other party before the corresponding base transaction is submitted to the Bitcoin network. But transaction malleability means that a base transaction can potentially be 'mutated' during the submission process, changing it's transaction ID and invalidating that previously signed refund.

Current status

Although, at the time of writing, there's no mention of transaction malleability on that atomic cross-chain trading Bitcoin wiki page, the Bitcoin developer community has been aware of this issue for some time, and there is work in progress on the problem of transaction malleability more generally.

There was some progress in fixing the transaction malleability issue in Bitcoin release 0.9, but it seems that these changes didn't address all possible sources of transaction malleability, and the fundamental issue remains.

There's a soft fork proposal in bip-0062, and so this issue may be fixed in a future release. (According to that proposal: "This document specifies proposed changes to the Bitcoin transaction validity rules in order to make malleability of transactions impossible (at least when the sender doesn't choose to avoid it).")

Pay on reveal secret

So there are issues implementing refund transactions in Bitcoin. But can we look at this all a bit differently?

The refund transactions (TX2 and TX4) are there to add in a kind of 'timeout clause' to the corresponding base transaction. But you could say that's kind of a hack to work around the specific constraints of the Bitcoin protocol. What if we could design our own transaction types, without worrying about these protocol details?

The fundamental semantics on each side of the exchange are as follows:

• pay a specified recipient
• if and only a given secret is revealed within a specified time frame
• otherwise refund the funds back to me

(For conciseness I'll refer to these semantics as just 'pay on reveal secret' from here on.)

As long as we have some robust implementation of these semantics, we can apply the atomic exchange algorithm, which can be restated a bit more generally, something along the lines of the following:

A picks a random number x (the secret)

1) A submits a transaction TX1 to blockchain 1 that pays w units of cryptocurrency 1, either:

• to [B's blockchain 1 public key] if x for H(x) revealed before timeout 1, or
• to [A's blockchain 1 public key] if timeout 1 reached without x being revealed

2) B verifies A's transaction (e.g. making sure there are sufficient confirmations), chooses a suitable value for timeout 2, and then submits a transaction TX2 to blockchain 2 that pays v units of cryptocurrency 2 either:

• to [A's blockchain 2 public key] if x for H(x) revealed before timeout 2, or
• to [B's blockchain 2 public key] if timeout 2 reached without x being revealed

3) A verifies and spends TX2 (using whatever mechanism is required for this on blockchain 2) revealing x

4) B spends TX1 (using whatever mechanism is required for this on blockchain 1) using the revealed x from step 3

If either party fails to complete (e.g. B fails to submit TX2, or A does not reveal x) A and B do whatever is required on each blockchain to ensure outstanding transactions are refunded on timeout

A key element is the 'secret', which we need to be able to specify without revealing, and confirm once revealed, e.g. by specifying the cryptographic hash H(x).

As long as both sides use exactly the same secret representation and hashing function, and the pay on reveal secret semantics are implemented correctly on both sides of the exchange, the atomic exchange algorithm should work, regardless of the actual implementation of pay on reveal secret on each side.

In other words, different implementations of pay on reveal secret can interact, as long as they share the same secret and hashing function.

Standardised pay on reveal secret

That's pretty cool. And it seems there's quite a big an opportunity here, I think. Perhaps the most important point in this article is then to suggest that:

• all cryptocurrencies should support the implementation of 'pay on reveal secret' in some form
• with secret representation and hashing function standardised used across all such implementations.

If we can do this, it becomes possible to implement atomic exchange, at a fundamental level, between arbitrary pairs of cryptocurrencies.

Working example

Looking at the 'pay on reveal secret' semantics, it seems like this shouldn't be hard to implement, and it isn't, in the general case.

I've implemented a working version of this, for example, in 'SwapBill'.

SwapBill is an protocol for updating a shared global state representation based on information embedded in certain (specially formatted but standard) Bitcoin transactions.

This is implemented in a python client application, and this client can currently be run against the Bitcoin and Litecoin testnet blockchains, and used to exchange value between these blockchains.

The actual fundamental cross-chain exchange operation is implemented between 'Bitcoin SwapBill' and 'Litecoin SwapBill', for a simple direct exchange between two parties (so without any offer matching), but SwapBill also includes a bunch of stuff to make it easy to exchange SwapBill with host coin on each blockchain (including trade books and offer matching), and you can use this to make a 3 step exchange between the two host currencies (e.g. Bitcoin -> Bitcoin SwapBill -> Litecoin SwapBill -> Litecoin).

There's some documentation for SwapBill here, and documentation for the cross chain exchange operation specifically on this page.

Pay on reveal secret in SwapBill

In Bitcoin, global state is essentially limited to the set of unspent transaction outputs.

SwapBill extends this to add a bunch of other stuff, like order books and pending payments, and this extra global state is then used to implement pay on reveal secret without the need for refund transactions.

When a 'pay on reveal secret' transaction goes through, SwapBill creates a pending payment object in the SwapBill global state.

By default, this pending payment will expire on a specified block, and the person making the payment is refunded on pending payment expiry. A second 'reveal secret' transaction is required (before expiry) in order for the payment to complete.

Note that we still need some way of referencing the initial pay on reveal secret transaction in the following reveal secret, and this is done by a 'pending payment ID'. Crucially however, this pending payment ID is not required for the default refund case, and can be checked by the recipient at the same time as checking that the 'pay on reveal secret' has actually gone through on the blockchain, with the right details, with enough confirmations, and so on.

Secret hashing function implementation

SwapBill's pay on reveal secret implementation currently uses Bitcoin public keys as the secret, and public key hashes as the secret hash.

This works out as follows:

import hashlib
def publicKeyToPubKeyHash(publicKey):
    assert type(publicKey) is type(b'')
    assert len(publicKey) == 64
    ripemd160 = hashlib.new('ripemd160')
    ripemd160.update(hashlib.sha256(b'\x04' + publicKey).digest())
    return ripemd160.digest()

It's a bit odd to use 'public keys' as a secret, but this works (you can't currently work back from Bitcoin addresses, which are essentially formatted public key hashes, to the corresponding public key) and this was a convenient way to set up secrets in SwapBill.

I don't recommend this as a standard, however.

I guess a standard hashing function should probably be a little bit more over-engineered and future proofed.

Suggestions about the best function to use for this, from people with more cryptographic chops than myself, are very welcome!

Timing issues

The refund transactions from the Bitcoin wiki use a block count (with nLockTime) to specify when refund transactions can be submitted, which corresponds to the expiry time in our pay on reveal secret semantics.

The SwapBill implementation also a block count, although with automatic expiry as part of the protocol definition.

We need to be aware then, that although Bitcoin uses difficulty adjustment to keep block generation times around a fixed period of 10 minutes, this block time can vary quite significantly.

When making exchanges we need to make an estimate based on expected average block time in order to approximate wall time, but this is not exact, and we'll need to leave a certain amount of room for error.

It's probably not a good idea, also, to perform exchanges across a difficulty step.

I think the block count mechanism should probably be considered an implementation detail (although an important one), and there may be other ways to approach this.

Bitcoin includes a block timestamp, and a mechanism for keeping this within certain bounds with respect to wall time, and other cryptocurrency may include similar features.

Maybe it's possible to use this kind of wall time tracking, then, for pay on reveal secret expiry times.

Making pay on reveal secret work in Bitcoin

So we've seen that pay on reveal secret can be implemented in an 'embedded protocol', but what are the possible approaches for making this work directly in Bitcoin?

We saw transaction malleability is being addressed, and maybe the approach based on refund transactions can be made to work at some point, but this is all quite tricky. Transaction IDs weren't designed to be immutable. There are a whole bunch of different ways transactions can potentially be mutated, and it all ends up quite difficult to understand in the entirety and 'audit'.

Another alternative might be to add more direct support for this in the Bitcoin protocol. For example, maybe it is possible to add support for some kind of conditional scripting, where one subscript can be used to spend an output only up to a certain block limit, and another part only after that block limit.

This isn't a detailed proposal. The point is just that, if support for pay on reveal secret functionality is considered a priority, there are certainly ways to implement this.

Politics

There are some potentially financial and political issues here, however.

In particular, if you have a vested interest in the price of Bitcoin you might not actually want to enable, or encourage exchanges between Bitcoin and other currencies.

That would seem like a short sighted point of view to me, however.

I don't think you really can prevent people from moving value to other cryptocurrencies, if they really want to do this, but support for trustless exchange is something that I think will increase the utility of Bitcoin, and cryptocurrencies in general.

(Disclaimer: I own some Bitcoin myself, although not a large amount, and try not to let this influence my opinions!)

Pay on reveal secret in other currencies

A lot of cryptocurrencies use a similar mechanism for transaction output scripts as Bitcoin, and so similar issues and alternatives will apply.

Some newer currencies change things up a bit more radically, however, with stuff like smart contracts and Turing complete scripting. It sounds like 'pay on reveal secret' should be easy to implement in these newer currencies, but I haven't looked into the details for this.

Extending to other types of exchanges

I don't think the pay on reveal secret semantics have to be limited to pure cryptocurrency exchanges. If you can set up delivery of physical goods or fiat with similar 'semantics' then it should be possible to apply the same atomic exchange idea here.

Imagine a world, for example, where the guy selling you something through eBay hands it over in return for scanning a QR code, where that QR code is a secret that unlocks the counterpayment.

Or maybe something like this can be used by the delivery guy for something you bought through Amazon. This isn't completely trustless. You still need to trust the guy not to grab the physical item back from you and run off, after you reveal the secret, but it seems better than the current mechanisms for this.

And wouldn't it be great if, as well as simple unconditional (and non-reversible) wire transfers, I could also make bank payments on condition that the recipient reveals a specified secret, within a specified time limit?

Conclusion

To sum up:

Atomic cross chain exchange is possible, given support for certain fundamental transaction semantics, and 'pay on reveal secret' seems like a good basis for this.

Standardising the secret hashing function makes this work across arbitrary currency pairs.

There are implementation issues in Bitcoin, currently, but these aren't fundamentally hard to resolve (or can be worked around with an embedded protocol).

Personally I think that this is the future of cryptocurrency exchange.

If you're an exchange operator, I think you should already be looking into what will be involved in building convenient exchange services on top of atomic exchange.

If you're working with a cryptocurrency that already supports pay on reveal secret, let us know.

Otherwise, if you're a cryptocurrency 'consumer' and could benefit from this feature, let the developers know!