A. Ideal Functionality
We now formally describe our ideal functionality Fswap
(Figure 3) for atomic swaps of coins that circumvents the
above problem. Fswap interacts with the two users U0;U1 and
the simulator S. In the first round, user U1 initiates a swap with
the message (swap1; id; V; V~ ; PK; P~K; S~K) that specifies the
coins V := (v1; : : : ; vn) (owned by U0) and ~ V := (~v1; : : : ; ~v~n)
(owned by U1) that are to be swapped. User U1 also gives his
authentication keys S~K for the addresses P~K corresponding to
the coins in ~ V .
In the second round, user U0 also acknowledges the swap
initiation by giving his authentication keys SK for the addresses
PK corresponding to the coins V . The ideal functionality uses
the Freeze subroutine to transfer each of those coins to an
id-specific address that is controlled by the functionality. The
functionality can do this because it knows the authentication
keys of each of those coins and can interact with FB to transfer
coins to these functionality controlled keys. If some transaction
fails, then the functionality returns the coins frozen so far to
the original owner.
In the third round, if user U0 aborts, all the coins are unfrozen
by the ideal functionality and transferred back to the respective
users. On the other hand, if the functionality receives buy for
some index set J  [~n] of coins from U0, then it uses the
Transfer subroutine to transfer the coins ~vj for j 2 J from
its control to user U0.
In the last round, if user U1 aborts, all the frozen coins of
user U0 (from V ) are unfrozen by the ideal functionality and
transferred back to user U0. On the other hand, all coins of
U1 that remained frozen (coins not in J) are unfrozen and
transferred back to U1. Otherwise, if user U1 responds with buy
for some index I  [n], the functionality uses the Transfer
subroutine to transfer the coins vi for i 2 I to user U1. Finally,
all coins still controlled by the functionality are unfrozen and
transferred to their initial owners.
Atomicity. The functionality ensures that if user U0 in round
3 aborts the swap, all the coins are refunded to both parties.
Instead if U0 initiates a swap for any subset of ~n coins in
round 3, user U1 is allowed to complete the swap in round 4
for all n coins. Since no party can unilaterally transfer a coin
(as it is locked with functionality), the functionality guarantees
atomicity for the n-to-~n swap.
The ideal functionality Fswap (in session id) interacts with
users U0 and U1 and the ideal adversary S.
(Round 1) Upon receiving (swap1; id; V; V~ ; PK; P~K; S~K)
from U1, where V := (v1; : : : ; vn) 2 N,
~ V := (~v1; : : : ; ~v~n) 2 N, PK := (pk1; : : : ; pkn),
P~K := (p~k1; : : : ; p~kn~), S~K := (s~k1; : : : ; s~kn~). Send
(swap1; id; V; V~ ; PK; P~K;U1) to S and store the input tuple.
(Round 2) Upon receiving (swap2; id; V; V~ ; PK; P~K; SK)
from user U0, where SK := (sk1; : : : ; skn), call the
subroutines Freeze(id; vi; pki; ski; i) and
Freeze(id; v~j ; p~kj ; s~kj ; j) for all i 2 [n] and j 2 [n~]. If all of
the invocations are successful, send
(swap2; id; V; V~ ; PK; P~K;U0) to S, store the input tuple and
proceed to round 3. Otherwise, revert the coin freezing by
invoking the corresponding subroutines
UnFreeze(id; vi; pki; i) and UnFreeze(id; v~j ; p~kj ; j).
(Round 3) Upon receiving (abort; id) from the user U0,
revert the freezing by calling UnFreeze(id; vi; pki; i) and
UnFreeze(id; v~j ; p~kj ; j) for all i 2 [n] and j 2 [n~].
Otherwise, upon receiving (buy; id; J; pk), for some J  [~n],
call the subroutine Transfer(id; J; pk). Store J and proceed
to round 4.
(Round 4) Upon receiving (abort; id) from the user U1, call
UnFreeze(id; vi; pki; i) for all i 2 [n] and
UnFreeze(id; v~j ; p~kj ; j) for all j 2= J and terminate.
Otherwise, upon receiver (buy; id; I; p~k) from U1 do the
following:
 If I 6= ; call Transfer(id; I; p~k), then
UnFreeze(id; v~j ; p~kj ; j) for all j 2= J and
UnFreeze(id; vi; pki; i) for all i =2 I.
 If I = ; call UnFreeze(id; vi; pki; i) and
UnFreeze(id; v~j ; p~kj ; j) for all i 2 [n] and j 2= J.
Notify S of the outcome of the operation.
Description of the subroutines
Freeze: On input a tuple (id; v; pk; sk; i), transfer v coins
from the address specified by pk (using sk) to some
id-specific address pkid controlled by the ideal functionality
via Post(id; pk; pkid; v). The function is successful if the
transaction is accepted by FB.
UnFreeze: On input a tuple (id; v; pk; i) transfer back the v
frozen coins to the corresponding public key pk, via
Post(id; pkid; pk; v).
Transfer: On input a tuple (id; I; pk), transfer all frozen
coins corresponding to the index set I to the public key pk,
via Post(id; pkid; pk;
P
i2I vi).
Fig. 3: Ideal functionality FB
swap for fair swap of coins
Fungibility. Notice that the functionality only makes standard
Transfer calls to the blockchain B. No additional information
is present, besides verification keys and transacted values. Thus
these calls are syntactically identical to regular transactions.

V. ATOMIC SWAPS FROM ADAPTOR SIGNATURES

Here we present an efficient atomic swap protocol for n-
to-~n swap of coins between two users P0 and P1, under the
condition that transactions are signed using Schnorr or ECDSA
signatures. The fundamental building blocks of our protocol
are adaptor signatures and verifiable timed dlog (VTD), both
of which are defined below.

A.  Adaptor Signature

Adaptor signatures [47] let users generate a pre-signature
on a message m which by itself is not a valid signature, but
can later be adapted into a valid signature if the user knows
some secret value. The formal definition of adaptor signatures
is given below.
Definition 2 (Adaptor Signatures): An adaptor signature
scheme AS w.r.t. a hard relation R and a signature
scheme DS = (KGen; Sign; Vf) consists of algorithms
(pSign; Adapt; pVf; Ext) defined as:
^ pSign(sk; m; Y ): The pre-sign algorithm takes as input
a secret key sk, message m 2 f0; 1g and statement Y 2 LR,
outputs a pre-signature ^.
0=1 pVf(pk; m; Y; ^): The pre-verify algorithm takes as
input a public key pk, message m 2 f0; 1g, statement Y 2 LR
and pre-signature ^, outputs a bit b.
 Adapt(^; y): The adapt algorithm takes as input a presignature
^ and witness y, outputs a signature .
y Ext(; ^; Y ): The extract algorithm takes as input a
signature , pre-signature ^ and statement Y 2 LR, outputs a
witness y such that (Y; y) 2 R, or ?.
In terms of security, we want (i) unforgeability that is similar
to the unforgeability of standard signature schemes, except that
we additionally want that producing a forgery  for some
message m is hard even given a pre-signature ~ on m, with
respect to some uniformly sampled instance Y 2 LR. We then
want (ii) witness extractability that guarantees that given a
valid signature  and a pre-signature ~ for a message m and
an instance Y , one can efficiently extract a witness y for Y .
Finally, we want (iii) pre-signature adaptability that guarantees
that any valid pre-signature ~ generated with respect to an
instance Y , can be adapted into a valid signature  if given
the witness y for the instance Y . For formal definitions we
refer the reader to Appendix C.
In this work, we consider the constructions proposed in [47]
of adaptor signatures where the signature scheme DS is
of Schnorr or ECDSA. The hard relation R used in their
constructions is that of the discrete log relation, where the
language is defined as: LR := fH : 9x 2 Zq
; s:t : H = Gxg,
where (G; G; q) are the group description, its generator, and
its order, respectively.

B. Verifiable Timed DLog

A Verifiable timed dlog [34] is defined with respect to a
group G of order q and a generator G. Here, a committer
generates a timed commitment of timing hardness T of a value
x 2 Zqsuch that H = Gx where H is public and x is referred
to as the dlog. (discrete logarithm) of H (wrt. G). The verifier
checks the well-formedness of the timed commitment and can
learn the value x by force opening the commitment in time T.
The formal definition is as follows.
Definition 3 (Verifiable Timed Dlog): A VTD for the group
G with generator G and order q is a tuple of four algorithms
(Commit;Verify; Open; ForceOp) where:
(C; ) Commit(x;T): the commit algorithm (randomized)
takes as input a discrete log value x 2 Zq (generated using
KGen(1)) and a hiding time T and outputs a commitment C
and a proof .
0=1 Verify(H;C; ): the verify algorithm takes as input a
group element H, a commitment C of hardness T and a proof
 and outputs 1 if and only if, the value x embedded in C
