Invited Paper: Fault-tolerant and Expressive Cross-Chain Swaps

A blockchain is a ledger (or database) that tracks ownership of assets. A blockchain is tamper-proof, meaning that it can be trusted to process transactions correctly and store data reliably. We assume blockchains supports smart contracts (or contracts). A smart contract is a program residing on the blockchain that can own and transfer assets. Contract code and state are public. A contract is deterministic since it is executed multiple times for reliability. A contract can read and write data on the same blockchain where it resides, and it can invoke functions exported by other contracts on the same blockchain, but it cannot directly access data or contracts on other blockchains. A party is a blockchain client, such as a person or an organization. A party can send transactions to be executed on the blockchain. When we say transactions, we mean transactions that happen on a single blockchain, including asset transfers, smart contract initialization, and calling smart contract functions.

We assume a synchronous communication model where there is a known upper bound $\Delta$ on the time needed for a transaction issued by one party to included and confirmed ¹¹1The mining process to include a transaction in a block and the confirmation of the block take a non-trivial time, see more in (Poon and Dryja, 2016). Local computation is considered instantaneous.in a blockchain and to become visible to others.

As mentioned, blockchains are assumed to be tamper-proof, and calls to smart contract functions are executed correctly. We rule out attacks on blockchain itself, for example, denial-of-service attacks. Parties can be Byzantine, departing arbitrarily from any agreed-upon protocol. We do not assume Byzantine parties are rational: they may act against their own self-interest. Because smart contracts typically reject ill-formed transactions, Byzantine parties are limited in how they can misbehave.

We make standard cryptographic assumptions. We assume a computationally bounded polynomial-time adversary. The hash function in our scheme is collision-resistant. Each party is equipped a public key and a private key, and the public keys are known to all. Participants use standard public key algorithms, e.g. ECDSA (Johnson et al., 2001), to sign their transactions so that they cannot be forged. We use $sig(m,u)$ to denote the signature generated by a party $u$ where he/she signs a message $m$ using his/her secret key.

An atomic cross-chain swap is represented by a directed graph. A directed graph(or digraph) $G=(V,A)$ is a set of vertices $V$ and a set of arcs $A\subseteq V\times V$. Each vertex represents a party, and each arc is labeled with an asset. A path from $u$ to $v$ in $G$ is a sequence of arcs $(v_{0},v_{1}),\ldots,(v_{k-1},v_{k})$ where $u=v_{0}$ and $v=v_{k}$, and each arc $(v_{i},v_{i+1})\in A$. A digraph is strongly connected if there is a path from any vertex to any other vertex.

An arc $(u,v)$ represents a proposed asset transfer from party $u$ to party $v$. All digraphs considered here are strongly connected, implying that all transfers are (perhaps indirect) exchanges. In real life, some exchanges may have off-chain components. For example, if Alice uses a token to pay for a sandwich, we would formally represent the off-chain food transfer as a “virtual” token transferred from the restaurant to Alice.

For brevity, when discussing a swap defined by a digraph, we use the terms vertex and party interchangeably. We use ”arc $(a,b)$” as shorthand for ”proposed transfer from party $a$ to party $b$”, and we say an arc is triggered if that proposed transfer takes place.

Generally speaking, an atomic swap works in the following way: an asset is first escrowed and protected by locks, and then the asset is transferred to the recipient upon unlock. Here we describe the lock mechanism used in the atomic swap protocol described later.

Let $Hash(.)$ be a collision-resistant hash function. A pair of value $s$ and $h$, where $s$ is a secret random value, and $h=Hash(s)$, forms a “lock and key” structure: a lock $h$ can be unlocked when the key $s$ such that $h=Hash(s)$ is shown. A hashlock is such a lock, augmented with more information in the hashkey to keep track of the propagation of the secret $s$ on the graph.

