{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T08:04:21Z","timestamp":1761897861076,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,4,8]],"date-time":"2023-04-08T00:00:00Z","timestamp":1680912000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,4,8]],"date-time":"2023-04-08T00:00:00Z","timestamp":1680912000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001773","name":"University of New South Wales","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001773","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper, we consider the problem of cross-chain payment whereby customers of different escrows\u2014implemented by a bank or a blockchain smart contract\u2014successfully transfer digital assets without trusting each other. Prior to this work, cross-chain payment problems did not require this success, or any form of progress. We introduce a new specification formalism called <jats:italic>Asynchronous Networks of Timed Automata<\/jats:italic> to formalise such protocols. We present the first cross-chain payment protocol that ensures termination in a bounded amount of time and works correctly in the presence of clock drift. We then demonstrate that it is impossible to solve this problem without assuming synchrony, in the sense that each message is guaranteed to arrive within a known amount of time. Yet, we solve an eventually terminating weaker variant of this problem, where success is conditional on the patience of the participants, without assuming synchrony, and in the presence of Byzantine failures. We also discuss the relation with the recently defined cross-chain deals.<\/jats:p>","DOI":"10.1007\/s00446-023-00446-0","type":"journal-article","created":{"date-parts":[[2023,4,8]],"date-time":"2023-04-08T19:02:37Z","timestamp":1680980557000},"page":"137-157","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Cross-chain payment protocols with success guarantees"],"prefix":"10.1007","volume":"36","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4712-7423","authenticated-orcid":false,"given":"Rob","family":"van Glabbeek","sequence":"first","affiliation":[]},{"given":"Vincent","family":"Gramoli","sequence":"additional","affiliation":[]},{"given":"Pierre","family":"Tholoniat","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,4,8]]},"reference":[{"issue":"2","key":"446_CR1","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0304-3975(94)90010-8","volume":"126","author":"R Alur","year":"1994","unstructured":"Alur, R., Dill, D.L.: A theory of timed automata. Theor. Comput. Sci. 126(2), 183\u2013235 (1994). https:\/\/doi.org\/10.1016\/0304-3975(94)90010-8","journal-title":"Theor. Comput. Sci."},{"key":"446_CR2","unstructured":"Avarikioti, G., Kogias, E. K., Wattenhofer, R., Zindros, D.: Brick: asynchronous payment channels (2020). arXiv:1905.11360"},{"key":"446_CR3","doi-asserted-by":"publisher","unstructured":"Bengtsson, J., Larsen, K., Larsson, F., Pettersson, P., Wang, Y.: UPPAAL\u2014a tool suite for automatic verification of real-time systems. In: Alur, R., Henzinger, T.A., Sontag, E.D. (eds.) Hybrid Systems III: Verification and Control, Proceedings of the DIMACS\/SYCON Workshop on Verification and Control of Hybrid Systems, October 1995, LNCS, vol. 1066, pp. 232\u2013243. Springer (1996). https:\/\/doi.org\/10.1007\/BFb0020949","DOI":"10.1007\/BFb0020949"},{"issue":"2","key":"446_CR4","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/0890-5401(87)90054-X","volume":"75","author":"G Bracha","year":"1987","unstructured":"Bracha, G.: Asynchronous Byzantine agreement protocols. Inf. Comput. 75(2), 130\u2013143 (1987). https:\/\/doi.org\/10.1016\/0890-5401(87)90054-X","journal-title":"Inf. Comput."},{"key":"446_CR5","doi-asserted-by":"crossref","unstructured":"Cholvi, V., Anta, A. F., Georgiou, C., Nicolaou, N., Raynal, M.: Atomic appends in asynchronous Byzantine distributed ledgers. In: Proceedings of the 16th European Dependable Computing Conference (EDCC), pp. 77\u201384 (2020)","DOI":"10.1109\/EDCC51268.2020.00022"},{"issue":"2","key":"446_CR6","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1145\/42282.42283","volume":"35","author":"C Dwork","year":"1988","unstructured":"Dwork, C., Lynch, N.A., Stockmeyer, L.J.: Consensus in the presence of partial synchrony. J. ACM 35(2), 288\u2013323 (1988). https:\/\/doi.org\/10.1145\/42282.42283","journal-title":"J. ACM"},{"key":"446_CR7","unstructured":"Fern\u00e1ndez Anta, A., Georgiou, C., Nicolaou, N.: Atomic appends: selling cars and coordinating armies with multiple distributed ledgers (2018). arXiv:1812.08446"},{"key":"446_CR8","doi-asserted-by":"publisher","unstructured":"Gazi, P., Kiayias, A., Zindros, D.: Proof-of-stake sidechains. In: 2019 IEEE Symposium on Security and Privacy, SP 2019, pp. 139\u2013156. IEEE (2019). https:\/\/doi.org\/10.1109\/SP.2019.00040","DOI":"10.1109\/SP.2019.00040"},{"key":"446_CR9","doi-asserted-by":"publisher","unstructured":"van Glabbeek, R., Gramoli, V., Tholoniat, P.: Feasibility of cross-chain payment with success guarantees. In: Proceedings 32nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2020, pp. 579\u2013581. ACM (2020). https:\/\/doi.org\/10.1145\/3350755.3400264","DOI":"10.1145\/3350755.3400264"},{"issue":"1","key":"446_CR10","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1145\/1132863.1132867","volume":"31","author":"J Gray","year":"2006","unstructured":"Gray, J., Lamport, L.: Consensus on transaction commit. ACM Trans. Datab. Syst. 31(1), 133\u2013160 (2006). https:\/\/doi.org\/10.1145\/1132863.1132867","journal-title":"ACM Trans. Datab. Syst."},{"key":"446_CR11","doi-asserted-by":"publisher","unstructured":"Guerraoui, R.: Revisiting the relationship between non-blocking atomic commitment and consensus. In: H\u00e9lary, J.M., Raynal, M. (eds.) Proceedings of the 9th International Workshop on Distributed Algorithms (WDAG), LNCS, vol. 972, pp. 87\u2013100. Springer (1995). https:\/\/doi.org\/10.1007\/BFb0022140","DOI":"10.1007\/BFb0022140"},{"key":"446_CR12","doi-asserted-by":"publisher","unstructured":"Hadzilacos, V.: On the relationship between the atomic commitment and consensus problems. In: Proceedings of the Asilomar Workshop on Fault-Tolerant Distributed Computing, LNCS, pp. 201\u2013208. Springer (1990). https:\/\/doi.org\/10.1007\/BFb0042336","DOI":"10.1007\/BFb0042336"},{"key":"446_CR13","doi-asserted-by":"publisher","unstructured":"Herlihy, M.: Atomic cross-chain swaps. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC, pp. 245\u2013254 (2018). https:\/\/doi.org\/10.1145\/3212734.3212736","DOI":"10.1145\/3212734.3212736"},{"issue":"2","key":"446_CR14","doi-asserted-by":"publisher","first-page":"100","DOI":"10.14778\/3364324.3364326","volume":"13","author":"M Herlihy","year":"2019","unstructured":"Herlihy, M., Liskov, B., Shrira, L.: Cross-chain deals and adversarial commerce. Proc. VLDB Endow. 13(2), 100\u2013113 (2019). https:\/\/doi.org\/10.14778\/3364324.3364326. arXiv:1905.09743v5","journal-title":"Proc. VLDB Endow."},{"key":"446_CR15","doi-asserted-by":"publisher","unstructured":"Kiayias, A., Zindros, D.: Proof-of-work sidechains. In: Bracciali, A., Clark, J., Pintore, F., R\u00f8nne, P.B., Sala, M. (eds.) Financial Cryptography and Data Security, Revised Selected Papers. Financial Cryptography Workshops 2019, LNCS, pp. 21\u201334. Springer (2020). https:\/\/doi.org\/10.1007\/978-3-030-43725-1_3","DOI":"10.1007\/978-3-030-43725-1_3"},{"key":"446_CR16","doi-asserted-by":"publisher","unstructured":"Krc\u00e1l, P., Yi, W.: Communicating timed automata: the more synchronous, the more difficult to verify. In: Ball, T., Jones, R.B. (eds.) Proceedings of 18th International Conference on Computer Aided Verification, CAV\u201906, LNCS, vol. 4144, pp. 249\u2013262. Springer (2006). https:\/\/doi.org\/10.1007\/11817963_24","DOI":"10.1007\/11817963_24"},{"key":"446_CR17","doi-asserted-by":"publisher","unstructured":"Lind, J., Naor, O., Eyal, I., Kelbert, F., Pietzuch, P., Sirer, E.: Teechain: reducing storage costs on the blockchain with offline payment channels. In: Proceedings of the 11th ACM International Systems and Storage Conference, p. 125, ACM (2018). https:\/\/doi.org\/10.1145\/3211890.3211904","DOI":"10.1145\/3211890.3211904"},{"key":"446_CR18","doi-asserted-by":"publisher","unstructured":"Lynch, N.: Input\/output automata: basic, timed, hybrid, probabilistic, dynamic. In: Amadio, R.M., Lugiez, D. (eds.) Proceedings of the International Conference on Concurrency Theory (CONCUR), LNCS, vol. 2761, pp. 191\u2013192 (2003). https:\/\/doi.org\/10.1007\/978-3-540-45187-7_12","DOI":"10.1007\/978-3-540-45187-7_12"},{"key":"446_CR19","doi-asserted-by":"publisher","unstructured":"van der Meyden, R.: On the specification and verification of atomic swap smart contracts (extended abstract). In: Proceedings of the IEEE International Conference on Blockchain and Cryptocurrency, ICBC, pp. 176\u2013179 (2019). https:\/\/doi.org\/10.1109\/BLOC.2019.8751250","DOI":"10.1109\/BLOC.2019.8751250"},{"key":"446_CR20","volume-title":"Communication and Concurrency","author":"R Milner","year":"1989","unstructured":"Milner, R.: Communication and Concurrency. Prentice Hall, Englewood Cliffs (1989)"},{"key":"446_CR21","unstructured":"Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system (2008)"},{"key":"446_CR22","unstructured":"Poon, J., Dryja, T.: The bitcoin lightning network: scalable off-chain instant payments, Draft Version 0.5.9.2 (2016). https:\/\/lightning.network\/lightning-network-paper.pdf"},{"key":"446_CR23","doi-asserted-by":"crossref","unstructured":"Ranchal-Pedrosa, A., Gramoli, V.: Platypus: offchain protocol without synchrony. In: Proceeding of the 18th IEEE International Symposium on Network Computing and Applications, NCA (2019). arXiv:1907.03730","DOI":"10.1109\/NCA.2019.8935037"},{"key":"446_CR24","unstructured":"Thomas, S., Schwartz, E.: A protocol for interledger payments. Whitepaper (2015). https:\/\/interledger.org\/interledger.pdf"},{"key":"446_CR25","unstructured":"Wood, Gavin: Polkadot: Vision for a heterogeneous multi-chain framework. White Paper (2016). https:\/\/polkadot.network\/PolkaDotPaper.pdf"},{"key":"446_CR26","doi-asserted-by":"crossref","unstructured":"Zakhary, V., Agrawal, D., El Abbadi, A.: Atomic commitment across blockchains. Proc. VLDB Endow. 13(9), 1319\u20131331 (2020). https:\/\/doi.org\/10.14778\/3397230.3397231","DOI":"10.14778\/3397230.3397231"},{"key":"446_CR27","doi-asserted-by":"publisher","unstructured":"Zamyatin, A., Al-Bassam, M., Zindros, D., Kokoris-Kogias, E., Moreno-Sanchez, P., Kiayias, A., Knottenbelt, W.J.: SoK: communication across distributed ledgers. In: Borisov, N., Diaz, C. (eds.) Proceedings of the 25th International Conference on Financial Cryptography and Data Security (FC\u201921), LNCS, vol. 12675, pp. 3\u201336. Springer (2021). https:\/\/doi.org\/10.1007\/978-3-662-64331-0_1","DOI":"10.1007\/978-3-662-64331-0_1"},{"key":"446_CR28","doi-asserted-by":"publisher","unstructured":"Zamyatin, A., Harz, D., Lind, J., Panayiotou, P., Gervais, A., Knottenbelt, W.J.: XCLAIM: trustless, interoperable, cryptocurrency-backed assets. In: 2019 IEEE Symposium on Security and Privacy, SP\u201919, San Francisco, USA, pp. 193\u2013210 (2019). https:\/\/doi.org\/10.1109\/SP.2019.00085","DOI":"10.1109\/SP.2019.00085"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-023-00446-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-023-00446-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-023-00446-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,15]],"date-time":"2023-05-15T15:27:43Z","timestamp":1684164463000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-023-00446-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,8]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["446"],"URL":"https:\/\/doi.org\/10.1007\/s00446-023-00446-0","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2023,4,8]]},"assertion":[{"value":"26 September 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 February 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 April 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}