Blockchains as Kripke models:an Analysis of Atomic CrossChain Swap
Yoichi HiraiLimassol, 2018-11-05

Atomic Cross-Chain Swap vsChandy-Misra“Atomic Swap” protocols swap tokens on
diﬀerent blockchains atomically.
No asynchronous communication can create a
new piece of common knowledge[Chandy, Misra: How Processes Learn, 1986].
“Atomic Swap” should require some synchrony.
What kind of?

Atomic Cross-Chain Swap
Uses Hash LockTo spend the fund in a hash lock,the first way is
1. with Bob’s signature
2. with input whose hash is H
3. before the deadline.
the second way is
1. with Alice’s signature
2. after the deadline.

Atomic Cross-Chain Swap
Success Casekopened with kktimek

opened with khashlock for* Bob with preimage of H
* Alice after 2 days

hashlock for* Alice with preimage of H
* Bob after 1 dayndfudnu

f

Alice

Chain X

Chain YBobAtomic Cross-Chain Swap
Failure Casetimeouttime

timeout

hashlock for* Bob with preimage of H
* Alice after 2 days

hashlock for* Alice with preimage of H
* Bob after 1 dayndfudnuf

AliceChain XChain YBobObservations
Obs. 1 Properties dependent on states.
Obs. 2 Most interesting properties are persistent.
e.g.
Once a hashlock is opened, it remains opened.
Once a secret is revealed on a blockchain, it remains
revealed.

Obs. 3 “Bob knows chain Y has something.”

Obs. 1 Properties dependent on
local states.
→ Kripke Models

□p
¬□pp

¬p

Obs. 2 Most interesting
properties are persistent.
Kripke models with persistent properties 〜
model of intuitionistic logic

timep
¬pp

× ×¬ppObs. 3 “Bob knows chain Yhas something.”
The logic needs epistemic modality.

time

fB
fY

fYkfB

KBKYk

KYk
Design choice [Hirai, LPAR-16]:
identify epistemic modality withcommunication

Some valid formulas
fY

fY

KYk

only consider models where fY is
idempotent

kfYk

KYk ⊃ KYKYk

KYk

KYk ⊃ konly consider models where fY
points to the past(and all formulas are persistent)

as hashlock’s
abilitytosettlepayments.
After
using
logicalformulas.
perty
isahashlock’s
abilitytosettlepayments.
Afternever.
Concretelyon
blockchain
X,aftertwodays,
ally,
if
Bob
ever
gets
toknow
thesecret,Alices
kswap
is
able
to
dictatewhetherthelockedfund(Fig.
1)
isaprotocolbasedonaprimitive called
abilitytosettle
payments.
After
aConcretely
is
able
to
dictatewhetherthelockedfund
e hashlock
fund
and onthesecrethas
beenrevealed(B^k)
or
X
ck.
In
other
words,
Alice
does
not
leak
the
secretwblockchain
X,
after
two
days,
to
specify
the hashlocks
using
logical formulas.
dictatewhetherthelocked
fund
(¬B).
r
never.
Concretelyonblockchain
X,
after
twodays,Xandthesecrethasbeen
revealed(B^k)
orkchainY:
Xropertyisahashlock’s
abilitytosettle
payments.
Afteron blockchain X, after two days,
he fund and the secret has been
revealed(B^k)
orX
AY(X-live1).
,et(Da has
hashlockisabletodictatewhetherthelockedfund
twodayshave((BX^ k)_ ¬Brevealed(Bpassed^ k) Kor
Bob k secretX2 beenXX)).
nd).
X) or(¬B···
becausethatonformula
is of
any
relevance
never.
Concretely
blockchainX,
aftertwodays,((B^k)_¬B)).
(X-live1)
Bobhasopened
thehashlock
onchainX haveXX
ked
using
asecret.
OnblockchainX,
iftwodayshain
Xatone-and-halfdays
shouldallow
BobtoD.
Theformula¬Dissatisfied
only
dKsatisfying
the
fund
and
the
secrethas
beenrevealed
(B^k)
or
22X
(D((B^k)_¬B)).
(X-live1)
X the
2 Bob
XX
¬B)).
(X-live1)
ides
secret(Kk),
Bobobtains
thefundnever
opens
theX,hashlock
onchain
X (BX ).
XBobngasecret.
Onblockchainiftwodays
have
unddays(¬BXpass.
).
wo
1 ((KKKk)
B).
ocked
using
asecret.
OnblockchainX,
iftwodayshavesecret(Kk),Bobobtains
thefund(B).
X
BobX
1
BobX
On
blockchain
X,kaif hashlock
twodays have
K_(KB)).
(X-live2)
2
reK
about
whatissupposed
todo.
There
X (D2BobX(D((B^k)_¬B)).
(X-live1)
X
2
X
X
vides
thesecret(Kk),Bobobtains
thefund(B).
BobXk),
Bobobtains
thefund(B).
obX
ashlock
isnotsupposed
todo.
Thehashlock
grants_(KkB)).
(X-live2)
BobX
henwe
imposethoseformulasateverystate,
thnlocked
usingasecret.
On
blockchainX,
iftwodayshaveobauthenticatesK(D2 _ (KBob khimself
B(X-live2)
B)).
XX )).with the secret k:(X-live2)
X
mepropertyholds.
rovidesthe secret(KBob k), Bob obtains the fund (BX ).

