Privacy vs. Consensus: New Paper Proves Untraceable Crypto Trade-offs

A new arXiv paper by Cachin, Lehnherr, Villacis, and Wicht formalizes the consensus properties of untraceable cryptocurrencies, separating designs into two classes: linear (LUAT) and constant-state (CUAT). LUAT retains a masking set per transfer and appends a nullifier, causing the ledger to grow linearly with each transaction. Its consensus number is 2, meaning it can solve consensus for up to 2 processes — higher than the standard asset transfer object's consensus number of 1. Importantly, LUAT is starvation-free, and partitioning accounts into fixed masking sets allows garbage collection without increasing that number.

CUAT, by contrast, consumes and replaces its entire masking set per transaction, keeping ledger state constant. This design leads to conflict when two transfers share an account. Under weak untraceability (protecting a single transaction), CUAT's consensus number is unbounded even for one-round protocols. Under strong untraceability (protecting against a full-history observer), the uniform incidence condition bounds the conflict graph, and the consensus number grows quadratically with the masking-set size. Moreover, CUAT is not starvation-free. The paper thus reveals a fundamental trade-off: LUAT pays for privacy with storage, while CUAT pays with synchronization overhead and fairness loss. These formal results have direct implications for designing next-generation privacy coins and distributed ledgers.