# On HTLC-Based Protocols for Multi-Party Cross-Chain Swaps††thanks: Research
supported by NSF grant CCF-2153723.

Emily Clark  University of California at Riverside  Chloe Georgiou  University
of California at Riverside  Katelyn Poon  University of California at
Riverside  Marek Chrobak  University of California at Riverside

###### Abstract

In his 2018 paper, Herlihy introduced an atomic protocol for multi-party asset
swaps across different blockchains. His model represents an asset swap by a
directed graph whose nodes are the participating parties and edges represent
asset transfers, and rational behavior of the participants is captured by a
preference relation between a protocol’s outcomes. Asset transfers between
parties are achieved using smart contracts. These smart contracts are quite
intricate and involve solving computationally intensive graph problems,
limiting practical significance of his protocol. His paper also describes a
different protocol that uses only standard hash time-lock contracts (HTLC’s),
but this simpler protocol applies only to some special types of digraphs. He
left open the question whether there is a simple and efficient protocol for
cross-chain asset swaps in arbitrary digraphs. Motivated by this open problem,
we conducted a comprehensive study of _HTLC-based protocols_ , in which all
asset transfers are implemented with HTLCs. Our main contribution is a full
characterization of swap digraphs that have such protocols.

##  1 Introduction

In his 2018 paper [8], Herlihy introduced a model for multi-party asset swaps
across different blockchains. In this model an asset swap is represented by a
strongly connected directed graph (digraph), with each vertex corresponding to
one party and each arc representing a pre-arranged asset transfer between two
parties. Given such a digraph, the goal is to design a protocol to implement
the transfer of all assets. There is no guarantee that all parties will follow
the protocol — some parties may attempt to cheat, even colluding between
themselves, or behave irrationally. The protocol must guarantee, irrespective
of the behavior of other parties, that each honest party will end up with an
outcome that it considers acceptable. The protocol should also discourage
cheating, so that any coalition of parties cannot improve its outcome by
deviating from the protocol. These two conditions are called _safety_ and
_strong Nash equilibrium_ , respectively. A protocol that satisfies these
conditions is called _atomic_ (see the formal definitions in Section 3).

In this model, Herlihy [8] developed an atomic protocol for multi-party asset
swaps in arbitrary strongly connected digraphs. This result constitutes a
major advance in our understanding of fundamental principles of asset swaps,
as it shows that it is possible, in principle, to securely implement complex
transactions involving multiple parties even if their assets are hosted on
multiple blockchains. Yet the practical significance of his protocol is
limited due to its intricacy and high computational complexity. Asset
transfers in this protocol are realized via smart contracts that need to store
and process the whole swap digraph, and designing these contracts involves
solving $\mathbb{NP}$-hard graph problems, like finding long paths or a small
feedback vertex set. To achieve the safety property, it uses an elaborate
cryptographic scheme involving nested digital signatures. Another concern is
privacy: since the execution of the protocol requires the parties to know the
topology of the whole swap digraph, they also receive information about asset
transfers between other parties.

Herlihy’s paper [8] also mentions a simplified and more efficient version of
his protocol. In terms of cryptographic tools, this simpler protocol uses only
standard smart contracts called _hash time-lock contracts_ (HTLC’s), that
require only one secret/hashlock pair and a time-out mechanism. This protocol,
however, has only limited applicability: it works correctly only for special
types of digraphs, that we call _bottleneck digraphs_ in our paper111Herlihy
calls such graphs _single-leader digraphs._. These are strongly connected
digraphs in which all cycles overlap on at least one vertex.

This raises a natural question, already posed in [8]: _Is there a simple and
efficient protocol for multi-party asset swaps that is atomic and works on all
strongly connected digraphs?_

_Our contributions._ Our work was motivated by the above question.
Specifically, the question we address is this: _Is it possible to solve the
cross-chain swap problem with an atomic protocol that is computationally
efficient and uses only HTLCs for asset transfers?_ We show that, while such
HTLC-based protocols are not possible for arbitrary digraphs, the class of
digraphs that have such protocols is much broader than just bottleneck
digraphs. In fact, we give a complete characterization of digraphs that have
HTLC-based protocols. We call them _reuniclus graphs_ 222Graphical
representations of these digraphs resemble visually a type of Pokemon called
Reuniclus.. A reuniclus graph consists of a number of (weakly) biconnected
components, with each component being an induced bottleneck subgraph. These
components form a hierarchical tree-like structure, where the bottleneck of
each non-root component is an articulation vertex belonging to its parent
component. (See the formal definition in Section 4.2).

To establish our characterization, we need to formalize the concepts of HTLCs
and HTLC-based protocols. In our model, an HTLC is a smart contract used to
transfer an asset from its seller to its buyer that (roughly) works like this:
After it’s created by the seller, the contract stores (escrows) this asset
secured with a hashlock value and with a timeout (expiration) value, both
provided by the seller. To claim this asset, the buyer must provide a secret
value that matches the hashlock. If the asset is not successfully claimed by
the buyer before its timeout, the contract automatically returns the asset to
the seller. In a HTLC-based protocol, all asset transfers are implemented with
HTLCs, and each party is allowed to generate one secret/hashlock pair, with
the hashlock value obtained from the secret value using a one-way permutation.

In this terminology, our main contribution can be stated as follows:

######  Theorem 1.

A swap digraph $G$ has an atomic HTLC-based protocol if and only if $G$ is a
reuniclus digraph.

The proof of Theorem 1 conists of two parts. The sufficiency condition is
proved in Section 4, where we provide an HTLC-based atomic protocol for asset
swaps in reuniclus digraphs. Our most technically challenging contribution is
the proof of the necessity condition, presented in Section 5. This proof shows
that non-reuniclus digraphs do not have atomic HTLC-protocols for asset swaps.

Along the way we also obtain a full characterization of digraphs that admit
HTLC-protocols when only one party is allowed to create a secret/hashlock
pair. Herlihy [8] showed that bottleneck graphs have such protocols. We
complement this result by proving that the bottleneck property is also
necessary.

Our asset-swap model is in fact a slight generalization of the one in [8], as
it uses a relaxed definition of the preference relation, which allows each
party to customize some of the preferences between its outcomes. As we explain
in Section 3, all crucial properties of the model in [8] remain valid. Among
these, the most critical is given in Lemma 1, which says that in this model
the strong Nash equlibrium property is in essence a consequence of the safety
property of a protocol; thus, in a way, it comes “for free”.

_Related work._ The problem of securely exchanging digital products between
two untrustful parties has been studied since 1990s under the name of _fair
exchange_. As simultaneous exchange is not feasible in a typical electronic
setting, protocols for fair exchage rely on a trusted party and use
cryptographic tools to reduce the need for this trusted party to interfere –
see for example [12, 6, 3, 1, 2]. In the asset-swap model from [8], adopted in
our paper, one can think of smart contracts as playing the role of trusted
parties.

Starting in early 2000’s, with different users holding assets on a quickly
growing number of different blockchains, cross-chain interoperability tools
became necessary to allow these users to trade their assets. An atomic swap
concept was one of the proposed tools to address this issue. The concept
itself and some early implementations of asset-swap protocols (see, for
example [14]) predate the work of Herlihy [8], although his paper was first to
provide systematic treatment of such protocols and extend it to multiple
parties.

In recent years there has been intensive research activity aimed at improving
various aspects of asset-swap protocols. The preference relation of the
participants in the model from [8] is very rudimentary, and some refinements
of this preference model were studied in [4, 10]. Some proposals [11, 15]
address the issue of “ griefing”, when one party needs to wait for the
counter-party to act, while its assets are locked and unaccessible. Other
directions of study include investigations of protocol’s time and space
complexity [10], privacy issues [5], and generalizations of swaps to more
complex transactions [9, 13, 7].

##  2 Graph Terminology

Let $G=(V,A)$ be a digraph with vertex set $V$ and arc set $A$. Throughout the
paper we assume that digraphs do not have self-loops or parallel arcs. If
$(u,v)\in A$ is an arc, we refer to $v$ as an _out-neighbor_ of $u$ and to $u$
as an _in-neighbor_ of $v$. By ${N_{v}^{in}}$ we denote the set of in-
neighbors of $v$, by ${A_{v}^{in}}$ its set of in-coming arcs, ${N_{v}^{out}}$
are the out-neighbors of $v$ and ${A_{v}^{out}}$ are its outgoing arcs.

To simplify notation, for a vertex $v$ we will sometimes write $u\in G$
instead of $v\in V$. Similarly, for an arc $(u,v)$, notation $(u,v)\in G$
means that $(u,v)\in A$.

We use standard terminology for directed graphs. A path in $G$ is a sequence
of vertices, each (except last) having an arc to the next one, without
repeating an arc. A cycle is a path in which the last vertex is equal to the
first one. A _simple path_ is a path that does not repeat a vertex. A _simple
cycle_ is a cycle where all vertices are different except the first and last
being equal.

A digraph $H=(V^{\prime},A^{\prime})$ is a subgraph of $G$ if
$V^{\prime}\subseteq V$ and $A^{\prime}\subseteq A$. $H$ is called an _induced
subgraph_ of $G$ if $A^{\prime}$ contains all arcs from $A$ connecting
vertices in $V^{\prime}$. The concept of induced subgraphs will be important.

Recall that a digraph $G$ is called _strongly connected_ if for every pair of
vertices $u$ and $v$ there is a path from $u$ to $v$. We are mostly interested
in strongly connected digraphs.

A set $U\subseteq V$ of vertices is called a _feedback vertex set_ in a
digraph $G$ if every cycle in $G$ includes at least one vertex from $U$.

For a digraph $G$ we will sometimes consider its undirected structure. A
vertex $v$ is caled an _articulation vertex_ of $G$ if removing $v$ from (the
undirected version of) $G$ creates a graph that has more connected components
than $G$. We say that $G$ is _biconnected_ if $G$ is (weakly) connected and
has no articulation vertices.

##  3 Multi-Party Asset Swaps

In broad terms, the _multi-party asset swap problem_ we want to solve is this:
There is a collection $V$ of parties. Each party has a collection of assets
that it wishes to exchange for some other set of assets. For example, Alice
may own a pair of skis and a pair of ski boots that she would like to exchange
for an iPad and a pair of earbuds. (In practice, these are typically digital
assets, like crypto-currency, but we can also consider a scenario where
ownership titles to physical assets are swapped.) Suppose that there is a way
to match these exchanges perfectly, namely to reassign assets from its current
owner to its new owner in such a way that each party will be assigned exactly
their specified collection of desired assets. This reassignment is called a
_multi-party asset swap_. We now would like to design a protocol to arrange
the transfers of all assets in this swap. We do not assume that the parties
are honest. Some parties may not follow the rules of the protocol, attempting
to achieve an outcome better than the one they originally specified. (For
example, they may end up with an extra new asset, or retain some of their own
assets.) Other parties may just behave irrationally. To address this, the
asset-swap protocol must satisfy, at the minimum, the following two
properties: (i) if all parties follow the protocol then all prearranged asset
transfers will take place, and (ii) an outcome of any honest party (that
follows the protocol) is guaranteed to be acceptable (not worse than its
initial holdings), even if some other parties deviate from the protocol or
collaboratively attempt to cheat.