satisfies H = Gx. Otherwise it outputs 0.
(x; r) Open(C): the open algorithm (run by committer)
takes as input a commitment C and outputs the committed
value x and the randomness r used in generating C.
x ForceOp(C): the force open algorithm takes as input the
commitment C and outputs a discrete log value x.
The security requirements for a VTD scheme are that of
(i) soundness where the user is convinced that, given C, the
ForceOp algorithm will produce the committed dlog. value
x in time T and (ii) privacy, where all PRAM algorithms6
whose running time is at most t (where t < T) succeed
in extracting x from the commitment C and  with at most
negligible probability. For formal definitions we refer the reader
to Appendix E.
The construction of VTD from [34] makes use of time-lock
puzzles [59], a primitive that lets a committer embed a secret
inside a puzzle with the guarantee that the puzzle can be opened
only after time T. Specifically, the committer embeds the dlog.
value x inside a time-lock puzzle and uses a special NIZK proof
to prove its validity. Specifically, the NIZK proves that the
time-lock puzzle can be solved in time T and whats embedded
inside satisfies the equation H = Gx. They construct such an
efficient NIZK proof using cut-and-choose techniques, Shamir
secret sharing [60] and homomorphic time-lock puzzles [61].
For completeness, we recall their construction in Figure 9.

C.  2-Party Protocols

Joint Key Generation. We require that two parties P0 and
P1 jointly generate (ECDSA and Schnorr) keys. We denote
this interactive protocol by 􀀀SIG
JKGen, where SIG = Schnorr or
SIG = ECDSA. The joint key generation protocol 􀀀SIG
JKGen takes
as input the security parameter 1 and the group description
(G; G; q) as input from both parties. The protocol outputs the
public key pk to both parties and outputs the secret key share
sk0 to P0 and sk1 to P1. We efficiently instantiate 􀀀Schnorr
JKGen
with the interactive protocol from [62], where in the end we
have pk = Gsk (sk is the secret key), and sk = (sk0 + sk1).
On the other hand, we instantiate 􀀀ECDSA
JKGen with the protocol
6PRAM algorithms are polynomial time algorithms that have polynomially
bounded amount of parallel computing power.
9
from [63] where in the end we have pk = Gsk (sk is the secret
key), and sk = (sk0
sk1).
Joint Adaptor Signing. We require the parties P0 and P1 to
jointly generate adaptor signatures on messages with respect
to an instance Y of a hard (dlog) relation R, for a joint public
key pk. We denote this interactive protocol by 􀀀SIG
AdpSg which
takes as common input a message m, and an instance Y of the
hard relation R. As private input, party P0 and P1 input their
secret key share sk0 and sk1, respectively. Here sk0 and sk1
are shares of the secret key sk whose corresponding public key
is pk. The output of the protocol for both parties is the presignature
~, such that it holds that SIG
AS :pVf(pk; m; Y ; ~) = 1.
We efficiently instantiate 􀀀SIG
AdpSg for SIG = Schnorr and SIG =
ECDSA with the protocols from [46].

D.  Our Protocol

We now describe our atomic swap protocol for transaction
schemes based on Schnorr and ECDSA signature schemes.
In Figure 5 and Figure 6, we present the protocol for n-to-~n
atomic swaps. That is, coins v(0)
i for i 2 [n] of party P0 are
swapped with coins v(1)
k for k 2 [~n] belonging to party P1.
On Choosing the Timing Hardness T0 and T1. The parties
shall make conservative estimates of each other’s computational
power in force opening the VTD commitments. This is to
prevent scenarios where P0 or P1 with a powerful machine
force opens its VTD commitments earlier than expected in
terms of real time. The party could potentially steal the coins
of the other party during the swap lock or swap complete
phase. In particular, the parties must ensure that
(such that
T0 = T1 +
) is large enough such that it tolerates the time
differences to open the VTD commitments.
Security Analysis. In the below theorem, we precisely state
the security of the above atomic swap protocol. For a formal
proof, we refer the reader to Appendix F.
Theorem 5.1: Let SIG 2 fSchnorr; ECDSAg and let SIG
AS :=
(pSign; pVf; Adapt; Ext) be a secure adaptor signature scheme
with respect to a strongly unforgeable signature scheme SIG
DS :=
(KGen; Sign; Vf) and a hard dlog relation R. Let 􀀀SIG
JKGen; 􀀀AdpSg
be UC secure 2PC protocols for computing JKGen and pSign,
respectively. Let VTD be a timed private and sound verifiable
timed dlog scheme. Then the atomic swap protocol described
in Figure 5 with access to (FB;Fsmt;Fclock), UC-realizes the
functionality Fswap.
E. Cross-Curve Swaps
The protocol described in Figure 5 assumes that the
Schnorr/ECDSA signatures used for spending different coins
are implemented on the same curve. We can easily extend
our protocol to a case where all of the n + ~n coins are
from transaction schemes using Schnorr/ECDSA signatures
but are implemented on different curves, possibly over groups
of different orders. In such a scenario we have for i 2 [n],
coin v(0)
i is in a currency whose transaction scheme uses
SIG 2 fSchnorr; ECDSAg implemented in the group Gi
with generator Gi and order qi. Similarly, for k 2 [~n],
coin v(1)
k is in a currency whose transaction scheme uses
SIG 2 fSchnorr; ECDSAg implemented in the group ~Gk with
generator ~Gk and order ~qk.
It is not hard to see that the only bridge that connects
the different signature schemes is the hard instance Y and
as soon as the signature schemes are defined over different
groups, it becomes unclear how to sample Y . The natural
solution for this problem is to define a different Yi for each
signature as Yi = Gy
i (or ~ Yk = ~Gy
k, respectively), where
Gi is the generator of the i-th group. At this point, we can
compute the i-th pre-signature with respect to the corresponding
instance Yi, instead of using a fixed Y . Since the witness y
(i.e., the discrete logarithm) is identical for all Yi, correctness
is preserved. However, nothing prevents P0 from diverging
from the protocol, which is the reason why we also need
to include a Non-Interactive Zero Knowledge (NIZK) [64]
proof to certify that all instances (Y1; : : : ; Yn; ~ Y1; : : : ; ~ Y~n) have
the same discrete logarithm. Fortunately, this NIZK can be
efficiently instantiated extending the construction from [65]
to support proving of equality of discrete logarithm in n + ~n
groups. The rest of the protocol is the same as in Figure 5.
We now argue the security of the protocol with this modification
in place. The analysis largely follows along the same
lines of Theorem 5.1, with the exception that we can no longer
reduce to the standard dlog problem, since we are now given
access to many instances (across different groups) with the same
discrete logarithm. While this problem has been (implicitly)
used before, to the best of our knowledge, it has never been
formalized. We call this problem the cross-group short discrete
logarithm problem and define it below.
Definition 4 (n-Cross-Group Short Discrete Logarithm):
Consider fGi;Gi; qigi2[n] be n uniformly sampled groups of -
bits orders qi. Let qi = min(q1; : : : ; qn). Let y $Zqi . Then
for all PPT adversaries A there exists a negligible function
negl such that
Pr

A(fGi;Gi; qi;Gy
i gi2[n]) = y

= negl():
Observe that y cannot be sampled to be perfectly uniform over
all groups (Zq1 ; : : : ;Zqn), since the groups may have different
orders, therefore we sample it uniformly from Zqi , where
qi is the smallest prime. The work of Corrigan-Gibbs and
Kogan [66] shows that solving the short exponent discrete
logarithm problem is as hard as solving the standard discrete
logarithm problem (in a group of order qi ) in the generic
group model. That is, if y $Zqi then the running time of the
best known generic algorithm to compute y given Gy
i (for some
i 6= i) is O(
p
qi ). We conjecture that this equivalence is still
true even when given all (Gy
1; : : : ;Gy
n). This generalization is
a natural analogue of the computational Diffie-Hellman [67]
problem across groups, where different group elements are
replaced with different generators of different groups. This
assumption was implicit in prior works [68].

VI .  P E R F O R M A N C E   A N A L Y S I S

We first evaluate each building block of our protocol
separately, followed by the atomic swap protocol (Section V-D).

Global input: (G, G, q, v, pk, T), Party U0’s input: sk
Parties U0 and U1 do the following:
1) Execute the 2PC protocol 􀀀SIG
JKGen with with common input (G; G; q). Party U0 receives (tsk0; tpk) as output while U1
receives (tsk1; tpk).
2) Party U1 generates (C; ) VTD:Commit(tsk1;T) and sends (C; ) to U0.
3) Party U0 does the following:
 Checks if SIG = Schnorr. If so it further checks if VTD:Verify

