This article explains the paper [Herlihy, 2018]1 in simple words. In the paper, Herlihy has introduced an effective atomic cross-chain swap protocol in order to exchange assets across multiple blockchains among multiple parties.

Model

A swap can be modeled using a directed graph $(V, A)$. $V$ is a set of involved users, and $A$ is a set of payments. Each payment is annotated as $(u, v)$ where $u$ is the payer and $v$ is the payee. The Atomic Swap Protocol ensures that when all users follow the protocol, if one payment succeeds, all other payments must succeed.

For example, following model represents a swap that Alice sends a payment to Bob, and Bob sends a payment to Carol.

[ \begin{array}{rl} V &= {\mathrm{Alice}, \mathrm{Bob}, \mathrm{Carol}} \ A &= {(\mathrm{Alice},\mathrm{Bob}), (\mathrm{Bob}, \mathrm{Carol})} \end{array} ]

Simple Protocol

When all payments can be connected into a path, like the example above, the protocol is simple and is similar to the payment hops in lightning network.

A path is annotated as $(u1, \ldots, u_l)$, which is consisted of $l-1$ payments: $(u_1, u_2),(u_2, u_3),\ldots,(u{l-1}, u_l)$.

The final payee $ul$ generates a secret $s$ and sends its hash $H(s)$ to the payer $u_1$. The payer $u_1$ creates a Hash Time Locked Contract $(H(s), 2(l-1)\Delta)$ that either $u_2$ can get the fund by providing the secret $s$, or $u_1$ can get the refund when time has elapsed $2(l-1)\Delta$ units. The users $u_i$ from $u_2$ to $u{l-2}$ creates a Hash Time Locked Contract $(H(s), 2(l-i)\Delta)$ when they confirm that they have received the inbound contract. The payee $ul$ can settle the deal by providing the secret $s$ to $u{l-1}$, and each user uses the received secret $s$ to settle their inbound contract.

The simple protocol also works when payee and payer are the same user ($u_1 = u_l$). From engineering points, it should work for most scenarios.

Arbitrary Connected Directed Graph

The paper also extends the swap protocol to arbitrary connected directed graph. A connected directed graph means for any two user $u, v$, there are a payment path from $u$ to $v$, and a payment path from $v$ to $u$. Such directed graphs contain loops, as in the example below:

[ \begin{array}{rl} V = {&A, B, C, D, E, F} \ A = { \ &(A, B), (B, C), (C, A), \ &(C, D), (D, B), \ &(D, E), (E, F), (F, D) \ } \ \end{array} ]

Leaders Selection

The protocol must select a Feedback Vertex Set of the directed graph as leaders. A feedback vertex set is a subset of $V$ that once removed from the graph, there will be no loops in the graph. For example, $(B, D)$ is a feedback vertex set of the example above. When there are multiple candidates, choose an arbitrary set.

The leaders generate secrets and publish their hashes. If $(B, D)$ are selected, they should publish $(H(s_B), H(s_D))$.

The protocol then move forward in two phases.

Phase One

In the first phase, users offer outbound contracts to counterparty for each payment.

Leaders must offer contracts first:

Publish a contract on every outbound payments, then

wait until all inbound contracts have been published.

Followers must confirm inbound contracts first:

Wait until correct inbound contracts have been published, then

publish a contract on every outbound payments.

The contracts are Hash Time Locked Contracts $(h, t)$ that payee can get the fund using the proof to unlock $h$, or the payer gets the refund after timeout $t$.

For a payment $(u, v)$, the proof of $h$ is a triple $(s, p, \sigma)$ where

$p$ is any payment path $(u_0, \ldots, u_k)$ starting from the payee $v$ ($u_0 = v$) to a leader $u_k$. The path $p$ can have a length of 0 if $v$ itself is a leader.

$s$ is the secret generated by the ending leader of the path $p$, and $h = H(s)$.

$\sigma$ is a nested signatures of $s$ signed by users in the path $p$.

The innest signature is $\mathrm{sig}_k = \mathit{sig}(s, u_k)$

For user $ui$ ($0 \leq i \leq k - 1$), the signature is $\mathrm{sig}_i = \mathit{sig}(\mathrm{sig}{i+1}, u_i)$

$\sigma = \mathrm{sig}_0$

The hash lock $h$ can be set to $H(s)$ for the shortest $p$, or just the hashes of all secrets to all unlocking using arbitrary ending leader of the path $p$.

The time lock $t$ is $(\mathit{diam}(\mathcal{D}) + |p|)\Delta$, where

$\mathit{diam}(\mathcal{D})$ is the longest length of a payment path without duplicated users in the directed graph.

$|p|$ is the length of the path $p$ in the hash lock.

$\Delta$ is a configured time unit constant for the time out.

Let’s see two examples.

The first example is the payment from a leader: $(B, C)$.

There are three candidate path $p$ from the payee $C$ to a leader either $B$ or $D$:

$(C, A, B)$

$(C, D)$

$(C, D, B)$

$B$ can choose any one, but the shortest one is recommended. Let’s use $(C, D)$. $B$ can publish the contract because he/she is the leader.

The hash lock for $(B, C)$ is $H(s_D)$.

The time lock is $6\Delta$, because the length of the longest path $(A, B, C, D, E, F)$ is 5, and the length of $(C, D)$ is 1.

The second example is the payment from a follower: $(C, A)$.

$C$ can choose the path $(A, B)$ and publish the contract:

The hash lock is $H(s_B)$.

The time lock is $6\Delta$

Phase Two

In phase two, leaders can unlock the inbound contracts because they know all secrets. For example, the leader $B$ can unlock the inbound payment $(A, B)$ by offering:

The path $p = (B)$

The secret $s_B$

The signature $sig(s_B, B)$

Followers must trace outbound contracts unlocking events. For example, $A$ can unlock the contract for $(C, A)$ after receiving the unlocking event above:

The path $p = (A, B)$

The secret $s_B$ since B has published it when unlocking $(A, B)$.

The signature $sig(sig(s_B, B), A)$

Herlihy, M. (2018). Atomic Cross-Chain Swaps (No. arXiv:1801.09515). arXiv. https://doi.org/10.48550/arXiv.1801.09515

Open in Zotero

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 parties. An atomic cross-chain swap protocol guarantees; (1) if all parties conform to the protocol, then all assets are exchanged among 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. Herlihy's protocol uses the graph topology and signature information to set appropriate hashed timelock contracts. The space complexity of the protocol (i.e., the total number of bits written in the blockchains in a swap) is O(|A|^2). The local time complexity of the protocol (i.e., the maximum execution time of a contract in a swap to transfer the corresponding asset) is O(|V||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||V|) and the local time complexity to O(|V|).

Open in Zotero

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)$.