#### Clearing service.

We assume the existence of a _market clearing service_. Each party submits its
proposed exchange (the two collections of its current and desired assets) to
this clearing service. If a multi-party swap is possible, the clearing service
constructs a digraph $G=(V,A)$ representing this swap. Each arc $(u,v)$ of $G$
represents the intended transfer of one asset from its current owner $u$ to
its new owner $v$. (In the context of this transfer, we refer to $u$ as “the
seller” and to $v$ as “the buyer”.) For simplicity, we assume that any party
can transfer only one asset to any other party. This way $G$ does not have any
parallel arcs. In our notations we will also identify assets with arcs, so
$(u,v)$ denotes both an arc of $G$ and the asset of $u$ to be transferred to
$v$. The market clearing service ensures that $G$ is strongly connected and
satisfies other assumptions of the swap protocol, if there are any. It then
informs each party of the steps of the swap protocol that this party should
execute. Importantly, we _do not_ assume that the parties trust the market
clearing service.

#### Secrets and hashlocks.

Our protocols use a cryptographic tool of one-way functions. We allow each
party $v$ to create a _secret value_ $s_{v}$, and convert it into a _hashlock
value_ $h_{v}=H(s_{v})$, where $H()$ is a one-way permutation. The value of
$s_{v}$ is secret, meaning that no other party has the capability to compute
$s_{v}$ from $h_{v}$. The hashlock values can be made public.

#### Hash time-lock contracts (HTLCs).

Asset transfers are realized vwith smart contracts, which in practice are
simply appropriate pieces of code running on a blockchain. For our purpose,
the internal processing within smart contracts is not relevant; in our model
these are just “black-box” objects with a specified functionality. The
contracts used in our model are called _hash time-lock contracts_ , or _HTLCs_
, for short, and are defined as follows: Each contract is associated with an
arc of $G$. For an arc $(u,v)$, its associated contract is used to transfer
the asset $(u,v)$ from $u$ to $v$. It is created by party $u$, with $u$
providing it with the asset, timeout value $\tau$, and a hashlock value $h$.
Once this contract is created, the possession of the asset is transferred from
$u$ to the contract; in other words, the asset is in this contract’s escrow.
The counter-party $v$ can access the contract to verify whether its
correctness; in particular, it can learn the hashlock value $h$. There are two
ways in which the asset can be released:

  * •

One, $v$ (the buyer) can claim it. To claim it successfully, $v$ must provide
a value $s$ such that $H(s)=h$ not later than at time $\tau$. When this
happens, the smart contract transfers the asset to $v$, and it also gives the
value of $s$ to $u$. One can think of this as an exchange of the asset for the
secret value $s$.

  * •

Two, the contract can expire. As soon as the current time exceeds $\tau$, and
if the asset has not been successfully claimed, the contract returns the asset
to its seller $u$.

All contracts considered in our paper are HTLCs, so the terms “contract” and
“HTLC” are from now on synonymous. Further overloading notation and
terminology, we will also refer to the contract on arc $(u,v)$ as “contract
$(u,v)$”. If this contract has hashlock $h_{x}$ of a party $x$ (where $x$ may
be different from $u$ and $v$), we will say that it is _protected by hashlock
$h_{x}$_ or simply _protected by party $x$_. Note that this does not mean that
this contract was created by $x$.

#### Swap protocols.

We assume that the time is discrete, consisting of unit-length time steps,
starting at time $0$. A swap protocol ${\mathbb{P}}$ specifies for each party
and each time step what actions this party executes at this step. These
actions may involve internal computation or external actions, like
communication.

In an execution of ${\mathbb{P}}$ there is no guarantee that all parties
actually follow ${\mathbb{P}}$. It may happen that some parties may deviate
from ${\mathbb{P}}$ for some reason, for example in an attempt to improve
their outcomes, or they may just behave erratically. When we refer to an
_honest_ or _conforming_ party $u$, we mean that $u$ follows ${\mathbb{P}}$,
except when it can infer from an interaction with some other party that not
all parties follow ${\mathbb{P}}$. From that point on, $u$ may behave
arbitrarily (but still rationally, so it would not do anything that might
worsen its ultimate outcome).

The execution of a protocol results in some assets being transferred between
parties. We assume that when the process completes, even if some parties do
not follow the protocol, an asset associated with arc $(u,v)$ will end up
either in the possession of $u$ or in the possession of $v$.

In an _HTLC-based protocol_ , all asset transfers are implemented with HTLCs,
and no other interaction between the parties is allowed. Each party is allowed
to create one secret/hashlock pair. These hashlock values are distributed via
smart contracts. (These values can in fact be simply made public.) A more
formal definition can be found in Section 5.

#### Outcomes.

For each party $v$, _$v$ ’s outcome_ associated with an execution of a
protocol ${\mathbb{P}}$ is specified by the sets of asets that are
relinguished and acquired by $v$ in this execution. Thus such an outcome is a
pair
${\omega}={\left\langle{{{\omega}^{in}}\,|\,{{\omega}^{out}}}\right\rangle}$,
where ${{\omega}^{in}}\subseteq{A_{v}^{in}}$ and
${{\omega}^{out}}\subseteq{A_{v}^{out}}$. To reduce clutter, instead of arcs,
in ${\left\langle{{{\omega}^{in}}\,|\,{{\omega}^{out}}}\right\rangle}$ we can
list only the corresponding in-neighbors and out-neighbors of $v$; for
example, instead of
${\left\langle{{\left\\{{(x,v),(y,v)}\right\\}}\,|\,{\left\\{{v,z}\right\\}}}\right\rangle}$
we will write ${\left\langle{x,y\,|\,z}\right\rangle}$.

An outcome
${\omega}={\left\langle{{{\omega}^{in}}\,|\,{{\omega}^{out}}}\right\rangle}$
of some party $u$ is called _acceptable_ if in this outcome $u$ retains all
its own assets or it gains all incoming assets. That is, either
${{\omega}^{in}}={A_{v}^{in}}$ or ${{\omega}^{out}}=\emptyset$ (or both).
Following Herlihy [8], we define several types of outcomes for each party $v$:

${\textsc{Deal}_{v}}={\left\langle{{A_{v}^{in}}\,|\,{A_{v}^{out}}}\right\rangle}$
represents an outcome where all prearranged asset transfers involving $v$ are
completed.

${\textsc{NoDeal}_{v}}={\left\langle{\emptyset\,|\,\emptyset}\right\rangle}$
represents an outcome where none of prearranged asset transfers involving $v$
is completed.

${\textsc{Discount}_{v}}={\left\\{{{\left\langle{{A_{v}^{in}}\,|\,{{\omega}^{out}}}\right\rangle}{\;:\;}{{\omega}^{out}}\neq{A_{v}^{out}}}\right\\}}$.
That is, ${\textsc{Discount}_{v}}$ is the set of outcomes in which all of
$v$’s incoming asset transfers are completed, but not all outgoing transfers
are.

${\textsc{FreeRide}_{v}}={\left\\{{{\left\langle{{{\omega}^{in}}\,|\,\emptyset}\right\rangle}{\;:\;}{{\omega}^{in}}\neq\emptyset}\right\\}}$.
That is, ${\textsc{FreeRide}_{v}}$ is the set of outcomes in which none of
$v$’s outgoing asset transfers is completed, but some of its incoming
transfers are.

We will skip the subscript $v$ in these notations whenever $v$ is understood
from context. These four types of outcomes are exactly all acceptable
outcomes, that is ${\omega}$ is acceptable if and only if

$\omega\;\in\;{\left\\{{\textsc{NoDeal}}\right\\}}\cup{\left\\{{\textsc{Deal}}\right\\}}\cup\textsc{FreeRide}\cup\textsc{Discount}$

(This is in fact how [8] defines the acceptable outcomes.) All other outcomes
are of type Underwater and are considered unacceptable.

For a set $C$ of parties, its set ${A_{C}^{in}}$ of incoming arcs consists of
arcs $(u,v)$ with $u\notin C$ and $v\in C$. The set ${A_{C}^{out}}$ of
outgoing arcs is defined analogously. With this, the concept of outcomes and
its properties, as defined above, extend naturally to sets of parties (that we
refer occasionally as “coalitions”). For example, an outcome of $C$ is
_acceptable_ if it either contains all incoming arcs of $C$ or does not
contain any outgoing arcs of $C$.

#### The preference relation.

A _preference relation_ of a party $v$ is a partial order on the set of all
outcomes for $v$ that satisfies the following three properties:

  * (_p1_)

If ${{\omega}_{1}^{in}}\subseteq{{\omega}_{2}^{in}}$ and
${{\omega}_{1}^{out}}\supseteq{{\omega}_{2}^{out}}$, then ${\omega}{{}_{2}}$
is preferred to ${\omega}{{}_{1}}$. In other words, it is better to receive
more assets and relinguish fewer assets.

  * (_p2_)

If ${\omega}\in\textsc{Underwater}$ then NoDeal is preferable to ${\omega}$.

  * (_p3_)

Deal is better than NoDeal. Otherwise, $v$ would have no incentive to
participate in the protocol.

The preference relation of a party $v$ captures which outcomes are more
desirable for $v$. Its intended to capture rational behavior of parties,
leading to the definition of Nash equilibrium property, given below.

Figure 1: Four types of acceptable outcomes. Solid arrows represent
transferred assets and dotted arrows represent those that are not. Figure 2:
An example of a preference relation of a node $v$ whose neighborhoods are
${N_{v}^{in}}={\left\\{{a,b}\right\\}}$ and
${N_{v}^{out}}={\left\\{{x,y}\right\\}}$. Arrows represent preferences.

#### Protocol properties.

Following [8], we define the following properties of a swap protocol
${\mathbb{P}}$:

_Liveness_ : ${\mathbb{P}}$ is called _live_ if all assets are transferred
(that is, each party ends up in Deal), providing that all parties follow
${\mathbb{P}}$.

_Safety_ : ${\mathbb{P}}$ is called _safe_ if each honest party ends up in an
acceptable outcome, independendently of the behavior of other parties.

