Atomic cross-chain swaps with improved space, time and local time complexities

【Author】 Imoto, Soichiro; Sudo, Yuichi; Kakugawa, Hirotsugu; Masuzawa, Toshimitsu

【Source】INFORMATION AND COMPUTATION

【影响因子】1.240

【Abstract】An 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 protocol guarantees; (1) if all parties conform to the protocol, then all assets are exchanged among the parties, (2) even if some parties or coalitions of parties deviate from the protocol, no party conforming to the protocol suffers a loss, and (3) no coalition has an incentive to deviate from the protocol. Herlihy [Herlihy, 2018] invented this protocol by using hashed timelock contracts. A cross-chain swap is modeled as a directed graph D = (V, A). Vertex set V denotes a set of parties and arc set A denotes a set of proposed asset transfers. Let A be time enough for a party to publish a contract on any of the blockchains, or to change the state of a contract and for the other party to detect the change. The space complexity of the protocol is O(|A|2). The local time complexity of the protocol is O(|V | center dot |L|), where L is a feedback vertex set computed by the protocol. We propose a new atomic cross-chain swap protocol which uses only signature information and improves the space complexity to O(|A| center dot |V |) and the local time complexity to O(| V |). Moreover, if all parties conform to our protocol, our proposed protocol improves the time complexity from O (| V |A) to O(A). (c) 2023 Elsevier Inc. All rights reserved.

【Keywords】Blockchain; Atomic cross -chain swap; Smart contract; Hashed timelock contract

【发表时间】2023 JUN

【收录时间】2023-06-27

【文献类型】理论性文章

【主题类别】

区块链技术-核心技术-跨链与多链