arXiv CSopen access

The Unicity Execution Layer

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

The Unicity Execution Layer 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 This paper introduces the Unicity Execution Layer, a modular component of the Unicity framework enabling secure off-chain transactions while maintaining trustless double-spending prevention. We present a formal security model where token ownership is represented by public keys and transfers require digital signatures. We prove three fundamental security properties: (1) no double-spending–each token state can be spent at most once, (2) no blocking–only the legitimate owner can prevent a token from being spent, and (3) service-side privacy–the Unicity Service cannot link transactions with the same token. The user-side privacy is addressed by introducing generalized multi-public-key signature schemes that allow one secret to generate multiple unlinkable public keys, and interactive and non-interactive concrete instantiations, enabling private transactions with stable public identity with minimal key management overhead.

1

Introduction

Blockchain technology has revolutionized digital asset management by enabling trustless peer-to-peer transactions without relying on centralized authorities. However, traditional blockchain architectures face fundamental scalability limitations that hinder their adoption for high-throughput applications. The core bottleneck stems from the fact that the “security” depends on the number of participating validators, which all have to participate in consensus on ordering, re-execute transactions, and store every produced block. This paper introduces Unicity, a novel blockchain infrastructure designed to enable secure off-chain transactions while maintaining the trustless guarantees of traditional blockchains. The key insight underlying Unicity is that the vast majority of blockchain operations—transaction execution, smart contract processing, and state transitions—can be moved off-chain, leaving only the essential 1

double-spending prevention mechanism on-chain. This also simplifies on-chain operations, making efficient and self-authenticating implementations possible. By minimizing the data that must be processed by the consensus layer, Unicity achieves linear scalability while preserving the security properties that make blockchains trustworthy. The system consists of three hierarchical layers: the Consensus Layer provides decentralized agreement and cryptoeconomical incentives, the Aggregation Layer maintains a distributed append-only dictionary of spent token states, and the Execution Layer handles peer-to-peer transaction processing and business logic. Our approach differs fundamentally from existing scaling solutions. Rather than optimizing transaction throughput within the constraints of traditional blockchain architectures, Unicity reconceptualizes the shared server-side functionality as a minimal, trustless service which prevents double-spending. This architectural shift enables transactions to occur off-chain and, with hardwarebased unicity-proving functionality, completely offline, while maintaining cryptographic guarantees against fraud. The contributions of this paper include: (1) a formal security model for off-chain transactions with on-chain double-spending prevention, modeled as trusted service in this paper’s scope, (2) cryptographic protocols ensuring transaction privacy and preventing attacks of blocking token spending, and (3) formal proofs of these security properties. Paper Structure After introduction, Sections 4–6 present the core Unicity infrastructure with signature-based token ownership (V(pk, m, σ) = 1), proving three core security properties: no double-spending, no blocking, and service-side privacy (transaction unlinkability). Section 7 addresses user-side privacy through multi-public-key (MPK) signature schemes: a theoretical framework where one secret generates multiple unlinkable public keys, followed by concrete instantiation for ECDSA, and a protocol enabling efficient private transactions with persistent public identity.

2

System Overview

2.1

Motivation

Traditional blockchain architectures, illustrated in Figure 1, require every validator node to process all transactions sequentially. This design creates several fundamental bottlenecks: (1) computational overhead from validating every transaction, (2) storage requirements that grow linearly with transaction history, and (3) bandwidth limitations from broadcasting all transaction data to every node. These constraints result in throughput limitations measured in tens of transactions per second for major blockchain networks, and transaction processing latency (time to finality) which is not suitable for interactive use cases.

2

new block

mempool

Consensus

Validator Validator Validator Thousands ... ... of Validators

tx

Sender

Unicity service RPC Recipient accepts

Sender

Recipient validates

Figure 1: Data flow of a typical blockchain. Figure 2: Data flow of Unicity transactions. Existing scaling approaches attempt to optimize within these architectural constraints. Layer-2 solutions batch transactions but still require periodic settlement on the main chain. Sharding distributes computation, but introduces complex cross-shard communication protocols. Both approaches face fundamental trade-offs between decentralization, security, and scalability. Unicity takes a fundamentally different approach by recognizing that most blockchain operations can be moved off-chain and performed by the party who is naturally interested in the validity of the transaction, the recipient (relying party). The key insight is that central coordination is required only to prevent double-spending—the creation of multiple valid transactions spending the same digital asset. Other functions, including transaction execution, smart contract processing, state updates, and data availability, can be provided by interested parties without global agreement. Figure 2 illustrates the Unicity transaction flow. Rather than broadcasting full transaction data to all network participants, Unicity maintains only a cryptographic commitment to spent asset states. Unicity as a transacting framework provides three essential guarantees: (1) unique spending—a digital asset can be spent no more than once, (2) nonblocking—only the legitimate owner of an asset can mark this asset as spent, and (3) privacy—transaction details remain confidential between participants, hidden from the Unicity Service. By decoupling transaction execution from consensus, Unicity enables new use cases previously impractical on traditional blockchains. Transactions can occur entirely off-chain, requiring no network connectivity at the time of execution. Multiple parties can transact directly using any communication channel, from internet protocols to physical media exchange. The resulting system scales linearly with the number of participants rather than facing the quadratic complexity growth of traditional blockchain networks.

2.2

Architecture

Unicity employs a hierarchical architecture that provides top-to-bottom decentralization and scalability, as illustrated in Figure 3. The three layers serve distinct functions:

3

Consensus Layer

Aggregation Layer

Execution Layer

Figure 3: Layered, hierarchical architecture of the Unicity Network. • Consensus Layer provides decentralized agreement and finality through a combination of Proof-of-Work mining, providing robust decentralization, and BFT consensus with fast and deterministic finality. This layer verifies the integrity of the Aggregation Layer’s state transitions and serves as the root of trust for the entire system. • Aggregation Layer implements the Unicity Service, maintaining a global append-only registry of spent token states. It provides inclusion and noninclusion proofs, processes state certification requests, and with these services allows Execution Layer to avoid the risk of double-spending. The layer is sharded for scalability, clustered for high availability, and uses cryptographic consistency proofs to maintain trustless operation. • Execution Layer handles transaction processing, smart contract execution (implemented through orchestrated execution of programmable stateful spending conditions, called predicates, discussed in a follow-up paper[4]; and business logic. This layer operates off-chain and is managed by users and agents who are interested parties in transaction validation and ordering.

2.3

Unicity Service Protocol

The Unicity execution framework relies on the Unicity Service that maintains a global, append-only registry of spent token states. Each digital token has an associated state hash that uniquely identifies its current ownership and transaction history. When a token owner wishes to transfer ownership, they create a signed transaction that references the current state and specifies the new owner. Protocol Participants entities:

Within this architecture, the protocol involves three

• Token Owners possess digital assets represented as tokens with unique state hashes. Owners sign transactions to transfer ownership and request certification from the Aggregation Layer. 4

• Unicity Service (provided by the Aggregation Layer) maintains a data store, modeled in this paper as key-value store R where keys are derived from public keys and state hashes, and the values are transaction hashes. The service accepts certification requests and provides inclusion proofs for registered transactions. • Recipients are the relying parties who receive token transfers and must verify the authenticity of transactions cryptographically before accepting ownership. Transaction Structure

Each transaction T = (hst , D) consists of:

• hst : the current state hash of the token being transferred • D = (pk′ , x, aux′ ): transaction data containing the recipient’s public key pk′ , a random nonce x, and auxiliary data of the next state aux′ To prevent information leakage, the transaction data D is committed using a perfectly hiding commitment scheme, producing a transaction data hash htx = Comc (H(D)). The sender signs H(hst , htx ) and submits a certification request Q = (pk, hst , htx , σ) to the Unicity Service. Double-Spending Prevention The Unicity Service processes certification requests by checking that (1) the digital signature is valid and (2) the key H(pk, hst ) has not been previously registered. If both conditions hold, the service records the mapping R[H(pk, hst )] ← htx and returns an inclusion proof πinc . This mechanism ensures that each token state can be spent at most once. The transaction flow is illustrated by the sequence diagram (Fig. 4). The formal analysis that follows demonstrates that this construction provides strong security guarantees against both double-spending and blocking attacks while preserving transaction unlinkability.

2.4

State of the Art

Layer 2 rollups are secondary protocols that are intended to solve the scalability and fee issues in base (Layer 1) blockchains. These protocols are run by any party in parallel with the base blockchain without compromising the overall security. Layer 2 networks can process large volumes of transactions off-chain in batches and then communicate a summary digest of the batch to the base layer, which is relatively easy to verify for the base blockchain. This saves the computing power and reduces the fees to be paid in the base blockchain. There are two types of Layer 2 rollups: • Optimistic rollups [5, 6, 7, 8] in which Layer 1 assumes by default that all committed transactions are valid and offer an arbitration protocol for detecting and proving fraudulent transactions later. • Zero-knowledge rollups [9, 10, 11] in which cryptographic computational integrity proof for a batch of transactions is presented to Layer 1. The

5

Recipient

Sender Obtain token

Unicity Service

Generate keypair

Public key pk′

Create transaction T Sign with own sk

Certification request Q Check signature Check not spent Record spent state

Inclusion proof πinc

Certified transaction

Verify signature Verify proof Accept token

Figure 4: Simplified Unicity transaction flow.

proof is easy to verify in Layer 1, but its generation may be a resource consuming computational process. One of the drawbacks of Layer 2 networks is the settlement time (to process and confirm a transaction). Although, rollups mostly offer soft confirmations of transactions in just a few seconds, the true Layer 1 finality can take a few minutes up to a week depending on the network. In the zk-rollups, the proof presented to Layer 1 has to involve the verification of all rules of transaction processing and therefore, the proof generation is resource consuming. RGB smart contracts [12, 13, 14, 15, 16] are a private Layer 2/Layer 3 system for Bitcoin and the Lightning Network. Instead of storing data on the base blockchain, data is processed off-chain, so that the state history of contracts 6

and data are kept off-chain and validated only by users interested in a particular contract (so called client-side validation). Smart contract states are locked to specific Bitcoin UTXOs (Unspent Transaction Outputs) which have to be spent during the next transaction with the asset related to the smart contract. This technique prevents double-spending and is referred to as single-use seals. The key benefits are privacy (as data is held off-chain, it is not possible to access by third parties) and Bitcoin compatibility (users can create their own tokens and rely on Bitcoin’s security and the speed of the Lightening Network without the need to create a new blockchain). A main drawback of RGB smart contracts is that the sender and the receiver must both be online and interact directly while performing a transfer — the receiver generates and shares a UTXO invoice before the asset can be sent securely. Hence, the transfers are not fully asynchronous which may create friction compared to traditional blockchains and hence, implementing decentralized applications remains difficult. Compared to the Unicity framework, RGB lacks a consensus-anchored global non-inclusion oracle and formal exact-security proofs. CoinJoin and Stealth Addresses[22] are techniques for ensuring privacy of blockchain transactions. CoinJoin obscures the link between senders and receivers by combining inputs and outputs into a single transaction, while stealth addresses (invented during the Dark Wallet project around 2013) solve the problem of address reuse. Both methods aim to conceal the chain of ownership history of the same asset in the blockchain. In the Unicity framework, this goal is achieved by design as we will prove in Sec.6. Cryptographic Accumulators [17, 18, 19, 20, 21] aggregate a large set of data into a single, succinct digest and allow verifiers to check if an element belongs to the set using a short proof (or witness). The proof can be verified without revealing other aggregated elements. In the Unicity framework, the Unicity Service uses a cryptographic accumulator without trusted setup currently implemented as a sparse Merkle tree. The main reason is that sparse Merkle trees is the most natural way of aggregating a function (a key-value store) rather than a set. We will show in Sec.5.3.2 that while aggregating just a set prevents double-spending, but is insufficient for other security properties. Other types of accumulators may be considered as a future work.

3

Preliminaries and Notation

3.1

Probabilities

In the paper, we only use finite probability spaces that are defined as pairs (Ω, Pr) so that Ω is a finite set and Pr is a function from the powerset (the set of all subsets) of Ω to the interval [0, 1] of real numbers so that: 1. Pr(Ω) = 1 7

2. Pr(A ∪ B) = Pr(A) + Pr(B) for every A, B ⊆ Ω with A ∩ B = ∅ The set Ω is called sample set and Pr is called probability function. The subsets of Ω are called events. For the probability Pr[{ω}] of a singleton subset, we use the shorthand notation Pr[ω]. By random variable we mean any function X : Ω → R where R is called the range of the random variable. If x ∈ R we use the notation Pr[X = x] = Pr[X −1 (x)], where X −1 (x) = {ω ∈ Ω : X(ω) = x} is the X-preimage of x. As Ω is finite, P we can express the probability Pr(A) of any event A as the sum Pr[A] = ω Pr[w] · [w ∈ A], where [w ∈ A] is the Iverson symbol, i.e. [w ∈ A] ∈ {0, 1} and [w ∈ A] = 1 iff w ∈ A. We also use Iverson symbol in a more general case for any mathematical statements A so that [A] = 1 iff A holds. P For example, Pr[X = x] = ω Pr[w] · [X(w) = x]. Note that [A ∧ B] = [A] · [B] for any two statements A and B. By probability distribution of a random variable X : Ω → R we mean the function DX : R → [0, 1] such that DX (x) = Pr[X = x] for every x ∈ R. If 1 for every x ∈ R, then we say that the DX is a constant, i.e. DX (x) = |R| distribution is uniform. We use the notation X ← R to denote that X is a uniformly distributed random variable with range R and also to say that X is uniformly sampled from R. A random variable X : Ω → R is t-time sampleable if there is a t-time probabilistic Turing machine M with all outputs values in R and every output value x ← M occurs with probability DX (x), i.e. the output distribution of M is DX . If X : Ω → RX and Y : Ω → RY are random variables, x ∈ RX and Py ∈ RY , then we use the notation Pr[X = x, Y = y] = Pr[X −1 (x) ∩ Y −1 (y)] = ω Pr[ω] · [X(ω) = x ∧ Y (ω) = y]. The probability distribution DX,Y : RX × RY → [0, 1] defined by DX,Y (x, y) = Pr[X = x, Y = y] is called the joint distribution of X and Y . We say that X and Y are independent if Pr[X = x, Y = y] = Pr[X = x] · Pr[Y = y] for every x ∈ RX and y ∈ RY . If (Ω1 , Pr1 ) and (Ω2 , Pr2 ) are probability spaces, then their direct product is the probability space (Ω, Pr), such that Ω = Ω1 × Ω2 and Pr[ω1 , ω2 ] = Pr1 [ω1 ] · Pr2 [ω2 ] for every ω1 ∈ Ω1 and ω2 ∈ Ω2 . We will omit the indices of the probability functions when it will not cause confusion.

3.2

Security and Security Proofs

A cryptographic primitive is described as a list of (parametrized) algorithms (finite sequences of atomic commands), correctness conditions (invariants), and attack scenarios. Adversaries are algorithms that participate in the security scenarios (interacting with environment) and break (are successful in the attack scenario of) the primitive with certain success (advantage) ϵ ∈ [0, 1], which often is the probability of a certain logical condition about the attack scenario. If the parameters of a cryptographic primitive are fixed, we get an instance of the primitive.

8

The running time of an adversary is the number of atomic commands the adversary executes during the attack scenario. We assume that the running time includes the code upload time, i.e. the running time is always greater than the size of the algorithm. This assumption is necessary when the primitives are fixed algorithms rather than parametrized families of algorithms like in asymptotic security models, e.g. the polynomial model. In this paper we use the exact security model that more precisely captures the practical use of cryptography where the primitives and adversaries are fixed algorithms. Every instance f of a primitive has security profile which is a function Sf : [0, 1] → N that for every ϵ ∈ [0, 1] returns a lower bound Sf (ϵ) of the running time of an adversary that is able to break the primitive with success at least ϵ. Security profiles are non-decreasing, i.e. Sf (ϵ) ≤ Sf (ϵ′ ) whenever ϵ ≤ ϵ′ . Therefore, every adversary that breaks a primitive f with success ϵ has running time t ≥ Sf (ϵ). Sometimes an instance of a cryptographic primitive g is constructed from instances f1 , . . . , fm of other cryptographic primitives (using programming techniques). A security reduction (or security proof ) is a mathematical proof that the constructed primitive g hash a security profile Sg based on the security profiles Sf1 , . . . , Sfm of f1 , . . . , fm , respectively. Usually, in such a proof, it is assumed that there is an adversary A with running time t that breaks g with success ϵ and then the adversaries A1 , . . . , Am are constructed based on A that break f1 , . . . , fm with (some unknown) successes ϵ1 , . . . , ϵm , respectively, so that inequality ϵ ≤ ϵ1 + . . . + ϵm holds. Mostly, A1 , . . . , Am use A as black-box, i.e. either call or simulate A and add some computational instructions. In this paper, we only have reductions where A is called only once by every Ai i.e. the running times of A1 , . . . , Am are upperbounded by τ1 (t), . . . , τm (t), respectively, where τi is the computational time overhead function for constructing Ai from A. Therefore, we have inequalities: τ1 (t) ≥ Sf1 (ϵ1 ),

τ2 (t) ≥ Sf2 (ϵ2 ),

...

τm (t) ≥ Sfm (ϵm )

−1 (Sfm (ϵm ))}, i.e. that imply t ≥ minϵ1 +...+ϵm =ϵ max{τ1−1 (Sf1 (ϵ1 )), . . . , τm

such

reductions will prove the following security profile Sg of g: Sg (ϵ) =

min

ϵ1 +...+ϵm =ϵ

−1 max{τ1−1 (Sf1 (ϵ1 )), . . . , τm (Sfm (ϵm ))}

(1)

The minimum is necessary because we have to consider the worst distribution of ϵ1 , . . . , ϵm because the only fact we know about ϵi is that they are non-negative and their sum is ϵ. Equation (1) implies a simpler but weaker profile Sg′ : −1 Sg′ (ϵ) = Smin (ϵ/m) = min{τ1−1 (Sf1 (ϵ/m)), . . . , τm (Sfm (ϵ/m))} .

Moreover, if τ (t) = max{τ1 (t), . . . , τm (t)} and Smin (ϵ) = min{Sf1 (ϵ), . . . , Sfm (ϵ)} then we have an even simpler security profile Sg′′ for g defined by: Sg′′ (ϵ) = τ −1 (Smin (ϵ/m)) .

(2)

In the security reductions of this paper, the time overhead function τ is linear, i.e. τ (t) = αt + β, where α and β are reduction-specific constants. 9

3.3

Signature Schemes

A signature scheme is a triple (G, S, V) of algorithms such that: • (pk, sk) ← G generates a public key pk and a private key sk • σ ← S(sk, m) generates a signature on a message m • b ← V(pk, m, σ) verifies a signature on a message (accepts if b = 1) so that for every message m the following verification identity holds: Pr[(pk, sk) ← G : V(pk, m, S(sk, m)) = 1] = 1 . Definition 3.1 (EF-CMA security) A signature scheme (G, S, V) is S-secure against existential forgeries under adaptive chosen message attacks (S-secure EF-CMA) if it has S as a security profile in the following attack scenario: 1. (pk, sk) ← G; 2. (m, σ) ← AS(sk;) (pk); 3. The attack is successful iff V(pk, m, σ) = 1 and A never queries S(sk; m). The success ϵ of A is the probability that the attack is successful.

3.4

One-Way Functions

Let f : X → Y be any function from the range X to a domain Y . Definition 3.2 (one-wayness) A function f is S-secure one-way if it has S as a security profile in the following attack scenario: 1. x ← X, i.e. x is chosen uniformly at random from the domain X; 2. x′ ← A(f (x)); 3. The attack is successful if f (x′ ) = f (x), and the success ϵ of A is the probability that the attack is successful.

3.5

Hash Functions

A hash function family is a pair (G, H) where: • G is a probabilistic algorithm that chooses a parameter par • H is a deterministic algorithm such that for every value of par, the function H = H(par; ·) is of type {0, 1}∗ → {0, 1}k . Definition 3.3 (collision-resistance) A hash function family (G, H) is Ssecure collision-resistant if it has S as a security profile in the following attack scenario: 1. par ← G; 2. (m, m′ ) ← A(par); 3. The attack is successful iff m ̸= m′ and H(par; m) = H(par; m′ ), and the success ϵ of A is the probability that the attack is successful

10

In the following, we assume that the sampling par ← G has been done before any attack scenario, and we often say that the function H = H(par; ·) itself is collision-resistant regardless of the fact that no fixed function can formally be collision-resistant. Definition 3.4 ((k, ℓ)-one-wayness) A function H : {0, 1}∗ → {0, 1}k is Ssecure (k, ℓ)−one-way if it has S as a security profile in the following attack scenario: 1. (h, a) ← A1 ; 2. x ← {0, 1}ℓ ; 3. x′ ← A2 (a; H(h, x)); 4. The attack is successful iff h ∈ {0, 1}k , x′ ∈ {0, 1}ℓ and H(h, x) = H(h, x′ ). The success ϵ of A is the probability that the attack is successful. Equivalently, H is S-secure (k, ℓ)-one-way iff the function fh defined by fh (x) = H(h, x) is S-secure one-way for every h ∈ {0, 1}k .

3.6

Commitment Schemes

A commitment scheme is a triple (Set, Com, Open) of probabilistic algorithms such that: • par ← Set is the setup algorithm that fixes the parameters of the scheme • (c, d) ← Com(par; m) computes commitment c and decommitment string d of a message m • m ← Open(par; c, d) opens the commitment so that for every m, the following correctness identity holds: m = Open(par; Com(par; m)) . We denote by Comc (par, m) the function that computes (c, d) ← Com(par; m) and returns c. We will often omit the parameter par and use the shorthand notations Com(m), Comc (m) and Open(c, d) instead of Com(par; m), Comc (par; m) and Open(par; c, d), respectively. Definition 3.5 (trivial commitment scheme) In the trivial commitment scheme (Set, Com, Open) the functions are defined as follows: • Set always returns ⊥. • Com(m) = (m, ⊥) is the identity function. • Open(c, d) = c just returns the first argument. In terms of security, the commitment schemes are required to be binding and hiding. The Binding property means that once the commitment c is fixed, it is not possible (or very hard) to open it in two different ways. The Hiding property means that the commitment c must not contain efficiently extractable information about the committed message. 11

3.6.1

Binding

Definition 3.6 (binding) A commitment scheme (Set, Com, Open) is S-secure computationally binding if it has S as a security profile in the following attack scenario: 1. par ← Set; 2. c, d, d′ ← A(par); 3. The attack is successful if Open(par; c, d) ̸= Open(par; c, d′ ), and the success ϵ of A is the probability that the attack is successful. This property is called computational binding because it protects against adversaries with limited computational power. There exist commitment schemes that are perfectly binding, which means that opening a commitment in two different ways is impossible by definition. For example, the trivial commitment is perfectly binding, however it is “perfectly non-hiding” because the commitment of m is m itself. 3.6.2

Hiding

Definition 3.7 (perfect hiding) A commitment scheme (Set, Com, Open) is said to be perfectly hiding if for every par and for every two messages m, m′ the commitments c ← Comc (par; m) and c′ ← Comc (par; m′ ) have equal probability distributions as random variables (assuming that the two calls of Com use independent internal random strings). Lemma 3.1 (output independence) If (Set, Com, Open) is a perfectly hiding commitment scheme, m is chosen according to any probability distribution and g is any deterministic function, then m and Comc (g(m)) are independent random variables. Proof. Let ω ← Ω be the internal randomness sampling of Comc . We denote by Comc ω the deterministic version of Comc where the internal random string ω is fixed. Let M denote the sampling space of m. We assume that the sampling µ ← M happens independently of ω ← Ω and hence, the total sampling space is a direct product space with sampling space M × Ω and Pr[µ, ω] = Pr[µ] · Pr[ω] for any values µ, ω. Let m = M (µ, ω) with µ ← M and ω ← Ω, i.e. M is the random variable corresponding to m. Let C be the corresponding random variable of c, i.e. c = C(µ, ω) = Comc ω (g(M (µ, ω))). Note that M (µ, ω) does not depend on ω. We have to show that Pr[M = m, C = c] = Pr[M = m] · Pr[C = c] in this probability space for any possible values m, c of the message and the commit-

12

ment, respectively. Pr[M = m, C = c]

=

X

Pr[µ, ω] · [M (µ, ω) = m] · [C(µ, ω) = c]

µ,ω

=

X

Pr[µ] · Pr[ω] · [M (µ, ω) = m] · [C(µ, ω) = c]

µ,ω

! = =

X

Pr[µ] · [M (µ, ω) = m]

X

·Pr[ω] · [C(µ, ω) = c]

µ

ω

X

Pr[µ] · [M (µ, ω) = m] · Pr[Comc (g(M (µ, ω))) = c]

µ

=

Pr[Comω (g(M (µ, ω))) = c] ·

X

Pr[µ] · [g(M (µ, ω)) = m]

µ

=

Pr[Comc ω (g(M (µ, ω))) = c] · Pr[M = m]

because p = Pr[Comc ω (g(M (µ, ω))) = c] does depend neither on µ due to the perfect hiding property, nor on ω. Moreover: =1

p

=

z }| { X Pr[Comc (g(M (µ, ω))) = c] · Pr[µ′ ]

=

X

µ′ ′

c

Pr[µ ] · Pr[Com (g(M (µ, ω))) = c]

µ′

=

X

Pr[µ′ ] · Pr[Comc (g(M (µ′ , ω))) = c]

µ′

=

X

Pr[µ′ ] ·

µ′

=

X

X

Pr[ω] · [Comc ω (g(M (µ′ , ω))) = c]

ω

Pr[µ , ω] · [Comc ω (g(M (µ′ , ω))) = c] = Pr[C = c] ′

µ′ ,ω

that proves the claim.

3.7

□

Perfectly Hiding Commitments and One-Wayness

Let f be a one way function and (Set, Com, Open) be a perfectly hiding commitment scheme. We will show that f remains hard to invert even if, in addition to the image f (x), the adversary also knows the commitment Comc (x). The following lemma shows that knowing Comc (x) does not help the adversary (much) in inverting a one-way function. Lemma 3.2 If f is Sf -secure one-way and (Set, Com, Open) is a perfectly hiding commitment scheme, then f is Sf′ -secure in the following attack scenario: 1. x ← X; 13

2. x′ ← A(f (x), Comc (x)); 3. The attack is successful if f (x′ ) = f (x); where Sf′ (ϵ) = Sf (ϵ) − tsm − tcom , where tsm and tcom are the running times of the samplings · ← X and · ← Comc (·), respectively.1 Proof. Let f be an S-secure one-way function and A be a t-time adversary that with probability ϵ succeeds in the attack scenario. Consider the following modified scenario with the same adversary: 1. x ← X; 2. x′′ ← X; 3. x′ ← A(f (x), Com(x′′ )); 4. the attack is successful if f (x′ ) = f (x). From Lemma 3.1 it follows that in both input distributions (f (x), Com(x)) and (f (x), Com(x′′ )) the commitments are independent of x and are equally distributed, and hence the joint distributions of (f (x), Com(x)) and (f (x), Com(x′′ )) are equal. It follows that the success probability of A in the second scenario is also equal to ϵ. Let A′ (y) be the adversary that, given y = f (x) as input proceeds as follows: 1. x′′ ← X; 2. c ← Com(x′′ ); 3. return A(y, c). The adversary A′ inverts f with probability ϵ and has a running time t + tsm + tcom . Therefore, t + tsm + tcom ≥ Sf (ϵ) and hence t ≥ Sf (ϵ) − tsm − tcom . □

3.8

Pseudo-random Function Families

Definition 3.8 (PRF) An S-secure pseudo-random function family (PRF) is a function F : K ×X → Y that has S as a security profile in the following attack scenario with a distinguisher D: 1. k ← K 2. Φ ← Y X , i.e. Φ is a randomly chosen function of type X → Y 3. b1 ← DF (k;·) 4. b0 ← DΦ(·) 5. The success of D is ϵ = |Pr[b1 = 1] − Pr[b0 = 1]| The oracle Φ can be simulated by using the so-called lazy sampling technique. The oracle stores a partial function (dictionary) ϕ that is initially nowhere defined (i.e. ϕ[x] = ⊥ for every x ∈ X) and every oracle call Φ(x) is handled as follows: 1. If ϕ[x] ̸= ⊥ then return ϕ[x]. 1 The overhead function is τ (t) = t + t −1 (t) = t − t sm + tcom and its inverse τ sm − tcom .

14

2. If ϕ[x] = ⊥ then: (a) Pick a random y ← Y (b) Define ϕ[x] ← y (c) Return y

4

Unicity Infrastructure

Unicity infrastructure is about maintaining identifiable digital assets called tokens. For example, tokens can represent units of digital currency. Parties can create (issue) tokens, own tokens, and transfer tokens to each other, i.e. the ownership of tokens may change. In order to transfer a token, its owner makes a signed transaction that redefines the ownership. We assume that transferred tokens can be sent using any channels and their storage does not require dedicated hardware devices. At the same time, the infrastructure has to guarantee some properties of the tokens such as unique ownership, i.e. the owner of a token should not be able to transfer the token to two different parties (i.e. double-spend the token), and once a token has been transferred, neither the previous owner nor any third parties should be able to do anything with the token—transfer it or make it unusable for the next owner (i.e. block the token). As nothing prevents copying of digital information, some additional components are needed in the infrastructure to guarantee the desired properties of tokens. For this, the Unicity infrastructure includes the Unicity Service—an online functionality that all parties can communicate with. In this section, we assume that (G, S, V) is a signature scheme and H is a hash function.

4.1

Unicity Service

We first model the Unicity Service as an ideal functionality, and later discuss how to implement such a service in a secure and efficient way. The Unicity Service US is modeled as a state machine with state R, which is a key-value store (dictionary), where both keys and values are of type {0, 1}|k| . Initially, R = ∅. We will write R[k] = ⊥ if there are no pairs (k, v) stored in R. Every input request Q is a tuple (pk, hst , htx , σ), where: • pk of type {0, 1}p is a public key: the public key of the current owner of a token, i.e. the owner before the transaction with the hash htx is executed; • hst of type {0, 1}k is a “state hash”, a value linking subsequent token states; • htx of type {0, 1}k is a transaction data hash (defined later); • σ of type {0, 1}s is a digital signature of the transaction. The request Q = (pk, hst , htx , σ) is processed by US with the state R as follows:

15

1. If R[H(pk, hst )] = ⊥ and V(pk, H(hst , htx ), σ) = 1 then R ← R ∪ {(H(pk, hst ), htx )} , i.e. the new value of R is defined by setting R[H(pk, hst )] ← htx and leaving the rest of the contents of R unchanged. 2. A proof πinc of the statement R[H(pk, hst )] = v (inclusion proof) is returned. It is easy to see that if R0 = ∅ is the initial state, Q1 , Q2 , . . . , Qn is any sequence of queries, and Ri is the state after the request Qi then: • 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] ̸= ⊥.

4.2

Verification Function

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 ′ . (3) • If R[H(pk, hst )] = htx after a request πinc ← US(pk, hst , htx , σ) to the Unicity Service, then V(H(pk, hst ), htx , πinc ) = 1.

4.3

Transactions with a Token

Every token has a state hash hst and an owner A represented by a public key pk. The state hash hst is initialized by the mint transaction of the token (Sec. 4.4). We will call the pair (pk, hst ) the state of the token. Every (unsigned) transaction with the token is a pair T = (hst , D), where: 1. hst is the state hash linking the token ledger, 2. D (transaction data) contains the following fields: • pk′ : the public key of the next owner, • x: a uniformly chosen random string x ← {0, 1}ℓ , • aux′ : other data for the next state. 3. The next state hash hst ′ is computed by hst ′ ← H(hst , x). The pair (pk′ , hst ′ ) defines the next state of the token after executing the transaction T . The main idea of the state is that the transaction T with a token is possible only if its current state (pk, hst ) is not spent, i.e. R[H(pk, hst )] = ⊥. When executed, T spends the state (pk, hst ) by sending a request Q = (pk, hst , htx , σ) to US, i.e. 16

R[H(pk, hst )] = htx ̸= ⊥ after execution and hence, no other transactions in the same state are possible. The next state (pk′ , hst ′ ) should be a non-spent state, i.e. R[H(pk′ , hst ′ )] = ⊥ for the next transactions with the same token being possible. This is guaranteed by the one-wayness and collision-resistance of the hash function H. As x is chosen randomly and is not visible by US and moreover, it is protected by a perfectly hiding commitment scheme, it is not possible for US to associate the current state and the next state of the token. 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 digital signature σ ← S(sk, hT ) is created with the private counterpart sk of pk, i.e. V(pk, hT , σ) = 1. 4. The request Q = (pk, hst , htx , σ) is created. 5. US is called to obtain π ← US(Q). 6. The certified transaction (T, σ, htx , d, π) is formed. Verifying a certified transaction A certified transaction (T, σ, htx , d, π) is verified in the state (pk, h) by the following algorithm: Vcert (T, σ, htx , d, π; pk, 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. V(pk, H(hst , htx ), σ) = 1; 4. V(H(pk, T.hst ), htx , π) = 1. Definition 4.1 (certification in a state) A tuple (T, σ, htx , d, π) is said to be certified in state (pk, h) iff Vcert (T, σ, htx , d, π; pk, h) = 1.

4.4

Mint Transaction

Mint transaction is the first transaction with every token. Mint transaction assigns a unique Token Identifier id and some more application-specific data fields, like a Mint Justification, packed into the auxiliary data aux. Minting uses the following public system-specific constants: • MINT SUFFIX – a fixed domain separator • pkmint – minting public key • skmint – minting private key Note that skmint is also public and is needed only for having a unified interface with US. A certified mint transaction is (T0 , σ0 , π0 ), where T0 = (hst , Dmint ), hst = H(id, MINT SUFFIX) where Dmint contains the following fields: 17

• pk′ : the public key of the first owner; • id: the token identifier; • aux′ : other data of the first state. Certifying a mint transaction T = (hst , Dmint ) involves the following steps: 1. htx ← H(Dmint ) (perfectly hiding commitment is unnecessary for mint) 2. hT ← H(hst , htx ) 3. σ ← S(skmint , hT ), i.e. create a digital signature the private key skmint . 4. Q ← (pkmint , hst , htx , σ), i.e. a request is created. 5. π ← US(Q), i.e. US is called to obtain an inclusion proof. 6. Output (T, σ, π) as a certified mint transaction Verifying a certified mint transaction (T, σ, π) involves the following checks: 1. T.hst = H(T.Dmint .id, MINT SUFFIX) 2. V(pkmint , H(hst , htx ), σ) = 1, where htx = H(T.Dmint ) 3. V(H(pkmint , hst ), htx , π) = 1. Application-specific checks (e.g., validation of the mint authorization based on the enclosed mint justification) follow.

4.5

Token Ledger

A token ledger is a sequence (T0 , σ0 , π0 ; pk0 , h0st ), (T1 , σ1 , htx 1 , d1 , π1 ; pk1 , h1st ), . . . , (Tn , σn , htx n , dn , πn ; pkn , hnst ) where: 1. (T0 , σ0 , π0 ) is a certified mint transaction 2. pk0 = T0 .Dmint .pk′ 3. hst 0 = H(T0 .Dmint .id, MINT SUFFIX) 4. For every index i = 1, . . . , n: 3.3. (Ti , σi , htx i , di , πi ) is a certified transaction in the state (pki−1 , hst i−1 ) 3.1. pki = Ti .D.pk′ 3.2. hist = H(hi−1 st , Ti .D.x)

5

Security

Consider a token with the state S = (pk, hst ). The transfer protocol ensures the following properties: • No blocking: Only the owner of the private key of pk can block the state S = (pk, hst ) if it was not blocked before. • No double-spending: Only one certified transaction can be created in the state S.

18

In this section, we present security proofs for both the no blocking and the no double-spending properties. Security against blocking does not depend on the choice of the commitment scheme and security against double spending assumes computational binding of the commitment scheme. Therefore, both proofs are also valid if the commitment scheme is trivial (i.e. htx = H(D) = H(pk′ , x, aux′ )) because the trivial commitment scheme is perfectly (and hence also computationally) binding. Later when we prove the privacy properties, we have to assume that the commitment scheme is perfectly hiding.

5.1

Security against Blocking

A blocking adversary A uses two oracles: 1. US: the Unicity Service, 2. TS(sk, ·): the transaction signer that, given as input a transaction (h, D) returns (σ, htx , d), where (htx , d) ← Com(H(D)) and σ ← S(sk, H(h, htx )). Blocking scenario involves the following steps: 1. (pk, sk) ← G, i.e. a keypair is generated; 2. hst ← AUS,TS(sk,·) (pk), i.e. A outputs a hash value; 3. A is successful if R[H(pk, hst )] ̸= ⊥ after the scenario and no queries of the form (σ, htx , d) ← TS(sk; 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 = (pk, hst , htx , σ) to US will trivially ensure R[H(pk, hst )] ̸= ⊥, and hence this is excluded by the security condition. Definition 5.1 (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 = (pk′ , h′st , htx , σ) with (pk′ , h′st ) ̸= (pk, hst ) to US enforces R[H(pk, hst )] ̸= ⊥, which means that H(pk, hst ) = H(pk′ , h′st ) and hence, a collision for H was found. b) A request Q = (pk, hst , htx , σ) to US enforces R[H(pk, hst )] ̸= ⊥, which implies V(pk, H(hst , htx ), σ) = 1 from the description of US. Then we have two possibilities: b1) A request (σ ′ , htx ′ , d) ← TS(sk; hst ′ , D) with hst ′ ̸= hst was made such that H(hst ′ , htx ′ ) = H(hst , htx ), which means that a collision for H was found. b2) If no requests (σ ′ , htx ′ , d) ← TS(sk; hst ′ , D) were made with H(hst ′ , htx ′ ) = H(hst , htx ) then this means that A was able to create the signature σ without “help” from the TS(sk; ·) oracle, and hence A was able to create an existential forgery against the signature scheme. 19

Theorem 5.1 If the signature scheme is S-secure EF-CMA and the hash function is S-secure collision-resistant, then the Unicity service is Sblock -secure against t S(ϵ/2) − max{tvergen,tsig }+1 and tgen , tsig , tver are the blocking, where Sblock (ϵ) = max{t ver ,tsig }+1 key generation time, signing time, and signature verification time, respectively. Proof. Let A be a t-time blocking adversary that succeeds with probability ϵ. We construct a collision-finder Acoll and an existential forger Aex as follows: • Acoll proceeds as follows: 1. (pk, sk) ← G. 2. Simulates hst ← AUS,TS(sk;·) (pk) and records all the oracle queries. 3. If AUS,TS(sk;·) (pk) 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: – US-queries: Acoll maintains its own version of R. – TS(sk; ·)-queries: Acoll uses the private key sk. The computational time overhead function for the construction of Acoll is τcoll (t) = (max{tver , tsig }+1)·t+tgen , where tver is the signature verification time (for US-queries), tsig is the signature creation time (for TS(sk; ·)queries), and tgen is the key generation time. S(sk;·) • Aex (pk) proceeds as follows: 1. Simulates hst ← AUS,TS(sk;·) (pk) and records all the oracle queries. 2. If AUS,TS(sk;·) (pk) was successful and b2) occurs and Q = (pk, hst , htx , σ) was the request that enforces R[H(pk, hst )] ̸= ⊥ then: 3. m ← H(hst , htx ). 4. Output (m, σ). The oracles are simulated as follows: – US-queries are simulated so that Acoll maintains its own version of R. – TS(sk; ·)-queries are simulated by using calls to S(sk; ·). As the request Q was accepted by US, we have V(pk, m, σ) = 1. Note that in the case b2) the request S(sk; m) was never made and hence, S(sk;·) Aex (pk) is successful as an existential forger in the EF-CMA scenario. The computational time overhead function for the construction of Aex is τex (t) = (tver + 1) · t + thash , where tver is the signature verification time (for US queries) and thash is the hash computation time (for output). If A succeeds, then either Acoll or Aex succeeds and hence ϵ ≤ ϵcoll +ϵex . Assuming that thash ≤ tgen , the inequality τex (t) ≤ τcoll (t) holds and hence by equation (2) −1 Sblock (ϵ) = τcoll (S(ϵ/2)) =

tgen S(ϵ/2) − max{tver , tsig } + 1 max{tver , tsig } + 1

is a security profile of the Unicity Service against blocking.

20

□

5.2

Security against Double-Spending

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

(4)

Definition 5.2 (Double-spending security) The Unicity Service is said to be S-secure against double-spending if it has S as a security profile in the doublespending scenario. Analysis: If the adversary is successful, then from (4) and the definition of Vcert it follows that T.hst = T ′ .hst = h and: V(H(pk, h), htx ; πinc ) = V(H(pk, h), htx ′ ; πinc ′ ) = 1 , which implies htx = htx ′ by equation (3). From Def. 4.1 it also follows that Open(htx , d) = H(T.D) and Open(htx , d′ ) = Open(htx ′ , 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. Theorem 5.2 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 signature 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, σ, htx , d, πinc ), (T ′ , σ ′ , htx ′ , d′ , πinc ′ ), (pk, 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 signature verification and the number of calls is limited by the running time t of A. • Acom proceeds as follows: 1. Simulate (T, σ, htx , d, πinc ), (T ′ , σ ′ , htx ′ , d′ , πinc ′ ), (pk, h) ← AUS by maintaining its own version of US. 21

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, by equation (2), 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.

5.3

Insecure Modifications of the Unicity Service

5.3.1

State Hash not Signed

□

Consider the following modification of US that, given a request Q = (pk, hst , hT , σ) proceeds as follows: 1. If R[H(pk, hst )] = ⊥ and V(pk, hT , σ) = 1 then R[H(pk, hst )] ← hT . 2. Return a proof π of the statement R[H(pk, hst )] = hT . Assume that a user A owns a token in state (pk, hst ). A malicious user that knows any pair (h, σ) such that V(pk, h, σ) = 1 can now lock A-s token by sending malicious request Q = (pk, hst , h, σ) to US. Other users may indeed know such pairs if they have received tokens from A (and hence, having seen transactions (T, σ) signed by A). Hence, such a US is insecure against blocking. 5.3.2

R as a Set

Consider the following modification of US where R is just a set and a request Q = (pk, hst , htx , σ) is processed as follows: 1. If H(pk, hst ) ̸∈ R and V(pk, H(hst , htx ), σ) = 1 then R ← R ∪ {H(pk, hst )}. 2. Return a proof πinc of the statement H(pk, hst ) ∈ R. The verification function V just ignores the second argument, i.e. V(k, v, π) = 1 holds iff k ∈ R in the current state of US. A user A who owns a token in state (pk, hst ) (such that H(pk, hst ) ̸∈ R) can now proceed as follows: 1. A creates two signed transactions (T1 , σ1 ) and (T2 , σ2 ) with T1 = (hst , D1 ) and T2 = (hst , D2 ) with T1 .D.pk′ ̸= T2 .D.pk′ , i.e. T1 and T2 transfer the same token to two different public keys. 2. Let (htx 1 , d1 ) ← Com(H(D1 )) and (htx 2 , d2 ) ← Com(H(D2 )). 3. A calls πinc ← US(Q), where Q = (pk, hst , htx 1 , σ1 ) and πinc is a proof of the statement H(pk, hst ) ∈ R. After that, H(pk, hst ) ∈ R holds. 22

4. Also, both (T1 , σ1 , htx 1 , d1 , πinc ) and (T2 , σ2 , htx 2 , d2 , πinc ) are certified transactions in (pk, hst ) because, as H(pk, hst ) ∈ R: V(H(pk, hst ), htx 1 , πinc ) = V(H(pk, hst ), htx 2 , πinc ) = 1 . Therefore, such a US is insecure against double-spending.

6

Service Side Privacy

Unicity service US obtains information about the transactions T = (hst , D) with tokens via the queries Q = (pk, hst , htx , σ). We want to ensure that US does not learn too much about the contents and context of transactions, for example, which transaction belongs to which token. Assume that a token is currently in the state (pk, hst ) and the next transaction with the token is T = (hst , D), where D = (pk′ , x, aux′ ). To certify T , the query Q = (pk, hst , htx , σ) is sent to US where htx = Comc (H(D)) and σ = S(sk; H(hst , htx )). Assume that US stores the query Q. In the future, the next transaction T ′ = (hst ′ , D′ ) will be executed with the same token and the query Q′ = (pk′ , hst ′ , htx ′ , σ ′ ) with hst ′ = H(hst , x) will be received by US. We do not want US to be able to associate Q and Q′ as two consecutive transactions with the same token. Such association is possible if US somehow obtains the random x included in the transaction T , because US can then check that H(hst , x) = hst ′ = fhst (x). There are several ways how to find x: • Invert the function fhst (·) = H(hst , ·), i.e. find x′ such that fhst (x′ ) = hst ′ and hope that x′ = x. To prevent that, we may assume that the hash function H is (k, ℓ)-one-way. • Find x based on the commitment htx = Comc (D). To prevent that, we may assume that the commitment scheme is computationally hiding. • Combine both techniques, i.e. invert fhst (x) with additional information about x obtained from htx . To prevent that, we assume that the commitment scheme in use is perfectly hiding. We will give a proof later in this section under some reasonable assumptions. Note that if ℓ is large, then H(hst , x) with x ← {0, 1}ℓ may give very little information about the previous state hash hst . For example, an extreme case is that if ℓ = k and the function H(h, ·) : {0, 1}k → {0, 1}k happens to be one-to-one for every h (which most likely never happens for practical hash functions), then in fact H(hst , x) gives no information on hst because the equation H(h, x) = hst ′ can be (uniquely) solved for every state hash h that US has stored or memorized. In practice, there is no need to choose a very large ℓ as practical security is possible if ℓ is much smaller than k.

6.1

Security against Association

The Association adversary A = (A1 , A2 ) is two-stage. Association scenario involves the following steps: 23

1. (hst , pk′ , aux′ , a) ← A1 . 2. x ← {0, 1}ℓ . 3. hst ′ ← H(hst , x). 4. htx ← Comc (H(pk′ , x, aux′ ))). 5. x′ ← A2 (a; hst ′ , htx ). 6. The attack is successful iff hst ∈ {0, 1}k , x′ ∈ {0, 1}ℓ , and H(hst , x′ ) = hst ′ . The success ϵ of A is the probability that the attack is successful. Definition 6.1 (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 6.1 If the hash function is S-secure (k, ℓ)-one-way 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 , pk′ , aux′ , a) ← A1 . 2. x ← {0, 1}ℓ . 3. hst ′ ← H(hst , x). 4. x′′ ← {0, 1}ℓ . 5. htx ′ ← Comc (H(pk′ , x′′ , aux′ ))). 6. x′ ← A2 (a; hst ′ , htx ′ ). 7. The attack is successful iff hst ∈ {0, 1}k , x′ ∈ {0, 1}ℓ , and H(hst , x′ ) = hst ′ . For any fixed value of L = (hst , pk′ , aux′ , a), due to perfect hiding, commitments htx = Comc (H(pk′ , x, aux′ )) and htx ′ = Comc (H(pk′ , x′′ , aux′ )) have equal probability distributions. Moreover, by Lemma 3.1 (with g(x) = H(pk′ , x, aux′ )), the random variables x and htx = Comc (H(pk′ , x, aux′ )) are independent. Since x′′ and x are independent, the commitment htx ′ = Comc (H(pk′ , x′′ , aux′ )) is independent of both x and hst ′ = H(hst , x). Therefore, the joint distributions of (hst ′ , htx ) and (hst ′ , htx ′ ) 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 , pk′ , aux′ , a) ← A1 ; 2. return (hst , a′ ), where a′ = (pk′ , aux′ , a). • A′2 (a′ ; y) with a′ = (pk′ , aux′ , a) proceeds as follows: 1. x′′ ← {0, 1}ℓ ; 2. htx ′ ← Comc (H(pk′ , x′′ , aux′ ))); 3. x′ ← A2 (a; y, htx ′ ); 4. return x′ .

24

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

6.2

□

Discussion

The security proofs against blocking and double spending are also valid in the case when the commitment scheme is omitted from the construction and the transaction data hash is computed by htx = H(pk′ , x, aux′ ). At the same time, there seem to be no obvious ways of proving that such a simplified scheme is secure against association. Still, it may be a plausible practical assumption that given hst and the next state hash hst ′ = H(hst , x) and htx = H(pk′ , x, aux′ ) it is infeasible to find x′ so that H(hst , x′ ) = hst ′ . At least for example, if H is SHA-256, there seem to be no obvious ways how to do it if x has sufficiently many random bits.