_Strong Nash Equalibrium_ : ${\mathbb{P}}$ has the _strong Nash equilibrium
property_ if no party has an incentive to deviate from the protocol. More
precisely, for any set $C$ of parties (a coalition), if all parties outside
$C$ follow the protocol then the parties in $C$ cannot improve the outcome of
$C$ by deviating from the protocol.

_Atomicity_ : ${\mathbb{P}}$ is called _atomic_ if its live, safe, and has the
strong Nash equilibrium property.

The lemma below is a mild extension of the one given by Herlihy [8]. The
difference is that in our definition of the preference relation we allow some
FreeRide outcomes to be preferable to Deal, which was not the case in [8]. The
point of the lemma is that, in Herlihy’s preference model, the strong Nash
equilibrium property comes for free, namely that each protocol has this
property as long as it satisfies the liveness and safety properties. The
strong connectivity assumption is necessary for the safety property to hold,
see [8].

######  Lemma 1.

Assume that digraph $G$ is strongly connected. If a protocol ${\mathbb{P}}$ is
live and safe then ${\mathbb{P}}$ is atomic.

###### Proof.

Assume that ${\mathbb{P}}$ is live and safe. To prove that ${\mathbb{P}}$ is
atomic, we need to show that it satisfies the strong Nash equilibrium
property, as defined above.

Towards contradiction, suppose that some coalition $C$ has an outcome
${\omega}$ preferable to Deal, even though all other parties outside $C$
follow ${\mathbb{P}}$. Since ${\omega}$ is preferable to Deal, it must be
either in Discount or in FreeRide. We now consider these two cases, in each
reaching a contradiction. (See Figure 3 for illustration.)

Case 1: ${\omega}\in\textsc{Discount}$. That is, all incoming assets of $C$
are transferred, but some outgoing asset $(x,y)$ of $C$ is not. Since $G$ is
strongly connected, there is a path $Q=y_{1}y_{2}...y_{k}$ in $G$ from
$y=y_{1}$ to $x=y_{k}$. Let $y_{j}$ be the first vertex on this path that is
in $C$. By the choice of $y_{1}$, we have $j>1$. As $y_{1}$ follows the
protocol, the safety condition guarantees that its outcome is acceptable.
Since $(x,y_{1})$ is not transferred and $y_{1}$’s outcome is acceptable, all
outgoing assets of $y_{1}$ are also not transferred. In particular, asset
$(y_{1},y_{2})$ is not transferred. The same argument gives us that if $j>2$
then all outgoing assets of $y_{2}$ are not transferred. Repeating this for
all vertices $y_{1},y_{2},...,y_{j-1}$, we will eventually obtain that the
asset $(y_{j-1},y_{j})$ is not transferred. But $(y_{j-1},y_{j})$ is an
incoming asset of $C$, so $C$’s outcome ${\omega}$ cannot be in Discount.

.

Figure 3: Illustration of Cases 1 and 2 in the proof of Lemma 1. Solid arrows
represent transferred assets and dotted arrows represent those that are not.
In the figure on the left, $j=6$. In the figure on the right, $k=7$ and $j=3$.

Case 2: $\omega\in\textsc{FreeRide}$. That is, at least one incoming asset of
$C$ is transferred, but no outgoing asset of $C$ is transferred. Consider a
transferred asset $(x,y)$ that is incoming into $C$. Since $G$ is strongly
connected, there is a path $Q=y_{1}y_{2}\ldots y_{k}$ in $G$ from $y=y_{1}$ to
$x=y_{k}$. Let $y_{j}$ be the last vertex in $C$ on this path. Then
$(y_{j},y_{j+1})$, being an outgoing asset from $C$, is not transferred. Since
$y_{j+1}$ follows the protocol, the safety condition guarantees that its
outcome is acceptable. Since $(y_{j},y_{j+1})$ is not transferred and
$y_{j+1}$’s outcome is acceptable, all outgoing asset of $y_{j+1}$ are also
not transferred. In particular, $(y_{j+1},y_{j+2})$ is not transferred. The
same argument gives us that if $j+2\leq k$ then all outgoing assets of
$y_{j+2}$ are not transferred. Repeating this for all remaining vertices on
the path, we will eventually obtain that asset $(y_{k},y)=(x,y)$ is not
transferred, which is a contradiction. So $C$’s outcome $\omega$ cannot be in
FreeRide.

∎

##  4 An Atomic Protocol for Reuniclus Digraphs

In this section we give an atomic asset-swap protocol for reuniclus digraphs.
The concept of reuniclus digraphs was introduced informally in Section 1, and
the formal definition is given below in Section 4.2.

We present this protocol in two steps. First, in Section 4.1, we describe an
atomic protocol for bottleneck digraphs called Protocol BDP (short for
_bottleneck-digraph protocol_). This protocol is essentially equivalent to a
simplified version of Herlihy’s protocol (see [8], Section 46). We include it
here for the sake of completeness, as it is an essential ingredient of our
full protocol for reuniclus digraphs, called Protocol RDP (short for
_reuniclus-digraph protocol_), that is presented in Section 4.2.

###  4.1 Protocol BDP for Bottleneck Digraphs

A vertex $v$ in a digraph $G$ is called a _bottleneck vertex_ if it belongs to
each cycle of $G$. In other words, $v$ is a singleton feedback vertex set of
$G$. If $G$ is strongly connected and has a bottleneck vertex then we refer to
$G$ as a _bottleneck digraph_.

We now describe Protocol BDP, an atomic asset-swap protocol for bottleneck
digraphs. Given a bottleneck digraph $G$, one bottleneck vertex of $G$ is
designated as the _leader_. This leader, denoted $\ell$, creates its
secret/hashlock pair $(s_{\ell},h_{\ell})$. The other vertices are called
_followers_. Protocol BDP has two phases. The first phase, initiated by
$\ell$, creates all contracts. Each follower waits for all the incoming
contracts to be created, and then creates the outgoing contracts. The timeout
values for all incoming contracts are strictly larger than the timeout values
for all outgoing contracts. In the second phase the assets are claimed,
starting with $\ell$ claiming its incoming assets. Now the process proceeds
backwards. For each follower $v$, when any of its outgoing assets is claimed,
$v$ learns the secret value $s_{\ell}$, and it can now claim its incoming
assets.

The detailed description of this protocol is given in Figure 4. In the
protocol, ${D^{-}_{v}}$ denotes the _maximum distance from $\ell$ to $v$_,
defined as the maximum length of a simple path from $\ell$ to $v$. In
particular, ${D^{-}_{\ell}}=0$. For $y\neq\ell$, the value of ${D^{-}_{y}}$
can be computed recursively using the formula

${D^{-}_{y}}\;=\;\max_{z\in{N_{y}^{in}}}{D^{-}_{z}}+1$ (1)

This is in essence the standard recurrence for computing the longest path in
acyclic digraphs. (One can think of $G$ as a DAG by splitting $\ell$ into two
vertices, one with the outgoing arcs of $\ell$ and the other with the incoming
arcs of $\ell$.) The values ${D^{-}_{y}}$ are used in contract creation times.

By ${D^{\ast}}$ we denote the maximum length of a simple cycle in $G$. This
cycle is just a path from $\ell$ to $\ell$ that does not repeat any vertices
except for $\ell$, so ${D^{\ast}}=\max_{z\in{N_{\ell}^{in}}}{D^{-}_{z}}+1$,
analogously to (1).

In the timeout values, the notation ${D^{+}_{v}}$ is the maximum distance from
$v$ to $\ell$. These values satisfy a recurrence symmetric to (1), namely
${D^{+}_{\ell}}=0$ and for $y\neq\ell$

${D^{+}_{y}}\;=\;\max_{z\in{N_{y}^{out}}}{D^{+}_{z}}+1$ (2)

Naturally, we then also have
$\max_{z\in{N_{\ell}^{out}}}{D^{+}_{z}}+1={D^{\ast}}$. Note that, for each
party $v$, the timeouts of all incoming contracts $(u,v)$ are equal
${D^{\ast}}+{D^{+}_{v}}$, exactly the time when $v$ is scheduled to claim
them. And, by equation (2), if $v\neq\ell$ then ${D^{\ast}}+{D^{+}_{v}}$ is
larger than the timeout ${D^{\ast}}+{D^{+}_{w}}$ of each outgoing contract
$(v,w)$.

Figure 5 shows an example of a bottleneck digraph and its timeout values in
Protocol BDP.

Protocol BDP for leader $\ell$: • At time $0$: Create a secret $s_{\ell}$ and
compute $h_{\ell}=H(s_{\ell})$. For each arc $(\ell,v)$, create the contract
with hashlock $h_{\ell}$ and timeout $\tau_{\ell v}={D^{\ast}}+{D^{+}_{v}}$. •
At time ${D^{\ast}}$: Check if all the incoming contracts are created,
correct, and have the same hashlock value $h_{\ell}$. (If not, abort.) Claim
all incoming assets using secret $s_{\ell}$. Protocol BDP for a follower $u$:
• At time ${D^{-}_{u}}$: Check if all the incoming contracts are created,
correct, and have the same hashlock value, say $h$. (If not, abort.) For each
arc $(u,v)$, create contract with hashlock $h$ and timeout
$\tau_{uv}={D^{\ast}}+{D^{+}_{v}}$. • At time ${D^{\ast}}+{D^{+}_{u}}$: Check
if any of the outgoing assets was claimed. (If not, abort.) Let $s$ be the
secret obtained from the contract for some claimed outgoing assets. Use $s$ to
claim all incoming assets.

Figure 4: Protocol BDP, with the protocol of the leader on the left, and the
protocol of the followers on the right. Each bullet-point step takes one time
unit. To check correctness of an incoming contract, the buyer verifies if the
seller created it according to the protocol; in particular, whether the
contract contains the desired asset and whether the timeout values are
correct.  Figure 5: An example of a bottlebeck digraph $G$ and the timeout
values for Protocol BDP for $G$. The longest cycle in $G$ is
$\ell,b,f,g,h,d,e,j,\ell$, so ${D^{\ast}}=8$.

######  Theorem 2.

If $G$ is a bottleneck digraph, then Protocol BDP is an atomic swap protocol
for $G$.

###### Proof.

According to Lemma 1, it is sufficient to prove only the liveness and safety
properties.

_Liveness._ For the liveness property, we need to prove that if all parties
follow BDP then all assets will be transferred, and thus all parties end up in
Deal. Assume all parties follow the protocol. In the first phase, according to
equation (1), each party has one time unit after all its incoming contracts
are placed to create its outgoing contracts. Thus all contracts will be
successfully created and the last contract will be created by the last in-
neighbor of $\ell$, in step
$\max_{z\in{N_{\ell}^{out}}}{D^{+}_{z}}={D^{\ast}}-1$, so before the second
phase starts. In the second phase each asset $(u,v)$ will be claimed at time
${D^{\ast}}+{D^{+}_{v}}$, and at that time $u$ will receive the secret
$s_{\ell}$. By equation (2), ${D^{\ast}}+{D^{+}_{u}}$ is larger than
${D^{\ast}}+{D^{+}_{v}}$. So $u$ will be able to sucessfully claim all
incoming assets at time ${D^{\ast}}+{D^{+}_{u}}$, which is also the timeout
value for these assets. This shows that Protocol BDP satisfies the liveness
property.

