arXiv CSopen access

Unicity: Predicates and Atomic Swaps

arXiv:2606.02192v1 [cs.CR] 1 Jun 2026

Unicity: Predicates and Atomic Swaps Ahto Buldas1 Dirk Draheim2 Mike Gault3 3 Risto Laanoja Vladimir Rogojin3 Ahto Truu3 1 2

Tallinn University of Technology, Estonia, [email protected] Tallinn University of Technology, Estonia, [email protected] 3 Unicity Labs OÜ, Estonia, [email protected] June 2, 2026 Abstract We generalize Unicity token ownership to programmable spending conditions called predicates, enabling smart-contract like functionality executed off-chain directly by relying parties rather than by consensus participants. We prove that the security properties of the Unicity execution layer are preserved under reduction to predicate family unforgeability. To demonstrate the utility of the model, we show how to implement trustless atomic swaps by using predicates.

1

Introduction

Predicates generalize the concepts of token ownership and transfer in the Unicity infrastructure, which in the paper [1] were defined via digital signatures as follows: • Owner – a (legal/physical) person who controls the private key of a digital signature scheme • Ownership condition – the public key pk that corresponds to the private key of the owner. • Transfer – the owner presents a digital signature σ on m = H(hst , htx ) (where hst , htx are the state hash and the transaction hash, respectively) such that V(pk, m, σ) = 1. In this paper, we present the following generalized concepts: • Owner – an abstract group of (legal/physical) persons that together control the information necessary to create the next transaction with the token. The information may include private keys. • Ownership condition – a logical condition (predicate) ν. 1

• Transfer – the owner (as a group) presents a bit-string u such that the condition ν(τ, m, u) = 1 holds, where m = H(hst , htx ) and τ is the system time (an integer defined by the Unicity service). This means that predicates may also put restrictions on transaction execution time. So far, we only have used predicates of type ν(τ, m, u) ≡ V(pk, m, σ), i.e. all predicates ν are in the form V(pk, ·, ·) and . The predicates approach is certainly not new and is used already in the Bitcoin blockchain, where ν is called the locking script and u is called the unlocking script or witness. A typical example of a generalized predicate is the delayed execution predicate defined by ν(τ, m, u) ≡ dexpk,τ0 (τ, m, u) ≡ (τ ≥ τ0 ) ∧ V(pk, m, u) = 1, which states that the next transaction can be executed by the owner of the private key of pk not earlier than τ0 . The delayed execution predicate is used in the protocols for inter-blockchain atomic swaps between Bitcoin type blockchains. It is a natural question whether the security properties (no double spending, no blocking, no association) will still hold in the Unicity infrastructure if the generalized predicates are in use. We will show shortly that double-spending is indeed impossible in the generalized scheme. However, the non-blocking condition is much less obvious. The main concern is that arbitrarily chosen predicates do not have guaranteed security properties like the UF-CMA condition for digital signatures. For example, if a user chooses the ownership predicate ν(τ, m, u) ≡ (u2 −2u+1 = 0) then anyone who is able to solve quadratic equations can make the next transfer with the token and hence, the no-blocking condition may seem to be violated. On the other hand, by intentionally choosing such an ownership condition, the previous owner may indicate that the next abstract owner of the token is the group of all people who can efficiently solve quadratic equations, and in this sense, intuitively, the no blocking condition is not violated. The predicates can also be chosen so that they cannot be solved (satisfied) in principle, i.e. they are logically inconsistent. For example ν(τ, m, u) ≡ (u2 +1 = 0), where u is required to be real number, cannot be satisfied. Another (less trivial) example of improper use of predicates is when a user applies one-time signature scheme as a many-times signature scheme. In this case, security-critical information leaks gradually so that an adversary, having triples (τ1 , m1 , u1 ), . . . , (τn , mn , un ) (so that ν(τi , mi , ui ) = 1), can construct a new triple (τ, m, u) such that ν(τ, m, u) = 1 and m ̸∈ {m1 , . . . , mn }. Therefore, the precise mathematical formulation of the no-blocking condition – only the owner of the private key of pk can block the state S = (pk, hst ) – must be revisited. We will redefine the no-blocking condition as follows – only those who can solve the predicate ν can block the state S = (ν, hst ), where by solving ν we mean finding, for a given m, a pair (τ, u) so that ν(τ, m, u) = 1. We will make this security definition precise and prove that it holds in the Unicity infrastructure. Intuitively, this means that undesired blocking can happen only because of the weakness of the user-chosen predicates and never because of the structural weakness of the Unicity infrastructure itself.

2

The paper is organized as follows. In Section 2 we define the predicates and give some examples. In Section 3, we show how to extend the Unicity Infrastructure with predicates. In Section 4, we prove that using predicates will not affect the security properties of the Unicity infrastructure. In Section 5, we discuss how to implement trustless atomic swaps by using predicates.

2

Predicates

In mathematics, a predicate ν is a function ν : D → {0, 1} that for every argument d ∈ D of the domain D defines a binary value ν(d) ∈ {0, 1}. A parametrized family of predicates is a set {ν(par; ·)}par∈P such that for every parameter par ∈ P, we have a predicate ν(par; ·) : Dpar → {0, 1}, i.e. ν(par; d) ∈ {0, 1} for every argument d ∈ Dpar . In this section, we describe how predicates are described in the Unicity infrastructure and give some examples of predicates.

2.1

Predicates in Unicity

Unicity infrastructure needs a somewhat restricted form of predicates. Every predicate νname (par; ·) in Unicity has: • Name of the predicate denoted by name • Parameters of the predicate denoted by par the type of which depends on name • Domain D = D0 × Dname , where D0 = T × H is the standard part and Dname is the name-dependent part. Here, T is the set of all possible time values and H is the range of the hash function H used in the Unicity system. Arguments of the predicates are in the form (τ, m, u), where: • τ ∈ T is the system time (explained below) • m ∈ H is a hash value • u ∈ Dname is the unlocking argument, the structure of which depends on both name and par. System time τ is a non-negative integer held by US and incremented when R is certified by the BFT layer. System time can be extracted from inclusion proofs by τ ′ ← time(π), where τ ′ is the value of system time when π was created. In a more technical description, the domain also contains a system information component T that enables to verify the inclusion proofs. In actual implementation of the system, T contains the blockchain verification information that comes from the consensus (BFT) layer of the system, which consists of the block headers of the blockchain. We assume that US and all users of the system 3

have up to date version of T and, in this paper, we do not describe or study how this is guaranteed. Therefore, we omit T for simplicity. In software implementations, predicates are encoded similarly to public keys – a predicate name code for name (like the algorithm identifier of generic public keys) followed by the binary representation of parameters par.

2.2

Examples of Predicates

In this section, we provide some examples of predicates that are useful to define in the Unicity infrastructure. 2.2.1

Signature Predicate

