Paper 2021/760

Analysis of CryptoNote Transaction Graphs using the Dulmage-Mendelsohn Decomposition

Saravanan Vijayakumaran

Abstract

Transactions in CryptoNote blockchains use linkable ring signatures to prevent double spending. Each transaction ring is associated with a key image, which is a collision-resistant one-way function of the spent output's secret key. Several techniques have been proposed to trace CryptoNote transactions, i.e. identify the actual output associated with a key image, by using the transaction history. In this paper, we show that the Dulmage-Mendelsohn (DM) decomposition of bipartite graphs can be used to trace CryptoNote transactions. The DM decomposition technique is optimal in the sense that it eliminates every output-key image association which is incompatible with the transaction history. We used the Monero transaction history for performance comparison. For pre-RingCT outputs in Monero, the DM decomposition technique performs better than existing techniques. For RingCT outputs in Monero, the DM decomposition technique has the same performance as existing techniques, with only five out of approximately 29 million outputs being identified as spent. To study the effect of hard forks on Monero RingCT output traceability, we used information from four Monero hard forks. The DM decomposition technique is able to trace only 62,809 out of approximately 26 million RingCT transaction rings. Our results are further evidence supporting the claim that Monero RingCT transactions are mostly immune to traceability attacks.

Note: Added results which use information from the Monero Original, MoneroV, Monero v7, and Monero v9 hard forks for traceability