Re-Thinking Untraceability in the CryptoNote-Style Blockchain

【Author】 Yu, Jiangshan; Au, Man Ho Allen; Esteves-Verissimo, Paulo

【Source】2019 IEEE 32ND COMPUTER SECURITY FOUNDATIONS SYMPOSIUM (CSF 2019)

【Abstract】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.

【Keywords】

【标题】重新思考Crytonote型区块链的不可追踪性

【摘要】我们为Cryptonote式区块链系统的交易不可追踪性奠定了新的基础。特别是，我们观察到新的攻击；建立交易不可追踪性模型的理论基础；提供交易不可追踪性保证的最小上限；提供有效和自动验证给定分类账是否实现最佳交易不可追踪性的方法；并提供了一个可证明最优事务不可追踪性的通用解决方案。与之前针对CryptoNote类型事务不可追踪性的级联效应攻击（ESORICS’17和PETS’18）不同，我们不仅考虑被动攻击者，还考虑主动自适应攻击者。我们观察到的攻击允许这两种类型的攻击者跟踪无法使用现有攻击跟踪的区块链交易。我们开发了一系列新游戏，我们称之为“孙子生存问题”，以模拟加密笔记式区块链交易的不可追踪性和我们识别的攻击。此外，我们得到了七个新的结果，其中三个为负，其余为正。特别是，由于我们的抽象博弈，我们能够构建二部图来建模事务不可追踪性，并提供了将计算不可追踪性的难度与计算所有可能二部图中完美匹配数的难度正式联系起来的约化。我们证明了计算事务不可追踪性是一个#P-完全问题，这被认为比NP问题更难求解。此外，我们提供了关于事务不可追踪性最小上界的第一个结果。此外，通过我们的理论结果，我们能够提供有效和自动验证给定分类账是否达到最佳交易不可追踪性的方法。此外，我们提出了一种用于加密注释式区块链系统的简单策略，以实现最佳的不可追踪性。我们以Monero为例，演示如何应用该策略来优化Monero提供的不可追踪性保证。

【发表时间】2019

【收录时间】2022-07-16

【文献类型】Proceedings Paper

【论文大主题】加密货币

【论文小主题】匿名性与安全

【翻译者】林定康