The signature predicate νsig (pk; ·) with a single public key pk as the parameter is equivalent to verification of a signatures with the public key pk, or in Bitcoin terms, pay to the public key. Standard arguments: τ, m, i.e. system time τ and hash of a transaction m. As all other predicates have the same standard arguments, we will omit them for the next predicates. Name-specific arguments: u = σ, i.e. u contains just a single digital signature σ. Definition: νsig (pk; τ, m, u) = 1 iff V(pk, m, σ) = 1 2.2.2

P2PKH Predicate

The Pay-to-Public-Key-Hash (P2PKH) predicate νp2pkh (hpk ; ·) with a public key hash hpk as the parameter is equivalent to verification of a signature with a public key that hashes to hpk . Name-specific arguments: u = (pk, σ), i.e. u contains the public key pk and a digital signature σ. Definition: νp2pkh (hpk ; τ, m, u) = 1 iff: • H(pk) = hpk ∧ V(pk, m, σ) = 1 2.2.3

Multi-Signature Predicate

The multi-signature predicate νmsig (pk1 , . . . , pkn ; ·) with a list pk1 , . . . , pkn of n public keys as parameters represents verification of n signatures on the same message hash. Name-specific arguments: u = (σ1 , . . . , σn ), where σi are digital signatures. Definition: νmsig (pk1 , . . . , pkn ; τ, m, u) = 1 iff: • V(pki , m, σi ) = 1 for every i ∈ {1, . . . , n}

4

2.2.4

Threshold-Signature Predicate

The threshold signature predicate νtsig (k, pk1 , . . . , pkn ; ·) with signature threshold k ∈ {1, . . . , n} and a list pk1 , . . . , pkn of n public keys as parameters is equivalent to verifying k digital signatures with different public keys (in the list) on the same message hash m. Name-specific arguments: u = ((σ1 , j1 ), . . . , (σk , jk )) contain a list of pairs (σi , ji ), where ji ∈ {1, . . . , n} is the index of the public key that is supposed to be used for verifying σi . Definition: νtsig (k, pk1 , . . . , pkn ; τ, m, u) = 1 iff: 1. V(pkji , m, σi ) = 1 for every i ∈ {1, . . . , k} 2. All ji are different, i.e. ji = ji′ implies i = i′ The last requirement is necessary because otherwise the predicate can be satisfied by presenting k copies of the same digital signature that verifies with the same public key, say pk1 . 2.2.5

Hashed Timelock Predicate

The hashed timelock predicate νhtlc (pk, pk′ , y, τmax ; ·) with two public keys pk, pk′ , a hash value y ∈ H, and a timeout τmax ∈ T as parameters is useful for atomic swaps, potentially between different blockchains [2, 3, 4]. We describe this predicate just as an example because the swap protocol described in this paper uses different predicates. Name-specific arguments: u = (x, σ), where x is a hash value (a pre-image of y) and σ is a a digital signature. Definition: νhtlc (pk, pk′ , y, τmax ; τ, m, u) = 1 iff (a) or (b), where: (a) V(pk′ , m, σ) = 1, y = H(x), and τ ≤ τmax (b) V(pk, m, σ) = 1 and τ > τmax The owner of pk′ is able to satisfy the predicate before system time τmax if he knows the H-preimage x of y. The owner of pk is able to satisfy the predicate after τmax .

3

Unicity Infrastructure with Predicates

3.1

Unicity Service with Predicates

Unicity service US maintains a key/value store R and system time τ , which is a non-negative integer. Initially, R[k] = ⊥ for every key k, and τ = 0. Unicity service processes requests Q = (ν, h, v, u), status queries Qst = (k), and new time messages N T = (τnew ):

5

• π ← US(Q): For k = H(ν, h) and m = H(h, v): – If R[k] = ⊥ and ν(τ, m, u) = 1 then: ∗ Assign R[k] ← (v, u) and return inclusion proof π – Else return error • (V, π) ← US(Qst ): Create inclusion proof π for V = R[k] and return (V, π). Note that V = (v, u) or V = ⊥ • US(N T ): If τ < τnew then τ ← τnew . Sometimes we use a shorthand notation R[k] = v instead of R[k] = (v, u) During the normal work of the system, NT is initiated by (and can only executed by) the consensus layer of the system. In attack scenarios, we will also give the adversary the access to the NT functionality. This is for making the security conditions stronger. It is easy to see that if (R0 , τ0 ) = (∅, 0) is the initial state, I1 , I2 , . . . , In is any sequence of inputs (requests or new time inputs), Ri is the dictionary after the input Ii , and τi is the system time after the input Ii , then: • τ0 ≤ τ1 ≤ . . . ≤ τn , i.e. the system time never decreases. • R0 ⊆ R1 ⊆ . . . ⊆ Rn , i.e. the elements are never removed. • The state Rn is a partial function, i.e. {(k, v), (k, v ′ )} ⊆ R implies v = v ′ . We say that a key k is blocked if R[k] ̸= ⊥.

3.2

Verification Function

We assume that the inclusion proofs πinc contain the system time τ , i.e. the value of τ when the corresponding new element was set in R. There is an extraction function time that extracts the system time from the proof πinc , i.e. τ ← time(πinc ). We assume that the inclusion proofs πinc can be verified by any party using a verification function V so that: • If V(k, v; πinc ) = 1 then R[k] = v in the current state (R, τ ) of US. Hence, ′ as R is a partial function, for every k, v, v ′ , πinc , πinc , the following implication holds: ′ V(k, v; πinc ) = V(k, v ′ ; πinc )=1

⇒

v = v′ .

(1)

• If R[H(ν, hst )] = htx after a request πinc ← US(ν, hst , htx , u) to the Unicity Service, then V(H(ν, hst ), htx , πinc ) = 1. • If a request πinc ← US(Q) was processed in the state S = (R, τ ) that changes R[H(ν, hst )] from ⊥ to ̸= ⊥, then time(πinc ) = τ .

3.3

Transactions with a Token

Every token has a state hash hst and an abstract owner A represented by a predicate ν. The state hash hst is initialized by the mint transaction of the token. We will call the pair (ν, hst ) the state of the token. 6

The transaction payload (before certifying the transaction) with the token is a pair T = (hst , D), where: 1. hst is the state hash before executing the transaction, 2. D (transaction data) contains the following fields: • ν ′ : the predicate of the next abstract owner, • x: a uniformly chosen random string x ← {0, 1}ℓ , • aux′ : auxiliary data for the next state. The pair (ν ′ , aux′ ) defines the next state of the token after executing the transaction T . The next state hash is h′st = H(hst , x). Certifying a transaction T = (hst , D) involves the following steps: 1. (htx , d) ← Com(H(D)) is computed using a perfectly hiding commitment scheme (Set, Com, Open). The commitment htx is called the transaction data hash. 2. The hash value hT = H(hst , htx ) is computed. 3. A solution u is created such that ν(τexp , hT , u) = 1 for an expected1 value τexp of system time. 4. The query Q = (ν, hst , htx , u) is created. 5. US is called to obtain π ← US(Q). 6. The certified transaction (T, u, htx , d, π) is formed. Verifying a certified transaction A certified transaction (T, u, htx , d, π) is verified in the state (ν, h) by the following algorithm: Vcert (T, u, htx , d, π; ν, h): If at least one of the following checks fail, return 0, otherwise return 1: 1. T.hst = h; 2. Open(htx , d) = H(T.D); 3. ν(time(π), H(hst , htx ), u) = 1; 4. V(H(ν, T.hst ), htx , π) = 1. Definition 3.1 (certification in a state) A tuple (T, u, htx , d, π) is said to be certified in state (ν, h) iff Vcert (T, u, htx , d, π; ν, h) = 1. Mint transactions are the same as in the signature-based ownership [1], i.e. they do not use generalized predicates.