6.3

Next Transaction Timing Privacy

While the Unicity infrastructure prevents the Unicity Service from linking consecutive transactions with the same token, a different privacy issue emerges in direct peer-to-peer transfers. The Privacy Leak Consider a transaction where party A (the sender) transfers a token to party B (the recipient). During this transfer, A possesses the following information: • The recipient’s public key pk′ • The random nonce x ← {0, 1}ℓ used in the transaction data • The current state hash hst of the token From this information, A can compute the next state hash: hst ′ = H(hst , x) . When B subsequently spends the token by executing a transaction, the Unicity Service records the mapping R[H(pk′ , hst ′ )] ← htx ′ for some transaction hash htx ′ . Since the registry R is publicly accessible (anyone can query whether R[k] = ⊥ for any key k), party A can fetch the key H(pk′ , hst ′ ) to detect when B spends the token. This represents a timing privacy leak: although A cannot determine the recipient of B’s subsequent transaction nor the transaction details, A learns the moment when B chooses to spend the token. In contexts where transaction timing correlates with sensitive information (e.g., spending patterns revealing business activities), this leakage may be undesirable.

25

Impact

The practical significance of the leak is limited, as:

• The leak reveals only timing information, not transaction content or recipient identity • It requires the sender to actively and continuously monitor the registry • It applies only to the next direct transfer Nevertheless, we present two mitigation strategies for contexts where even timing privacy is required.

6.4

Solution 1: Timing Obfuscation

The simplest mitigation strategy is for party B to introduce uncertainty about the actual spending moment through a dummy transaction, e.g. to himself. Specifically: • Upon receiving a token, B may probabilistically execute a transaction to themselves • This creates a registry entry R[H(pk′ , hst ′ )] ← htx ′ at a time chosen by B • The token’s state then transitions to (pk′′ , hst ′′ ) where pk′′ = pk′ and hst ′′ = H(hst ′ , x′ ) for a fresh random x′ ← {0, 1}ℓ • Party A may observe the registry update but cannot distinguish whether B has genuinely spent the token or executed a dummy self-transfer By randomizing the decision to make such self-transfers, B can effectively hide the timing of the actual spending transaction. The trade-off is the cost of additional transactions to the Unicity Service and the increased transaction history length.

6.5

Solution 2: Masked Address Protocol

An interactive protocol that prevents A from computing the observable registry key prevents such leak. The recipient B computes a masking key y which blinds the recipient’s identity and provides the randomness needed for the next state hash. There is no need for x from the base protocol. Protocol 1. Recipient generates masked address: Party B samples a random mask y ← {0, 1}ℓ and computes: ′

f ← H(pk′ , y) . pk ′

f to A. 2. Address exchange: B sends pk ′ f , aux′ ) (note: 3. Transaction creation: A creates transaction data D = (pk no x field), computes the commitment (htx , d) ← Com(H(D)), creates signature σ ← S(sk, H(hst , htx )), and obtains inclusion proof πinc ← US(pk, hst , htx , σ). 26

4. Transaction transmission: A sends (T, σ, htx , d, πinc ) to B. Note that y need not be transmitted since B already possesses it. 5. State hash computation: Upon receiving the certified transaction, B computes the next state hash as: hst ′ ← H(hst , y) . 6. Token ledger verification: When B presents the token to a third party or spends it, the ledger entry (T, σ, htx , d, πinc ; pk, hst ) must be verified along with the tuple (pk′ , y) where: ′

f (mask consistency) • H(pk′ , y) = T.D.pk ′ • hst = H(hst , y) (state hash derivation) 7. Spending the token: B spends from state (pk′ , hst ′ ) by creating a new certification request Q′ = (pk′ , hst ′ , htx ′′ , σ ′ ) to the Unicity Service. Security Against Double-Spending The simplified protocol maintains the fundamental double-spending prevention property. We must verify that B cannot create multiple valid next states from a single certified transaction. Theorem 6.2 (No Parallel Registry Entries) If H is S-secure collisionresistant, then recipient B cannot create two distinct valid next states from a single certified transaction. Proof. Assume B receives a certified transaction (T, σ, htx , d, πinc ) in state ′ f = H(pk′ , y) for B’s public key pk′ and mask y. (pk, hst ), where T.D.pk Suppose B attempts to create two distinct next states (pk′ , hst ′1 ) and (pk′ , hst ′2 ) with hst ′1 ̸= hst ′2 . For both states to be valid continuations from the certified transaction, there must exist masks y1 , y2 such that: ′

f = H(pk′ , y2 ) H(pk′ , y1 ) = T.D.pk hst ′1 = H(hst , y1 ) hst ′2 = H(hst , y2 ) From the first equation, if H is collision-resistant, then with overwhelming probability y1 = y2 , which implies hst ′1 = H(hst , y1 ) = H(hst , y2 ) = hst ′2 , contradicting the assumption that hst ′1 ̸= hst ′2 . More formally, if B could create such distinct states, then B could be used to construct a collision-finding adversary Acoll that outputs ((pk′ , y1 ), (pk′ , y2 )) with y1 ̸= y2 but H(pk′ , y1 ) = H(pk′ , y2 ), contradicting the collision-resistance of H. Therefore, the certified transaction from A uniquely determines B’s next state as (pk′ , H(hst , y)) where y is the unique preimage (up to collisions) of ′ f under the function H(pk′ , ·). T.D.pk □

27

Security Against Blocking The masked protocol inherits the blocking resistance of the standard protocol: Theorem 6.3 (No Blocking in Masked Address Protocol) The masked protocol is Sblock -secure against blocking with the same security profile as the standard protocol. Proof. The blocking security analysis from Section 5.1 applies directly. The ′ f , aux′ ) only modification is that transaction data now has the form D = (pk instead of D = (pk′ , x, aux′ ). An adversary attempting to block state (pk′ , hst ′ ) must create a valid certification request Q = (pk′ , hst ′ , htx , σ) where V(pk′ , H(hst ′ , htx ), σ) = 1. This requires either: • Breaking the signature scheme (existential forgery), or • Finding a collision in H to reuse a previous signature Neither attack is facilitated by the removal of x from the transaction structure. The security reduction proceeds identically to Theorem 1 in Section 5.1. □ Timing Privacy vacy:

The masked protocol provides next transaction timing pri-

Theorem 6.4 (Timing Privacy in Masked Address Protocol) If H is (k, ℓ)one-way, party A cannot feasibly determine when party B spends the token. Proof. For A to monitor when B spends the token, A must compute the registry key k ′ = H(pk′ , hst ′ ) that will be set upon B’s certification request. This requires computing hst ′ = H(hst , y). ′ f = H(pk′ , y) but not y. To compute hst ′ , A must: Party A knows hst and pk ′

f and pk′ (which may not be known to A), or 1. Extract y from pk 2. Guess y and verify the guess by checking if H(hst , y) matches some observed registry entry Option (1) requires inverting H(pk′ , ·), contradicting the one-wayness of H. ′ f (again by one-wayness) Option (2) fails because A cannot determine pk′ from pk and thus cannot construct the registry key H(pk′ , H(hst , y)) to verify any guess. □ Implementation Considerations The masked protocol requires B to reliably store the mask y along with the private key sk′ and state hash hst ′ until making the next transaction. Loss of y renders the token unspendable, as B cannot prove that hst ′ = H(hst , y) is the legitimate next state derived from the previous owner’s certified transaction.

28

6.6

Solution 3: Non-Interactive Masked Protocol

The interactive masked protocol requires the recipient to generate and com′ f = H(pk′ , y) before the sender can construct the transaction. We municate pk now present a non-interactive variant that eliminates this communication round while preserving all security properties. 6.6.1

Mask Derivation via Verifiable Random Function

We observe that a Verifiable Random Function (VRF) allows the holder of a private key to produce a unique, verifiable pseudorandom value derived from an input. This property enables verifiable, deterministic mask derivation without revealing the private key. VRF Construction The recipient B computes a VRF proof and output on the incoming state hash: (y, π) ← VRF.Prove(sk′ , hst ) The value y serves as the mask. As the VRF has the uniqueness property, y is uniquely determined by (sk′ , hst ). Complete Protocol

Transaction A → B:

1. Transaction data: D = (pk′ , aux′ ) 2. Commitment: (htx , d) ← Com(H(D)) 3. Signature: σ ← S(sk, H(hst , htx )) 4. Request to US: Q = (pk, hst , htx , σ) 5. Obtain inclusion proof πinc 6. Send to B: (T, σ, htx , d, πinc ) where T = (hst , D) B computes next state: 1. VRF computation: (y, π) ← VRF.Prove(sk′ , hst ) 2. Next state hash: hst ′ ← H(hst , y) Transaction B → C: 1. Transaction data: D′ = (pk′′ , aux′′ ) 2. Commitment: (htx ′ , d′ ) ← Com(H(D′ )) 3. Signature: σ ′ ← S(sk′ , H(hst ′ , htx ′ )) 4. Request to US: Q′ = (pk′ , hst ′ , htx ′ , σ ′ ) 5. Obtain inclusion proof πinc ′ 6. Send to C: (T ′ , σ ′ , htx ′ , d′ , πinc ′ ; π) along with ledger L

29

Recipient C’s Verification ture σbind , and ledger L:

Given the certified transaction, binding signa-

1. Verify VRF: ?

VRF.Verify(pk′ , hst , y, π) = 1 where y is the claimed mask provided (or derived from π). 2. Verify state hash derivation: ?

hst ′ = H(hst , y) 3. Verify certified transaction: ?

Vcert (T ′ , σ ′ , htx ′ , d′ , πinc ′ ; pk′ , hst ′ ) = 1 4. Verify ledger: Recursively verify all previous transactions in L Security Analysis Theorem 6.5 (No Double-Spending) If the signature scheme is deterministic and unforgeable, recipient B cannot create two distinct valid next states from a single certified transaction. Proof. Given a certified transaction in state (pk, hst ) transferring to pk′ , the VRF output y is uniquely determined by hst and the private key sk′ corresponding to pk′ . For a secure VRF, there exists exactly one valid output y for input hst and key sk′ . Therefore hst ′ = H(hst , y) is unique. To produce a different valid state hst ′′ ̸= hst ′ , party B would need to produce a valid proof π ′ for a different output y ′ , which contradicts the uniqueness property of the VRF. □ Theorem 6.6 (Timing Privacy) If the VRF is pseudorandom, party A cannot determine when B spends the token. Proof. To compute the registry key H(pk′ , hst ′ ) that US will record when B spends, party A must compute hst ′ = H(hst , y) where y is the VRF output. Party A knows pk′ and hst . However, computing y requires sk′ . Since A does not possess sk′ , predicting y contradicts the pseudorandomness property of the VRF. □ Theorem 6.7 (Service-Side Privacy) The Unicity Service cannot link consecutive token states. Proof. The service US observes requests Q = (pk, hst , htx , σ) and Q′ = (pk , hst ′ , htx ′ , σ ′ ). To link these as consecutive states of the same token, US must verify that hst ′ = H(hst , y) for some valid y. Computing the VRF output y requires sk′ . The service knows hst but not ′ sk , and therefore cannot compute y. Without y, the service cannot verify any relationship between hst and hst ′ due to the preimage resistance of H and pseudorandomness of y. □ ′

30

Implementation Considerations This protocol requires a VRF. A practical instantiation of a VRF is a Unique Signature Scheme, where for every valid key pair (pk, sk) and message m, there exists exactly one signature σ such that V(pk, m, σ) = 1. In this case: 1. VRF.Prove(sk, m) outputs π = σ = Sign(sk, m) and y = H(σ). ?

?

2. VRF.Verify(pk, m, y, π) checks V(pk, m, π) = 1 and y = H(π). Recommended instantiations include: • BLS Signatures (Boneh-Lynn-Shacham): BLS signatures are inherently unique. • RSA-FDH (Full Domain Hash): RSA signatures with a full-domain hash are unique. • Specially designed VRF like EC-VRF (RFC 9381). Note that deterministic signature shemes like EdDSA and Schnorr are not unique signature schemes as-is and thus are unsafe for this protocol.

6.7

Combined Protocol with Unlinkable Keys

We now present the complete protocol combining unlinkable transaction keys and persistent recipient identities (Section ??) with the binding signature mechanism (Section 6.6) for verifiable mask derivation. 6.7.1

Key Derivation

For a recipient with persistent keypair (d, P = [d]G) and sender-chosen ephemeral value r ∈ Zq : 1. Sender computes ephemeral point: R ← [r]G 2. Sender computes shared secret: S ← [r]P 3. Blinding factor: s ← Hkey (S, R, hst ) 4. Transaction public key: Ptx ← P + [s]G 5. Recipient computes same shared secret: S = [d]R 6. Recipient derives private key: dtx ← d + s mod q Note that [dtx ]G = [d + s]G = [d]G + [s]G = P + [s]G = Ptx , so the derived keys are consistent. 6.7.2

Transaction Protocol

Transaction A → B Party A holds a token in state (PA , hst ) (note the ECDSA specific notation, instead of pkA we write PA ) and transfers to party B with persistent public key PB . 1. Key derivation: 31

• A samples r ← Zq and computes R ← [r]G • A computes shared secret S ← [r]PB • A computes blinding factor s ← Hkey (S, R, hst ) • A computes transaction key Ptx ← PB + [s]G 2. Transaction data: D = (Ptx , R, aux′ ) 3. Commitment: (htx , d) ← Com(H(D)) 4. Signature: σ ← S(dA , H(hst , htx )) 5. Certification: Q = (PA , hst , htx , σ), obtain πinc ← US(Q) 6. Send to B: (T, σ, htx , d, πinc ) where T = (hst , D) B Processes Incoming Transaction 1. Validate ephemeral point: Verify R ̸= O (point at infinity) 2. Derive keys: • Compute shared secret S ← [dB ]R • Compute blinding factor s ← Hkey (S, R, hst ) • Verify PB + [s]G = Ptx (from transaction data) • Compute transaction private key dtx ← dB + s mod q 3. VRF computation: (y, π) ← VRF.Prove(dtx , hst ) 4. Next state: hst ′ ← H(hst , y) 5. Store: (dtx , hst ′ , π) for spending Transaction B → C public key PC .

Party B spends the token to party C with persistent

1. Key derivation for C: • B samples r′ ← Zq and computes R′ ← [r′ ]G • B computes S ′ ← [r′ ]PC • B computes s′ ← Hkey (S ′ , R′ , hst ′ ) • B computes Ptx′ ← PC + [s′ ]G 2. Transaction data: D′ = (Ptx′ , R′ , aux′′ ) 3. Commitment: (htx ′ , d′ ) ← Com(H(D′ )) 4. Signature: σ ′ ← S(dtx , H(hst ′ , htx ′ )) 5. Certification: Q′ = (Ptx , hst ′ , htx ′ , σ ′ ), obtain πinc ′ ← US(Q′ ) 6. Send to C: (T ′ , σ ′ , htx ′ , d′ , πinc ′ ; π) along with ledger L 6.7.3

Transaction Verification

Given the certified transaction, binding signature σbind , and ledger L: 1. Verify VRF: ?

VRF.Verify(Ptx , hstprev , y, π) = 1 where Ptx is the transaction public key from the previous transaction’s data. 32

2. Verify state hash derivation: ?

hst ′ = H(hstprev , y) 3. Verify certified transaction: ?

Vcert (T ′ , σ ′ , htx ′ , d′ , πinc ′ ; Ptx , hst ′ ) = 1 4. Verify ledger: Recursively verify all previous transactions in L

33

7

User Side Privacy

In the previous sections, there is the assumption that the recipient generates a fresh keypair for every transaction. This may be impractical in some applications, especially where the recipient’s secure storage is limited. We present two solutions that allow for the generation of unlinkable public keys while maintaining only a single persistent private key. As a requirement, we avoid the persistent state on the client side that must be retained between transactions.

7.1

A General Solution using Pseudo-Random Functions

In this subsection, we define multi public key (MPK) signature schemes where a user has a single private key but many public keys, each capable of verifying signatures created with the same private key. This is achieved by separating key generation into two phases: 1. Private key generation. 2. Public key generation that depends on a user-chosen index ι. MPK signature schemes have to satisfy two security properties: 1. Existential unforgeability, which is similar to the standard EF-CMA condition for the ordinary signature schemes. 2. Unlinkability of keys, i.e. the one-time public keys and the signatures verifiable with one-time keys contain no useful information about whether they correspond to the same private key or not. We will show that a wide class of generic signature schemes S = (G, S, V ) can be transformed to MPK signature schemes SF by using a pseudo random function family F . This wide class contains, for example all Schnorr type signature schemes (like EdDSA) and DSA type signature schemes like ECDSA (used in Bitcoin). In principle, such a transformation also applies to RSA but is much less efficient. We will prove that whenever a generic scheme is EF-CMA secure and F is a secure pseudo-random function family, then the MPK signature scheme SF is both existentially unforgeable and unlinkable. 7.1.1

Definition and Motivation

Definition 7.1 (MPK signature scheme) A multi public key (MPK) signature scheme is a tuple (Gs , Gp , S, V ) such that: • k ← Gs generates the private key • Xι ← Gp (k, ι) generates a (one-time) public key for an index ι • σ ← S(k; ι, m) creates a signature for a message m • V (X, m, σ) verifies a signature σ on a message m with public key X

34

so that the following verification identity holds for every key k, for every message m, and for every index ι: V (Gp (k, ι), m, S(k; ι, m)) = 1 . MPK signature schemes may be used in payment scenarios, where a payee has the private key k of a MPK signature scheme (Gs , Gp , S, V ): 1. The payee first sends an invoice to the payer, where the invoice contains the index ι as a reference number as well as the specific public key Xι = Gp (k, ι). The reference number may depend on the goods or services for which the invoice was sent. 2. The payer forms a transaction T that among the other necessary information contains the reference number ι, signs the transaction with a signature σ, and sends the signed transaction (T, σ) to the payment system (e.g. Bitcoin blockchain). 3. The payee may then check that the signed transaction (T, σ) was received by the payment system (for example, is in a sufficiently old Bitcoin block) and that T.Xι = Gp (k, T.ι). By the explicit reference number T.ι, the payee is also able to check for which goods or services the incoming payment was made. If the MPK signature scheme is unlinkable, it is not later possible to determine whether any two signed payment transactions (T, σ), (T ′ , σ ′ ) are associated with the same payee or the same payer. 7.1.2

Security Definitions

For the existential unforgeability, we use a formal security condition that is similar to the standard EF-CMA, but where the adversary can itself initiate public key generation and choose the corresponding indices ι arbitrarily by itself. The attack scenario involves an oracle OkS̃ that holds a secret key k, has a set I (which is initially empty) as its state, and answers two types of queries: • OkS̃ (gen; ι) – a key generation query that is answered as follows. If ι ∈ I the oracle returns ⊥ (the index was already used). Otherwise, the oracle sets I ← I ∪ {ι} (marks ι as ”used”) and returns Xι = Gp (k, ι). • OkS̃ (sig; ι, m) – a signing query that is answered as follows. If ι ̸∈ I the oracle returns ⊥ (the key Xι is not yet generated). Otherwise, the oracle returns σ = S(k; ι, m). Definition 7.2 (EF-CKMA) A MPK signature scheme S̃ = (Gs , Gp , S, V ) is s-secure against existential forgeries under chosen key-message attack (EFCKMA) if it has s as a security profile s in the following attack scenario: 1. k ← Gs S̃ 2. (X, ι, m, σ) ← AOk 3. The attack is successful iff: 35

(a) V (X; m, σ) = 1 (b) The query X ← OkS̃ (gen; ι) was made by A (c) The query OkS̃ (sig; ι, m) was never made by A The success ϵ of A is the probability that A is successful. For defining the unlinkability, we introduce an additional oracle OS̃ that is similar to the first oracle, but handles queries as follows: • OS̃ (gen; ι) – a key generation query that is answered as follows. If ι ∈ I, the oracle returns ⊥ (the index was already used). Otherwise, the oracle sets I ← I ∪ {ι} (marks ι as ”used”), generates kι ← Gs , saves kι , and returns Xι = Gp (kι , ι). • OS̃ (sig; ι, m) – a signing query that is answered as follows. If ι ̸∈ I the oracle returns ⊥ (the key Xι is not yet generated). Otherwise, the oracle returns σ = S(kι ; ι, m). Definition 7.3 (Unlikability) A MPK signature scheme S̃ = (Gs , Gp , S, V ) is s-secure unlinkable if it has s as a security profile in the following scenario: 1. k ← Gs S̃ 2. b1 ← DOk S̃ 3. b0 ← DO 4. The success of D is ϵ = |Pr[b1 = 1] − Pr[b0 = 1]|. The idea of the security condition is that a distinguisher D cannot make difference whether the secret key is the same k for all key-generation queries (the oracle OkS̃ ) or is generated independently for every (adversary-chosen) index (the oracle OS̃ ). The oracles are defined so that the queries OkS̃ (gen; ι) cannot be made twice, i.e. ⊥ is returned for a repeated query. This restriction is essential because otherwise D can easily distinguish the oracles: OkS̃ (gen; ι) will always be the same, but the public keys generated by calling OS̃ (gen; ι) twice can be different. 7.1.3

EF-CKMA for Ordinary Signature Schemes

Before defining a general construction of MPK signature schemes from ordinary ones, we need to define EF-CKMA security for ordinary signature schemes. For that, we define an additional oracle OS that handles the queries as follows: • OS (gen; ι) – a key generation query that is answered as follows. If ι ∈ I, the oracle returns ⊥ (the index was already used). Otherwise, the oracle sets I ← I ∪ {ι} (marks ι as ”used”), generates (xι , Xι ) ← G, saves xι , and returns Xι . • OS (sig; ι, m) – a signing query that is answered as follows. If ι ̸∈ I the oracle returns ⊥ (the key Xι is not yet generated). Otherwise, the oracle returns σ = S(xι ; m). 36

Definition 7.4 (EF-CKMA for ordinary signatures) A signature scheme S = (G, S, V ) is s-secure EF-CKMA if it has s as a security profile in the following attack scenario: S

1. (X, ι, m, σ) ← AO 2. The attack is successful iff: (a) V (X; m, σ) = 1 (b) The query X ← OS (gen; ι) was made by A. (c) The query OS (sig; ι, m) was never made by A. EF-CKMA differs from traditional EF-CMA because the adversary is able to initiate the use of new keys and may create an existential forgery with any of the keys. The indices are used just for labeling the generated keys. It turns out that EF-CKMA is not a conceptually stronger notion of security because any EF-CMA signature scheme is also EF-CKMA, though with some security loss. Theorem 7.1 (EF-CMA implies EF-CKMA) Every signature scheme S = (G, S, V ) that is s-secure EF-CMA is s′ -secure EF-CKMA, where s′ is a function for which the implication τ (t) ≥ s(ϵ/t) ⇒ t ≥ s′ (ϵ) holds for every t and τ is defined by τ (t) = (1 + max{tgen , tsig }) · t + tsm . Proof. Given a t-time adversary A that has success ϵ in the EF-CKMA scenario, we construct an EF-CMA adversary B that has success ϵ/t and running time τ (t), which means that τ (t) ≥ s(ϵ/t). The adversary B S(x;·) (X) (where (x, X) is a private-public key pair) proceeds as follows: 1. Generates a random number t0 ← {1, . . . , t} S 2. Simulates (ι, X, m, σ) ← AO by answering the OS -queries as follows: • OS (gen; ι) – if this is the t0 -th query, set ι0 ← ι and return X. Otherwise, compute (Xι , xι ) ← G and return Xι . • OS (sig; ι, m) – If ι0 is defined and ι = ι0 , then query the oracle σ ← S(x; m) and return σ. Otherwise, if xι is not defined, return ⊥; and if xι is defined, compute σ ← S(xι ; m) and return σ. 3. Returns (m, σ). S

With probability ϵ/t the adversary (ι, X, m, σ) ← AO succeeds in the simulation so that ι = ι0 which means that B S(x;·) (X) succeeds with the same probability in the EF-CMA game. The computational overhead function can be chosen to be τ (t) = (1 + max{tgen , tsig }) · t + tsm . □ To illustrate the security loss, assume that s(ϵ) = scma · ϵ is a linear function. From τ (t) ≥ s(ϵ/t) it follows that: (tsm + max{tgen , tsig }) · t ≥ (1 + max{tgen , tsig }) · t + tsm ≥ scma · ϵ/t

37

Hence, t ≥

q

scma ·ϵ tsm +max{tgen ,tsig } and hence it is sufficient to take

s s′ (ϵ) = 7.1.4

s(ϵ) . tsm + max{tgen , tsig }

Generic Construction and Security Proofs

In this section, we define a wide class of MPK-friendly signature schemes that can be transformed into MPK signature schemes. Definition 7.5 (MPK-friendly signature scheme) A signature scheme is MPK-friendly if the key-generation function G is in the form: 1. x ← X 2. X ← f (x) 3. Output (X, x) where f is a deterministic function. For example, ECDSA and EdDSA are MPK-friendly, because their keys are generated by the rule: x ← Zq , X = xg, where g is a generator of a cyclic group G with order q, i.e. in that case, X = Zq and f : Zq → G is defined by f (x) = xg. Definition 7.6 (Transformed scheme) Let S = (G, S, V ) be a MPK-friendly signature scheme, and F : K × I → X be a pseudo-random function family. The transformed scheme SF = (Gs , Gp , S ′ , V ) is defined as follows: • Gs outputs a uniformly random k ← K • Gp (k, ι) = f (Fk (ι)) for every k ∈ K and ι ∈ I • S ′ (k; ι, m) = S(Fk (ι); m) for every k ∈ K, ι ∈ I, and for every message m It is easy to see that the transformed scheme is a MPK signature scheme. Note also that in the scenario k ← K, xι ← Fk (ι), Xι ← Gp (ι, xι ) the distribution of (Xι , xι ) is the same as in the scenario (Xι , xι ) ← G. Theorem 7.2 If S = (G, S, V ) is a MPK-friendly signature scheme and F is an s-secure PRF, then the transformed scheme S̃ = SF = (Gs , Gp , S ′ , V ) is s(ϵ) s′ -secure unlinkable, where s′ (ϵ) = 1+max{t . gen ,tsig }) Proof. Let D be a t-time distinguisher that has success ϵ in the unlinkability scenario. We construct a distinguisher D for F as follows. Given access to an oracle φ(·) the distinguisher Dφ(·) proceeds as follows: φ

