This post summarizes key ideas in the conference paper “Atomic Cross-Chain Swaps”. (Detailed Presentation)

Objective

An atomic swap protocol guarantees

1. If all parties conform to the protocol, then all swaps take place
2. If some parties deviate from the protocol, then no conforming party ends up worse off
3. No coalition has an incentive to deviate from the protocol

Problem Statement

• When such swaps possible?
• How to implement?
• What do they cost?

Paper Approach

1. Model the swap by a directed graph (or digraph)
2. Classify protocol outcomes
3. Analyze the protocol using pebble games
4. Propose the protocol
5. Conclude with existence condition, time and space complexity

Conclusion

1. For any pair (𝒟,𝐿), where 𝒟=(𝑉,𝐴) is a strongly-connected digraph and 𝐿⊂𝑉 a feedback vertex set, the paper gives an atomic cross-chain swap protocol using hashed timelock contracts, where vertexes in 𝐿 generate the hashlocked secrets.

2. No such protocol is possible if 𝒟 is not strongly connected, or if 𝒟 is strongly connected but 𝐿 is not a feedback vertex set.

3. The protocol has time complexity 𝒪(𝑑𝑖𝑎𝑚(𝒟)) and space complexity (bits stored on all blockchains) 𝒪(abs(𝐴)^2).