3.4

Token Ledger

A token ledger is a sequence (T0 , u0 , π0 ; h1st ), (T1 , u1 , h1tx , d1 , π1 ; h2st ), . . . , (Tn , un , hntx , dn , πn ; hn+1 st ) where (T0 , u0 , π0 ) is a certified mint transaction and for every index i = 1, . . . , n: 1 In order to avoid failed certification calls, users could (1) query the current time from US to minimize the difference, and (2) prioritize safety in predicate design. For example, the delayed execution predicate dexpk,τ0 from the introduction uses an inequality τ ≥ τ0 , which remains satisfiable for all future times.

7

1. (Ti , ui , hitx , di , πi ) is a certified transaction in the state (Ti−1 .D.ν ′ , hist ); 2. hist = H(hi−1 st , xi−1 ) where xi−1 = Ti−1 .D.x.

4

Security

Consider a token with the state S = (ν, aux). The transfer protocol ensures the following properties: • No double-spending: Only one certified transaction can be created in the state S. • No association: the Unicity service is unable to identify the transactions with the same token. • No blocking: Only those who can solve the predicate ν can block the state S = (ν, aux) if it was not blocked before. In this section, we present security proofs for all three properties. The proofs of no double-spending and no association are very similar to the proofs in the paper [1]. The no blocking property had to be modified to cover arbitrary predicates.

4.1

Security against Double-Spending

A double-spending adversary uses US as an oracle. Double-spending scenario involves the following steps: ′ ), (ν, h) ← AUS . 1. (T, u, htx , d, πinc ), (T ′ , u′ , h′tx , d′ , πinc ′ 2. The attack is successful iff T ̸= T and ′ Vcert (T, u, htx , d, πinc ; ν, h) = Vcert (T ′ , u′ , h′tx , d′ , πinc ; ν, h) = 1 .

(2)

Definition 4.1 (Double-spending security) The Unicity Service is said to be S-secure against double-spending if it has S as a security profile2 in the double-spending scenario. Analysis: If the adversary is successful, then from (2) and the definition of Vcert it follows that T.hst = T ′ .hst = h and: ′ V(H(ν, h), htx ; πinc ) = V(H(ν, h), h′tx ; πinc )=1 ,

which implies htx = h′tx by equation (1). From Def. 3.1 it also follows that Open(htx , d) = H(T.D) and Open(htx , d′ ) = Open(h′tx , d′ ) = H(T ′ .D). From (h, T.D) = (T.hst , T.D) = T ̸= T ′ = (T ′ .hst , T ′ .D) = (h, T ′ .D) it follows that T.D ̸= T ′ .D. Hence, we have two cases: a) H(T.D) = H(T ′ .D), which means that a collision has been found for H. b) H(T.D) ̸= H(T ′ .D), which implies Open(htx , d) = H(T.D) ̸= H(T ′ .D) = Open(htx , d′ ) and hence, the commitment htx has been opened in two different ways. 2 The concept of security profiles is defined in [1].

8

Theorem 4.1 If H is S-secure collision-resistant and the commitment scheme is S-secure computationally binding, then the Unicity service is Sdouble -secure against double-spending, where Sdouble (ϵ) = S(ϵ/2) tver +1 and tver is the predicate verification time. Proof. Let A be a t-time double-spending adversary that succeeds with probability ϵ. We construct a collision-finder Acoll for the hash function and a doubleopening adversary Acom for the commitment scheme as follows: • Acoll proceeds as follows: ′ 1. Simulate (T, u, htx , d, πinc ), (T ′ , u′ , h′tx , d′ , πinc ), (ν, h) ← AUS by maintaining its own version of US. 2. Output the pair (T.D, T ′ .D).

The computational overhead function of Acoll is τcoll (t) = (tver + 1) · t, because simulating a US query requires one predicate verification and the number of calls is limited by the running time t of A. • Acom proceeds as follows: ′ 1. Simulate (T, u, htx , d, πinc ), (T ′ , u′ , h′tx , d′ , πinc ), (ν, h) ← AUS by maintaining its own version of US. 2. Output the triple (htx , d, d′ ).

The computational overhead function of Acom is the same as that of Acoll , i.e. τcom (t) = τcoll (t) = (tver + 1) · t. If A succeeds, then in case a) the collision finder Acoll succeeds, and in case b) the double-opener Acom succeeds. Hence, ϵ ≤ ϵcoll +ϵcom , where ϵcoll is the success probability of Acoll and ϵcom is the success probability of Acom . Therefore, the function Sdouble defined by −1 Sdouble (ϵ) = τcoll (S(ϵ/2)) =

S(ϵ/2) tver + 1

is a security profile of the Unicity service against double-spending.

4.2

□

Security against Association

The Association adversary A = (A1 , A2 ) is two-stage. Association scenario involves the following steps: 1. (hst , ν ′ , aux′ , a) ← A1 . 2. x ← {0, 1}ℓ . 3. h′st ← H(hst , x). 4. htx ← Comc (H(ν ′ , x, aux′ ))). 3 5. x′ ← A2 (a; h′st , htx ). 3 We denote by Comc (par, m) the function that computes (c, d) ← Com(par; m) and returns only c.

9

6. The attack is successful iff hst ∈ {0, 1}k , x′ ∈ {0, 1}ℓ , and H(hst , x′ ) = h′st . The success ϵ of A is the probability that the attack is successful. Definition 4.2 (association security) The Unicity Service is said to be Ssecure against association if it has S as a security profile in the association scenario. Theorem 4.2 If the hash function is S-secure (k, ℓ)-one-way4 and the commitment scheme is perfectly hiding, then the Unicity Service is Sassoc -secure against association, where Sassoc (ϵ) = S(ϵ) − tsm − thash − tcom , where tsm , thash , tcom are the random sampling time, the hashing time, and the commitment computation time, respectively. Proof. Let A = (A1 , A2 ) be a t-time adversary that succeeds in the association scenario with probability ϵ. Consider the following modified attack scenario: 1. (hst , ν ′ , aux′ , a) ← A1 . 2. x ← {0, 1}ℓ . 3. h′st ← H(hst , x). 4. x′′ ← {0, 1}ℓ . 5. h′tx ← Comc (H(ν ′ , x′′ , aux′ ))). 6. x′ ← A2 (a; h′st , h′tx ). 7. The attack is successful iff hst ∈ {0, 1}k , x′ ∈ {0, 1}ℓ , and H(hst , x′ ) = h′st . For any fixed value of L = (hst , ν ′ , aux′ , a), due to perfect hiding, commitments htx = Comc (H(ν ′ , x, aux′ )) and h′tx = Comc (H(ν ′ , x′′ , aux′ )) have equal probability distributions. Moreover, by the Output Independence Lemma5 (with g(x) = H(ν ′ , x, aux′ )), the random variables x and htx = Comc (H(ν ′ , x, aux′ )) are independent. Since x′′ and x are independent, the commitment h′tx = Comc (H(ν ′ , x′′ , aux′ )) is independent of both x and h′st = H(hst , x). Therefore, the joint distributions of (h′st , htx ) and (h′st , h′tx ) are equal, and hence A succeeds in the modified scenario with probability ϵ. We construct an adversary A′ = (A′1 , A′2 ) as follows: • A′1 proceeds as follows: 1. (hst , ν ′ , aux′ , a) ← A1 ; 2. return (hst , a′ ), where a′ = (ν ′ , aux′ , a). • A′2 (a′ ; y) with a′ = (ν ′ , aux′ , a) proceeds as follows: 1. x′′ ← {0, 1}ℓ ; 2. h′tx ← Comc (H(ν ′ , x′′ , aux′ ))); 3. x′ ← A2 (a; y, h′tx ); 4. return x′ . 4 Defined in [1]. 5 Defined in [1].

10

The computational time overhead function of A′ is τ (t) = t + tsm + thash + tcom and hence, the function Sassoc defined by Sassoc (ϵ) = τ −1 (S(ϵ)) = S(ϵ) − tsm − thash − tcom is a security profile of the Unicity service against association.

4.3

□

Security against Blocking

By a predicate family we mean a pair (Gpr , Spr ) of algorithms so that: • (sk, ν) ← Gpr generates a private key sk and a predicate ν. • Spr (sk, m) solves the predicate for m, i.e. either ⊥ ← Spr (sk, m) (the solver gives up) or (τ, u) ← Spr (sk, m) such that ν(τ, m, u) = 1. The case ⊥ ← Spr (sk, m) is necessary because the predicates can potentially be chosen so that they cannot be satisfied. A predicate solving adversary AO solve for the predicate family (Gpr , Spr ) uses an oracle O that uses (initially empty) dictionaries sk[ι], ν[ι] as the state and answers to two types of queries: • O(gen; ι) – a generation query that returns ⊥ if ν[ι] ̸= ⊥, and otherwise generates (sk, ν) ← Gpr , sets sk[ι] ← sk, ν[ι] ← ν, and returns ν. • O(solve; ι, m) – a solving query that returns ⊥ if either ν[ι] = ⊥ or Spr (sk[ι], m) = ⊥, and otherwise, if (τ, u) ← Spr (sk[ι], m), it returns (τ, u). The predicate solving scenario involves the following steps: 1. (ι, τ, m, u) ← AO solve 2. The attack is successful if: a) ν[ι] ̸= ⊥, i.e. the query O(gen; ι) was made by AO solve . b) ν[ι](τ, m, u) = 1 c) All queries of the form O(solve; ι, m) made by AO solve (if there were any) were answered with ⊥. A blocking adversary A uses two oracles: 1. US: the Unicity Service, 2. TS: that uses (initially empty) dictionaries sk[ι], ν[ι] as the state and answers to two types of queries: • TS(gen; ι) – a generation query that returns ⊥ if sk[ι] ̸= ⊥, and otherwise generates (sk, ν) ← Gpr , sets sk[ι] ← sk, ν[ι] ← ν, and returns ν. • TS(solve; ι, h, D) – a solving query that returns ⊥ if either sk[ι] = ⊥ or Spr (sk[ι], H(h, htx )) = ⊥, and otherwise, returns (τ, u, htx , d), where (htx , d) ← Com(H(D)) and (τ, u) ← Spr (sk[ι], H(h, htx )). Blocking scenario involves the following steps: 11

1. (ι, hst ) ← AUS,TS 2. A is successful if: a) ν[ι] ̸= ⊥ b) R[H(ν[ι], hst )] ̸= ⊥ after the scenario c) No (successful) queries of the form TS(solve; ι, hst , D) were made. The success ϵ of A is the probability that the attack is successful Note that if such a query was made, then the request Q = (ν[ι], hst , htx , u) to US at system time τ will trivially ensure R[H(ν[ι], hst )] ̸= ⊥. Note that the adversary can set the system time appropriately before the request Q. Hence, this is excluded by the security condition. Definition 4.3 (blocking security) The Unicity Service is said to be S-secure against blocking if it has S as a security profile in the blocking scenario. Analysis: The adversary A can be successful in the following cases: a) A request Q = (ν ′ , h′st , htx , u) with (ν ′ , h′st ) ̸= (ν[ι], hst ) to US enforces R[H(ν[ι], hst )] ̸= ⊥, which means that H(ν[ι], hst ) = H(ν ′ , h′st ) and hence, a collision for H was found. b) A request Q = (ν[ι], hst , htx , u) to US enforces R[H(ν[ι], hst )] ̸= ⊥, which implies ν[ι](τ, H(hst , htx ), u) = 1 from the description of US. Then we have two possibilities: b1) A query (τ ′ , u′ , h′tx , d) ← TS(solve; ι, h′st , D) was made such that the equality H(h′st , h′tx ) = H(hst , htx ) holds. From the success condition of A it follows that h′st ̸= hst and we have a collision for H. b2) If no queries (τ ′ , u′ , h′tx , d) ← TS(solve; ι, h′st , D) were made with H(h′st , h′tx ) = H(hst , htx ) then this means that A was able to solve the predicate family, i.e. for m = H(hst , htx ) finds τ, u so that ν[ι](τ, m, u) = 1 without using the predicate solving functionality. Theorem 4.3 If the predicate family (Gpr , Spr ) is S-secure against solving and the hash function is S-secure collision-resistant, then the Unicity service is Sblock -secure against blocking, where Sblock (ϵ) = max{tgen ,tS(ϵ/2) and tgen , sig ,tver ,tcom ,thash } tsig , tver , tcom , thash are the key generation time (for Gpr ), solving time (for Spr ), verification time (for ν), commitment time, and hashing time, respectively. Proof. Let A be a t-time blocking adversary that succeeds with probability ϵ. We construct a collision-finder Acoll and a solver AO solve as follows: • Acoll proceeds as follows: 1. Simulates (ι, hst ) ← AUS,TS and records all the oracle queries. 2. If AUS,TS was successful and either the case a) or b1) occurs, Acoll outputs the collision that is guaranteed in this case. The oracles are simulated as follows: 12

– US-queries: Acoll maintains its own version of R. – TS-queries: Acoll directly uses Gpr and Spr . The computational time overhead function for the construction of Acoll is τcoll (t) = max{tgen , tsig , tver } · t, where tver is the predicate verification time (for US-queries), tsig is the predicate solving time (for TS(solve; ·)-queries), and tgen is the generation time (for TS(gen; ·)-queries). • AO solve proceeds as follows: 1. Simulates (ι, hst ) ← AUS,TS and records all the oracle queries. 2. If AUS,TS was successful and b2) occurs and Q = (ν ′ , hst , htx , u) was the request that enforces R[H(ν[ι], hst )] ̸= ⊥ at system time τ then: 3. m ← H(hst , htx ). 4. Output (ι, τ, m, u). The oracles are simulated as follows: – US-queries are simulated so that AO solve maintains its own version of R. – US-queries are simulated so that AO solve maintains its own copy of the dictionary ν[] and processes the queries as follows: ∗ TS(gen; ι) – If ν[ι] ̸= ⊥ then return ⊥. Otherwise, call ν[ι] ← O(gen; ι) and return ν[ι]. ∗ TS(solve; ι, h, D) – If ν[ι] = ⊥ then return ⊥. Otherwise, compute (htx , d) ← Com(H(D)), call v ← O(solve; ι, H(h, htx )) and return v. Note that either v = ⊥ or v = (τ, u). As the request Q was accepted by US and it changes R[H(ν[ι], hst )], we have ν ′ = ν[ι] (description of US) and ν[ι](τ, m, u) = 1. Note that in the case b2) the request TS(solve; ι, hst , D) with Open(htx , d) = H(D) was never made which also means that the query O(solve; ι, m) with m = H(hst , htx ) was never made, and hence, AO solve is successful in the predicate solving scenario. The computational time overhead function for the construction of AO solve , on the assumption that t ≥ 1, is τsolve (t) = max{tver , tcom } · t + thash ≤ max{tver , tcom , thash } · t where tver is the predicate verification time (for US queries), tcom is the commitment time (for TS(solve; ·)-queries) and thash is the hash computation time (for output). If A succeeds, then either Acoll or AO solve succeeds and hence ϵ ≤ ϵcoll +ϵsolve . As for the function τ (t) = max{tgen , tsig , tver , tcom , thash } · t the inequalities τcoll (t) ≤ τ (t) and τsolve (t) ≤ τ (t) hold, we imply that Sblock (ϵ) = τ −1 (S(ϵ/2)) =

S(ϵ/2) max{tgen , tsig , tver , tcom , thash }

is a security profile of the Unicity Service against blocking.

13

□

5

Atomic Swap in the Unicity Infrastructure

In this section, we describe an atomic commit protocol in the Unicity Infrastructure that uses specific predicates. The protocol has several advantages compared to the hashed timelock based inter-blockchain atomic swaps used for example in Bitcoin-like blockchains. For example, it is secure even if unconditional delays occur in the system. The key aspect of success is the presence of a common reference information provided by the Unicity service.

5.1

Motivation and General Idea

The goal of atomic swap is to fairly and securely exchange tokens between their owners. Assume users A and B own tokens TokA and TokB and they want to exchange their tokens so that after the exchange, A owns TokB and vice versa. The parties agree to a certain timeout and run the swap protocol so that the following properties hold: 1. If both parties follow the protocol, then the tokens change their owners. 2. If at least one party deviates from the protocol, then A and B will retain control over their tokens after the agreed timeout. To achieve this goal, the following multi-stage protocol is used: 1. The parties transfer their tokens to special preparation states and agree on the timeout. 2. The parties send each other the whole token ledgers and verify whether the tokens are indeed in the preparation states (based on the ledgers). 3. The parties (are supposed to) commit, i.e. transfer (independently) their tokens (directly from the preparation states) to special commit (swap) states. The swap states are defined (via suitable ownership predicates) so that: 1. If TokA is in the swap state, then B will control (can make the next transaction with) TokA if B committed TokB in time (before the timeout), and otherwise, A will retain its control after the timeout. 2. If TokB is in the swap state, then A will control (can make the next transaction with) TokB if A committed TokA in time (before the timeout), and otherwise, B will retain its control after the timeout. The main question is how to define the abstract ownership predicates for the preparation states and for the swap states that guarantee the requirements of the atomic swap protocol, and how to define the unlocking witness u of the swap predicate so that it includes the knowledge about actions of the other party, considering that the commitments may happen independently without direct communication between the parties.

14

5.2

Design Choices of the Protocol

Assume that initially, TokA and TokB are in ”pure” states S0A = (νsig (pkA ; ·), h0A ) and S0B = (νsig (pkB ; ·), h0B ), respectively, i.e. their use (next transfer) requires digital signatures of the parties. In the preparation phase, the parties transfer their tokens to the preparation A B states Sprep = (νprep (pkA ; ·), h1A ) and Sprep = (νprep (pkB ; ·), h1B ), respectively by A A B B executing transactions Tprep = (h0A , Dprep ) and Tprep = (h0B , Dprep ), where: A Dprep

=

A (νprep (pkA ; ·), xA prep , auxprep )

B Dprep

=

B (νprep (pkB ; ·), xB prep , auxprep ) .

The execution means that the parties sign those transactions, obtain the inA B A = from US, and add certified transactions Cprep and πprep clusion proofs πprep B B B B A A A (Tprep , σprep , πprep ) and Cprep = (Tprep , σprep , πprep ) to their ledgers. As the parB A and Tprep ties are supposed to exchange their ledgers, they can both see Tprep and can check that the transactions contain the correct preparation predicates. Note also that the predicate νprep is defined in a way that after preparation, both parties still have full control over their tokens, i.e. transferring the tokens further requires only the knowledge of their own private keys. In the commit phase, the parties transfer their tokens to the swap states: A Sswap

=

(νswap (pkA , h1A , pkB , h1B , τmax ; ·), h2A )

B Sswap

=

(νswap (pkB , h1B , pkA , h1A , τmax ; ·), h2B )