Formally, a hashlock is a hash value $h$. The structure to unlock hashlocks is called a hashkey. Given a digraph $G=(V,A)$, a hashkey on an arc $(u,v)$ is a triple $(s,p,\sigma)$, where $s$ is a randomly-chosen value called a secret, $p$ is a path $(u_{0},...,u_{k})$ from $u_{0}$ to $u_{k}$ in the graph where $u_{0}=v$, $u_{k}$ is the party who chose $s$. $\sigma$ is called a path signature, where each party in the path $p$ provides a signature. Recall that $sig(m,u)$ denotes the signature of a party $u$ signing a message $m$ using his/her secret key. $\sigma$ is a signature composed recursively by each party $u_{j}$ in the path signs the signature of $u_{j+1}$ as a message using their secret key. More formally,

A hashkey $(s,p,\sigma)$ has its lifespan. The exact definition of the lifespan and more details can be found in the original document  (Herlihy, 2018). In short, the hashkey $(s,p,\sigma)$’s lifespan is linear to the length of the path: it times out at $|p|\Delta$, where $\Delta$ is the upper bound of message delay defined in Section 2.2 ²²2More precisely, it times out at $(MaxPathLength(G)+|p|)\Delta$ after the protocol starts. Here we focus on brevity other than precision.

We say a hashkey matches a hashlock if it can unlock the hashlock. On any arc $(u,v)$, its hashlock $h$ can be unlocked by a hashkey $(s,p,\sigma)$ if and only if all of the following condition holds. (1) $h=Hash(s)$,(2) $p$ is a path from $v$ to the party who chose $s$. (3) $\sigma$ is a valid path signature for $s$ and $p$ constructed as Eq.1. (4) The hashkey does not time out. Roughly speaking, the hashkey structure guarantees that, if a hashlock $h$ on an outgoing arc from $u$ is unlocked, then $h$ on all arcs entering $u$ can be unlocked.

A hashlock circuit $C(u,v)$ for an arc $(u,v)$ is a formula linking hashlocks on that arc via operators $\vee$, $\wedge$ and $\neg$.

Here we describe a protocol  (Herlihy, 2018) that is atomic, but not robust. It does not support alternative swaps, but it does provide a starting point for developing robust protocols.

The swap is represented as a strongly-connected directed graph $G=(V,A)$, where each arc represents a proposed asset transfer. Each transfer along an arc is controlled by a contract. We say an asset is escrowed on an arc when the owner forfeits the asset’s control to the contract on the arc.

The protocol starts with a feedback vertex set (FVS), a set of vertices whose removal leaves the graph without cycles. The vertices in the FVS are called leaders, the rest followers. At the beginning, each leader $l_{i}$ chooses a random secret $s_{i}$ and construct the hashlock $h_{i}=Hash(s_{i})$. After the hashlocks are distributed among the leaders, the protocol can start running on the blockchains. Each contract/arc is associated with a hashlock circuit $C=\bigwedge_{l_{i}\in FVS}h_{i}$ to protect the escrowed asset. When a hashlock is unlocked, it evaluates to $\mathit{true}$ and when the hashlock circuit evaluates to $\mathit{true}$, the asset is redeemed by the proposed recipient. We call an arc is triggered when the asset is redeemed.

Overview of the protocol is shown in Figure 2. The protocol consists of two phases: Escrow phase and Redeem phase. Note that transactions sent to blockchains can included on blockchains and observed by others within $\Delta$.

In the Escrow phase, each leader escrows their assets on all outgoing arcs (Leader Step a). Then the leaders start waiting for their incoming arcs before they enter redeem phase (Leader Step b). Followers first wait until all the incoming arcs are escrowed (Follower Step a), then they escrow their assets on the outgoing arcs (Follower Step b).

The total amount of assets by a party escrowed is called the party’s collateral. During the Escrow phase if any expected escrow does not arrive for an extended period the party should just abort the protocol.