_Safety._ Consider some party $v$, and assume that $v$ follows the protocol.
We need to show that $v$ will end up in an acceptable outcome, even if other
parties deviate from the protocol. In other words, we need to show that either
all incoming assets of $v$ are transferred or all outgoing assets of $v$ are
not transferred. We consider two cases, when $v$ is the leader and when $v$ is
a follower.

Case 1: $v=\ell$. If some incoming contract of $\ell$ is not created before
time ${D^{\ast}}$, $\ell$ will abort the protocol333It may be tempting, if
$\ell$ has any incoming contract created, to claim its asset, even if some
other incoming contract is not created. This, however, would make the protocol
unsafe, because then $\ell$ could lose some of its outgoing assets.. Since
$\ell$ does not reveal its secret, none of $\ell$’s outgoing assets can be
claimed. So all outgoing contracts will expire and their assets will be
returned to $\ell$. In this case, $\ell$’s outcome is NoDeal, so it is
acceptable.

Next, suppose that all incoming contracts of $\ell$ are created before time
${D^{\ast}}$. According to the protocol, each incoming contract $(u,\ell)$ of
$\ell$ has timeout $\tau_{u\ell}={D^{\ast}}+{D^{+}_{\ell}}={D^{\ast}}$. Thus
$\ell$ can claim all incoming assets at time ${D^{\ast}}$, so its outcome will
be Deal or Discount, both acceptable.

Case 2: $v\neq\ell$. If some incoming contract of $v$ is not created before
time ${D^{-}_{v}}$, $v$ likewise will abort the protocol. Then none of $v$’s
outgoing assets will be claimed and the incoming contracts will expire, so the
outcome will be NoDeal, which is acceptable.

Next suppose that at time ${D^{-}_{v}}$ all incoming contracts of $v$ are
created, correct, and all have the same hashlock value $h$. Then $v$ will
create all outgoing contracts with the same hashlock $h$. (We remark here
that, as other parties may not follow the protocol, it is not necessarily true
that $h=h_{\ell}$.) At time ${D^{\ast}}+{D^{+}_{v}}$, if none of the outgoing
assets of $v$ are claimed then the outgoing assets will be returned to $v$, so
$v$’s outcome will be NoDeal or FreeRide. On the other hand, if any asset
$(v,w)$ is claimed, it must be claimed no later than at time
$\tau_{vw}={D^{\ast}}+{D^{+}_{w}}$, and at this time $v$ will obtain a secret
value $s$. Since $v$ used the same hashlock $h$ on the outgoing contracts as
the one on the incoming contracts, it must be that $H(s)=h$, for otherwise $w$
would not be able to successfully claim $(v,w)$. So $s$ will also work
correctly for any incoming contract. Since $\tau_{vw}<{D^{\ast}}+{D^{+}_{v}}$,
and ${D^{\ast}}+{D^{+}_{v}}$ is the timeout of all $v$’s incoming contracts,
$v$ will successfully claim all incoming assets at time
${D^{\ast}}+{D^{+}_{v}}$. Thus $v$’s outcome would be either Deal or Discount,
both of which are acceptable. ∎

We remark that some optimizations can reduce the number of steps needed in
Protocol BDP. For example, it is not necessary for a follower $u$ to wait
until step ${D^{\ast}}+{D^{+}_{u}}$ to claim the incoming assets. Instead, $u$
can claim all its incoming assets as soon as any of its outgoing assets is
claimed.

###  4.2 Protocol BDP for Reuniclus Digraphs

Reuniclus digraphs. Let $G$ be a strongly connected digraph. We call $G$ a
_reuniclus digraph_ if there are vertices $b_{1},b_{2},...,b_{p}\in G$,
induced subgraphs $G_{1},G_{2},...,G_{p}$ of $G$, and a rooted tree $\cal{K}$
whose nodes are $b_{1},b_{2},...,b_{p}$, with the following properties:

(rg1) Each digraph $G_{j}$ is a bottleneck subgraph, with $b_{j}$ being its
bottleneck vertex. We call $G_{j}$ a _bottleneck component_ of $G$.

(rg2) If $i\neq j$, then

$G_{i}\cap G_{j}\;=\;\begin{cases}{\left\\{{b_{j}}\right\\}}&\textrm{if
$b_{i}$ is the parent of $b_{j}$ in $\cal{K}$}\\\
\emptyset&\textrm{otherwise}\end{cases}$

Part (rg2) says that $G_{i}$ and $G_{j}$ are either disjoint or only share one
vertex, which is the bottleneck $b_{j}$ of $G_{j}$. We call $G_{j}$ the _home
component_ of $b_{j}$. We refer to $\cal{K}$ as the _control tree_ of $G$.
(See Figure 6 for an example.) We extend the tree terminology to relations
between bottleneck components, or between bottleneck vertices and components,
in a natural fashion. For example, if $b_{i}$ is the parent of $b_{j}$ in
$\cal{K}$ then we refer to $G_{i}$ as the parent component of $b_{j}$, to
$G_{j}$ as the child component of $b_{i}$. The same convention applies to the
ancestor and descendant relations.

Intuitively, a reuniclus graph $G$ can be divided into bottleneck components.
Among these, most of are pairwise disjoint. Overlaps are allowed only between
two components if one is the parent of the other in the control tree
$\cal{K}$, in which case the overlap is just a single vertex that is the
bottleneck of the child component.

Figure 6: An example of a reuniclus graph (left) and its control tree (right).
The bottleneck components (circled) are $B$, $U$, $X$, $Y$ and $Z$. Their
designated bottleneck vertices are $b$, $u$, $x$, $y$ and $z$. Note that $Z$
consists of two biconnected components.

From the definition, we have that the set of all bottleneck vertices in $G$
forms a feedback vertex set of $G$. These bottleneck vertices are articulation
vertices of $G$. The bottleneck components are not necessarily biconnected;
each bottleneck component may consist of several biconnected components that
share the same bottleneck vertex.

#### Protocol RDP.

Protocol RDP can be thought of as a hierachical extension of Protocol BDP.
Each bottleneck vertex $b_{j}$ is called the leader of $G_{j}$. It creates its
own secret/hashlock pair $(s_{j},h_{j})$, and its hashlock $h_{j}$ is used to
safely transfer assets within $G_{j}$, while the transfer of assets in the
descendants components of $b_{j}$ is “delegated” to the children of $b_{j}$ in
$\cal{K}$. We assume that the root component of $\cal{K}$ is $G_{1}$, and its
bottleneck $b_{1}$ is called the _main leader_ , that will be also denoted by
$\ell$. All non-leader vertices are called _followers_.

Protocol RDP has two parts. In the first part all contracts are created and in
the second part the parties claim their incoming assets. In the first phase,
at time $0$ all leaders create the outgoing contracts within their home
bottleneck components. Then the contracts are propagated within the bottleneck
components, to some degree independently; except that each leader $b_{j}$
creates its outgoing contracts in its parent component $G_{i}$ only after all
its incoming contracts, _both in $G_{i}$ and $G_{j}$_, are created. This in
fact ensures that at that time all contracts in its descendant components will
be already created.

In the asset claiming phase, the main leader $\ell$ is the first to claim the
incoming contracts. The behavior of followers is the same as in Protocol BDP:
they claim the incoming assets one step after all their outgoing assets were
claimed. The behavior of all non-main leaders is more subtle. Each such leader
$b_{j}$ waits until all its outgoing assets _in the parent component_ are
claimed, and then it claims all of its incoming assets. (So $b_{j}$ does not
wait for the outgoing assets in its home component to be claimed.)

The full protocol for non-main leaders $b_{j}$ is given in Figure 7. Figure 8
shows timeout values for the reuniclus graph in Figure 6. In what follows we
explain some notations used in the protocol.

As before, we use notation ${D^{+}_{y}}$ for the maximum distance from $y$ to
$\ell$ in $G$ (see the formula (1) in Section 4.1). The formula (2) remains
valid as is. We also need the concept analogous to the maximum distance from a
leader, but this one is a little more subtle than for bottleneck graphs,
because we now need to consider paths whose initial bottleneck vertex can be
repeated once later on the path. Formally, if $v\in G_{i}$, then ${B^{-}_{v}}$
denotes the maximum length of a path with the following properties:

(i) it starts at some leader $b_{j}$ that is a descendant of $b_{i}$ (possibly
$b_{j}=b_{i}$),

(ii) it ends in $v$, and

(iii) it does not repeat any vertices, with one possible exception: it can
only revisit $b_{j}$, and if it does, it either ends or leaves $G_{j}$ (and
continues in the parent component of $b_{j}$).

(This can be interpreted as a maximum path length in a DAG obtained by
splitting each leader into two vertices, one with the outgoing arcs into its
home component and the other with all other arcs.) For example, in the example
in Figure 6, one allowed path for $v=u$ is $x-y-z-d-x-j-u$.

These values can be computed using auxiliary values ${B^{-}_{uv}}$ defined for
each edge $(u,v)$. Call an edge $(u,v)$ a _bottleneck edge_ if $u$ is a
bottleneck vertex, say $u=b_{j}$, and $v\in G_{j}$. That is, bottleneck edges
are the edges from bottleneck vertices that go into their home components.
First, for each bottleneck edge $(b_{j},v)$ let ${B^{-}_{b_{j}v}}=0$. Then,
for each vertex $u$ and each non-bottleneck edge $(u,v)$ let

${B^{-}_{u}}\;=\;{B^{-}_{uv}}\;=\;\max_{(x,u)}{B^{-}_{xu}}+1$ (3)

where the maximum is over all edges $(x,u)$ entering $u$. By ${B^{\ast}}$ we
denote the value of ${B^{-}_{\ell}}$.

The values ${B^{-}_{z}}$ determine contract creation times. As shown in Figure
7, each leader $b_{j}$ will create its contracts in its home component at time
$0$. Each other contract $(u,v)$ will be created at time ${B^{-}_{u}}$. The
last contract will be created by some in-neighbor of $\ell$ at time step
${B^{\ast}}-1$. Then $\ell$ will initiate the contract claiming phase at time
${B^{\ast}}$. Analogous to Protocol BDP, each party $u$ will claim its
incoming contracts at time ${B^{\ast}}+{D^{+}_{u}}$, which is its timeout
value.

Protocol BDP for a leader $b_{j}\in G_{i}\cap G_{j}$: • At time $0$: Generate
secret $s_{j}$ and compute $h_{j}=H(s_{j})$. For each arc $(b_{j},v)$ in
$G_{j}$, create contract with hashlock $h_{j}$ and timeout
$\tau_{b_{j}v}={B^{\ast}}+{D^{+}_{v}}$. • At time ${B^{-}_{u}}$: Check if all
incoming contracts are in place, if they are correct, if all the hashlocks in
the incoming contracts in $G_{i}$ have the same value $h$, and if all the
hashlocks in the incoming contracts in $G_{j}$ are equal $h_{j}$. (If not,
abort.) For each arc $(b_{j},v)$ in $G_{i}$ create its contract with hashlock
$h$ and timeout $\tau_{b_{i}v}={B^{\ast}}+{D^{+}_{v}}$. • At time
${B^{\ast}}+{D^{+}_{u}}$: Check if any of the outgoing assets in $G_{i}$ was
claimed. (If not, abort.) Let $s$ be the secret obtained from the contract for
some claimed outgoing assets in $G_{i}$. Claim all its incoming assets, using
secret $s$ in $G_{i}$ and using secret $s_{j}$ in $G_{j}$.

Figure 7: Protocol RDP for a sub-leader $b_{j}$, namely the bottleneck vertex
of $G_{j}$ that also belongs to its parent graph $G_{i}$. Recall that
${B^{-}_{u}}$ is the maximum distance from some leader to $u$ along a path
that satisfies conditions (i)-(iii), and that ${B^{\ast}}={B^{-}_{\ell}}$.
${D^{+}_{v}}$ is the maximum length of a simple path from $v$ to $\ell$, as
defined in Section 4.1. As explained in the text, the protocols for the main
leader and the pure followers are the same as in Protocol BDP.

Figure 8: Timeout values and hashlocks for Protocol RDP for the graph in
Figure 6. The main leader is $\ell=b$. We have ${B^{\ast}}=9$ (this is the
length of path $y-c-y-z-d-g-x-j-u-b$).

######  Theorem 3.

If $G$ is a reuniclus digraph, then Protocol RDP is an atomic swap protocol
for $G$.

###### Proof.

According to Lemma 1, it is sufficient to prove only the liveness and safety
properties.

_Liveness._ The liveness property is quite straightforward. Each party
$u\neq\ell$ has exactly one time unit, after its last incoming contract is
created, to create its outgoing contracts, according to (3). This will
complete the contract creation at time ${B^{\ast}}-1$. Thus at time
${B^{\ast}}$ leader $\ell$ can claim its incoming assets. For any other party
$u$, each incoming asset $(x,u)$ of $u$ has timeout
$\tau_{xu}={B^{\ast}}+{D^{+}_{u}}$. By formula (2), if $u$ is a follower then
all the outgoing assets of $u$ will be claimed before time $\tau_{xu}$, and if
$u$ is a non-main leader then all of $u$’s ougoing assets in its parent
component will be claimed before time $\tau_{xu}$. So $u$ can claim all
incoming assets at time $\tau_{xu}$.

_Safety._ The proof of the safety condition for the main leader $\ell$ and
pure followers is the same as in Protocol BDP for bottleneck digraphs. So here
we focus only on non-main leaders.

Let $b_{j}$ be a non-main leader whose parent component is $G_{i}$. Assume
that $b_{j}$ follows the protocol. So, according to Protocol RDP, $b_{j}$ will
create its outgoing contracts in $G_{j}$ at time $0$. Before creating its
outgoing contracts in $G_{i}$, $b_{j}$ checks if _all_ incoming contracts are
created. If any of its incoming contracts is not created or if any value in
this contract is not as specified in the protocol, $b_{j}$ will abort without
creating its outgoing contracts in $G_{i}$. Thus its outcome will be NoDeal.

So assume that all incoming contracts of $b_{j}$ are created and correct; in
particular all incoming contracts in $G_{j}$ have hashlock $h_{j}$ and all
incoming contracts in $G_{i}$ have the same hashlock $h$ (which may or may not
be equal to $h_{i}$). Then $b_{j}$ creates its outgoing contracts in $G_{i}$,
as in the protocol. We now need to argue that if any of $b_{j}$’s outgoing
assets is successfully claimed then $b_{j}$ successfully claims _all_ its
incoming assets.

Suppose that some outgoing asset of $b_{j}$, say $(b_{j},w)$ is successfully
claimed by $w$. Two cases arise, depending on whether $w$ is in $G_{i}$ or
$G_{j}$.

If $w\in G_{i}$ (the parent component of $b_{j}$) then from contract
$(b_{j},w)$ will provide $b_{j}$ with some secret value $s$ for which
$H(s)=h$, because $b_{j}$ used $h$ for its outgoing contracts in $G_{i}$. At
this point, $b_{j}$ has both secret values $s$ and $s_{j}$, and, by formula
(2), the timeout of all incoming contracts of $b_{j}$ is greater than the
timeout of $(b_{j},w)$. Therefore $b_{j}$ has the correct secrets and at least
one time unit to claim all incoming contracts, and its outcome will be Deal or
Discount, thus acceptable.

In the second case, $w\in G_{j}$, the home component of $b_{j}$. For $w$ to
successfully claim $(b_{j},w)$, it must have the value of $s_{j}$. But, as
$b_{j}$ follows the protocol, it releases $s_{j}$ only when claiming all
incoming assets. So at this time $b_{j}$ already has all incoming assets.
Therefore in this case the outcome of $b_{j}$ is also either Deal or Discount.
∎

##  5 A Characterization of Digraphs that Admit SHL-Based Protocols

In this section we provide a full characterization of digraphs that have HTLC-
based protocols, showing that these are exactly the reuniclus digraphs. The
concept of HTLC-based protocols was informally introduced in Section 1. For
our characterization we need a more precise definition that we provide next.

Formal definition of HTLC-based protocols. We will say that a protocol
${\mathbb{P}}$ is an _HTLC-based protocol_ if ${\mathbb{P}}$ consists of
discrete time steps, each taking one time unit, and in each step any party $v$
is allowed to execute any number of the following actions:

_Create a secret/hashlock pair_ : $v$ can create a secret value $s_{v}$ and
compute the corresponding hashlock $h_{v}=H(s_{v})$. We assume that $v$ can
create only one hashlock.

_Create contract_ : If $(v,w)\in G$, $v$ can create an HTLC for transferring
the asset $(v,w)$ to $w$. This contract can be created only once. It must be
secured with a hashlock $h_{x}$ of some party $x$ that created a
secret/hashlock pair.

_Claim asset:_ If $(u,v)\in G$ and the contract $(u,v)$ is placed and and not
yet expired (that is, the current time does not exceed the timeout value
$\tau_{uv}$ of this contract), then $v$ can claim asset $(u,v)$, providing
that $v$ knows the secret value $s_{y}$ corresponding to the hashlock value
$h_{y}$ that protects this contract.

Parties have read access to the incoming contracts, so that they can verify
their correctness and obtain their hashlock values. This allows a protocol to
propagate the hashlock values. But the model also allows the parties to make
the hashlock values public or distribute them selectively to other parties.
There are no restrictions on local computation, with one obvious exception,
namely that the parties cannot break any cryptographic tools used in smart
contracts.

We now turn to our characterization, captured by Theorem 1 in Section 1, that
we restate here for convenience:

Theorem 1. A swap digraph $G$ has an atomic HTLC-based protocol if and only if
$G$ is a reuniclus digraph.

The rest of this section is devoted to the proof of Theorem 1. By
straightforward inspection, Protocol RDP from Section 4.2 is HTLC-based: each
party creates at most one secret/hashlock pair, and all contracts are created
and claimed following the rules detailed above. This already proves the
$(\Leftarrow)$ implication in Theorem 1.

It remains to prove the $(\Rightarrow)$ implication, namely that the existence
of an atomic HTLC-based protocol implies the reuniclus property of the
underlying graph. We divide the proof into two parts. First, in Section 5.1 we
establish some basic properties of HTLC-based protocols. Using these
properties, we then wrap up the proof of the $(\Rightarrow)$ implication in
Section 5.2.

###  5.1 Basic Properties of HTLC-Based Protocols

Let ${\mathbb{P}}$ be an HTLC-based protocol for a strongly connected digraph
$G$, and for the rest of this section assume that ${\mathbb{P}}$ is atomic. We
now establish some fundamental properties that must be satisfied by
${\mathbb{P}}$. To be more precise, whenever we say that ${\mathbb{P}}$ has a
certain property, we mean that this property is satisfied in the _conforming
execution_ of ${\mathbb{P}}$ on $G$, that is when all parties are _conforming_
(or, equivalently, _honest_), that is they follow ${\mathbb{P}}$.

Withouth loss of generality we can assume that in ${\mathbb{P}}$ each asset
$(u,v)$ is claimed by $v$ exactly at the expiration time $\tau_{uv}$ of
contract $(u,v)$. This is because otherwise we can decrease the timeout value
$\tau_{uv}$ to the time step when $v$ claims asset $(u,v)$ in ${\mathbb{P}}$,
and after this change ${\mathbb{P}}$ remains HTLC-based and atomic. Note also
that the liveness property of ${\mathbb{P}}$ implies that $\tau_{uv}$ must be
larger than the creation time of contract $(u,v)$.

Most of the proofs of protocol properties given below use the same fundamental
approach, based on an argument by contradiction: we show that if
${\mathbb{P}}$ did not satisfy the given property then there would exist a
(non-conforming) execution of ${\mathbb{P}}$ in which some parties, by
deviating from ${\mathbb{P}}$, would force a final outcome of some conforming
party to be unacceptable, thus violating the safety property.

######  Lemma 2.

If some party successfully claims an incoming asset at some time $t$, then all
contracts in the whole graph must be placed before time $t$.

###### Proof.

Assume that a party $v$ successfully claims an asset $(u,v)$ at time $t$.
Towards contradiction, suppose that there is some arc $(x,y)$ for which the
contract is still not placed at time $t$. Since $G$ is strongly connected,
there is a path $y=u_{1},u_{2},...,u_{p}=u$ from $y$ to $u$ in $G$. Let also
$u_{0}=x$ and $u_{p+1}=v$. Now consider an execution of ${\mathbb{P}}$ in
which all parties except $x$ are conforming, $x$ follows ${\mathbb{P}}$ up to
time $t-1$, but later it never creates contract $(x,y)$. This execution is
indistinguishable from the conforming execution up until time $t-1$, so at
time $t$ node $v$ will claim contract $(u,v)$. Since the first asset on path
$u_{0},u_{1},...,u_{p+1}$ is not transferred and the last one is, there will
be a party $u_{j}$ on this path, with $1\leq j\leq p$, for which asset
$(u_{j-1},u_{j})$ is not transferred but $(u_{j},u_{j+1})$ is. But then the
outcome of $u_{j}$ is unacceptable even though $u_{j}$ is honest,
contradicting the safety property of ${\mathbb{P}}$. ∎

Lemma 2 is important: it implies that ${\mathbb{P}}$ must consist of two
phases: the _contract creation_ phase, in which all parties place their
outgoing contracts (by the liveness property, all contracts must be created),
followed by the _asset claiming_ phase, when the parties claim their incoming
assets.

Recall that by a _contract protected by $x$_ we mean a created contract with
hashlock $h_{x}$. (Here, $x$ is not necessarily the party that created the
contract.)

######  Lemma 3.

Suppose that at a time $t$ a party $v$ creates an outgoing contract protected
by a party different than $v$. Then all $v$’s incoming contracts must be
created before time $t$.

###### Proof.

Suppose the property in the lemma does not hold for some party $v$, that is,
at some time $t$, $v$ creates a contract $(v,w)$ protected by hashlock $h_{x}$
of some party $x\neq v$, while some incoming contract $(u,v)$ is not yet
created.

We consider another execution of the protocol. In this execution, $v$ is
conforming. Also, up until time $t-1$ all parties follow the protocol, so that
$v$’s behavior at time $t$ will not change and it will create contract
$(v,w)$. Then at time $t$ some parties will deviate from the protocol.
Specifically, (i) at time $t$ party $x$ will give its secret value $s_{x}$ to
$w$ (this is needed only if $x\neq w$), (ii) using $s_{x}$, party $w$ will
claim asset $(v,w)$ at time $t+1$, and (iii) $u$ will never create contract
$(u,v)$. As a result, $v$ will lose its asset $(v,w)$ without getting asset
$(u,v)$, so $v$’s outcome is not acceptable. This contradicts the safety
property of ${\mathbb{P}}$, so we can conclude that ${\mathbb{P}}$ must
satisfy the lemma. ∎

Consider now the snapshot of of ${\mathbb{P}}$ right after the contract
creation phase, when all contracts are already in place but none of the assets
are yet claimed. The corollary below follows directly from Lemma 3.

######  Corollary 4.

(a) If on some path each contract except possibly first is not protected by
its seller, then along this path the contract creation times strictly
increase. (b) Each cycle must contain a contract protected by its seller.

Next, we establish some local properties of ${\mathbb{P}}$. Namely, in the
next four lemmas we will show that for each party $v$ there is at most one
other party that protects contracts involving $v$. We will also establish some
relations between the timeout values of the contracts involving $v$.

######  Lemma 5.

If a party $v$ has an incoming contract protected by some party $x$ different
from $v$ then

(a) Party $v$ has at least one outgoing contract protected by $x$.

(b) All contracts involving $v$ are protected either by $v$ or by $x$.

###### Proof.

Let $(u,v)$ be an incoming contract protected by $x$, where $x\neq v$.

(a) This claim is easy: if $v$ didn’t have an outgoing contract protected by
$x$, then even in the conforming execution it would never receive the secret
value $s_{x}$ needed to claim $(u,v)$. That would violate the liveness
property of ${\mathbb{P}}$.

(b) We first show that all outgoing contracts must be protected by $v$ or $x$.
Suppose that it is not true, namely that some outgoing contract $(v,w)$ is
protected by some party $y$, where $y\notin{\left\\{{v,x}\right\\}}$. Let $t$
be the time right after all contracts are created. We change the behavior of
some parties, as follows. Up to time $t-1$ they follow the protocol. At time
$t$, $y$ can provide $w$ with secret $s_{y}$, allowing $w$ to claim $(v,w)$ at
time $t+1$. All parties other than $v$ and $w$ don’t do anything starting at
time $t$. Then $v$ will not receive the secret $s_{x}$ needed to claim asset
$(u,v)$, so it will end up in an unacceptable outcome, contradicting the
safety property. We can thus conclude that all outgoing contracts not
protected by $v$ must be protected by $x$.

Next, consider incoming contracts not protected by $v$. If $(u^{\prime},v)$ is
an incoming contract of $v$ protected by some party
$x^{\prime}\notin{\left\\{{v,x}\right\\}}$ then, by part (a), $v$ would have
at least one outgoing contract protected by $x^{\prime}$, contradicting that
all outgoing contracts are protected either by $v$ or $x$. This completes the
proof of (b). ∎

######  Lemma 6.

Let $P=u_{1},u_{2},...,u_{k}$ be a simple path whose last contract is
protected by some party $z\notin{\left\\{{u_{1},u_{2},...,u_{k-1}}\right\\}}$.
Then for each $i=1,...,k-1$, contract $(u_{i},u_{i+1})$ is protected by one of
the parties $u_{i+1},u_{i+2},...,u_{k-1},z$. Consequently, each contract on
$P$ is not protected by its seller.

###### Proof.

The second part of the lemma follows trivially from the first.

We prove the first part by induction, proceeding backwards on $P$. The claim
is true for $i=k-1$, because, by our assumption, contract $(u_{k-1},u_{k})$ is
protected by $z$. Inductively (going backwards on $P$), assume that the lemma
holds for $i=k-1,k-2,...,j$, where $j\geq 2$. In particular, by the inductive
assumption, $(u_{j},u_{j+1})$ is protected by some party
$u^{\prime}\in{\left\\{{u_{j+1},u_{j+2},...,u_{k-1},z}\right\\}}$, Since $P$
is a simple path, we have $u^{\prime}\neq u_{j}$. Then Lemma 5 implies that
contract $(u_{j-1},u_{j})$ is protected either by $u_{j}$ or by $u^{\prime}$.
Therefore contract $(u_{j-1},u_{j})$ is protected by one of the parties
$u_{j},u_{j+1},...,u_{k-1},z$. So the lemma holds for $i=j-1$, completing the
inductive step. ∎

######  Lemma 7.

If all incoming contracts of a party $v$ are protected by $v$ then all
outgoing contracts of $v$ are also protected by $v$.

Intuitively, if $v$ had an outgoing contract protected by some other party $x$
but not an incoming contract protected by $x$, then this outgoing contract
would be “redundant” for $v$, since $v$ does not need the secret from this
contract to claim an incoming contracts. The lemma shows that the issue is not
just redundancy — this is in fact not even possible if the protocol is atomic.

###### Proof.

We prove the lemma by contradiction. Suppose that all $v$’s incoming contracts
are protected by $v$, but $v$ has an outgoing contract $(v,w)$ protected by
some other party $x$. Let $P=u_{1},u_{2},...,u_{p}$ be a simple path from $w$
to $v$, that is $u_{1}=w$ and $u_{p}=v$. Then Lemma 6 implies that all
contracts on $P$ are not protected by their sellers. The contract
$(u_{p},u_{1})=(v,w)$ is not protected by its seller $v$. This would give us a
cycle, namely $C=u_{p},u_{1},...,u_{p-1},u_{p}$, in which each contract is not
protected by the seller. But this contradicts Corollary 4(b), completing the
proof of the lemma. ∎

######  Lemma 8.

If a party $v$ has an outgoing contract protected by some party $x$ different
from $v$ then it has an incoming contract protected by $x$.

###### Proof.

This follows quite easily from the lemmas above. Consider the incoming
contracts of $v$. Not all of them can be protected by $v$, because otherwise
Lemma 7 would imply that all outgoing contracts would also be protected by
$v$, contradicting the assumption of the lemma. So some incoming contract is
protected by some party $x^{\prime}\neq v$. But then Lemma 5(b) implies that
all outgoing contracts must be protected by either $v$ or $x^{\prime}$, so we
must have $x^{\prime}=x$. ∎

######  Lemma 9.

A party $v$ has an incoming contract protected by $v$ if and only if it has an
outgoing contract protected by $v$.

###### Proof.

$(\Rightarrow)$ Suppose that $v$ has an incoming contract $(u,v)$ protected by
$v$. By Lemma 8, $u$ has an incoming contract $(u^{\prime},u)$ protected by
$v$. If $u^{\prime}\neq v$, by the same argument, $u^{\prime}$ must also have
an incoming contract protected by $v$. Repeating this process, we obtain a
backward path with all contracts protected by $v$. If this path did not reach
$v$ it would have to create a cycle in which all contracts are protected by a
party (namely $v$) outside this cycle, but this would contradict Corollary
4(b).

$(\Leftarrow)$ The argument is symmetric to that in part (a). Suppose that $v$
has an outgoing contract protected by $v$, say $(v,w)$. If $w\neq v$ then, by
Lemma 5, $w$ has an outgoing contract protected by $v$. Repeating this
process, we obtain a path with all contracts protected by $v$. If this path
did not reach $v$ it would have to create a cycle, but this would contradict
Corollary 4(b). ∎

The theorem below summarizes the local properties of the contracts involving a
party $v$. See also the illustration of this theorem in Figure 9.

######  Theorem 4.

Consider the contracts involving a party $v$, both incoming and outgoing.

(a) For each party $x$ (which may or may not be $v$), $v$ has an incoming
contract protected by $x$ if and only if $v$ has an outgoing contract
protected by $x$.

(b) If there are any contracts protected by $v$, then at least one incoming
contract protected by $v$ has a smaller timeout than all outgoing contracts
protected by $v$.

(c) There is at most one party $x\neq v$ that protects a contract involving
$v$. For this $x$, all timeouts of the outgoing contracts protected by $x$ are
smaller than all timeouts of the incoming contracts (no matter what party
protects them).

Figure 9: Illustration of Theorem 4. Each contract is labelled by its timeout
and the party that protects it. Per part (b), the minium timout $19$ of
incoming contracts protected by $v$ which is itself smaller than the minimum
timeout $20$ of outgoing contracts protected by $v$. Per part (c), the maximum
timeout $18$ of outgoing contracts protected by $x$ is smaller than the minium
timout $19$ of all incoming contracts.

###### Proof.

(a) This part is just a restatement of the properties established earlier. For
$x=v$, the statement is the same as in Lemma 9. For $x\neq v$, if $v$ has an
incoming contract protected by $x$ then, by Lemma 5, it must have an outgoing
contract protected by $x$, and if $v$ has an outgoing contract protected by
$x$ then, by Lemma 8, it must have an incoming contract protected by $x$.

