Cross-chain Swaps with Preferences Eric Chan University of California at RiversideMarek Chrobak

2025-05-06 0 0 2.79MB 23 页 10玖币

侵权投诉

Cross-chain Swaps with Preferences

Eric Chan

University of California at Riverside

Marek Chrobak

University of California at Riverside

Mohsen Lesani

University of California at Riverside

Abstract—Extreme valuation and volatility of cryptocurrencies

require investors to diversify often which demands secure exchange

protocols. A cross-chain swap protocol allows distrusting parties

to securely exchange their assets. However, the current models

and protocols assume predeﬁned user preferences for acceptable

outcomes. This paper presents a generalized model of swaps

that allows each party to specify its preferences on the subsets

of its incoming and outgoing assets. It shows that the existing

swap protocols are not necessarily a strong Nash equilibrium in

this model. It characterizes the class of swap graphs that have

protocols that are safe, live and a strong Nash equilibrium, and

presents such a protocol for this class. Further, it shows that

deciding whether a swap is in this class is NP-hard through

a reduction from 3SAT, and further is

ΣP

-complete through a

reduction from ∃∀DNF.

I. INTRODUCTION

The multitude and volatility of cryptocurrencies force in-

vestors to diversify and frequenty trade their holdings. However,

these currencies are hosted by distinct distributed blockchains

and trading across blockchains is not atomic by default. This has

