💻 computer science

The Consensus Number of Untraceable Cryptocurrencies

This paper analyzes the synchronization costs of sender untraceability in cryptocurrencies by formalizing two designs—linear (LUAT) and constant-state (CUAT) untraceable asset transfer objects—and determining that while LUAT achieves a low consensus number of 2 at the expense of growing storage, CUAT offers constant state but incurs unbounded or quadratic consensus numbers and lacks starvation-freedom depending on the strength of the untraceability guarantee.

Original authors: Christian Cachin, David Lehnherr, Juan Villacis, François-Xavier Wicht

Published 2026-07-24

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Christian Cachin, David Lehnherr, Juan Villacis, François-Xavier Wicht

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Great Digital Heist: Hiding in Plain Sight

Imagine you are in a crowded room where everyone is whispering secrets. In the digital world of cryptocurrencies, this room is the "ledger," a giant public notebook that records who sent money to whom. Usually, this notebook is like a glass wall: you can see exactly who paid whom, even if you don't know their real names. But what if you wanted to make a payment without anyone knowing which person in the crowd actually handed over the cash? This is the challenge of "sender untraceability."

To solve this, cryptographers use a trick called a "masking set." Imagine you are the one paying, but you stand in a group of ten friends. You all hold up identical-looking envelopes. To an outside observer, it looks like any one of the ten friends might have paid, but they can't tell which one. The paper we are exploring dives deep into the mechanics of these groups. It asks a very specific, almost philosophical question: If we want to hide the sender inside a group, does that hiding act change how the group works? Specifically, does it make it harder for the group to agree on what happened next? The authors are looking at the "consensus number," a fancy way of measuring how much coordination is needed to get things done. Think of it as a "traffic jam meter": a low number means cars can drive past each other easily; a high number means they have to stop, wait, and argue about who goes first.

The Two Ways to Hide: The "Keep-It-All" vs. The "Swap-It-All"

The paper compares two different strategies for managing these groups of friends (masking sets) to hide the sender. Let's call them the Linear Strategy and the Constant Strategy.

The Linear Strategy (LUAT): The Ever-Growing Guest List
Imagine a party where, every time someone pays, they don't just hide in a group; they also leave a permanent note on the wall saying, "Someone from this group paid!" The party never deletes these notes. The list of "potential payers" (the allow-set) keeps growing, and the list of "people who already paid" (the deny-set) keeps growing too.

The Good News: This method is surprisingly chill. Even though the list gets huge, the "traffic jam meter" stays very low. The authors prove that no matter how big the group of friends is, the system only needs to coordinate for 2 people at a time. It's like a dance floor where everyone can move freely; even if you bump into someone, you don't need to stop the whole party to figure out who moved first.
The Catch: The party wall gets covered in sticky notes forever. The storage space needed to remember everyone who might have paid grows linearly with every transaction. It's like trying to remember every single person who ever walked through a door, even if they left years ago.

The Constant Strategy (CUAT): The Magic Re-Randomization
Now, imagine a different party. When someone pays, they don't just leave a note. Instead, the entire group of friends instantly changes their clothes, their names, and their identities. The old group vanishes, and a brand new group appears. This keeps the total number of people in the room constant, so the "wall" never gets messy. This is the method used by systems like Quisquis.

The Catch: This is where things get chaotic. Because the entire group changes, if two people try to pay at the same time and their groups overlap (even just one person in common), they crash into each other. They can't both succeed.
The Result: The "traffic jam meter" explodes. The authors found that the coordination needed here grows quadratically with the size of the group. If your group has 10 people, the coordination needed is roughly 100. If you have 100 people, you need coordination for 10,000! It's like a game of musical chairs where if two groups share even one chair, the whole game has to stop and restart to figure out who sits where.

The Privacy vs. Progress Trade-Off

The paper's biggest discovery is a strict trade-off. You can have privacy, but you have to pay for it in one of two currencies: Storage or Synchronization.

Pay in Storage (Linear Strategy): You keep the history forever. The system stays fast and easy to coordinate (consensus number of 2), but your hard drive fills up.
Pay in Synchronization (Constant Strategy): You keep the history small and clean. But to do that, you force the system to coordinate massively. The more people you try to hide among, the harder it is to get everyone to agree on the order of events.

The authors also looked at a "super-privacy" mode called Strong Untraceability. This is like having a detective who watches the entire history of the party, not just one moment. They noticed that if you want to hide the sender perfectly over a long history, the groups of friends must be arranged in a very specific, mathematical pattern (like a perfect grid or a projective plane). If you don't arrange them perfectly, the detective can guess who paid by seeing who shows up in too many groups. When you force this perfect arrangement, the "traffic jam meter" hits a specific, high ceiling based on the group size.

The Starvation Problem: The Mean Scheduler

Finally, the paper tackles a dark side of the Constant Strategy: Starvation.
Imagine a bully at the party (an "adversarial scheduler") who controls the music. In the Linear Strategy, if you are ready to pay, you can always pay eventually, even if the bully tries to stop you. But in the Constant Strategy, because the whole group changes, the bully can keep hitting the "reset" button on your specific group.
The authors proved that in the Constant Strategy, a bully can make one person pay forever while making another person wait forever, even if the waiting person has money and is ready to go. The waiting person keeps trying, but every time they try, the bully resets the group just before they can finish. This is a "denial of service" that is mathematically impossible to prevent if the system is designed to keep the state small.

The Bottom Line

This paper doesn't just say "one is better than the other." It maps out the exact cost of your choices.

If you want a system that never runs out of space and is fair to everyone, you must accept that the list of past transactions will grow forever (Linear).
If you want a system that stays small and tidy, you must accept that it will get incredibly slow and complicated to coordinate as you add more people, and it might let a bully starve some users out (Constant).

The authors have proven these limits with mathematical certainty. They showed that you cannot have the best of both worlds: you cannot have a small, tidy history and a fast, fair, easy-to-coordinate system at the same time. The universe of cryptocurrencies demands a price for privacy, and this paper tells you exactly how much you have to pay.

Technical Summary: The Consensus Number of Untraceable Cryptocurrencies

Problem Statement
Cryptocurrencies aim to provide sender untraceability, hiding the specific account funding a transaction within a set of candidate accounts known as a "masking set." While cryptographic definitions of privacy are well-established, the synchronization costs and progress guarantees of these mechanisms remain under-analyzed. The paper addresses a fundamental design choice in untraceable asset transfer: whether to retain spent accounts in a growing ledger (linear state) or to invalidate and replace the entire masking set upon transfer (constant state). The authors investigate how this choice impacts the system's synchronization power, specifically its consensus number, and its ability to guarantee fairness (starvation-freedom).

Methodology
The authors formalize two distinct designs as shared-memory objects parameterized by the masking-set size $\lambda$ :

Linear Untraceable Asset Transfer (LUAT): Models systems like Zcash and Monero. A transfer consumes one account from a masking set and appends a nullifier to a deny-set, while the allow-set grows. The masking set acts as a decoy set; overlapping sets do not conflict.
Constant Untraceable Asset Transfer (CUAT): Models systems like Quisquis. A transfer atomically consumes and replaces every account in its masking set with new representations. Consequently, any two transfers with intersecting masking sets cannot both succeed; overlap constitutes a conflict.

The analysis employs the consensus hierarchy [Her91], determining the consensus number (the maximum number of processes for which wait-free consensus can be solved) for these objects. The study distinguishes between two untraceability notions:

Weak Untraceability: Protects a transaction in isolation.
Strong Untraceability: Protects against an adversary observing the complete transaction history, requiring that any two accounts sharing a masking set appear in the same number of masking sets (uniform incidence).

The authors utilize conflict graphs to model synchronization constraints, where vertices represent masking sets and edges represent conflicts (shared accounts). They analyze both one-round protocols (single transaction submission) and multi-round protocols (iterative adaptation).

Key Contributions and Results

1. LUAT: Low Synchronization, High Storage

Consensus Number: The consensus number of an unshared LUAT object is exactly 2, independent of the masking-set size $\lambda$ $λ$ and the untraceability notion (weak or strong).
- This exceeds the consensus number of standard asset transfer (1) because the deny-set reveals the linearization order of transfers.
- If $k$ processes share an account, the consensus number becomes $\max(k, 2)$ .
Garbage Collection: The paper formalizes a partitioning object to garbage-collect exhausted masking sets. This object has a consensus number of 2 (implementable via fetch-and-add), meaning garbage collection adds no additional synchronization cost.
Fairness: LUAT is starvation-free. Since a transfer only consumes one account and names the rest as decoys, a competitor cannot invalidate a valid transfer by spending a different account in the same masking set.
Trade-off: The cost of LUAT is monotonic state growth (linear in the number of transfers).

2. CUAT: Bounded State, High Synchronization, No Fairness

Weak Untraceability: Under weak untraceability, the consensus number is unbounded ( $\infty$ ). A "hub" account can be included in arbitrarily many masking sets, creating arbitrarily large conflict cliques.
Strong Untraceability: This notion imposes a uniform incidence constraint: every account in a connected component of the conflict graph must appear in the same number of masking sets.
- One-Round Protocols: The consensus number is bounded between $\lfloor \lambda^2/2 \rfloor$ and $\lambda^2 - \lambda + 1$ . The upper bound is attained if $\lambda-1$ is a prime power (using projective planes).
- Multi-Round Protocols: The exact consensus number is determined as $4\lfloor \lambda/2 \rfloor \lceil \lambda/2 \rceil$ (i.e., $\lambda^2$ for even $\lambda$ , $\lambda^2-1$ for odd $\lambda$ ). This is strictly higher than the one-round bound for $\lambda \ge 3$ .
Fairness: CUAT is not starvation-free. An adversarial scheduler can indefinitely starve a process by repeatedly issuing zero-value transfers on an overlapping masking set, invalidating the victim's pending transfer before it can commit. This confirms a conjecture regarding Quisquis.
Trade-off: The cost of CUAT is high synchronization power (quadratic in $\lambda$ ) and the loss of starvation-freedom.

Significance and Claims
The paper claims to expose a hidden design choice in private payment systems that is often obscured at the cryptographic layer. The consensus hierarchy reveals that sender untraceability itself is not inherently costly in terms of synchronization. The cost arises specifically when the mechanism used to hide the sender (the masking set) is also tasked with bounding the system state.

LUAT pays for privacy in storage (growing ledger) but maintains low synchronization (consensus number 2) and fairness.
CUAT pays for privacy in synchronization and progress guarantees (quadratic consensus number, no starvation-freedom) to achieve constant state.

The authors conclude that the "price" of privacy depends on whether the anonymity mechanism is decoupled from state management. When decoupled (LUAT), privacy is "free" regarding synchronization. When coupled (CUAT), privacy incurs a quadratic synchronization cost and forfeits fairness guarantees. The paper provides exact bounds for these trade-offs, formalizing the conflict structures (cliques and bipartite intersections) that dictate the limits of parallelism and fairness in untraceable cryptocurrencies.