Features of a hash lock

BKk.
_IfK
(Kk MBX )).
(X-live2)
X X (DKBobosition
52 X
aBobmodel
satisfies (X-live2),(X-safe)(Y-time1ance), (X-live1 2 ) at every state, M also satisfies (hain Y, either the fund is given or not given:

if the hash is known, the fund is given:ame
propertiesofAthe
hashlock on the other (Y-live2)
blockchain.
_(Kk)).
Alice
YKY (D1 ((AY ^ k) _ ¬AY )).
(Y-live1)
chain
Y, either
thefundis given or not given:(Y-live2)_(KkA)).
1AliceYthe blockchain
Y isunlessshehash:chain
Y, if the hashknown,thereveals
fund is thegiven:
KY (D1 ((AY ^ k) _ ¬AY )).
(Y-live1)
the blockchain Y unless she reveals the hash:K(D_(KkA)).
(Y-live2)
Y1
AliceYAKk.
(Y-safe)
Y Y, if
Y the hash is known, the fund is given:kchainAY KY k.
(Y-safe)

Another hashlockundKon(Dthe_blockchainY
unlesssherevealsthehash:(KAlice k AY )).
(Y-live2)
Y1

ng of day one and day twoAKk.
(Y-safe)YY
fundofonday
the blockchain
unlesstwo
she reveals the hash:ingone andYday
has already passed, too:AKk.
(Y-safe)
YY
alreadypassed,
l hasorderingof dayone too:and day two
D2 D1 .
(Days)
onedayhasalreadypassed,too:al Dordering
D1 .of day one and day two(Days)
2and a timing constraint

D2 alreadyD1 . passed, too:
, one day has(Days)

