Re-thinking untraceability in the CryptoNote-style blockchain

Jiangshan Yu, Man Ho Allen Au, Paulo Esteves-Verissimo

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

11 Citations (Scopus)


We develop new foundations on transaction untraceability for CryptoNote-style blockchain systems. In particular, we observe new attacks; develop theoretical foundations to model transaction untraceability; provide the least upper bound of transaction untraceability guarantee; provide ways to efficiently and automatically verify whether a given ledger achieves optimal transaction untraceability; and provide a general solution that achieves provably optimal transaction untraceability. Unlike previous cascade effect attacks (ESORICS' 17 and PETS' 18) on CryptoNote-style transaction untraceability, we consider not only a passive attacker but also an active adaptive attacker. Our observed attacks allow both types of attacker to trace blockchain transactions that cannot be traced by using the existing attacks. We develop a series of new games, which we call 'The Sun-Tzu Survival Problem', to model CryptoNote-style blockchain transaction untraceability and our identified attacks. In addition, we obtain seven novel results, where three of them are negative and the rest are positive. In particular, thanks to our abstract game, we are able to build bipartite graphs to model transaction untraceability, and provide reductions to formally relate the hardness of calculating untraceability to the hardness of calculating the number of perfect matchings in all possible bipartite graphs. We prove that calculating transaction untraceability is a #P-complete problem, which is believed to be even more difficult to solve than NP problems. In addition, we provide the first result on the least upper bound of transaction untraceability. Moreover, through our theoretical results, we are able to provide ways to efficiently and automatically verify whether a given ledger achieves optimal transaction untraceability. Furthermore, we propose a simple strategy for CryptoNote-style blockchain systems to achieve optimal untraceability. We take Monero as a concrete example to demonstrate how to apply this strategy to optimise the untraceability guarantee provided by Monero.

Original languageEnglish
Title of host publicationProceedings - 2019 IEEE 32nd Computer Security Foundations Symposium, CSF 2019
EditorsStephanie Delaune, Limin Jia
Place of PublicationPiscataway NJ USA
PublisherIEEE, Institute of Electrical and Electronics Engineers
Number of pages14
ISBN (Electronic)9781728114064
ISBN (Print)9781728114088
Publication statusPublished - 2019
EventIEEE Computer Security Foundations Symposium 2019 - Hoboken, United States of America
Duration: 25 Jun 201928 Jun 2019
Conference number: 32nd (Proceedings)


ConferenceIEEE Computer Security Foundations Symposium 2019
Abbreviated titleCSF 2019
Country/TerritoryUnited States of America
Internet address


  • Blockchain
  • CryptoNote
  • Privacy
  • Untraceability

Cite this