2026-10-03T23:39:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27859 2026-10-02T17:40:21Z ddc:004 open_access

The Consensus Number of Untraceable Cryptocurrencies Cachin, Christian Lehnherr, David Villacis, Juan Wicht, François-Xavier Consensus number untraceability privacy-preserving cryptocurrencies wait-freedom masking sets concurrent objects Privacy-preserving cryptocurrencies hide which account funds a transfer among a set of candidate accounts, called its masking set. To prevent the hidden account from being spent twice, classical schemes retain the candidates and append a nullifier that marks the spent account without revealing it. Their ledgers therefore grow with every transfer. Constant-state schemes instead consume and replace the entire masking set. Here, we study the synchronization cost of this second design. We introduce the constant untraceable asset transfer (CUAT) object. A CUAT transfer atomically replaces every account in its masking set; hence two transfers with intersecting sets cannot both succeed. We capture this contention by a conflict graph on transfer invocations, whose edges join invocations with intersecting masking sets. In one-round protocols, the relevant sets form a clique at a critical configuration. In general protocols, only sets from opposite valency classes must intersect. Under weak untraceability, which considers one transaction in isolation, CUAT has unbounded consensus number even for one-round protocols. Under strong untraceability, which considers the complete history, accounts in a common masking set must have equal incidence. This condition makes both the one-round consensus power and CUAT’s consensus number grow quadratically with the masking-set size. Cyclic and projective-plane constructions establish the corresponding one-round lower bounds, while a recursive grid construction shows that CUAT’s consensus number is exactly the square of the masking-set size. CUAT is also not starvation-free. The full version studies the complementary linear untraceable asset transfer (LUAT) object, which retains its masking set and records a nullifier. Its state grows, but its consensus number is two for every masking-set size and under either untraceability notion, and it is starvation-free. Thus LUAT pays for untraceability in storage, whereas CUAT pays in synchronization and fairness. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christian Cachin and David Lehnherr and Juan Villacis and François-Xavier Wicht 2026 Is Part Of LIPIcs, Volume 395, 8th Conference on Advances in Financial Technologies (AFT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AFT.2026.5 urn:nbn:de:0030-drops-278593 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2026.5 eng https://creativecommons.org/licenses/by/4.0/legalcode