B B A A ), but the = (h1B , Dswap ) and Tswap = (h1A , Dswap by executing transactions Tswap problem is that the parties may not see each other transactions. For example, A (or any other if A is malicious and commits, but after that does not send Tswap information) to B. If B also committed, then for making the next transaction A with TokA (swap happened) B has to construct a certified transaction for Tswap without knowing the contents of the transaction. If A did not commit and refuses to communicate with B then how can B ”convince” the swap predicate of his own token that A did not commit in time? The only additional information source for B is the Unicity Service, which gives information of type R[k] = v, i.e. which indices k correspond to which A A values. For example, B can query US for the status of kprep = H(Sprep ), and A ′ if R[kprep ] = ⊥ at τ > τmax , then B knows that A did not commit in time A because a timely swap transaction would have caused R[kprep ] ̸= ⊥ before τmax . A ′ However, if R[kprep ] = v ̸= ⊥ at τ > τmax then we do not know whether the A A transaction T = (h1A , D) that defined R[kprep ] (and spent Sprep ) was a correct swap transaction, because on one hand, v is computed using a perfectly hiding commitment scheme and contains no information about D. On the other hand, even if swap transactions were certified without the commitment scheme (like minting transactions), then still v = H(ν, x, aux) and x is random. So for v

15

giving any useful information about the correctness of T , we define the following requirements to swap transactions: 1. Swap transactions are certified without the commitment scheme (similar to mint transactions). 2. The fields x and aux in swap transactions must be known constants. We choose these constants to be x = 0ℓ and aux = ⊥. This means that if pkA , h1A , pkB , h1B , τmax are known, then also the value A vswap = H(νswap (pkA , h1A , pkB , h1B , τmax ; ·), 0ℓ , ⊥)

is known. Under these requirements, TokA is correctly transferred from the A preparation state Sprep = (νprep (pkA ; ·), h1A ) to a correct swap state only if A A R[kprep ] = vswap . Therefore, we have the following rollback rule: A A at some point τ ′ > τmax , then A certainly ] ̸= vswap Rollback rule: If R[kprep did not commit in time.

We also need a positive rule to decide that A committed in time. Assume now A A at some point τ ′ ≤ τmax . Does this imply that A has ] = vswap that R[kprep committed in time? The answer turns out to be yes under the assumption that no H-collisions occur in the system and the signature scheme used is existentially unforgeable. This follows from the non-blocking security of the system – only A A A can block the state Sprep with a request Q = (νprep (pkA ; ·), h1A , vswap , u) to US and once A has done it, the corresponding inclusion proof π enables A to A . It may construct a certified transaction that transfers TokA to the state Sswap seem that we are done, but not yet. In practice, we cannot assume that B A A from US in time (i.e., ] = vswap can always obtain the inclusion proof for R[kprep before τmax ) because A may have committed in the last minute, US may not always be accessible promptly, and the clocks of B and US may not be ideally synchronized. A A at ] = vswap So, what can we imply if we only have information that R[kprep ′ some point τ > τmax ? Similarly to the discussion in the last paragraph, we can conclude that if no H-collisions occurred in the system, then a request of A A the form Q = (νprep (pkA ; ·), h1A , vswap , u) was made to US that defines R[kprep ]= A vswap , but we are not sure if it occurred before the timeout τmax . That is why we will define the predicate νprep (pkA ; ·) in such a way that transferring TokA from the state (νprep (pkA ; ·), h1A ) to the corresponding swap state with the ownership predicate νswap (pkA , h1A , pkB , h1B , τmax ; ·) is only possible before timeout τmax . This is also the main reason why we need special preparation states. Now we finally have a proper execution rule: A A Execution rule: If R[kprep ] = vswap at any point, no collisions occurred and the signature scheme is existentially unforgeable, then A committed in time.

Figure 1 depicts the details of the commitment step in the atomic swap protocol, assuming that both parties successfully commit. 16

Figure 1: Computations and message flow of the commit phase.

5.3

Swap-Related Predicates

In this section, we give definitions to the prepare predicate and the swap predicate and prove that their properties are sufficient to guarantee secure atomic swaps. 5.3.1

Swap Preparation Predicate

A special predicate νprep (pk; ·) that is used as an abstract ownership condition for preparing tokens for atomic swaps. Functionally, it is similar to the signature predicate, but has different unlock arguments u = (h, D, σ), where h is a hash value, D is an arbitrary data structure, and σ is a digital signature. The value of the predicate is defined as follows: νprep (pk; τ, m, h, D, σ) = 1 iff: 1. V(pk, m, σ) = 1 2. m = H(h, H(D)) 3. If D = (νswap (pk, h, pk′ , h′ , τmax ; ·), 0ℓ, ⊥) (for some pk′, h′,τmax) then τ ≤ τmax . This definition implies that if T = (h, D) is a swap transaction from the state (νprep (pk; ·), h) to a state with ownership predicate νswap (pk, h, pk′ , h′ , τmax ; ·), then it cannot be certified after the timeout τmax without H-collisions created in the system. If pkA , h1A , pkB , h1B , τmax were the swap parameters agreed by A and B and A TokA is in the state Sprep = (νprep (pkA ; ·), h1A ), then A must commit at τmax (US 1 A A time) the latest, because later the request QA swap = (νprep (pkA ; ·), hA , vswap , uswap ) (Fig. 1) will not be accepted by US.

17

5.3.2

Swap Predicate

A special predicate νswap (pk, h, pk′ , h′ , τmax ; ·) that is used as an abstract ownership condition for tokens committed to swaps. It has unlock arguments u = (v, π, σ), where v is a storage value (of R in US), π is an inclusion proof, and σ is a digital signature. The value of the predicate is defined as follows: νswap (pk, h, pk′ , h′ , τmax ; τ, m, v, π, σ) = 1 iff: ′ ′ 1. finc (H(Sprep ), v, π) = 1 for Sprep = (νprep (pk′ ; ·), h′ ) ′ 2. For vswap = H(νswap (pk′ , h′ , pk, h, τmax ; ·), 0ℓ , ⊥) either (a) or (b): ′ (a) V(pk′ , m, σ) = 1 ∧ v = vswap ′ (b) V(pk, m, σ) = 1 ∧ v ̸= vswap ∧ τmax < τ

The inclusion proof verification function finc (k, v, π) ∈ {0, 1} is evaluated via ? direct check R[k] = v by US and via the verification function V(k, v, π) by users. In general, if time(π) ̸= τ then it is possible that users and US (at τ ) evaluate finc (k, v, π) differently. However, it turns out that in the case of the swap protocol, this difference does not play any role. ′ ′ ′ = (νprep (pk′ ; ·), h′ ), at τ > τmax , where Sprep )] ̸= vswap Lemma 5.1 If R[H(Sprep ′ ′ ′ , = H(νswap (pk , h′ , pk, h, τmax ; ·), 0ℓ , ⊥), and a token was in the state Sprep vswap then the token was not properly committed by its owner in the swap protocol with parameters pk, h, pk′ , h′ , τmax .

Proof. Assume to the contrary that the owner of the token committed prop′ ′ ′ = ), where Dswap = (h′ , Dswap erly. This means that the transaction Tswap ′ ′ ℓ ′ (νswap (pk , h , pk, h, τmax ; ·), 0 , ⊥) was certified at Sprep before τmax . This implies ′ , u′ ) to US before that there was a successful request Q = (νprep (pk′ ; ·), h′ , vswap ′ ′ τmax , but such a request will induce R[H(Sprep )] ← vswap ̸= ⊥ before τmax and ′ ′ at τ > τmax , a contradiction. □ )] = vswap hence, as R is append-only, R[H(Sprep ′ ′ ′ Lemma 5.2 If R[H(Sprep )] = vswap at some point, where Sprep = (νprep (pk′ ; ·), h′ ), ′ ′ ′ ℓ ′ , and vswap = H(νswap (pk , h , pk, h, τmax ; ·), 0 , ⊥), a token was in the state Sprep ′ ′ ′ no H-collisions occur, then a successful request Q = (νprep (pk ; ·), h , vswap , u′ ) to ′ ′ US was made at τ ≤ τmax that certifies the swap transaction Tswap = (h′ , Dswap ), ′ ′ ′ ℓ ′ where Dswap = (νswap (pk , h , pk, h, τmax ; ·), 0 , ⊥) at state Sprep . ′ ′ ′ Proof. If R[H(Sprep )] = vswap , then a successful request π ← US(ν, h, vswap , u) ′ at some point τ was received by US so that H(Sprep ) = H(ν, h) and hence ν = νprep (pk′ ; ·) and h = h′ . The request was successful then u′ is in the form ′ u′ = (h, D, σ), and νprep (pk′ ; τ, H(h′ , vswap ), h, D, σ) = 1. From the definition ′ of νprep (2.), it follows that m = H(h′ , vswap ) = H(h′ , H(D)) which implies ′ ′ ′ vswap = H(D) and hence D = (νswap (pk , h , pk, h, τmax ; ·), 0ℓ , ⊥), which from the definition of νprep (3.) implies τ = time(π) ≤ τmax . As ′ νprep (pk′ ; time(π), H(h′ , vswap ), u′ ) = 1 .

18

′ ′ ′ and V(H(Sprep ), vswap , π) = 1, we conclude that (Tswap , u′ , π) is a certified swap ′ transaction at Sprep . □

If the signature scheme is existentially unforgeable and the private key of pk′ is not compromised, then practically the conclusion of Lemma 5.2 means that the owner of the token committed properly. ′ ′ ′ ′ The conditions A ≡ R[H(Sprep )] = vswap and B ≡ R[H(Sprep )] ̸= vswap ∧ τmax < τ clearly cannot be both true at the same time. Moreover, if B holds at τ , then A can never hold, because the proof of Lemma 5.2 suggests that if A is true at any time, then it must be true also at some τ ′ ≤ τmax , but then, due to the append-only property, A must hold also at τ . Also, at any time τ > τmax , either A or B must be true, because always, either ′ ′ ′ ′ R[H(Sprep )] = vswap or R[H(Sprep )] ̸= vswap . Therefore, the swap predicate νswap correctly implements the requirements of the swap protocol between A and B: 1. If A and B follow the protocol, then the swap happens 2. If A or B (or both) deviate from the protocol, then A and B will get their tokens back

5.4

Detailed Message Flow of the Protocol

In this subsection, we describe the message flow and computations during the swap protocol from the viewpoint of A. Preparation of A: To transfer TokA to the state (νprep (pkA ; ·), h1A ), the party A runs the following protocol that involves communication with US: A ← (νprep (pkA ; ·), 0ℓ , ⊥) 1. A computes: Dprep A A ) ← H(Dprep 2. A computes: vprep A 0 A 3. A computes: Tprep ← (hA , Dprep ) A 0 4. A computes: uA prep ← S(skA , H(hA , vprep )) A 0 A , uA 5. A sends US: Qprep = (νsig (pkA ; ·), hA , vprep prep ) A 6. US computes: τprep ← τ A 7. US computes: ksig ← H(νsig (pkA ; ·), h0A ) A 8. US checks: R[ksig ] = ⊥ A A 9. US checks: νsig (pkA ; τprep , H(h0A , vprep ), uA prep ) = 1 A A A A 10. US obtains: πprep for Qprep . Note that time(πprep ) = τprep A A A 11. US sets: R[ksig ] ← (vprep , uprep ) A 12. US sends A: πprep A A A A A 13. A computes : Cprep ← (Tprep , uA prep , vprep , πprep ) and adds Cprep as a certified transaction to the ledger of TokA .

After these steps, TokA is in the state (νprep (pkA ; ·), h1A ), where h1A = H(h0A , 0ℓ ), and if B proceeds analogously, TokB is in the state (νprep (pkB ; ·), h1B ), where h1B = H(h0B , 0ℓ ). The parties now exchange the full token ledgers, check if the tokens are indeed in correct states, and agree on the timeout value τmax . Party A is now ready for the commitment phase. 19

A Commitment of A: To transfer TokA to (νswap (pkA , h1A , pkB , h1B , τmax ; ·), h2A ), the party A runs the following protocol that involves communication with US: A 1. A computes: Dswap ← (νswap (pkA , h1A , pkB , h1B , τmax ; ·), 0ℓ , ⊥) A A 2. A computes: vswap ← H(Dswap ) A 1 A 3. A computes: Tswap ← (hA , Dswap ) A A 4. A computes: σswap ← S(skA , H(h1A , vswap )) A 1 A A 5. A computes: uswap ← (hA , Dswap , σswap ) 1 A A 6. A sends US: QA swap = (νprep (pkA ; ·), hA , vswap , uswap ) A 7. US computes: τswap ← τ A 8. US computes: kprep ← H(νprep (pkA ; ·), h1A ) A 9. US checks: R[kprep ]=⊥ A A ), uA , H(h1A , vswap 10. US checks: νprep (pkA ; τswap swap ) = 1 A A A 11. US sets: R[kprep ] ← (vswap , uswap ) A A A for QA 12. US obtains: πswap swap . Note that time(πswap ) = τswap A 13. US sends A: πswap A A A A A , uA ← (Tswap 14. A computes : Cswap swap , vswap , πswap ) and adds Cswap as a certified transaction to the ledger of TokA . A 15. A sends B : Cswap

TokA is now in state (νswap (pkA , h1A , pkB , h1B , τmax ; ·), h2A ), where h2A = H(h1A , 0ℓ ). If B did the same then TokB is in state (νswap (pkB , h1B , pkA , h1A , τmax ; ·), h2B ), B B B B where h2B = H(h1B , 0ℓ ) and A receives Cswap = (Tswap , uB swap , vswap , πswap ) from B. A is now ready for successful finalization. B Recovery of A: If A has not received Cswap at τmax , then: B ← (νswap (pkB , h1B , pkA , h1A , τmax ; ·), 0ℓ , ⊥) 1. A computes: Dswap B B ) 2. A computes: vswap ← H(Dswap B 1 B 3. A computes: Tswap ← (hB , Dswap ) B ← H(νprep (pkB ; ·), h1B ) 4. A computes: kprep B ) 5. A sends US : Qprf (kprep ′ 6. US computes : τ ← τ B 7. US computes : v ← R[kprep ] B B 8. US obtains : πprf for v = R[kprep ]. B B B B 9. US sends A : v, πprf . ( time(πprf ) = τ ′ > τmax and V(kprep , v, πprf ) = 1) B

B B B B B If v = (vswap , uB swap ) then A computes C swap = (Tswap , uswap , vswap , πprf ). As B B B B ′ B V(kprep , v, πprf ) = 1 implies that R[kprep ] = (vswap , uB swap ) at τ = time(πprf ), B B B there was a request Q = (ν, hst , vswap , uswap ) such that H(ν, hst ) = kprep = H(νprep (pkB ; ·), h1B ) which implies ν = νprep (pkB ; ·) and hst = h1B if no HB

collisions occur. Therefore, C swap is a certified transaction in (νprep (pkB ; ·), h1B ) and can be used to extend the ledger of TokB (see also Lemma 5.2), and A is now ready for successful finalization.

20

B If v = ⊥ or v = (v ′ , u) where v ′ ̸= vswap then A is ready for unsuccessful finalization (Lemma 5.1).

Successful finalization of A: Party A now controls TokB . The last certified A A A A transaction in the ledger of TokA is Cswap = (Tswap , uA swap , vswap , πswap ). The A inclusion proof πswap is the proof that A have committed TokA . To transfer A TokB from (νswap (pkB , h1B , pkA , h1A , τmax ; ·), h2B ) to (νsig (pkA ; ·), h3A ), the party A runs the following protocol that involves communication with US: A 1. A computes: Dfin ← (νsig (pkA ; ·), 0ℓ , ⊥) A A 2. A computes: vfin ← H(Dfin ) A 2 A 3. A computes: Tfin ← (hB , Dfin ) A A 4. A computes: σfin ← S(skA , H(h2B , vfin )) A A A A 5. A computes: ufin ← (vswap , πswap , σfin ) A A 2 1 1 6. A sends US: QA fin = (νswap (pkB , hB , pkA , hA , τmax ; ·), hB , vfin , ufin ) A 7. US computes: τfin ←τ A 8. US computes: kfin ← H(νswap (pkB , h1B , pkA , h1A , τmax ; ·), h2B ) A 9. US checks: R[kfin ]=⊥ A A ), uA , H(h2B , vfin 10. US checks: νswap (pkB , h1B , pkA , h1A , τmax ; τfin fin ) = 1. A A 11. US sets: R[kfin ] ← (vfin , uA ) fin A A A 12. US obtains: πfin for QA fin . Note that time(πfin ) = τfin A 13. US sends A: πfin A A A A A 14. A computes : Cfin ← (Tfin , uA fin , vfin , πfin ) and adds Cfin as a certified transaction to the ledger of TokB .

TokB is now in the state (νsig (pkA ; ·), h3B ), where h3B = H(h2B , 0ℓ ), which means that A has now full control over TokB . Unsuccessful finalization of A: Party A now controls TokA . The last record B B B , uB = (Tswap in the ledger of TokB is a certified transaction Cswap swap , vswap , π) B B (where π ∈ {πprf , πswap }). In order to transfer the token TokA from the state A (pkA ; ·), h3A ), the party A (νswap (pkA , h1A , pkB , h1B , τmax ; ·), h2A ) to the state (νsig runs the following protocol that involves communication with US: A 1. A computes: Dfin ← (νsig (pkA ; ·), 0ℓ , ⊥) A A 2. A computes: vfin ← H(Dfin ) A A 3. A computes: Tfin ← (h2A , Dfin ) A A 4. A computes: σfin ← S(skA , H(h2A , vfin )) A 5. A computes: uA ← (v, π, σ ) fin fin 1 1 2 A A 6. A sends US: QA fin = (νswap (pkA , hA , pkB , hB , τmax ; ·), hA , vfin , ufin ) A 7. US computes: τfin ←τ A 8. US computes: kfin ← H(νswap (pkA , h1A , pkB , h1B , τmax ; ·), h2A ) A 9. US checks: R[kfin ] = ⊥ A A 10. US checks: νswap (pkA , h1A , pkB , h1B , τmax ; τfin , H(h2A , vfin ), uA fin ) = 1 A A A 11. US sets: R[kfin ] ← (vfin , ufin ) A A A 12. US obtains: πfin for QA fin . Note that time(πfin ) = τfin A 13. US sends A: πfin

21

A A A A A 14. A computes : Cfin ← (Tfin , uA fin , vfin , πfin ) and adds Cfin as a certified transaction to the ledger of TokB .

TokA is now in the state (νsig (pkA ; ·), h3A ), where h3A = H(h2A , 0ℓ ), which means that A has now full control over TokA .

5.5

Atomic Swap with Hashed Timelock and Discussion

Assume that A owns TokA and B owns TokB . Atomic swap protocol can also be designed with the hashed timelock predicate [2, 3, 4] νhtlc (pk, pk′ , y, τmax ; ·) as follows: 1. A generates a random number x, computes y ← H(x) and sends y to B. 2. A and B agree to two timeouts τA and τB , where τA < τB and the difference τB − τA is sufficiently large. A 3. A transfers TokA to the lock state Shtlc = (νhtlc (pkA , pkB , y, τB ; ·), h1A ). In this state, A will be able transfer the token back to herself after τB in case B did not transfer the token before τB . However, B is not yet able to transfer the token because he does not know the pre-image x of y. A 4. B checks that TokA is indeed in the state Shtlc and transfers TokB to the 1 B state Shtlc = (νhtlc (pkB , pkA , y, τA ; ·), hB ). In this state, A is able to transfer TokB to her public key pkA until the timeout τA and for transferring the token, she has to reveal x. 5. A transfers TokB to the state with ownership νsig (pkA ; ·) and reveals x, which is included into the unlocking arguments u = (x, σA ). 6. B checks the status of TokB via US and obtains x as a part of the unlocking arguments. He has now all information but a limited time until τB to transfer TokA to himself. 7. B transfers TokA to the state with ownership νsig (pkB ; ·). This protocol has more steps compared to the symmetric atomic swap described above and, moreover, it involves a risk that if B is late to transfer TokA at step 7 of the protocol (which may happen due to circumstances that B does not control, such as network connection failures), then after τB , party A controls both tokens. The conclusion is that the symmetric atomic swap protocol is better suited for the Unicity framework compared to the hashed timelock protocol, although we do not claim that the symmetric protocol would provide a better alternative to hashed timelock in an inter-blockchain setting where there are no reliable common reference services.

References [1] Buldas, A., Draheim, D., Gault,M., Laanoja, R., Rogojin, V., Truu, A.: The Unicity Execution Layer. A manuscript. May 2026

22

[2] Herlihy, M.: Atomic Cross-Chain Swaps. In PODC ’18: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing pp. 245–254 (2018) https://doi.org/10.1145/3212734.3212736 [3] Atomic cross-chain trading. In Bitcoinwiki (2018) https://en.bitcoin.it/wiki/Atomic_cross-chain_trading

[4] Nolan, T.: Atomic swaps using cut and choose. In Bitcoinwiki (2018) https://bitcointalk.org/index.php?topic=1364951

23

A

Sequence Diagram with Predicates Recipient

Sender

Unicity Service

Prepare ν ′ , aux′ ν ′ , aux′ x ← {0, 1}ℓ D = (ν ′ , x, aux′ ) T = (hst , D) (htx , d) ← Com(H(D)) hT = H(hst , htx ) u such that ν(τexp , hT , u) = 1 Q = (ν, hst , htx , u)

?

ν(τ, hT , u) = 1 ?

R[H(ν, hst )] = ⊥ R[H(ν, hst )] ← htx πinc (with τ ) L ∪ (T, u, htx , d, πinc )

?

T.hst = H(hprev st , xprev ) ?

Open(htx , d) = H(T.D) τ ← time(πinc ) ?

ν(τ, H(hst , htx ), u) = 1 ?

V(H(ν, T.hst ), htx , πinc ) = 1 Accept transaction if all checks pass

Figure 2: One unicity transaction, where the predicate ν represents the current ownership, and the capability to unlock ν ′ defines the new owner. System time τ is extracted from the inclusion proof πinc and used in predicate evaluation by the future verifiers.

24