Maurice Herlihy
ABSTRACT
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 D, whose vertexes are parties and whose arcs are proposed asset transfers. For any pair (D, L), where D = (V,A) is a strongly-connected directed graph and L ⊂ V a feedback vertex set for D, we give an atomic cross-chain swap protocol for 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 D is not strongly connected, or if D is strongly connected but L is not a feedback vertex set. The protocol has time complexityO(diam(D)) and space complexity (bits stored on all blockchains) O(|A|2).
- David J. Abraham, Avrim Blum, and Tuomas Sandholm . 2007. Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide Kidney Exchanges. In Proceedings of the 8th ACM Conference on Electronic Commerce (EC '07). ACM, New York, NY, USA, 295--304. Google Scholar
Digital Library
- J. Bang-Jensen and G. Gutin . 2001. Digraphs: Theory, Algorithms, and Applications. Springer. showLCCN00044032deftempurl%https://books.google.com/books?id=d3gpAQAAMAAJ tempurl Google ScholarDigital Library
- Ann Becker and Dan Geiger . 1996. Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. Artificial Intelligence Vol. 83, 1 (1996), 167 -- 188. Google ScholarDigital Library
- bitcoinwiki . {n. d.} a. Atomic cross-chain trading. https://en.bitcoin.it/wiki/Atomic_cross-chain_trading. As of 9 January 2018.Google Scholar
- bitcoinwiki . {n. d.} b. Hashed Timelock Contracts. deftempurl%https://en.bitcoin.it/wiki/Hashed_Timelock_Contracts Retrieved 8 January 2018 from tempurlGoogle Scholar
- Sean Bowe and Daira Hopwood . {n. d.}. Hashed Time-Locked Contract transactions. deftempurl%https://github.com/bitcoin/bips/blob/master/bip-0199.mediawiki Retrieved 9 January 2018 from tempurlGoogle Scholar
- Vitalik Buterin . {n. d.}. On sharding blockchains. deftempurl%https://github.com/ethereum/wiki/wiki/Sharding-FAQ Retrieved 8 January 2018 from tempurlGoogle Scholar
- Christian Decker and Roger Wattenhofer . 2015. A Fast and Scalable Payment Network with Bitcoin Duplex Micropayment Channels Stabilization, Safety, and Security of Distributed Systems, bibfieldeditorAndrzej Pelc and Alexander A. Schwarzmann (Eds.). Springer International Publishing, Cham, 3--18. Google ScholarDigital Library
- DeCred . {n. d.}. Decred cross-chain atomic swapping. deftempurl%https://github.com/decred/atomicswap Retrieved 8 January 2018 from tempurlGoogle Scholar
- John P. Dickerson, David F. Manlove, Benjamin Plaut, Tuomas Sandholm, and James Trimble . 2016. Position-Indexed Formulations for Kidney Exchange. CoRR Vol. abs/1606.01623 (2016). showeprint{arxiv}1606.01623deftempurl%http://arxiv.org/abs/1606.01623 tempurlGoogle Scholar
- Matthew K. Franklin and Gene Tsudik . 1998. Secure Group Barter: Multi-party Fair Exchange with Semi-Trusted Neutral Parties Financial Cryptography. Google ScholarDigital Library
- Matthew Green and Ian Miers . 2016. Bolt: Anonymous Payment Channels for Decentralized Currencies. Cryptology ePrint Archive, Report 2016/701. https://eprint.iacr.org/2016/701Google Scholar
- Zhipeng Jia, Pingzhong Tang, Ruosong Wang, and Hanrui Zhang . 2017. Efficient Near-optimal Algorithms for Barter Exchange Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems (AAMAS '17). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 362--370. deftempurl%http://dl.acm.org/citation.cfm?id=3091125.3091181 tempurl Google ScholarDigital Library
- Randy M. Kaplan . 2011. An improved algorithm for multi-way trading for exchange and barter. Electronic Commerce Research and Applications Vol. 10, 1 (2011), 67 -- 74. Special Section: Service Innovation in E-Commerce. Google ScholarDigital Library
- Richard M. Karp . 1972. Reducibility Among Combinatorial Problems. In Proceedings of a symposium on the Complexity of Computer Computations, held March 20--22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York. 85--103. deftempurl%http://www.cs.berkeley.edu/ luca/cs172/karp.pdf tempurlGoogle ScholarCross Ref
- Rami Khalil and Arthur Gervais . 2017. Revive: Rebalancing Off-Blockchain Payment Networks Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (CCS '17). ACM, New York, NY, USA, 439--453. Google ScholarDigital Library
- Silvio Micali . 2003. Simple and Fast Optimistic Protocols for Fair Electronic Exchange Proceedings of the Twenty-second Annual Symposium on Principles of Distributed Computing (PODC '03). ACM, New York, NY, USA, 12--19. Google ScholarDigital Library
- Andrew Miller, Iddo Bentov, Ranjit Kumaresan, and Patrick McCorry . 2017. Sprites: Payment Channels that Go Faster than Lightning. CoRR Vol. abs/1702.05812 (2017). showeprint{arxiv}1702.05812deftempurl%http://arxiv.org/abs/1702.05812 tempurlGoogle Scholar
- Raiden Network . {n. d.}. What is the Raiden Network?deftempurl%https://raiden.network/101.html Retrieved 26 January 2018 from tempurlGoogle Scholar
- T. Nolan . {n. d.}. Atomic swaps using cut and choose. deftempurl%https://bitcointalk.org/index.php?topic=1364951 Retrieved 9 January 2018 from tempurlGoogle Scholar
- The Komodo Organization . {n. d.}. The BarterDEX Whitepaper: A Decentralized, Open-Source Cryptocurrency Exchange, Powered by Atomic-Swap Technology. deftempurl%https://supernet.org/en/technology/whitepapers/BarterDEX-Whitepaper-v0.4.pdf Retrieved 9 January 2018 from tempurlGoogle Scholar
- J. Poon and T. Dryja . 2016. The Bitcoin Lightning Network: Scalable Off-Chain Instant Payments. deftempurl%https://lightning.network/lightning-network-paper.pdf tempurl As of 29 December 2017.Google Scholar
- Lloyd Shapley and Herbert Scarf . 1974. On cores and indivisibility. Journal of Mathematical Economics Vol. 1, 1 (1974), 23--37. deftempurl%https://EconPapers.repec.org/RePEc:eee:mateco:v:1:y:1974:i:1:p:23--37 tempurlGoogle ScholarCross Ref
- Solidity documentation . {n. d.}. http://solidity.readthedocs.io/en/latest/index.html.Google Scholar
- Gerhard Weikum and Gottfried Vossen . 2001. Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA. Google ScholarDigital Library
- Wikipedia . {n. d.}. Two-phase commit protocol. deftempurl%https://en.wikipedia.org/wiki/Two-phase_commit_protocol Retrieved 18 May 2018 from tempurlGoogle Scholar
- G. Zyskind, C. Kisagun, and C. FromKnecht . {n. d.}. Enigma Catalyst: a machine-based investing platform and infrastructure for crypto-assets. https://www.enigma.co/enigma_catalyst.pdf. As of 25 January 2018.Google Scholar
Recommendations
Atomic cross chain swaps via relays and adapters
CryBlock '20: Proceedings of the 3rd Workshop on Cryptocurrencies and Blockchains for Distributed SystemsBlockchain technologies have proven their potential when it comes to store assets and value. However, swapping assets across chains, for example trading ethers for bitcoins is still a challenging problem to solve. Current solutions widely rely on ...
On the optionality and fairness of Atomic Swaps
AFT '19: Proceedings of the 1st ACM Conference on Advances in Financial TechnologiesAtomic Swap enables two parties to atomically exchange their own cryptocurrencies without trusted third parties. This paper provides the first quantitative analysis on the fairness of the Atomic Swap protocol, and proposes the first fair Atomic Swap ...
Atomic cross-chain swaps with improved space, time and local time complexities
AbstractAn effective atomic cross-chain swap protocol is introduced by Herlihy [Herlihy, 2018] as a distributed coordination protocol in order to exchange assets across multiple blockchains among multiple untrusted parties. The atomic cross-chain swap ...
Comments