De-Anonymizing Monero: A Maximum Weighted Matching-Based Approach

As the leading privacy coin, Monero is widely recognized for its high level of anonymity. Monero utilizes linkable ring signature to hide the sender of a transaction. Although the anonymity is preferred by users, it poses challenges for authorities seeking to regulate financial activities. Researchers are actively engaged in studying methods to de-anonymize Monero. Previous methods usually relied on a specific type of ring called zero-mixin ring. However, these methods have become ineffective after Monero enforced the minimum ringsize. In this paper, we propose a novel approach based on maximum weighted matching to de-anonymize Monero. The proposed approach does not rely on the existence of zero-mixin rings. Specifically, we construct a weighted bipartite graph to represent the relationship between rings and transaction outputs. Based on the empirical probability distribution derived from users’ spending patterns, three weighting methods are proposed. Accordingly, we transform the de-anonymization problem into a maximum weight matching (MWM) problem. Due to the scale of the graph, traditional algorithms for solving the MWM problem are not applicable. Instead, we propose a deep reinforcement learning-based algorithm that achieves near-optimal results. Experimental results on both real-world dataset and synthetic dataset demonstrate the effectiveness of the proposed approach.