Analysis of CryptoNote Transaction Graphs

Saravanan Vijayakumaran

EE Department, IIT Bombay

October 24, 2023

CryptoNote

  • A proposal for a privacy-focused cryptocurrency (circa 2013)

  • Monero is the most popular CryptoNote implementation, with several improvements

    • Confidential amounts
    • Bulletproofs-based ring signatures and range proofs
    • RandomX PoW algorithm for ASIC resistance

Blockchains are bad for privacy

  • Suppose Alice does some content writing for Bob and gets paid in Bitcoin
  • Bob knows Alice’s address
  • Alice donates some BTC to the Trump campaign from the same address
  • Bob informs Elizabeth Warren
  • Alice gets a tax notice

Ring Signatures

  • Digital signatures: Signer knows the private key x corresponding to some public key P
  • Ring signatures: Signer knows one of the private keys corresponding to a set of public keys P_1, P_2, \ldots,P_n
  • Proposal: Hide source funds in a cryptocurrency transaction using ring signatures
  • Problem: How to prevent double spending?

Linkable Ring Signatures

  • Ring signatures which also reveal a one-way function of the private key

    • OWF output is called the key image
    • Two signatures using the same private key can be linked

  • Key image calculation in CryptoNote

    • Let P = xG be a public key
    • The key image of P is I = x H_{\text{p}}(P) where H_{\text{p}} is a point-valued hash function
    • If DDH is hard, P and I are unlinkable

Ring Selection in Monero

  • RingCT = Ring confidential transactions

    • Transaction type with hidden amounts
    • Mandatory since Sep 2017

  • Pre-RingCT ring selection

    • Suppose Alice wants to spend 1 XMR
    • Sample decoy keys from all those having 1 XMR

  • RingCT ring selection

    • Sample decoy keys from all keys having hidden amounts

Rings Can Overlap

Example of overlap: Q_1= P_4 and Q_2 = P_5

Bipartite Graph Representation

Maximum Matchings = Ground Truth Candidates

CryptoNote Transaction Graphs

  • Transaction outputs contain unique public keys

  • \mathcal{K}_h: Set of all key images that have appeared on the blockchain until block height h

  • \mathcal{O}_h: Set of all outputs that have appeared in at least one transaction ring

  • CryptoNote transaction graph

    • A bipartite graph on \mathcal{O}_h \times \mathcal{K}_h with edge set E
    • (P,I) \in E if P appeared in the transaction ring that created I

CryptoNote Transaction Graphs

  • Number of outputs \ge Number of key images
  • A maximum matching always exists

Traceable Rings

  • Suppose a transaction has a ring \{P_1, P_2, \ldots, P_k\} and a key image I

  • Definition: The signing key is the public key P_i such P_i = xG and I = x H_{\text{p}}(P_i) for a secret key x

  • Definition: A transaction ring is said to be traceable if the true signing key is correctly identified with probability 1

  • Traceable rings reveal the true output being spent

    • Such outputs are also called traceable outputs

Cascade Attack

Consider three rings \{P_1\}, \{P_1, P_2\}, \{P_1, P_2, P_3, P_4\} with key images I_1, I_2, I_3

Closed Sets

  • Zero-mixin transactions are not the only way to identify spent outputs
  • Consider four rings \begin{align*} R_1 & = \left\{ P_1, P_2, P_3 \right\},& R_2 & = \left\{ P_2, P_3 \right\},\\ R_3 & = \left\{ P_1, P_3 \right\}, & R_4 & = \left\{ P_1, P_2, P_3, P_4 \right\}. \end{align*}

  • Let \mathcal{R}_h = \{R_1, R_2,\ldots, R_n \} be a multiset of CryptoNote transaction rings and \mathcal{O}_h = \cup_{i=1}^n R_i.
  • A subset C of \mathcal{O}_h having cardinality k is called a closed set of \mathcal{R}_h if there exist k transaction rings R_{i_1}, R_{i_2}, \ldots, R_{i_k} in \mathcal{R}_h such that C = \cup_{j=1}^k R_{i_j}.

Closed Set Attack

  • Cascade attack needs zero-mixin transactions to start

  • Yu et al (FC 2019) proposed the closed set (CS) attack

    • Proved it has same performance as a brute-force attack

  • Naive implementation of the CS attack is infeasible

  • Yu et al proposed an approximation called the clustering algorithm

  • Our contribution: Polynomial algo to implement CS attack

Closed-Set Attack

  • Find all closed sets in the transaction graph

  • Remove edges from closed-set outputs to “other” key images

  • If an output has only one outgoing edge, it is traceable

Clustering Algorithm

  • A subset of the set of all rings is called a cluster
  • Initializes a cluster \mathcal{C} to \{R\} for a ring R
  • Keeps adding other rings R' to \mathcal{C} which satisfy d(R', \mathcal{C}) \le 1
  • If the eventual \mathcal{C} is a closed set, then removes edges from keys in \mathcal{C} to “other” key images
  • Repeats cluster-finding step

The Dulmage-Mendelsohn Decomposition

  • Key Observation: Closed sets have a one-to-one correspondence with minimum covers of the transaction graph

  • The Dulmage-Mendelsohn decomposition (1958) finds all minimum covers of a bipartite graph

Computing the DM Decomposition

  1. Find a maximum matching
  2. Perform DFS to find outputs reachable from unmatched vertices via an alternating path
  3. Find strongly connected components in a directed graph on outputs

DM Decomposition Example

Our Contributions

Thanks for listening

Saravanan Vijayakumaran

sarva@ee.iitb.ac.in