led to the development of cross-chain swap protocols [

], [

[

], [

] that allow distrusting parties to securely

exchange their assets. Application of such swap protocols is

not limited to trading digital currencies — they can be used for

trading any type of digital assets (NFTs, for example), or even

for trading physical objects by safely trasferring ownership

documentation.

In a pioneering work, Herlihy [

] formalizes a cross-chain

swap as a directed graph where vertices represent parties, and

arcs represent assets to be exchanged. An execution of a swap

graph is represented as the subset of arcs that are triggered in

that execution. The outcome for each party is captured in ﬁve

predeﬁned classes:

DEAL

NODEAL

DISCOUNT

FREERIDE

and

UNDERWATER

. The classes

DEAL

and

NODEAL

represent

outcomes for a party where respectively, all and none of

the arcs of that party are triggered. The class

DISCOUNT

represents outcomes where some of the outgoing arcs are

not triggered, and

FREERIDE

represents outcomes where at

least one incoming but no outgoing arc is triggered. Outcomes

in all these classes are considered acceptable by each party.

The class

UNDERWATER

captures all unacceptable outcomes,

namely outcomes where at least one outgoing arc is triggered

but not all incoming arcs are. Given this model of outcomes,

Herlihy presented a protocol based on hashed time-locks and

proved it to be atomic, meaning that it satisﬁes the conditions

of liveness, safety and strong Nash equilibrium.

This project has been supported by NSF Career 1942711, DARPA YFA

D22AP00146, and NSF grant CCF-2153723.

In practice, as noted in the original proposal [

], some

parties may ﬁnd it advantageous to exchange only some of

their outgoing assets for only some of their incoming assets.

As an example, suppose that Alina has a white shirt and white

pants and she joins the swap hoping to trade for a black shirt

and black pants. Coincidentally, Bohdan has exactly these items

and joins the swap looking for the reverse trade. However, both

of them would actually prefer to retain one white article of

clothing and one black article of clothing, if possible. Thus,

it would be preferable for both parties to, say, only swap the

shirts or only swap the pants, although it is also acceptable to

swap both. Such scenarios are not captured by the model in

[

], because the outcomes with just one item swapped are in

the class UNDERWATER.

This leads to the natural question, left open in [

]: is there

a more general swap model that allows each party to specify

its personal preferences over all possible swap outcomes, and,

at the same time, admits an atomic protocol.

Addressing this question, this paper introduces a general

model of cross-chain swaps that we call swap systems. In a

swap system, as in [

], the set of prearranged asset transfers

is represented by a directed graph. Unlike in [

], however, in

our model each party can specify its own preferences between

all its possible outcomes (that is, between sets consisting of

its incoming and outgoing arcs). These preferences can be

arbitrary, as long as they form a poset and satisfy natural

monotonicity conditions. This generality allows us to capture

not only subjectivity of preferences, but also dependencies

between assets. The example above (about trading clothing

items) illustrates such a dependency: for the purpose of trading,

Alina values her pair of items higher than the sum of their

individual values. Such dependencies often arise in practice

when a party intends to trade multiple assets — in fact, common

investment strategies are guided by objectives (diversiﬁcation,

for example) that inherently involve asset dependencies.

As it turns out, Herlihy’s protocol is not necessarily atomic

in all swap systems, although it still satisﬁes the conditions of

liveness, safety, and weak Nash equilibrium. We then present

a characterization of swap systems that admit atomic protocols.

The correctness proof of this characterization embodies such a

protocol. We then focus on the problem of verifying whether

a given swap systems has an atomic protocol. To this end, we

provide a full characterization of the time complexity of this

problem and show that it’s computationally infeasible, by a

novel proof of completeness in the complexity class

ΣP

. As a

stepping stone to this full characterization, we also include an

easier proof of NP-hardness.

arXiv:2210.11791v2 [cs.DC] 23 May 2023

The paper is organized as follows.

•

In section II we introduce our model of swap systems,

including the deﬁnitions of atomic protocols in this model.

•

In section III we show that our model is indeed a

generalization of Herlihy’s model.

•

The full characterization of swap systems that admit

atomic protocols is given in section IV.

•

The decision problem of testing whether a swap systems

admits an atomic protocol is studied in section V and

section VI, ﬁrst proving

-hardness and then reﬁning

the proof to show ΣP

2-completeness.

For readers interested in the practical impact of our work,

the overall take-out message from this paper is this: (i) Even if

some parties wish to specify outcome preferences not captured

by the model in [

], it still may be possible to realize the swap

with a protocol that is atomic and efﬁcient. (ii) The challenge is

that in order to determine whether it is possible, and to actually

specify this protocol, one needs to solve a computationally

infeasible decision problem. Naturally, for small number of

parties this can still be done in practice – say by exhaustive

search.

II. SWAP SYSTEMS

As discussed in the introduction, Herlihy’s model [

]

for cross-chain swaps assumed that the rational behavior of

participating parties is determined by preferences between ﬁve

types of outcomes:

DEAL

NODEAL

DISCOUNT

FREERIDE

and

UNDERWATER

. These preferences were assumed to be

shared by all parties, and can be interpreted as a simple partial

order on all possible outcomes. Some of these preferences

are natural; for example, in

DISCOUNT

a party receives all

incoming assets without trading all outgoing assets, making it

preferable to

DEAL

. But, as explained in the introduction, in

practice a party may consider some outcomes designated as

UNDERWATER

in [

] to be acceptable, or even preferable to

DEAL

. As another example, suppose that Alina possesses items

and

that she values at

$10

and

$12

, and Bohdan possesses

items

and

that Alina values at

$11

and

$14

. Providing

that Alina’s preferences are based only on the monetary value,

she would accept to join the swap that allows her to swap

both

and

for Bohdan’s

and

, but she would be even

happier if she ends up swapping only

for

instead. Similarly,

there is no justiﬁcation for the outcomes in

FREERIDE

to be

incomparable to DEAL or DISCOUNT.

To represent such individual preferences, we now reﬁne

Herlihy’s model by allowing each party to specify a partial

order on all her possible outcomes of a protocol. Our model

is very general in that (unlike in the example above) a

party’s preferences are not determined by numerical values

of individual assets, but rather involve comparing directly

whole sets of traded and acquired assets. The advantage of this

approach is that it captures dependencies between assets, when

a party values a set of assets higher or lower than the sum of

their individual values. As an example, say that Alina owns a

power drill and a shovel, while Bohdan is in possession of a

pair of skis. Alina would not swap any of her items for any

single ski, but she may be happy to swap both of her items for

the pair. On the other hand, if, instead of skis, Bohdan needs

to get rid of two skateboards, Alina may prefer to swap any

of her items for one skateboard rather than swapping both for

two skateboards.

Swap Systems. A swap system is speciﬁed by a pair

(D,P)

consisting of a digraph

that represents the pre-

arranged asset transfers and a collection

of posets that

speciﬁes the preferences of each involved party among all of

its potential outcomes. Next, we give a formal deﬁnition of

these two components of S.

Digraph

D= (V, A)

is called a swap digraph. Each vertex

v∈V

represents a party that participates in the swap, and

each arc

(u, v)∈A

represents an asset that is to be transferred

from party

to party

. By

Ain

and

Aout

we will denote the

sets of vertex

’s incoming and outgoing arcs, respectively.

(x, v)∈Ain

then

is called an in-neighbor of

, and if

(v, x)∈Aout

then

is called an out-neighbor of

. Throughout

the paper we assume that

does not have multiple arcs

. We

also assume that

is weakly connected (otherwise a swap

can be arranged for each connected component separately).

To exclude some degenerate scenarios, we also assume that

|V| ≥ 2and that Ain

v̸=∅and Aout

v̸=∅for each v∈V.

An outcome of a party

v∈V

is a pair

ω=⟨ωin |ωout⟩

where

ωin ⊆Ain

and

ωout ⊆Aout

. An outcome represents the

sets of acquired and traded assets,

ωin

and

ωout

respectively.

The set of all possible outcomes of

will be denoted

Ωv

. To

reduce clutter, instead of arcs, in

⟨ωin |ωout⟩

we will often list

only the corresponding in-neighbors and out-neighbors of

;

for example, instead of

⟨{(x, v),(y, v)}|{v, z}⟩

we will write

⟨x, y |z⟩.

The collection

P={Pv}v∈V

consists of preference posets.

The preference poset of a party

v∈V

Pv= (Ωv,⪯v)

, where

⪯v

is a partial order on

Ωv

. We will write

ω≺vω′

ω⪯vω′

and

ω̸=ω′

. This poset naturally represents

’s evaluation of its

potential outcomes; that is, relation

ω⪯vω′

holds if

views

outcome

ω′

to be better than outcome

. The outcome where

does not participate in any transfer is

NODEALv=⟨∅|∅⟩

and the outcome where all of

’s transfers are realized is

DEALv=⟨Ain

v|Aout

v⟩

. Each preference poset

is assumed

to have the following properties:

(p.1)

DEAL

is better than

NODEAL

NODEALv≺vDEALv

Naturally, each party prefers swapping all assets over being

completely excluded, as otherwise it would not even join the

swap system.

(p.2) Inclusive Monotonicity:

(ωin

1⊆ωin

2∧ωout

2⊆ωout

1)⇒

ω1⪯vω2

, for every two outcomes

ω1, ω2∈Ωv

. That is, it’s

better to receive more assets and to trade fewer assets2.

The preference pairs

ω1≺vω2

that are determined by rules

(p.1) and (p.2) above will be called generic. The size of the

preference poset may be exponentially large with respect to

This assumption is only for convenience – our model and results trivially

extend to multi-digraphs, although this requires more cumbersome notation

and terminology.

2Duuh.

the size of the swap digraph

, but it is not necessary for a

party to specify generic preferences as they are implied from

the above rules. Therefore, throughout the paper, we assume

that Pvis speciﬁed by its generator set, which is a subset of

its non-generic preference pairs that, together with the generic

pairs and transitivity, generate the whole poset. A generator

set of a poset may not be unique. We use this convention in

our examples and running time bounds. (This does not affect

our hardness results — they hold even if the preference poset

of each party is speciﬁed by listing all preference pairs.)

An outcome

ω∈Ωv

is called acceptable if

ω⪰NODEALv

The set of acceptable outcomes of a node

will be denoted

Av3.

Throughout the paper, we will often omit subscript

in these

notations (and others as well) if

is implicit in the context or

irrelevant. On the other hand, if any ambiguity may arise, we

will sometimes add a superscript to some notations specifying

the digraph under consideration; for example we will write

DEALD

to specify that outcome

DEALD

is with respect to

digraph D.

Protocols. Given a swap system

S= (D,P)

, a swap protocol

for

speciﬁes actions of each party over time, in particular

it determines how assets change hands. Initially, an asset

represented by an arc

(u, v)∈A

is in the possession of

, and,

when

completes, this asset must be in possession of either

. If

(u, v)

ends up in the possession of

, we will say

that the arc

(u, v)

has been triggered. The outcome of

after

executing

⟨ωin |ωout⟩

, where

ωin

and

ωout

are the sets

of incoming and outgoing arcs of

that are triggered in this

execution. In particular, we write

P(v)

for the outcome of

in an execution of protocol

in which all parties follow

. If

some party (possibly

itself) deviates from

, we assume that

’s outcome is also ﬁnalized when

completes, but it may be

different from P(v).

A protocol may use appropriate cryptographic primitives. In

particular, following [

], we assume the availability of smart

contracts. A smart contract for an arc

a= (u, v)

allows

put asset

in an escrow secured with a suitable collection

of hashed time-locks: each such time-lock is speciﬁed by a

pair

(h, τ)

, where

h=H(s)

is a hashed value of a secret

and

is a time-out value. In order to unlock this time-lock,

(and only

) must provide the value of

before time

If all time-locks of

(u, v)

are unlocked,

can claim

. This

automatically triggers arc

(u, v)

. If any time-lock times out,

is automatically returned to

. We describe a more elaborate

hashed time-lock in the next section.

Properties. For a swap protocol to be useful, it must guarantee

that if all parties follow it then every party ends in an outcome

at least as favorable as trading all their outgoing for all their

This deﬁnition can be relaxed to allow some outcomes incomparable

NODEAL

be acceptable. In this extended model, the set

of accept-

able outcomes would be part of a swap system speciﬁcation, and would

have to satisfy three conditions: (i)

{ω:ω⪰NODEALv} ⊆ Av

, (ii)

{ω:ω≺NODEALv}∩Av=∅

, and (iii)

ω∈ Av∧ω⪯ω′⇒ω′∈ Av

Our results can be extended naturally to this model. We adopted the simpler

deﬁnition to streamline the presentation.

incoming assets. Further, every conforming party should end

up with an acceptable outcome, no matter whether other parties

follow the protocol or not. Lastly, rational parties should have

no incentive to deviate from the protocol. Herlihy [

] captured

these properties using the concepts of uniformity and strong

Nash equilibrium. Our deﬁnitions, below, are their natural

extensions to the more general model of swap systems.

Uniformity. A swap protocol

is called uniform if it

satisﬁes the following two conditions:

Liveness: If all parties follow

, they all end in outcome

DEAL or better, that is P(v)⪰DEALvfor all v∈V.

Safety: If a party conforms to

, then its outcome will be

acceptable, independently of the behavior of other parties.

A less restrictive concept of uniformity may also be of interest:

We say that a protocol

is weakly uniform if it satisﬁes the

safety condition above, but the liveness condition is replaced by

the following weak liveness requirement: if all parties follow

, then at least one party ends in an outcome strictly better

than NODEAL. The assumptions on preference posets imply

directly that a protocol that is uniform is also weakly uniform.

Nash equilibria and atomicity. We extend the concept of

outcomes to sets of parties, where an outcome of a set is just a

vector of individual outcomes. On this set we can then deﬁne

a preference relation in a standard way, via a coordinate-wise

ordering of outcomes. Formally, for any set of parties

C⊆V

an outcome vector of

¯ω= (ωv)v∈C

, where

ωv∈Ωv

for

all

v∈C

. Denote by

ΩC

the set of all outcome vectors of

Given two outcome vectors

¯ω, ¯ω′∈¯

ΩC

, we write

¯ω⪯C¯ω′

ωv⪯vω′

for all

v∈C

. If also

¯ω̸= ¯ω′

then we write

¯ω≺C¯ω′

. (In other words,

¯ω≺C¯ω′

means that at least one

party in

does strictly better in

¯ω′

than in

¯ω

, and every party

does at least as good.) In this notation, if all parties follow

a protocol

, then the outcome vector

P(C)

of a protocol

for a set of parties Cis (P(v))v∈C.

We will say that a protocol

is a strong Nash equilibrium

if no coalition of participating parties can improve its vector

outcome by deviating from

; more precisely, for every set

of parties, if

¯ω

denotes the outcome vector of

in some

execution of

where all parties in

V\C

, then we

cannot have

¯ω≻CP(C)

. We will call

atomic if it is both

uniform and a strong Nash equilibrium.

Example 1. Consider a swap system

S= (D,P)

whose

digraph

is shown in Figure 1. The preference poset

generated by two preference pairs

DEALu≺ ⟨v|v⟩ ≺ ⟨v|w⟩

the preference poset

is generated by two preference pairs

DEALv≺ ⟨u|u⟩≺⟨w|u⟩

, and the preference poset

generated by one preference pair DEALw≺ ⟨u|v⟩.

Consider also a swap protocol

for

such that if all parties

then all end up with outcome

DEAL

. Then

is not a

strong Nash equilibrium, because for

C={u, v}

, the parties

can ignore

altogether and simply swap their assets

between themselves, improving their outcomes. Nevertheless,

as we show later in Section IV,

does have an atomic protocol.

Roughly, instead of using the whole digraph

, in this protocol

only assets represented by arcs

(u, w)

(w, v)

and

(v, u)

will

be swapped. Then the outcome of each party will be better

<latexit sha1_base64="GRS/k2NURQKKhlLWAeXz6/04pXw=">AAAB6HicdVDLSsNAFJ3UV62vqktBBovgKiRNsenKghuXLdgHtKFMppN27GQSZiZCCV26cuNCEbd+hd/hzm/QjX/gtFVQ0QMXDufcyz33+jGjUlnWi5FZWFxaXsmu5tbWNza38ts7TRklApMGjlgk2j6ShFFOGooqRtqxICj0GWn5o9Op37okQtKIn6txTLwQDTgNKEZKS/Wkly9YplUsFSsOtEzbcZ1ySZOia5WdCrRNa4bCyfvr1f5T/a3Wyz93+xFOQsIVZkjKjm3FykuRUBQzMsl1E0lihEdoQDqachQS6aWzoBN4qJU+DCKhiys4U79PpCiUchz6ujNEaih/e1PxL6+TqMD1UsrjRBGO54uChEEVwenVsE8FwYqNNUFYUJ0V4iESCCv9m5x+wtel8H/SLJr2sVmq24WqC+bIgj1wAI6ADcqgCs5ADTQABgRcg1twZ1wYN8a98TBvzRifM7vgB4zHD5+3kfM=</latexit>

<latexit sha1_base64="x+mhS+CA7qfsf/dCseVSyQPhjAE=">AAAB6HicdVC7SgNBFJ31GeMrainIYBCsltlsMJvKgI1lAuYByRJmJ7PJmNkHM7OBsKS0srFQxNav8Dvs/AZt/AMniYKKHrhwOOde7rnXizmTCqEXY2FxaXllNbOWXd/Y3NrO7ew2ZJQIQusk4pFoeVhSzkJaV0xx2ooFxYHHadMbnk395ogKyaLwQo1j6ga4HzKfEay0VBt1c3lkokKxULYhMi3bsUtFTQoOKtllaJlohvzp++vVwVPtrdrNPXd6EUkCGirCsZRtC8XKTbFQjHA6yXYSSWNMhrhP25qGOKDSTWdBJ/BIKz3oR0JXqOBM/T6R4kDKceDpzgCrgfztTcW/vHaifMdNWRgnioZkvshPOFQRnF4Ne0xQovhYE0wE01khGWCBidK/yeonfF0K/yeNgmmdmMWala84YI4M2AeH4BhYoAQq4BxUQR0QQME1uAV3xqVxY9wbD/PWBeNzZg/8gPH4AaE7kfQ=</latexit>

<latexit sha1_base64="lN+M9dwqGXtaNpYmeiESrpSXwNg=">AAAB6HicbZC7SgNBFIbPxluMt6ilIItBsAq7IprOgI1lAuYCSQizk7PJmNnZZWZWCUtKKxsLRWx9ilQ+hJ3P4Es4uRSa+MPAx/+fw5xzvIgzpR3ny0otLa+srqXXMxubW9s72d29qgpjSbFCQx7KukcUciawopnmWI8kksDjWPP6V+O8dodSsVDc6EGErYB0BfMZJdpY5ft2NufknYnsRXBnkLv8GJW/Hw5HpXb2s9kJaRyg0JQTpRquE+lWQqRmlOMw04wVRoT2SRcbBgUJULWSyaBD+9g4HdsPpXlC2xP3d0dCAqUGgWcqA6J7aj4bm/9ljVj7hVbCRBRrFHT6kR9zW4f2eGu7wyRSzQcGCJXMzGrTHpGEanObjDmCO7/yIlRP8+55/qzs5ooFmCoNB3AEJ+DCBRThGkpQAQoIj/AML9at9WS9Wm/T0pQ169mHP7LefwCsOZFD</latexit>

Fig. 1. The digraph Din the example.

than

DEAL

, and

and

will have no incentive to deviate from

this protocol.

III. HERLIHY’SSWAP MODEL

In this section, we show that the concept of swap systems

is a generalization of Herlihy’s model [

]. To this end, we

deﬁne a simple type of swap system called h-swap systems,

and we show that it captures the model in [

]. In particular

we prove that in h-swap systems, our deﬁnition of atomicity

is equivalent to the deﬁnition in [19].

h-Swap Systems. Given a swap system

S= (D,P)

and a

party v∈V, deﬁne three sets of outcomes of v:

DISCOUNTv=ω|ωin =Ain

v∧ωout ̸=Aout

v

FREERIDEv=ω|ωin ̸=∅∧ωout =∅

UNDERWATERv=ω|ωin ̸=Ain

v∧ωout ̸=∅

Since

Ain

v̸=∅

and

Aout

v̸=∅

, all sets

DISCOUNTv

FREERIDEv

and

UNDERWATERv

are well-deﬁned,

none of them contains

NODEALv

nor

DEALv

UNDERWATERv∩(DISCOUNTv∪FREERIDEv) = ∅

DISCOUNTv∩FREERIDEv={⟨Ain

v|∅⟩}, and

Ωv={NODEALv}∪{DEALv} ∪ DISCOUNTv

∪FREERIDEv∪UNDERWATERv.

The inclusive monotonicity property (p.2) implies that all

outcomes in

FREERIDEv

are better than

NODEALv

, and all

outcomes in DISCOUNTvare better than DEALv.

We will call

an h-swap system if it satisﬁes the following

conditions for all v∈V:

(h.1) If ω∈UNDERWATERvthen ω≺vNODEALv,

(h.2) Party

has no other non-generic preferences besides

these in (h.1).

In other words, in an h-swap system all preference posets

are generated by relations

ω≺NODEAL

for outcomes

UNDERWATER

. Figure 2 illustrates the structure of a preference

poset of an h-swap system

. Note that in an h-swap system,

the set of acceptable outcomes of a node

Av= Ωv\

UNDERWATERv={NODEALv}∪{DEALv}∪ DISCOUNTv∪

FREERIDEv

. The preferences of an h-swap system

S= (D,P)

are uniquely determined by its digraph

, so it is not even

necessary to specify P.

The preference poset structure of h-swap systems, as deﬁned

above, captures the concept of a party’s preferences assumed

This ﬁgure differs slightly from Figure 3 in [

], which mistakenly showed

the sets DISCOUNTvand FREERIDEvas disjoint.

<latexit sha1_base64="tEYFmYDP6G+S/0/Oa+tQDqm0nDM=">AAAB/nicdVDLSgNBEJz1GeMrRjx5GQyCp2U3CSZ6CnjxqGhUSEKYnXR0cHZ2melVwxLwG/wDETwo4tXv8ObRP3GSKKhoQUNR1U13VxBLYdDz3pyx8YnJqenMTHZ2bn5hMbeUPzJRojnUeSQjfRIwA1IoqKNACSexBhYGEo6D852Bf3wB2ohIHWIvhlbITpXoCs7QSu3cShPhCg1P66oD+pIh6H77op0reK5XLBe3StRz/VK1VClbUqx6ldIW9V1viEIt/759czd5sNfOvTY7EU9CUMglM6bhezG2UqZRcAn9bDMxEDN+zk6hYaliIZhWOjy/T9et0qHdSNtSSIfq94mUhcb0wsB2hgzPzG9vIP7lNRLsVlupUHGCoPhoUTeRFCM6yIJ2hAaOsmcJ41rYWyk/Y5pxm4LJ2hC+PqX/k6Oi62+6/r5fqFXJCBmyStbIBvFJhdTILtkjdcJJSm7JA3l0rp1758l5HrWOOZ8zy+QHnJcPzEOZoA==</latexit>

Underwaterv

<latexit sha1_base64="7S8DvtLOay8yjez8D5MEqyhJ0OQ=">AAAB+nicdVDLSgNBEJz1bXwl8ehlMAielt1ETPQU0IMnUTSJkIQwO+kkg7MPZnrVsOYnvHtRUMSrX+LNo3/iJFFQ0YKGoqqb7i4vkkKj47xZE5NT0zOzc/OphcWl5ZV0JlvVYaw4VHgoQ3XmMQ1SBFBBgRLOIgXM9yTUvPO9oV+7AKVFGJxiP4Kmz7qB6AjO0EitdKaBcIWaJ4fhPjA5aF200jnHdvJb+Z0CdWy3UCoUtwzJl5xiYYe6tjNCrpx93725nz45aqVfG+2Qxz4EyCXTuu46ETYTplBwCYNUI9YQMX7OulA3NGA+6GYyOn1AN4zSpp1QmQqQjtTvEwnzte77nun0Gfb0b28o/uXVY+yUmokIohgh4ONFnVhSDOkwB9oWCjjKviGMK2FupbzHFONo0kqZEL4+pf+Tat52t2332M2VS2SMObJG1skmcUmRlMkBOSIVwskluSUP5NG6tu6sJ+t53Dphfc6skh+wXj4AKmCXig==</latexit>

NoDealv

<latexit sha1_base64="rbSVpVTSKi8y1jAvmoQA1Q7RxBY=">AAAB/HicdVDLSgNBEJyN7/iK8ehlMAielt0kmMRTQBCPvqJCEsLspGOGzD6Y6Q2GJX6EP+BBD4p49UO8efRPnCQKKlrQUFR1093lRVJodJw3KzU1PTM7N7+QXlxaXlnNrGXPdBgrDjUeylBdeEyDFAHUUKCEi0gB8z0J515vb+Sf90FpEQanOIig6bPLQHQEZ2ikVma9gXCFmif7CuBYtGHY6rcyOcd28sV8pUAd2y2UC6WiIfmyUypUqGs7Y+Sq2ffdm7uZk8NW5rXRDnnsQ4BcMq3rrhNhM2EKBZcwTDdiDRHjPXYJdUMD5oNuJuPjh3TLKG3aCZWpAOlY/T6RMF/rge+ZTp9hV//2RuJfXj3GTrmZiCCKEQI+WdSJJcWQjpKgbaGAoxwYwrgS5lbKu0wxjiavtAnh61P6PznL2+6O7R65uWqZTDBPNsgm2SYuKZEqOSCHpEY4GZBb8kAerWvr3nqynietKetzZp38gPXyAcL2mHE=</latexit>

FreeRidev

<latexit sha1_base64="3N2by3Dfu5fBcXHCVcyVpwwSEbM=">AAAB/HicdVDLTgJBEJz1ifhCOHqZSEw8bXaBCHgi0YNHjPJIgJDZYZAJs7ObmV4i2eBH+AMe9KAxXv0Qbx79EwfQRI1W0kmlqjvdXV4ouAbHebMWFpeWV1YTa8n1jc2t7dROuq6DSFFWo4EIVNMjmgkuWQ04CNYMFSO+J1jDGx5P/caIKc0DeQHjkHV8cil5n1MCRuqmMm1gV6BpfMI1DSIJk+6om8o6tpMr5Mp57NhuvpQvFgzJlZxivoxd25khW0m/H93cLZ9Xu6nXdi+gkc8kUEG0brlOCJ2YKOBUsEmyHWkWEjokl6xlqCQ+0514dvwE7xulh/uBMiUBz9TvEzHxtR77nun0CQz0b28q/uW1IuiXOjGXYQRM0vmifiQwBHiaBO5xxSiIsSGEKm5uxXRAFKFg8kqaEL4+xf+Tes52D233zM1WSmiOBNpFe+gAuaiIKugUVVENUTRGt+gBPVrX1r31ZD3PWxesz5kM+gHr5QMpzZi0</latexit>

Discountv

<latexit sha1_base64="kJ0fx3IVSDhZgMiYwvNioR19AkU=">AAAB+HicdVDLSgNBEJz1GeMrxqOXwSB4WnYTMYmngB48RjQPSEKYnXR0cPbBTG8wLvkJr14EFfHqp3jz6J84SRRUtKChqOqmu8uLpNDoOG/WzOzc/MJiaim9vLK6tp7ZyNZ1GCsONR7KUDU9pkGKAGooUEIzUsB8T0LDuzwc+40BKC3C4AyHEXR8dh6IvuAMjdTNrLcRrlDz5AiYHHUH3UzOsZ38Xr5coI7tFkqF4p4h+ZJTLJSpazsT5CrZ94Ob+/nTajfz2u6FPPYhQC6Z1i3XibCTMIWCSxil27GGiPFLdg4tQwPmg+4kk8NHdMcoPdoPlakA6UT9PpEwX+uh75lOn+GF/u2Nxb+8Voz9UicRQRQjBHy6qB9LiiEdp0B7QgFHOTSEcSXMrZRfMMU4mqzSJoSvT+n/pJ633X3bPXFzlRKZIkW2yDbZJS4pkgo5JlVSI5zE5JY8kEfr2rqznqznaeuM9TmzSX7AevkAtTGWuQ==</latexit>

Dealv

Fig. 2. The structure of a preference poset of a party

in an h-swap system. The

arrows symbolize the preference relation. The one outcome in

DISCOUNTv∩

FREERIDEvis ⟨Ain

v|∅⟩.

in the model from [

], except for the addition of preferences

determined by inclusive monotonicity.

Comment. The model in [

] was not formulated in terms

of posets, raising a question of how to formally capture a

relation for pairs of outcomes between which preferences

were not speciﬁed in [

]. In our model, such outcomes

are considered incomparable in the poset (unless they are

related by the inclusive monotonicity). One may try to consider

another option: to allow arbitrary relations between such

pairs, providing that the poset axioms are satisﬁed and the

condition (h.1) holds. However, with this approach there is

no meaningful way to extend such individual preferences to

collective preferences of sets of parties (see the discussion later

in this section).

h-Uniformity. To distinguish between our and Herlihy’s

deﬁnition of uniformity, we will refer to his concept as h-

uniformity. A swap protocol

is called h-uniform if it satisﬁes

the safety property and the following h-liveness condition:

If all parties follow

, they all end in outcome DEAL. This

condition seems stricter than our deﬁnition of uniformity, but

we show that in h-swap systems these two deﬁnitions are in fact

equivalent. In fact, they are also equivalent to weak uniformity,

as deﬁned earlier in Section II.

Lemma 1. Let

S= (D,P)

be an h-swap system in which

some subset of arcs in

are triggered, and let

be a path in

whose all internal nodes are in acceptable outcomes. Then,

along

, all triggered arcs of

are before all non-triggered

arcs of Q.

Proof.

If all arcs on

are triggered, except possibly for the

last one, we are done. Otherwise, let

(x, y)

be the ﬁrst non-

triggered arc on

and let

be the successor of

. Since

’s

outcome is acceptable and

(x, y)

is not triggered, this outcome

must be either

NODEALy

or in

FREERIDEy

. Therefore

(y, z)

is also not triggered. Repeating this argument, we obtain that

all arcs on Qafter (x, y)are not triggered.

Theorem 1. Let

be a swap protocol for an h-swap system

S= (D,P)

, where

is strongly connected. Then the following

three conditions are equivalent: (i)

is uniform, (ii)

is weakly

uniform, (iii) Pis h-uniform.

Proof.

Trivially, h-uniformity implies uniformity, which in turn

implies weak uniformity. Thus it is sufﬁcient to show that weak

uniformity implies h-uniformity.

So assume that

is weakly uniform. As the safety condition

is the same, it is sufﬁcient to show that

satisﬁes the h-

liveness property. Assume that all parties follow

. Then, from

the assumptions about safety and weak liveness, all parties will

end up in acceptable outcomes, with at least one party ending

in an outcome strictly better than NODEAL.

Suppose, towards contradiction, that there is a party with

outcome other than

DEAL

. This gives us that some arc

(x, y)

is not triggered. Further, since some party has an outcome

other than

NODEAL

, there must be a triggered arc

(x′, y′)

. By

strong connectivity, there is a path

from

y′

whose ﬁrst

arc is

(x, y)

and the last arc is

(x′, y′)

. Then the existence of

this path contradicts Lemma 1.

h-Atomicity. The approach in [

] differs from ours in the

way it formalizes the gain of a coalition (subset) of parties

when they deviate from the protocol. Roughly, the deﬁnition

in [

] captures a collective gain, while our deﬁnition views it

as a vector of individual outcomes. In spite of this apparent

difference, we show that in h-swap systems our concept of

atomicity is in fact equivalent to the one in [19].

In the discussion below, let

S= (D,P)

be a ﬁxed h-swap

system. Following [

], we will deﬁne the h-outcome of a

coalition

of parties by, in essence, contracting

into a single

vertex. (The term “h-outcome” is ours, to better distinguish

this concept from our concept of outcome vectors.) More

formally, deﬁne

’s incoming and outgoing arcs in a natural

way:

Ain

C=Sv∈C Ain

v\Sv∈C Aout

and similarly,

Aout

Sv∈C Aout

v\Sv∈C Ain

. The h-outcomes for

are pairs

ˆω=

⟨ˆωin |ˆωout⟩

where

ˆωin ⊆Ain

and

ˆωout ⊆Aout

ΩC

is the set

of all h-outcomes of

. The preference poset and acceptable

set of

are deﬁned analogously to that of a single party

in an h-swap system. That is, we deﬁne NODEALC, DEALC,

DISCOUNTC

FREERIDEC

, and

UNDERWATERC

in the natural

way, and we assume the analogues of conditions (p.1) and (p.2)

for swap systems (in Section II) and conditions (h.1) and (h.2)

for h-swap systems. The set of acceptable h-outcomes

consists of all h-outcomes of

that are not in

UNDERWATERC

(Note that if

consists of a single party then its h-outcome is

identical to its outcome.)

Deﬁne a protocol

to be a strong Nash h-equilibrium if

it satisﬁes the following condition for every set

of parties:

providing that the parties outside

, the parties in

cannot end up in an h-outcome better than their outcome

resulting from following

is called h-atomic if it is h-

uniform and a strong Nash h-equilibrium.

Culminating the earlier discussion, the following theorem

establishes that our model indeed captures the model introduced

in [19].

Theorem 2. Let

be a protocol for an h-swap system

(D,P).Pis atomic if and only if it is h-atomic.

Proof. (⇒)

Suppose that

is atomic. Theorem 1 implies that

is h-uniform. Thus, from the deﬁnition of h-uniformity, if

all parties follow Pthen each party’s outcome will be DEAL.

It remains to show that

is a strong Nash h-equilibrium. Let

C⊆V

, and consider an execution of

in which all parties

outside

. Since

is a strong Nash equilibrium, the

outcome vector of

is not better than

(DEALv)v∈C

. Denote

ˆω

the h-outcome of

. We need to show that

ˆω

is not better

than DEALC.

Towards contradiction, suppose that

ˆω≻DEALC

. The

deﬁnition of preference posets for h-outcomes gives us that

ˆω∈DISCOUNTC

. Now consider another execution of

where

the parties in

behave just like before, but they also trigger

all arcs connecting two members of

. This will not affect

the execution of

for parties outside

. Then the outcome

vector

¯ω

consists of all arcs between

and

V\C

(in

both directions) that are triggered in

ˆω

, as well as all arcs

with both endpoints inside

. Since

ˆω∈DISCOUNTC

, each

v∈C

has all its incoming arcs in

¯ω

, and there is at least

one

u∈C

that has one arc to

V\C

that is not in

¯ω

. So the

outcome of each

v∈C

is either

DEALv

DISCOUNTv

, and

this

’s outcome is

DISCOUNTu

. But then

¯ω

is better than

(DEALv)v∈C

, contradicting the assumption that

is a strong

Nash equilibrium.

(⇐)

Now suppose that

is h-atomic; that is,

is h-uniform

and is a strong Nash h-equilibrium. From Theorem 1 we obtain

that Pis uniform.

It remains to prove that

is a strong Nash equilibrium. Let

C⊆V

, and consider some execution of

in which all parties

outside

. Since

is a strong Nash h-equilibrium,

the h-outcome of

is not better than

DEALC

. We need to

show that

’s outcome vector is not better than

(DEALv)v∈C

We again argue by contradiction. Suppose that

’s outcome

vector is

¯ω≻(DEALv)v∈C

. Then each

v∈C

has outcome

{DEALv} ∪ DISCOUNTv

and there is some

u∈C

with

outcome in

DISCOUNTu

. This implies that all parties in

have their incoming arcs in

¯ω

. Further, some outgoing arc of

is not in

¯ω

, and this arc must go to

V\C

. We consider

the h-outcome of

in the same run of

, without changing

the behavior of any members of

. (In the h-outcome of

the status of arcs internal to

is not relevant.) Denote this

h-outcome by

ˆω

. Then

ˆω

will include the same arcs between

and

V\C

(in both directions) as in

¯ω

. The properties of

¯ω

established earlier imply that

ˆω∈DISCOUNTC

, and thus

ˆω≻DEALC

, which contradicts our earlier assumption that

is a strong Nash h-equilibrium.

Herlihy’s Protocol. Herlihy presented a protocol for h-swap

systems [

] that is h-atomic. We summarize this protocol that

we will refer to as H.

Since the generation and distribution of the swap system is

not the focus of this paper, we assume a third-party service that

reliably distributes information to the participating parties. The

service begins by assembling a swap graph

and distributing

it to every party. Each party

then generates and hashes a

secret

hi=hash(si)

and sends it back to the service.

The

Herlihy describes an optimization where the service computes a feedback

vertex set for

(i.e. the removal of this set would leave

acyclic). He refers

to these parties as leaders and only uses the hashed secrets of these parties

in subsequent steps of the protocol. As this is not a necessary step, we will

ignore it for simplicity.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Cross-chainSwapswithPreferencesEricChanUniversityofCaliforniaatRiversideMarekChrobakUniversityofCaliforniaatRiversideMohsenLesaniUniversityofCaliforniaatRiversideAbstract—Extremevaluationandvolatilityofcryptocurrenciesrequireinvestorstodiversifyoftenwhichdemandssecureexchangeprotocols.Across-chainsw...

展开>> 收起<<

Cross-chain Swaps with Preferences Eric Chan University of California at RiversideMarek Chrobak.pdf

共23页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Cross-chain Swaps with Preferences Eric Chan University of California at RiversideMarek Chrobak

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: