REVIEW 4 major objections 3 minor 13 references
The Consensus Number of Untraceable Cryptocurrencies
T0 review · 4 major / 3 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read A constant-state private payment object has quadratic consensus power in its anonymity-set size.
desk verdict The CUAT+ quadratic consensus number is false — duplicate masking sets break the upper bound — though the LUAT half is a clean contribution. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing objects are the conflict graph, whose vertices are masking sets and whose edges join sets sharing an account index, and the uniform-incidence condition that strong untraceability imposes on histories. For the one-round regime, consensus power equals the largest clique in the conflict graph; the upper bound is the extremal size of a symmetric pairwise-intersecting $\lambda$-uniform family, attained by a projective plane when $\lambda-1$ is a prime power. For unrestricted protocols the relevant structure at a critical configuration is a complete bipartite intersection between opposite valency classes rather than a clique, and the exact bound $4\lfloor\lambda/2\rfloor\lceil\lambda/2\rceil$ is reached by composing a cyclic difference cover with either a grid (even $\lambda$) or a cyclic cross-cover family (odd $\lambda$). The same conflict graph, read over a workload, also yields the chromatic-number characterization of sequential rounds, the independence-number bound on parallel throughput, and the starvation impossibility based on repeated zero-value transfers.
What would settle it
Take $\lambda=4$, where the claimed bound is 16. Allow two of the 17 processes to submit the exact same masking set and keep the remaining sets as in the paper's even grid; if attempt-and-adopt still solves wait-free 17-process consensus, Theorem 6.20 is false. More generally, checking whether the conflict graph's clique number can exceed $4\lfloor\lambda/2\rfloor\lceil\lambda/2\rceil$ under identical masking sets settles whether the distinctness assumption is load-bearing.
Extended reading notes
Core claim
Under the paper's model, the difference between untraceable payment designs is not privacy but what a transfer does to its masking set. LUAT transfers name their masking set as decoys and consume only one account, so transfers on distinct accounts commute; the deny-set reveals the transfer's position in the linearization order, giving consensus number exactly 2 (and $\max(k,2)$ when $k$ processes share an account). CUAT transfers atomically consume and replace all $\lambda$ accounts of the masking set, so overlapping sets conflict. Weak untraceability imposes no global incidence restriction and a single hub account yields arbitrarily large cliques, making $\mathrm{cons}(\mathrm{CUAT}^-_\lambda)=\infty$ already for one-round protocols. Strong untraceability holds on a history exactly when any two accounts sharing a masking set appear in the same number of masking sets in that history; this uniform-incidence constraint bounds the conflict graph, and the paper's matching constructions attain it, so $\mathrm{cons}(\mathrm{CUAT}^+_\lambda)=4\lfloor\lambda/2\rfloor\lceil\lambda/2\rceil = \lambda^2$ for even $\lambda$ and $\lambda^2-1$ for odd $\lambda$ for every $\lambda\ge 3$. The protocol achieving the lower bound runs two groups of processes through a cyclic one-round protocol and reconciles the group decisions on a cross-cover family whose sets intersect exactly across groups.
Load-bearing premise
The one-round upper-bound arguments assume that different processes never invoke the same masking set, so the conflict graph has one vertex per process and each vertex is distinct; the model never explicitly forbids duplicate masking sets, and the even-$\lambda$ cross-cover construction deliberately assigns the same row masking set to $\lambda/2$ processes within a class.
Editorial extensions
If this is right
- A constant-state private payment system modeled by CUAT cannot have a contention-free parallel commit slice larger than about $\lambda^2$ processes, so the anonymity parameter directly caps the amount of independent processing available.
- Strong untraceability adds a combinatorial constraint, uniform incidence, that is harmless for LUAT but is exactly what caps CUAT's power; privacy itself is not the cost, the coupling of privacy with state reclamation is.
- One-round submission, the way payment systems actually use CUAT, supports only between $\lfloor\lambda^2/2\rfloor$ and $\lambda^2-\lambda+1$ processes, with the upper end reachable exactly when $\lambda-1$ is a prime power.
- CUAT cannot be made starvation-free by any wait-free implementation: an unfair scheduler can always let a zero-value re-randomization win the race against a competitor's transfer on the same masking set.
- LUAT's storage growth can be garbage-collected by a $k$-partitioning object with consensus number 2, so the linear-state design pays for privacy in storage rather than in synchronization.
Reading between the lines
- A direct stress test of the upper bound is to allow duplicate masking sets in the construction: the proofs count one vertex per process and would break if two processes submit the identical set, potentially changing $4\lfloor\lambda/2\rfloor\lceil\lambda/2\rceil$.
- The quadratic dependence on $\lambda$ suggests that a constant-state deployment should keep anonymity sets small if it wants to preserve shardable parallelism; alternatively, designs that make invalidation sender-local sidestep conflict while keeping bounded state at the price of per-epoch throughput caps.
- The exact bound resembles a multi-word compare-and-swap counting argument, so one could test whether weakening strong untraceability to a bounded number of historical observations interpolates between unbounded and the quadratic value.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper formalizes two shared-memory objects for sender-untraceable cryptocurrencies: the linear untraceable asset transfer (LUAT), which retains spent accounts and appends nullifiers, and the constant untraceable asset transfer (CUAT), which consumes and replaces its whole masking set. It claims that LUAT has consensus number 2 (or max(k,2) with a shared account) regardless of the masking-set size and untraceability notion, while CUAT under strong untraceability has consensus number exactly 4*floor(lambda/2)*ceil(lambda/2) for every lambda >= 3, with weak untraceability giving unbounded consensus power already for one-round protocols. The analysis is carried out through a conflict graph on masking sets and a uniform-incidence characterization of strong untraceability, with lower bounds built from projective planes, cyclic difference covers, and grid/cyclic cross-cover families. The paper also proves that CUAT is not starvation-free whereas LUAT is, and connects these results to deployed systems such as Quisquis, Zcash, and Monero.
Significance. If the claimed exact characterization were correct, it would be a significant contribution: it would place two privacy-preserving payment designs in the consensus hierarchy, quantify the synchronization cost of strong untraceability, and separate storage costs from coordination costs. The paper has genuine strengths: the formal object definitions are clear, the LUAT results are coherent and well argued, the lower-bound constructions (projective planes, cyclic difference covers, cross-cover families) are concrete and reproducible, and the connection to real systems is useful. However, the central upper-bound theorem for CUAT under strong untraceability is invalid under the model as stated, because the model permits multiple processes to use identical masking sets while the upper-bound proofs count only distinct sets. The headline result is therefore false, and the error is load-bearing rather than cosmetic.
major comments (4)
- [§6.1 and §6.2.4 (Definitions 6.1, 6.3; Theorem 6.16)] The upper-bound proof of Theorem 6.16 is invalid because the model permits duplicate masking sets. Definition 6.1 never requires the old masking sets S_beta of different transfers to be distinct, and Definition 6.3 defines the conflict graph with one vertex per masking set, so a set reused by several processes is represented by a single vertex. The proof counts i_a and j_a as per-process incidences (multiplicities), but then bounds them by lambda using Fisher's inequality applied to the family of distinct masking sets. Once a set is reused, every account in it can have multiplicity larger than lambda while the number of distinct sets stays small; the step 'vm = d*lambda ... d <= v ... m <= lambda' mixes multiplicities with distinct-set counts and does not hold. The claimed bound on the number of processes therefore does not follow.
- [§6.2.1 (Lemma 6.8)] Lemma 6.8 assumes distinctness of the masking sets when it argues that pairwise conflict of S_1,...,S_n yields an n-clique: if S_i = S_j, the two vertices v_{S_i} and v_{S_j} coincide, so there is no n-clique. The model never forbids equality, and the paper's own constructions use it (Lemma 6.19 assigns the same row set to lambda/2 processes). Consequently the one-round upper bound of Theorem 6.12 is also false as stated: with all processes reusing one set of size lambda, every pair conflicts, but the conflict graph has only one vertex.
- [§6.2.2 (Theorem 6.10)] The proof of Theorem 6.10 contains the assertion that two processes across the valency partition use distinct pending masking sets, with the justification that identical sets would leave 'no consistent register to adopt.' This is incorrect: if two processes use the same old masking set S, at most one transfer succeeds, the response returns the fresh account set S'_winner, and the loser can match S'_winner against the registers where processes published their proposed new sets and adopt the winner's input. This is precisely the mechanism of the attempt-and-adopt protocol of Lemma 6.7. Hence the complete-bipartite-subgraph structure extracted in Lemma 6.6 is not necessary, and the upper bound on the number of processes collapses.
- [§6.1 and §4 (Definitions 6.1, 4.3; Theorem 4.4)] There is a concrete counterexample to Theorem 6.20. For any integer N and any lambda >= 2, let N processes co-own a_1 in S = {a_1,...,a_lambda}. Each p_i writes its input to R[i], publishes a distinct fresh account set S_i' in A[i], and invokes a transfer with old masking set S. Exactly one transfer linearizes first and succeeds; every other transfer fails because S is invalidated. Each loser reads the returned account set, identifies S_winner, and adopts the corresponding register value, giving wait-free N-process consensus with validity and agreement. The history is admissible under strong untraceability because every account in S has incidence N, so the uniformity condition of Theorem 4.4 is satisfied. Therefore cons(CUAT+_lambda) is unbounded for every lambda >= 2, contradicting Theorems 6.10, 6.16, and 6.20.
minor comments (3)
- [§6.2.4 (Theorem 6.12)] The bound |F| <= lambda^2 - lambda + 1 is attributed to 'Füredi [Für81] and Ihringer and Kupavskii [IK19]' but no theorem number or statement is given; please cite the exact result.
- [§6.2.4 (Theorem 6.16)] The sentence 'if d masking sets of size lambda cover v accounts with common incidence m' should specify whether d counts distinct sets or transfers; the present text is ambiguous and, as discussed above, the two readings give different bounds.
- [Figure 4] The strong() function is not specified in the figure and the text refers the reader to [IK19]; supplying the pseudocode or a precise construction would make the lower bound easier to verify.
Circularity Check
No circular derivation detected; the LUAT/CUAT consensus bounds are proved from object definitions and external combinatorial results, not from fitted parameters or self-cited targets.
full rationale
Walking the derivation chain of Theorems 5.5, 5.12, 6.9, 6.11, 6.16, and 6.20, I find no step in which a claimed prediction is identical by construction to an input, nor any load-bearing self-citation. The LUAT bounds follow from Lemma 5.2 (commuting transfers) plus the standard critical-state argument; the partitioning object is reduced to fetch-and-add (Lemma 5.11), whose consensus number is taken from Herlihy's external hierarchy. The CUAT bounds are derived from the conflict graph (Definition 6.3), Lemma 6.6's bipartite-intersection characterization, and external extremal facts (Füredi; Ihringer and Kupavskii). The lower bounds are explicit constructions (hub family, projective plane, cyclic difference cover, grid and cyclic cross-covers) with incidence verified directly from the definitions and Theorem 4.4. Theorem 4.4 itself proves an equivalence between the stated adversary model and a uniform-incidence condition; it is not a restatement of the target consensus results, and the later bounds do not assume the conclusion of Theorem 6.20. The only self-citations, e.g., [CW25] on garbage collection and beacon-based partitioning, describe an application or design and are not used to establish any consensus-number bound. The duplicate-masking-set issue raised in the reader's take is a potential correctness gap in the upper-bound proofs, not a circular reduction, and is therefore outside this pass.
Assumptions & free parameters
assumptions (4)
- domain assumption Strong untraceability is exactly characterized by uniform masking-set incidence (Theorem 4.4).
- ad hoc to paper Protocol masking sets form a simple family, i.e., different processes use distinct masking sets.
- standard math Furedi and Ihringer-Kupavskii bound on regular intersecting families is correct as cited.
- ad hoc to paper Fisher's inequality gives d <= v for the pending masking sets at a critical configuration.
Cite this review
Pith. "Pith review of The Consensus Number of Untraceable Cryptocurrencies." pith.science (2026). https://pith.science/paper/YIT5OEWD
@misc{pith2026260720929,
author = {Pith},
title = {Pith review of: The Consensus Number of Untraceable Cryptocurrencies},
year = {2026},
howpublished = {\url{https://pith.science/paper/YIT5OEWD}},
note = {Machine review of arXiv:2607.20929}
}
read the original 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 and constant untraceable asset transfer objects (LUAT and CUAT) 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 starvation-free. 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.
Figures
Figures from the paper (3 more)
Reference graph
Works this paper leans on
-
[1]
NopenenaUntraceablePayments: Defeating Graph Analysis with Small Decoy Sets
[AGC24] JayamineAlupotha,MathieuGestin,andChristianCachin.“NopenenaUntraceablePayments: 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 Contract...
work page 2024
-
[7]
Toxic Decoys: A Path to Scaling Privacy- Preserving Cryptocurrencies
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 Privacy- Preserving Cryptocurrencies”. In:Proc. Priv. Enhancing Technol.2025.4 (2025), pp. 926– 943.doi: 10.56553/POPETS-2025-0165.url: https://doi.org/10.56553/pope...
arXiv 2025
-
[121]
On Defeating Graph Analysis of Anonymous Transactions
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 (...
-
[281]
Maximum degree and fractional matchings in uniform hypergraphs
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: Combinatorica1.2 (1981), pp. 155–162. [Gif79] David K. Gifford. “Weighted Voting for Replicated Data”. I...
-
[1979]
The consensus number of a cryptocurrency
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/S0044...
-
[2013]
An Empirical Analysis of Traceability in the Monero Blockchain
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...
work page doi:10.1109/sp.2013.34.url:https://doi.org/10.1109/sp.2013.34 2018
-
[2014]
459–474.doi:10.1109/SP.2014.36.url: https://doi.org/10.1109/SP.2014.36
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 Kokoris- Kogias, Xun Li, Mark Logan, Ashok Menon, Todd Nowacki, Alberto Sonnino, Brandon Williams, and Lu Zhang.Sui Lutris: A Blockchain Combining Broadcast and Cons...
arXiv 2014
-
[2020]
Zef: Low-latency, Scalable, Private Payments
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
work page Pith review arXiv 2020
Show all 13 references
-
[2021]
640–651.doi:10.1109/ICDCS51616.2021.00067.url: https://doi
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
2021
-
[2022]
Zerocash: Decentralized Anonymous Payments from Bitcoin
[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
-
[2023]
Zether: Towards Privacy in a Smart Contract World
[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 Pape...
2020 doi
-
[2024]
A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases
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/3...
1979
-
[2508]
Obstruction-Free Synchronization: Double-Ended Queues as an Example
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...
2019
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.