= 1, and aborts otherwise.
 It generates tx frz := tx (pk; tpk; v) and a signature frz DS:SignSIG (sk; tx frz). It posts (tx frz; frz) on B.
 It starts solving VTD:ForceOp (C).
4) Party U0 returns (tx frz; frz; tpk; tsk0;C; ) and party U1 returns (tpk; tsk1) as output.
Fig. 4: Freeze Protocol for SIG = fSchnorr; ECDSAg
A.  Verifiable Time DLog
We developed a prototype C implementation of VTD [34]
to demonstrate the feasibility of our construction. The implementation
encompasses the Commit and Verify algorithms,
simulating thus the functionality that would be carried out by
the atomic swap participants during a successful swap. We omit
the Setup algorithm as this can be pre-computed and shared
across several instances of atomic swaps, and the ForceOp
algorithm, as it is only executed in case the coins are not
swapped and the running time is pre-defined by the timing
hardness T [48]. For the time-lock puzzles, we leveraged the
implementation available in [69].
Computation time. We evaluated the VTD construction VTD
for different values of the statistical parameter n. We set the
threshold to t = n=2 (not the same as T the hiding parameter
in VTD) as required for soundness of the VTD [34]. We obtain
the results shown in Table II. We observe that even with the
value n = 256 (possibly too high to be used in practice), the
overall running time is below 1 second, which is even below the
block confirmation time of virtually all cryptocurrencies today
that is in the order of several minutes. The practical advantage of
VTD shows up when comparing it to verifiable timed signatures
(VTS). As reported in [34], a VTS for the variants of Schnorr
and ECDSA requires approximately 7 seconds for the Commit
algorithm and 10 seconds for Verify with a value n = 30
whereas VTD requires only below 0:04 seconds.
Communication overhead. Apart from the crs and public
parameters of the underlying time-lock puzzle, the overhead
imposed by VTD is of (i) n group elements for verifiability of
Shamir secret sharing; (ii) a total of 4
n group elements for the
time-lock puzzles and related proofs; and (iii) a total of t 􀀀 1
pairs of two group elements (x; r) for the cut and choose style
proof. In summary, each party needs to store 5
n+(t􀀀1)
n
TABLE II: Computation time of VTD (in seconds).
n t VTD:Commit VTD:Verify
32 16 0:04 0:03
64 32 0:041 0:033
128 64 0:091 0:076
256 128 0:236 0:255
values of Zq to handle a VTD.

B.   2-Party Protocols for Adaptor Signatures

Here, we have used the implementation of the 2 party
computation protocol of adaptor signatures available at [70].
Computation time. We evaluated both the Schnorr and the
ECDSA implementations. We observe that the joint presignature
generation (Schnorr) requires 4:85 ms while that
for ECDSA requires 266:30 ms. For both implementations, the
pre-signature verification, witness extraction and pre-signature
adaption are rather fast (i.e. < 1 ms). As expected, these results
are similar to those in [46].
Communication overhead. The communication overhead
is the same as reported in [46] and we report it here for
completeness. In particular, the the 2PC protocol 􀀀Schnorr
AdpSg
requires 256 bytes of communication between the two parties
while its ECDSA counterpart 􀀀ECDSA
AdpSg requires 416 bytes.

C. Atomic Swap Protocol

For the sake of clarity we chose not to include several
optimisations to the description in Figure 5. We discuss them
below and also incorporate them in our implementation.
Implementation-level Optimizations. In the setup phase
(Figure 5), we create a new VTD commitment for each coin
that is being swapped, requiring thus n+~n VTD commitments
for both parties put together. However, in practice, one can
have the same functionality while each party has to create and
force open only a single VTD commitment.
To do this, assume for a moment that fungibility of the
transactions is not a problem. Then each party could create a
single key pair, embed the corresponding secret key in the VTD
and use the corresponding public key repeatedly as an address
for each of the coins that it owns (either n or ~n). In order to
gain fungibility back (i.e., make each public key look random
to the eyes of the blockchain observer), the two parties carry
out a coin toss protocol to generate a common randomness r
and generate each public key with respect to it. For instance,
consider that (pk; sk) was the key generated by P0. The i-th
public key can be computed as pkH(rjji). Note that given the
original public key pk and the randomness r, party P1 can
11
Global input:
n
v(0)
i ; pk(0)
i
o
i2[n]
;
n
v(1)
k ; pk(1)
k
o
k2[~n]
;T0;T1;
. Here T0;
2 N and T1 = T0 􀀀
.
Party P0’s input:
n
sk(0)
i
o
i2[n]
, Party P1’s input:
n
sk(1)
i
o
k2[~n]
Swap Setup Phase – Freezing coins
Parties P0 and P1 freeze the coins that they want to swap by doing the following:
1) For i 2 [n], party P0 plays the role of U0 and party P1 plays the role of U1 in the freeze algorithm (Figure 4). Specifically,
 Party P0’s input:

v(0)
i ; pk(0)
i ; sk(0)
i ;T0

, and party P1’s input:

v(0)
i ; pk(0)
i ;T0

.
 Party P0’s output:

tx (0)
frz;i; (0)
frz;i; pk(01)
i ; sk(01)
0;i ;C(0)
i ; (0)
i

, and party P1’s output:

pk(01)
i ; sk(01)
1;i

.
2) For k 2 [~n], party P0 plays the role of U1 and party P1 plays the role of U0 in the freeze algorithm (Figure 4). Specifically,
 Party P0’s input:

v(1)
k ; pk(1)
k ;T1

, and party P1’s input:

v(1)
k ; pk(1)
k ; sk(1)
k ;T1

.
 Party P0’s output:

pk(10)
k ; sk(10)
0;k

, and party P1’s output:

tx (1)
frz;k; (1)
frz;k; pk(10)
k ; sk(10)
1;k ;C(1)
k ; (1)
k

.
Swap Lock Phase
1) Party P0 picks (Y; y) 2 R using GenR(1) and sends Y to party P1.
2) Parties then setup the transactions doing the following:
 Party P1 generates

pk(1)
swpd;i; sk(1)
swpd;i

SIG
DS :KGen(1) for i 2 [n].
 Party P1 generates swap transaction tx (1)
swp;i := tx

pk(01)
i ; pk(1)
swpd;i; v(0)
i

for i 2 [n] and sends it to party P0.
 Party P0 generates

pk(0)
swpd;k; sk(0)
swpd;k

SIG
DS :KGen(1) for k 2 [~n].
 Party P0 generates swap transaction tx (0)
swp;k := tx

pk(10)
k ; pk(0)
swpd;k; v(1)
k

and sends it to party P1.
3) For i 2 [n], parties P0 and P1 run a 2PC protocol 􀀀SIG
AdpSg that does the following:
 The 2PC protocol takes as common input

tx (1)
swp;i; Y

from the parties, and as private input sk(01)
0;i from party P0, and as
private input sk(01)
1;i from party P1.
 If SIG = Schnorr, compute sk(01)
i :=

sk(01)
0;i + sk(01)
1;i

mod q, and if SIG = ECDSA, compute
sk(01)
i :=

sk(01)
0;i
sk(01)
1;i

mod q.
 It computes ~(1)
swp;i SIG
AS :pSign

sk(01)
i ; tx (1)
swp;i; Y

and outputs ~(1)
swp;i first to P0 and then to P1.
 Both parties check if SIG
AS :pVf

pk(01)
i ; tx (1)
swp;i; Y ; ~(1)
swp;i

= 1, and abort otherwise.
 In the end, both parties P0 and P1 obtain
n
~(1)
swp;i
o
i2[n]
.
4) After the above step is successful, for all k 2 [~n], party P0 and P1 run the 2PC protocol 􀀀SIG
AdpSg that does the following:
 The 2PC protocol takes as common input

tx (0)
swp;k; Y

from the parties, and as private input sk(10)
0;k from party P0, and
as private input sk(10)
1;k from party P1.
 If SIG = Schnorr, compute sk(10)
k :=

sk(10)
0;k + sk(10)
1;k

mod q, and, if SIG = ECDSA, compute
sk(10)
k :=

sk(10)
0;k
sk(10)
1;k

mod q
 It computes ~(0)
swp;k SIG
AS :pSign

sk(10)
k ; tx (0)
swp;k; Y

and outputs ~(0)
swp;k to both parties first to P0 and then to P1.
 Both parties check if SIG
AS :pVf

pk(10)
k ; tx (0)
swp;k; Y ; ~(0)
swp;k

= 1, and abort otherwise.
 In the end, both parties P0 and P1 obtain