(b) Let $(v,w)$ be an outgoing contract protected by $v$ whose timeout value
$\tau_{vw}$ is smallest. Consider any path $P$ from $w$ to $v$ with all
contracts on $P$ protected by $v$. (This path must exist. To see this,
starting from $w$ follow contracts protected by $v$. By Corollary 4(b),
eventually this process must end at $v$.) Then part (b) of Theorem 4 implies
that along this path timeut values must decrease, so its last contract $(u,v)$
must satisfy $\tau_{uv}<\tau_{vw}$. So the timeout value of $(u,v)$ is smaller
than that of $(v,w)$, and thus also smaller than all timeout values of the
outgoing contracts protected by $v$.

(c) Let $x\neq v$. If $v$ has an incoming contract protected by $x$ then, by
Lemma 5, all contracts involving $v$ but not protected by $v$ are protected by
$x$. If $v$ has an outgoing contract protected by $x$ then Lemma 8 implies
that some incoming contract is protected by $x$, which leads to the same
conclusion.

We now consider the claims about the timeout values. Let $(v,w)$ be an
outgoing contract protected by $x$, and let $(u,v)$ be an incoming contract.
Towards contradiction, suppose that in ${\mathbb{P}}$ the timeouts of these
contracts satisfy $\tau_{uv}\leq\tau_{vw}$. Denote by $t$ the first step of
${\mathbb{P}}$ after the contract creation phase. We consider two cases,
depending on whether $(u,v)$ is protected by $x$ or $v$.

Case 1: contract $(u,v)$ is protected by $x$. Suppose that in ${\mathbb{P}}$
the timeout of contract $(u,v)$ is $\tau_{uv}\leq\tau_{vw}$. We consider an
execution of ${\mathbb{P}}$ where all parties follow ${\mathbb{P}}$ until itme
$t-1$. Then, starting at time $t$, we alter the behavior of some parties, as
follows: all parties other than $v$, $w$ and $x$ will abort the protocol, $x$
will provide its secret $s_{x}$ to $w$, and $w$ will claim asset $(v,w)$ at
time $\tau_{vw}$. This way, the earliest $v$ can claim asset $(u,v)$ is at
time $\tau_{vw}+1$, which is after timeout $\tau_{uv}$ of $(u,v)$. Thus $v$
ends up in an unacceptable outcome, giving us a contradiction, which completes
the proof of (b).

Case 2: contract $(u,v)$ is protected by $v$. We can assume that its timeout
$\tau_{uv}$ is minimum among all incoming contracts protected by $v$.
(Otherwise, in the argument below replace $(u,v)$ by the incoming contract
protected by $v$ that has minimum timeout.) Let $(v,y)$ be any outgoing
contract protected by $v$. From part (b), we have that $\tau_{uv}<\tau_{vy}$.
Let also $(z,v)$ be any incoming contract protected by $x$.

We now consider an execution of ${\mathbb{P}}$ where all parties follow the
protocol until time $t-1$. At time $t$, all parties other than $u,v,x,y,z$
abort the protocol, and $x$ gives its secret $s_{x}$ to $w$. As time proceeds,
$v$ may notice that some parties do not follow the protocol, so, even though
$v$ is honest, from this time on it is not required to follow the protocol. We
show that independently of $v$’s behavior, it will end up in an unacceptable
outcome, contradicting the safety property of ${\mathbb{P}}$.

To this end, we consider two possibilities. If $v$ does not claim $(u,v)$ at
or before time $\tau_{uv}$, then $w$ can claim $(v,w)$ at time $\tau_{vw}$, so
$v$ will lose asset $(v,w)$ without getting asset $(u,v)$. On the other hand,
if $v$ claims $(u,v)$, then $u$ can give secret $s_{v}$ to $y$ that can then
claim asset $(v,y)$, and $w$ will not claim asset $(v,w)$, so $v$ will not be
able to claim asset $(z,v)$, as it will not have secret $s_{x}$. In both
cases, the outcome of $v$ is unacceptable. ∎

We now use the above properties to establish some global properties of
${\mathbb{P}}$. These properties involve paths and cycles in $G$. The first
corollary extends Corollary 4, and is a direct consequence of Theorem 4(b).

######  Corollary 10.

If on some path each contract except possibly first is not protected by the
seller, then along this path the timeout values strictly decrease.

The next corollary follows from Corollaries 4 and 10.

######  Corollary 11.

Let $P$ be a path such that all contracts on $P$ except possibly first are
protected by a party $x$ that is not an internal vertex of $P$. Then all
contract creation times along $P$ strictly increase and all timeout values
strictly decrease.

######  Corollary 12.

(a) Let $(u,v)$ be a contract protected by some party $x$ other than $v$.
Consider a path $P$ starting with arc $(u,v)$, that doesn’t contain $x$ as an
internal vertex and on which each contract is not protected by its seller.
Then all contracts along $P$ are protected by $x$.

(b) Let $(u,v)$ be a contract protected by some party $x$ other than $u$.
Consider a path $P$ ending with arc $(u,v)$, that doesn’t contain $x$ as an
internal vertex and on which each contract is not protected by its buyer. Then
all contracts along $P$ are protected by $x$.

###### Proof.

(a) The corollary follows easily by repeated application of Theorem 4. Let
$(v,w)$ be the second arc on $P$. By the assumption, $(v,w)$ is not protected
by $v$, and since $v$ has an incoming contract protected by $x$ and $x\neq v$,
Theorem 4 implies that contract $(v,w)$ must be also protected by $x$. If
$w=x$, this must be the end of $P$. If $w\neq x$, then $w$ has an incoming
contract protected by $x$, so we can repeat the same argument for $w$, and so
on. This implies part (a).

(b) The proof for this part is symmetric to that for part (a), with the only
difference being that we proceed now backwards from $u$ along $P$. ∎

######  Theorem 5.

(a) Let $P$ be a simple path starting at a vertex $x$ whose last contract is
protected by $x$. Then all contracts on $P$ are protected by $x$.

(b) Let $Q$ be a simple path ending at a vertex $x$ whose first contract is
protected by $x$. Then all contracts on $Q$ are protected by $x$.

###### Proof.

(a) Let $P=u_{1},u_{2},...,u_{p+1}$, where $u_{1}=x$ and $(u_{p},u_{p+1})$ is
protected by $x$. The proof is by contradiction. Suppose that $P$ violates
part (a), namely it contains a contract not protected by $x$. (In particular,
this means that $p\geq 2$.) We can assume that among all simple paths that
violate property (a), $P$ is shortest. (Otherwise replace $P$ in the argument
below by a shortest violating path.) Then $(u_{p-1},u_{p})$ is not protected
by $x$, because otherwise the prefix of $P$ from $x$ to $u_{p}$ would be a
violating path shorter than $P$. So $(u_{p-1},u_{p})$ is protected by $u_{p}$.
Using Lemma 6, each contract on the path $u_{1},u_{2},...,u_{p}$ is not
protected by the seller. Since $(u_{p},u_{p+1})$ is protected by $x$ and
$x\neq u_{p}$, each contract on $P$ is not protected by its seller.

Figure 10: Illustration of the proof of Theorem 5(a). Path $P$ is marked with
solid arrows, path $P^{\prime}$ is marked with dashed arrows. Here, $p=8$ and
$u_{1}=x$. The labels on edges show the parties that protect them.

Next, we claim that there is a simple path $P^{\prime}$ from $u_{p+1}$ to $x$
whose all contracts are protected by $x$. If $u_{p+1}=x$, this is trivial, so
assume that $u_{p+1}\neq x$. Then, since $u_{p+1}$ has an incoming contract
protected by $x$ and $x\neq u_{p+1}$, $u_{p+1}$ must have an outgoing contract
$(u_{p+1},w)$ protected by $x$. If $w=x$, we are done. Else, we repeat the
process for $w$, and so on. Eventually, extending this path we must end at
$x$, for otherwise we would have a cycle with all contracts protected by $x$
but not containing $x$, contradicting Corollary 4(b). This proves that such
path $P^{\prime}$ exists. Since all contracts on $P^{\prime}$ are protected by
$x$, they are not protected by their sellers.

Finally, let $C$ be the cycle obtained by combining paths $P$ and
$P^{\prime}$. (See Figure 10.) As shown above, every contract on $C$ is not
protected by its seller. But this contradicts Corollary 4, completing the
proof of part (a).

(b) Let $Q=v_{0},v_{1},...,v_{q}$, where $v_{q}=x$ and $(v_{0},v_{1})$ is
protected by $x$. Towards contradiction, suppose that some contract on $Q$ is
not protected by $x$. Analogously to part (a) we can make two assumptions:
One, we can assume that $q\geq 2$ and $(v_{1},v_{2})$ is not protected by $x$,
which implies that it is protected by $v_{1}$. Two, we can assume that there
is a simple path $Q^{\prime}$ from $v_{1}$ to $x$ with all contracts protected
by $x$.

The rest of the proof is also similar to the proof of (a), but with a twist
(because we do not have an analogue of Corollary 4 for buyers). The idea is to
divide $Q$ into segments protected by the same party, for each segment take a
reverse path protected by this party, and combine these reverse paths into a
path $T$ from $v_{q}$ to $v_{1}$, with each contract not protected by its
seller.

We now describe this construction. By the argument identical (except for
reversing direction) to that in Lemma 6, each contract $(v_{i},v_{i+1})$, for
$i\geq 1$, is protected by one of parties $v_{1},v_{2},...,v_{i}$. Further,
for each party $v_{i}$, where $i\notin{\left\\{{0,q-1}\right\\}}$, the
contracts protected by $v_{i}$ (if any) form a segment of $Q$ starting at
$v_{i}$. Let $A$ consist of all indices $i$ for which contract
$(v_{i},v_{i+1})$ is protected by $v_{i}$, and also include $q$ in $A$. Order
$A$ in increasing order $a_{1}<a_{2}<...<a_{s}$. So $a_{1}=1$, $a_{s}=q$, and
for each $r=1,2,...,s-1$ the segment $v_{a_{r}},v_{a_{r}+1},....,v_{a_{r+1}}$
of $Q$ has all contracts protected by $v_{a_{r}}$.

Figure 11: Illustration of the proof of Theorem 5(b). Path $Q$ is marked with
solid arrows. Here, $q=9$ and $v_{9}=x$. Path $Q^{\prime}$ is marked with
dashed arrows. $Q$ is divided into three segments, protected by $v_{1}$,
$v_{4}$, and $v_{6}$, respectively. So $a_{1}=1$, $a_{2}=4$, $a_{3}=6$, and
$a_{4}=9$. The corresponding reverse paths are $T_{1}$, $T_{4}$ and $T_{6}$,
marked with dotted arrows.

