Source-linked AI summary
Atomic Cross-Chain Swaps
Maurice Herlihy
TL;DR
The paper asks when multi-party asset exchanges across blockchains can be coordinated without trust. It models swaps as directed graphs and constructs hashed-timelock protocols under graph-theoretic conditions, proving both feasibility and impossibility boundaries.
Problem
The paper studies when atomic cross-chain swaps are possible, how they can be implemented, and what they cost.
Method
The paper models parties and proposed transfers as a directed graph and uses hashed timelock contracts with secrets generated by leaders in a feedback vertex set.
Results
Atomic protocols exist for strongly connected swap digraphs with feedback-vertex-set leaders, but not when strong connectivity or the feedback-vertex-set condition fails.
Takeaways & Limitations
The protocol coordinates cross-chain exchanges while ensuring that no conforming party ends up underwater, with time scaling as O(diam(D)).
Takeaways & Limitations
The protocol assumes that the swap digraph, its leaders, and their hashlocks are common knowledge among participants.
Abstract
from arXiv · showhide
An atomic cross-chain swap is a distributed coordination task where multiple parties exchange assets across multiple blockchains, for example, trading bitcoin for ether. An atomic swap protocol guarantees (1) if all parties conform to the protocol, then all swaps take place, (2) if some coalition deviates from the protocol, then no conforming party ends up worse off, and (3) no coalition has an incentive to deviate from the protocol. A cross-chain swap is modeled as a directed graph ${\cal D}$, whose vertexes are parties and whose arcs are proposed asset transfers. For any pair $({\cal D},L)$, where ${\cal D} = (V,A)$ is a strongly-connected directed graph and $L \subset V$ a feedback vertex set for ${\cal D}$, we give an atomic cross-chain swap protocol for ${\cal D}$, using a form of hashed timelock contracts, where the vertexes in $L$ generate the hashlocked secrets. We show that no such protocol is possible if ${\cal D}$ is not strongly connected, or if ${\cal D}$ is strongly connected but $L$ is not a feedback vertex set. The protocol has time complexity $O(diam({\cal D}))$ and space complexity (bits stored on all blockchains) $O(|A|^2)$.
1 MOTIVATION
The paper motivates atomic cross-chain swaps as trust-free coordination for exchanging assets across blockchains, then models their feasibility and implementation using swap digraphs, leaders, and hashed timelocks.
- A three-party example exchanges Alice’s alt-coins, Bob’s bitcoins, and Carol’s automobile title without requiring mutual trust.The proposed sequence uses blockchain contracts to coordinate the transfers.
- Hashed timelock contracts transfer assets when a matching secret is revealed before a deadline; otherwise, the original owner receives a refund.A hashlock verifies the secret, while a timelock limits the claim period.
- Sequential contract deployment and staggered timeouts prevent a participant from claiming an asset without enabling the preceding transfer.If a party halts during deployment, contracts time out and refund; if a party halts during triggering, only that party is harmed.
- Atomic swap protocols must complete all exchanges when parties conform, protect conforming parties when others deviate, and eliminate coalition incentives to deviate.These guarantees address both rational self-interest and irrational behavior in multi-party exchanges.
- Atomic cross-chain swaps may also coordinate updates across blockchain shards, software versions, or data schemas as a trust-free distributed commitment mechanism.The immediate motivation is digital-asset exchange, but the paper identifies broader distributed-systems applications.
- The paper models swaps as directed graphs of parties and transfers, and gives a hashed-timelock protocol for strongly connected graphs with leaders forming a feedback vertex set.Leaders generate the hashlocked secrets, while non-leaders are followers; the paper also proves impossibility outside these structural conditions.
2 MODEL
The model treats a swap as a directed graph executed over publicly readable, tamper-proof blockchains with irrevocable smart contracts and rational or irrational participants.
- 2.1 Digraphs: A digraph D = (V,A) consists of vertices V and ordered pairs of distinct vertices called arcs.The paper uses vertices for parties and arcs for proposed transfers.
- 2.1 Digraphs: A digraph is strongly connected when every vertex can reach every other vertex, and a feedback vertex set is a vertex subset whose deletion leaves the graph acyclic.These structural properties determine when the swap protocol can apply.
- 2.1 Digraphs: The transpose D^T reverses every arc, while strong connectivity and feedback-vertex-set status are preserved under transposition.This provides a symmetry of the graph model.
- 2.2 Blockchains and Smart Contracts: A blockchain is modeled as a publicly readable, tamper-proof distributed ledger, with known duration ∆ sufficient for publishing or confirming a contract.The timing assumption abstracts away from the particular blockchain algorithm.
- 2.2 Blockchains and Smart Contracts: Smart contracts are irrevocable scripts that transfer asset ownership when specified conditions are met.Once published, neither the creator nor another party can remove the contract or alter its terms.
- 2.3 Participants: Rational parties deviate only when profitable, may collude, and differ from irrational parties who may deviate even without profit.Irrational deviations can arise from spite, hacking, or unforeseen profits.
3 SWAP DIGRAPHS AND GAMES
The section models cross-chain swaps as cooperative games on directed graphs, defines acceptable and unacceptable outcomes, and formalizes atomicity as uniformity plus coalition-proof incentives. It proves that uniform protocols are atomic exactly when the swap digraph is strongly connected, under an assumption that value transfers are recorded on blockchains.
- Swap digraphs and outcomes: A cross-chain swap is modeled by a directed graph whose vertices are parties and arcs are proposed asset transfers via shared blockchains.Possible outcomes are subdigraphs indicating which transfers were triggered.
- Swap digraphs and outcomes: Parties’ outcomes range from FreeRide and Discount to Deal, NoDeal, and the unacceptable Underwater outcome.Deal means all expected transfers occur; Underwater means a party pays while failing to acquire all expected assets.
- Protocol and game definitions: A uniform protocol gives every compliant party Deal when followed and prevents any compliant party from receiving Underwater after coalition deviations.Atomicity additionally requires that no coalition can improve its payoff by deviating.
- Strong connectivity: If the swap digraph is strongly connected, every uniform protocol is atomic because coalition deviations cannot consistently separate triggered and untriggered transfers.Strong connectivity supplies paths that propagate trigger conditions across the coalition boundary, yielding a contradiction.
- Strong connectivity: If the digraph is not strongly connected, a coalition can obtain FreeRide by triggering internal transfers while withholding transfers toward reachable parties.Thus, rational parties would deviate from any uniform protocol, and such a swap would not be agreed to in practice.
- Assumptions: The characterization assumes that all value transfers, including off-chain consequences, are explicitly recorded on a shared blockchain.Without that assumption, unrecorded transfers could falsify the theorem’s outcome model.
4 AN ATOMIC SWAP PROTOCOL
The protocol uses hashed timelock contracts whose hashlocks and path-dependent timeouts coordinate transfers on a strongly connected swap digraph. Leaders generate secrets from a feedback vertex set; conforming swaps complete within a diameter-based bound, while deviations protect conforming parties and the leader condition is necessary.
- Hashlocks and hashkeys: A hashed timelock contract transfers an asset when the matching secret arrives before its timeout; otherwise, it refunds the original owner.The contract stores an asset, swap digraph, leaders, parties, timeout vector, and hashlock vector.
- Timeouts: Timeouts on arcs entering a follower are at least ∆ later than timeouts on arcs leaving it, preserving time to trigger incoming contracts.This ordering works for a single leader because the follower subdigraph is acyclic, but not across cycles.
- Hashkeys: For general digraphs, leaders form a feedback vertex set and generate hashlocks; each arc receives hashkeys tied to leader-to-counterparty paths and signatures.A hashkey unlocks a hashlock before (diam(D) + |p|) · ∆, and an arc triggers only after all its hashlocks are unlocked.
- Market clearing: The market-clearing service publishes the swap digraph, leaders, leaders’ hashlocks, and a start time after combining parties’ offers.The service need not be trusted because parties can check the consistency of its responses.
- Correctness and complexity: 2 · diam(D) · ∆ bounds contract triggering and the time conforming parties’ assets remain escrowed when deviations occur.If all parties conform, every contract triggers within this bound; otherwise, conforming parties’ assets are refunded by the deadline.
- Correctness and complexity: O(|A|^2) blockchain space is required, and any uniform hashed-timelock protocol must assign secrets to a feedback vertex set.The necessity follows because followers cannot publish outgoing contracts before all incoming contracts, implying that leaders intersect every cycle.
5 REMARKS
The paper discusses protocol extensions, optimization opportunities, computational trade-offs, and unresolved limitations for atomic cross-chain swaps.
- Single-leader swap digraphs need only timeouts, whereas general cases raise questions about reducing digital-signature use.
- Finding a minimal feedback vertex set is NP-complete, although an efficient 2-approximation exists.
- The protocol extends to directed multigraphs, allowing multiple asset transfers between the same pair of parties on distinct blockchains.
- The protocol remains vulnerable to weak denial-of-service attacks that temporarily render assets inaccessible when adversaries repeatedly abandon attractive swaps.
- Recurring swaps can distribute the next round’s hashlocks during the previous round and may support more off-chain execution.
- The protocol assumes that the swap digraph, leaders, and hashlocks are common knowledge among participants.
6 RELATED WORK
The related work connects atomic cross-chain swaps to prior work on two-party swaps, off-chain networks, kidney exchange, fair exchange, and broader cross-chain transactions.
- Two-party hashed-timelock swap protocols have open-source implementations for selected currencies, alongside proposals for swap applications.
- Off-chain payment networks address blockchain scalability through off-chain transactions, while using hashed timelocks for different problems.
- Kidney-exchange research primarily studies matching donors and recipients, including algorithms for constructing swap digraphs and analyzing market equilibria.
- Fair exchange predates atomic cross-chain swaps and seeks either mutual exchange or retention of both parties’ assets, often using trusted intermediaries without blockchains.
- Atomic cross-chain swaps are a subset of atomic cross-chain transactions because not every sequence of cross-chain exchanges can be expressed as swaps.
- A broader theory of atomic cross-chain transactions remains future work.