n
~(0)
swp;k
o
k2[~n]
.
Fig. 5: Atomic Swap protocol run between parties P0 and P1 where SIG = fSchnorr; ECDSAg
verify that the i-th key is correctly generated. While knowing
the secret key sk, the party can derive ski := sk
H(rjji).
We can also parallelise the computation of different instances
of the 2PC protocol 􀀀SIG
AdpSg. In practice, it would be possible to
use the multi-core architecture available at current commodity
machines to perform this paralellization for moderate amount
of coin swaps.
Performance. With the aforementioned implementation-level
optimizations, we do a back-of-the-envelope calculation of
the performance of our protocol by extracting the number
12
Swap Complete Phase
1) For all k 2 [~n] party P0 computes (0)
swp;k SIG
AS :Adapt

~(0)
swp;k; y

, and posts

tx (0)
swp;k; (0)
swp;k

on the blockchain B.
2) Party P1 picks j 2 [~n], and does the following:
 Compute y SIG
AS :Ext

(0)
swp;j ; ~(0)
swp;j ; Y

, and for all i 2 [n], compute (1)
swp;i SIG
AS :Adapt

~(1)
swp;i; y

 It posts

tx (1)
swp;i; (1)
swp;i

for all i 2 [n] on the blockchain B (corresponding to currency of i-th coin).
Swap Timeout Phase
1) If party P0 fails to post

tx (0)
swp;j ; (0)
swp;j

for any j 2 [~n] on chain before time T1, party P1 does the following:
 Finish computing sk(10)
0;j VTD:ForceOp

C(1)
j

.
 If SIG = Schnorr, compute sk(10)
j :=

sk(10)
0;j + sk(10)
1;j

mod q, else if SIG = ECDSA, compute
sk(10)
j :=

sk(10)
0;j
sk(10)
1;j

mod q.
 Generate fresh key pairs

pk(1)
rfnd;i; sk(1)
rfnd;j

SIG
DS :KGen(1), and generate redeem transaction
tx (1)
rfnd;j := tx

pk(10)
j ; pk(1)
rfnd;j ; v(1)
j

.
 Generate a signature (1)
rfnd;j SIG
DS :Sign

sk(10)
j ; tx (1)
rfnd;j

on the redeem transaction.
 Reclaim the v(1)
j coins by posting

tx (1)
rfnd;j ; (1)
rfnd;j

on the blockchain B (corresponding to currency of j-th coin).
2) Similarly, if party P1 fails to post a valid transaction-signature pair

tx (1)
swp;j ; (1)
swp;j

for any j 2 [n] on chain before time
T0, party P0 follows steps analogous to above and reclaims the v(0)
j coins by posting

tx (0)
rfnd;j ; (0)
rfnd;j

on the blockchain B.
Fig. 6: Swap complete and timeout phase of the atomic swap protocol between P0 and P1 where SIG = fSchnorr; ECDSAg
of invocations to the underlying building blocks, namely (i)
adaptor signatures SIG
AS ; (ii) VTD commit and verify; and
(iii) standard digital signature scheme DS:Sign. We show
our results in Table III. Overall we observe that the protocol
uses several operations only once. The costliest operation is
􀀀SIG
AdpSg since it requires interaction between the two participants.
Yet, each instance of 􀀀SIG
AdpSg requires only 267ms for ECDSA
and 5ms for Schnorr as reported in Section VI-B. The rest
of operations that need to be repeated n + ~n times can be
performed locally by each participant.
Comparison with HTLC. We have taken the HTLC implementation
in Solidity available at [71] and calculated the gas
costs to compute the three operations required in a swap: (i)
create the HTLC contract; (ii) redeem the contract with a valid
hash preimage; and (iii) refund the contract in case the timeout
expires. The gas costs are shown in Table IV.
We observe that in the case of universal swap, we only
require a standard transfer of ETH between two accounts, an
TABLE III: Operations required in our atomic swap protocol.
Op type Setup Phase Lock Phase Complete Phase
Joint key generation 1 0 0
Key generation 0 (n + ~n) 0
Signing (n + ~n) 1 0
Signature verify 0 1 0
VTD commit 2 0 0
VTD verify 2 0 0
Joint pre-signing 0 (n + ~n) 0
Pre-signature verify 0 (n + ~n) 0
Pre-signature adapt 0 0 (n + ~n)
Witness extract 0 0 1
TABLE IV: Gas cost of swaps in Ethereum
Create Redeem Refund
HTLC 134320 79752 58065
Our n-to-~n Schnorr/ECDSA Swap 21000 21000 21000
inexpensive operation (since it is the basic one) in Ethereum.
In contrast, the HTLC-based operations require between 2.7x
and 6.3x more gas.
Apart from higher gas cost, the HTLC-based approach also
requires a higher transaction size, since it needs to store the
parameters of the contract (i.e., hash value, receiver and timeout).
This additional overhead not only hinders the scalability of
the underlying blockchain as the on-chain space is limited, but
also the fungibility of the swap, as it is trivial for an observer
to match two coins swapped as they share the same hash value.
In summary, although the swap functionality would be
easily implementable in a smart contract such as HTLC, our
protocol is preferable due to smaller on-chain cost both in
gas and transaction size, fungibility guarantees and backwards
compatibility with virtually all blockchains available today.

V I I.  C O N C L U S I O N

In this work we investigate the problem of atomic swaps
of multiple assets across all cryptocurrencies. We propose a
universal protocol supporting n-to-~n swaps. without relying
on any special scripts from the blockchain apart from the
ability to verify signatures. Following the outline of the generic
protocol we give a highly efficient protocol for the specific
cases where the transactions are signed with ECDSA or Schnorr
13
signatures. We also explore extensions to multi-party cyclic
swaps and cross-curve swaps. In terms of future work, we aim at
developing efficient solutions for other signature schemes with
different properties (e.g., post-quantum security or aggregatable
signatures).

R E F E R E N C E S