YYbelongs
toYBobornever.
Concretelyon
blockchain
X,aK(D((A^k)_¬A)).
(Y1YY
Hashlockon
BlockchainYsatisfy
ASo,success.
without
looking
atcase,Boris¬B, supposede
importantthingthatahashlock
nottodo.
TheBKk.
ng
anincompleteInourthetwounlocking
eventsonY either.
XKXXX
Bobe
most
relevant
propertyisa
hashlock’s
abilitytosettle
Bobhasobtainedthefundandthesecrethas
been
revealnotsatisfy(A^MB_((¬AwY(Fig.
)Bob^ (¬B)).
However,ys constructing
anda state3) soorM
satisfies
YonlyX )succeed
Xthatns
X andYa model
need
to
both
failboth. all
One himself
way to express
thisundtoBobwhen
authenticateswiththesons
at blockchain
every
state
but
wimplication
doesnotifsatisfy(Binary-Outcome).
Thestateeamountoftime,ahashlockisabletodictatewhetherlnever
get
the
fund
(¬B).
es
not
satisfythe(Binary-Outcome).
tu
on
Y,
the
hashisknown,thefundisgiven:
X
ate
the
same
properties
ofthehashlock
on
the
other
bloc
uld
notsay(¬D)···
becausethat
formulaisofany
al3 does
formulagoes
like
this;
after
twodays,
at
least
oneof
the
twoallowed2
not satisfy ¬A because there is a future state satisfying A . Onyate
belongs
tofuture
Bobornever.
Concretelyon
blockchainX
hand,w
does notsatisfy
Aeither.
So,withoutlooking
at B. Theor¬B, formulapens:
FortheHashlockon
Blockchain
Ywithnosatisfying
D¬DissationblockchainY,eitherthefundisgivenor
notgiven:atew
inFig.
3,
twodayshavepassedbutneither2)).K
2
BKk.
XX
Bobnclude that w does not satisfy (AK^X
B (D) _ ((¬A)^(¬B
However,((B^k)_¬B)).
2XX
K(D_(KkA)).
(Ysiblesince
beginningoftheprotocol.
Bobhasobtainedthefundand Ythe tusecret has been reve
Ysatisfy
1the implication
Alicetisfy
Dblocks.ends
Sow does
notthe(Binary-Outcome).
orldbeforetwodayspass.
D((AY ^ theBX ) _((¬AY) ^ (¬BX ))).of the hashlock(Binary-Outcome)2
nashlockformulatesame
properties
ontheothy
speaking,
onstate
winFig.
3,
twodayshave
passedbutneitherillnevergetthefund(¬B).
K(D((A^k)_¬A)).
(YX
ve
two
properties
whatahashlock
issupposed
tocanbeusing
asecret.
X,
ifY unlocked
1are aboutY
Y On blockchainn has produced visible blocks since the beginning of the protocol.
tainthefundontheblockchainY
unlessshereveals
thehFortheHashlock
onBlockchainYneday,
onblockchainY,eitherthefundisgivenornotgier, thealready
introduced
axiomsnotsupposed
guarantee
AifY, k,
rtant
thing
that
a hashlock
isdonotto do.
The
hashlosed
yet,Bobprovidesthesecret(KBob(Binary-Outcome).
k),Bobobtains
K(D((B^k)_¬B)).
X2XX,Bobon blockchainY,
if authenticatesthe hash is known,
thefundissecretgiven
1D2, D
only
whenBobhimself
withtheion formulate
3 There is athemodelthatsatisfies
allof(Y-live1),(Y-live2),(Ycansame
properties
ofthehashlock
on
theot
AKKk.
(YK
(D((A^k)_¬A)).
Y X (DY_(KkB)).
1 2
YBob
XY
hashlockcanbeunlocked
usingsecret.
On
blockchain(X-live2),(X-safe)andY,(Days)
ataeverystate,
butgiven
does notsat-Xgrlive1),one day,
onKblockchain
eitherthefundisornot(D1 _(KkA)).
(YYstate.
AliceYBKKk.
ry-Outcome)ata
X
X secretBob
assed
yet,
ifBob
providesthek), Bob
one day, on blockchain Y, if the hash(Kis Bobknown,
the obtainfund iw D2, D1
temporalorderingKofday
one((AYand^ k) day_ ¬AtwoY (D1Y )).
btain the fund on theKblockchainY
unlessshereveals
the(D_(KkB)).
X2
BobX
fXf
Y
KY (D1 _ (KYAY )).
heHashlockonBlockchain
Alice kerepassed,
onehas alreadyone day,onday
blockchain
Y, if passed,the hashtoo:
is known, the fundAY KY k.
(mulatethe sameof blockchain
the hashlock
the otherblannot obtain
theproperties
fund on theY onunlessshe reveDD.
(K(D_(KkA)).
21YAliceYay, on blockchain Y, either the fund is given or not given:

These don’t imply binary
outcomes.
YYYX

YX

YXX

≼

2

A one
K andk. day two
temporal ordering of day

model M and a state w for the proof of Prop. 3. Three circles represent theY shown. TheY
es of M . Each function fa is identity whenever not explicitly

Then Require Blocks on
We can require that both blockchains contain blocks produced after two days
ave passed: Both Chains after Day 2

4.2

A Failure on a Weaker Binary Outcome

Proof. By constructing a model M and a state w in it (Fig. 4).

tu

Fig. 4 demonstrates a lack of communication between the two chains. Morespecifically, although the hashlock on blockchain Y is unlocked, Bob fails to use
the secret revealed on blockchain Y to unlock the hashlock on blockchain X.

KX D 2(KY D2((AY ^ BX ) _ ((¬AY ) ^ ¬BX ))). (Weak-Binary-Outcome)This new proposition is strictlyweaker
than the old one. All states satisfying
D1, D
2,w A(Weak-Binary-Outcome),
Y, ¬BX,Binary-Outcome) also satisfy
but the inverse is not always the case. For instance, statek w in Fig. 3 does not satisfy (Binary-Outcome),
fX
fY
ut it satisfies (Weak-Binary-Outcome).

Proposition 4 There is a model that satisfies (Y-live1), (Y-live2), (Y-safe),
X-live1), (X-live2), (X-safe) and (Days)
atallstates, but does not satisfy (WeakD
1,D2,
though transfer
D1, D2,Binary-Outcome)X timed out at some
AY, k¬BX states.

D1

occurred on YfX≼≼

fY

X after two days
knows nothing about
Y after one day.

col execution.” In the models, f1 12 (w) is equal to w when the wallme at w is less than one-and-half days from the beginning of protocol
n. Otherwise, f1 12 (w) is a previous state where the wall-clock time is less-and-half days from the beginning.
wedefinedcan spell
assumptions;wheneverblockchaina recordvea set outof infinitely
many logicalformulaswhere 'Yishas
replaced
finedasetofinfinitely
many
logicalformulaswhere'isreplaced
bitrary
logicalformulas.
nd-quarterdays,
Bob many
shouldlogicalhave formulas
read andwheresubmitted
the record tofinedasetofinfinitely'isreplaced
Anything
that
reaches
blockchain
Yby
1+1/4
days
also
ry
logicalformulas.
en
blockchain
Y contains
records at the two-day moment, it also contains
inby one-and-half
days:
ry X
logicalformulas.
ockchain
Y contains
records
at thetwo-day
moment,it alsocontains
reachesBob,
andchainXby
1+1/2days.
esfromtheone-and-quarter-day
moment,sayingthatthehashlock
ockchain Y contains records at the two-day moment, it also contains had
1 '.
(Ksettled;
K1 14 ')
KAliceKmoment,
KYthe
K1saying(Bob-has-chance)om
theone-and-quarter-day
that
the thehashlock
hador
Y
X K1 12hadBob
been
eitherused
secrettounlock
hashock,
4om the one-and-quarter-day moment, sayingthat the hashlock had
nould
settled;eitherAlice
had used the secret to unlock the hashock, orneverunlock
it:n settled;eitherAlice
had used thesecrettothe
unlockthe hashock,orhas
By
2days,
blockchainYsees,
hashlockonY
neverunlock
it:never unlock it:

What makes it work?

K1timeout((AY ^ k)since_ (¬AYbeenKopen1))).
+ 1/4 days.
Y (D2 or1
4

(Y-timed1)

K1114((A((AY^^k)k)__(¬A(¬AY))).
(Y-timed1)
K))).
(Y-timed1)
YY
14
ally, if Bob ever gets to know the secret, Alice should have opened theIn otherAlicedoes
notleak thesecretwithout
gettingthefundf Bob
everwords,
gets totoknow
thesecret,Aliceshouldhaveopened
theifk.
Bobevergetsknow
thesecret,AliceshouldhaveopenedtheBy
thetimeBobgetsthesecret,
Alicehas
openedthekchainY:otherwords,
Alicedoes
doesnot
notleakleakthethesecretsecretwithout
without
getting
fundother words,
Alicegettingthethefund(Alice-opsec)
nn Y:hashlock on Y. KBob k AY .
Kdays.
(Alice-opsec)
kkshould
AA. allow
BobBobYYhain X at one-and-halfK
Bob to unlock(Alice-opsec)
thehashlock:K(D2Y(DKY2chain X sees
thesecretsignedby Bobby
1 + 1/2 days,
X
daysshould
shouldallowBob
Bobtotounlock
unlockhashlock:
X atIfone-and-half
one-and-halfdays
allow
thethehashlock:1
K1 ((KonBob k)
the hash lockKXopens
X.
12

BX ).

(X-live1 2 )

1 1
1K
K
((Kk)
B).
(X-live1) 2)
Kk)
B(X-live1
XX K112 1 ((KBobX X ).
Bob2
en we impose those formulas
at every state, the desired weak binary
2Then it works somehow.
If a model satisfies (X-live2), (Y-timed1),(Alice-opsec), (Bob-has-chance), (X-live1+1/2) at every state,
the model also satisfies (Weak-BinaryOutcome) at every state.

Proof: reasoning on themodels or deductions?
I chose to reason about Kripke models directly
rather than using
(ax)
(⊃-E)

Km Ka ϕ ⊢sc Km Ka ϕ(nec)
(⊃-I)

(ax)

Km Ka ϕ ⊃ Km Kb ψ ⊢sc Km Ka ϕ ⊃ Km Kb ψKm Ka ϕ, Km Ka ϕ ⊃ Km Kb ψ ⊢sc Km Kb ψKa Km Ka ϕ, Ka (Km Ka ϕ ⊃ Km Kb ψ) ⊢sc Ka Km Kb ψKa Km Ka ϕ ⊢sc Ka (Km Ka ϕ ⊃ Km Kb ψ) ⊃ Ka Km Kb ψm Kb ψ), Ka Km Ka ϕ ⊢sc Ka Km Kb ψm Kb ψ) ⊢sc Ka Km Ka ϕ ⊃ Ka Km Kb ψ

because, defining a deduction system takes space.
and the formal proof is not smaller than the English proof
on models.

c (Km Ka ϕ ⊃ Km Kb ψ) ∨ (Km Kb ψ ⊃ Km Ka ϕ)

To remedy the situation, we need to assume certain communication bet
two chains. Especially, contents on blockchain Y should be read bytransmitted over to blockchain X in a timely manner.
In order to talk about the timing restrictions, we add two morethe language: 1 14 and 1 12 that represent “1 14 (resp. 1 12 ) days from the bof protocol execution.” In the models, f1 12 (w) is equal to w whenclock time at w is less than one-and-half days from the beginning ofexecution. Otherwise, f1 12 (w) is a previous state where the wall-clock ti“1 + 1/2 days”
and “1 + 1/4 days” are arbitrary.
than one-and-half days from the beginning.
Now we can spell out assumptions; whenever blockchain Y hasat one-and-quarter
days,aspects.
Bob should have read and submitted the rFailed to capture
probabilistic
blockchain X by one-and-half days:Discussion') KXin
K1“ KBob KY K
Y K1hidden
Finality of blockchains(Kare…”
1 '.beingpersistent.
1
4

1
2

1
4

Moreover, Bob never mistakenly believes finality.
Players’ strategies are missing.

(Bob-ha