For each $r=2,3,...,s$, contract $(v_{a_{r}-1},v_{r_{a}})$ is protected by
$v_{r_{a}-1}$. By the same argument as in (a), we then obtain that there is a
simple path $T_{a_{r}-1}$ from $v_{r_{a}}$ to $v_{a_{r}-1}$ with all contracts
protected by $v_{a_{r}-1}$, so none protected by its seller. The concatenation
of these paths forms a path $T$ from $v_{r_{s}}=v_{q}$ to $v_{a_{1}}=v_{1}$.
So each contract on $T$ is not protected by its seller.

To finish, combine the two paths $T$ and $Q^{\prime}$ into a cycle $C$. On
$C$, each contract is not protected by the seller. This contradicts Corollary
4, completing the proof. ∎

###  5.2 Proof of the $\boldsymbol{(\Leftarrow)}$ Implication in Theorem 1

In this section we use the protocol properties established in the previous
section to prove necessary conditions for a digraph to admit an atomic HTLC
protocol. We start with protocols that use only one common hashlock for the
whole graph.

######  Lemma 13.

Suppose that $G$ has an atomic HTLC protocol ${\mathbb{P}}$ in which only one
party creates a secret/hashlock pair. Then $G$ must be a bottleneck graph.

###### Proof.

Strong connectivity is a required property for _any_ atomic protocol to exist,
see [8]. If $x$ is the party that created the secret/hashlock pair, then
Corollary 4 implies that any cycle in $G$ must contain $x$. Thus $x$ is a
bottleneck of $G$, proving the theorem. ∎

We now consider the general case, when all parties are allowed to create
secret/hashlock pairs. The lemma below establishes the $(\Rightarrow)$
implication in Theorem 1.

######  Lemma 14.

Suppose that $G$ has an atomic HTLC protocol ${\mathbb{P}}$. Then $G$ must be
a reuniclus digraph.

###### Proof.

Recall what we have established so far in Section 5.1. From Theorem 4(c) we
know that, for each party $u$, all contracts involving $u$ as a party are
protected either by $u$ or by just one other party. Using this property, we
define the control relation on parties, as follows: If $u$ has any contracts
protected by some other party $x$, we will say that $x$ _controls_ $u$. Let
$\cal{K}$ be a digraph whose vertices are the parties that created
secret/hashlock pairs, and each arc $(u,x)$ represents the control relation,
meaning that $x$ controls $u$. We want to prove that $\cal{K}$ is a tree.

Each node in $\cal{K}$ has at most one outgoing arc. This property already
implies that each connected component of $\cal{K}$ is a so-called _1-tree_ ,
namely a graph that has at most one cycle. So in order to show that $\cal{K}$
is actually a tree, it is sufficient to show the two claims below.

######  Claim 15.

$\cal{K}$ does not have any cycles.

We now prove Claim 15. Towards contradiction, suppose that $\cal{K}$ has a
cycle, say $C=v_{1},v_{2},...,v_{k},v_{k+1}$, where $v_{k+1}=v_{1}$. Consider
any arc $(v_{i},v_{i+1})$ on $C$. This arc represents that $v_{i+1}$ controls
$v_{i}$. So, in $G$, $v_{i}$ has an outgoing contract protected by $v_{i+1}$.
Let $P_{i}$ be any path in $G$ starting with this contract and ending at
$v_{i+1}$. Then Theorem 5(b) gives us that all contracts on $P_{i}$ protected
by $v_{i+1}$. Combining these paths $P_{1},...,P_{k}$ we obtain a cycle
$C^{\prime}$ in $G$. Then in $C^{\prime}$, each contract is not protected by
its seller, which would contract Corollary 4(b). This completes the proof of
Claim 15.

######  Claim 16.

$\cal{K}$ has only one tree.

From Claim 15 we know that each (weakly) connected component of $\cal{K}$ is a
tree. The roots of these trees have the property that they are not protected
by any other party. To prove Claim 16, suppose towards contradiction that
$\cal{K}$ has two different trees, and denote by $r$ and $r^{\prime}$ the
roots of these trees. Since $r,r^{\prime}$ are roots of trees, all contracts
involving $r$ are protected by $r$ and all contracts involving $r^{\prime}$
are protected by $r^{\prime}$. Consider any simple path
$P=u_{1},u_{2},...,u_{k}$ from $u_{1}=r$ to $r^{\prime}=u_{k}$. Since the last
contract on $P$ is protected by $r^{\prime}$ and $r^{\prime}$ is not in
${\left\\{{u_{1},u_{2},...,u_{k-1}}\right\\}}$, Lemma 6 implies that all
contracts on this path are not protected by their sellers. But this
contradicts the fact that $(u_{1},u_{2})$ is protected by $u_{1}$. This
completes the proof of Claim 16.

We now continue with the proof of the theorem. Denote by
$b_{1},b_{2},...,b_{p}$ the nodes of $\cal{K}$. For each $b_{j}$, define
$G_{j}$ to be the subgraph induced by the contracts protected by $b_{j}$. That
is, for each contract $(u,v)$ protected by $b_{j}$ we add vertices $u$, $v$
and arc $(u,v)$ to $G_{j}$. The necessary properties (rg1) and (rg2) follow
from our results in Section 5.1. It remains to show that subgraphs graphs
$G_{1},G_{2},...,G_{p}$, together with tree $\cal{K}$, satisfy conditions
(rg1) and (rg2) that characterize reuniclus graphs.

Consider some $u\neq b_{j}$ that is in $G_{j}$. By the definition of $G_{j}$,
$u$ is involved in a contract protected by $b_{j}$. Then Theorem 4 gives us
that $u$ has both an incoming and outgoing contract protected by $b_{j}$. Take
any path $P$ starting at an outgoing contract of $u$ protected by $b_{j}$ and
ending at $b_{j}$. Then Theorem 5(b) implies that all contracts on $P$ are
protected by $b_{j}$. By the same reasoning, there is a path $P^{\prime}$
starting at $b_{j}$ and ending with an incoming contract of $u$ protected by
$b_{j}$. Then, by Theorem 5(a) all contracts on $P^{\prime}$ are protected by
$b_{j}$. This gives us that $G_{j}$ is strongly connected. And, by Corollary
4, $G_{j}$ cannot contain a cycle not including $b_{j}$. Therefore $G_{j}$ is
a bottleneck graph with $b_{j}$ as its bottleneck.

We also need to prove that $G_{j}$ is in fact an induced subgraph, that is, if
$u,v\in G_{j}$ and $G$ has an arc $(u,v)$, then $(u,v)\in G_{j}$ as well. That
is, we need to prove that $(u,v)$ is protected by $b_{j}$. Suppose, towards,
contradiction, that $(u,v)$ is protected by some $b_{i}\neq b_{j}$. Then both
$u$ and $v$ are involved in contracts protected by both $b_{i}$ and $b_{j}$,
and this implies that $u=b_{i}$ and $v=b_{j}$, or vice versa. And this further
implies that $b_{i}$ would be protected by $b_{j}$ and vice versa, which would
be a cycle in $\cal{K}$, contradicting that $\cal{K}$ is a tree. This
completes the proof of property (rg1).

Finally, consider property (rg2). If a vertex $u$ is not any of designated
bottlebeck vertices $b_{1},b_{2},...,b_{p}$, then, by Theorem 4, all its
contracts are protected by the same party, which means that it belongs to
exactly one graph $G_{j}$. On the other hand, if $u=b_{j}$, then again by
Theorem 4, it is involved in only in contracts protected by itself and one
other party, say $b_{i}$. But then it belongs only to $G_{j}$ and $G_{i}$,
completing the proof of (rg2). ∎

## References

  * [1] N. Asokan, Matthias Schunter, and Michael Waidner.  Optimistic protocols for fair exchange.  In Proceedings of the 4th ACM Conference on Computer and Communications Security, CCS ’97, pages 7–17, New York, NY, USA, 1997. ACM.
  * [2] N. Asokan, Victor Shoup, and Michael Waidner.  Optimistic fair exchange of digital signatures.  IEEE Journal on Selected Areas in Communications, 18:593–610, 1997\.
  * [3] Michael Ben-Or, Oded Goldreich, Silvio Micali, and Ronald L. Rivest.  A fair protocol for signing contracts.  In Wilfried Brauer, editor, Automata, Languages and Programming, pages 43–52, Berlin, Heidelberg, 1985. Springer Berlin Heidelberg.
  * [4] Eric Chan, Marek Chrobak, and Mohsen Lesani.  Cross-chain swaps with preferences.  In 36th IEEE Computer Security Foundations Symposium, CSF 2023, Dubrovnik, Croatia, July 10-14, 2023, pages 261–275. IEEE, 2023.
  * [5] Apoorvaa Deshpande and Maurice Herlihy.  Privacy-preserving cross-chain atomic swaps.  In International Conference on Financial Cryptography and Data Security, pages 540–549. Springer, 2020.
  * [6] Matt Franklin and Gene Tsudik.  Secure group barter: Multi-party fair exchange with semi-trusted neutral parties.  In Rafael Hirchfeld, editor, Financial Cryptography, pages 90–102, Berlin, Heidelberg, 1998. Springer Berlin Heidelberg.
  * [7] Ethan Heilman, Sebastien Lipmann, and Sharon Goldberg.  The arwen trading protocols.  In International Conference on Financial Cryptography and Data Security, pages 156–173. Springer, 2020.
  * [8] Maurice Herlihy.  Atomic cross-chain swaps.  In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC ’18, pages 245–254, New York, NY, USA, 2018. ACM.
  * [9] Maurice Herlihy, Barbara Liskov, and Liuba Shrira.  Cross-chain deals and adversarial commerce.  arXiv preprint arXiv:1905.09743, 2019.
  * [10] Soichiro Imoto, Yuichi Sudo, Hirotsugu Kakugawa, and Toshimitsu Masuzawa.  Atomic cross-chain swaps with improved space and local time complexity, 2019.
  * [11] Subhra Mazumdar.  Towards faster settlement in htlc-based cross-chain atomic swaps, 2022\.
  * [12] Silvio Micali.  Simple and fast optimistic protocols for btcwiki electronic exchange.  In Proceedings of the Twenty-second Annual Symposium on Principles of Distributed Computing, PODC ’03, pages 12–19, New York, NY, USA, 2003. ACM.
  * [13] Sri AravindaKrishnan Thyagarajan, Giulio Malavolta, and Pedro Moreno-Sánchez.  Universal atomic swaps: Secure exchange of coins across all blockchains.  Cryptology ePrint Archive, 2021.
  * [14] Tier Nolan.  Alt chains and atomic transfers.  https://bitcointalk.org/index.php?topic=193281.msg2224949#msg2224949, 2013\.  [Online; accessed 23-January-2021].
  * [15] Yingjie Xue and Maurice Herlihy.  Hedging against sore loser attacks in cross-chain transactions.  In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, PODC’21, page 155–164, New York, NY, USA, 2021. Association for Computing Machinery.