Explain Atomic Cross-Chain Swaps by Herlihy

This article explains the paper [Herlihy, 2018]¹ 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 $(u_1, \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 $u_l$ 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 $u_l$ 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:

1. Publish a contract on every outbound payments, then
2. wait until all inbound contracts have been published.

Followers must confirm inbound contracts first:

1. Wait until correct inbound contracts have been published, then
2. 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 $u_i$ ($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$:

1. $(C, A, B)$
2. $(C, D)$
3. $(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)$