[1] A. Zamyatin, M. Al-Bassam, D. Zindros, E. Kokoris-
Kogias, P. Moreno-Sanchez, A. Kiayias, and W. J. Knottenbelt,
Sok: Communication across distributed ledgers,
Cryptology ePrint Archive, Report 2019/1128, https :
//eprint.iacr.org/2019/1128, 2019.
[2] J. Kwon and E. Buchman, Cosmos: A network of
distributed ledgers, https://github.com/cosmos/cosmos/
blob/master/WHITEPAPER.md.
[3] D. J. Hosp, T. Hoenisch, and P. Kittiwongsunthorn,
Comit – cryptographically-secure off-chain multi-asset
instant transaction network, 2018. arXiv: 1810.02174
[cs.DC].
[4] S. Thomas and E. Schwartz, Interledger: A protocol for
interledger payments, https://interledger.org/interledger.
pdf.
[5] G. Wood, Polkadot: Vision for a heterogenous multichain
framework, https : / / polkadot . network /
PolkaDotPaper.pdf.
[6] S. Dziembowski, L. Eckey, and S. Faust, “FairSwap:
How to fairly exchange digital goods,” in ACM CCS
2018, D. Lie, M. Mannan, M. Backes, and X. Wang,
Eds., ACM Press, Oct. 2018, pp. 967–984. D O I: 10.
1145/3243734.3243857.
[7] M. Herlihy, Atomic cross-chain swaps, 2018. arXiv: 1801.
09515 [cs.DC].
[8] M. Herlihy, B. Liskov, and L. Shrira, “Cross-chain
deals and adversarial commerce,” arXiv preprint
arXiv:1905.09743, 2019.
[9] G. Malavolta, P. Moreno-Sanchez, A. Kate, M. Maffei,
and S. Ravi, “Concurrency and privacy with paymentchannel
networks,” in ACM CCS 2017, B. M. Thuraisingham,
D. Evans, T. Malkin, and D. Xu, Eds., ACM Press,
2017, pp. 455–471. D O I: 10.1145/3133956.3134096.
[10] C. Baum, B. David, and T. Frederiksen, P2dex: Privacypreserving
decentralized cryptocurrency exchange, Cryptology
ePrint Archive, Report 2021/283, https://eprint.
iacr.org/2021/283, 2021.
[11] I. Bentov, Y. Ji, F. Zhang, Y. Li, X. Zhao, L. Breidenbach,
P. Daian, and A. Juels, Tesseract: Real-time cryptocurrency
exchange using trusted hardware, Cryptology
ePrint Archive, Report 2017/1153, https://eprint.iacr.org/
2017/1153, 2017.
[12] G. Chen, S. Chen, Y. Xiao, Y. Zhang, Z. Lin, and T. H.
Lai, “Sgxpectre: Stealing intel secrets from sgx enclaves
via speculative execution,” in 2019 IEEE European
Symposium on Security and Privacy (EuroS P), 2019,
pp. 142–157. D O I: 10.1109/EuroSP.2019.00020.
[13] J. Van Bulck, D. Oswald, E. Marin, A. Aldoseri, F. D.
Garcia, and F. Piessens, “A tale of two worlds: Assessing
the vulnerability of enclave shielding runtimes,” in
Proceedings of the 2019 ACM SIGSAC Conference on
Computer and Communications Security, ser. CCS ’19,
London, United Kingdom: Association for Computing
Machinery, 2019, 1741–1758, I S B N: 9781450367479.
D O I: 10.1145/3319535.3363206. [Online]. Available:
https://doi.org/10.1145/3319535.3363206.
[14] What is atomic swap and how to implement it, https:
//www.axiomadev.com/blog/what-is-atomic-swap-andhow-
to-implement-it/.
[15] Submarine swap in lightning network, https://wiki.ion.
radar.tech/tech/research/submarine-swap.
[16] Uniswap, https://uniswap.org/whitepaper.pdf.
[17] Raiden network, https://raiden.network/.
[18] M. Campanelli, R. Gennaro, S. Goldfeder, and L. Nizzardo,
“Zero-knowledge contingent payments revisited:
Attacks and payments for services,” in ACM CCS 2017,
B. M. Thuraisingham, D. Evans, T. Malkin, and D. Xu,
Eds., ACM Press, 2017, pp. 229–243. D O I: 10.1145/
3133956.3134060.
[19] S. Bursuc and S. Kremer, “Contingent payments on a
public ledger: Models and reductions for automated
verification,” in ESORICS 2019, Part I, K. Sako, S.
Schneider, and P. Y. A. Ryan, Eds., ser. LNCS, vol. 11735,
Springer, Heidelberg, Sep. 2019, pp. 361–382. D O I: 10.
1007/978-3-030-29959-0_18.
[20] I. Tsabary, M. Yechieli, A. Manuskin, and I. Eyal, Madhtlc:
Because htlc is crazy-cheap to attack, 2021. arXiv:
2006.12031 [cs.CR].
[21] tinyurl.com/2z59vhys.
[22] R. W. F. Lai, V. Ronge, T. Ruffing, D. Schröder, S. A. K.
Thyagarajan, and J. Wang, “Omniring: Scaling private
payments without trusted setup,” in ACM CCS 2019,
L. Cavallaro, J. Kinder, X. Wang, and J. Katz, Eds., ACM
Press, Nov. 2019, pp. 31–48. D O I: 10.1145/3319535.
3345655.
[23] A. Poelstra, Mimblewimble, https://download.wpsoftware.
net/bitcoin/wizardry/mimblewimble.pdf.
[24] D. Schwartz, N. Youngs, A. Britto, et al., “The ripple
protocol consensus algorithm,” Ripple Labs Inc White
Paper, vol. 5, no. 8, 2014.
[25] D. Mazieres, “The stellar consensus protocol: A federated
model for internet-level consensus,” Stellar Development
Foundation, vol. 32, 2015.
[26] E. Ben-Sasson, A. Chiesa, C. Garman, M. Green, I. Miers,
E. Tromer, and M. Virza, “Zerocash: Decentralized
anonymous payments from bitcoin,” in 2014 IEEE
Symposium on Security and Privacy, IEEE Computer
Society Press, May 2014, pp. 459–474. D O I: 10.1109/
SP.2014.36.
[27] https://thecharlatan.ch/Monero-Unlock-Time-Privacy/.
[28] https://github.com/mimblewimble/grin/issues/25.
[29] https://github.com/zcash/zcash/issues/344.
14
[30] https : / / medium . com / \spacefactor \
@m{}YcashFoundation / announcing – ycash – the – first –
friendly-fork-of-the-zcash-blockchain-ac386ed6368c.
[31] R. Canetti, “Security and composition of multiparty
cryptographic protocols,” Journal of Cryptology, vol. 13,
no. 1, pp. 143–202, Jan. 2000. D O I: 10 . 1007 /
s001459910006.
[32] D. Boneh and M. Naor, “Timed commitments,” in
CRYPTO 2000, M. Bellare, Ed., ser. LNCS, vol. 1880,
Springer, Heidelberg, Aug. 2000, pp. 236–254. D O I:
10.1007/3-540-44598-6_15.
[33] J. A. Garay and M. Jakobsson, “Timed release of
standard digital signatures,” in FC 2002, M. Blaze, Ed.,
ser. LNCS, vol. 2357, Springer, Heidelberg, Mar. 2003,
pp. 168–182.
[34] S. A. K. Thyagarajan, A. Bhat, G. Malavolta, N. Döttling,
A. Kate, and D. Schröder, “Verifiable timed signatures
made practical,” in Proceedings of the 2020 ACM
SIGSAC Conference on Computer and Communications
Security, ser. CCS ’20, Virtual Event, USA: Association
for Computing Machinery, 2020, 1733–1750, I S B N:
9781450370899. D O I: 10 . 1145 / 3372297 . 3417263.
[Online]. Available: https://doi.org/10.1145/3372297.
3417263.
[35] S. A. K. Thyagarajan, G. Malavolta, F. Schmidt, and
D. Schröder, Paymo: Payment channels for monero,
Cryptology ePrint Archive, Report 2020/1441, https :
//eprint.iacr.org/2020/1441, 2020.
[36] P. Moreno-Sanchez, A. Blue, D. V. Le, S. Noether,
B. Goodell, and A. Kate, “Dlsag: Non-interactive refund
transactions for interoperable payment channels in
monero,” in Financial Cryptography and Data Security,
J. Bonneau and N. Heninger, Eds., Cham: Springer
International Publishing, 2020, pp. 325–345.
[37] Tx1, https://tinyurl.com/y3n9hvqb.
[38] Tx2, https://tinyurl.com/y4yqoj2c.
[39] Tx3, https://tinyurl.com/y3m82xg5.
[40] Tx4, https://tinyurl.com/y3h6rh3f.
[41] Tx5, https://tinyurl.com/y2fsa3ak.
[42] M. Zhandry, “The magic of ELFs,” in CRYPTO 2016,
Part I, M. Robshaw and J. Katz, Eds., ser. LNCS,
vol. 9814, Springer, Heidelberg, Aug. 2016, pp. 479–508.
D O I: 10.1007/978-3-662-53018-4_18.
[43] B. Schoenmakers, M. Veeningen, and N. de Vreede,
“Trinocchio: Privacy-preserving outsourcing by distributed
verifiable computation,” in ACNS 16, M. Manulis,
A.-R. Sadeghi, and S. Schneider, Eds., ser. LNCS,
vol. 9696, Springer, Heidelberg, Jun. 2016, pp. 346–366.
D O I: 10.1007/978-3-319-39555-5_19.
[44] Engineers demonstrate zcash/bitcoin atomic swaps,
https : / / news . bitcoin . com / engineers – demonstrate –
zcashbitcoin-atomic-swaps/.
[45] J. Liu, T. Jager, S. A. Kakvi, and B. Warinschi, “How to
build time-lock encryption,” Des. Codes Cryptography,
vol. 86, no. 11, 2549–2586, Nov. 2018, I S S N: 0925-
1022. D O I: 10.1007/s10623- 018- 0461- x. [Online].
Available: https://doi.org/10.1007/s10623-018-0461-x.
[46] G. Malavolta, P. Moreno-Sanchez, C. Schneidewind,
A. Kate, and M. Maffei, “Anonymous multi-hop locks
for blockchain scalability and interoperability,” in
NDSS 2019, The Internet Society, Feb. 2019.
[47] L. Aumayr, O. Ersoy, A. Erwig, S. Faust, K. Hostakova,
M. Maffei, P. Moreno-Sanchez, and S. Riahi, Generalized
bitcoin-compatible channels, Cryptology ePrint Archive,
Report 2020/476, https://eprint.iacr.org/2020/476, 2020.
[48] S. A. K. Thyagarajan, A. Bhat, G. Malavolta, N. Döttling,
A. Kate, and D. Schröder, “Verifiable timed signatures
made practical,” in ACM CCS 20, ACM Press, 2020,
pp. 1733–1750. D O I: 10.1145/3372297.3417263.
[49] “Personal communication,” To Appear at ACM CCS
2021.
[50] R. Canetti, “Universally composable security: A new
paradigm for cryptographic protocols,” in Proceedings
42nd IEEE Symposium on Foundations of Computer
Science, IEEE, 2001, pp. 136–145.
[51] R. Canetti, Y. Dodis, R. Pass, and S. Walfish, “Universally
composable security with global setup,” in TCC 2007,
S. P. Vadhan, Ed., ser. LNCS, vol. 4392, Springer,
Heidelberg, Feb. 2007, pp. 61–85. D O I: 10.1007/978-3-
540-70936-7_4.
[52] S. Goldwasser, S. Micali, and R. L. Rivest, “A digital signature
scheme secure against adaptive chosen-message
attacks,” SIAM Journal on Computing, vol. 17, no. 2,
pp. 281–308, Apr. 1988.
[53] M. Backes and D. Hofheinz, “How to break and repair
a universally composable signature functionality,” in
ISC 2004, K. Zhang and Y. Zheng, Eds., ser. LNCS,
vol. 3225, Springer, Heidelberg, Sep. 2004, pp. 61–72.
[54] J. Katz, U. Maurer, B. Tackmann, and V. Zikas, “Universally
composable synchronous computation,” in
TCC 2013, A. Sahai, Ed., ser. LNCS, vol. 7785, Springer,
Heidelberg, Mar. 2013, pp. 477–498. D O I: 10.1007/978-
3-642-36594-2_27.
[55] S. Dziembowski, L. Eckey, S. Faust, J. Hesse, and
K. Hostáková, “Multi-party virtual state channels,” in
EUROCRYPT 2019, Part I, Y. Ishai and V. Rijmen, Eds.,
ser. LNCS, vol. 11476, Springer, Heidelberg, May 2019,
pp. 625–656. D O I: 10.1007/978-3-030-17653-2_21.
[56] L. Aumayr, O. Ersoy, A. Erwig, S. Faust, K. Hostakova,
M. Maffei, P. Moreno-Sanchez, and S. Riahi, “Generalized
bitcoin-compatible channels.,” IACR Cryptol. ePrint
Arch., vol. 2020, p. 476, 2020.
[57] A. R. Choudhuri, M. Green, A. Jain, G. Kaptchuk, and
I. Miers, “Fairness in an unfair world: Fair multiparty
computation from public bulletin boards,” in ACM CCS
2017, B. M. Thuraisingham, D. Evans, T. Malkin, and
D. Xu, Eds., ACM Press, 2017, pp. 719–728. D O I: 10.
1145/3133956.3134092.
[58] I. Bentov and R. Kumaresan, “How to use bitcoin
to design fair protocols,” in CRYPTO 2014, Part II,
J. A. Garay and R. Gennaro, Eds., ser. LNCS, vol. 8617,
15
Springer, Heidelberg, Aug. 2014, pp. 421–439. D O I:
10.1007/978-3-662-44381-1_24.
[59] R. L. Rivest, A. Shamir, and D. A. Wagner, “Timelock
puzzles and timed-release crypto,” Cambridge, MA,
USA, Tech. Rep., 1996.
[60] A. Shamir, “How to share a secret,” Communications
of the Association for Computing Machinery, vol. 22,
no. 11, pp. 612–613, Nov. 1979.
[61] G. Malavolta and S. A. K. Thyagarajan, “Homomorphic
time-lock puzzles and applications,” in CRYPTO 2019,
Part I, A. Boldyreva and D. Micciancio, Eds., ser. LNCS,
vol. 11692, Springer, Heidelberg, Aug. 2019, pp. 620–
649. D O I: 10.1007/978-3-030-26948-7_22.
[62] R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin,
“Secure distributed key generation for discrete-log
based cryptosystems,” in EUROCRYPT’99, J. Stern, Ed.,
ser. LNCS, vol. 1592, Springer, Heidelberg, May 1999,
pp. 295–310. D O I: 10.1007/3-540-48910-X_21.
[63] Y. Lindell, “Fast secure two-party ECDSA signing,” in
CRYPTO 2017, Part II, J. Katz and H. Shacham, Eds.,
ser. LNCS, vol. 10402, Springer, Heidelberg, Aug. 2017,
pp. 613–644. D O I: 10.1007/978-3-319-63715-0_21.
[64] A. De Santis, S. Micali, and G. Persiano, “Non-interactive
zero-knowledge proof systems,” in Conference on the
Theory and Application of Cryptographic Techniques,
Springer, 1987, pp. 52–72.
[65] S. Noether, Discrete logarithm equality across groups,
https://web.getmonero.org/zh- cn/resources/researchlab/
pubs/MRL-0010.pdf.
[66] H. Corrigan-Gibbs and D. Kogan, “The discretelogarithm
problem with preprocessing,” in EUROCRYPT
2018, Part II, J. B. Nielsen and V. Rijmen,
Eds., ser. LNCS, vol. 10821, Springer, Heidelberg, 2018,
pp. 415–447. D O I: 10.1007/978-3-319-78375-8_14.
[67] W. Diffie and M. E. Hellman, “New directions in cryptography,”
IEEE Transactions on Information Theory,
vol. 22, no. 6, pp. 644–654, 1976.
[68] J. Gugger, Bitcoin-monero cross-chain atomic swap,
Cryptology ePrint Archive, Report 2020/1126, https :
//eprint.iacr.org/2020/1126, 2020.
[69] A. Bhat, Liblhtlp – c library implementing linearly
homomorphic time lock puzzles, https : / / github.com/
verifiable-timed-signatures/liblhtlp.
[70] E. Tairi, Anonymous atomic locks (a2l), https://github.
com/etairi/A2L.
[71] Github Project, https : / / github.com/ chatch / hashed –
timelock-contract-ethereum.
[72] TierNolan, Atomic swap – bitcoin wiki, https://en.bitcoin.
it/wiki/Atomic_swap.
[73] M. Herlihy, B. Liskov, and L. Shrira, “Cross-chain deals
and adversarial commerce,” Proceedings of the VLDB
Endowment, vol. 13, no. 2, 100–113, 2019, I S S N: 2150-
8097. D O I: 10 . 14778 / 3364324 . 3364326. [Online].
Available: http://dx.doi.org/10.14778/3364324.3364326.
[74] A. Zamyatin, D. Harz, J. Lind, P. Panayiotou, A. Gervais,
and W. J. Knottenbelt, Xclaim: Trustless, interoperable
cryptocurrency-backed assets, Cryptology ePrint Archive,
Report 2018/643, https://eprint.iacr.org/2018/643, 2018.
[75] S. Dziembowski, L. Eckey, and S. Faust, Fairswap:
How to fairly exchange digital goods, Cryptology ePrint
Archive, Report 2018/740, https://eprint.iacr.org/2018/
740, 2018.
[76] A. Zamyatin, M. Al-Bassam, D. Zindros, E. Kokoris-
Kogias, P. Moreno-Sanchez, A. Kiayias, and W. J. Knottenbelt,
Sok: Communication across distributed ledgers,
Cryptology ePrint Archive, Report 2019/1128, https :
//eprint.iacr.org/2019/1128, 2019.
[77] S. Thyagarajan and G. Malavolta, “Lockable signatures
for blockchains: Scriptless scripts for all signatures,” in
2021 2021 IEEE Symposium on Security and Privacy
(SP), Los Alamitos, CA, USA: IEEE Computer Society,
2021, pp. 937–954. D O I: 10.1109/SP40001.2021.00065.
[Online]. Available: https://doi.ieeecomputersociety.org/
10.1109/SP40001.2021.00065.
[78] J. Camenisch, S. Krenn, and V. Shoup, “A framework
for practical universally composable zero-knowledge
protocols,” in ASIACRYPT 2011, D. H. Lee and X. Wang,
Eds., ser. LNCS, vol. 7073, Springer, Heidelberg, Dec.
2011, pp. 449–467. D O I: 10.1007/978-3-642-25385-
0_24.
[79] B. M. Thuraisingham, D. Evans, T. Malkin, and D. Xu,
Eds., ACM CCS 2017, ACM Press, 2017.
AP P E N D I X
A. Solution to Exercise
The solution to the fun exercise posed in Section I-B is the
transaction [37]. This is the swap transaction on the Bitcoin
side of the protocol.
B. Related Work
We give an overview of the related work in the following.
HTLC-Based Atomic Swaps. First introduced by Tier-
Nolan [72], HTLC-based atomic swaps have constituted the
core building block for several cryptocurrency transfers and
exchange protocols [7], [73]. These protocols however suffer
from the drawbacks on HTLC- and timelock-compatibility as
described previously in this section.
Other Approaches for Atomic Swaps. Atomic swaps based
on the Atomic Multi-Hop Locks (AHML) primitive [46] depart
from HTLC-based ones in that the cryptographic condition to
coordinate the swap is embedded in the creation of the digital
signature that authorizes the swap, thereby departing from the
need of hash functions. Yet, AMHL-based swaps as in [46]
still rely on ledgers compatible with timelock functionality
and support single-asset swaps. Recently, [68] have proposed
an atomic swap protocol between Bitcoin and Monero that
does not require hash functionality at any of the ledgers while
timelock functionality is only required at one of the ledgers
(i.e., in this case Bitcoin). Yet, this protocol is single-asset
swap and tailored to these two ledgers.
16
Decentralized Exchanges. Leveraging the expressive scripting
language available at cryptocurrencies like Ethereum, decentralized
exchanges are implemented as a smart contract that
encodes the (somewhat complex) logic to exchange multiple
assets among multiple users. This approach is, however, supported
only by those cryptocurrencies with expressive scripting
language such as that in Ethereum and forces uses with assets
in other ledgers to migrate their assets to Ethereum [74], [75].
Other Cross-chain Communication. Apart from the cryptocurrency
transfers and exchanges, cross-chain communication
is a critical component for scalability solutions such as sharding,
feature extensions via sidechains, as well as bootstrapping of
new systems. Although these applications are out of the scope of
this paper, we find them an interesting future research direction.
We refer the reader to [76] for further reading.
Scriptless Payment Channel Network. Lockable Signature
was a recently introduced tool [77] useful to construct payment
channel networks scriptlessly from any signature scheme.
However the resulting protocol still relies on time-lock scripts
from the currencies to realize payment expiry, and therefore is
not universal.
C. Security Definitions of Adaptor signatures
The correctness definition of adaptor signatures is described
below.
Definition 5 (Pre-signature Correctness): An adaptor
signature scheme AS satisfies pre-signature correctness if
for every  2 N, every message m 2 f0; 1g and every
statement/witness pair (Y; y) 2 R, the following holds:
Pr
2
66664
pVf(pk; m; Y; ^) = 1
^
Vf(pk; m; ) = 1
^
(Y; y0) 2 R

