{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,30]],"date-time":"2026-06-30T15:40:03Z","timestamp":1782834003337,"version":"3.54.5"},"reference-count":55,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,8,20]],"date-time":"2021-08-20T00:00:00Z","timestamp":1629417600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,8,20]],"date-time":"2021-08-20T00:00:00Z","timestamp":1629417600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1917990"],"award-info":[{"award-number":["1917990"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2022,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Modern distributed data management systems face a new challenge: how can autonomous, mutually distrusting parties cooperate safely and effectively? Addressing this challenge brings up familiar questions from classical distributed systems: how to combine multiple steps into a single atomic action,  how to recover from failures, and how to synchronize concurrent access to data. Nevertheless, each of these issues requires rethinking when participants are autonomous and potentially adversarial. We propose the notion of a <jats:italic>cross-chain deal<\/jats:italic>, a new way to structure complex distributed computations that manage assets in an adversarial setting. Deals are inspired by classical atomic transactions, but are necessarily different, in important ways, to accommodate the decentralized and untrusting nature of the exchange. We describe novel safety and liveness properties, along with two alternative protocols for implementing cross-chain deals in a system of independent blockchain ledgers. One protocol, based on synchronous communication, is fully decentralized, while the other, based on semi-synchronous communication, requires a globally shared ledger. We also prove that some degree of centralization is required in the semi-synchronous communication model.<\/jats:p>","DOI":"10.1007\/s00778-021-00686-1","type":"journal-article","created":{"date-parts":[[2021,8,20]],"date-time":"2021-08-20T12:02:43Z","timestamp":1629460963000},"page":"1291-1309","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":38,"title":["Cross-chain deals and adversarial commerce"],"prefix":"10.1007","volume":"31","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3059-8926","authenticated-orcid":false,"given":"Maurice","family":"Herlihy","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Barbara","family":"Liskov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Liuba","family":"Shrira","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,8,20]]},"reference":[{"key":"686_CR1","unstructured":"Abraham, I., Gueta, G.,Malkhi, D: Hot-stuff the linear, optimal-resilience, one-message BFT devil. CoRR, abs\/1803.05069 (2018)"},{"key":"686_CR2","doi-asserted-by":"crossref","unstructured":"Aiyer, A.\u00a0S., Alvisi, L., Clement, A., Dahlin, M., Martin, J.-P., Porth, C.: BAR fault tolerance for cooperative services. In Proceedings of the Twentieth ACM Symposium on Operating Systems Principles, SOSP \u201905, pages 45\u201358, New York, NY, USA, ACM (2005)","DOI":"10.1145\/1095810.1095816"},{"key":"686_CR3","doi-asserted-by":"crossref","unstructured":"Al-Bassam, M., Sonnino, A., Bano, S., Hrycyszyn, D., Danezis, G.\u00a0: Chainspace: A sharded smart contracts platform. CoRR, abs\/1708.03778 (2017)","DOI":"10.14722\/ndss.2018.23241"},{"key":"686_CR4","doi-asserted-by":"crossref","unstructured":"Androulaki, E., Barger, A., Bortnikov, V., Cachin, C., Christidis, K., De\u00a0Caro, A., Enyeart, D., Ferris, C., Laventman,G., Manevich, Y., Muralidharan, S., Murthy, C. Nguyen, B., Sethi, M., Singh, G., Smith, K., Sorniotti, A., Stathakopoulou, C., Vukoli\u0107, M., Cocco, S.\u00a0W., Yellick, J: Hyperledger fabric: a distributed operating system for permissioned blockchains. In Proceedings of the Thirteenth EuroSys Conference, EuroSys \u201918, pages 30:1\u201330:15, New York, NY, USA, ACM (2018)","DOI":"10.1145\/3190508.3190538"},{"key":"686_CR5","doi-asserted-by":"crossref","unstructured":"Androulaki, E., Cachin, C., Caro, A.\u00a0D, Kokoris-Kogias, E.: Channels: Horizontal scaling and confidentiality on permissioned blockchains. In ESORICS (2018)","DOI":"10.1007\/978-3-319-99073-6_6"},{"key":"686_CR6","unstructured":"Association, L.: An introduction to libra (2019)"},{"key":"686_CR7","unstructured":"Barrett, B.: Hack brief: hackers stole \\$40 million from binance cryptocurrency exchange (2019)"},{"key":"686_CR8","unstructured":"Bernstein, P.A., Hadzilacos, V., Goodman, N.: Concurrency Control and Recovery in Database Systems. Addison-Wesley Longman Publishing Co., Inc, Boston, MA, USA (1986)"},{"key":"686_CR9","unstructured":"Binance Academy. What are flash loans in DeFi? (2020)"},{"key":"686_CR10","unstructured":"Binance Academy. What is an automated market maker (AMM)? (2020)"},{"key":"686_CR11","unstructured":"bitcoinwiki. Atomic cross-chain trading"},{"key":"686_CR12","unstructured":"Bowe, S., Hopwood, D.\u00a0: Hashed time-locked contract transactions"},{"key":"686_CR13","unstructured":"Castro, M., Liskov, B.\u00a0: Practical byzantine fault tolerance. In Proceedings of the Third Symposium on Operating Systems Design and Implementation, OSDI \u201999, pages 173\u2013186, Berkeley, CA, USA, 1999. USENIX Association. Number of pages: 14 Place: New Orleans, Louisiana, USA tex.acmid: 296824"},{"key":"686_CR14","unstructured":"Chester, J.: Your guide on bitcoin\u2019s lightning network: The opportunities and the issues (2018)"},{"key":"686_CR15","doi-asserted-by":"crossref","unstructured":"Clement, A., Li, H., Napper, J., Martin, J.P.M., Alvisi, L., Dahlin, M.: BAR primer. In Proceedings of the International Conference on Dependable Systems and Networks (DSN), DCC Symposium, Place, Anchorage, AK (2008)","DOI":"10.1109\/DSN.2008.4630097"},{"key":"686_CR16","unstructured":"Coindesk. Tether stablecoin launches on its seventh blockchain (2020)"},{"key":"686_CR17","unstructured":"Coleman, J., Horne, L.\u00a0, Xuanji, L.: Counterfactual: generalized state channels (2018)"},{"key":"686_CR18","doi-asserted-by":"crossref","unstructured":"Decker, C., Wattenhofer, R.: A fast and scalable payment network with bitcoin duplex micropayment channels. In: Pelc, A., Schwarzmann, A.A. (eds.) Stabilization. Safety, and Security of Distributed Systems, pp. 3\u201318. Springer, Cham (2015)","DOI":"10.1007\/978-3-319-21741-3_1"},{"key":"686_CR19","unstructured":"DeCred. Decred cross-chain atomic swapping"},{"issue":"2","key":"686_CR20","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1145\/42282.42283","volume":"35","author":"C Dwork","year":"1988","unstructured":"Dwork, C., Lynch, N., Stockmeyer, L.: Consensus in the presence of partial synchrony. J. ACM 35(2), 288\u2013323 (1988)","journal-title":"J. ACM"},{"key":"686_CR21","unstructured":"Ethereum"},{"key":"686_CR22","unstructured":"Evans, A.: A crash course in mechanism design for cryptoeconomic applications (2017)"},{"key":"686_CR23","doi-asserted-by":"crossref","unstructured":"Fischer, M.\u00a0J., Lynch, N.\u00a0A., and Paterson, M.\u00a0S.: Impossibility of distributed consensus with one faulty process. J. ACM, 32(2), 374\u2013382, 1985. Number of pages: 9 Publisher: ACM tex.acmid: 214121 tex.address: New York, NY, USA tex.issue\\_date (1985)","DOI":"10.1145\/3149.214121"},{"key":"686_CR24","unstructured":"Ford, B., B\u00f6hme, R.: Rationality is Self-Defeating in Permissionless Systems. arXiv:1910.08820 [cs], arXiv:1910.08820 (2019)"},{"key":"686_CR25","unstructured":"Foundation, E.: ERC20 token standard (2019)"},{"key":"686_CR26","doi-asserted-by":"crossref","unstructured":"Franklin, M.K. and Tsudik, G.: Secure group barter: multi-party fair exchange with semi-trusted neutral parties. In Financial Cryptogrphy (1998)","DOI":"10.1007\/BFb0055475"},{"key":"686_CR27","doi-asserted-by":"crossref","unstructured":"Gilad, Y., Hemo, R., Micali, S., Vlachos, G., Zeldovich, N.: Algorand: Scaling byzantine agreements for cryptocurrencies. In Proceedings of the 26th Symposium on Operating Systems Principles, SOSP \u201917, pages 51\u201368, New York, NY, USA, ACM (2017)","DOI":"10.1145\/3132747.3132757"},{"key":"686_CR28","doi-asserted-by":"crossref","unstructured":"Green, M., Miers, I., Bolt: Anonymous payment channels for decentralized currencies. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (2017)","DOI":"10.1145\/3133956.3134093"},{"issue":"4","key":"686_CR29","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1145\/289.291","volume":"15","author":"T Haerder","year":"1983","unstructured":"Haerder, T., Reuter, A.: Principles of transaction-oriented database recovery. ACM Comput. Surv. 15(4), 287\u2013317 (1983)","journal-title":"ACM Comput. Surv."},{"key":"686_CR30","doi-asserted-by":"crossref","unstructured":"Heilman, E., Lipmann, S., Goldberg, S.: The arwen trading protocols (2019)","DOI":"10.1007\/978-3-030-51280-4_10"},{"key":"686_CR31","doi-asserted-by":"crossref","unstructured":"Herlihy, M.: Atomic cross-chain swaps. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC \u201918, pages 245\u2013254, New York, NY, USA. ACM. Number of pages: 10 Place: Egham, United Kingdom tex.acmid: 3212736 (2018)","DOI":"10.1145\/3212734.3212736"},{"key":"686_CR32","unstructured":"Investopedia. UTXO (2019)"},{"key":"686_CR33","doi-asserted-by":"crossref","unstructured":"Kiayias, A., Lamprou, N., Stouka, A.-P.: Proofs of proofs of work with sublinear complexity. In International Conference on Financial Cryptography and Data Security (2016)","DOI":"10.1007\/978-3-662-53357-4_5"},{"key":"686_CR34","doi-asserted-by":"crossref","unstructured":"Kiayias, A., Miller, A., Zindros, D.: Non-interactive Proofs of Proof-of-Work. In: Bonneau, J., Heninger, N. (eds.) Financial Cryptography and Data Security. Lecture Notes in Computer Science, pp. 505\u2013522. Springer International Publishing, Cham (2020)","DOI":"10.1007\/978-3-030-51280-4_27"},{"key":"686_CR35","doi-asserted-by":"crossref","unstructured":"Kokoris\u00a0Kogias, E., Jovanovic, P.S., Gasser, L., Gailly, N., Syta, E., Ford, B.A., OmniLedger: A secure, scale-out, decentralized ledger via sharding. In 2018 IEEE Symposium on Security and Privacy (SP), page\u00a016 (2018)","DOI":"10.1109\/SP.2018.000-5"},{"key":"686_CR36","unstructured":"Krishna, V.: Auction theory. Academic Press\/Elsevier, Burlington, MA, 2nd ed edition, OCLC: ocn326688263 (2010)"},{"key":"686_CR37","doi-asserted-by":"crossref","unstructured":"Lind, Y., Eyal, I., Kelbert, F., Naor, O., Pietzuch, P.R., Sirer, E.G., Teechain: Scalable blockchain payments using trusted execution environments. CoRR, abs\/1707.05454 (2017)","DOI":"10.1145\/3211890.3211904"},{"key":"686_CR38","doi-asserted-by":"crossref","unstructured":"Micali, S.: Simple and fast optimistic protocols for fair electronic exchange. In Proceedings of the Twenty-Second Annual Symposium on Principles of Distributed Computing, PODC \u201903, pages 12\u201319, New York, NY, USA. ACM. Number of pages: 8 Place: Boston, Massachusetts tex.acmid: 872038 (2003)","DOI":"10.1145\/872035.872038"},{"key":"686_CR39","unstructured":"Nakamoto, S.: Bitcoin: A peer-to-peer electronic cash system (2009)"},{"key":"686_CR40","unstructured":"Network, R.: What is the raiden network?"},{"key":"686_CR41","doi-asserted-by":"crossref","unstructured":"Nisan, N.: (Eds) Algorithmic Game Theory. Cambridge University Press, Cambridge ; New York. OCLC: ocn122526907 (2007)","DOI":"10.1017\/CBO9780511800481"},{"key":"686_CR42","unstructured":"Nolan, T.: Atomic swaps using cut and choose (2016)"},{"key":"686_CR43","unstructured":"Organization, T.K.: The BarterDEX whitepaper: a decentralized, open-source cryptocurrency exchange, powered by atomic-swap technology"},{"key":"686_CR44","unstructured":"Peterson, J., Krug, J., Zoltu, M., Williams, A.K., Alexander, S., Augur: a decentralized oracle and prediction market platform (2018)"},{"key":"686_CR45","unstructured":"Poon, J., Dryja, T.: The bitcoin lightning network: Scalable off-chain instant payments (2016)"},{"key":"686_CR46","unstructured":"Solidity documentation"},{"key":"686_CR47","unstructured":"Tendermint (2015)"},{"key":"686_CR48","unstructured":"The Committee for the Prize in Economic Sciences in Memory of Alfred Nobel. Improvements to Auction Theory and Inventions of New Auction Formats (2020)"},{"key":"686_CR49","unstructured":"Wikipedia. Mt. Gox (2019)"},{"key":"686_CR50","unstructured":"Wikipedia. Quadriga fintech solutions (2019)"},{"key":"686_CR51","unstructured":"Wikipedia. Tether (cryptocurrency) (2020)"},{"key":"686_CR52","first-page":"1","volume":"151","author":"G Wood","year":"2014","unstructured":"Wood, G.: Ethereum: a secure decentralised generalised transaction ledger. Ethereum project yellow paper 151, 1\u201332 (2014)","journal-title":"Ethereum project yellow paper"},{"key":"686_CR53","doi-asserted-by":"crossref","unstructured":"Xue, Y., Herlihy, M.: Hedging against sore loser attacks in cross-chain transactions. In ACM Symposium on Principles of Distributed Computing (2021)","DOI":"10.1145\/3465084.3467904"},{"key":"686_CR54","unstructured":"Zakhary, V., Agrawal, D., El\u00a0Abbadi, A.: Atomic commitment across blockchains. CoRR (2019). ArXiv:1905.02847. tex.bibsource: dblp computer science bibliography, https:\/\/dblp.org tex.biburl: https:\/\/dblp.org\/rec\/bib\/journals\/corr\/abs-1905-02847 tex.timestamp (2019)"},{"key":"686_CR55","unstructured":"Zyskind, G., Kisagun, C., FromKnecht, C.: Enigma Catalyst: a machine-based investing platform and infrastructure for crypto-assets"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-021-00686-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-021-00686-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-021-00686-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,21]],"date-time":"2022-10-21T07:23:29Z","timestamp":1666337009000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-021-00686-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,20]]},"references-count":55,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["686"],"URL":"https:\/\/doi.org\/10.1007\/s00778-021-00686-1","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,20]]},"assertion":[{"value":"29 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 May 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 May 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 August 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}