1. Simulates b ← DO , where the oracle calls are simulated as follows: • Oφ (gen; ι) – If ι ∈ I then return ⊥. Otherwise, set I ← I ∪ {ι} and return f (φ(ι)) 38

• Oφ (sig; ι, m) – If ι ̸∈ I then return ⊥. Otherwise, return S(φ(ι); m) 2. Returns b If φ(·) = Fk (·), then the oracle Oφ is equivalent to OkS̃ , because then: • Oφ (gen; ι) = OkS̃ (gen; ι) as f (φ(ι)) = f (Fk (ι)) = Gp (k, ι), and • Oφ (sig; ι, m) = OkS̃ (sig; ι, m) due to S(φ(ι); m) = S(Fk (ι); m) = S ′ (k; ι, m) If φ(·) = Φ(·), then the oracle Oφ is equivalent to OS̃ , because then: • Oφ (gen; ι) = OS̃ (gen; ι) because due to lazy sampling technique, computing f (φ(ι)) = f (Φ(ι)) is equivalent to kι ← K ≡ kι ← Gs and returning Xι = Gp (kι , ι) • Oφ (sig; ι, m) = OkS̃ (sig; ι, m) due to S(φ(ι); m) = S(Φ(ι); m) = S ′ (kι ; ι, m) in case kι was a saved value during lazy sampling and hence Φ(ι) = kι . Therefore, the unlinkability scenario with D is equivalent to the PRF scenario with D and hence, the success of D in the PRF-scenario is ϵ. As the computational time overhead function is τ (t) = (1 + max{tgen , tsig }) · t, the statement of the theorem follows. □ Theorem 7.3 If S = (G, S, V ) is a MPK-friendly signature scheme that is s-secure EF-CKMA and its transformed scheme S̃ = SF = (Gs , Gp , S ′ , V ) is s-secure unlinkable, then S̃ is s′ -secure EF-CKMA, where s′ (ϵ) = s(ϵ/2). Proof. Let AO be a t-time oracle adversary that succeeds with probability ϵ in the EF-CKMA scenario. We construct a distinguisher DO for unlinkability and an EF-CKMA adversary AO ckma for S as follows: • DO simulates (X, ι, m, σ) ← AO and returns 1 iff A is successful. O • AO ckma also simulates (X, ι, m, σ) ← A and returns (X, ι, m, σ). In the EF-CKMA scenario, k ← K ≡ k ← Gs is picked uniformly at random S̃ and (X, ι, m, σ) ← AOk produces existential forgery with probability ϵ. Hence, S̃ S̃ Pr[1 ← DOk ] = ϵ. Let ϵ′ be the probability that (X, ι, m, σ) ← AO produces S̃ existential forgery. Hence, Pr[1 ← DO ] = ϵ′ and the success of D in the unlinkability scenario is ϵunl = |ϵ − ϵ′ |. Note also that the oracles OS̃ (from Def. 7.3) and OS (from Def. 7.4) are equivalent because: • OS̃ (gen; ι) = OS (gen; ι) as the scenario [kι ← Gs , Xι ← Gp (kι ), Return Xι ] is equivalent to the scenario [(xι , Xι ) ← G, Return Xι ]. • OS̃ (sig; ι, m) = OS (sig; ι, m) as S ′ (kι ; ι, m) = S(Fkι (ι); m) = S(xι ; m). S

′ Hence, AO ckma succeeds in the EF-CKMA scenario with probability ϵckma = ϵ . Therefore, ϵ ≤ ϵunl + ϵkcma . As the construction of D and Ackma involves no computational time overhead, we conclude that S̃ is s′ -secure EF-CKMA with s′ (ϵ) = s(ϵ/2). □

39

7.1.5

Remarks on Practical Implementation

The main tool in the construction is the pseudo-random function family F and hence the security of the scheme directly depends on the security of F as a PRF. For the ECDSA and EdDSA with groups the order q of which is much less than 2512 we may apply the HMAC construction [2] as follows: Fk (ι) = Int(HMACsha512 (k; ι))

mod q

where Int : {0, 1}512 → Z2512 converts bitstrings to non-negative integers, k ← K = {0, 1}m , and ι ∈ I = {0, 1}64 . If q ≪ 2512 , then the output distribution of Fk (·) is almost as indistinguishable from the uniform distribution Uq on Zq as the output distribution of HMACsha512 (k; ·) from the uniform distribution U2512 on {0, 1}512 because the statistical distance between Uq and the distribution q Int(U2512 ) mod q has an upper bound 2513 . In [1], Bellare proved that HMAC is a PRF if the compression function (of the hash function) is a PRF, which is a good practical security guarantee since no efficient attacks are known against the PRF-security of the compression function.

7.2

A Solution for ECDSA

Unlike the rest of the paper which is not signature scheme specific, we are assuming the ECDSA signature scheme[3] in the following subsections, and use the ECDSA, DH specific notation. 7.2.1

Interactive Protocol

The recipient holds a persistent keypair (d, P ) where P = d·G with generator G and order n. For each transaction, the recipient generates an ephemeral blinding factor r ← Zn and derives a transaction-specific public key P ′ = (d + r) · G. The protocol is shown in Figure 5. The recipient maintains only the persistent secret d and derives ephemeral signing keys deterministically from data field R, included with the transaction. When spending the token, the recipient reconstructs the blinding factor r′ = H(d || R) and derives the private key d′ = d + r′ mod n corresponding to P ′ . 7.2.2

Non-Interactive Protocol

For applications requiring persistent public keys as “addresses”, or non-interactive operation, the parties can create the blinded public key using Diffie-Hellman key exchange. The recipient publishes a persistent public key P = d · G. The protocol is shown in Figure 6. The key challenge in non-interactive protocols is protecting against malicious senders who might choose predictable ephemeral keys r or leak them to compromise transaction unlinkability. The secure construction addresses this by binding the blinding factor to both the shared Diffie-Hellman secret and public transaction data. 40

Setup: Recipient holds persistent keypair (d, P ) where P = d · G Sender

Recipient $

r ← Zn Ptx ← (d + r) · G R←r·G (Ptx ,R)

←−−−−−−−−−−−−−−− tx ← {Ptx , R, . . .} tx

−−−−−−−−−−−−−−−−→ r′ ← H(d || R) dtx ← d + r′ mod n σ ← Sign(dtx ; txnext ) Figure 5: Interactive protocol for generating unlinkable ECDSA public keys. The sender generates an ephemeral keypair (r, R = r · G) and computes a Diffie-Hellman shared secret r · P . The blinding factor s is derived by hashing the shared secret together with the ephemeral public key R and the previous transaction identifier txprev : s = H1 (r · P || R || txprev ) The transaction-specific public key is computed as Ptx = P + s · G, and both Ptx and R are included in the transaction. Upon receiving the transaction, the recipient: 1. Verifies that R ̸= O (the point at infinity) to prevent trivial attacks 2. Computes the same shared secret d·R = r ·P using their persistent private key 3. Derives s′ = H1 (d · R || R || txprev ) and verifies that P + s′ · G = Ptx 4. Computes the transaction-specific private key dtx = d + s′ mod n for signing the next transaction By including both R and txprev in the hash input, the protocol ensures that: • Even if the sender chooses a predictable r, the blinding factor s depends on the hash function output and remains unpredictable to external observers • The recipient can verify that the sender correctly computed Ptx without learning r • Each transaction uses a unique blinding factor (assuming txprev is always unique), preventing linkability even if the sender reuses the same r across different transactions We assume that txprev is always unique, as a malicious sender reusing the exact (r, txprev ) pair could break unlinkability. In practice, txprev can be the hash of the previous transaction or a timestamp with sufficient granularity. 41

Setup: Recipient has persistent keypair (d, P = d · G) and publishes P Sender

Recipient

$

r ← Z∗n R←r·G s ← H1 (r · P || R || txprev ) Ptx ← P + s · G tx ← {Ptx , R, . . . } tx

−−−−−−−→ if R = O then abort s′ ← H1 (d · R || R || txprev ) if P + s′ · G ̸= Ptx then abort dtx ← d + s′ mod n Sign next transaction using dtx Figure 6: Non-interactive protocol secure against malicious sender. 7.2.3

Desired Privacy Properties:

1. Transaction Identity Unlinkability: For any two transactions txi , txj with i ̸= j: Dist[(Ptx,i , Ri )] ≈c Dist[(U1 , U2 )] $

where U1 , U2 ← G are uniform random group elements. Informally: The ownership-related fields in each transaction appear as uniformly random data. The pair (Ptx , R) in any transaction is computationally indistinguishable from two random group elements, making all transactions unlinkable to each other and to any recipient addresses. 2. Forward Privacy: Given dtx,i = di + H1 (di · Ri || Ri || txi−1 ):   Pr A(dtx,i , {txj }nj=1 ) → di ≤ negl(λ) Informally: If a transaction-specific private key dtx,i is compromised (e.g., leaked or extracted from a device), the adversary cannot recover the recipient’s persistent private key di . This ensures that past key exposures do not compromise the recipient’s persistent identity or future transactions. Remark: Transaction Identity Unlinkability implies several important corollaries: • Address Unlinkability: An adversary observing a transaction cannot determine which of two candidate recipients it was sent to, beyond random guessing. This follows immediately since if (Ptx , R) is pseudorandom, it reveals no information about the underlying persistent address P .

42

• Recipient Unlinkability: An adversary observing multiple transactions cannot determine which transactions belong to the same recipient. Even when a recipient reuses their persistent public key P across multiple transactions, the resulting transaction-specific keys appear independent and uniformly random. 7.2.4

Cryptographic Assumptions

For the privacy proofs, we require the following standard cryptographic assumptions in the elliptic curve group G of prime order n with generator G: Definition 7.7 (Decisional Diffie-Hellman (DDH)) The DDH problem is S-hard in G if it has S as a security profile in the following distinguishing scenario: $

$

1. Sample a, b, c ← Z∗n and d ← {0, 1} 2. If d = 0: set T ← (a · G, b · G, ab · G) 3. If d = 1: set T ← (a · G, b · G, c · G) 4. d′ ← A(T ) 5. The attack is successful iff d′ = d = Pr[d′ = d] − 12 . The advantage is AdvDDH A Definition 7.8 (Discrete Logarithm (DL)) The DL problem is S-hard in G if it has S as a security profile in the following attack scenario: $

1. x ← Z∗n , X ← x · G 2. x′ ← A(X) 3. The attack is successful iff x′ = x We model H1 : G × G × M → Zn as a hash function with standard collisionresistance and additional properties suitable for key derivation. 7.2.5

Privacy Proofs

Theorem 7.4 (Transaction Identity Unlinkability) If the DDH problem is S-hard in G and H1 is modeled as a random oracle, then the protocol in Fig. 6 satisfies transaction identity unlinkability. Specifically, for any two transactions txi , txj with i ̸= j: Dist[(Ptx,i , Ri )] ≈c Dist[(U1 , U2 )] $

where U1 , U2 ← G are uniformly random, with distinguishing advantage at most AdvDDH + qnH where qH is the number of hash queries. A $

Proof. For transaction txi , the sender chooses ri ← Z∗n and computes: Ri = ri · G si = H1 (ri · Pi || Ri || txi−1 ) Ptx,i = Pi + si · G 43

We use a game-based argument to show that (Ptx,i , Ri ) is indistinguishable $

from (U1 , U2 ) where U1 , U2 ← G. Game 0: The real transaction generation process as described above. Game 1: Replace si = H1 (ri · Pi || Ri || txi−1 ) with a uniformly random $

si ← Z∗n . Claim: | Pr[Game 0] − Pr[Game 1]| ≤ AdvDDH + qnH . A Consider the tuple (Pi , Ri , ri · Pi ) = (di · G, ri · G, ri di · G). Under the DDH assumption, this is computationally indistinguishable from (di · G, ri · G, c · G) $

where c ← Z∗n . Since H1 is modeled as a random oracle and txi−1 is unique (by assumption), if the adversary does not query H1 (ri · Pi || Ri || txi−1 ), the value si is uniformly random. The probability of guessing the correct input is at most qH n . Game 1 Analysis: Since ri is chosen uniformly at random, Ri = ri · G $ is uniformly distributed in G. Given that si ← Z∗n is uniformly random and independent, Ptx,i = Pi + si · G is uniformly distributed in G, since adding a uniformly random scalar times the generator to any group element yields a uniformly random element. Therefore, in Game 1, (Ptx,i , Ri ) has the same distribution as two independent uniformly random group elements (U1 , U2 ). Since this holds for each transaction independently (with fresh randomness ri for each transaction), the identity data in all transactions is unlinkable. □ Theorem 7.5 (Forward Privacy) If the discrete logarithm problem is S-hard in G and H1 is modeled as a random oracle, then for any PPT adversary A:   qH Pr A(dtx,i , {txj }nj=1 ) → di ≤ AdvDL A + n where dtx,i = di + si mod n and si = H1 (di · Ri || Ri || txi−1 ). Proof. The recipient’s transaction-specific private key is: dtx,i = di + si mod n where si = H1 (di · Ri || Ri || txi−1 ). To recover di from dtx,i , the adversary must compute si , since: di = dtx,i − si mod n Computing si requires evaluating H1 (di · Ri || Ri || txi−1 ), which in turn requires computing the shared secret di · Ri = di ri · G. The adversary observes: • Ri = ri · G (from the transaction) • Pi = di ·G (possibly inferred or public, though unlinkable by Theorem 7.4) • dtx,i (the leaked transaction key)

44

Case 1: The adversary does not query H1 (di · Ri || Ri || txi−1 ). Since H1 is a random oracle, without querying the correct input, si appears uniformly random in Zn . Given dtx,i = di + si mod n where si is unknown and uniform, the value di is information-theoretically hidden. The adversary can succeed only by guessing among qH hash queries, with probability at most qnH . Case 2: The adversary queries H1 (di · Ri || Ri || txi−1 ). To make this query, the adversary must compute di · Ri = di ri · G from Pi = di · G and Ri = ri · G. This is precisely the Computational Diffie-Hellman (CDH) problem, which is at least as hard as the discrete logarithm problem. If the adversary can compute di · Ri , they can use the discrete logarithm oracle to extract di from Pi (or ri from Ri ), succeeding with probability at most AdvDL A . Combining both cases, the adversary’s advantage in recovering di is bounded qH □ by AdvDL A + n , which is negligible. 7.2.6

Remarks on Standard Model

The proofs above use H1 as a random oracle. To achieve standard model security, we propose the following adjustment: Adjustment: Replace the hash function H1 with a key derivation function (KDF) based on a pseudorandom function (PRF) family {fk }k∈K combined with randomness extraction. Specifically: 1. Use a randomness extractor Ext : G → {0, 1}λ based on a strong randomness extractor (e.g., leftmost bits of the x-coordinate under suitable encoding). 2. Define s ← PRF(Ext(r · P ), R || txprev ) where PRF is a pseudorandom function. Under the DDH assumption, the value r · P is pseudorandom (given r · G and P ), and thus Ext(r · P ) serves as a pseudorandom key for the PRF. The PRF output is then pseudorandom, providing similar guarantees to the random oracle model. With this adjustment, the proofs can be adapted to the standard model by replacing random oracle arguments with PRF indistinguishability under DDH, at the cost of slightly more complex security reductions and stronger assumptions on the randomness extractor properties.

45

References [1] Bellare, M.: New proofs for NMAC and HMAC: Security without collision resistance. Journal of Cryptology 28, 844–878 (2015) [2] Bellare, M., Canetti, R., Krawczyk, H.: Keying hash functions for message authentication. In: Koblitz, N. (Ed.) CRYPTO’96. LNCS 1109, pp. 1–15 (1996) [3] Johnson, D., Menezes, A., Vanstone, S.: The elliptic curve digital signature algorithm (ECDSA). In: International journal of information security, 1(1), pp. 36–63 (2001) [4] Buldas, A., Laanoja, R., Rogojin, V., Truu, A.: Unicity: Predicates and Atomic Swaps. (Manuscript, 2025) https://github.com/ unicitynetwork/unicity-predicates-tex [5] Capretto, M., Ceresa, M., Anta, A.F., Moreno-Sánchez, P., Sánchez, C.: Fast and secure decentralized optimistic rollups using Setchain. arXiv:2406.02316 [cs.CR] (2024) https://doi.org/10.48550/arXiv. 2406.02316 [6] Bousfield, L., Bousfield, R., Buckland, C., Burgess, B., Colvin, J., Felten, E., Goldfeder, S., Goldman, D., Huddleston, B., Kalonder, H., Lacs, F., Ng, H., Sanghi, A., Wilson, T., Yermakova, V., Zidenberg, T.: Arbitrum nitro: A second-generation optimistic rollup. (2022) https://github.com/ OffchainLabs/nitro/blob/master/docs/Nitro-whitepaper.pdf [7] Optimism Foundation. Optimism. https://www.optimism.io/ [8] Coinbase. base. https://base.org/ [9] Starknet. https://www.starknet.io/en [10] Matter Labs. zkSync. https://zksync.io/ [11] A Consensys Formation. Linea. https://linea.build/ [12] RGB: Post-blockchain smart contracts. https://rgb.tech/ [13] Ihantjuk, V.: RGB Review: A scalable, confidential smart contract protocol based on Bitcoin. (2024) https://boostylabs.com/blog/rgb [14] Learn RGB. https://rgb.tech/learn/ [15] Jesse H: Introduction to RGB. https://medium.com/@jesse06/ introduction-of-rgb-92c235b2b2dc [16] All you need to know about the RGB protocol. https://www.gate.com/ learn/articles/all-you-need-to-know-about-the-rbg-protocol/ 1196 46

[17] Benaloh, J., de Mare, M.: One-way accumulators: A decentralized alternative to digital signatures. In: Hellseth, T. (Ed.) Eurocrypt 1993, LNCS 765, pp. 274-285 (1993) [18] Camenisch, J., Lysyanskaya, A.: Dynamic accumulators and application to efficient revocation of anonymous credentials. In: Yung, M. (Ed.) Crypto 2002, LNCS 2442, pp. 61-76 (2002) [19] Lipmaa, H.: Secure accumulators from Euclidean rings without trusted setup. In: Bao, F., Samarati, P., Zhou, J. (Eds.) ACNS 2012, LNCS 7341, pp.224-240 (2012) [20] Bonneau, J., Chen, J., Christ, M., Karantaidou, I.: Merkle mountain ranges are optimal: on witness update frequency for cryptographic accumulators. In: Tauman Kalai, Y., Kamara, S.F. (Eds.) Crypto 2025, LNCS 16001, pp. 170-202 (2025) [21] Boneh, D. Bünz, Fisch,B.: Batching techniques for accumulators with applications to IOPs and stateless blockchains. In: Boldyreva, A., Micciancio, D. (Eds.) Crypto 2019, LNCS 11692, pp.561-586 (2019) [22] Coinjoin. https://bitcoinops.org/en/topics/coinjoin/

47

A

Detailed Transaction Sequence Diagram Recipient

Sender

Unicity Service

(pk′ , sk′ ) ← G pk′ x ← {0, 1}ℓ D = (pk′ , x, aux′ ) T = (hst , D) (htx , d) ← Com(H(D)) hT = H(hst , htx ) σ ← S(sk, hT ) Q = (pk, hst , htx , σ)

?

V(pk, hT , σ) = 1 ?

R[H(pk, hst )] = ⊥ R[H(pk, hst )] ← htx

πinc L ∪ (T, σ, htx , d, πinc )

?

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

Open(htx , d) = H(T.D) ?

V(pk, H(hst , htx ), σ) = 1 ?

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

Figure 7: Detailed Unicity transaction flow.

48

Recipient B

Sender A

Unicity Service

y ← {0, 1}ℓ ′ f ← H(pk′ , y) pk ′

f pk ′

f , aux′ ) D = (pk T = (hst , D) (htx , d) ← Com(H(D)) σ ← S(sk, H(hst , htx )) Q = (pk, hst , htx , σ)

?

V(pk, H(hst , htx ), σ) = 1 ?

R[H(pk, hst )] = ⊥ R[H(pk, hst )] ← htx

πinc (T, σ, htx , d, πinc ) ?

Vcert (T, σ, htx , d, πinc ; pk, hst ) = 1 ′ ? f H(pk′ , y) = T.D.pk hst ′ ← H(hst , y)

Figure 8: Masked Address Protocol (Interactive). Recipient generates masked ′ f = H(pk′ , y) to prevent sender from inferring next state. address pk

49

Recipient B

Sender A

Unicity Service

D = (pk′ , aux′ ) T = (hst , D) (htx , d) ← Com(H(D)) σ ← S(sk, H(hst , htx )) Q = (pk, hst , htx , σ)

?

V(pk, H(hst , htx ), σ) = 1 ?

R[H(pk, hst )] = ⊥ R[H(pk, hst )] ← htx

πinc (T, σ, htx , d, πinc ) ?

Vcert (T, σ, htx , d, πinc ; pk, hst ) = 1 (y, π) ← VRF.Prove(sk′ , hst ) hst ′ ← H(hst , y)

Figure 9: Non-Interactive Masked Protocol. Recipient derives deterministic mask y via VRF without prior interaction.

50

Recipient B

Sender A

Unicity Service

r ← Zq , R ← [r]G S ← [r]PB s ← Hkey (S, R, hst ) Ptx ← PB + [s]G D = (Ptx , R, aux′ )

(htx , d) ← Com(H(D)) σ ← S(dA , H(hst , htx )) Q = (PA , hst , htx , σ) ?

V(PA , H(hst , htx ), σ) = 1 R[H(PA , hst )] ← htx

πinc (T, σ, htx , d, πinc )

S ← [dB ]R s ← Hkey (S, R, hst ) ?

PB + [s]G = Ptx dtx ← dB + s

(y, π) ← VRF.Prove(dtx , hst ) hst ′ ← H(hst , y)

Figure 10: Combined Protocol with Unlinkable Keys. Recipient’s permanent public key is PB . Sender derives unlinkable transaction key Ptx = PB + [s]G using ECDH. Recipient derives private key and mask via VRF.

51