(sk; pk) KGen(1)
^ pSign(sk; m; Y )
 := Adapt(^; y)
y0 := Ext(; ^; Y )
3
77775
= 1:
Next, we formally define the security properties of an adaptor
signature scheme.
Definition 6 (Unforgeability): An adaptor signature scheme
AS is aEUF-CMA secure if for every PPT adversary A there
exists a negligible function negl such that:
Pr

aSigForgeA;AS () = 1

 negl()
where the experiment aSigForgeA;AS is defined as follows:
Definition 7 (Pre-signature Adaptability): An adaptor
signature scheme AS satisfies pre-signature adaptability if for
any  2 N, any message m 2 f0; 1g, any statement/witness
pair (Y; y) 2 R, any key pair (sk; pk) KGen(1) and any
pre-signature ^ f0; 1g with pVf(pk; m; Y; ^) = 1 we have:
Pr[Vf(pk; m; Adapt(^; y)) = 1] = 1
Definition 8 (Witness Extractability): An adaptor signature
scheme AS is witness extractable if for every PPT adversary
A, there exists a negligible function negl such that the following
holds:
Pr[aWitExtA;AS () = 1]  negl()
aSigForgeA;AS ()
Q := ;
(sk; pk) KGen(1)
m ASignO(
);pSignO(
;
)(pk)
(Y; y) GenR(1)
^ pSign(sk; m; Y )
 ASignO(
);pSignO(
;
)(^; Y )
return (m 62 Q ^ Vf(pk; m; ))
SignO(m)
 Sign(sk;m)
