arXiv CSopen access

The Consensus Number of Untraceable Cryptocurrencies

The Consensus Number of Untraceable Cryptocurrencies Christian Cachin

1 , David Lehnherr

1 , Juan Villacis

1 , and François-Xavier Wicht #

1 Institute of Computer Science, University of Bern, Switzerland

arXiv:2607.20929v1 [cs.DC] 23 Jul 2026

Abstract Sender untraceability hides the account spent by a cryptocurrency transfer among a set of candidates, its masking set. What a transfer does to that set separates two designs: classical schemes retain the whole set and append a nullifier marking the spent account, so the ledger grows with every transfer; constant-state schemes instead consume and replace the entire set. We ask how this choice affects synchronization. We formalize the two designs as the linear untraceable asset transfer (LUAT) and constant untraceable asset transfer (CUAT) objects and locate them in the consensus hierarchy. In LUAT, transfers from distinct accounts commute. Its consensus number is 2, compared with 1 for standard asset transfer, independently of the masking-set size and of the untraceability notion, and LUAT is starvationfree. Partitioning the accounts into fixed masking sets lets exhausted sets be garbage-collected without increasing that number. In CUAT, a transfer consumes and replaces every account of its masking set, so two transfers whose sets intersect cannot both take effect. We formalize this with the conflict graph on masking sets, whose edges join sets sharing an account. Under weak untraceability, which protects a transaction in isolation, the consensus number is unbounded already for one-round protocols. Under strong untraceability, which protects against an observer of the complete history, untraceability holds on a history exactly when any two accounts sharing a masking set occur in the same number of the masking sets in it. This uniform incidence bounds the conflict graph, and matching constructions attain it, so the consensus number is determined exactly and grows quadratically in the masking-set size. Finally, CUAT is not starvation-free. The two objects therefore pay for the same privacy differently: LUAT in storage, CUAT in synchronization and fairness.

1

1

Contents 1

Introduction

3

2

Related work

6

3

Preliminaries

8

4

Sender untraceability

9

5

Linear untraceable asset transfer

11

5.1

Formal model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

5.2

Consensus number . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

5.2.1

Unshared accounts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

5.2.2

Shared accounts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

5.2.3

Untraceability and the consensus number . . . . . . . . . . . . . . . . . . . . .

17

State growth and garbage collection . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

5.3 6

Constant untraceable asset transfer

21

6.1

Formal model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

6.2

Consensus number . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

6.2.1

One-round protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

6.2.2

Multi-round protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

6.2.3

Weak untraceability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

6.2.4

Strong untraceability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

7

Parallelization and fairness

36

8

Conclusion

40

2

1

Introduction

Cryptocurrencies enable peer-to-peer value transfer without trusted intermediaries. At their core, these systems maintain a ledger, a replicated data structure recording the transaction history and the current state of all accounts. While systems such as Bitcoin provide pseudonymity, privacy-preserving cryptocurrencies aim for stronger guarantees. In particular, sender untraceability prevents an external observer from identifying which account initiated a transaction within a set of candidate accounts, called here the masking set. Achieving this property while preventing double spending poses a fundamental challenge for system design. The standard approach to sender untraceability relies on two complementary data structures: an allow-set containing all potentially unspent accounts and a deny-set of nullifiers marking spent accounts. To transfer value, a user proves in zero knowledge that an account in the allow-set corresponds to a previously unused nullifier, without revealing which one. The limitation of this approach is indefinite state growth: removing an account may reveal that it was spent, whereas removing its nullifier may permit a double spend. Partitioning the accounts into pre-declared masking sets of bounded size recovers part of the loss. A set of 𝑘 accounts admits at most 𝑘 transfers, after which it is exhausted and both the set and its nullifiers can be collected [Cho+23; CW25]. This slows the growth without bounding it, and it adds a second shared object to the system, whose synchronization cost we also determine. Recent work avoids this growth through account re-randomization. Quisquis and related systems [Fau+19; AGC24; MS25] invalidate and replace every account in a fixed-size masking set whenever one of them transfers value. Cryptographic randomization hides which balances changed, and the ledger retains only the current account representations. The resulting state is bounded by the number of active accounts, but two transfers whose masking sets overlap cannot both succeed. Three questions follow, and the paper answers all three. (1) What synchronization power does each design provide? (2) What does untraceability itself cost? (3) What is traded when unbounded state is replaced by masking-set contention? The synchronization consequences of this distinction are not captured by the cryptographic security definitions alone. We study them through the consensus hierarchy [Her91], building on the shared-memory formulation of asset transfer by Guerraoui et al. [Gue+22]. The consensus number of a shared object is the largest number of processes that can solve wait-free consensus using instances of that object and atomic registers. Standard asset transfer has consensus number one: transfers on independently owned accounts require no agreement on their relative order. Consensus numbers therefore provide a natural language for asking whether sender untraceability preserves this independence, and how the answer changes when the anonymity mechanism is also used to keep the state bounded. This perspective also captures the parallelism available to a cryptocurrency implementation. Systems such as Sui and Zef exploit the consensus number one of standard asset transfer [Gue+22] by processing independent accounts without a global total order and invoking stronger coordination only when accounts are shared. For private transfers, a higher consensus number identifies a larger potential contention

3

structure and therefore limits the same form of parallel commit and shardable verification. Our bounds measure how much of this independence is preserved by the two untraceability mechanisms. We formalize the two designs as shared objects parameterized by the masking-set size 𝜆. The linear untraceable asset transfer object LUAT𝜆 models the allow-set/deny-set approach. A transfer consumes one sender account, creates previously unused account representations, and names the remaining members of its masking set only as decoys. The constant untraceable asset transfer object CUAT𝜆 1 models account re-randomization. A transfer atomically consumes and replaces every account in its masking set, although only the sender and recipient balances change. In both objects the sender is hidden among 𝜆 accounts; the distinction is that masking-set overlap is inert in LUAT𝜆 and constitutes a conflict in CUAT𝜆 . This distinction already determines the behavior of the linear-state object. We prove that a LUAT𝜆 object has consensus number exactly 2, independently of 𝜆. Transfers spending distinct accounts commute and both succeed, so increasing the masking-set size creates no additional contention. The object nevertheless exceeds the consensus number of standard asset transfer because a successful operation observes the resulting deny-set and thereby learns its position among concurrent transfers. When 𝑘 processes share an account, contention over its unique nullifier raises the consensus number to max(𝑘, 2). The same separation persists in the progress and storage properties of LUAT𝜆 . A transfer that is eligible when invoked cannot be invalidated by activity on accounts owned by other processes, and the object is therefore starvation-free. Its cost is the monotone growth of the allow-set and deny-set. We formalize the partitioning object used to garbage-collect exhausted, pre-declared masking sets and determine its consensus number. Along the executions relevant to garbage collection, the object is implementable from fetch-and-add and implements two-process consensus; its consensus number is therefore exactly 2 for every part size at least two. Partitioning does not increase the synchronization power required by the linear-state design. The analysis of CUAT𝜆 is governed instead by the intersection pattern of its masking sets. We associate with a protocol a conflict graph whose vertices are the masking sets it may use and whose edges join sets that share an account index. Adjacent transfers cannot both succeed, whereas non-adjacent transfers commute. For one-round protocols, in which every process invokes one transfer, this graph gives an exact characterization: a clique of size 𝑑 implements 𝑑-process consensus by an attempt-and-adopt protocol, and the masking sets of a one-round consensus protocol form a clique at a critical configuration. Hence the one-round consensus power equals the largest admissible clique. This regime captures the synchronization within a single payment attempt, where the masking set is fixed before submission. Unrestricted protocols can use CUAT𝜆 in several rounds and choose later masking sets as a function of earlier outcomes. The relevant structure at a critical configuration is then weaker than a clique: pending transfers from opposite valency classes must intersect, producing a complete bipartite subgraph of the conflict graph, but transfers within one class need not intersect. This distinction is essential. It separates the synchronization required by a single transaction from the full consensus power of the object, and it allows multi-round protocols to solve consensus among strictly more processes than any one-round protocol. We consider two notions of sender untraceability, distinguished by the adversary’s view. Weak untraceability protects each transaction in isolation. We write CUAT𝜆− for CUAT under this requirement and CUAT+𝜆 1 Pronounced Coo-at.

4

for CUAT under strong untraceability. Weak untraceability imposes no global restriction on masking-set incidence, and a single hub account can occur in arbitrarily many masking sets. These sets form arbitrarily large cliques, so cons ( CUAT𝜆− ) = ∞ already for one-round protocols. Strong untraceability protects against an adversary that observes the complete transaction history and uses repeated account appearances to update its beliefs. We prove that strong untraceability holds on a history exactly when any two accounts sharing a masking set appear in the same number of them; on the pairwise-intersecting families a consensus protocol uses, this makes the incidence equal across every account occurring in the history. This uniform-incidence characterization turns the privacy requirement into a combinatorial constraint on the conflict graph. For one-round protocols, uniform incidence together with pairwise intersection bounds the number of masking sets by 𝜆2 − 𝜆 + 1. When 𝜆 − 1 is a prime power, the lines of PG(2, 𝜆 − 1), the projective plane of order 𝜆 − 1, meet the bound: every line contains 𝜆 points, every two lines intersect, and every point has the same incidence. For general 𝜆 ≥ 3, we construct a cyclic difference cover with ⌊𝜆2 /2⌋ translates. It yields a uniformly incident, pairwise-intersecting family and therefore a one-round protocol of that size. Thus the one-round consensus number under strong untraceability lies between ⌊𝜆2 /2⌋ and 𝜆2 − 𝜆 + 1, with equality at the upper bound whenever 𝜆 − 1 is a prime power. For unrestricted protocols, we determine the consensus number exactly: cons ( CUAT+𝜆 ) = 4⌊𝜆/2⌋ ⌈𝜆/2⌉ for every 𝜆 ≥ 3, that is, 𝜆2 when 𝜆 is even and 𝜆2 − 1 when it is odd. The upper bound follows from a refined incidence count over the complete bipartite intersection at a critical configuration. For the matching lower bound, two groups of processes first run the cyclic one-round protocol independently and then reconcile their group decisions on a common object. The second round uses a cross-cover family in which every set from one group intersects every set from the other while all accounts retain uniform incidence. A grid supplies such a family for even 𝜆; for odd 𝜆 we give a cyclic construction that alternates the two possible balanced incidence patterns. The resulting protocol attains the upper bound without any arithmetic condition on 𝜆. In particular, the multi-round consensus number strictly exceeds the one-round upper bound for every 𝜆 ≥ 3. Finally, the conflict structure that gives CUAT𝜆 its synchronization power also prevents starvation-freedom under asynchronous scheduling. A process can repeatedly issue zero-value transfers that re-randomize an overlapping masking set before a competitor succeeds, while remaining eligible indefinitely. This establishes the denial-of-service behavior conjectured for Quisquis [Bün+20]. The contrast with LUAT𝜆 is again structural: a linear-state transfer cannot invalidate a masking set that it merely names, whereas a constant-state transfer invalidates every account in the set it uses. The two objects therefore satisfy the same uniform-incidence condition for strong untraceability but pay for it differently. In LUAT𝜆 , uniformity constrains the masking sets without affecting synchronization. In CUAT𝜆 , the masking sets simultaneously provide anonymity, bound the state, and determine which transfers conflict; the exact consensus number is quadratic in 𝜆. The additional synchronization cost is thus not a consequence of sender privacy alone. It arises when the mechanism that hides the sender is also made responsible for reclaiming state. From an operational perspective, the distinction is local rather than global. Disjoint CUAT transfers still commute and may be processed independently; the additional coordination appears only among transfers connected in the conflict graph. The parameter 𝜆 nevertheless controls both the size of the anonymity set and the worst-case synchronization power of that contention structure. LUAT separates these two roles at 5

the cost of retaining historical state, whereas CUAT couples them in order to reclaim it. The consensus hierarchy therefore exposes a design choice that is hidden at the cryptographic layer: private payment systems may pay for sender untraceability in storage, or use the same masking sets to bound storage and pay instead in synchronization and progress guarantees. We treat the two cases in parallel in Sections 5 and 6, over the untraceability notions that Section 4 defines and characterizes by uniform masking-set incidence, and Section 7 turns the same conflict structure on parallelization and fairness.

2

Related work

Our analysis of CUAT’s synchronization power connects four research areas: consensus numbers of cryptocurrency objects and privacy-preserving primitives, quorum systems and combinatorial design theory, multi-word compare-and-swap primitives, and the storage cost of authenticated data structures. Table 1 collects the consensus numbers of the objects discussed below, together with the ones this paper establishes. Object

System

Untraceability

cons

Source

Asset transfer 𝑘-shared asset transfer ERC20 token Allow-list Deny-list

Bitcoin, Ethereum Sui, Zef Tornado Cash, Railgun identity, e-voting identity, e-voting

none none whole pool — —

1 𝑘 𝑚 1 𝑑

[Gue+22] [Gue+22] [Alp+21] [FGR23] [FGR23]

LUAT𝜆 LUAT𝜆 , 𝑘-shared account

𝑘-partitioning

Zcash, Monero shared account garbage collection

weak or strong weak or strong —

2 max(𝑘, 2) 2

Theorem 5.5 Theorem 5.8 Theorem 5.12

CUAT𝜆− CUAT+𝜆

Quisquis and successors Quisquis and successors

weak strong

∞ 4⌊𝜆/2⌋ ⌈𝜆/2⌉

Theorem 6.11 Theorem 6.20

Table 1. Consensus numbers of asset-transfer objects. The parameters are distinct: 𝑘 processes share an account, 𝑚 spenders are approved on an ERC20 token, 𝑑 processes access the deny-list, 𝜆 is the masking-set size, and the 𝑘 of 𝑘-partitioning is a part size, for which the value is 1 when it equals one. The value for CUAT+𝜆 holds for every 𝜆 ≥ 3 and needs multi-round protocols; one-round protocols reach only between ⌊𝜆2 /2⌋ and 𝜆2 − 𝜆 + 1 (Corollary 6.15). Only CUAT𝜆 is not starvation-free (Theorem 7.4). Guerraoui et al. [Gue+22] challenge the assumption that consensus is necessary for cryptocurrencies. By modeling asset transfers as concurrent objects, they show the consensus number of standard asset transfer is 1, which means that transactions can be processed asynchronously without total ordering. Building on this insight, modern cryptocurrencies like Sui, Libra/Diem, and Zef adopt their 𝑘-shared asset transfer model, where only the 𝑘 users sharing an account need consensus, thereby reducing synchronization overhead. As Alpos et al. [Alp+21] observe, ERC20 tokens let an account owner approve several spenders, which makes the consensus number depend on how many are authorized. Consensus requirements in smart contracts are therefore state-dependent rather than fixed. Privacy-preserving systems, however, face distinct synchronization challenges. Frey et al. [FGR23] analyze allow-list and deny-list objects, showing that while allow-lists need no synchronization, deny-lists require consensus among verifiers performing set-non-membership proofs. More broadly, their framework applies to decentralized identity management and e-voting.

6

CUAT’s pairwise-intersecting masking sets bear structural similarities to quorum systems [Tho79; Gif79]. Both use intersections among sets of elements to provide synchronization in distributed systems. The key distinction is that quorum systems are designed to tolerate process failures and must satisfy constraints derived from failure assumptions, whereas masking sets in CUAT need not account for such failures. We show that CUAT requires two conditions beyond pairwise intersection. First, to implement consensus, the intersections must be structured so that a losing transfer can identify the winner. Second, to maintain sender untraceability across a history, incidence must be uniform: any two accounts sharing a masking set appear in the same number of them. A CUAT transfer also acts like a multi-word compare-and-swap (MCAS), the primitive that Harris et al. [HFP02] implement from single-word CAS. Both update several locations atomically, here the account representations of a masking set, and commit only if every location matches its expected value. The difference is again privacy: an MCAS reveals the locations it touches, whereas a CUAT transfer must keep its sender untraceable. Christ and Bonneau [CB23] introduce revocable proof systems (RPS) as a unifying abstraction for authenticated data structures, including stateless blockchains and set commitments. They prove a fundamental trade-off: any scheme with sublinear global state must incur near-linear proof-update costs when statements are revoked (e.g., when coins are spent). This information-theoretic lower bound focuses on storage and witness maintenance rather than concurrency, but it delimits the same design space we classify. Within that space, what a transfer does to its masking set separates our two objects and sorts the deployed systems. A transfer that consumes one account and only names the rest of its masking set as decoys leaves a growing allow-set and deny-set behind, the design of Zerocoin, Zcash and Monero, which we model as LUAT𝜆 ; a transfer that consumes and replaces its entire masking set keeps the state bounded, the design

of Quisquis and its successors, which we model as CUAT𝜆 . Table 2 places the main systems on this division. Anonymity obtained outside the ledger falls under neither object: mixing services and mixnets relocate the unlinkability to a shuffling party, and in the credential-based variants the deny-set becomes a spent-credential set held by a coordinator, so the object carrying the synchronization is the coordinator rather than the payment system.

System

Anonymity mechanism

Ledger state

Object

Zerocoin [Mie+13] Zcash [Ben+14] Monero [AT20] Anon. Zether [Bün+20]

commitment set, serial numbers note commitments, nullifiers ring signatures, key images anonymity set, per-epoch nonces

linear linear linear bounded

LUAT𝜆 LUAT𝜆 LUAT𝜆 LUAT𝜆

Quisquis [Fau+19] [AGC24; MS25]

masking set, rerandomization masking set, rerandomization

constant constant

CUAT𝜆 CUAT𝜆

Mixers, mixnets, tumblers

off-ledger shuffling or credentials

—

out of scope

Table 2. Untraceable payment designs by the effect of a transfer on its masking set. The LUAT𝜆 designs reference their masking set and consume one account; the CUAT𝜆 designs consume the whole set. Anonymous Zether discards its deny-set at each epoch boundary, so its state is bounded by one epoch of activity rather than fixed, and it is the only listed design whose state does not grow with the transaction count without replacing accounts. 7

3

Preliminaries

This section establishes the theoretical foundations for our analysis. We present the system model, consensus numbers, and the consensus hierarchy theorem. Notation.

We use ← for assignment in algorithms, = for equality testing, := for definitions, and

standard set notation (∈ for membership, ⊆ for subset, ∩ for intersection, ∪ for union). We write 𝑆
:= { 𝐴 ⊆ 𝑆 | | 𝐴| = 𝑘 } for the family of 𝑘-element subsets of 𝑆. 𝑘 System model. We consider 𝑁 asynchronous sequential processes 𝑝 1 , . . . , 𝑝 𝑁 in a set P that may crash (crash-failure model). Throughout, Π denotes a protocol; the process set is P. Processes interact through shared objects supporting operations that produce responses. Objects satisfy linearizability [HW87], where operation histories appear as if executed in a single, consistent order respecting real-time constraints. A register is a shared-memory abstraction supporting read and write operations. We assume atomic registers with linearizable semantics, where each operation appears to take effect instantaneously between invocation and response. Wait-freedom. An implementation of a shared object is wait-free if every operation invoked by a correct process completes in a finite number of steps, regardless of the behavior of other processes. Consensus numbers and the consensus hierarchy. The consensus number cons (𝑂) of an object 𝑂 is the largest number 𝑛 such that it is possible to wait-free implement a consensus object from atomic registers and objects of type 𝑂, in a system of 𝑛 processes [Her91]. The consensus hierarchy shows that objects with higher consensus numbers are strictly more powerful and cannot be implemented from objects with lower consensus numbers. Valency. Following the standard terminology [Her91], a configuration 𝐶 of a binary consensus protocol is 𝑣-valent (with 𝑣 ∈ {0, 1}) if every execution extending 𝐶 decides 𝑣, univalent if it is 𝑣-valent for some 𝑣, and bivalent if both decision values are still reachable from 𝐶. We write 𝐶 · 𝑝 for the configuration reached when process 𝑝 takes one step from 𝐶, and chain steps as 𝐶 · 𝑝 · 𝑞 for the configuration reached when 𝑝 then 𝑞 each take one step. A bivalent configuration is critical if every immediate successor 𝐶 · 𝑝 is univalent. Ownership. Both objects we study attach an owner to each account through a map 𝜇 : A → 2 P \ {∅}, and only a process in 𝜇(𝑎) may spend 𝑎 or read its balance. An account 𝑎 is 𝑘-shared if |𝜇(𝑎)| = 𝑘, and unshared if |𝜇(𝑎)| = 1; an object is unshared if all of its accounts are. Following Guerraoui et al. [Gue+22], sharing is the mechanism by which several processes contend for one account. Account-representation uniqueness. Every transfer of either object creates account representations. We require each newly created representation to differ from every representation already used by the system, and assume that distinct processes never generate the same representation. In a concrete instantiation, account representations embed independent randomness, so a collision occurs only with negligible probability in the security parameter. This condition is required for security, and in particular for integrity: reusing a representation could conflate distinct ownership and balance histories or make an old account representation valid again. It also keeps the concurrency model faithful to the payment abstraction, since otherwise two processes could contend by proposing the same representation rather than by operating on the same account. In particular, the account sets created by concurrent transfers are disjoint. 8

