TY - GEN
T1 - Re-thinking untraceability in the cryptonote-style blockchain
AU - Yu, Jiangshan
AU - Au, Man Ho Allen
AU - Esteves-Verissimo, Paulo
N1 - Funding Information:
ACKNOWLEDGMENT The authors would like to thank Dr. Jie Han (University of Rhode Island) for discussions on the Bregman’s theorem, and we appreciate the anonymous reviewers for their valuable suggestions. This work is partially supported by the Fonds National de la Recherche Luxembourg (FNR) through PEARL grant FNR/P14/8149128, the MonashU-PolyU-Collinstar Capital Joint Lab on Blockchain and Cryptocurrency Technologies, and the Research Grants Council of Hong Kong (Grant No. 25206317).
Publisher Copyright:
© 2019 IEEE.
PY - 2019/6
Y1 - 2019/6
N2 - 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.
AB - 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.
KW - Blockchain
KW - CryptoNote
KW - Privacy
KW - Untraceability
UR - http://www.scopus.com/inward/record.url?scp=85072603965&partnerID=8YFLogxK
U2 - 10.1109/CSF.2019.00014
DO - 10.1109/CSF.2019.00014
M3 - Conference article published in proceeding or book
AN - SCOPUS:85072603965
T3 - Proceedings - IEEE Computer Security Foundations Symposium
SP - 94
EP - 107
BT - Proceedings - 2019 IEEE 32nd Computer Security Foundations Symposium, CSF 2019
PB - IEEE Computer Society
T2 - 32nd IEEE Computer Security Foundations Symposium, CSF 2019
Y2 - 25 June 2019 through 28 June 2019
ER -