Q := Q [ fmg
return 
pSignO(m; Y )
^ pSign(sk; m; Y )
Q := Q [ fmg
return ^
Fig. 7: Unforgeabiltiy experiment of adaptor signatures
aWitExtA;AS ()
Q := ;
(sk; pk) KGen(1)
(m; Y ) ASignO(
);pSignO(
;
)(pk)
^ pSign(sk; m; Y )
 ASignO(
);pSignO(
;
)(^)
y0 := Ext(pk; ; ^; Y )
return (m 62 Q ^ (Y; y0) 62 R
^ Vf(pk; m; ))
SignO(m)
 Sign(sk;m)
Q := Q [ fmg
return 
pSignO(m; Y )
^ pSign(sk; m; Y )
Q := Q [ fmg
return ^
Fig. 8: Witness extractability experiment for adaptor signatures
where the experiment aWitExtA;AS is defined as follows
Combining the three properties described above, we can
define a secure adaptor signature scheme as follows.
Definition 9 (Secure Adaptor Signature Scheme): An adaptor
signature scheme AS is secure, if it is aEUF-CMA secure,
pre-signature adaptable and witness extractable.
D. Non-Interactive Zero Knowledge Proofs.
Let R : f0; 1g  f0; 1g ! f0; 1g be a n NP-witnessrelation
with corresponding NP language L := fx : 9w s.t.
R(x;w) = 1g. A non-interactive zero-knowledge proof
(NIZK) [64] system for the relation R is initialized with
a setup algorithm Setup(1) that, outputs a common reference
string crs and a trapdoor td. A prover can show
the validity of a statement x (provided he has a witness
w) by invoking PNIZK;LR(crs; x;w), which outputs a proof
. The verifier checks the proof  efficiently checked using
VNIZK;LR(crs; x; ). We require a NIZK system to be (1) zeroknowledge,
where the verifier does not learn more than the
validity of the statement x, and (2) simulation sound extractable,
if there exists an extractor algorithm E that on input the common
reference string crs, a trapdoor information td, the statement x
and the proof , and outputs a witness w such that (x;w) 2 R
with high probability. For formal UC-style definition of security
we refer the reader to [78].
E. Verifiable Timed Dlog
Definition 10 (Soundness): A VTD scheme VTD =
(Commit;Verify; Open; ForceOp) for a group G with generator
G and order q is sound if there is a negligible function negl()
17
such that for all probabilistic polynomial time adversaries A
and all  2 N, we have:
Pr
2
664
b1 = 1 ^ b2 = 0 :
(H;C; ;T) A(1)
x ForceOp(C)
b1 := Verify(H;C; )
b2 := (H = Gx)
3
775
 negl()
We say that a VTD is simulation-sound if it is sound even
when the prover has access to simulated proofs for (possibly
false) statements of his choice; i.e., the prover must not be
able to compute a valid proof for a fresh false statement of his
choice. In the following definition we present the definition of
privacy.
Definition 11 (Timed Privacy): A VTD scheme VTD =
(Commit;Verify; Open; ForceOp) for a group G with generator
G and order q is private if there exists a PPT simulator S,
a negligible function negl(), and a polynomial ~T such that
for all polynomials T > ~ T, all PRAM algorithms A whose
running time is at most t < T, all messages m 2 f0; 1g, and
all  2 N it holds that

Pr
2
4A(H;C; ) = 1 :
x f0; 1g
H := Gx
(C; ) Commit(x;T)
3
5
􀀀Pr
2
4A(H;C; ) = 1 :
x f0; 1g
H := Gx
(C; ) S(H;T)
3
5

 negl()
1) Construction of Verifiable Timed Dlog: The construction
uses a NIZK for proving range proofs over time-lock puzzles.
The language is specified below.
Lrange :=

stmt = (Z; a; b;T) : 9wit = (x; r) s.t.
(Z PGen(T; x; r)) ^ (x 2 [a; b])

The formal construction is given in Figure 9.
F. Security analysis of construction of Atomic Swaps from
Adaptor Signatures for Schnorr and ECDSA signatures
Proof 1 (Proof of Theorem 5.1): We now prove that our
protocol in Figure 5 securely US-realizes the atomic swap
functionality from Figure 3.
We describe a simulator S that handles either of the parties P0
or P1 that are corrupted by a PPT A and simulates the real world
execution protocol while interacting with the ideal functionality
Fswap. We have a static corruption where the environment E
at the beginning of a session specifies the corrupted parties
and the honest parties. The simulator S faithfully impersonates
the honest party. For operations exclusively among corrupted
users, the environment does not expect any interaction with
the simulator. Similarly, communications exclusively among
honest nodes happen through secure channels and therefore
the attacker does not gather any additional information other
than the fact that the communication took place. For simplicity,
we omit these operations in the description of our simulator.
The operations to be simulated for a n-to-~n atomic swap are
described in the following.
In describing S’s operations for swapping, we begin by
describing a series of hybrid executions, where we begin with
a real world execution and gradually change the simulation
in these hybrids and then we argue about the proximity of
neighbouring experiments. Simulator S’s execution for the
payment operation is defined as the final hybrid’s execution.
Below we describe the hybrid executions first and later argue
about their proximity. Note that the switching of hybrid
executions is performed over every session, but one at a time
and we only discuss here a single time for simplicity and
readability.
Hybrid H0: This is the same as the real execution of the
protocol in Figure 5.
Hybrid H1: This is the same as the above execution except
now the 2PC protocol 􀀀SIG
JKGen in the freezing coins of swap
setup phase to generate shared keys is simulated using the 2PC
simulator S2pc;1 for the corrupted parties. Notice that such a
simulator is guaranteed to exist for the 2PC protocol 􀀀SIG
JKGen.
Rest of the execution is unchanged from H0.
Hybrid H2: This is the same as the above execution except now
the 2PC protocol 􀀀AdpSg in the swap lock phase to generate
the pre-signatures is simulated using S2pc;2 for the corrupted
parties.
Hybrid H3: This is the same as the above execution except
now if in some session q3, the adversary corrupts user
P1 and the adversary outputs  on a transaction tx (1)
swp;i
under the public key pk(01)
i for some i 2 [n] such that
SIG
DS :Vf

pk(01)
i ; tx (1)
swp;i; 

= 1, before the simulator initiates
the swap on behalf of P0, the simulator aborts by outputting
abort1.
Hybrid H4: This is the same as the above execution except
now if in some session q4, the adversary corrupts P0 and
outputs  on a transaction tx (0)
swp;k under the public key pk(10)
k
for some k 2 [~n] such that SIG
DS :Vf

pk(10)
k ; tx (0)
swp;k; 

= 1.
The simulator computes y0 SIG
AS :Ext

; ~(0)
swp;k; Y

and if
(Y; y0) =2 R, the simulator aborts by outputting abort2.
Hybrid H5: This is the same as the above execution except now
if in some session q5, the adversary corrupts P0 and outputs
 on a transaction tx (0)
swp;k under the public key pk(10)
k for
some k 2 [~n] such that SIG
DS :Vf

pk(10)
k ; tx (0)
swp;k; 

= 1.
 the simulator computes y SIG
AS :Ext

; ~(0)
swp;k; Y

and
(Y; y) 2 R
 the simulator computes for all i 2 [n],
(1)
swp;i SIG
AS :Adapt

~(1)
swp;i; y

and there exists some i 2 [n] such that
SIG
DS :Vf

pk(01)
i ; tx (1)
swp;i ; (1)
swp;i

= 0
18
Setup: On input 1 the setup algorithm does the following.
 Run SetupZK(1) to generate crsrange
 Generate the public parameters pp PSetup(1;T)
 Output crs := (crsrange; pp)
Commit and Prove: On input (crs; wit) the Com algorithm does the following.
 Parse wit := x, crs := (crsrange; pp), H := Gx
 For all i 2 [t 􀀀 1] sample a uniform xi Zq and set Hi := Gxi
 For all i 2 ft; : : : ; ng compute
xi =
0
@x 􀀀
X
j2[t]
xj
`j(0)
1
A
`i(0)􀀀1
Hi =
0
@ H
Q
j2[t] H`j(0)
j
1
A
`i(0)􀀀1
where `i(
) is the i-th Lagrange polynomial basis.
 For i 2 [n], generate puzzles with corresponding range proofs as shown below
ri f0; 1g;Zi PGen(p; xi; ri)
range;i PNIZK;Lrange (crsrange; (Zi; a; b;T); (xi; ri))
 Compute I H0 (H; (H1;Z1; range;1); : : : ; (Hn;Zn; range;n))
 The Com algorithm outputs C := (Z1; : : : ;Zn;T) and  := (fHi; range;igi2[n]; I; fxi; rigi2I )
 Finally output (H;C; )
Verification: On input (crs;H;C; ) the Verify algorithm does the following.
 Parse C := (Z1; : : : ;Zn;T),  := (fHi; range;igi2[n]; I; fxi; rigi2I ) and crs := (crsrange; pp)
 If any of the following conditions is satisfied output 0, else return 1:
1) There exists some j =2 I such that
Q
i2I H`i(0)
i
H`j(0)
j 6= H
2) There exists some i 2 [n] such that VNIZK;Lrange (crsrange; (Zi; a; b;T); range;i) 6= 1
3) There exists some i 2 I such that Zi 6= PGen(p; xi; ri) or Hi = Gxi
4) I 6= H0 (H; (H1;Z1; range;1); : : : ; (Hn;Zn; range;n))
Open: The Open algorithm outputs (x; frigi2[n]).
Force Open: The ForceOp algorithm take as input C := (Z1; : : : ;Zn;T) and works as follows:
 Runs xi Solve(pp;Zi) for i 2 [n] to obtain all shares. ForceOp has to solve only (n 􀀀 t + 1) puzzles, as t 􀀀 1 puzzles
are already opened.
 Output x :=
P
j2[t](xj)
`j(0) where wlog., the first t are valid shares.
Fig. 9: Verifiable Timed Dlog for a group G with generator G and order q, where H = Gx; and x is the discrete log value
committed to
, the simulator aborts by outputting abort3.
Hybrid H6: This is the same as the above execution except now
if in some session q6, an adversarial P0, outputs any transaction
tx  and a signature  such that SIG
DS :Vf

pk(01)
i ; tx ; 

= 1
for some i 2 [n] before time T0, the simulator aborts by
outputting abortPRIV;0.
Hybrid H7: This is the same as the above execution except now
if in some session q7, an adversarial P1, outputs any transaction
tx  and a signature  such that SIG
DS :Vf

pk(10)
k ; tx ; 

= 1
for some k 2 [~n] before time T1, the simulator aborts by
outputting abortPRIV;1.
Hybrid H8: This is the same execution as above except now, if
in some session q8, the adversary corrupts P0, and the simulator
obtains sk0 VTD:ForceOp

C(1)
j

for some j 2 [~n]. The
simulator aborts with abort4, if sk0 6= sk(10)
0;j where sk(10)
0;j is
the secret share of the adversary generated in the freeze coin
phase.
Hybrid H9: This is the same execution as above except now, if
in some session q9, the adversary corrupts P1, and the simulator
obtains sk0 VTD:ForceOp

C(0)
j

for some j 2 [n]. The
simulator aborts with abort5, if sk0 6= sk(01)
1;j where sk(01)
1;j is
the secret share of the adversary generated in the freeze coin
19
phase.
Simulator S: The execution of the simulator is defined as the
execution in H9 while it interacts with the ideal functionality
Fswap. The simulator receives (swap1; id; V; V~ ; PK; P~K;U1)
and (swap2; id; V; V~ ; PK; P~K;U0) from Fswap. It proceeds
as in the execution of H9 by simulating the view of the
adversary appropriately as it receives messages from the ideal
functionality Fswap. If the simulated view deviates from the
execution of the ideal functionality, we note that the simulation
must have already aborted (as discussed in cases of abort in
the above hybrids).
Below we discuss the indistinguishability arguments and
we use the notation c;T to denote computational indistinguishability
for a PPT algorithm, and indistinguishability for
depth T bounded algorithms, respectively.
H0 c H1: the indistinguishability follow from the security
of the 2PC protocols, namely 􀀀SIG
JKGen in the freeze coin phase.
Security of the 2PC protocol 􀀀SIG
JKGen for the derivation of keys
guarantees the existence of S2pc;1.
H1 c H2: the indistinguishability follow from the security of
the 2PC protocols, namely 􀀀AdpSg in the swap lock phase. The
security of the 2PC protocol for the pre-signature generation
􀀀AdpSg guarantees the existence of S2pc;2. Notice that the
simulator extracts the adversaries key shares in 􀀀SIG
JKGen using
S2pc;1 and uses them in the simulation of S2pc;2.
H2 c H3: the only difference between the hybrids is that in
H3 the simulator aborts with abort1, if in some session q3,
the adversary corrupts user P1 and the adversary outputs 
on a transaction tx (1)
swp;i under the public key pk(01)
i for some
i 2 [n] such that SIG
DS :Vf

pk(01)
i ; tx (1)
swp;i; 

= 1, before the
simulator initiates the swap on behalf of P0. Via Lemma 1,
we bound the probability Pr[abort1jH3] to be negligible.
Therefore the indistinguishability between H2 and H3 follows.
Lemma 1: There exists a negligible function negl such that
Pr[abort1jH3]  negl()
Proof 2 (Lemma 1): To show this, we consider the following
hybrid executions. Using standard hybrid arguments we show
the indistinguishability of the hybrids. Using the final hybrid
execution we show a reduction to the unforgeability property of
the adaptor signature scheme and show that Pr[abort1jH3] 
negl(). Note that these hybrid executions are only designed
to prove the above lemma.
Hybrid H3;0: Is the same execution as H3 as in session q3,
except now the simulator chooses the keys pk(01)
i for i 2 [n]
and pk(10)
j for j 2 [~n] uniformly at random and chooses the
adversarial shares of the corresponding secret keys also to be
chosen unfirmly at random. Rest of the execution is unchanged.
Hybrid H03 : Is the same execution as H3;0 as in session
q3, except now the hard relation is chosen as follows. The
simulator samples Y R without the corresponding witness
and simulates the NIZK proof  SNIZK(Y ) using the NIZK
simulator SNIZK for the language LR. Rest of the execution is
unchanged.