4

Sender untraceability

We consider an external adversary E that eavesdrops on network ciphertexts, records shared-object states, and analyzes process interactions to infer relationships among accounts. We model E as computationally unbounded while idealizing the cryptographic primitives: in particular, the zero-knowledge proof reveals no information about its witness. Thus, for each transfer, E observes the masking set but not the sender account hidden by the witness. The definitions below apply to any untraceable asset-transfer object: a shared object whose transfers each name a masking set of accounts, one of which funds the transfer. Definition 4.1 (Masking sets and 𝜆-masking). A masking set is a set 𝑆 ⊆ A named by a transfer, exactly one of whose members funds it; the remaining members are decoys. An object is 𝜆-masking if every masking set it uses has size exactly 𝜆. We assume throughout that masking sets have at least 𝜆 ≥ 2 members. Nothing else about the object matters here; in particular it is irrelevant whether a transfer leaves its masking set intact or replaces it, and Sections 5 and 6 introduce one object of each kind. Untraceability prevents E from identifying the funding account. We distinguish two views: a single transfer and the complete transfer history, including failed transfers. We write 𝑃(𝑎 𝑖 | ·) for E’s posterior probability that account 𝑎 𝑖 is the sender account of the transfer under consideration. Definition 4.2 (Weak untraceability). An untraceable asset-transfer object satisfies weak untraceability if, for every transfer 𝜏 with masking set 𝑆 and every 𝑎 𝑖 ∈ 𝑆, 𝑃(𝑎 𝑖 | 𝜏) = 1/|𝑆|. The first notion fixes E’s view to one transfer in isolation. Widening it to everything E has recorded, including the masking sets of transfers that failed, gives the second. Definition 4.3 (Strong untraceability). An untraceable asset-transfer object satisfies strong untraceability if, for every transfer 𝜏 with masking set 𝑆 in every history 𝐻 and every 𝑎 𝑖 ∈ 𝑆, 𝑃(𝑎 𝑖 | 𝐻) = 1/|𝑆|. Weak untraceability is the standard guarantee when a transaction is considered in isolation [Mie+13; Ben+14]; strong untraceability additionally protects against statistical inference from repeated account appearances [Mös+18; Egg+22]. The second notion implies the first: averaging 𝑃(𝑎 𝑖 | 𝐻) = 1/|𝑆| over the histories consistent with an observed 𝜏 gives 𝑃(𝑎 𝑖 | 𝜏) = 1/|𝑆|. Since every masking set has at least 𝜆 members, both notions bound the adversary’s success probability by 1/𝜆. For an object 𝑂 we write 𝑂 − for its weak variant and 𝑂 + for its strong one; the notion in force restricts the admissible executions of the object, and no other component of its specification changes. Strong untraceability admits a combinatorial characterization that depends on the masking sets alone. For a history 𝐻, let 𝑓 𝑎 (𝐻) denote the number of masking sets in which account 𝑎 appears, and let A (𝐻) = {𝑎 : 𝑓 𝑎 (𝐻) ≥ 1} denote the accounts occurring in the history. We use a symmetric worst-case adversary model. Each account has an unknown probability of funding a transfer and, in objects whose 9

masking sets also contain the recipient, an unknown probability of receiving one. Decoys are sampled uniformly. Before observing 𝐻, the adversary treats all accounts alike; after observing it, the adversary updates its beliefs using the account-incidence counts. Transfers are issued independently. Side channels such as network metadata and timing are outside the model. Theorem 4.4 (Uniformity). Under the adversary model above, an untraceable asset-transfer object satisfies strong untraceability on a history 𝐻 if and only if 𝑓𝑖 (𝐻) = 𝑓 𝑗 (𝐻) for every two accounts 𝑎 𝑖 , 𝑎 𝑗 lying in a common masking set of 𝐻. Proof. Write 𝐴 = A (𝐻). An account enters the masking set 𝑆 𝜏 of a transfer 𝜏 in exactly one of three ways: it funds 𝜏, which has unknown probability 𝑞 𝑎 ; it receives 𝜏, of unknown probability 𝑟 𝑎 , on objects that place the recipient in the masking set; or it is one of the decoys, which the sender draws uniformly, so that this last event has the same probability for every account alike. Transfers are issued independently, and an account’s identity bears on these events only through (𝑞 𝑎 , 𝑟 𝑎 ), so the probability of 𝐻 depends on an account only through the number 𝑓 𝑎 (𝐻) of masking sets containing it:     Pr 𝐻 | (𝑞 𝑎 , 𝑟 𝑎 ) 𝑎∈ 𝐴 = Pr 𝐻 ′ | (𝑞 𝑎 , 𝑟 𝑎 ) 𝑎∈ 𝐴

whenever 𝑓 𝑎 (𝐻) = 𝑓 𝑎 (𝐻 ′ ) for every 𝑎 ∈ 𝐴.

Thus 𝑓 𝑎 (𝐻) is a sufficient statistic for (𝑞 𝑎 , 𝑟 𝑎 ). The prior is symmetric, so relabelling the accounts by any bijection that leaves every count unchanged leaves the adversary’s beliefs unchanged as well; two accounts with the same count are therefore interchangeable to it. Two accounts with different counts are not: decoy draws contribute equally to every count, so of two accounts the one occurring more often is the one the adversary rates more likely to have funded a transfer, and E[𝑞 𝑎 | 𝐻] grows strictly with 𝑓 𝑎 (𝐻). Uniform incidence implies strong untraceability. Suppose 𝑓 𝑎 (𝐻) = 𝑓𝑏 (𝐻) for all 𝑎, 𝑏 ∈ 𝐴. Fix 𝜏 ∈ 𝐻 and 𝑎 𝑖 , 𝑎 𝑗 ∈ 𝑆 𝜏 , and note 𝑆 𝜏 ⊆ 𝐴. Let 𝜋 swap 𝑎 𝑖 and 𝑎 𝑗 and fix every other account. It maps 𝑆 𝜏 to itself and 𝐻 to a history carrying the same counts, which the adversary therefore judges as it judges 𝐻, while taking the event “𝑎 𝑖 funded 𝜏” to “𝑎 𝑗 funded 𝜏”. The two events have equal posterior probability. Exactly one member of 𝑆 𝜏 funded 𝜏, so these |𝑆 𝜏 | probabilities sum to 1 and each equals 1/|𝑆 𝜏 |. Strong untraceability holds on 𝐻. Strong untraceability implies uniform incidence. Suppose strong untraceability holds on 𝐻, and fix 𝜏 ∈ 𝐻 with 𝑎 𝑖 , 𝑎 𝑗 ∈ 𝑆 𝜏 . Both have posterior probability 1/|𝑆 𝜏 | of having funded 𝜏. Were 𝑓𝑖 (𝐻) ≠ 𝑓 𝑗 (𝐻), strict monotonicity of E[𝑞 𝑎 | 𝐻] in 𝑓 𝑎 (𝐻) would give the two accounts different posterior funding propensities, hence different posterior probabilities of having funded 𝜏, and some 𝑎★ ∈ 𝑆 𝜏 would satisfy 𝑃(𝑎★ | 𝐻) > 1/|𝑆 𝜏 |. Hence 𝑓𝑖 (𝐻) = 𝑓 𝑗 (𝐻): incidence is constant on every masking set of 𝐻. □ The condition is local: it compares two accounts only when some transfer places them in the same masking set. It becomes the global condition used throughout the paper as soon as the masking sets are linked. Corollary 4.5 (Uniform incidence). Let 𝐻 be a history whose masking sets are connected under intersection, meaning that their intersection graph is connected; this holds in particular when they pairwise intersect. Then an untraceable asset-transfer object satisfies strong untraceability on 𝐻 if and only if 𝑓𝑖 (𝐻) = 𝑓 𝑗 (𝐻) for all 𝑎 𝑖 , 𝑎 𝑗 ∈ A (𝐻).

10

Proof. If incidence is constant on A (𝐻) it is constant on every masking set of 𝐻, and Theorem 4.4 gives strong untraceability. Conversely, let strong untraceability hold on 𝐻 and let 𝑎, 𝑏 ∈ A (𝐻). The theorem makes incidence constant on each masking set of 𝐻. Each of 𝑎, 𝑏 lies in some masking set, and by hypothesis there are masking sets 𝑆 (1) , . . . , 𝑆 (𝑚) of 𝐻 with 𝑎 ∈ 𝑆 (1) , 𝑏 ∈ 𝑆 (𝑚) and 𝑆 (𝑙) ∩ 𝑆 (𝑙+1) ≠ ∅ for each 𝑙 < 𝑚. Consecutive sets share an account at which their two constants agree, so one value runs along the whole chain and 𝑓 𝑎 (𝐻) = 𝑓𝑏 (𝐻).

□

Connectedness cannot be dropped. If 𝐻 uses two disjoint masking sets, one once and the other twice, incidence is constant on each of them, so every transfer keeps its members equiprobable and strong untraceability holds, yet incidence takes two values on A (𝐻). The masking sets of every execution analyzed in Section 6 pairwise intersect (Lemma 6.8), so the corollary applies there throughout. The theorem quantifies over A (𝐻), not over A. Every transfer creates previously unused account representations, and an account that has never appeared in a masking set has incidence zero. Such an account is not a candidate sender in 𝐻, and quantifying over it would leave strong untraceability unsatisfiable. Restricted this way, the condition constrains the masking sets alone, and is therefore indifferent to whether a transfer keeps its masking set or replaces it. The two objects of the next sections differ in exactly that respect: under the same condition, one keeps a consensus number of 2 while the other’s grows quadratically in 𝜆.

5

Linear untraceable asset transfer

Zcash [Ben+14] and Monero [AT20] retain spent accounts: they publish a growing allow-set of potentially unspent accounts together with a deny-set of nullifiers marking the spent ones, and a transfer proves in zero knowledge that some account of a masking set has been nullified, without revealing which. The two systems differ in how a transfer names that set. In Zcash it is implicit: the proof establishes membership in the whole note-commitment tree, so the masking set is every account on the ledger when the transfer is issued and 𝜆 grows with it. In Monero it is explicit: a ring signature names a small set of decoys chosen by the sender, and 𝜆 is the ring size, fixed by the protocol; full-chain membership proofs [The24] would move Monero to the implicit form as well. The distinction sets 𝜆 but not the semantics: in both cases the transfer names its masking set and consumes one account of it. We model this family as the linear untraceable asset transfer (LUAT) object, whose state grows linearly in the number of transfers. Here we give the formal LUAT𝜆 model, determine its consensus number for unshared and for shared accounts, show that neither untraceability notion changes it, and analyze the garbage collection forced by its state growth. Section 6 then treats the constant-state family, whose transfers consume and replace the whole masking set.

5.1

Formal model

The object maintains an allow-set Aallow of all potentially valid accounts and a deny-set N of nullifiers for spent accounts. Accounts are single-use: each transfer consumes one account and creates new ones. To spend an account, a process proves knowledge of a secret key for some account of a masking set (a subset

11

of the allow-set) without revealing which, and the transfer publishes a nullifier that invalidates exactly one account of that set. A nullifier is a value 𝜈 ∈ Nspace derived deterministically from an account via a collision-resistant function Nullify : A → Nspace ; distinct accounts therefore have distinct nullifiers. Definition 5.1 (LUAT𝜆 object). Let A be a finite set of accounts and 𝜇 : A → 2 P \ {∅} the owner map. Fix 𝜆 ≥ 2. The LUAT𝜆 object is the tuple (𝑄, 𝑞 0 , 𝑂, 𝑅, Δ, 𝑈), where: • States: 𝑄 consists of triples 𝑞 = (𝛽, Aallow , N ) where Aallow ⊆ A is the allow-set, 𝛽 : Aallow → N assigns balances, and N ⊆ Nspace is the deny-set. The initial state is 𝑞 0 = (𝛽0 , A0 , ∅). • Operations: 𝑂 = {read (𝑎) : 𝑎 ∈ A} ∪ {transfer (𝑆, 𝑎 𝑠 , 𝜈, Anew , 𝛽new ) : 𝑆 ⊆ A, 𝑎 𝑠 ∈ 𝑆, 𝜈 ∈ Nspace , Anew ⊆ A, 𝛽new : Anew → N}. • Responses: 𝑅 = {(Aallow , N )} ∪ N ∪ {⊥}: a transfer returns the resulting allow-set and deny-set, and a read returns a balance or ⊥. • Transitions: For a state 𝑞 = (𝛽, Aallow , N ), a process 𝑝 ∈ P, an operation 𝑜 ∈ 𝑂, a response 𝑟 ∈ 𝑅, ′ and a new state 𝑞 ′ = (𝛽′ , Aallow , N ′ ), we have (𝑞, 𝑝, 𝑜, 𝑞 ′ , 𝑟) ∈ Δ if and only if one of the following

holds:    𝛽(𝑎) if 𝑎 ∈ Aallow and 𝑝 ∈ 𝜇(𝑎)  – ;  ⊥ otherwise  – 𝑜 = transfer (𝑆, 𝑎 𝑠 , 𝜈, Anew , 𝛽new ) ∧ 𝑆 ⊆ Aallow ∧ |𝑆| ≥ 𝜆 ∧ 𝑎 𝑠 ∈ 𝑆 ∧ 𝑝 ∈ 𝜇(𝑎 𝑠 ) ∧ Nullify (𝑎 𝑠 ) = Í 𝜈∧𝜈 ∉ N ∧Anew ∩Aallow = ∅∧ 𝑎∈ Anew 𝛽new (𝑎) = 𝛽(𝑎 𝑠 )∧(∀𝑎 ∈ Anew : 𝛽′ (𝑎) = 𝛽new (𝑎))∧ 𝑜 = read (𝑎) ∧ 𝑞 ′ = 𝑞 ∧ 𝑟 =

′ ′ (∀𝑎 ∈ Aallow : 𝛽′ (𝑎) = 𝛽(𝑎)) ∧ Aallow = Aallow ∪ Anew ∧ N ′ = N ∪ {𝜈} ∧ 𝑟 = (Aallow , N ′ );

– otherwise, 𝑞 ′ = 𝑞 ∧ 𝑟 = (Aallow , N ). • Untraceability: 𝑈 is the untraceability notion in force, giving LUAT𝜆− under Definition 4.2 and LUAT+𝜆 under Definition 4.3. As for the constant-state object, 𝑈 restricts the admissible executions.

A transfer transfer (𝑆, 𝑎 𝑠 , 𝜈, Anew , 𝛽new ) by 𝑝 succeeds exactly when 𝑝 owns 𝑎 𝑠 inside the masking set 𝑆, the nullifier 𝜈 is unused, and the new account representations have not been used before. It then distributes the balance of 𝑎 𝑠 over Anew and adds 𝜈 to the deny-set. We record three consequences of the definition. First, invalidated accounts stay in Aallow with their original balance. Removing them would reveal which account a nullifier invalidated, so retaining them is what makes the allow-set monotone. Second, the deny-set prevents double spending: once 𝜈 appears in N , the condition 𝜈 ∉ N fails in every later state. Third, two transfers spending distinct accounts do not interfere. Their nullifiers differ, the allow-set only grows, and account-representation uniqueness makes their new account sets disjoint, so each succeeds irrespective of the other. Contention in LUAT thus requires two processes to spend the same account, hence an account that is shared.

5.2

Consensus number

We now determine the consensus number of LUAT𝜆 . Protocols may use any finite number of LUAT𝜆 instances together with atomic registers. The analysis splits on ownership: Section 5.2.1 treats unshared objects, Section 5.2.2 objects with a 𝑘-shared account, and Section 5.2.3 determines the effect of the untraceability notion in force, which we show to be none. Both bounds follow from a single commutation property. Lemma 5.2 (Commuting transfers). Let 𝑂 be a LUAT𝜆 object in state 𝑞, and let 𝜏𝑝 and 𝜏𝑝′ be transfers 12

pending at distinct processes 𝑝 and 𝑝 ′ that spend distinct accounts, so that 𝜈 𝑝 ≠ 𝜈 𝑝′ . If both succeed when applied alone at 𝑞, then both succeed in either order, and the two orders yield the same state: applying 𝜏𝑝 then 𝜏𝑝′ at 𝑞 gives the same state as applying 𝜏𝑝′ then 𝜏𝑝 . Proof. Suppose 𝜏𝑝 is applied first, taking 𝑞 = (𝛽, Aallow , N ) to 𝑞 𝑝 = (𝛽 𝑝 , Aallow ∪ Anew, 𝑝 , N ∪ {𝜈 𝑝 }). We check each precondition of 𝜏𝑝′ at 𝑞 𝑝 . Its masking set satisfies 𝑆 𝑝′ ⊆ Aallow ⊆ Aallow ∪ Anew, 𝑝 , since the allow-set only grows. Its nullifier satisfies 𝜈 𝑝′ ∉ N ∪ {𝜈 𝑝 }, because 𝜈 𝑝′ ∉ N by hypothesis and 𝜈 𝑝′ ≠ 𝜈 𝑝 . Its new accounts satisfy Anew, 𝑝′ ∩ (Aallow ∪ Anew, 𝑝 ) = ∅, since Anew, 𝑝′ ∩ Aallow = ∅ by ′

′

hypothesis and Anew, 𝑝′ ∩ Anew, 𝑝 = ∅ by account-representation uniqueness. Finally 𝛽 𝑝 (𝑎 𝑠𝑝 ) = 𝛽(𝑎 𝑠𝑝 ), ′ Í because 𝜏𝑝 preserves balances on Aallow , so the balance condition 𝑎 𝛽new, 𝑝′ (𝑎) = 𝛽(𝑎 𝑠𝑝 ) still holds. Hence 𝜏𝑝′ succeeds at 𝑞 𝑝 , and symmetrically 𝜏𝑝 succeeds after 𝜏𝑝′ . Applying both in either order yields the allow-set Aallow ∪ Anew, 𝑝 ∪ Anew, 𝑝′ , the deny-set N ∪ {𝜈 𝑝 , 𝜈 𝑝′ }, and the balance map that agrees with 𝛽 on Aallow , with 𝛽new, 𝑝 on Anew, 𝑝 , and with 𝛽new, 𝑝′ on Anew, 𝑝′ . Union is commutative and the three domains are pairwise disjoint, so the resulting state does not depend on the order. 5.2.1

□

Unshared accounts

On an unshared object, every account has one owner, so any two processes necessarily spend distinct accounts and Lemma 5.2 applies to every pair. The object nevertheless has non-trivial power: a process learns how many transfers preceded its own by reading the size of the deny-set. Lemma 5.3 (Lower bound). For any 𝜆 ≥ 2, an unshared LUAT𝜆 object implements wait-free 2-process consensus. Hence cons ( LUAT𝜆 ) ≥ 2. Proof. Let 𝑝 1 , 𝑝 2 have inputs 𝑣 1 , 𝑣 2 , let 𝑎 1 , 𝑎 2 ∈ A0 be accounts with 𝜇(𝑎 𝑖 ) = {𝑝 𝑖 }, and let 𝑆 = {𝑎 1 , 𝑎 2 , 𝑎 3 , . . . , 𝑎 𝜆 } ⊆ A0 be a masking set of size 𝜆 containing both. The protocol is given in Figure 1. Agreement. Both transfers succeed: 𝑝 𝑖 owns 𝑎 𝑖 , the nullifiers 𝜈1 ≠ 𝜈2 are distinct and initially absent from N = ∅, and the new account representations have not been used before. By linearizability they are ordered; let 𝑝 𝑖 come first. Its response carries N = {𝜈𝑖 }, so |N | = 1 and 𝑝 𝑖 decides 𝑣 𝑖 . The response of 𝑝 𝑗 , 𝑗 ≠ 𝑖, carries N = {𝜈𝑖 , 𝜈 𝑗 }, so |N | = 2 and 𝑝 𝑗 reads 𝑅[𝑖], which 𝑝 𝑖 wrote before invoking its transfer, and decides 𝑣 𝑖 . Both decide 𝑣 𝑖 . Validity. The decision is 𝑣 1 or 𝑣 2 , both inputs. Termination. The protocol has no loops and every operation is wait-free.

□

The protocol uses the only information a LUAT transfer reveals about concurrent activity, namely its own position in the linearization order. By Lemma 5.2 it reveals nothing else, which yields a matching upper bound at 3 processes. Two commuting transfers leave the object in the same state in either order, so the two orders are indistinguishable to any process that did not take part in them, while the two participants do distinguish them by reading different deny-set sizes. The contradiction therefore needs a third process, which exists only when 𝑛 ≥ 3. Lemma 5.4 (Upper bound). For any 𝜆 ≥ 2, no wait-free 3-process consensus protocol exists using unshared LUAT𝜆 objects and atomic registers. Hence cons ( LUAT𝜆 ) ≤ 2 on unshared objects. 13

2-process consensus from LUAT Shared state: 1: 𝑅[1], 𝑅[2] atomic registers (proposals) 2: A LUAT𝜆 object with accounts A0 = {𝑎 1 , . . . , 𝑎 𝜆 } 3: Masking set 𝑆 = {𝑎 1 , . . . , 𝑎 𝜆 }, where 𝜇(𝑎 𝑖 ) = {𝑝 𝑖 } for 𝑖 ∈ {1, 2} propose(𝑣) at process 𝑝 𝑖 , 𝑖 ∈ {1, 2}: 4: 𝑅[𝑖].write (𝑣) // Publish proposal 5: 𝜈𝑖 ← Nullify (𝑎 𝑖 ) // Compute nullifier 6: Anew,𝑖 ← {𝑏 𝑖 } // One previously unused account 7: 𝛽new,𝑖 (𝑏 𝑖 ) ← 𝛽0 (𝑎 𝑖 ) // Transfer full balance 8: (Aallow , N ) ← transfer (𝑆, 𝑎 𝑖 , 𝜈𝑖 , Anew,𝑖 , 𝛽new,𝑖 ) 9: if |N | = 1 then // First to transfer 10: return 𝑣 // Decide own value 11: else // Second to transfer (|N | = 2) 12: return 𝑅[3 − 𝑖].read () // Decide other’s value

Figure 1. Wait-free 2-process consensus from an unshared LUAT𝜆 object. Proof. Suppose for contradiction that Π is such a protocol for a process set P with 𝑛 = |P | ≥ 3. By the standard critical-state construction [Her91], Π has a reachable critical configuration 𝐶: 𝐶 is bivalent and every successor 𝐶 · 𝑝 is univalent. Partition P = P0 ⊔ P1 by the valency of the successors, where P𝑣 = {𝑝 : 𝐶 · 𝑝 is 𝑣-valent}; both parts are non-empty because 𝐶 is bivalent. Fix 𝑝 ∈ P0 and 𝑞 ∈ P1 . The two pending steps leave identical shared state in either order. At a critical configuration neither pending step is a register operation [Her91]: a read leaves the shared state unchanged, writes to distinct registers commute, and of two writes to one register the second overwrites the first, leaving a configuration that every process except the overwritten writer cannot distinguish from the one in which that writer never took its step. Each case makes two oppositely valent successors indistinguishable to some process that decides in both. Both pending steps are therefore operations on LUAT𝜆 objects. If they are on distinct objects, they act on disjoint state and trivially commute. If either is a read, or a transfer that fails, it leaves the state unchanged and again commutes. In the remaining case both are successful transfers on a common object; since the object is unshared, 𝑝 and 𝑞 own disjoint sets of accounts and so spend distinct accounts, and Lemma 5.2 gives 𝜈 𝑝 ≠ 𝜈𝑞 , both succeeding in either order and reaching a common state. In every case the shared state at 𝐶 · 𝑝 · 𝑞 equals that at 𝐶 · 𝑞 · 𝑝. A spectator derives the contradiction. Neither step writes a register, so the local state of every process other than 𝑝 and 𝑞 is also the same in 𝐶 · 𝑝 · 𝑞 and 𝐶 · 𝑞 · 𝑝. Since 𝑛 ≥ 3, choose 𝑠 ∈ P \ {𝑝, 𝑞} and run 𝑠 alone from each of the two configurations. By wait-freedom 𝑠 decides in both, and because the two configurations are indistinguishable to 𝑠, it decides the same value 𝑣 in both. But 𝐶 · 𝑝 is 0-valent, so every extension of 𝐶 · 𝑝 · 𝑞 decides 0, forcing 𝑣 = 0; and 𝐶 · 𝑞 is 1-valent, so every extension of 𝐶 · 𝑞 · 𝑝 decides 1, forcing 𝑣 = 1. This contradiction shows no such Π exists.

□

Theorem 5.5 (Consensus number of LUAT𝜆 ). For any 𝜆 ≥ 2, an unshared LUAT𝜆 object has consensus number exactly 2, under either untraceability notion.

14

Proof. Immediate from Lemmas 5.3 and 5.4; Corollary 5.9 verifies that both bounds survive the restriction to executions admissible under each notion.

□

The bound does not depend on 𝜆: enlarging the masking set improves privacy at no synchronization cost. The reason is that a LUAT masking set is an argument to a zero-knowledge proof rather than a set of accounts the transfer consumes, so two transfers may name overlapping masking sets and both commit. Section 6 treats the object in which this no longer holds. 5.2.2

Shared accounts

Contention in LUAT requires a shared account. When 𝑘 processes co-own 𝑎★, each of them may spend it but only one succeeds, since their transfers carry the same nullifier 𝜈★ and the deny-set admits it once. This is the LUAT analogue of the 𝑘-shared asset transfer of Guerraoui et al. [Gue+22]. Lemma 5.6 (Lower bound). Let 𝑘 ≥ 2 and let 𝜇(𝑎★) = {𝑝 1 , . . . , 𝑝 𝑘 }. Then {𝑝 1 , . . . , 𝑝 𝑘 } implement wait-free 𝑘-process consensus using the LUAT𝜆 object and atomic registers. Proof. Initialize 𝑎★ with balance 2𝑘. Each 𝑝 𝑖 spends 𝑎★ with the common nullifier 𝜈★ and creates two accounts 𝑏 𝑖 , 𝑐 𝑖 , both owned by all 𝑘 processes, with balances 𝑖 and 2𝑘 − 𝑖, respectively. Thus every transfer has the same public shape, while the smaller of the two confidential balances identifies the winner. The protocol is given in Figure 2. 𝑘-process consensus from LUAT with a shared account Shared state: 1: 𝑅[1], . . . , 𝑅[𝑘] atomic registers (proposals) 2: A LUAT𝜆 object with shared account 𝑎★, 𝜇(𝑎★) = {𝑝 1 , . . . , 𝑝 𝑘 }, 𝛽0 (𝑎★) = 2𝑘 3: Account pairs (𝑏 𝑖 , 𝑐 𝑖 ) with 𝜇(𝑏 𝑖 ) = 𝜇(𝑐 𝑖 ) = {𝑝 1 , . . . , 𝑝 𝑘 } for every 𝑖 ∈ [𝑘] 4: Masking set 𝑆 ∋ 𝑎★ with |𝑆| ≥ 𝜆 propose(𝑣) at process 𝑝 𝑖 , 𝑖 ∈ [𝑘]: 5: 𝑅[𝑖].write (𝑣) // Publish proposal 6: 𝜈★ ← Nullify (𝑎★) // Shared nullifier 7: Anew,𝑖 ← {𝑏 𝑖 , 𝑐 𝑖 } // Two previously unused accounts 8: 𝛽new,𝑖 (𝑏 𝑖 ) ← 𝑖; 𝛽new,𝑖 (𝑐 𝑖 ) ← 2𝑘 − 𝑖 // Encode 𝑖 in the balances 9: (Aallow , N ) ← transfer (𝑆, 𝑎★, 𝜈★, Anew,𝑖 , 𝛽new,𝑖 ) 10: {𝑏, 𝑐} ← Aallow \ A0 // The winner’s new accounts 11: ℓ ← min{read (𝑏), read (𝑐)} // Decode the winner 12: if ℓ = 𝑖 then 13: return 𝑣 // Won 14: else // Lost; the winner is 𝑝 ℓ 15: return 𝑅[ℓ].read ()

Figure 2. Wait-free 𝑘-process consensus from a LUAT𝜆 object with a 𝑘-shared account. Every contender creates two accounts and encodes its identifier as the smaller of the two resulting balances.

15

Agreement. By linearizability the 𝑘 transfers are ordered; let 𝑝 𝑗 come first. At its linearization point 𝑎★ ∈ 𝑆 ⊆ Aallow , 𝜈★ ∉ N = ∅, 𝑝 𝑗 ∈ 𝜇(𝑎★), and Anew, 𝑗 contains only previously unused representations, so 𝜏 𝑗 succeeds. The balance condition holds because 𝛽new, 𝑗 (𝑏 𝑗 ) + 𝛽new, 𝑗 (𝑐 𝑗 ) = 𝑗 + (2𝑘 − 𝑗) = 2𝑘 = 𝛽0 (𝑎★). It adds 𝜈★ to N and 𝑏 𝑗 , 𝑐 𝑗 to the allow-set, so Aallow \ A0 = {𝑏 𝑗 , 𝑐 𝑗 }. Every process owns both accounts and can read their balances. Since 𝑗 ≤ 𝑘 ≤ 2𝑘 − 𝑗, each obtains ℓ = min{ 𝑗, 2𝑘 − 𝑗 } = 𝑗. Every later transfer 𝜏𝑖 , 𝑖 ≠ 𝑗, finds 𝜈★ ∈ N and fails, leaving the state unchanged. Hence 𝑝 𝑖 also reads ℓ = 𝑗. As ℓ = 𝑗 ≠ 𝑖, it reads 𝑅[ 𝑗] and decides 𝑣 𝑗 , which 𝑝 𝑗 wrote before invoking its transfer. Process 𝑝 𝑗 computes ℓ = 𝑗 = 𝑗 and decides its own 𝑣 𝑗 . All decide 𝑣 𝑗 . Validity. The decision is 𝑅[ 𝑗] for some 𝑗 ∈ [𝑘], an input. Termination. The protocol has no loops and every operation is wait-free.

□

The balance encoding is available precisely because the source and the newly created accounts are shared: every participant is authorized to read the resulting balance. It cannot be used to obtain consensus from unshared accounts, or in the CUAT constructions below, because balance confidentiality prevents a losing process from reading an account owned by the winner. Those constructions must therefore expose the winner through the object’s synchronization pattern rather than through balances. Sharing lifts the bound to 𝑘 but no further. A process outside 𝜇(𝑎★) cannot contend for 𝜈★, so by Lemma 5.2 its transfers commute with those of every other process. Lemma 5.7 (Upper bound). Let 𝑘 ≥ 2, let 𝑎★ be the only shared account of a LUAT𝜆 object with 𝜇(𝑎★) = {𝑝 1 , . . . , 𝑝 𝑘 }, and let 𝑝 𝑘+1 ∉ 𝜇(𝑎★). Then {𝑝 1 , . . . , 𝑝 𝑘+1 } have no wait-free (𝑘 + 1)-process consensus protocol using that object and atomic registers. Proof. Suppose such a protocol Π exists. As in Lemma 5.4, take a reachable critical configuration 𝐶, partition P = P0 ⊔ P1 by successor valency with both parts non-empty, and note every pending step is an operation on the object. Process 𝑝 𝑘+1 lies in one part; say 𝑝 𝑘+1 ∈ P0 , the other case being symmetric. Choose 𝑞 ∈ P1 , so 𝑞 ∈ {𝑝 1 , . . . , 𝑝 𝑘 }. Since 𝑎★ is the only shared account and 𝑝 𝑘+1 ∉ 𝜇(𝑎★), every account 𝑝 𝑘+1 may spend is owned by 𝑝 𝑘+1 alone, so the pending steps of 𝑝 𝑘+1 and 𝑞 spend distinct accounts. By Lemma 5.2 (or trivially, if either step leaves the state unchanged), the shared state at 𝐶 · 𝑝 𝑘+1 · 𝑞 equals that at 𝐶 · 𝑞 · 𝑝 𝑘+1 , and neither step writes a register. It remains to find a spectator. The process set has 𝑘 + 1 ≥ 3 members, so there is some 𝑠 ∉ {𝑝 𝑘+1 , 𝑞}. Running 𝑠 alone from the two configurations, wait-freedom makes it decide, and indistinguishability makes it decide the same value in both, contradicting the opposite valencies of 𝐶 · 𝑝 𝑘+1 and 𝐶 · 𝑞 exactly as in Lemma 5.4.

□

Theorem 5.8 (Consensus number of 𝑘-shared LUAT𝜆 ). If 𝑘 processes share ownership of an account 𝑎★ in an otherwise unshared LUAT𝜆 object, the consensus number among them is max(𝑘, 2), under either untraceability notion. Proof. For 𝑘 ≥ 2, Lemmas 5.6 and 5.7 give matching bounds of 𝑘. For 𝑘 = 1 the object is unshared and Theorem 5.5 gives 2. Corollary 5.9 verifies both bounds under each notion.

16

□

The floor at 2 distinguishes LUAT from standard asset transfer [Gue+22], whose 𝑘-shared consensus number is exactly 𝑘 and drops to 1 without sharing. It is due to the deny-set: even with no shared account, a LUAT transfer reports how many transfers preceded it, which a plain asset transfer does not. This is consistent with Frey et al. [FGR23], who locate the synchronization cost of private payments in the deny-list rather than the allow-list. 5.2.3

Untraceability and the consensus number

Neither bound above mentions the untraceability notion in force. Strong untraceability does constrain how LUAT may be used, by the same mechanism as in the constant-state case: by Corollary 4.5, masking-set

incidence must be uniform. Uniformity is therefore a real constraint on LUAT: histories that over-use an account are inadmissible under LUAT+𝜆 , and the hub families of Section 6.2.3 are excluded here too. It does not, however, affect the consensus number, and the following corollary makes the two bounds of Sections 5.2.1 and 5.2.2 explicit in the untraceability notion. Corollary 5.9 (Untraceability does not affect cons ( LUAT𝜆 )). For every 𝜆 ≥ 2,   2 

on unshared objects,

 max(𝑘, 2) 

on objects with a 𝑘-shared account.

cons ( LUAT𝜆− ) = cons ( LUAT+𝜆 ) = 

Proof. The untraceability notion in force restricts the admissible executions, hence the masking sets a protocol may carry; we check that neither bound depends on that restriction. Upper bounds. Lemmas 5.4 and 5.7 rest on Lemma 5.2, whose only hypothesis is that the two transfers spend distinct accounts. Masking sets are not mentioned, so the bounds hold over every family of masking sets, hence over the admissible executions of either variant. Restricting the executions can only lower a consensus number, so both variants are bounded as stated. Lower bounds. It suffices to exhibit admissible executions of LUAT+𝜆 realizing them, strong untraceability implying weak untraceability as noted in Section 4. The protocols of Figures 1 and 2 fix one masking set 𝑆 with |𝑆| ≥ 𝜆, used by every invocation, and constrain it no further. Take A0 = 𝑆. Every transfer of the execution, successful or not, carries 𝑆, so each 𝑎 ∈ 𝑆 has incidence 𝑓 𝑎 (𝐻) = |𝐻|, while the accounts created during the execution lie in no masking set and are excluded from A (𝐻). Incidence is therefore constant on A (𝐻) = 𝑆, and Theorem 4.4 makes the execution admissible under strong untraceability. The decisions are unaffected, so the protocols achieve 2- and 𝑘-consensus respectively on LUAT+𝜆 .

□

The corollary separates two things that coincide for CUAT𝜆 . Uniformity constrains which masking sets a protocol may use; it does not constrain synchronization, because in LUAT the masking set is inert and overlapping masking sets do not conflict. A protocol is therefore free to satisfy untraceability with one choice of masking sets and to obtain its synchronization from a disjoint mechanism, namely the shared account. Section 6 treats an object whose transfers consume their entire masking set; there the two coincide, since overlap is conflict, and the same uniformity constraint determines the consensus number.

17

5.3

State growth and garbage collection

The counterpart of LUAT’s low synchronization cost is its state. Both the allow-set and the deny-set grow monotonically: every transfer adds a nullifier to N and previously unused account representations to Aallow , while retaining the invalidated ones. The state therefore scales with the number of transfers rather than with the number of active accounts, and neither structure can be pruned without sacrificing untraceability (removing an invalidated account reveals which nullifier invalidated it) or security (dropping a nullifier permits a double spend). One remedy partitions accounts into pre-declared, immutable masking sets. Once a masking set of size 𝑘 has been used 𝑘 times, its accounts are exhausted and both the set and its nullifiers can be collected. This technique, studied by Chow et al. [Cho+23] and Cachin and Wicht [CW25], uses an auxiliary partitioning object maintaining a consistent partition of the account set into parts of bounded size. We formalize it and determine its consensus number, which settles whether garbage collection costs more synchronization than LUAT itself. Collection need not be triggered by exhaustion: Anonymous Zether [Bün+20] scopes each nullifier to an epoch and discards the deny-set at every epoch boundary, which bounds the state at the price of one transfer per account per epoch. The two triggers differ in progress as well as in state. Exhaustion is caused by the transfers themselves, so a transfer that is eligible when invoked stays eligible and Theorem 7.5 still applies; an epoch boundary is external to them, and a transfer whose proof is not included before it expires must be reissued, which makes progress depend on a synchrony assumption that LUAT𝜆 itself does not need.

Definition 5.10 (𝑘-partitioning object). Let A be a set of accounts, ≺ a fixed total order on A, and 𝑘 ≥ 1. The 𝑘-partitioning object is the tuple (𝑄, 𝑞 0 , 𝑂, 𝑅, Δ) where: • States: 𝑄 consists of the families B ⊆ 2 A of pairwise-disjoint non-empty parts with |𝐵| ≤ 𝑘 for every 𝐵 ∈ B, of which at most one is incomplete (of size < 𝑘). The initial state is 𝑞 0 = ∅. A

• Operations and responses: 𝑂 = {partition ( 𝐴) : 𝐴 ⊆ A} and 𝑅 = 22 . Ð • Transitions: On partition ( 𝐴) in state B, let 𝑈 = 𝐴 \ B be the yet unpartitioned elements of 𝐴. The new state B ′ is obtained by: (i) if B has an incomplete part 𝐵∗ , replacing it by 𝐵∗ ∪𝐴′ , where 𝐴′ consists of the min(𝑘−|𝐵∗ |, |𝑈|) smallest elements of 𝑈 under ≺; (ii) partitioning 𝑈 \ 𝐴′ , taken in ≺-order, into consecutive parts of size 𝑘, with at most one final part of size < 𝑘. The response is 𝑟 = {𝐵 ∩ 𝐴 : 𝐵 ∈ B ′ , 𝐵 ∩ 𝐴 ≠ ∅}. An execution is admissible if the sets partitioned by distinct operations are pairwise disjoint and each is partitioned by its owner. This matches the garbage-collection setting, where a process partitions the accounts it has just created. Fixing ≺ makes the transition deterministic, so the object has a well-defined sequential specification; the invariant that at most one part is incomplete is preserved, since step (i) consumes the only incomplete part and step (ii) leaves at most one. The response reports the partition restricted to 𝐴, so a process learns how its own accounts were grouped and nothing else. This withholds nothing the application needs. A process does eventually require the whole part, to name its co-members as decoys, but it reads them from the ledger once the part is complete, and a register read has consensus number 1. What the restriction denies 18

is only that this information arrive atomically with the operation, and that is where the synchronization power would lie: were the response to expose whole parts, a process could read foreign accounts out of its own part and reconstruct the arrival order of other operations. Already at 𝑘 = 3, three processes each partitioning a pair {𝑥𝑖 , 𝑦 𝑖 } would identify the first to arrive, raising the consensus number to at least 3. Collection itself needs no coordination and is therefore excluded from the object: once the partition is agreed, a part is discarded when its own 𝑘 accounts have been spent, which every process can determine locally. Two conditions on ≺ matter. It must be fixed in advance and identical at every process, evaluated locally on account representations and never negotiated during the execution, since agreeing on an order would itself be an agreement problem; this is what keeps ≺ out of the synchronization analysis, and Lemma 5.11 confirms it by implementing the object from a single fetch-and-add. It must also be independent of ownership, so that membership in a part does not follow from who created an account. Independence is necessary but not sufficient. Under admissibility a process partitions accounts it has just created, and step (ii) forms parts from those accounts alone, so an invocation with | 𝐴| ≥ 𝑘 fills a part with one owner’s accounts whatever ≺ is; only the part inherited by step (i) mixes owners. The parts therefore serve as masking sets when invocations are small relative to 𝑘, which is the garbage-collection regime, where a transfer creates an output and a change account. The degenerate case is invisible to Theorem 4.4: every account lies in exactly one part, so incidence is uniformly 1 and the funding account remains one of 𝑘 candidates, but those candidates share an owner and the transfer identifies its sender. The object reduces to a standard primitive. Lemma 5.11 (Reduction to fetch-and-add). Let 𝑡 = |

Ð

B| denote the number of partitioned elements

before an operation. Along admissible executions: (i) the 𝑘-partitioning object is implementable from a fetch-and-add register modulo 𝑘 and atomic registers; and (ii) writing 𝐵 for the response part containing the ≺-least element of 𝐴, we have |𝐵| = min 𝑘 −
(𝑡 mod 𝑘), | 𝐴| . Proof. Admissibility gives 𝑈 = 𝐴 for every operation, since no element of 𝐴 has been partitioned before. By the state invariant at most one part is incomplete, and it has size 𝑡 mod 𝑘: the partitioned elements fill parts of size 𝑘 in order, leaving 𝑡 mod 𝑘 elements in the last one. Steps (i) and (ii) therefore place the elements of 𝐴, in ≺-order, into the 𝑘 − (𝑡 mod 𝑘) free slots of the incomplete part and then into new parts of size 𝑘. The induced partition of 𝐴, which is exactly the response, is thus a function of 𝑡 mod 𝑘, | 𝐴|, and the ≺-order of 𝐴; the last two are local to the invoking process. The effect on the shared state is 𝑡 ↦→ 𝑡 + | 𝐴|. This yields claim (i): on partition ( 𝐴), fetch-and-add | 𝐴| to a register modulo 𝑘, obtaining 𝑡 mod 𝑘, and compute the response locally by the rule above. Each operation takes a single fetch-and-add, so the implementation is wait-free and linearizes at that step. For claim (ii), write 𝑐 = 𝑡 mod 𝑘 and let 𝑎 1 be the ≺-least element of 𝐴. If 𝑐 = 0 there is no incomplete part, so 𝑎 1 opens a new part, which receives the ≺-first min(𝑘, | 𝐴|) elements of 𝐴. If 𝑐 > 0 the incomplete part has 𝑘 − 𝑐 free slots, and 𝑎 1 joins it along with the ≺-next min(𝑘 − 𝑐, | 𝐴|) − 1 elements of 𝐴. Admissibility makes 𝐴 disjoint from every other partitioned set, so intersecting with 𝐴 removes exactly the foreign 19

elements of that part, leaving |𝐵| = min(𝑘 − 𝑐, | 𝐴|). Both cases agree with |𝐵| = min 𝑘 − (𝑡 mod 𝑘), | 𝐴| , since 𝑐 = 0 gives 𝑘 − 𝑐 = 𝑘.

□

Theorem 5.12 (Consensus number of 𝑘-partitioning). Along admissible executions, cons (1-Part) = 1 and cons (𝑘-Part) = 2 for every 𝑘 ≥ 2. Proof. Case 𝑘 = 1. Here 𝑡 mod 1 = 0 always, so by Lemma 5.11 the response is the constant {{𝑎} : 𝑎 ∈ 𝐴}, which the invoking process computes without consulting the shared state. The object is implementable from nothing, so it adds no power to atomic registers, whose consensus number is 1 [Her91]. Hence cons (1-Part) = 1.

Upper bound for 𝑘 ≥ 2. By Lemma 5.11 the object is implementable from a fetch-and-add register and atomic registers. Fetch-and-add has consensus number 2 [Her91], and an object implementable from objects of consensus number 2 cannot exceed 2, since otherwise the implementation would solve 3-process consensus from consensus-number-2 objects. Hence cons (𝑘-Part) ≤ 2. The bound is not an artefact of the reduction. By claim (ii) each of 𝑑 processes partitioning 𝑘 + 1 accounts sees a different response size, and so learns its own position in the linearization order; for 𝑘 ≥ 3 the first three see 𝑘, 𝑘 − 1 and 𝑘 − 2. A position is not an identity, however: the third process learns that it is third but not which of the other two preceded it, and so has no register it can adopt. Only at two processes does a position determine the other party, which is the same reason fetch-and-add itself stops at 2. Lower bound for 𝑘 ≥ 2. Let 𝑝 1 , 𝑝 2 hold disjoint account sets 𝐴1 , 𝐴2 with | 𝐴𝑖 | = 𝑘 + 1 and inputs 𝑣 1 , 𝑣 2 . Each 𝑝 𝑖 writes 𝑣 𝑖 to the single-writer register 𝑅[𝑖], invokes partition ( 𝐴𝑖 ), and inspects the part 𝐵𝑖 of its response that contains the ≺-least element of 𝐴𝑖 . It decides its own input if |𝐵𝑖 | = 𝑘, and otherwise reads 𝑅[3 − 𝑖] and decides that value. By linearizability the two operations are ordered; let 𝑝 𝑖 come first. It meets 𝑡 = 0, so claim (ii) of Lemma 5.11 gives |𝐵𝑖 | = min(𝑘, 𝑘 + 1) = 𝑘, and 𝑝 𝑖 decides 𝑣 𝑖 . Process 𝑝 𝑗 , 𝑗 ≠ 𝑖, meets 𝑡 = | 𝐴𝑖 | = 𝑘 + 1, hence 𝑡 mod 𝑘 = 1 and |𝐵 𝑗 | = min(𝑘 − 1, 𝑘 + 1) = 𝑘 − 1. As 𝑘 − 1 ≠ 𝑘, process 𝑝 𝑗 takes the second branch and reads 𝑅[𝑖], which 𝑝 𝑖 wrote before invoking its operation, and decides 𝑣 𝑖 . Both decide 𝑣 𝑖 , so agreement holds; validity is immediate, as the decision is 𝑣 1 or 𝑣 2 ; and the protocol has no loops, so it is wait-free. Hence cons (𝑘-Part) ≥ 2. The choice | 𝐴𝑖 | = 𝑘 + 1 matters: it is the smallest size that is neither a multiple of 𝑘 (which would leave 𝑡 mod 𝑘 at 0 for both processes, making the responses coincide) nor equal to 1 (for which the response is the singleton { 𝐴𝑖 } in every state, carrying no information).

□

For 𝑘 ≥ 2 the partitioning object therefore has the same consensus number as LUAT itself, so partitioningbased garbage collection adds no synchronization requirement to the classical design. Randomizing the assignment does not change this number. Cachin and Wicht [CW25] draw the partition from a distributed randomness beacon, so that an adversary cannot grind account keys to steer its accounts into a chosen part; a public deterministic rule, including the order ≺ above, offers no such guarantee. The beacon value is read-only shared data, of consensus number 1, and it selects which part an account joins, not how many free slots that part still has. Enforcing |𝐵| ≤ 𝑘 requires the object to track that occupancy, so the response continues to report how much of a part was already filled, which is exactly what the lower bound uses. Randomization therefore leaves the object at 2; what it buys is grinding resistance and the independence from ownership discussed above, and what it costs is a stronger failure 20

assumption. Unpredictability requires the beacon value to be unknown when the accounts are created, so a partition waits for the beacon to publish, and publishing needs enough correct processes to contribute, a threshold set by the beacon scheme. The partitioning object is wait-free and tolerates any number of crashes, whereas the randomness it consumes is available only under a bound on the number of faulty processes. This differs from the epoch-scoped nullifiers noted above, which instead presuppose synchrony. A beacon that must also agree on which contributions were counted adds synchronization of its own, which a beacon whose round value is a unique threshold signature on the round number avoids. To summarize the linear-state family: its consensus number is 2, independently of 𝜆 and of the untraceability notion in force, and max(𝑘, 2) under 𝑘-sharing; strong untraceability constrains its masking sets but not its synchronization; and its state growth is collectable at no synchronization cost. Its cost is storage. Section 6 removes that cost and determines what replaces it.

6

Constant untraceable asset transfer

Quisquis and similar systems [Fau+19; AGC24; MS25] address the monotonic growth that Section 5.3 charged to LUAT, and they do so by discarding the spent account instead of retaining it: each transfer invalidates all accounts of its masking set and creates new ones in their place, while cryptographic proofs hide which of them moved value. The ledger then stores only current accounts, and its size is bounded by the number of active accounts rather than by the number of transfers. We model this family as the constant untraceable asset transfer (CUAT) object, again building on the asset transfer formalism of Guerraoui et al. [Gue+22]. The common untraceability notions and their uniform-incidence characterization appear in Section 4; this section gives the formal CUAT model and determines its consensus number. One difference from Section 5 accounts for the difference in the results. A LUAT transfer consumes a single account and names the rest of its masking set as decoys, so overlapping masking sets do not conflict and, by Lemma 5.2, transfers on distinct accounts commute. A CUAT transfer consumes its masking set. Two transfers whose masking sets meet cannot both commit, so overlap is conflict, the masking-set family carries a graph structure, and the uniformity required by strong untraceability, which does not affect LUAT (Corollary 5.9), bears on the consensus number.

6.1

Formal model

We now formalize the 𝜆-CUAT object. Each transfer atomically invalidates an old masking set and creates a new one of size 𝜆, with a zero-knowledge proof witnessing ownership of the invalidated accounts. In the terms of Definition 4.1, CUAT𝜆 is 𝜆-masking, whereas LUAT𝜆 only requires at least 𝜆 members.

21

Definition 6.1 (CUAT𝜆 object). CUAT𝜆 is a shared-memory asset transfer object specified by the tuple CUAT𝜆 = (𝑄, 𝑞 0 , 𝑂, 𝑅, Δ, 𝑈) where:

• States: 𝑄 consists of pairs 𝑞 = (A, 𝛽) where A is a finite set of currently valid accounts and 𝛽 : A → N maps each account to its balance. Each account 𝑎 ∈ A carries two fixed fields assigned at creation: an owner set 𝜇(𝑎) ⊆ P and an index idx(𝑎) ∈ N also denoted by a subscript. The initial state is 𝑞 0 = (A0 , 𝛽0 ) for some finite A0 . • Operations: The set 𝑂 consists of: read(𝑎) for any account 𝑎, and transfer(𝑆 𝛽 ′ , 𝜋) where 𝑆 𝛽 ′ = {𝑎 1′ , . . . , 𝑎 𝜆′ } is a set of 𝜆 new accounts and 𝜋 is a zero-knowledge proof. The transfer carries an implicit bijection 𝜙 : 𝑆 𝛽 → 𝑆 𝛽 ′ between the old and new masking set that preserves both account fields: 𝜇(𝜙(𝑎)) = 𝜇(𝑎) and idx(𝜙(𝑎)) = idx(𝑎) for every 𝑎 ∈ 𝑆 𝛽 . • Responses: 𝑅 consists of: – For read(𝑎): either 𝛽(𝑎) if the invoking process owns 𝑎, or ⊥ otherwise. – For transfer(𝑆 𝛽 ′ , 𝜋): a pair (A, 𝑏) where A is the current account set and 𝑏 ∈ {TRUE, FALSE} indicates success or failure. • Transitions: Δ ⊆ 𝑄 × 𝑂 × 𝑅 × 𝑄 specifies allowed state transitions. For any 𝑞 = (A, 𝛽) and 𝑞 ′ = (A ′ , 𝛽′ ): – Account read: If 𝑜 = read(𝑎) invoked by process 𝑝, then 𝑞 ′ = 𝑞 and    𝛽(𝑎)  𝑟=  ⊥ 

if 𝑎 ∈ A and 𝑝 ∈ 𝜇(𝑎), otherwise.

– Transfer success: If 𝑜 = transfer(𝑆 𝛽 ′ , 𝜋) with 𝑆 𝛽 ⊆ A, 𝑆 𝛽 ′ ∩ A = ∅, |𝑆 𝛽 ′ | = 𝜆, and 𝜋 is a proof demonstrating ∃𝑝 ∈ P, 𝑎 𝑠 , 𝑎𝑟 ∈ 𝑆 𝛽 , 𝑣 ∈ N such that 𝑝 ∈ 𝜇(𝑎 𝑠 ) and 𝛽(𝑎 𝑠 ) ≥ 𝑣, then the new account set is A ′ = (A \ 𝑆 𝛽 ) ∪ 𝑆 𝛽 ′ , and the new balance map 𝛽′ : A ′ → N is    𝛽(𝜙 −1 (𝑎)) − 𝑣       𝛽(𝜙 −1 (𝑎)) + 𝑣  ′ 𝛽 (𝑎) =   𝛽(𝜙 −1 (𝑎))       𝛽(𝑎) 

if 𝑎 = 𝜙(𝑎 𝑠 ), if 𝑎 = 𝜙(𝑎𝑟 ), if 𝑎 ∈ 𝑆 𝛽 ′ \ {𝜙(𝑎 𝑠 ), 𝜙(𝑎𝑟 )}, if 𝑎 ∈ A \ 𝑆 𝛽 .

Return 𝑟 = (A ′ , TRUE). – Transfer failure: In all other cases of transfer(·), set 𝑞 ′ = 𝑞 and 𝑟 = (A, FALSE). • Untraceability: 𝑈 specifies the untraceability notion required for the object. We consider two notions: weak untraceability (Definition 4.2), giving the object CUAT𝜆− , and strong untraceability (Definition 4.3), giving CUAT+𝜆 . We write CUAT𝜆 for either variant when the result or argument applies to both. The notion restricts the valid executions of the object, as some use patterns lead to untraceability loss, especially under strong untraceability. The 𝜆-CUAT models privacy-preserving cryptocurrencies through account invalidation and creation. A transfer operation takes a set 𝑆 𝛽 ′ = {𝑎 1′ , . . . , 𝑎 𝜆′ } of 𝜆 new accounts and a zero-knowledge proof 𝜋. The proof 𝜋 demonstrates ownership and valid balance updates without revealing the sender or recipient. 22

Successful transfers atomically invalidate all accounts in 𝑆 𝛽 and create all accounts in 𝑆 𝛽 ′ with updated balances. This atomic masking-set update is the key mechanism: all old accounts are removed, all new accounts are created, and the cryptographic proof hides which accounts are the sender and recipient. Balance confidentiality ensures that only account owners can observe account balances. Figure 3 illustrates the effect of a successful transfer on the masking set. Example 6.2 (Transfer on a 3-element masking set). Consider a system with 𝜆 = 3. Suppose the current state has A = {𝑎 1 , . . . , 𝑎 8 } with accounts 𝑎 3 , 𝑎 5 , 𝑎 7 ∈ A. Process 𝑝 3 (owner of 𝑎 3 ) invokes 𝜏 = transfer(𝑆 𝛽 ′ , 𝜋) with 𝑆 𝛽 ′ = {𝑎 3′ , 𝑎 5′ , 𝑎 7′ } (new accounts) where 𝑆 𝛽 = {𝑎 3 , 𝑎 5 , 𝑎 7 } is paired with 𝑆 𝛽 ′ via the field-preserving bijection 𝜙 : 𝑎 𝑖 ↦→ 𝑎 𝑖′ (so 𝜇(𝑎 𝑖′ ) = 𝜇(𝑎 𝑖 ) and idx(𝑎 𝑖′ ) = idx(𝑎 𝑖 ) = 𝑖). The proof 𝜋 demonstrates that 𝑝 3 owns some account in 𝑆 𝛽 and that it transfers 𝑣 units between two accounts while preserving all other balances. If 𝜏 succeeds, the state transition yields: Accounts: A ′ = (A \ {𝑎 3 , 𝑎 5 , 𝑎 7 }) ∪ {𝑎 3′ , 𝑎 5′ , 𝑎 7′ }. The zero-knowledge proof 𝜋 hides which accounts in 𝑆 𝛽 = {𝑎 3 , 𝑎 5 , 𝑎 7 } are the sender and recipient. Any concurrent transfer using an overlapping masking set will fail after 𝜏 completes, since the old accounts 𝑎 3 , 𝑎 5 , 𝑎 7 are no longer valid. Accounts 𝑎 𝑖 and 𝑎 𝑖′ share the same index field (idx(𝑎 𝑖 ) = idx(𝑎 𝑖′ ) = 𝑖), representing the same logical position despite differing cryptographic representations. Initial state (old accounts)

𝑎1

𝑎2

𝑎3

𝑎4

𝑎5

𝑎6

𝑎7

𝑎8

After transfer (new accounts 𝑆 = {𝑎 3′ , 𝑎 5′ , 𝑎 7′ })

𝑎1

𝑎2

𝑎 3′

𝑎4

𝑎 5′

𝑎6

𝑎 7′

𝑎8

Figure 3. Effect of a successful transfer transfer(𝑆 𝛽 ′ , 𝜋) with 𝑆 𝛽 ′ = {𝑎 3′ , 𝑎 5′ , 𝑎 7′ } where 𝑆 𝛽 = {𝑎 3 , 𝑎 5 , 𝑎 7 } is identified by shared index fields (idx(𝑎 𝑘 ) = idx(𝑎 ′𝑘 ) = 𝑘). The proof 𝜋 demonstrates ownership and valid rerandomization. Shaded accounts are the new accounts in masking set 𝑆 𝛽 ′ ; the old accounts 𝑆 𝛽 are removed and replaced by 𝑆 𝛽 ′ . Accounts outside 𝑆 𝛽 remain unchanged. The properties and design of the CUAT highlights a key consequence: a transfer that invalidates accounts in 𝑆 𝛽 prevents all concurrent transfers that use any account from 𝑆 𝛽 in their masking set. This interdependence creates complex synchronization requirements. Overlapping transfers must coordinate to prevent conflicts, while disjoint transfers can proceed concurrently. The atomicity requirement for masking-set updates suggests that CUAT objects possess non-trivial synchronization power, which we analyze in the next section.

6.2

Consensus number

This section characterizes the wait-free consensus number of 𝜆-CUAT. Protocols may use any finite number of 𝜆-CUAT instances together with atomic registers. By Definition 6.1, the bijection 𝜙 of every successful transfer preserves each account’s index idx(𝑎). Accounts with the same index therefore represent the same logical position across rerandomizations, and two masking sets conflict precisely when they share an index. We capture this synchronization structure by a graph on masking sets (Definition 6.3). Two modeling choices distinguish the analysis from earlier work on asset transfer. Guerraoui et al. [Gue+22] encode the winning process in account balances. CUAT cannot use this channel because only an account’s owner may query its balance, so its synchronization must instead run through the masking sets. Moreover,

23

untraceability is a runtime constraint [Dai+18]: we admit only executions consistent with the notion in force and take the consensus number over that restricted family. The analysis splits along the round structure of 𝜏-invocations, and we begin with the case of practical interest. Section 6.2.1 treats one-round protocols (one 𝜏-invocation per process). This models how CUAT is used in payment systems [Fau+19; AGC24; MS25]: a user submits a single transaction whose masking set is fixed before submission, and validators either commit it or reject it. The one-round upper bound therefore captures the synchronization cost faced inside one such transaction: validators process non-conflicting transfers independently and only need to coordinate when two transfers contend over a shared masking set, and the upper bound sizes the worst-case coordination slice. Section 6.2.2 lifts the analysis to multi-round protocols, where CUAT is used as a synchronization primitive inside a layered agreement protocol whose outer rounds adapt their masking sets to earlier outcomes. This captures CUAT’s theoretical synchronization power but is not the typical operational mode of payment systems. To start our analysis, we first formalize the conflict graph and its clique number. Definition 6.3 (Conflict graph and clique number). Two masking sets 𝑆 and 𝑆 ′ on a common CUAT𝜆 object conflict when there exist 𝑎 ∈ 𝑆 and 𝑎 ′ ∈ 𝑆 ′ with idx(𝑎) = idx(𝑎 ′ ). Let S(Π) denote the family of masking sets carried by some 𝜏-invocation in some execution of Π admissible under the untraceability notion in force. The conflict graph 𝐺 of Π has a vertex 𝑣 𝑆 for each 𝑆 ∈ S(Π), and an edge (𝑣 𝑆 , 𝑣 𝑆 ′ ) ∈ 𝐸 whenever 𝑆 and 𝑆 ′ conflict. A clique in 𝐺 is a set of pairwise-conflicting masking sets, and the clique number 𝜔(𝐺) is the size of the largest clique. The family S(Π) captures every masking set Π may issue, including across executions where processes adapt their choices to the schedule. Any single execution realizes a subgraph of 𝐺, with clique number at most 𝜔(𝐺). The upper-bound arguments below inspect the masking set each process is about to invoke at a critical configuration; these masking sets lie in S(Π) by definition, so the bounds hold whether Π chooses masking sets statically or dynamically. The matching lower bounds are realized by protocols whose masking-set assignment is fixed in advance. Alongside the conflict graph, a second invariant tracks how many masking sets contain a given account. Definition 6.4 (Incidence number). The incidence of an account 𝑎 ∈ A is the number of vertices 𝑣 𝑆 ∈ 𝑉 (𝐺) such that 𝑎 ∈ 𝑆. The incidence number of Π is 𝑟 (Π) = max𝑎∈ A incidence(𝑎). Cliques in 𝐺 implement consensus. When 𝑑 masking sets pairwise conflict, at most one of the associated transfers can return true: any pair shares an index, and the second transfer to commit finds that index already invalidated and fails. Losing transfers inspect the published CUAT state, locate the successful masking set, and adopt the value its issuer wrote to a single-writer register. Pairing each of 𝑑 processes with one clique member yields a 𝑑-process consensus protocol that attempts the transfer, decides on success, and adopts on failure; hence 𝜔(𝐺) lower-bounds the consensus power of 𝜆-CUAT. The matching upper bounds, both at 𝜔(𝐺) and beyond, rest on a binary-input specialization of the standard critical-state construction [Her91]. Lemma 6.5 (Different valencies). Let Π be a deterministic wait-free consensus protocol for 𝑛 ≥ 2 processes in the asynchronous shared-memory model. For any process 𝑝 and any 𝑣 ∈ {0, 1}, the input assignment 𝐼 with 𝐼 ( 𝑝) = 𝑣 and 𝐼 (𝑠) = 1 − 𝑣 for 𝑠 ≠ 𝑝 admits a reachable critical configuration 𝐶 such that 𝐶 · 𝑝 is 𝑣-valent and 𝐶 · 𝑠 is (1 − 𝑣)-valent for every 𝑠 ≠ 𝑝. 24

Proof. By symmetry of 0 and 1, take 𝑣 = 0; process 𝑝 then has input 0 and every other process has input 1. Let 𝜎 be the schedule in which 𝑝 takes no steps and every other process runs to completion. By wait-freedom each 𝑠 ≠ 𝑝 decides along 𝜎, and by validity every such decision is 1, since 1 is the only input present. Hence 𝜎 ends in a 1-valent configuration. The initial configuration is bivalent (𝜎 decides 1 while running 𝑝 alone decides 0), so 𝜎 has a last bivalent prefix, and the standard critical-state construction extends that prefix 𝑝-silently to a reachable critical configuration 𝐶. Fix 𝑠 ≠ 𝑝 and suppose, toward a contradiction, that 𝐶 · 𝑠 is 0-valent. Every extension of 𝐶 · 𝑠 then decides 0. Consider the extension that runs every process in P \ {𝑝} to completion before 𝑝 takes a step: wait-freedom guarantees termination, and validity forces the decision to be 1, since every participant before 𝑝 acts has input 1. This contradicts 0-valence, so 𝐶 · 𝑠 is 1-valent for every 𝑠 ≠ 𝑝. By bivalence of 𝐶, the remaining successor 𝐶 · 𝑝 is 0-valent.

□

In each subsequent application, we extract a reachable critical configuration whose successors split processes by valency, then exploit the commutativity of 𝜆-CUAT transfers on disjoint account indices: two masking sets on opposite valency sides must conflict, since otherwise their transfers commute, and a spectator process, unable to distinguish the two orders, would be forced to decide both values. The next lemma packages this technique; the spectator is why it requires a third process. Lemma 6.6 (Bipartite intersection at a critical configuration). Let Π be a wait-free binary consensus protocol for 𝑛 ≥ 3 processes on CUAT𝜆 objects and atomic registers, and let 𝐶 be a reachable critical configuration of Π. There exist a CUAT𝜆 object 𝑂 and a non-trivial partition P0 ⊔ P1 = P such that every pending step at 𝐶 is a 𝜏-invocation on 𝑂, and, writing 𝑆 𝑝 for the masking set carried by 𝑝’s pending invocation: (i) 𝐶 · 𝑝 is 0-valent for every 𝑝 ∈ P0 and 𝐶 · 𝑞 is 1-valent for every 𝑞 ∈ P1 ; (ii) 𝑆 𝑝 ∩ 𝑆 𝑞 ≠ ∅ on 𝑂 for every ( 𝑝, 𝑞) ∈ P0 × P1 . Proof. At a critical configuration neither pending step is a register operation [Her91]: a read leaves the shared state unchanged, writes to distinct registers commute, and of two writes to one register the second overwrites the first, leaving a configuration indistinguishable to every process except the overwritten writer. Each case makes two oppositely valent successors indistinguishable to some process that decides in both. Every pending step at 𝐶 is therefore a 𝜏-invocation. Define P0 = {𝑝 ∈ P : 𝐶 · 𝑝 is 0-valent} and P1 = P \ P0 ; both are non-empty by bivalency of 𝐶, and property (i) follows. Fix 𝑝 ∈ P0 and 𝑞 ∈ P1 , and suppose toward a contradiction that 𝜏(𝑆 𝑝 ) and 𝜏(𝑆 𝑞 ) are on distinct 𝜆-CUAT objects, or on a common object with 𝑆 𝑝 ∩ 𝑆 𝑞 = ∅. Each transfer’s outcome is then unaffected by the other: the two masking sets are disjoint, and by account-representation uniqueness neither transfer’s new accounts can appear in the other’s masking set. The object states after the pair of steps therefore agree in either order, and neither step writes a register, so the shared state at 𝐶 · 𝑝 · 𝑞 equals that at 𝐶 · 𝑞 · 𝑝. The two configurations are not indistinguishable to 𝑝 and 𝑞 themselves, whose transfer responses carry the current account set and hence reveal the order; but they are indistinguishable to every other process. Since 𝑛 ≥ 3, choose a spectator 𝑠 ∉ {𝑝, 𝑞} and run it alone from each configuration. By wait-freedom 𝑠 decides in both runs, and indistinguishability makes the two decisions equal; yet every extension of 𝐶 · 𝑝 · 𝑞 decides 0, as 𝐶 · 𝑝 is 0-valent, and every extension of 𝐶 · 𝑞 · 𝑝 decides 1, as 𝐶 · 𝑞 is 1-valent. This 25

contradiction shows that 𝑝 and 𝑞 invoke 𝜏 on a common 𝜆-CUAT object with 𝑆 𝑝 ∩ 𝑆 𝑞 ≠ ∅ on that object. Iterating over ( 𝑝, 𝑞) ∈ P0 × P1 , all cross-valency pairs share a single object 𝑂; transitivity through such pairs forces every process in P to invoke 𝜏 on 𝑂, and property (ii) holds with masking sets on 𝑂.

□

In particular, applying the lemma to the critical configuration produced by Lemma 6.5 with ( 𝑝, 𝑣) gives the star specialization, with P𝑣 = {𝑝} and P1−𝑣 = P \ {𝑝}: 𝑝’s pending masking set conflicts on a common object with every other process’s pending masking set. Iterating over 𝑝 is what the one-round upper bound relies on. 6.2.1

One-round protocols

Throughout this subsection, Π denotes a wait-free one-round consensus protocol on 𝜆-CUAT objects and atomic registers: each process makes a single 𝜏-invocation and identifies a contested winner from the published CUAT state. Before its 𝜏-step a process has access only to the CUAT’s initial state and its own identity, so its masking set is determined by the protocol from these two pieces of data alone. A process may also read registers, but atomic registers have consensus number 1 [Her91] and add no synchronization power on top of 𝜆-CUAT. The analysis pairs a lower bound from constructive cliques in 𝐺 with an upper bound from iterating Lemma 6.6 over each process. Any clique of 𝐺 admits a wait-free consensus protocol of matching size, by the standard attempt-and-adopt construction. Lemma 6.7 (One-round lower bound from cliques). Let 𝐺 be a conflict graph admissible under the untraceability notion in force, and let 𝐾 = {𝑆1 , . . . , 𝑆 𝑛 } ⊆ 𝑉 (𝐺) be a clique of size 𝑛. Then there is a wait-free one-round 𝑛-consensus protocol Π over a CUAT𝜆 object in which process 𝑝 𝑖 uses masking set 𝑆𝑖 . Consequently cons ( CUAT𝜆 ) ≥ 𝜔(𝐺). Proof. Construction. Assign 𝑆𝑖 as 𝑝 𝑖 ’s masking set. Each 𝑝 𝑖 writes its input to a single-writer register 𝑟 𝑖 (proposal) and invokes 𝜏(𝑆𝑖 ) on the 𝜆-CUAT object. On success (𝜏 returns true), 𝑝 𝑖 decides its own input. On failure, 𝑝 𝑖 reads the published CUAT state to identify which masking set 𝑆 𝑗 ∈ 𝐾 has been committed, reads 𝑟 𝑗 , and decides that value. Figure 4 gives the full pseudocode; the function weak selects masking sets under weak untraceability and strong uses the projective-plane construction under strong untraceability (Section 6.2.4). Wait-freedom. The protocol contains no loops: 𝜏 is invoked once, and identification of the winner is a single inspection of the published state. Each process completes in a bounded number of steps regardless of the schedule. Validity. The decided value is either 𝑝 𝑖 ’s own input (on success) or 𝑟 𝑗 ∗ for some 𝑗 ∗ , which is 𝑝 𝑗 ∗ ’s input. Agreement. Linearize the 𝑛 𝜏-invocations on 𝐾 and let 𝑆 𝑗 ∗ ∈ 𝐾 be the first to return true. For every other 𝑆𝑖 ∈ 𝐾, 𝑆𝑖 ∩ 𝑆 𝑗 ∗ ≠ ∅ by the clique property of 𝐾; the account shared between 𝑆𝑖 and 𝑆 𝑗 ∗ is invalidated when 𝑆 𝑗 ∗ commits, so 𝜏(𝑆𝑖 ) fails. Process 𝑝 𝑖 then identifies 𝑆 𝑗 ∗ as the winner in the published state and decides 𝑟 𝑗 ∗ . Process 𝑝 𝑗 ∗ also decides 𝑟 𝑗 ∗ on success. Every process therefore decides the same value 𝑟 𝑗∗ .

□

Conversely, Lemma 6.6 turns wait-freedom into a clique witness in 𝐺.

26

Consensus from 𝜆-CUAT Shared state: 1: 𝑅[ 𝑗] for 𝑗 ∈ {1, . . . , 𝑑}, atomic registers (proposals) 2: 𝐴[ 𝑗] for 𝑗 ∈ {1, . . . , 𝑑}, atomic registers (new account sets) 3: A 𝜆-CUAT object CUAT with initial state (A0 , 𝛽0 ) where A0 = {𝑎 1 , . . . , 𝑎 𝑑+1 } (with 𝑑 ≥ 𝜆), 𝜇(𝑎 1 ) = {𝑝 1 }, 𝜇(𝑎 𝑖+1 ) = {𝑝 𝑖 } for 𝑖 ∈ {1, . . . , 𝑑}, and 𝛽0 (𝑎) = 0 for all 𝑎 ∈ A0 ; process 𝑝 1 owns 𝑎 1 which doubles as the hub account 4: An untraceability level weak ∈ {0, 1} propose(𝑣) at process 𝑝 𝑖 where 𝜇(𝑎 𝑖+1 ) = {𝑝 𝑖 }: 5: 𝑅[𝑖].write(𝑣) // Write proposal 6: 𝑆old ← masking(𝑖, 𝜆, weak) // Old masking set ′ , 0) // Generate new accounts and proof 7: (𝑆new , 𝜋) ← Compute 𝑝𝑖 (𝑆old , 𝑎 𝑖+1 , 𝑎 𝑖+1 8: 𝐴[𝑖].write(𝑆new ) // Write new account set 9: (A, 𝑏) ← CUAT.transfer(𝑆new , 𝜋) 10: if 𝑏 = TRUE then 11: return 𝑣 // Won: decide own value 12: else // Lost: identify winner by reading account sets 13: 𝑆winner ← A \ A0 // New accounts in A 14: for 𝑗 ∈ {1, . . . , 𝑑} do 15: if 𝐴[ 𝑗].read() = 𝑆winner then // Process 𝑗 won 16: return 𝑅[ 𝑗].read() // Adopt winner’s value function: masking(𝑖, 𝜆, weak) : 17: 18: 19: 20:

if weak = 1 then weak(𝑖, 𝜆) else // Strong untraceability strong(𝑖, 𝜆)

function: weak(𝑖, 𝜆) : 21: 22: 23: 24: 25: 26: 27:

𝑆 ′ ← {1} // Hub account 𝑎 1 , owned by 𝑝 1 𝑗 ← 𝑖 + 1 // Start with 𝑝 𝑖 ’s account 𝑎 𝑖+1 repeat 𝜆 − 1 times 𝑆′ ← 𝑆′ ∪ { 𝑗 } 𝑗 ← ( 𝑗 mod (𝑑 + 1)) + 1 if 𝑗 = 1 then 𝑗 ← 2 // Skip hub return 𝑆 ′

function: strong(𝑖, 𝜆) : (see [IK19]) Figure 4. Wait-free implementation of 𝑑-consensus using a 𝜆-CUAT object. Lemma 6.8 (One-round upper bound from pairwise intersection). Let Π be a wait-free one-round consensus protocol on CUAT𝜆 objects and atomic registers, with 𝐺 its conflict graph. If 𝑐𝑛(Π) ≥ 3, then 𝑐𝑛(Π) ≤ 𝜔(𝐺). Proof. Suppose, for contradiction, that Π solves 𝑛-consensus for 𝑛 = 𝜔(𝐺) + 1 ≥ 3, so the largest clique of 𝐺 has size 𝑛 − 1. Write 𝑆𝑖 for the masking set used by 𝑝 𝑖 for 𝑖 = 1, . . . , 𝑛.

27

A non-conflicting pair exists. If every pair {𝑆𝑖 , 𝑆 𝑗 } conflicted, the vertices 𝑣 𝑆1 , . . . , 𝑣 𝑆𝑛 would form an 𝑛-clique in 𝐺 (Definition 6.3), contradicting 𝜔(𝐺) = 𝑛 − 1. Hence there exist processes 𝑝 ≠ 𝑞 whose masking sets 𝑆 𝑝 , 𝑆 𝑞 do not conflict: either they sit on distinct 𝜆-CUAT objects or they share no index on a common object. Critical configuration with different valencies. Set 𝑞’s input to 0 and every other input to 1, and apply Lemma 6.5: there is a reachable critical configuration 𝐶 at which 𝐶 · 𝑞 is 0-valent, 𝐶 · 𝑠 is 1-valent for every 𝑠 ≠ 𝑞, and every process’s pending step is its first 𝜏-invocation. At a critical configuration neither pending step is a register operation [Her91]: a read leaves the shared state unchanged, writes to distinct registers commute, and of two writes to one register the second overwrites the first, leaving a configuration indistinguishable to every process except the overwritten writer. Each case makes two oppositely valent successors indistinguishable to some process that decides in both. The pending step of 𝑝 at 𝐶 is therefore a 𝜏-invocation carrying 𝑆 𝑝 , and likewise for 𝑞 with 𝑆 𝑞 . In particular, 𝐶 · 𝑝 is 1-valent and 𝐶 · 𝑞 is 0-valent. Equal shared state. Since 𝑆 𝑝 and 𝑆 𝑞 do not conflict, 𝜏(𝑆 𝑝 ) and 𝜏(𝑆 𝑞 ) act on disjoint state: the outcome of each is unaffected by the other, and the 𝜆-CUAT object(s) reach the same state after the pair in either order. Neither step modifies a register, so the shared state at 𝐶 · 𝑝 · 𝑞 equals that at 𝐶 · 𝑞 · 𝑝. The two orders are visible to 𝑝 and 𝑞 themselves, whose transfer responses carry the current account set, but to no other process. A spectator derives the contradiction. Since 𝑛 ≥ 3, choose 𝑠 ∉ {𝑝, 𝑞} and run it alone from each of the two configurations. By wait-freedom 𝑠 decides in both, and because its local state and the shared state agree in the two configurations, it decides the same value 𝑣 in both. But every extension of 𝐶 · 𝑝 · 𝑞 decides 1 because 𝐶 · 𝑝 is 1-valent, forcing 𝑣 = 1, while every extension of 𝐶 · 𝑞 · 𝑝 decides 0 because 𝐶 · 𝑞 is 0-valent, forcing 𝑣 = 0, a contradiction. The contradiction rules out 𝑐𝑛(Π) > 𝜔(𝐺), so 𝑐𝑛(Π) ≤ 𝜔(𝐺).

□

Combining the two bounds gives equality. Theorem 6.9 (One-round consensus number). If Π is a one-round protocol on CUAT𝜆 with 𝑐𝑛(Π) ≥ 3, then 𝑐𝑛(Π) = 𝜔(𝐺). Consequently, the largest 𝑛 achievable by a one-round 𝑛-consensus protocol on CUAT𝜆 equals the supremum of 𝜔(𝐺) over conflict graphs admissible under the untraceability notion in

force. Proof. Combine Lemma 6.7 and Lemma 6.8.

□

Theorem 6.9 matches the one-round upper bound to 𝜔(𝐺), and the bound is the limit of the one-round regime: a committed 𝜏 permanently invalidates its masking set, and the surviving masking sets that conflicted with it can no longer fire, so the conflict graph is exhausted after one round of contention. Two follow-up questions remain. Section 6.2.2 relaxes the one-round restriction and asks how far multi-round protocols can push the consensus number past 𝜔(𝐺). Sections 6.2.3 and 6.2.4 take the orthogonal question of how large 𝜔(𝐺) can be made under each untraceability notion: weak untraceability leaves 𝜔(𝐺) unbounded, while strong untraceability caps it at 𝜆2 − 𝜆 + 1.

28

6.2.2

Multi-round protocols

A multi-round protocol lets each process invoke 𝜏 more than once and adapt later invocations to earlier outcomes. The structural gain over 𝜔(𝐺) is not larger cliques but a weaker requirement on the conflict graph: pairwise intersection at the critical configuration can be relaxed once the pending processes split by valency, so the next 𝜏-round need only enforce conflict across the partition. Lemma 6.6 already extracts such a partition P = P0 ⊔ P1 with a complete bipartite intersection between the two sides. At incidence 2 a 𝜆-block biclique supports 2𝜆 vertices, exceeding the one-round upper bound. Theorem 6.10 (Upper bound). A wait-free binary consensus protocol Π over CUAT𝜆 objects and atomic
registers can solve consensus among at most max 2, 2𝜆(𝑟 (Π) − 1) processes. Proof. Suppose Π solves 𝑛-consensus, so |P | = 𝑛; for 𝑛 ≤ 2 the bound is immediate, so assume 𝑛 ≥ 3. Take 𝐶, P0 , P1 as in Lemma 6.6; the partition covers P, and cross-valency pending masking sets conflict on a common CUAT𝜆 object. Two processes across the valency partition use distinct pending masking sets. Were 𝑝 ∈ P0 and 𝑞 ∈ P1 to share 𝑆 𝑝 = 𝑆 𝑞 = 𝑆, the winner-identification rule of Section 6.2.1 would match the single committed 𝑆 in the published CUAT state to both 𝑝 and 𝑞, and the two valency classes (which decide 0 and 1 respectively in any extension, by property (i) of Lemma 6.6) would have no consistent register to adopt, breaking agreement. Same-side sharing is benign: two processes in the same valency class agree on the decision value of any extension, so adopting either’s register is consistent. Hence {𝑣 𝑆 𝑝 : 𝑝 ∈ P0 } ∩ {𝑣 𝑆𝑞 : 𝑞 ∈ P1 } = ∅ in 𝑉 (𝐺), and property (ii) of Lemma 6.6 yields a complete bipartite subgraph 𝐾 | P0 |, | P1 | ⊆ 𝐺 between these two vertex sets. Fix 𝑝 ∈ P0 . Each account 𝑎 ∈ 𝑆 𝑝 has incidence at most 𝑟 (Π) in 𝐺, hence lies in at most 𝑟 (Π) − 1 vertices distinct from 𝑣 𝑆 𝑝 . Summing over the 𝜆 accounts of 𝑆 𝑝 , at most 𝜆(𝑟 (Π) − 1) distinct vertices in 𝑉 (𝐺) are adjacent to 𝑣 𝑆 𝑝 via a shared account. Since every 𝑣 𝑆𝑞 with 𝑞 ∈ P1 is adjacent to 𝑣 𝑆 𝑝 , we get |P1 | ≤ 𝜆(𝑟 (Π) − 1). By symmetry |P0 | ≤ 𝜆(𝑟 (Π) − 1), so 𝑛 = |P0 | + |P1 | ≤ 2𝜆(𝑟 (Π) − 1).

□

In the following two sections, we discuss how the incidence number 𝑟 (Π) relates to privacy and, through it, to the consensus number. 6.2.3

Weak untraceability

Under weak untraceability the incidence number 𝑟 (Π) is unconstrained: an account may appear in every masking set without violating per-transaction anonymity. The hub construction of Figure 4 (function weak) places the shared hub account 𝑎 1 (owned by 𝑝 1 ) in all 𝑑 masking sets, making the conflict graph a 𝑑-clique, and satisfies weak untraceability for any 𝑑. By Theorem 6.9 this yields 𝑐𝑛(Π) = 𝑑, so the consensus number is unbounded. Theorem 6.11 (Consensus number under weak untraceability). For every 𝑑 ≥ 2, CUAT𝜆− supports a wait-free one-round 𝑑-consensus protocol. Hence cons ( CUAT𝜆− ) = ∞. Proof. We instantiate Lemma 6.7 on the hub family and verify that the family satisfies weak untraceability. Construction. Use the hub function of Figure 4: every masking set 𝑆𝑖 contains the hub 𝑎 1 (owned by 𝑝 1 ) together with 𝜆 − 1 further accounts chosen cyclically. Since all 𝑑 sets share 𝑎 1 , they pairwise intersect, so 29

𝐾 = {𝑆1 , . . . , 𝑆 𝑑 } is a 𝑑-clique in the conflict graph 𝐺. Lemma 6.7 then implements wait-free 𝑑-consensus on this clique. Weak untraceability. The cryptographic proof 𝜋 of each 𝜏-invocation is zero-knowledge: an observer of 𝜏 learns the masking set 𝑆old and the published state, but obtains no advantage over the uniform distribution on 𝑆old for the sender’s identity. Hence 𝑃(𝑎 𝑖 | 𝜏) = 1/|𝑆old | = 1/𝜆 for every 𝑎 𝑖 ∈ 𝑆old , regardless of 𝑑 or of the hub-account structure. Therefore Π achieves wait-free 𝑑-consensus and preserves weak untraceability for every 𝑑 ≥ 2.

□

The hub construction leaves 𝑎 1 in every masking set, so a history-aware adversary identifies it as a near-certain decoy; this statistical leakage motivates strong untraceability. 6.2.4

Strong untraceability

Strong untraceability requires anonymity against adversaries that observe the full transaction history. The masking sets of a consensus protocol pairwise intersect, so Corollary 4.5 applies and they must have uniform incidence. We first combine this condition with the clique characterization of one-round consensus, and then with the bipartite-intersection characterization of unrestricted protocols. The one-round bound is an extremal question about set systems, and a projective plane is its extremal case. A one-round protocol needs its 𝑛 masking sets to pairwise intersect, while uniform incidence forbids any account from carrying more of those intersections than the others. Suppose every account lies in 𝑚 of the sets, and write 𝑣 for the number of accounts. Counting incidences two ways gives 𝑣𝑚 = 𝑛𝜆,



and an account of incidence 𝑚 accounts for at most 𝑚2 of the 𝑛2 pairs that must meet, so 𝑛2 ≤ 𝑣 𝑚2 . Substituting 𝑣 = 𝑛𝜆/𝑚 leaves 𝑛 ≤ 𝜆(𝑚 − 1) + 1, and 𝑚 ≤ 𝜆, so 𝑛 ≤ 𝜆2 − 𝜆 + 1. Equality forces both counts to be tight at once: every account lies in exactly 𝜆 sets, and every two sets meet in exactly one account, since a second shared account would spend incidence on a pair already covered. Those two conditions are the axioms of a projective plane of order 𝜆 − 1, read with accounts as points and masking sets as lines. A family of size 𝜆2 − 𝜆 + 1 is therefore a projective plane, and the bound is attained exactly when one exists. Theorem 6.12 (One-round upper bound under strong untraceability). A wait-free one-round consensus protocol on CUAT+𝜆 can solve consensus among at most 𝜆2 − 𝜆 + 1 processes. Proof. Let Π be a 𝑑-consensus protocol of the class of Section 6.2.1, with 𝑑 ≥ 3, and let 𝐹 = {𝑆1 , . . . , 𝑆 𝑑 } be its masking sets. By Lemma 6.8 they lie on a common object and form a 𝑑-clique in 𝐺, so they pairwise intersect; each has size 𝜆 by definition; and by Corollary 4.5 strong untraceability forces every account of Ð 𝑖 𝑆 𝑖 to lie in a common number 𝑚 of them. Füredi [Für81] and Ihringer and Kupavskii [IK19] bound such symmetric pairwise-intersecting 𝜆-uniform families by |𝐹 | ≤ 𝜆2 − 𝜆 + 1. Hence 𝑑 ≤ 𝜆2 − 𝜆 + 1.

□

The upper bound is attained by a projective plane whenever 𝜆 − 1 is a prime power. Theorem 6.13 (Projective-plane construction). If 𝜆 − 1 is a prime power, CUAT+𝜆 supports a wait-free one-round (𝜆2 −𝜆 +1)-consensus protocol, instantiated by attempt-and-adopt on the line set of PG(2, 𝜆 −1). Proof. Let 𝑞 = 𝜆 − 1. The projective plane PG(2, 𝑞) has 𝜆2 − 𝜆 + 1 points and the same number of lines; each line contains 𝜆 = 𝑞 + 1 points, every two lines meet in exactly one point, and each point lies

30

on exactly 𝜆 lines [IK19]. Interpreting points as accounts and lines as masking sets yields a 𝜆-uniform pairwise-intersecting family of size 𝜆2 − 𝜆 + 1 over 𝜆2 − 𝜆 + 1 accounts, of uniform incidence 𝜆, hence admissible under strong untraceability by Theorem 4.4. To run the attempt-and-adopt protocol of Lemma 6.7 (Figure 4) on this family, each of the 𝜆2 − 𝜆 + 1 processes must be assigned a distinct masking set containing one of that process’s accounts. This is a perfect-matching problem in the bipartite graph between accounts and masking sets, with an edge for each containment. Each account appears in exactly 𝜆 masking sets and each masking set contains exactly 𝜆 accounts, so the graph is 𝜆-regular; König’s theorem [Wes00] yields a perfect matching. Lemma 6.7 then implements (𝜆2 − 𝜆 + 1)-consensus on this family.

□

For other 𝜆 no plane exists, and the one we have cannot be cut down to size: if a sub-family of 𝑛 lines still covering all 𝜆2 − 𝜆 + 1 points had uniform incidence 𝑚, then (𝜆2 − 𝜆 + 1)𝑚 = 𝑛𝜆, and 𝜆2 − 𝜆 + 1 ≡ 1 (mod 𝜆) makes the two factors coprime, forcing 𝜆 | 𝑚, hence 𝑚 = 𝜆 and 𝑛 = 𝜆2 − 𝜆 + 1, the whole line set. Uniform incidence is not hereditary, so a smaller family has to be built directly. We use a cyclic construction. In a family of translates {𝐷 + 𝑡}𝑡 ∈Z𝑛 , an account 𝑥 lies in 𝐷 + 𝑡 exactly when 𝑡 ∈ 𝑥 − 𝐷, so its incidence is |𝐷 | for any choice of 𝐷. Pairwise intersection then reduces to a condition on the differences of 𝐷, which can be satisfied at size ⌊𝜆2 /2⌋ for every 𝜆. Theorem 6.14 (Cyclic construction). For every 𝜆 ≥ 3, CUAT+𝜆 supports a wait-free one-round ⌊𝜆2 /2⌋consensus protocol, instantiated by attempt-and-adopt on the translates of a cyclic difference cover. Proof. Put 𝑔 = ⌊𝜆/2⌋, ℎ = ⌈𝜆/2⌉ and 𝑛 = ⌊𝜆2 /2⌋, so that 𝑔 + ℎ = 𝜆 and, checking both parities (𝜆 = 2𝑘 gives 𝑔ℎ = 𝑘 2 and 𝑛 = 2𝑘 2 ; 𝜆 = 2𝑘 + 1 gives 𝑔ℎ = 𝑘 (𝑘 + 1) and 𝑛 = 2𝑘 (𝑘 + 1)), 𝑔ℎ = ⌊𝜆/2⌋ ⌈𝜆/2⌉ =

𝑛 . 2

(1)

Identify both the accounts and the processes with Z𝑛 , let 𝜇(𝑥) = {𝑥}, and set 𝐷 = {0, 1, . . . , 𝑔 − 1} ∪ {𝑔, 2𝑔, . . . , ℎ𝑔} ⊆ Z𝑛 , a run of 𝑔 consecutive residues followed by the first ℎ multiples of 𝑔. The masking-set family is the set of translates 𝑆𝑡 = 𝐷 + 𝑡, 𝑡 ∈ Z𝑛 , with 𝑆𝑡 assigned to process 𝑡. Size and incidence. The run and the multiples are disjoint, as 𝑗 𝑔 ≥ 𝑔 > 𝑔 − 1 for 𝑗 ≥ 1, and 𝑔, 2𝑔, . . . , ℎ𝑔 are distinct as ℎ𝑔 = 𝑛/2 < 𝑛; hence |𝐷 | = 𝑔 + ℎ = 𝜆 and every translate has size 𝜆. For 𝑥 ∈ Z𝑛 we have Ð 𝑥 ∈ 𝐷 + 𝑡 iff 𝑡 ∈ 𝑥 − 𝐷, so 𝑥 lies in exactly |𝐷 | = 𝜆 translates. The account set is 𝑡 𝑆𝑡 = Z𝑛 and every account has incidence 𝜆, so the family is admissible under strong untraceability by Theorem 4.4. Pairwise intersection. As (𝐷 + 𝑡) ∩ (𝐷 + 𝑡 ′ ) ≠ ∅ iff 𝑡 ′ − 𝑡 ∈ 𝐷 − 𝐷, the translates pairwise intersect iff 𝐷 − 𝐷 = Z𝑛 . The run contributes [−(𝑔 − 1), 𝑔 − 1], and for each 𝑗 ∈ {1, . . . , ℎ} the multiple 𝑗 𝑔 contributes 𝑗 𝑔 − {0, . . . , 𝑔 − 1} = [( 𝑗 − 1)𝑔 + 1, 𝑗 𝑔]; these ℎ blocks tile [1, ℎ𝑔] without gaps. Hence 𝐷 − 𝐷 ⊇ [−ℎ𝑔, ℎ𝑔], which modulo 𝑛 is [0, 𝑛/2] ∪ [𝑛/2, 𝑛 − 1] = Z𝑛 because ℎ𝑔 = 𝑛/2 by (1). So the 𝑛 vertices 𝑣 𝑆𝑡 form an 𝑛-clique of 𝐺. Distinct masking sets. The translates are pairwise distinct iff the stabilizer 𝐻 = ⟨𝑑⟩ of 𝐷 is trivial. As 0 ∈ 𝐷 and 𝐷 is a union of 𝐻-cosets, 𝐻 ⊆ 𝐷 ⊆ [0, ℎ𝑔] = [0, 𝑛/2]; from 𝑛 − 𝑑 ∈ 𝐻 we get 𝑛 − 𝑑 ≤ 𝑛/2, so

31

𝑑 ≥ 𝑛/2. If 𝑑 = 𝑛/2 then 𝐷 is a union of pairs {𝑥, 𝑥 + 𝑛/2}, which lie in [0, 𝑛/2] only for 𝑥 = 0, forcing 𝐷 = {0, 𝑛/2} and 𝜆 = 2, excluded. Hence 𝑑 = 𝑛 and 𝐻 is trivial. Assignment. Since 0 ∈ 𝐷, process 𝑡 owns the account 𝑡 ∈ 𝑆 𝑡 , so 𝑡 ↦→ 𝑆 𝑡 gives each process a distinct masking set containing one of its own accounts, and Lemma 6.7 applied to this 𝑛-clique implements wait-free one-round 𝑛-consensus.

□

Combining the upper bound with the two constructions yields the following. Corollary 6.15 (One-round consensus number under strong untraceability). For every 𝜆 ≥ 3, the largest 𝑛 for which CUAT+𝜆 supports a wait-free one-round 𝑛-consensus protocol satisfies ⌊𝜆2 /2⌋ ≤ 𝑛 ≤ 𝜆2 − 𝜆 + 1, with equality on the right when 𝜆 − 1 is a prime power. Proof. The upper bound is Theorem 6.12, the lower bound is Theorem 6.14, and the prime-power case is Theorem 6.13.

□

We now turn to unrestricted protocols, where the demand on the masking sets is weaker. A one-round protocol needs every pair of its sets to meet; by Lemma 6.6 an unrestricted protocol needs this only across the two valency classes, leaving the pairs inside a class free. Fewer pairs must be covered at the same incidence, so the bound is larger. It follows by counting how much of the complete bipartite intersection a single account can cover under uniform incidence. Theorem 6.16 (Upper bound under strong untraceability). For every 𝜆 ≥ 2, a wait-free consensus protocol on CUAT+𝜆 can solve consensus among at most 4⌊𝜆/2⌋ ⌈𝜆/2⌉ processes, that is, at most 𝜆2 if 𝜆 is even and at most 𝜆2 − 1 if 𝜆 is odd. Proof. Suppose Π solves 𝑛-consensus; if 𝑛 ≤ 2 the bound holds trivially, since 4⌊𝜆/2⌋ ⌈𝜆/2⌉ ≥ 4, so assume 𝑛 ≥ 3. Take 𝐶, P0 , P1 , and 𝑂 as in Lemma 6.6, and write 𝑠 = |P0 | + |P1 |. Uniformity first bounds the incidence of an account by 𝜆: if 𝑑 masking sets of size 𝜆 cover 𝑣 accounts with common incidence 𝑚, then 𝑣𝑚 = 𝑑𝜆 by double counting, while Fisher’s inequality gives 𝑑 ≤ 𝑣, and hence 𝑚 ≤ 𝜆. For every account 𝑎 on 𝑂, let 𝑖 𝑎 and 𝑗 𝑎 count its incidences among the pending masking sets of P0 Í and P1 , respectively. Every cross-class pair must share an account, so |P0 | · |P1 | ≤ 𝑎 𝑖 𝑎 𝑗 𝑎 . Moreover, Í 𝑎 (𝑖 𝑎 + 𝑗 𝑎 ) = 𝑠𝜆 and 𝑖 𝑎 + 𝑗 𝑎 ≤ 𝜆. Put   𝜆2 /4  𝜆 even, 𝜅 := max 𝑖 𝑗 = ⌊𝜆/2⌋ ⌈𝜆/2⌉ =  𝑖+ 𝑗 ≤𝜆  (𝜆2 − 1)/4 𝜆 odd, 𝑖, 𝑗 ≥0  attained when 𝑖 and 𝑗 are balanced and 𝑖 + 𝑗 = 𝜆. For every 𝑖 + 𝑗 ≤ 𝜆, we have 𝑖 𝑗 ≤ (𝜅/𝜆) (𝑖 + 𝑗), and Í Í therefore 𝑎 𝑖 𝑎 𝑗 𝑎 ≤ (𝜅/𝜆) 𝑎 (𝑖 𝑎 + 𝑗 𝑎 ) = 𝑠𝜅. The balanced input assignment forces |P0 | = |P1 | = 𝑠/2 at Í 2 the critical configuration, so 𝑠4 = |P0 | · |P1 | ≤ 𝑎 𝑖 𝑎 𝑗 𝑎 ≤ 𝑠 𝜅, giving 𝑠 ≤ 4𝜅 = 4⌊𝜆/2⌋ ⌈𝜆/2⌉, i.e., 𝜆2 for even 𝜆 and 𝜆2 − 1 for odd.

□

To attain the bound, split the processes into two groups of 𝑛 = ⌊𝜆2 /2⌋. Each group first uses Theorem 6.14 to agree on one value. A second round then selects between the two group values. The masking sets of this round need only intersect across the groups, which motivates the following definition.

32

Definition 6.17 (Cross-cover family). Let P0 and P1 be disjoint sets of 𝑛 processes each. A cross-cover family of order 𝑛 assigns to every 𝑟 ∈ P0 ∪ P1 a masking set 𝑆𝑟(2) on one common CUAT𝜆 object 𝑂 such that (i) |𝑆𝑟(2) | = 𝜆 for every 𝑟; (ii) every account of 𝑂 lies in exactly 𝜆 of the sets 𝑆𝑟(2) ; and (2) (iii) 𝑆 (2) 𝑝 ∩ 𝑆 𝑞 ≠ ∅ for every ( 𝑝, 𝑞) ∈ P0 × P1 .

Condition (iii) is exactly the bipartite intersection that Lemma 6.6 extracts from any wait-free protocol at a critical configuration; conditions (i) and (ii) are imposed by strong untraceability. No intersection is required within a class, so a cross-cover family may exceed the one-round bound. Lemma 6.18 (Composition). Suppose CUAT+𝜆 supports a wait-free one-round 𝑛-consensus protocol, and that a cross-cover family of order 𝑛 exists. Then CUAT+𝜆 supports a wait-free 2𝑛-consensus protocol, so cons ( CUAT+𝜆 ) ≥ 2𝑛.

Proof. Let P0 , P1 be the two classes of the cross-cover family, of 𝑛 processes each, and give each class its own CUAT𝜆 object on which to run the one-round protocol. Round 1. Each class runs the one-round 𝑛-consensus protocol among its own 𝑛 processes, on its own object. Every process of class 𝑣 thus decides a common class value 𝑤 𝑣 , which is the input of some process of that class, and the round is admissible under strong untraceability by hypothesis. Round 2. Each process 𝑟 writes 𝑤 𝑣 to a single-writer register and invokes 𝜏 on its masking set 𝑆𝑟(2) on the shared object 𝑂. By condition (iii) of Definition 6.17, the masking sets of any cross-class pair meet, so once some transfer commits, every transfer of the other class finds a shared account invalidated and fails. All committing transfers therefore belong to one class, the winning class, and at least one commits, namely the first to linearize. A process that commits decides its own class value; one that fails inspects the published state of 𝑂, identifies a committed masking set, reads off the class of its owner, and adopts that class’s value from the corresponding register. Every process thus decides the winning class’s value 𝑤 𝑣 , which round 1 made common to that class and which is some process’s input, so agreement and validity hold; both rounds are loop-free and wait-free, so the composition is. Round 2 is admissible under strong untraceability by conditions (i) and (ii) of Definition 6.17 with Theorem 4.4.

□

Lemma 6.18 requires its two ingredients at the same order, so the cross-cover family must match the order that Theorem 6.14 supplies for the first round. It remains to construct one at order ⌊𝜆2 /2⌋, which the two parities require us to do separately. Lemma 6.19 (Cross-cover families exist at order ⌊𝜆2 /2⌋). For every 𝜆 ≥ 3 there is a cross-cover family of order 𝑛 = ⌊𝜆2 /2⌋. Proof. Even 𝜆: a grid. Here 𝑛 = 𝜆2 /2. Partition P0 into 𝜆 blocks 𝑃1 , . . . , 𝑃𝜆 of size 𝜆/2, and likewise P1 into 𝑄 1 , . . . , 𝑄 𝜆 ; this is possible since |P𝑣 | = 𝑛 = 𝜆 · (𝜆/2). On a new object instance take accounts {𝑎 𝑖 𝑗 }𝑖, 𝑗 ∈ [𝜆] and set 𝑆 (2) 𝑝 = {𝑎 𝑖 𝑗 : 𝑗 ∈ [𝜆]} ( 𝑝 ∈ 𝑃𝑖 ),

𝑆 𝑞(2) = {𝑎 𝑖 𝑗 : 𝑖 ∈ [𝜆]} (𝑞 ∈ 𝑄 𝑗 ). 33

Each masking set is a row or a column of the grid, hence of size 𝜆, giving (i). The account 𝑎 𝑖 𝑗 lies in 𝑆 (2) 𝑝 exactly for the 𝜆/2 processes 𝑝 ∈ 𝑃𝑖 and in 𝑆 𝑞(2) exactly for the 𝜆/2 processes 𝑞 ∈ 𝑄 𝑗 , so its incidence is 𝜆/2 + 𝜆/2 = 𝜆, giving (ii). For a cross pair ( 𝑝, 𝑞) ∈ 𝑃𝑖 × 𝑄 𝑗 , row 𝑖 and column 𝑗 meet exactly in 𝑎 𝑖 𝑗 , giving (iii). Figure 5 illustrates the construction for 𝜆 = 4. 𝑄1

𝑄2

𝑄3

𝑄4

𝑃1

𝑎 11

𝑎 12

𝑎 13

𝑎 14

𝑃2

𝑎 21

𝑎 22

𝑎 23

𝑎 24

𝑃3

𝑎 31

𝑎 32

𝑎 33

𝑎 34

𝑃4

𝑎 41

𝑎 42

𝑎 43

𝑎 44

𝑆 (2) 𝑝 , 𝑝 ∈ 𝑃2

𝑆 𝑞(2) , 𝑞 ∈ 𝑄 3

Figure 5. The even cross-cover construction for 𝜆 = 4. Processes in block 𝑃𝑖 ⊆ P0 use row 𝑖, and processes in 𝑄 𝑗 ⊆ P1 use column 𝑗. The highlighted masking sets intersect in 𝑎 23 . Each block contains 𝜆/2 = 2 processes, so every account has two row incidences and two column incidences, for total incidence 𝜆 = 4. Odd 𝜆: a cyclic design. Here 𝑛 = (𝜆2 − 1)/2, and an account cannot split evenly between the classes. The construction alternates accounts of the two types (𝑔, ℎ) and (ℎ, 𝑔), arranged cyclically so that even and odd differences are covered separately. Set 𝑔=

𝜆−1 , 2

ℎ=

𝜆+1 , 2

𝑛 = 2𝑔ℎ =

𝜆2 − 1 , 2

so that 𝑔 + ℎ = 𝜆 and, 𝑔 and ℎ being consecutive integers, gcd(𝑔, ℎ) = 1. Identify both classes with Z𝑛 , writing P0 = P1 = Z𝑛 , and take all arithmetic modulo 𝑛. On a new object instance 𝑂 place 2𝑛 accounts 𝑐 𝑡 , 𝑑𝑡 for 𝑡 ∈ Z𝑛 , specifying each by the processes whose masking set contains it: writing 𝑋 (·) ⊆ P0 and 𝑌 (·) ⊆ P1 for those two sides, 𝑔−1

𝑌 (𝑐 𝑡 ) = {𝑡 + 2𝑔 𝑗 } ℎ−1 𝑗=0 ,

𝑋 (𝑐 𝑡 ) = {𝑡 + 2ℎ𝑖}𝑖=0 , 𝑋 (𝑑𝑡 ) = {𝑡 + 2𝑔 𝑗 } ℎ−1 𝑗=0 ,

𝑔−1

𝑌 (𝑑𝑡 ) = {𝑡 + 1 + 2ℎ𝑖}𝑖=0 .

Equivalently, 𝑐 𝑡 occupies the rectangle 𝑋 (𝑐 𝑡 ) × 𝑌 (𝑐 𝑡 ) of the cross-class grid P0 × P1 , and 𝑑𝑡 the rectangle 𝑋 (𝑑𝑡 ) × 𝑌 (𝑑𝑡 ). Accordingly 𝑆 𝑥(2) = {𝑐 𝑡 : 𝑥 ∈ 𝑋 (𝑐 𝑡 )} ∪ {𝑑𝑡 : 𝑥 ∈ 𝑋 (𝑑𝑡 )} for 𝑥 ∈ P0 , and symmetrically on the other side. Sizes (i) and incidence (ii). Fix 𝑥 ∈ P0 . Then 𝑥 ∈ 𝑋 (𝑐 𝑡 ) iff 𝑡 = 𝑥 − 2ℎ𝑖 for some 𝑖 ∈ {0, . . . , 𝑔 − 1}, giving exactly 𝑔 values of 𝑡, and 𝑥 ∈ 𝑋 (𝑑𝑡 ) iff 𝑡 = 𝑥 − 2𝑔 𝑗 for some 𝑗 ∈ {0, . . . , ℎ − 1}, giving ℎ; hence |𝑆 𝑥(2) | = 𝑔 + ℎ = 𝜆, and symmetrically |𝑆 𝑦(2) | = ℎ + 𝑔 = 𝜆 for 𝑦 ∈ P1 . Each account’s incidence is the size of its rectangle’s two sides, 𝑔 + ℎ = 𝜆 for 𝑐 𝑡 and ℎ + 𝑔 = 𝜆 for 𝑑𝑡 . Cross-pair cover (iii). We show the stronger statement that every pair (𝑥, 𝑦) ∈ P0 × P1 lies in exactly one account. The argument for both parities of the difference 𝑦 − 𝑥 uses the same observation: as gcd(𝑔, ℎ) = 1, 34

the map (𝑖, 𝑗) ↦→ 𝑔 𝑗 − ℎ𝑖 mod 𝑔ℎ is a bijection [𝑔] × [ℎ] → Z𝑔ℎ , since reducing it modulo 𝑔 leaves −ℎ𝑖 with ℎ invertible, recovering 𝑖, symmetrically modulo ℎ recovers 𝑗, and the Chinese remainder theorem combines the two. The differences realized inside 𝑐 𝑡 are {2(𝑔 𝑗 − ℎ𝑖)} and those inside 𝑑𝑡 are {1 + 2(ℎ𝑖 − 𝑔 𝑗)}, for 𝑖 ∈ [𝑔], 𝑗 ∈ [ℎ]. Doubling the bijection therefore makes the former a bijection onto the even residues of Z2𝑔ℎ and the latter one onto the odd residues, so 𝑐 𝑡 realizes each even difference exactly once and 𝑑𝑡 each odd difference exactly once. As 𝑡 ranges over Z𝑛 , the unique pair inside 𝑐 𝑡 realizing a given even difference shifts cyclically through all 𝑛 pairs of that difference, and likewise for 𝑑𝑡 on odd differences. Every pair has one parity or the other, so it lies in exactly one account, and in particular 𝑆 𝑥(2) ∩ 𝑆 𝑦(2) ≠ ∅. Figure 6 shows this cover for 𝜆 = 3.

□

P0

𝑦=0

𝑦=1

𝑦=2

𝑦=3

𝑥=0

𝑐0

𝑑0

𝑐0

𝑑2

𝑥=1

𝑑3

𝑐1

𝑑1

𝑐1

𝑥=2

𝑐2

𝑑0

𝑐2

𝑑2

𝑥=3

𝑑3

𝑐3

𝑑1

𝑐3

P1

𝑐 𝑡 : even 𝑦 − 𝑥 𝑑𝑡 : odd 𝑦 − 𝑥

Figure 6. The odd cyclic cross-cover for 𝜆 = 3, where 𝑔 = 1, ℎ = 2, and 𝑛 = 4. Rows and columns represent processes 𝑥 ∈ P0 and 𝑦 ∈ P1 . Each cell names the unique account shared by the corresponding pair. Accounts 𝑐 𝑡 cover even cyclic differences and accounts 𝑑𝑡 cover odd differences. Each process is incident to three accounts, and each account occurs in three masking sets. The construction is available for every 𝜆 ≥ 3 and, by Lemma 6.18, matches the upper bound. Theorem 6.20 (Consensus number under strong untraceability). For every 𝜆 ≥ 2, cons ( CUAT+𝜆 ) ≤ 4⌊𝜆/2⌋ ⌈𝜆/2⌉, and for every 𝜆 ≥ 3 equality holds:   𝜆2  + cons ( CUAT𝜆 ) = 4⌊𝜆/2⌋ ⌈𝜆/2⌉ =  𝜆2 − 1

if 𝜆 is even, if 𝜆 is odd.



Proof. The upper bound is Theorem 6.16. For the lower bound, let 𝑛 = ⌊𝜆2 /2⌋. Lemma 6.19 supplies a cross-cover family of order 𝑛 and Theorem 6.14 the one-round 𝑛-consensus protocol each class runs, so Lemma 6.18 yields a wait-free 2𝑛-consensus protocol on CUAT+𝜆 . Finally 2𝑛 = 2⌊𝜆2 /2⌋ = 4⌊𝜆/2⌋ ⌈𝜆/2⌉ matches the upper bound.

□

The prime-power condition is therefore confined to attaining the one-round upper bound through a projective plane, the exact multi-round value carrying no arithmetic condition on 𝜆. Moreover, for every 𝜆 ≥ 3, 4⌊𝜆/2⌋ ⌈𝜆/2⌉ > 𝜆2 − 𝜆 + 1; hence multi-round protocols are strictly more powerful than one-round protocols under strong untraceability. Having determined cons ( CUAT+𝜆 ) through the conflict graph structure, we now examine how that structure affects parallelization opportunities and fairness guarantees. 35

7

Parallelization and fairness

Sections 5 and 6 read the conflict graph at a single critical configuration, where it bounds how many processes can agree. Taken over a whole workload instead, the same graph governs how that workload executes: its chromatic number is the number of sequential rounds a batch of transfers requires, and its independence number is how many of them commit in one round. The conflict structure also settles fairness. No CUAT𝜆 implementation is starvation-free under an unfair scheduler, while LUAT𝜆 is, which locates the asymmetry between the two objects in the scheduler rather than in the consensus number. The section closes with the attack surface these quantities expose and the mitigations available against it. Fix a workload of transfers T and let 𝐺 T = (𝑉, 𝐸) denote its workload conflict graph: 𝑉 contains one vertex per transfer (including distinct transfers that use the same masking set), and two vertices are adjacent when their masking sets share an index. Adjacent transfers cannot both succeed concurrently, since the second to commit finds at least one account invalidated by the first; non-adjacent transfers act on disjoint account indices and commute. Between sequential rounds, a pending transfer is rebased by replacing every account representation in its masking set with the current representation of the same index. This preserves the intended logical transfer while making its masking set valid after earlier rounds. Theorem 7.1 (Chromatic number and sequential complexity). In an execution without external interference in which every transfer remains balance-eligible when rebased, the chromatic number 𝜒(𝐺 T ) equals the minimum number of sequential rounds required to execute every transfer in T successfully, when pending transfers may be rebased between rounds. Proof. (≤) A proper 𝑘-coloring of 𝐺 T partitions 𝑉 into 𝑘 independent sets 𝑉1 , . . . , 𝑉𝑘 . Before round 𝑖, rebase the transfers in 𝑉𝑖 onto the current account representations and schedule them concurrently. No two transfers in 𝑉𝑖 share an index, so their 𝜏-invocations act on pairwise disjoint accounts and all succeed. (≥) Conversely, take any successful schedule using 𝑘 rounds. Assign to each transfer the index of its round. Two transfers in the same round cannot share an index, since rebasing preserves indices and one of the two would otherwise fail. The assignment is therefore a proper 𝑘-coloring, so 𝜒(𝐺 T ) ≤ 𝑘. Hence no schedule uses fewer than 𝜒(𝐺 T ) rounds.

□

The chromatic number quantifies sequential rounds; the dual quantity, the maximum independent set, quantifies parallel throughput. Theorem 7.2 (Maximum independent set and parallel throughput). The independence number 𝛼(𝐺 T ) equals the maximum number of transfers from T that can execute in parallel in a single round with all succeeding. Proof. (≥) Any independent set 𝐼 ⊆ 𝑉 is a set of pairwise non-conflicting transfers, so the masking sets of 𝐼 are pairwise disjoint in the index sense; their 𝜏-invocations commute and all succeed when scheduled concurrently. Hence 𝛼(𝐺 T ) transfers fit in one round. (≤) Conversely, any set of transfers that all succeed concurrently must be pairwise non-conflicting (the preceding theorem’s argument applied to one round) and so forms an independent set in 𝐺 T . The maximum such set has size 𝛼(𝐺 T ).

□

36

The conflict graph also exposes a fundamental limitation: when processes use overlapping masking sets, at most one transfer succeeds, forcing coordination. While CUAT provides wait-freedom, this only guarantees termination. Transfers may fail due to concurrent interference on overlapping masking sets, even when the invoking process has sufficient balance. This structural property enables starvation under adversarial scheduling. We consider the standard asynchronous model with an adversarial scheduler that may delay or advance any correct process arbitrarily, subject only to preserving program order within each process. Under such a scheduler, we show that CUAT cannot guarantee even minimal fairness. Specifically, no implementation can prevent starvation: an adversarial scheduler may indefinitely deny successful transfers to some processes while allowing others to succeed repeatedly. While denial-of-service attacks on randomizationbased systems, specifically Quisquis, have been conjectured by Bünz et al. [Bün+20], we prove this impossibility formally. Definition 7.3 (Starvation-freedom). An implementation of an untraceable asset-transfer object is starvation-free if, for every correct process 𝑝, every infinite execution in which 𝑝 invokes infinitely many eligible transfers contains infinitely many successful invocations by 𝑝. Eligibility is evaluated at invocation: the sender account is owned by 𝑝, its balance covers the chosen value, and the masking set is valid. For CUAT𝜆 , successive invocations may follow the current representations of the same logical accounts through rerandomization; for LUAT𝜆 , they may spend successive unspent accounts owned by 𝑝. This notion is deliberately minimal: it requires neither bounded waiting nor proportional success rates, only that a process which persistently attempts transfers and is frequently eligible cannot be starved indefinitely. Theorem 7.4 (Impossibility of starvation-freedom). No CUAT𝜆 implementation can guarantee starvationfreedom under an asynchronous, unfair scheduler. Specifically, there exists a schedule in which one correct process 𝑝★ succeeds infinitely often along the rerandomized lineage of a masking set 𝑆, while another correct contender on that lineage is starved: its infinitely many invocations all return FALSE. This holds even when balances pose no fundamental limit, since zero-value transfers (𝑣 = 0) keep 𝑝★ perpetually eligible. Proof. Fix a masking set 𝑆 = {𝑎 1 , . . . , 𝑎 𝜆 } with two distinct accounts 𝑎, 𝑎★ ∈ 𝑆 owned by processes 𝑝 and 𝑝★, so 𝜇(𝑎) = {𝑝} and 𝜇(𝑎★) = {𝑝★ }. Let 𝑏, 𝑏★ ∈ 𝑆 be arbitrary destinations. We construct an infinite execution in rounds 𝑟 = 1, 2, . . . where both processes repeatedly attempt transfers on the current representations of these logical accounts, and the scheduler resolves the race in favor of 𝑝★ every round. To avoid cumbersome indices, within each round we write 𝑆, 𝑎, 𝑎★, 𝑏, 𝑏★ for those current representations. Round 𝑟. Process 𝑝 invokes 𝜏𝑟 = transfer(𝑆 ′𝑝 , 𝜋 𝑝 ) with 𝜋 𝑝 = (𝑆, 𝑎, 𝑏, 𝑣, 𝑝) for some 𝑣 ≤ 𝛽(𝑎). At invocation, 𝑆 is valid and the transfer is eligible. The scheduler pauses 𝑝 before its linearization point and lets 𝑝★ complete its zero-value transfer 𝜏𝑟★ = transfer(𝑆★′ , 𝜋★) with witness 𝜋★ = (𝑆, 𝑎★, 𝑏★, 0, 𝑝★). This invocation succeeds: 𝑆 ⊆ A holds at its linearization point, and 𝛽(𝑎★) ≥ 0 trivially. It invalidates all of 𝑆 and publishes the newly generated masking set 𝑆★′ , so the post-state has 𝑆 ∩ A = ∅. The scheduler now resumes 𝑝. Because 𝑆 ∩ A = ∅ at 𝜏𝑟 ’s linearization point, the precondition 𝑆 ⊆ A fails and 𝜏𝑟 returns false. At the start of round 𝑟 + 1, 𝑝 rebases its next invocation onto the latest valid masking set containing the 37

current descendant of 𝑎, and the pattern repeats. The scheduler iterates the same protocol indefinitely. Why 𝑝★ stays eligible. 𝑝★’s value parameter is 𝑣★ = 0, so its balance is preserved across rounds. Its accounts after each round are replaced by the rerandomization of 𝑆. Hence 𝑝★ never runs out of eligible transfers, and the schedule is well-defined for all 𝑟 ≥ 1. Conclusion. 𝑝★ succeeds infinitely often (one success per round) while every invocation of 𝑝 returns false. Starvation arises not from balance exhaustion or crash failure, but from the unfair scheduling of an adversary who can always insert 𝑝★’s commit before 𝑝’s on the shared masking set.

□

The impossibility is specific to the constant-state object. Its linear-state counterpart is starvation-free, for the same reason that its consensus number does not depend on 𝜆 (Corollary 5.9): a LUAT transfer consumes one account rather than its whole masking set, so a competitor cannot invalidate it. Theorem 7.5 (LUAT guarantees starvation-freedom). Every LUAT𝜆 implementation is starvation-free. If a correct process repeatedly invokes transfers spending distinct unspent accounts it owns, with masking sets valid at invocation, then infinitely many of those invocations succeed, under any asynchronous scheduler. Proof. Let 𝑝 repeatedly invoke transfers, the 𝑟-th spending an account 𝑎𝑟 it owns whose nullifier 𝜈𝑟 = Nullify (𝑎𝑟 ) has never entered the deny-set. We show each such invocation succeeds. Its preconditions at the linearization point are: 𝑆𝑟 ⊆ Aallow , which holds because 𝑆𝑟 was valid at invocation and the allow-set only grows; 𝑝 ∈ 𝜇(𝑎𝑟 ), which is local to 𝑝; 𝜈𝑟 ∉ N , which holds because only a transfer spending 𝑎𝑟 can add 𝜈𝑟 , distinct accounts have distinct nullifiers by collision-resistance of Nullify, and no other process owns 𝑎𝑟 ; Anew,𝑟 contains only previously unused representations, by account-representation uniqueness; and the balance condition, which holds because a transfer never alters balances on the existing allow-set. Every precondition is therefore insensitive to concurrent activity, so the invocation succeeds regardless of the schedule, and all infinitely many of them do.

□

The two objects differ in what a scheduler can revoke. Under LUAT the deny-set is monotone and a nullifier is consumed only by an owner of its account, so a process that is eligible remains eligible; under CUAT𝜆 a competitor’s commit invalidates the entire masking set, and eligibility is exactly what the scheduler controls. The state growth of Section 5.3 is what buys this, since spent accounts are never reclaimed and a pending transfer’s masking set cannot be invalidated. Constant state and starvation-freedom are thus in tension, and 𝜆 does not mediate it in either direction. Escaping the CUAT𝜆 conflict is moreover not sufficient for asynchronous progress. Anonymous Zether [Bün+20] makes invalidation sender-local and so admits no competitor-driven starvation, yet bounds its deny-set by expiring nullifiers at epoch boundaries, which lets a scheduler that defers inclusion past every boundary starve a process just as effectively. Theorem 7.5 rests on eligibility being irrevocable once held, and a deadline revokes it no less than a competitor does. The three theorems above support three correlated attack vectors against an honest batch. • Throughput attack. By submitting transfers whose masking sets intersect honest ones, an adversary can increase 𝜒(𝐺 T ) and hence the number of sequential rounds required to commit the enlarged workload. Although adding vertices cannot decrease 𝛼(𝐺 T ), adversarial transfers that a scheduler admits in a round can exclude adjacent honest transfers from that round and thereby reduce honest throughput.

38

• Starvation attack. On any chosen masking set, an adversary in concert with an unfair scheduler can starve the honest contenders by issuing repeated zero-value transfers. The attacker’s eligibility is renewed each round without cost. • Amplification through masking-set incidence. Increasing 𝜆 gives each adversarial transfer more account indices through which it may conflict with honest transfers, but its actual reach is determined by the incidence of those indices in the workload. Strong untraceability regularizes this incidence rather than eliminating it, so privacy and contention remain coupled through the conflict graph. Bünz et al. [Bün+20] conjectured this attack pattern against Quisquis; the three theorems characterize it precisely. Instantiations. In a deployment, a masking set is an anonymity set or ring, invalidation is the publication of a nullifier or key image, and a conflict is the rejection of a transfer whose inputs another transfer has already consumed. Sui [Bla+23] and Zef [Bau+22] commit transfers on disjoint accounts in parallel and invoke the BFT layer only on contention; 𝜒(𝐺) and 𝛼(𝐺) bound what that architecture yields once the transferred object is untraceable rather than public, and Theorem 7.4 denies its fast path starvation-freedom. Anonymous Zether [Bün+20] is a documented case of a design that met this conflict and avoided it. Its authors first consider incrementing a nonce for every account of the anonymity set, and observe that a transfer is then rejected whenever another transfer touches one of its accounts first, which is exactly an edge of 𝐺. They reject that scheme and derive the nonce from the sender’s secret key instead, so a transfer consumes only its own sender’s nonce and leaves the rest of the set spendable. Invalidation becomes sender-local, transfers commute, and the object is LUAT𝜆 rather than CUAT𝜆 . The nonce set is a deny-set, discarded at each epoch boundary, so the state stays bounded without account replacement. The price is a concurrency bound: the nonce set admits one nonce per account per epoch, so each account has exactly one transfer in flight at a time and the epoch length fixes its throughput. This is the per-account form of the rate limiting listed below, adopted here to bound the deny-set rather than to resolve contention. The contrast with LUAT𝜆 is visible in the same setting. A Monero ring or a Zcash note-commitment set is referenced but not consumed, so two transfers sharing decoys both commit and the conflict graph has no edges; a repeated key image or nullifier is a double spend rather than contention. This is the deployed form of the separation of Section 5.2.3: the masking set carries privacy in both objects, but only in CUAT𝜆 does it also carry synchronization. The proof of Theorem 7.4 uses three ingredients: a wait-free implementation, a scheduler that decides the order of steps, and transfers that a process may repeat at no cost. A deployment that wants starvation-freedom must weaken one of them. The main options are the following. • Synchrony assumptions. Under a scheduler with bounded step delays, or under any fair scheduler, an adversary can no longer take unboundedly many steps between two steps of its victim, which is what the proof needs; the progress guarantee then holds only as long as the timing assumption does. • Per-transfer fees. Charging for each attempt, as Bitcoin and Ethereum do, limits how many transfers an adversary can issue, but honest users pay the fee as well. • Scheduler with first-contender tracking. Recording which transfer reached a masking set first, by timestamp or sequence number, breaks the symmetric race the proof relies on and keeps wait-freedom, but the recorded order reveals timing. • Per-set rate limiting. Allowing a masking set to be attempted only a fixed number of times per time

39

window stops an adversary from repeating attempts on it, but restricts honest users in the same way. • Obstruction- or lock-freedom with randomized backoff. Replacing wait-freedom by a weaker progress condition [HLM03] gives starvation-freedom with high probability, but no longer guarantees that every operation terminates. Each option drops a different requirement, and none of them keeps all three ingredients. Practical implications. The quantities 𝜒(𝐺 T ) and 𝛼(𝐺 T ) depend on the workload, not on the object alone, and a deployment can act on them. At a fixed 𝜆, it chooses which transfers are batched together and in what order, and so changes both quantities. It does not choose the range they can take: strong untraceability forces uniform incidence, and uniform incidence keeps the conflict graph dense. Fairness cannot be tuned at all. By Theorem 7.4 a deployment has to accept one of the options above, and each of them gives up asynchrony, wait-freedom, a fee-free interface, timing privacy, or the equal treatment of honest users. A system that wants to keep all five should not use its anonymity mechanism to bound the state: LUAT𝜆 has consensus number 2 for every 𝜆, is starvation-free, and by Theorem 5.12 its storage can be reclaimed without additional coordination. Both families pay for sender privacy; they differ in whether they pay in storage or in synchronization.

8

Conclusion

We have located both families of untraceable cryptocurrency in the consensus hierarchy. The comparison amounts to a trade-off between state and synchronization. The linear-state object LUAT𝜆 , which models Zcash and Monero, has consensus number 2 independently of 𝜆, and max(𝑘, 2) when 𝑘 processes share an account. Its transfers on distinct accounts commute, but their responses expose enough of the resulting deny-set to distinguish their positions in the linearization order and solve two-process consensus. This information, absent from standard asset transfer, accounts for the floor at 2. The object is starvation-free, and the partitioning object that garbage-collects its state is equivalent to fetch-and-add and hence also of consensus number 2, so garbage collection carries no synchronization cost. Drawing the partition from a randomness beacon, as resistance to grinding requires, leaves that number unchanged and trades the ordering rule for an assumption on the number of correct processes. The cost of LUAT𝜆 is storage. The constant-state object CUAT𝜆 , which models Quisquis and similar systems, removes that cost. Under weak untraceability it has unbounded consensus number already with one-round protocols, via a hub-account family. Under strong untraceability we prove an equivalence: the object satisfies strong untraceability on a history exactly when any two accounts sharing a masking set appear in the same number of the masking sets occurring in that history. This uniformity caps the one-round upper bound at 𝜆2 − 𝜆 + 1, attained by the line set of PG(2, 𝜆 − 1) when 𝜆 − 1 is a prime power, and caps cons ( CUAT+𝜆 ) at 4⌊𝜆/2⌋ ⌈𝜆/2⌉. The latter bound we attain for every 𝜆 ≥ 3, composing a per-class one-round protocol built from a cyclic difference cover with a grid or cyclic cross-cover family, so cons ( CUAT+𝜆 ) = 𝜆2 for even 𝜆 and 𝜆2 − 1 for odd, with no arithmetic condition on 𝜆. The same cyclic construction gives the only one-round lower bound available when 𝜆 − 1 is not a prime power, placing the one-round regime between ⌊𝜆2 /2⌋ and 𝜆2 − 𝜆 + 1. Finally, CUAT𝜆 cannot guarantee starvation-freedom under asynchronous scheduling: an unfair scheduler starves any process via repeated zero-value transfers on its masking set.

40

Both objects satisfy the same uniformity characterization, which locates the difference between them. Untraceability constrains which masking sets either object may use; cons ( LUAT𝜆 ) does not depend on that choice, whereas cons ( CUAT+𝜆 ) is determined by it, because a LUAT transfer names its masking set as decoys while a CUAT transfer consumes it. Privacy is thus not by itself costly in synchronization. It becomes costly when the anonymity mechanism is also made to carry the state bound, at a price quadratic in the privacy parameter. Several directions remain open. • Other privacy mechanisms. We analyze masking-set untraceability, in its linear-state and constantstate forms. Mix nets, ORAM-style designs and related mechanisms fall outside both objects, and their synchronization cost has to be determined separately. • Designs between the two objects. LUAT𝜆 has linear state and consensus number 2, and CUAT+𝜆 has constant state and consensus number 4⌊𝜆/2⌋ ⌈𝜆/2⌉. Designs whose state grows sublinearly in the number of transfers, through batched revocation or hierarchical commitments, lie between the two and are not yet placed in the hierarchy. Anonymous Zether [Bün+20] occupies part of the gap: it keeps the LUAT𝜆 semantics and consensus number 2, and bounds its deny-set by one epoch of activity. It pays in concurrency rather than in state, since an epoch-scoped nullifier admits one nonce per account per epoch, so each user has one transfer in flight and the epoch length fixes per-account throughput. Whether the gap can be closed without such a cap, and without the synchrony that epochs require, is open. • Fairness under weaker assumptions. Theorem 7.4 assumes wait-freedom, an asynchronous scheduler, and transfers that cost nothing to repeat, and Section 7 lists the ways to give up one of them. Which relaxation buys starvation-freedom at the smallest price is open, and in particular whether obstructionor lock-freedom [HLM03] with randomized backoff gives starvation-freedom with high probability without weakening untraceability. • Authenticated data structures. Both objects are maintained on structures whose concurrent behavior is itself unsettled: Merkle trees for the allow-set, and accumulators for membership proofs. Their updates and proof computations are specified sequentially, and how much of that maintenance can proceed without agreement is not known. Christ and Bonneau [CB23] bound the storage and proof-update cost of such structures; the corresponding question for synchronization is open. Our results measure privacy the way the consensus hierarchy measures any other requirement, by where the object that provides it lands. On that scale, sender untraceability is free only as long as it is not also made to bound the state; where it is, the consensus number is quadratic in 𝜆.

References [AGC24]

Jayamine Alupotha, Mathieu Gestin, and Christian Cachin. “Nopenena Untraceable Payments: Defeating Graph Analysis with Small Decoy Sets”. In: IACR Cryptol. ePrint Arch. (2024), p. 903. url: https://eprint.iacr.org/2024/903.

[Alp+21]

Orestis Alpos, Christian Cachin, Giorgia Azzurra Marson, and Luca Zanolini. “On the Synchronization Power of Token Smart Contracts”. In: 41st IEEE International Conference on Distributed Computing Systems, ICDCS 2021, Washington DC, USA, July 7-10, 2021.

41

IEEE, 2021, pp. 640–651. doi: 10.1109/ICDCS51616.2021.00067. url: https://doi. org/10.1109/ICDCS51616.2021.00067. [AT20]

Kurt M. Alonso and The Monero Community. Zero to Monero: Second Edition — Second Edition: First Principles and Cryptonote Cryptography. Version 2.0.0, April 2020. 2020. url: https://web.getmonero.org/library/Zero-to-Monero-2-0-0.pdf.

[Bau+22]

Mathieu Baudet, Alberto Sonnino, Mahimna Kelkar, and George Danezis. Zef: Low-latency, Scalable, Private Payments. arXiv:2201.05671. https://arxiv.org/abs/2201.05671. 2022.

[Ben+14]

Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, and Madars Virza. “Zerocash: Decentralized Anonymous Payments from Bitcoin”. In: 2014 IEEE Symposium on Security and Privacy, SP 2014, Berkeley, CA, USA, May 18-21, 2014. IEEE Computer Society, 2014, pp. 459–474. doi: 10.1109/SP.2014.36. url: https://doi.org/10.1109/SP.2014.36.

[Bla+23]

Sam Blackshear, Andrey Chursin, George Danezis, Anastasios Kichidis, Lefteris KokorisKogias, Xun Li, Mark Logan, Ashok Menon, Todd Nowacki, Alberto Sonnino, Brandon Williams, and Lu Zhang. Sui Lutris: A Blockchain Combining Broadcast and Consensus. arXiv:2310.18042. https://arxiv.org/abs/2310.18042. 2023.

[Bün+20]

Benedikt Bünz, Shashank Agrawal, Mahdi Zamani, and Dan Boneh. “Zether: Towards Privacy in a Smart Contract World”. In: Financial Cryptography and Data Security - 24th International Conference, FC 2020, Kota Kinabalu, Malaysia, February 10-14, 2020 Revised Selected Papers. Ed. by Joseph Bonneau and Nadia Heninger. Vol. 12059. Lecture Notes in Computer Science. Springer, 2020, pp. 423–443. doi: 10.1007/978-3-030-51280-4\_23. url: https://doi.org/10.1007/978-3-030-51280-4%5C_23.

[CB23]

Miranda Christ and Joseph Bonneau. “Limits on Revocable Proof Systems, With Implications for Stateless Blockchains”. In: Financial Cryptography and Data Security - 27th International Conference, FC 2023, Bol, Brač, Croatia, May 1-5, 2023, Revised Selected Papers, Part II. Ed. by Foteini Baldimtsi and Christian Cachin. Vol. 13951. Lecture Notes in Computer Science. Springer, 2023, pp. 54–71. doi: 10 . 1007 / 978 - 3 - 031 - 47751 - 5 \ _4. url: https://doi.org/10.1007/978-3-031-47751-5%5C_4.

[Cho+23]

Sherman S. M. Chow, Christoph Egger, Russell W. F. Lai, Viktoria Ronge, and Ivy K. Y. Woo. “On Sustainable Ring-Based Anonymous Systems”. In: 36th IEEE Computer Security Foundations Symposium, CSF 2023, Dubrovnik, Croatia, July 10-14, 2023. IEEE, 2023, pp. 568–583. doi: 10.1109/CSF57540.2023.00035. url: https://doi.org/10.1109/ CSF57540.2023.00035.

[CW25]

Christian Cachin and François-Xavier Wicht. “Toxic Decoys: A Path to Scaling PrivacyPreserving Cryptocurrencies”. In: Proc. Priv. Enhancing Technol. 2025.4 (2025), pp. 926– 943. doi: 10.56553/POPETS-2025-0165. url: https://doi.org/10.56553/popets2025-0165.

42

[Dai+18]

Eli Daian, Giuliano Losa, Yehuda Afek, and Eli Gafni. “A Wealth of Sub-Consensus Deterministic Objects”. In: 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15-19, 2018. Ed. by Ulrich Schmid and Josef Widder. Vol. 121. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, 17:1–17:17. doi: 10.4230/LIPICS.DISC.2018.17. url: https://doi.org/10.4230/LIPIcs.DISC. 2018.17.

[Egg+22]

Christoph Egger, Russell W. F. Lai, Viktoria Ronge, Ivy K. Y. Woo, and Hoover H. F. Yin. “On Defeating Graph Analysis of Anonymous Transactions”. In: Proc. Priv. Enhancing Technol. 2022.3 (2022), pp. 538–557. doi: 10.56553/POPETS-2022-0085. url: https: //doi.org/10.56553/popets-2022-0085.

[Fau+19]

Prastudy Fauzi, Sarah Meiklejohn, Rebekah Mercer, and Claudio Orlandi. “Quisquis: A New Design for Anonymous Cryptocurrencies”. In: Advances in Cryptology - ASIACRYPT 2019 25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan, December 8-12, 2019, Proceedings, Part I. Ed. by Steven D. Galbraith and Shiho Moriai. Vol. 11921. Lecture Notes in Computer Science. Springer, 2019, pp. 649– 678. doi: 10.1007/978-3-030-34578-5\_23. url: https://doi.org/10.1007/9783-030-34578-5%5C_23.

[FGR23]

Davide Frey, Mathieu Gestin, and Michel Raynal. “The Synchronization Power (Consensus Number) of Access-Control Objects: the Case of AllowList and DenyList”. In: 37th International Symposium on Distributed Computing, DISC 2023, October 10-12, 2023, L’Aquila, Italy. Ed. by Rotem Oshman. Vol. 281. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, 21:1–21:23. doi: 10.4230/LIPICS.DISC.2023.21. url: https: //doi.org/10.4230/LIPIcs.DISC.2023.21.

[Für81]

Zoltán Füredi. “Maximum degree and fractional matchings in uniform hypergraphs”. In: Combinatorica 1.2 (1981), pp. 155–162.

[Gif79]

David K. Gifford. “Weighted Voting for Replicated Data”. In: Proceedings of the Seventh Symposium on Operating System Principles, SOSP 1979, Asilomar Conference Grounds, Pacific Grove, California, USA, 10-12, December 1979. Ed. by Michael D. Schroeder and Anita K. Jones. ACM, 1979, pp. 150–162. doi: 10 . 1145 / 800215 . 806583. url: https://doi.org/10.1145/800215.806583.

[Gue+22]

Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovic, and Dragos-Adrian Seredinschi. “The consensus number of a cryptocurrency”. In: Distributed Comput. 35.1 (2022), pp. 1–15. doi: 10.1007/S00446-021-00399-2. url: https://doi.org/10. 1007/s00446-021-00399-2.

[Her91]

Maurice Herlihy. “Wait-Free Synchronization”. In: ACM Trans. Program. Lang. Syst. 13.1 (1991), pp. 124–149. doi: 10.1145/114005.102808. url: https://doi.org/10.1145/ 114005.102808.

[HFP02]

Timothy L. Harris, Keir Fraser, and Ian A. Pratt. “A Practical Multi-word Compare-and-Swap Operation”. In: Distributed Computing, 16th International Conference, DISC 2002, Toulouse, France, October 28-30, 2002 Proceedings. Ed. by Dahlia Malkhi. Vol. 2508. Lecture Notes

43

in Computer Science. Springer, 2002, pp. 265–279. doi: 10.1007/3-540-36108-1\_18. url: https://doi.org/10.1007/3-540-36108-1%5C_18. [HLM03]

Maurice Herlihy, Victor Luchangco, and Mark Moir. “Obstruction-Free Synchronization: Double-Ended Queues as an Example”. In: 23rd International Conference on Distributed Computing Systems (ICDCS 2003). IEEE Computer Society, 2003, pp. 522–529.

[HW87]

Maurice Herlihy and Jeannette M. Wing. “Axioms for Concurrent Objects”. In: Conference Record of the Fourteenth Annual ACM Symposium on Principles of Programming Languages, Munich, Germany, January 21-23, 1987. ACM Press, 1987, pp. 13–26. doi: 10.1145/41625. 41627. url: https://doi.org/10.1145/41625.41627.

[IK19]

Ferdinand Ihringer and Andrey Kupavskii. “Regular intersecting families”. In: Discrete Applied Mathematics 270 (2019), pp. 142–152. issn: 0166-218X. doi: https://doi.org/ 10.1016/j.dam.2019.07.009. url: https://www.sciencedirect.com/science/ article/pii/S0166218X19303257.

[Mie+13]

Ian Miers, Christina Garman, Matthew Green, and Aviel D. Rubin. “Zerocoin: Anonymous Distributed E-Cash from Bitcoin”. In: 2013 IEEE Symposium on Security and Privacy, SP 2013, Berkeley, CA, USA, May 19-22, 2013. IEEE Computer Society, 2013, pp. 397–411. doi: 10.1109/SP.2013.34. url: https://doi.org/10.1109/SP.2013.34.

[Mös+18]

Malte Möser, Kyle Soska, Ethan Heilman, Kevin Lee, Henry Heffan, Shashvat Srivastava, Kyle Hogan, Jason Hennessey, Andrew Miller, Arvind Narayanan, and Nicolas Christin. “An Empirical Analysis of Traceability in the Monero Blockchain”. In: Proc. Priv. Enhancing Technol. 2018.3 (2018), pp. 143–163. doi: 10.1515/POPETS-2018-0025. url: https: //doi.org/10.1515/popets-2018-0025.

[MS25]

Varun Madathil and Alessandra Scafuro. “sfPri tt FHEsfte: Achieving Full-Privacy in Account-Based Cryptocurrencies is Possible”. In: Advances in Cryptology - ASIACRYPT 2025 - 31st International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, VIC, Australia, December 8-12, 2025, Proceedings, Part VII. Ed. by Goichiro Hanaoka and Bo-Yin Yang. Vol. 16251. Lecture Notes in Computer Science. Springer, 2025, pp. 199–229. doi: 10.1007/978- 981- 95- 5122- 4\_7. url: https://doi.org/10.1007/978-981-95-5122-4%5C_7.

[The24]

The Monero Project. Full-Chain Membership Proofs. Published 27 April 2024. 2024. url: https://www.getmonero.org/2024/04/27/fcmps.html.

[Tho79]

Robert H. Thomas. “A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases”. In: ACM Trans. Database Syst. 4.2 (1979), pp. 180–209. doi: 10.1145/ 320071.320076. url: https://doi.org/10.1145/320071.320076.

[Wes00]

Douglas B West. Introduction to graph theory. 2nd ed. Upper Saddle River, NJ: Prentice Hall, Aug. 2000.

44