MoneroResearch.info

WIKINDX Resources

Vijayakumaran, S. 2023, Analysis of CryptoNote Transaction Graphs using the Dulmage-Mendelsohn Decomposition. Paper presented at 5th Conference on Advances in Financial Technologies (AFT 2023). 
Added by: Rucknium (24/02/2022, 21:35)   Last edited by: Rucknium (10/01/2024, 16:22)
Resource type: Proceedings Article
ID no. (ISBN etc.): 978-3-95977-303-4
BibTeX citation key: Vijayakumaran2021
View all bibliographic details
 Categories: Monero-focused
Creators: Bonneau, Vijayakumaran, Weinberg
Publisher: Schloss Dagstuhl -- Leibniz-Zentrum f{"u}r Informatik
Collection: 5th Conference on Advances in Financial Technologies (AFT 2023)		 Views: 348/5387
Attachments   2021-760-published-version.pdf [27/394], 2021-760.pdf [25/1169] URLs   AFT conference, IACR page
Abstract
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.
  
Notes
 

Software with documentation: https://www.respectedsir.com/cna/

Abstract of previous version draft:

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.
 


  
WIKINDX 6.10.2 | Total resources: 233 | Username: -- | Bibliography: WIKINDX Master Bibliography | Style: APA Enhanced