In the Redeem phase, hashkeys are sent to contracts that manage their assets to unlock hashlocks. For a leader $l_{i}$, if it has observed that all its incoming assets are escrowed, it constructs a hashkey $(s_{i},l_{i},sig(s_{i},l_{i}))$ and sends it to corresponding contracts representing all its incoming arcs (Leader Step c). The hashlock $h_{i}$ associated with the contracts can be unlocked upon receiving $(s_{i},l_{i},sig(s_{i},l_{i}))$. Then both leaders and followers can propagate the secrets (Leader Step d and Follower Step c) using the hashkey structure. For a party $u$, when a hashlock on its outgoing arcs is unlocked by a hashkey $(s,p,\sigma)$, it can construct and send the hashkey $(s_{i},u||p,sig(\sigma,u))$ to all contracts managing its incoming arcs to unlock the same hashlock.

The hashkey mechanism guarantees that if any party observes a matching hashkey sent to its outgoing arc, there is one more $\Delta$ allowing it to send a new matching hashkey to all of its incoming arcs. If all secrets are propagated correctly, all hashlocks are unlocked, and all the assets will be redeemed.

There is an additional time-out structure that ensures that assets cannot be escrowed forever, which is described in the original document (Herlihy, 2018). In short, if a hashlock cannot be unlocked anymore, the asset will be refunded. .

In summary, the atomic swap protocol satisfies liveness: if all parties conform, all asset transfers happen. It also satisfies safety: a conforming party $u$’s assets are all refunded if $u$ does not receive all its incoming assets. We call atomic swaps as all-or-nothing swaps because of those properties.

The directed graph formalism suffices to describe all-or-nothing swaps, where success means all proposed transfers take place. We now define a way to describe swaps where parties also accept outcomes where only a subset of the proposed swaps take place.

We first define a boolean variable $v$ on each arc. $v$ is $\mathit{true}$ if the transfer it represents takes place, and $\mathit{false}$ otherwise. An acceptable outcome for a party $x$ can be represented with a boolean predicate of its incoming and outgoing arcs. Suppose party $x$ has incoming arcs $i_{1}$, $i_{2}$, outgoing arcs $o_{1}$, $o_{2}$, and $x$ wants to exchange $o_{1}$ with $i_{1}$, or exchange $o_{2}$ with $i_{2}$. Naively one would construct the predicate as $(o_{1}\wedge i_{1})\vee(o_{2}\wedge i_{2})$. Looking at it closely, this predicate definition has two problems. Firstly, it does not capture safety. When $o_{1}\wedge i_{1}$ is $\mathit{true}$, this predicate will be $\mathit{true}$ even if $o_{2}$ is $\mathit{true}$, but this would mean that $x$ is paying both $o_{1}$ and $o_{2}$, i.e. $x$ overpays. Secondly, it does not allow $x$ to accept greedy outcome. If $i_{1}$ is $\mathit{true}$, and all other arcs are $\mathit{false}$, it is perfectly acceptable to $x$, but our predicate evaluates $\mathit{false}$ to this situation.

To capture their expected exchanges (liveness), safety requirements, and allow greediness, each party has liveness and safety requirements, characterizing acceptable outcomes in the (partial) success and failure cases respectively. First, we consider safety requirements. For each possible outgoing asset, there is an income predicate associated with it. That captures the payoff that, if this party pays this asset, what should they get at least to be safe. Note that, a participant may want some exchanges to happen atomically, say does not pay an asset unless getting a bundle of other assets even though get a subset of them already gives him/her a better payoff. This is also characterized as a safety requirement. The safety requirement for party $x$ is given by a predicate $S_{x}$.

In Example I, we use the arc ”$(a,c)$” as shorthand for “the asset labeling arc $(a,c)$ is transferred from party $a$ to party $c$”. Alice’s safety predicate is

meaning that if Alice transfers her assets to Carol (“$(a,c)$”) then Bob transfers his assets to her (“$(b,a)$”). Importantly, Alice can be greedy. Her predicate is satisfied if she gets something for nothing: that is, if Bob pays her but she somehow does not pay Carol. This predicate is also satisfied if no payments are made, an outcome that Alice may not prefer, but considers acceptable because it leaves her no worse off. The no payment scenario incentives Alice to try alternatives.

Formally, for every asset $\gamma$ that a party $x$ may pay, there is an income predicate $I_{x}^{\gamma}$. In addition, there is a predicate $O_{x}$ over those outgoing payments to make sure $x$ does not overpay, for example, the predicate may require that at most two of three outgoing assets are paid.

In Example II, Alice’s predicate is

The first two clauses say that if Alice pays either Carol or David, then she gets Bob’s NFT in exchange, and the third clause says that Alice does not want to pay both.

In general, if party $x$ has potential exchanges with parties $u_{1},\ldots,u_{k}$, then $x$’s safety predicate has the form:

where each implication clause states that if $x$ pays $u_{i}$ it gets the agreed-upon amount in return, and the final clause limits how many of the outgoing payments’ clauses $(x,u_{i})$ can be $\mathit{true}$. For example $O_{x}$ might say “no more than one of the $k$ transfers can occur”, or “no more than $m$”, or “at least $m$”, and so on.

Next, we consider liveness requirements. The liveness requirement for party $x$ is given by a predicate $L_{x}$. First, the liveness predicate contains the safety predicate since this is a property that should always hold. In addition to safety, liveness characterizes that something good should happen. That means, one of the income predicates $x$ specified previously in safety requirements should be $\mathit{true}$. That is,

The predicate for each party $x$ is denoted as $P_{x}$, which consists of two predicates $L_{x}$ and $S_{x}$. Unless otherwise specified, $P_{x}$ means $S_{x}$, since $S_{x}$ should always be $\mathit{true}$, while, reasonably, $L_{x}$ is $\mathit{true}$ only if a party completes an asset transfer. Thus, $L_{x}$ is implied implicitly in $P_{x}$, since if a party transfers an asset to someone, one of its income predicates in $S_{x}$ must be $\mathit{true}$.

Suppose Alice would like to exchange 1 Xcoin for 1 Ycoin. She sets up alternative trades with Bob and Carol, but she is willing to trade with only one of them. Bob expects to exchange 1 Ycoin for 1 Xcoin, with either Alice or Carol, but not both. Carol is willing to trade with Alice, or Bob, or both.

The predicates are as follows. For brevity, arcs are labeled as shown in Figure 3. (For example, $a_{1}$ is the arc from Alice to Bob.)

A robust cross-chain swap can be described by a digraph $G=(V,A)$ accompanied with a set of predicates from all participants. Each arc in $G$ is a proposed asset transfer. An arc is set to $\mathit{true}$ if the asset transfer happens. A predicate is satisfied if it evaluates to $\mathit{true}$. Is there a trade that satisfies every party’s predicate? Whether such a trade exists is the satisfiability problem. If not, then the proposed trade is infeasible.

We should first find solutions that satisfy all parties’ predicates. A solution $s$ is an assignment that satisfies all parties’ predicates, where each arc is assigned a Boolean. ³³3The trade where no assets are transferred is acceptable to all parties, but we exclude that solution as trivial. For example, here is one possible solution for the digraph shown in Figure 3:

After finding solutions, we can map them to feasible swaps. In each solution $s$, we look at the set of arcs that $s$ assigns to $\mathit{true}$, which forms a digraph denoted as $G_{s}$. The set of transfers in $G_{s}$, if executed atomically, will satisfy all parties. A digraph $G_{s}$ is a called feasible swap, or an alternative.

If there is more than one such feasible swap, it is tempting to execute all the alternatives in parallel, because some alternatives might fail. The following describes challenges that arise if we try to execute the alternatives in parallel.

1. (1)

   Alternatives may conflict: in one solution, Alice pays Bob and not Carol, but in another, she pays Carol and not Bob. Completing both swaps would cause Alice to overpay.

