The problem of an atomic swap is one where (at least) two parties, Alice and Bob, own coins, and want to exchange them without having to trust a third party (centralized exchange).
A non-atomic trivial solution would have Alice send her coins to Bob, and then have Bob send other coins 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 sets of coins.
Atomic swaps can be used for trading between bitcoin and another cryptocurrency, or for trading bitcoin UTXOs for privacy purposes.
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, revealing 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 nLockTime - if counterparty does not go through the trade, our funds are locked and cannot used in another trade for the duration of timeout. Additionally, it depends on transaction replacement which may, or may not be considered standard under current bitcoin protocol rules.
Another proposal of cross-chain p2ptrade is to use specialized altchain with properties for efficient operation of p2ptrade from bitcoin chain. Additionally, we use only single standard bitcoin transaction which looks exactly the same as normal payment (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.
- Bob create and sign the transaction as usual and compute its txid. He sends txid and the transaction body with input scripts/signature blanked to Alice.
- Alice computes hash of the blanked body, call it blankhash, and constructs transaction with special bitcointxid(blankhash,txid) opcode. Broadcasts the transaction to altchain.
- Bob waits for altchain tx to confirm and verify its outputs are as previously agreed - at that point he sends the "uncensored" Bitcoin tx to Alice who'll broadcast it. Alice is therefore credited the bitcoin funds, which in turn validate altchain transaction at the same time (this is the atomic point).
- Note that bob releases his tx only if he 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, however 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.