The problem of atomic cross-chain trading is one where (at least) two parties, Alice and Bob, own coins in separate cryptocurrencies (e.g. Bitcoin and Litecoin), and want to exchange them without having to trust a third party (centralized exchange).
A non-atomic trivial solution would have Alice send her Bitcoins to Bob, and then have Bob send Litecoins to Alice - but Bob has the option of going back on his end of the bargain and simply not following through with the protocol, ending up with both Bitcoins and Litecoins.
Solution using revealing secrets of contract
Here is one description of an algorithm that solves this problem, credit goes to TierNolan for this specific description (the algorithm was described in other terms by other people including Mike Hearn above).
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.
Solution using specialized altchain
The previously mentioned approach can be used directly to trade between bitcoin-derived chains without special support on the side of protocol. The obvious disadvantage is the timeout - if counterparty does not go through the trade, our funds are locked and cannot used in another trade for the duration of timeout.
Another proposal of cross-chain p2ptrade is to use specialized altchain with properties for efficient operation of p2ptrade from bitcoin chain. Additionaly, we use only single standard bitcoin transaction (no nlocktime, no multisig, no special script).
Assuming the altchain has actual economic value to support it, it can even serve as proxy for (relatively) efficient zero-trust p2p market between fe. BTC and LTC thanks to arbitraging market makers.
- In bitcoin, you create and sign the transaction as usual and compute its txid. You txid and the transaction body with input scripts/signature blanked to altchain counterparty.
- Altchain counterparty computes hash of the blanked body, call it blankhash, and constructs transaction with special bitcointxid(blankhash,txid) opcode. Broadcasts the transaction to altchain.
- Bitcoin party waits for altchain tx to confirm and verify its outputs are as agreed - at that point it releases the "uncensored" tx. Altchain user receives the bitcoin funds, which will also enable the altchain tx at the same time (this is the atomic point).
- Bitcoin party releases its tx only if it is sufficiently confident the altchain will not reorg its transactions, thus possibly double spend. This might imply that *many* confirmations in altchain should come first - during that time each of them might decide to cancel the trade with no further consequences.
Opcodes and altchain special rules
- bitcointxid evaluates to true if txid (and blankhash is equal to tx body) are seen confirmed in the bitcoin blockchain (altchain client must consult bitcoin for that) and it's outputs are spendable (ie verify it's standard tx).
- The transaction is constructed in such a way it is valid to be included in altchain even if there is no matching txid/blankhash in bitcoin
- Its outputs are not spendable and inputs are free to be spent by another tx (i know, ugly!) until bitcoin txid confirmed "freezes" the tx (at which point it consumes inputs, and it's outputs become spendable).
- Optionally there could be bitcoin block# parameter at which point the freeze occurs (effectively dictating number of confirms on bitcoin side).
- It is legal for inputs to be mentioned multiple times, first (in blockheight order) transaction which gets "frozen" wins and other same-input consumers become invalid.