2. (2)

   Alternatives may charge twice for the same transfers: if there are two solutions where Alice pays Bob, then Alice has to escrow the same amount of assets twice. Alice’s collateral would exceed the value of the assets she trades away.

3. (3)

   Trades are not independent when one alternative’s digraph is a subgraph of the other. For example, Figure 4 shows two solutions. In $s_{1}$, Alice and Carol trade only with one another, setting only $a_{2},c_{1}$ to $\mathit{true}$. Suppose Alice is the only leader. In $s_{2}$, Alice trades with Carol, and Carol with Bob, setting $a_{2},c_{1},b_{2},c_{2}$ to $\mathit{true}$. Suppose Alice and Bob are leaders. To complete both alternatives, Alice would have to create and release secrets for both $s_{1},s_{2}$. She might not have an incentive to participate in $s_{2}$, since that alternative provides her no additional robustness.

To tackle the challenges, we first describe some concepts and building blocks for our proposed protocols.

We propose two novel protocols for composable and robust cross-chain swaps. These protocols make different trade-offs: one optimizes for time at the cost of higher collateral, and the other makes the opposite choice.

$\mathit{ProtocolA}$ prioritizes time over collateral. In the best case, when all parties conform to the protocol and avoid delays, the trade can be completed in a short time. In the worst case, when all trades fail, the parties’ assets are refunded quickly. The catch is that parties must provide higher collateral: parties must create separate escrows for each alternative, temporarily tying up more assets than are eventually traded.

$\mathit{ProtocolB}$ prioritizes collateral over time. A party can use a single escrow for multiple alternatives. The catch is that the trade takes longer to settle: transfers require a hard timeout even when all parties conform to the protocol and avoid unnecessary delay. $\mathit{ProtocolB}$ also provides more fault-tolerance than $\mathit{ProtocolA}$. See Section A.2 for more details.

This section describes $\mathit{ProtocolA}$, a protocol that favors time over collateral. Given a predicated digraph $({\mathcal{P}},G)$, we first find a set of solutions $s_{1},\cdots s_{k}$ by identifying sets of arcs such that executing trades on those sets satisfies $\phi({\mathcal{P}})$. Such solutions could be generated by an all-SAT solvers (Toda and Soh, 2016; Yu et al., 2014; Toda, 2015), though it may not be necessary to identify all solutions. The parties run these solutions in parallel. The follow summarizes $\mathit{ProtocolA}$.

• •

  To control conflicting trades, each redundancy provider uses distinct hashlocks in distinct solutions. In the Redeem Phase, that party can choose which hashlocks to unlock.

• •

  A party can add additional hashlocks after an asset is escrowed, allowing overlapping arcs in different solutions, indexed by their hashlocks.

• •

  If $G_{s_{1}}\subsetneq G_{s_{2}}$, then the hashlocks on $G_{s_{1}}$ are reused in $G_{s_{2}}$.

First, the parties set up a mutually-agreeable trade, and express their requirements in the form of predicates, yielding a predicated digraph $({\mathcal{P}},G)$. We assume the predicates are reasonable and if not, a party can be rejected to join in the trade. A preliminary Market Clearing Phase decides what swaps are feasible, and what hashlocks to use in each swap.

Here is a high-level sketch of $\mathit{ProtocolB}$.

We focus on the difference between $\mathit{ProtocolA}$ and $\mathit{ProtocolB}$ in the description.

Solutions that can conflict with each must be ranked to decide which one is preferable. This ranking is established by some kind of negotiation. Participants who are not proposers can accept if the proposed order is acceptable and leave the deal otherwise. We can design a more sophisticated protocol to make a smarter decision. Details are left to interested readers.

Let $S$ be the set of solutions output by an all-SAT solver. Here are some desired properties for both protocols.

We compare the two proposed protocols with prior protocols in Section A.2.