Paper 2021/760

Analysis of CryptoNote Transaction Graphs using the Dulmage-Mendelsohn Decomposition

Saravanan Vijayakumaran

Abstract

Transactions in CryptoNote blockchains induce a bipartite graph, with the set of transaction outputs forming one vertex class and the set of key images forming the other vertex class. In this graph, an edge exists between an output and a key image if the output appeared in the ring of the linkable ring signature which created the key image. Any maximum matching on this graph is a plausible candidate for the ground truth, i.e.~the association of each key image with the actual output being spent in the transaction. The Dulmage-Mendelsohn (DM) decomposition of a bipartite graph reveals constraints which are satisfied by every maximum matching on the graph. It identifies vertices which are matched in every maximum matching. It classifies edges as \textit{admissible} or \textit{inadmissible}. An edge is called admissible if it appears in at least one maximum matching and is called inadmissible if it does not appear in any maximum matching. The DM decomposition of a CryptoNote transaction graph reveals a set of outputs which can be marked as spent (precisely those outputs which are matched by every maximum matching). In some transaction rings, the decomposition identifies the true output being spent (making the ring traceable) by classifying the edges from all the other outputs to the key image as inadmissible. For pre-RingCT outputs in Monero, the DM decomposition performs better than existing techniques for Monero traceability, but the improvement is marginal. For RingCT outputs in Monero up to April 1, 2021, the DM decomposition is only able to identify the same five outputs that were identified as spent by existing techniques (which do not use information from hard forks).