License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AFT.2023.28
URN: urn:nbn:de:0030-drops-192172
Go to the corresponding LIPIcs Volume Portal

Vijayakumaran, Saravanan

Analysis of CryptoNote Transaction Graphs Using the Dulmage-Mendelsohn Decomposition

LIPIcs-AFT-2023-28.pdf (0.8 MB)


CryptoNote blockchains like Monero represent the largest public deployments of linkable ring signatures. Beginning with the work of Kumar et al. (ESORICS 2017) and Möser et al. (PoPETs 2018), several techniques have been proposed to trace CryptoNote transactions, i.e. identify the actual signing key, by using the transaction history. Yu et al. (FC 2019) introduced the closed set attack for undeniable traceability and proved that it is optimal by showing that it has the same performance as the brute-force attack. However, they could only implement an approximation of the closed set attack due to its exponential time complexity. In this paper, we show that the Dulmage-Mendelsohn (DM) decomposition of bipartite graphs gives a polynomial-time implementation of the closed set attack. Our contribution includes open source implementations of the DM decomposition and the clustering algorithm (the approximation to the closed set attack proposed by Yu et al). Using these implementations, we evaluate the empirical performance of these methods on the Monero dataset in two ways - firstly using data only from the main Monero chain and secondly using data from four hard forks of Monero in addition to the main Monero chain. We have released the scripts used to perform the empirical analysis along with step-by-step instructions.

BibTeX - Entry

  author =	{Vijayakumaran, Saravanan},
  title =	{{Analysis of CryptoNote Transaction Graphs Using the Dulmage-Mendelsohn Decomposition}},
  booktitle =	{5th Conference on Advances in Financial Technologies (AFT 2023)},
  pages =	{28:1--28:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-303-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{282},
  editor =	{Bonneau, Joseph and Weinberg, S. Matthew},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-192172},
  doi =		{10.4230/LIPIcs.AFT.2023.28},
  annote =	{Keywords: Cryptocurrency, CryptoNote, Monero, Traceability}

Keywords: Cryptocurrency, CryptoNote, Monero, Traceability
Collection: 5th Conference on Advances in Financial Technologies (AFT 2023)
Issue Date: 2023
Date of publication: 18.10.2023
Supplementary Material: Software: archived at:
Other (Documentation):

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI