Introduction

The following pages contain instructions to perform the analysis described in the paper Analysis of CryptoNote Transaction Graphs using the Dulmage-Mendelsohn Decomposition. It will appear in AFT 2023.

These instructions are maintained by Saravanan Vijayakumaran. They have been tested only on Ubuntu 22.04. If you find a bug in these instructions, please file an issue.

The code required to perform the analysis is available here. The scripts (Python, Bash, SQL, C++) and programs used are organized as follows.

cryptonote-analysis
├── Cargo.lock
├── Cargo.toml
├── scripts
│   ├── hardforks
│   │   ├── find_ring_intersection_from_forks.py
│   │   ├── monero-original
│   │   │   ├── create_keyimages_table.sql
│   │   │   ├── create_outputs_table.sql
│   │   │   ├── find_xmr_xmo_addresses.py
│   │   │   ├── populate_xmo_tables.py
│   │   │   ├── sql_table_creation.sh
│   │   │   └── trim_ring_xmr_xmo.py
│   │   ├── monerov
│   │   │   ├── create_keyimages_table.sql
│   │   │   ├── create_outputs_table.sql
│   │   │   ├── Dockerfile
│   │   │   ├── find_xmr_xmv_addresses.py
│   │   │   ├── populate_xmv_tables.py
│   │   │   ├── sql_table_creation.sh
│   │   │   └── trim_ring_xmr_xmv.py
│   │   ├── monero-v7
│   │   │   ├── create_keyimages_table.sql
│   │   │   ├── create_outputs_table.sql
│   │   │   ├── find_xmr_xmrv7_addresses.py
│   │   │   ├── populate_xmrv7_tables.py
│   │   │   ├── sql_table_creation.sh
│   │   │   └── trim_ring_xmr_xmrv7.py
│   │   └── monero-v9
│   │       ├── create_keyimages_table.sql
│   │       ├── create_outputs_table.sql
│   │       ├── find_xmr_xmrv9_addresses.py
│   │       ├── populate_xmrv9_tables.py
│   │       ├── sql_table_creation.sh
│   │       └── trim_ring_xmr_xmrv9.py
│   └── monero
│       ├── create_csparse_edges.cpp
│       ├── create_keyimages_table.sql
│       ├── create_outputs_table.sql
│       ├── keyimage_table_creation.sh
│       ├── output_table_creation.sh
│       └── populate_keyimage_table.py
└── src
    ├── bin
    │   ├── cascade.rs
    │   ├── cluster.rs
    │   ├── dmdec.rs
    │   ├── stats_cla.rs
    │   └── stats_dm.rs
    └── lib.rs

Requirements

Hardware Requirements

A computer with at least 24 GB of RAM and a 1 TB SSD.

Some comments about the disk space and RAM required.

  • The Monero blockchain upto height 2530000 occupies about 150 GB.
  • The hard fork databases occupy about 229 GB. If you are not planning on performing the analysis using hard fork data, you can discount this space.
  • The PostgreSQL tables take up about 60 GB.
  • The following two steps require more than 8 GB of RAM.
    • Compiling the MoneroV client using docker (needs 16 GB)
    • Running the Rust program that performs DM decomposition analysis (needs 24 GB).

Software Requirements

On a machine with Ubuntu Linux 22.04, install the following software.

  1. Rust
  2. Python 3
  3. pip 
    sudo apt install python3-pip
  4. requests 
    pip install requests
  5. PostgreSQL 
    sudo apt install postgresql libpq-dev
  6. Psycopg 
    pip install psycopg2
  7. numpy 
    pip install numpy
  8. Docker
    • Only required for analysing Monero using hardfork data.
    • These instructions have been tried after installing Docker Desktop.

Download the Monero Blockchain

We need to download all the blocks of the CryptoNote blockchain to perform our analysis. This involves downloading the client software and running it.

For Monero, download the latest release of the client from the releases page: https://github.com/monero-project/monero/releases/.

Unzip the archive and run the Monero CLI using the following command in the unzipped directory.

./monerod

It can take more than a day to sync the entire Monero blockchain onto an SSD. Using an HDD can take even longer.

Create PostgreSQL Tables

We will be using PostgreSQL tables to store the transaction graph. We will need three tables that are named as follows.

  • xmr_keyimages: Contains transaction rings and key images
  • xmr_outputs: Contains the transaction outputs
  • xmr_bigraph_edges: Contains the edges of the bipartite transaction graph

Do the following before proceeding to the table creation steps.

  1. Install PostgreSQL if you have not already done so.
  2. Set the password for the postgres user via the following commands.
    • sudo su postgres
    • psql
    • \password postgres

Create Key Image Table

  1. Install PostgreSQL if you have not already done so.

  2. Set the password for the postgres user via the following commands.

    • sudo su postgres
    • psql
    • \password postgres

  3. There is a file called create_keyimages_table.sql in the scripts/monero directory with the following contents.

    CREATE TABLE xmr_keyimages
(
    image                   VARCHAR(64) NOT NULL,
    id                      SERIAL PRIMARY KEY,
    ring_amount             BIGINT,
    ring_indices            INTEGER[],
    distinct_ring_indices   INTEGER[],
    block_height            INTEGER,
    UNIQUE(image)
)

    Note: Some old transaction rings in Monero have repeated ring members. The distinct_ring_indices only stores the distinct ring member indices.

  4. Run the following command in the scripts/monero directory to create the xmr_keyimages table.

    psql -U postgres -h 127.0.0.1 -W -f create_keyimages_table.sql

    NOTE: Alternatively, you can create the xmr_keyimages table by running the script called keyimage_table_creation.sh in the scripts/monero directory. You can run the command source keyimage_table_creation.sh and enter the Postgres user password when prompted.

  5. You can check that the table was successfully created by running the \dt command in the psql shell.

    • Run the following commands to enter the psql shell. 
      sudo su postgres
psql
    • Run the \dt command in the shell. The output should look like the following. 
      postgres=# \dt
            List of relations
 Schema |     Name      | Type  |  Owner   
--------+---------------+-------+----------
 public | xmr_keyimages | table | postgres
(1 row)
    • The xmr_keyimages table will be initially empty. 
      postgres=# SELECT * FROM xmr_keyimages;
 image | id | ring_amount | ring_indices | distinct_ring_indices | block_height 
-------+----+-------------+--------------+-----------------------+--------------
(0 rows)

  6. Run the Monero CLI client in offline mode using the following command. In this mode, the client will not download new blocks.

    ./monerod --offline

  7. Run the populate_keyimage_table.py script that is located in the scripts/monero directory.

    python3 populate_keyimage_table.py

    This script will query the Monero client and populate the xmr_keyimages table with non-coinbase transactions from block height 0 to block height 2,530,000. The latter block was mined on January 4, 2022. This script can take more than a day to finish running.

    WARNING: Before running this script, don't forget to change the postgres user password in the script to the password you have set. It needs to be changed in the argument to psycopg2.connect().

  8. Once the populate_keyimage_table.py script finishes running, you can stop the monerod client by pressing Ctrl-D in the CLI window.

Create Outputs Table

  1. There is a file called create_outputs_table.sql in the scripts/monero directory with the following contents. 
    CREATE TABLE xmr_outputs
(
    address       VARCHAR(64),
    id            SERIAL PRIMARY KEY,
    amount        BIGINT,
    index         INTEGER,
    UNIQUE(amount, index)
)
  2. Run the following command in the scripts/monero directory to create the xmr_outputs table. 
    psql -U postgres -h 127.0.0.1 -W -f create_outputs_table.sql

    NOTE: Alternatively, you can create the xmr_outputs table by running the script called output_table_creation.sh in the scripts/monero directory. You can run the command source output_table_creation.sh and enter the Postgres user password when prompted.

  3. Populate the xmr_outputs table using the following steps.
    • Run the following commands to enter the psql shell. 
      sudo su postgres
psql
    • Run ONLY ONE of the following queries. These queries consider transactions upto block height 1541236. This block height was used by Yu et al in their FC 2019 paper.
      • Run the following query to consider all outputs (RingCT and pre-RingCT). 
        INSERT INTO xmr_outputs(amount, index) SELECT ring_amount, UNNEST(ring_indices) FROM xmr_keyimages WHERE block_height <= 1541236 ON CONFLICT(amount, index) DO NOTHING;
      • To consider only RingCT outputs, run the following query. The difference from the previous query is the AND ring_amount=0 clause. 
        INSERT INTO xmr_outputs(amount, index) SELECT ring_amount, UNNEST(ring_indices) FROM xmr_keyimages WHERE block_height <= 1541236 AND ring_amount=0 ON CONFLICT(amount, index) DO NOTHING;

    NOTE: The point of creating the xmr_outputs table is to generate a unique integer index for every output. Then any edge in the CryptoNote transaction graph can be represented as a pair of integers: the key image index and the output index.

Create Edges Table

  1. Run the following commands to enter the psql shell (if you are not already inside it). 
    sudo su postgres
psql
  2. Create the xmr_bigraph_edges table by running ONLY ONE of the following queries. These queries consider transactions upto block height 1541236.
    • Run the following query to consider all outputs (RingCT and pre-RingCT). 
      CREATE TABLE xmr_bigraph_edges AS SELECT xk.id as keyimage_id, xo.id as output_id, xo.amount as output_amount, xo.index as output_index FROM (SELECT id, ring_amount, UNNEST(ring_indices) AS index FROM xmr_keyimages WHERE block_height <= 1541236) AS xk INNER JOIN xmr_outputs xo ON xk.ring_amount = xo.amount AND xk.index = xo.index;
    • To consider only RingCT outputs, run the following query. The difference from the previous query is the ring_amount = 0 clause. 
      CREATE TABLE xmr_bigraph_edges AS SELECT xk.id as keyimage_id, xo.id as output_id, xo.amount as output_amount, xo.index as output_index FROM (SELECT id, ring_amount, UNNEST(ring_indices) AS index FROM xmr_keyimages WHERE ring_amount = 0 AND block_height <= 1541236) AS xk INNER JOIN xmr_outputs xo ON xk.ring_amount = xo.amount AND xk.index = xo.index;

Create the Transaction Graph

  1. Create the edges file using the following steps
    • Run the following commands to enter the psql shell. 
      sudo su postgres
psql
    • Run the following query to write the edges file to disk. 
      \COPY (SELECT keyimage_id, output_id FROM xmr_bigraph_edges) TO '/tmp/edges-1541236.txt' WITH DELIMITER ' ';
  2. Each row in the edges-1541236.txt file represents an edge. The keyimage_id and output_id values that represent the edge are index values from the respective PostgreSQL tables. These index values do not form a contiguous range and can have gaps. But the sparse graph representations we will use work better without gaps in the index ranges.
    • Copy the edges-1541236.txt file to the scripts/monero directory.
    • Compile the create_csparse_edges.cpp file located in the scripts/monero directory. Run it with the block height as argument. 
      cd scripts/monero
g++ -O2 create_csparse_edges.cpp 
./a.out 1541236
      The output should look like the following. 
      Reading edge file
Finished reading edge file
Number of key images: 23164745
Number of outputs: 25126033
Number of vertices: 48290778
Number of edges: 58791856
Creating keyimage index map
Finished creating keyimage index map
Creating output index map
Finished creating output index map
Adding edges to graph
Finished adding edges to graph
    • Three output files are created.

      • csparse-edges-1541236.txt

        The edges in this file are represented as pairs of indices starting from 0 followed by a 1. This is the CSparse format for representing sparse matrices. The 1 corresponds to the value of the matrix entry. In our case, we use this format to represent sparse bipartite graphs.

      • index-keyimageid-map-1541236.txt

        This file has pairs of indices and key image IDs per line. It is to translate the result of the transaction graph analysis back to the key image ID space.

      • index-outputid-map-1541236.txt

        This file has pairs of indices and output IDs per line. It is to translate the result of the transaction graph analysis back to the output ID space.

DM Decomposition Analysis

  1. Compile the Rust binaries by running cargo build --release.

  2. Run the Dulmage-Mendelsohn decomposition program as follows.

    cargo run --release --bin dmdec csparse-edges-1541236.txt rings-before-dm-1541236.txt rings-after-dm-1541236.txt blocksizes-1541236.txt fine-decomp-1541236.txt

    Note: The significance of the arguments to dmdec can be understood by running cargo run -r --bin dmdec -- --help or ./target/release/dmdec --help.

    The output should look like the following.

    Edge file read in 6.920599929s
Num keyimages = 23164745, Num public keys = 25126033
Matched 23164745 out of 25126033 rows (public keys)
Number of unreachable pubkeys and keyimages = 16343677 16343677
Number of blocks in fine decomposition: 16338353
Singletons (traceable keyimages): 16335308
Closed set size histogram: {1: 16335308, 2: 2281, 3: 596, 4: 46, 5: 23, 6: 8, 7: 14, 8: 11, 9: 8, 10: 4, 11: 5, 12: 4, 13: 5, 14: 4, 15: 6, 16: 4, 17: 5, 18: 4, 20: 3, 21: 2, 22: 1, 24: 1, 26: 1, 27: 1, 40: 1, 43: 1, 50: 1, 55: 1, 103: 1, 106: 1, 119: 1, 122: 1}

    The above output says that out of the 23164745 transaction rings in the data set, 16335308 are traceable, i.e. the true output being spent in these transactions can be identified. Furthermore, there are 2281 closed sets of size 2, 596 closed sets of size 3, and so on. For a definition of a closed set, see Yu et al (FC 2019).

  3. To calculate statistics related to the DM decomposition analysis, run the following command.

    cargo run --release --bin stats_dm scripts/csparse-edges-1541236.txt rings-before-dm-1541236.txt rings-after-dm-1541236.txt

    Note: The significance of the arguments to stats_dm can be understood by running cargo run -r --bin stats_dm -- --help or ./target/release/stats_dm --help.

    The output should look like the following.

    Edge file read in 6.77205837s
Num keyimages = 23164745, Num public keys = 25126033
Pre DM decomposition rings file read in 9.421371749s
Pre DM decomposition mixin histogram:
[12209675, 707786, 4496490, 1486593, 3242625, 319352, 432875, 21528, 30067, 17724, 200030]
Post DM decomposition rings file read in 6.898382785s
Post DM decomposition mixin histogram:
[16335308, 1413028, 2369796, 279377, 2369578, 186257, 73690, 13086, 23615, 13071, 87939]
DM decomposition traceable ring mixin histogram:
[12209675, 625641, 1779446, 952862, 451981, 74186, 202360, 4296, 3506, 2178, 29177]

    The above output can be interpreted as follows.

    • Out of the 16335308 traceable rings, 12209675 had zero mixins (there were already traceable) before the DM decomposition, 625641 had one mixin before the DM decomposition, 1779446 had two mixins, and so on.
    • The number of mixins in a transaction ring can be quite large. For example, this transaction from block 1296030 has 4500 mixins. In the above histograms, we combine all mixin counts of 10 or more. So 200030 corresponds to the number of transaction rings with 10 or more mixins before the DM decomposition, 87939 is the same number after the DM decomposition, and 29177 is the number of traceable rings which had 10 or more mixins before the DM decomposition.

Closed Set Attack

  1. Compile the Rust binaries by running cargo build --release (if not already done).

  2. Perform the cascade attack first by running the following command.

    cargo run --release --bin cascade csparse-edges-1541236.txt rings-after-cascade-1541236.txt 10

    Note: The significance of the arguments to cascade can be understood by running cargo run -r --bin cascade -- --help or ./target/release/cascade --help.

    The output should look like the following.

    Edge file read in 6.780508534s
Num keyimages = 23164745, Num public keys = 25126033
Zero-mixin rings before CA = 12209675
Zero-mixin rings after CA iteration 1 = 15985204. Time taken = 4.434802555s.
Zero-mixin rings after CA iteration 2 = 16285257. Time taken = 277.680441ms.
Zero-mixin rings after CA iteration 3 = 16322672. Time taken = 111.501964ms.
Zero-mixin rings after CA iteration 4 = 16328236. Time taken = 87.87365ms.
Zero-mixin rings after CA iteration 5 = 16329045. Time taken = 83.504531ms.
Zero-mixin rings after CA iteration 6 = 16329176. Time taken = 83.173992ms.
Zero-mixin rings after CA iteration 7 = 16329215. Time taken = 82.656612ms.
Zero-mixin rings after CA iteration 8 = 16329215. Time taken = 82.576734ms.
No change in number of traceable rings. Exiting cascade attack loop

    The above output shows that 16329215 rings were traced by the cascade attack after 7 iterations. As there was no change in the number of traceable rings in the 8th iteration, the program exited.

  3. Run the clustering algorithm attack by running the following command.

    cargo run --release --bin cluster rings-after-cascade-1541236.txt rings-after-cluster-1541236.txt

    Note: The significance of the arguments to cluster can be understood by running cargo run -r --bin cluster -- --help or ./target/release/cluster --help.

    The output should look like the following. The key index values may be different.

    Rings file read in 6.888624255s
Ring sets created in 2.083401154s
Counted initial number of traceable rings in 87.942429ms
Number of traceable rings = 16329215
At beginning of clustering algorithm while loop
1: Cluster of size 491 found at key index 21441. Search iteration = 1
Number of blocks in fine decomposition: 485
Singletons (traceable keyimages): 484
2: Cluster of size 593 found at key index 21450. Search iteration = 1
Number of blocks in fine decomposition: 580
Singletons (traceable keyimages): 579
3: Cluster of size 555 found at key index 23092. Search iteration = 1
Number of blocks in fine decomposition: 538
Singletons (traceable keyimages): 537
4: Cluster of size 346 found at key index 33335. Search iteration = 1
Number of blocks in fine decomposition: 340
.
.
.
3009: Cluster of size 2 found at key index 22416538. Search iteration = 2
Number of blocks in fine decomposition: 1
Singletons (traceable keyimages): 0
3010: Cluster of size 2 found at key index 22868731. Search iteration = 2
Number of blocks in fine decomposition: 1
Singletons (traceable keyimages): 0
3011: Cluster of size 15 found at key index 22868933. Search iteration = 2
Number of blocks in fine decomposition: 1
Singletons (traceable keyimages): 0
3012: Cluster of size 8 found at key index 22868960. Search iteration = 2
Number of blocks in fine decomposition: 1
Singletons (traceable keyimages): 0
Number of traceable rings = 16334967
Number of closed sets = 8765
Number of singleton closed sets = 5752
Number of non-singleton closed sets = 3013
Closed set size histogram: {2: 2278, 3: 596, 4: 44, 5: 23, 6: 8, 7: 14, 8: 11, 9: 7, 10: 4, 11: 4, 12: 4, 13: 3, 14: 2, 15: 2, 16: 2, 17: 3, 18: 2, 20: 1, 21: 1, 43: 1, 50: 1, 55: 1}
Number of public keys in all sets = 13230
Number of public keys in non-singleton closed sets = 7478
Pre attack mixin histogram:
[16329215, 1416089, 2372296, 279613, 2369745, 186294, 73721, 13095, 23646, 13068, 87963]
Post attack mixin histogram:
[16334967, 1413031, 2370099, 279384, 2369606, 186257, 73690, 13086, 23615, 13071, 87939]

    The above output can be interpreted as follows.

    • The clustering algorithm renders 5752 transaction rings traceable. The number of traceable rings increases from 16329215 (after the cascade attack) to 16334967. In comparison, the DM decomposition had rendered 16335308 rings traceable, i.e. 341 rings more than the clustering algorithm.
    • There are 2278 closed sets of size 2, 596 closed sets of size 3, and so on. Note that the maximum size of a closed set found by the clustering algorithm is 55. In contrast, the largest closed set found by the DM decomposition is 122.

  4. To calculate statistics related to the clustering algorithm, run the following command.

    cargo run --release --bin stats_cla csparse-edges-1541236.txt rings-after-cascade-1541236.txt rings-after-cluster-1541236.txt

    Note: The significance of the arguments to stats_cla can be understood by running cargo run -r --bin stats_cla -- --help or ./target/release/stats_cla --help.

    The output should look like the following.

    Edge file read in 6.987560875s
Num keyimages = 23164745, Num public keys = 25126033
Initial mixin histogram:
[12209675, 707786, 4496490, 1486593, 3242625, 319352, 432875, 21528, 30067, 17724, 200030]
Post cascade attack rings file read in 6.91789017s
Post cascade attack mixin histogram:
[16329215, 1416089, 2372296, 279613, 2369745, 186294, 73721, 13095, 23646, 13068, 87963]
Cascade traceable ring pre-attack mixin histogram:
[12209675, 625264, 1776192, 951984, 451230, 73980, 202100, 4282, 3490, 2162, 28856]
Pre-attack mixin histogram of rings traced by cascade attack
0 12209675
1 625264
2 1776192
3 951984
4 451230
5 73980
6 202100
7 4282
8 3490
9 2162
10 28856
Total number of rings traced by cascade attack = 16329215
Post clustering algorithm rings file read in 6.917414066s
Post clustering algorithm mixin histogram:
[16334967, 1413031, 2370099, 279384, 2369606, 186257, 73690, 13086, 23615, 13071, 87939]
Cluster traceable ring post-attack mixin histogram:
[12209675, 625641, 1779134, 952855, 451959, 74186, 202360, 4296, 3506, 2178, 29177]
Post-attack mixin histogram of rings traced by clustering algorithm
0 0
1 377
2 2942
3 871
4 729
5 206
6 260
7 14
8 16
9 16
10 321
Total number of rings traced by clustering algorithm = 5752

    The above output can be interpreted as follows.

    • Out of the 16329215 rings traced by the cascade attack, 12209675 had zero mixins (there were already traceable) before the attack, 625264 had one mixin before the attack, 1776192 had two mixins, and so on.
    • Out of the 5752 rings traced by the clustering algorithm, 377 had one mixin after the cascade attack and before the clustering algorithm was executed, 2942 had two mixins, and so on.
    • In the above histograms, we combine all mixin counts of 10 or more.
      • So 200030 corresponds to the number of transaction rings with 10 or more mixins before the cascade attack, 87963 is the same number after the cascade attack, and 87939 is the number of rings which had 10 or more mixins after the clustering algorithm was executed.
      • Similarly, 28856 is the number of rings traced by the cascade attack that had 10 or more mixins before the attack. And 321 is the number of rings traced by the clustering algorithm that had 10 or more mixins before the algorithm was executed.

What and Why of Hard Forks

Hard forks of the Monero chain are blockchains which have diverged from the main Monero chain at some block height. This divergence could be accidental due to some nodes not upgrading their client software in time. Or it could be intentional due to some developers forking the Monero client and introducing changes that are incompatible with the main Monero chain.

Data from four hard forks is available: Monero Original, MoneroV, Monero v7, and Monero v9. The first two were intentional hard forks and the last two are accidental ones. The table below shows the number of blocks in each of these forks. The accidental forks lasted only for a few blocks.

Fork NameFork blockBlocks in forkCommon key images
Monero Original1,546,000238,68286,685
MoneroV1,564,966146,3259,387
Monero v71,685,555291,061
Monero v91,788,000731,581

The same output can be spent in both the main Monero chain and a hard fork without violating the no double spending restriction. Whenever an output is spent, its key image is revealed. If the same key image appears in a Monero transaction and a hard fork transaction, the output being spent must be in the intersection of both transaction rings. If the transaction rings have an intersection size of one, the output being spent is identified.

This type of cross-chain analysis for Monero was first performed by Hinteregger et al. (2018). The instructions in the following chapters describe steps to perform their analysis followed by a final DM decomposition analysis. Hinteregger et al. had considered data from Monero Original and MoneroV. We add the two smaller hard forks which appeared after their work was published.

The last column in the above table shows the number of key images from each hard fork that also appeared on the main Monero chain (upto block height 2,530,000). If any of the outputs corresponding to these key images can be identified, they can be marked as mixins in all the other transactions they appear in. And the corresponding edges in these other transactions can be deleted before performing the DM decomposition analysis.

Why not use monero-blockchain-mark-spent-outputs?

Every Monero release contains a command-line tool called monero-blockchain-mark-spent-outputs which can be used to identify spent outputs. This tool takes a list of LMDB databases as input (see Download Hard Fork Data) and outputs a list of spent outputs. It implements the cascade attack, finds transactions which cause the zero-mixin effect as characterized by Wijaya et al., attempts to identify closed sets, and performs the cross-chain analysis proposed by Hinteregger et al. It is informally called the "blackball tool" in the Monero community.

This tool's goal is to help Monero users avoid spent outputs while choosing mixins for their transactions. Technically, we could have also used it to identify spent outputs. But we chose to identify the spent outputs without using this tool for the following two reasons.

  1. The tool fails to read the transactions in the MoneroV LMDB database. It outputs the error message Failed to parse transaction from blob.
  2. When the hard fork databases are given as input, it gives some errors with the message Rings for the same key image are disjoint.

The errors in point 2 can be explained as below.

  • Within a single Monero chain, an output is uniquely determined by the (amount, index) pair.
    • The amount corresponds to the number of coins associated with the output (zero for RingCT outputs).
    • The index is an incrementing counter which specifies the rank of the output in the list of all outputs corresponding to a particular amount (when the list is sorted by order of appearance on the blockchain).
  • An (amount, index) pair may be associated with different one-time addresses (public keys) on different Monero chains.
  • The monero-blockchain-mark-spent-outputs does not translate the (amount, index) pairs to one-time addresses (this was true at least until version v0.18.2.2, April 2023). So when a key image appears on two Monero chains, the corresponding transaction rings may have disjoint output indices.

To avoid such errors, our analysis uses RPC queries to the respective Monero clients to translate (amount, index) pairs to one-time addresses on each Monero chain before computing intersections.

Create Fork Indices Column

We will add a column named fork_indices to the xmr_keyimages table. Here is some motivation.

  • It will initially contain the distinct output indices corresponding to the transaction ring members.
  • For key images which have appeared in both the main Monero chain and at least one hard fork, we may be able to remove some of the output indices in the fork_indices.
  • Our analysis using hard fork data will translate (amount, index) pairs to one-time addresses on each chain and then find the intersection of the transaction rings corresponding to a key image from all five chains — Monero and the four hard forks.
  • The fork_indices column will store the intersection of the transaction rings using indices from the main Monero chain.

Do the following to add the fork_indices column.

  1. Run the following commands to enter the psql shell. 
    sudo su postgres
psql
  2. Add the fork_indices column to the xmr_keyimages table. 
    ALTER TABLE xmr_keyimages ADD fork_indices INTEGER[];

    Note: We could have added the fork_indices column when creating the xmr_keyimages table in the Create Key Image Table step. We chose not to do so because this column is required only for the analysis using hard fork data.

  3. Populate the fork_indices column with the contents of dist_ring_indices. 
    UPDATE xmr_keyimages SET fork_indices=distinct_ring_indices;

Download Hard Fork Data

Acknowledgement: As the hard fork blockchains are no longer operational, we used the blockchain databases made available by Justin Ehrenhofer at https://github.com/monero-blackball/monero-blackball-site. We thank him for making these databases freely available.

  1. In the README of the monero-blackball-site repo, go to the section named "Full Blockchain LMDB Downloads".
  2. Download the files corresponding to monerov, monerov6, monerov7, and monerov9. They are hosted on Google Drive.
  3. From each of the links, you will get two files called data.mdb and lock.mdb.
  4. Create a directory for each of the hardforks with names monerov, monerov6, monerov7, and monerov9.
  5. Create a subdirectory called lmdb in each of the four directories.
  6. Copy the downloaded data.mdb file corresponding to each hard fork to the respective lmdb directories. Your directory structure should like the following where hardfork-lmdb-databases is the parent directory.
        hardfork-lmdb-databases/
        ├── monerov
        │   └── lmdb
        │       └── data.mdb
        ├── monerov6
        │   └── lmdb
        │       └── data.mdb
        ├── monerov7
        │   └── lmdb
        │       └── data.mdb
        └── monerov9
            └── lmdb
                └── data.mdb

Use Monero Original Data

Monero Original is a hard fork of Monero which devitated from the main chain at block height 1,546,000 (April 6, 2018) and lasted for 238,682 blocks.

Run Monero Original Client

  1. Download the Helium Hydra Original R3 release of the Monero Original client.
  2. Run the following command to connect the monerod daemon to the LMDB database of the Monero Original blockchain. You may have to replace hardfork-lmdb-databases with the path on your machine. 
    ./monerod --data-dir hardfork-lmdb-databases/monerov6/ --offline
  3. The RPC server is exposed on port 18081. You can check if it is working by running the following command. 
    curl http://127.0.0.1:18081/getheight
    You should see the following output. It shows that there are 1784682 blocks in the chain. 
    {
   "height": 1784682,
   "status": "OK"
}

Create PostgreSQL Tables

We will be using PostgreSQL tables to store the Monero Original data. We will need three tables that are named as follows.

  • xmo_keyimages: Contains transaction rings and key images
  • xmo_outputs: Contains the transaction outputs
  • xmr_xmo_keyimages: Contains the rows of xmr_keyimages whose key images appear in xmo_keyimages

  1. There is a file called create_keyimages_table.sql in the scripts/hardforks/monero-original directory with the following contents.

    CREATE TABLE xmo_keyimages
(
    image                   VARCHAR(64) NOT NULL,
    id                      SERIAL PRIMARY KEY,
    ring_amount             BIGINT,
    ring_indices            INTEGER[],
    block_height            INTEGER,
    UNIQUE(image)
)

  2. Run the following command in the scripts/hardforks/monero-original directory to create the xmo_keyimages table.

    psql -U postgres -h 127.0.0.1 -W -f create_keyimages_table.sql

  3. There is a file called create_outputs_table.sql in the scripts/hardforks/monero-original directory with the following contents.

    CREATE TABLE xmo_outputs
(
    image                   VARCHAR(64) NOT NULL,
    id                      SERIAL PRIMARY KEY,
    ring_amount             BIGINT,
    ring_indices            INTEGER[],
    block_height            INTEGER,
    UNIQUE(image)
)

  4. Run the following command in the scripts/hardforks/monero-original directory to create the xmo_outputs table.

    psql -U postgres -h 127.0.0.1 -W -f create_outputs_table.sql

    NOTE: Alternatively, you can create the xmo_keyimages and xmo_outputs tables by running the script called sql_table_creation.sh in the scripts/hardforks/monero-original directory. You can run the command source sql_table_creation.sh and enter the Postgres user password when prompted.

  5. Run the populate_xmo_tables.py script that is located in the scripts/hardforks/monero-original directory.

    python3 populate_xmo_tables.py

    This script will query the Monero Original client and populate the xmo_keyimages and xmo_outputs tables with non-coinbase transactions from block height 1,546,000 to block height 1,784,681. The Monero Original blockchain diverged from the main Monero chain at block height 1,546,000.

  6. Once the populate_xmo_tables.py script finishes running, you can stop the Monero Original client by pressing Ctrl-D in the CLI window.

  7. Create the xmr_xmo_keyimages table using the following steps. It will contain the subset of xmr_keyimages that corresponds to key images which have appeared both on the main Monero chain and the Monero Original chain.

    • Run the following commands to enter the psql shell. 
      sudo su postgres
psql
    • Run the following query. 
      CREATE TABLE xmr_xmo_keyimages AS (SELECT xmrk.* FROM xmr_keyimages xmrk INNER JOIN xmo_keyimages xmok ON xmrk.image=xmok.image);

Find Output Addresses

  1. Run the Monero CLI client in offline mode using the following command. 
    ./monerod --offline

    Note: This is the Monero client and not the Monero Original client.

  2. Run the find_xmr_xmo_addresses.py script that is located in the scripts/hardforks/monero-original directory. 
    python3 find_xmr_xmo_addresses.py
    This script will query the Monero client and find the one-time addresses (public keys) corresponding to the outputs which appear in the transaction rings of xmr_xmo_keyimages. It will write a Python dictionary mapping (ring_amount, index) pairs to the one-time addresses into a file called xmr_xmo_addr.dat.
  3. Once the find_xmr_xmo_addresses.py script finishes running, you can stop the monerod client by pressing Ctrl-D in the CLI window.

Find Ring Intersections

  1. Run the trim_ring_xmr_xmo.py script that is located in the scripts/hardforks/monero-original directory.

    python3 trim_ring_xmr_xmo.py

    This script will replace the fork_indices column in xmr_xmo_keyimages with the intersection of the transaction rings.

    Note: This script reads the Python dictionary mapping (ring_amount, index) pairs to the one-time addresses from the file called xmr_xmo_addr.dat. Ensure that this file is in the same directory as the script.

  2. You can query the number of transaction rings where the actual output being spent has been identified by running the following query in the psql shell.

    SELECT COUNT(*) FROM xmr_xmo_keyimages WHERE ARRAY_LENGTH(fork_indices,1) = 1 AND ARRAY_LENGTH(distinct_ring_indices, 1) <> 1 AND block_height <= 2530000;

    The result of this query was 77121. Note that the query restricts the block height to 2530000.

Use MoneroV Data

MoneroV is a hard fork of Monero which devitated from the main chain at block height 1,565,244 (May 4, 2018) and lasted for 146,047 blocks.

Compile MoneroV Client

  1. Ensure that you have docker installed.
  2. Clone the MoneroV repo (including submodules via the --recursive flag). 
    git clone --recursive https://github.com/monerov/monerov.git
  3. Overwrite the Dockerfile in the monerov repo with the one the scripts/hardforks/monerov directory. 
    cd monerov
cp <path-to-the-instructions-repo>/scripts/hardforks/xmv/Dockerfile .
  4. In the monerov repo, run the following command to build a docker image containing the monerovd client binary. 
    docker build -t monerov .

    Note: You may have to increase the RAM allotted to the VM that docker uses to build the image. An allocation of 7.5 GB was sufficient for the image to be succesfully built. This can be done in the Settings > Advanced menu of Docker Desktop.

  5. The monerovd client binary is in the /src/build/release/bin/ directory of the image. To copy it to the host machine, we need a running container based on this image. 
    docker run -d monerov bash -c "tail -f /dev/null"
    The tail -f /dev/null command prevents the container from exiting. Make a note of the container id that is printed or obtain it by running the docker ps command.
  6. Copy the monerovd binary from the container to the host using the following command (after replacing <container-id> with the actual container ID). 
    docker cp <container-id>:/src/build/release/bin/monerovd .
    The current directory of the host must have the monerovd binary.
  7. Stop and delete the container with the following command. 
    docker rm -f <container-id>

Run MoneroV Client

  1. Run the following command to connect the monerovd daemon to the LMDB database of the MoneroV blockchain. You may have to replace hardfork-lmdb-databases with the path on your machine. 
    ./monerovd --data-dir hardfork-lmdb-databases/monerov/ --offline
  2. The RPC server is exposed on port 19091. You can check if it is working by running the following command. 
    curl http://127.0.0.1:19091/get_height
    You should see the following output. It shows that there are 1711291 blocks in the chain. 
    {
   "height": 1711291,
   "status": "OK",
   "untrusted": false
}

Create PostgreSQL Tables

We will be using PostgreSQL tables to store the MoneroV data. We will need three tables that are named as follows.

  • xmv_keyimages: Contains transaction rings and key images
  • xmv_outputs: Contains the transaction outputs
  • xmr_xmv_keyimages: Contains the rows of xmr_keyimages whose key images appear in xmv_keyimages

  1. There is a file called create_keyimages_table.sql in the scripts/hardforks/monerov directory with the following contents.

    CREATE TABLE xmv_keyimages
(
    image                   VARCHAR(64) NOT NULL,
    id                      SERIAL PRIMARY KEY,
    ring_amount             BIGINT,
    ring_indices            INTEGER[],
    block_height            INTEGER,
    UNIQUE(image)
)

  2. Run the following command in the scripts/hardforks/monerov directory to create the xmv_keyimages table.

    psql -U postgres -h 127.0.0.1 -W -f create_keyimages_table.sql

  3. There is a file called create_outputs_table.sql in the scripts/hardforks/monerov directory with the following contents.

    CREATE TABLE xmv_outputs
(
    image                   VARCHAR(64) NOT NULL,
    id                      SERIAL PRIMARY KEY,
    ring_amount             BIGINT,
    ring_indices            INTEGER[],
    block_height            INTEGER,
    UNIQUE(image)
)

  4. Run the following command in the scripts/hardforks/monerov directory to create the xmv_outputs table.

    psql -U postgres -h 127.0.0.1 -W -f create_outputs_table.sql

    NOTE: Alternatively, you can create the xmv_keyimages and xmv_outputs tables by running the script called sql_table_creation.sh in the scripts/hardforks/monerov directory. You can run the command source sql_table_creation.sh and enter the Postgres user password when prompted.

  5. Run the populate_xmv_tables.py script that is located in the scripts/hardforks/monerov directory.

    python3 populate_xmv_tables.py

    This script will query the MoneroV client and populate the xmv_keyimages and xmv_outputs tables with non-coinbase transactions from block height 1,564,966 to block height 1,711,290. The MoneroV blockchain diverged from the main Monero chain at block height 1,564,966.

  6. Once the populate_xmv_tables.py script finishes running, you can stop the MoneroV client by pressing Ctrl-D in the CLI window.

  7. Create the xmr_xmv_keyimages table using the following steps. It will contain the subset of xmr_keyimages that corresponds to key images which have appeared both on the main Monero chain and the MoneroV chain.

    • Run the following commands to enter the psql shell. 
      sudo su postgres
psql
    • Run the following query. 
      CREATE TABLE xmr_xmv_keyimages AS (SELECT xmrk.* FROM xmr_keyimages xmrk INNER JOIN xmv_keyimages xmvk ON xmrk.image=xmvk.image);

Find Output Addresses

  1. Run the Monero CLI client in offline mode using the following command. 
    ./monerod --offline

    Note: This is the Monero client and not the MoneroV client.

  2. Run the find_xmr_xmv_addresses.py script that is located in the scripts/hardforks/monerov directory. 
    python3 find_xmr_xmv_addresses.py
    This script will query the Monero client and find the one-time addresses (public keys) corresponding to the outputs which appear in the transaction rings of xmr_xmv_keyimages. It will write a Python dictionary mapping (ring_amount, index) pairs to the one-time addresses into a file called xmr_xmv_addr.dat.
  3. Once the find_xmr_xmv_addresses.py script finishes running, you can stop the monerod client by pressing Ctrl-D in the CLI window.

Find Ring Intersections

  1. Run the trim_ring_xmr_xmv.py script that is located in the scripts/hardforks/monerov directory.

    python3 trim_ring_xmr_xmv.py

    This script will replace the fork_indices column in xmr_xmv_keyimages with the intersection of the transaction rings.

    Note: This script reads the Python dictionary mapping (ring_amount, index) pairs to the one-time addresses from the file called xmr_xmv_addr.dat. Ensure that this file is in the same directory as the script.

  2. You can query the number of transaction rings where the actual output being spent has been identified by running the following query in the psql shell.

    SELECT COUNT(*) FROM xmr_xmv_keyimages WHERE ARRAY_LENGTH(fork_indices,1) = 1 AND ARRAY_LENGTH(distinct_ring_indices, 1) <> 1;

    The result of this query was 7287. Note that the query restricts the block height to 2530000.

Use Monero v7 Data

Monero v7 is a hard fork of Monero which devitated from the main chain at block height 1,685,555 (October 18, 2018) and lasted for 29 blocks.

Run Monero v7 Client

  1. Download the Lithium Luna, Point Release 3 version of the Monero client.
  2. Run the following command to connect the monerod daemon to the LMDB database of the Monero v7 blockchain. You may have to replace hardfork-lmdb-databases with the path on your machine. 
    ./monerod --data-dir hardfork-lmdb-databases/monerov7/ --offline
  3. The RPC server is exposed on port 18081. You can check if it is working by running the following command. 
    curl http://127.0.0.1:18081/get_height
    You should see the following output. It shows that there are 1685584 blocks in the chain. 
    {
     "height": 1685584,
     "status": "OK",
     "untrusted": false
}

Create PostgreSQL Tables

We will be using PostgreSQL tables to store the Monero v7 data. We will need three tables that are named as follows.

  • xmrv7_keyimages: Contains transaction rings and key images
  • xmrv7_outputs: Contains the transaction outputs
  • xmr_xmrv7_keyimages: Contains the rows of xmr_keyimages whose key images appear in xmrv7_keyimages

  1. There is a file called create_keyimages_table.sql in the scripts/hardforks/monero-v7 directory with the following contents.

    CREATE TABLE xmrv7_keyimages
(
    image                   VARCHAR(64) NOT NULL,
    id                      SERIAL PRIMARY KEY,
    ring_amount             BIGINT,
    ring_indices            INTEGER[],
    block_height            INTEGER,
    UNIQUE(image)
)

  2. Run the following command in the scripts/hardforks/monero-v7 directory to create the xmrv7_keyimages table.

    psql -U postgres -h 127.0.0.1 -W -f create_keyimages_table.sql

  3. There is a file called create_outputs_table.sql in the scripts/hardforks/monero-v7 directory with the following contents.

    CREATE TABLE xmrv7_outputs
(
    image                   VARCHAR(64) NOT NULL,
    id                      SERIAL PRIMARY KEY,
    ring_amount             BIGINT,
    ring_indices            INTEGER[],
    block_height            INTEGER,
    UNIQUE(image)
)

  4. Run the following command in the scripts/hardforks/monero-v7 directory to create the xmrv7_outputs table.

    psql -U postgres -h 127.0.0.1 -W -f create_outputs_table.sql

    NOTE: Alternatively, you can create the xmrv7_keyimages and xmrv7_outputs tables by running the script called sql_table_creation.sh in the scripts/hardforks/monero-v7 directory. You can run the command source sql_table_creation.sh and enter the Postgres user password when prompted.

  5. Run the populate_xmrv7_tables.py script that is located in the scripts/hardforks/monero-v7 directory.

    python3 populate_xmrv7_tables.py

    This script will query the Monero v7 client and populate the xmrv7_keyimages and xmrv7_outputs tables with non-coinbase transactions from block height 1,685,555 to block height 1,685,583. The Monero v7 blockchain diverged from the main Monero chain at block height 1,685,555.

  6. Once the populate_xmrv7_tables.py script finishes running, you can stop the Monero v7 client by pressing Ctrl-D in the CLI window.

  7. Create the xmr_xmrv7_keyimages table using the following steps. It will contain the subset of xmr_keyimages that corresponds to key images which have appeared both on the main Monero chain and the Monero v7 chain.

    • Run the following commands to enter the psql shell. 
      sudo su postgres
psql
    • Run the following query. 
      CREATE TABLE xmr_xmrv7_keyimages AS (SELECT xmrk.* FROM xmr_keyimages xmrk INNER JOIN xmrv7_keyimages xmrv7k ON xmrk.image=xmrv7k.image);

Find Output Addresses

  1. Run the Monero CLI client in offline mode using the following command. 
    ./monerod --offline

    Note: This is the Monero client and not the Monero v7 client.

  2. Run the find_xmr_xmrv7_addresses.py script that is located in the scripts/hardforks/monero-v7 directory. 
    python3 find_xmr_xmrv7_addresses.py
    This script will query the Monero client and find the one-time addresses (public keys) corresponding to the outputs which appear in the transaction rings of xmr_xmrv7_keyimages. It will write a Python dictionary mapping (ring_amount, index) pairs to the one-time addresses into a file called xmr_xmrv7_addr.dat.
  3. Once the find_xmr_xmrv7_addresses.py script finishes running, you can stop the monerod client by pressing Ctrl-D in the CLI window.

Find Ring Intersections

  1. Run the trim_ring_xmr_xmrv7.py script that is located in the scripts/hardforks/monero-v7 directory.

    python3 trim_ring_xmr_xmrv7.py

    This script will replace the fork_indices column in xmr_xmrv7_keyimages with the intersection of the transaction rings.

    Note: This script reads the Python dictionary mapping (ring_amount, index) pairs to the one-time addresses from the file called xmr_xmrv7_addr.dat. Ensure that this file is in the same directory as the script.

  2. You can query the number of transaction rings where the actual output being spent has been identified by running the following query in the psql shell.

    SELECT COUNT(*) FROM xmr_xmrv7_keyimages WHERE ARRAY_LENGTH(fork_indices,1) = 1 AND ARRAY_LENGTH(distinct_ring_indices, 1) <> 1 AND block_height <= 2530000;

    The result of this query was 650. Note that the query restricts the block height to 2530000.

Use Monero v9 Data

Monero v9 is a hard fork of Monero which devitated from the main chain at block height 1,788,000 (March 9, 2019) and lasted for 73 blocks.

Run Monero v9 Client

  1. Download the Beryllium Bullet, Point Release version of the Monero client.
  2. Run the following command to connect the monerod daemon to the LMDB database of the Monero v9 blockchain. You may have to replace hardfork-lmdb-databases with the path on your machine. 
    ./monerod --data-dir hardfork-lmdb-databases/monerov9/ --offline
  3. The RPC server is exposed on port 18081. You can check if it is working by running the following command. 
    curl http://127.0.0.1:18081/get_height
    You should see the following output. It shows that there are 1788073 blocks in the chain. 
    {
   "height": 1788073,
   "status": "OK",
   "untrusted": false
}

Create PostgreSQL Tables

We will be using PostgreSQL tables to store the Monero v9 data. We will need three tables that are named as follows.

  • xmrv9_keyimages: Contains transaction rings and key images
  • xmrv9_outputs: Contains the transaction outputs
  • xmr_xmrv9_keyimages: Contains the rows of xmr_keyimages whose key images appear in xmrv9_keyimages

  1. There is a file called create_keyimages_table.sql in the scripts/hardforks/monero-v9 directory with the following contents.

    CREATE TABLE xmrv9_keyimages
(
    image                   VARCHAR(64) NOT NULL,
    id                      SERIAL PRIMARY KEY,
    ring_amount             BIGINT,
    ring_indices            INTEGER[],
    block_height            INTEGER,
    UNIQUE(image)
)

  2. Run the following command in the scripts/hardforks/monero-v9 directory to create the xmrv9_keyimages table.

    psql -U postgres -h 127.0.0.1 -W -f create_keyimages_table.sql

  3. There is a file called create_outputs_table.sql in the scripts/hardforks/monero-v9 directory with the following contents.

    CREATE TABLE xmrv9_outputs
(
    image                   VARCHAR(64) NOT NULL,
    id                      SERIAL PRIMARY KEY,
    ring_amount             BIGINT,
    ring_indices            INTEGER[],
    block_height            INTEGER,
    UNIQUE(image)
)

  4. Run the following command in the scripts/hardforks/monero-v9 directory to create the xmrv9_outputs table.

    psql -U postgres -h 127.0.0.1 -W -f create_outputs_table.sql

    NOTE: Alternatively, you can create the xmrv9_keyimages and xmrv9_outputs tables by running the script called sql_table_creation.sh in the scripts/hardforks/monero-v9 directory. You can run the command source sql_table_creation.sh and enter the Postgres user password when prompted.

  5. Run the populate_xmrv9_tables.py script that is located in the scripts/hardforks/monero-v9 directory.

    python3 populate_xmrv9_tables.py

    This script will query the Monero v9 client and populate the xmrv9_keyimages and xmrv9_outputs tables with non-coinbase transactions from block height 1,788,000 to block height 1,788,072. The Monero v9 blockchain diverged from the main Monero chain at block height 1,788,000.

  6. Once the populate_xmrv9_tables.py script finishes running, you can stop the Monero v9 client by pressing Ctrl-D in the CLI window.

  7. Create the xmr_xmrv9_keyimages table using the following steps. It will contain the subset of xmr_keyimages that corresponds to key images which have appeared both on the main Monero chain and the Monero v9 chain.

    • Run the following commands to enter the psql shell. 
      sudo su postgres
psql
    • Run the following query. 
      CREATE TABLE xmr_xmrv9_keyimages AS (SELECT xmrk.* FROM xmr_keyimages xmrk INNER JOIN xmrv9_keyimages xmrv9k ON xmrk.image=xmrv9k.image);

Find Output Addresses

  1. Run the Monero CLI client in offline mode using the following command. 
    ./monerod --offline

    Note: This is the Monero client and not the Monero v9 client.

  2. Run the find_xmr_xmrv9_addresses.py script that is located in the scripts/hardforks/monero-v9 directory. 
    python3 find_xmr_xmrv9_addresses.py
    This script will query the Monero client and find the one-time addresses (public keys) corresponding to the outputs which appear in the transaction rings of xmr_xmrv9_keyimages. It will write a Python dictionary mapping (ring_amount, index) pairs to the one-time addresses into a file called xmr_xmrv9_addr.dat.
  3. Once the find_xmr_xmrv9_addresses.py script finishes running, you can stop the monerod client by pressing Ctrl-D in the CLI window.

Find Ring Intersections

  1. Run the trim_ring_xmr_xmrv9.py script that is located in the scripts/hardforks/monero-v9 directory.

    python3 trim_ring_xmr_xmrv9.py

    This script will replace the fork_indices column in xmr_xmrv9_keyimages with the intersection of the transaction rings.

    Note: This script reads the Python dictionary mapping (ring_amount, index) pairs to the one-time addresses from the file called xmr_xmrv9_addr.dat. Ensure that this file is in the same directory as the script.

  2. You can query the number of transaction rings where the actual output being spent has been identified by running the following query in the psql shell.

    SELECT COUNT(*) FROM xmr_xmrv9_keyimages WHERE ARRAY_LENGTH(fork_indices,1) = 1 AND ARRAY_LENGTH(distinct_ring_indices, 1) <> 1 AND block_height <= 2530000;

    The result of this query was 187. Note that the query restricts the block height to 2530000.

Update Fork Indices Column

We need to update the fork_indices column in the xmr_keyimages table to contain the intersection of all transaction rings which had the same key image. See the discussion in Create Fork Indices Column for context.

  1. Run the find_ring_intersection_from_forks.py script present in the scripts/hardforks directory. 
    python3 find_ring_intersection_from_forks.py
  2. You can query the number of transaction rings where number of mixins has changed due to the hard fork information by runnng the following query in the psql shell. 
    SELECT COUNT(*) FROM xmr_keyimages WHERE ARRAY_LENGTH(distinct_ring_indices, 1) <> ARRAY_LENGTH(fork_indices, 1) AND block_height <= 2530000;
    The result of this query was 86338. Note that the query restricts the block height to 2530000.

RingCT Analysis

In this chapter, we describe the traceability analysis of RingCT transactions upto block height 2,530,000.

Create Edges Table

  1. Run the following command the psql shell to delete any previously created xmr_bigraph_edges table. 
    DROP TABLE xmr_bigraph_edges;

    Note: We delete the previously created xmr_bigraph_edges to recover disk space. The table occupies about 20 GB. If you have ample disk space available, you can skip the deletion. But remember to create the table in the next step with a name different from xmr_bigraph_edges. For example, you can use xmr_bigraph_edges_hardfork.

  2. Create the xmr_bigraph_edges table by running the following query in the psql shell. This query consider transactions upto block height 2530000. 
    CREATE TABLE xmr_bigraph_edges AS SELECT xk.id as keyimage_id, xo.id as output_id, xo.amount as output_amount, xo.index as output_index FROM (SELECT id, ring_amount, UNNEST(fork_indices) AS index FROM xmr_keyimages WHERE ring_amount = 0 AND block_height <= 2530000) AS xk INNER JOIN xmr_outputs xo ON xk.ring_amount = xo.amount AND xk.index = xo.index;

    Note: The only difference between the above query and the RingCT one in the previous Create Edges Table section is that the ring_indices column is replaced with the fork_indices column. Of course, the block height there was 1541236 to reproduce the results from Yu et al's FC 2019 paper.

Create the Transaction Graph

  1. Run the following query in the psql shell to write the edges file to disk. 
    \COPY (SELECT keyimage_id, output_id FROM xmr_bigraph_edges) TO '/tmp/fork-ringct-edges-2530000.txt' WITH DELIMITER ' ';
  2. Each row in the fork-ringct-edges-2530000.txt file represents an edge. The keyimage_id and output_id values that represent the edge are index values from the respective PostgreSQL tables. These index values do not form a contiguous range and can have gaps. But the sparse graph representations we will use work better without gaps in the index ranges.
    • Copy the fork-ringct-edges-2530000.txt file to the scripts/monero directory.
    • Compile the create_csparse_edges.cpp file located in the scripts/monero directory. Run it with the block height as argument. 
      cd scripts/monero
g++ -O2 create_csparse_edges.cpp 
./a.out 2530000 fork-ringct
      The output should look like the following. 
      Reading edge file
Finished reading edge file
Number of key images: 40351733
Number of outputs: 45805316
Number of vertices: 86157049
Number of edges: 409132035
Creating keyimage index map
Finished creating keyimage index map
Creating output index map
Finished creating output index map
Adding edges to graph
Finished adding edges to graph
    • Three output files are created.

      • fork-ringct-csparse-edges-2530000.txt

        The edges in this file are represented as pairs of indices starting from 0 followed by a 1. This is the CSparse format for representing sparse matrices. The 1 corresponds to the value of the matrix entry. In our case, we use this format to represent sparse bipartite graphs.

      • fork-ringct-index-keyimageid-map-2530000.txt

        This file has pairs of indices and key image IDs per line. It is to translate the result of the transaction graph analysis back to the key image ID space.

      • fork-ringct-index-outputid-map-2530000.txt

        This file has pairs of indices and output IDs per line. It is to translate the result of the transaction graph analysis back to the output ID space.

DM Decomposition Analysis

  1. Compile the Rust binaries by running cargo build --release (if not already done).

  2. Run the Dulmage-Mendelsohn decomposition program as follows.

    cargo run --release --bin dmdec fork-ringct-csparse-edges-2530000.txt fork-ringct-rings-before-dm-2530000.txt fork-ringct-rings-after-dm-2530000.txt fork-ringct-blocksizes-2530000.txt fork-ringct-fine-decomp-2530000.txt

    Note: The significance of the arguments to dmdec can be understood by running cargo run -r --bin dmdec -- --help or ./target/release/dmdec --help.

    The output should look like the following.

    Edge file read in 64.973245831s
Num keyimages = 40351733, Num public keys = 45805316
Matched 40351733 out of 45805316 rows (public keys)
Number of unreachable pubkeys and keyimages = 63120 63120
Number of blocks in fine decomposition: 63116
Singletons (traceable keyimages): 63115
Closed set size histogram: {1: 63115, 5: 1}

    The above output says that out of the 40351733 RingCT transaction rings in the data set, 63115 are traceable, i.e. the true output being spent in these transactions can be identified. Furthermore, there is a single closed set of size 5. This closed set corresponds to the five outputs which were deliberately spent using the same size 5 ring in the experiment by Wijaya et al.

  3. To calculate statistics related to the DM decomposition analysis, run the following command.

    cargo run --release --bin stats_dm fork-ringct-csparse-edges-2530000.txt fork-ringct-rings-before-dm-2530000.txt fork-ringct-rings-after-dm-2530000.txt

    Note: The significance of the arguments to stats_dm can be understood by running cargo run -r --bin stats_dm -- --help or ./target/release/stats_dm --help.

    The output should look like the following.

    Edge file read in 56.658098576s
Num keyimages = 40351733, Num public keys = 45805316
Pre DM decomposition rings file read in 72.727879975s
Pre DM decomposition mixin histogram:
[63060, 1214, 1556222, 141805, 2313832, 179183, 1577210, 294913, 55131, 16364, 34152799]
Post DM decomposition rings file read in 70.455324036s
Post DM decomposition mixin histogram:
[63115, 5224, 1556096, 213498, 2251506, 241582, 1515511, 285533, 52644, 62843, 34104181]
DM decomposition traceable ring mixin histogram:
[63060, 40, 9, 0, 5, 0, 1, 0, 0, 0, 0]

    The above output can be interpreted as follows.

    • Out of the 63115 traceable RingCT rings, 63060 had zero mixins (there were already traceable) before the DM decomposition, 40 had one mixin before the DM decomposition, 9 had two mixins, and so on.
    • In the above histograms, we combine all mixin counts of 10 or more. So 34152799 corresponds to the number of RingCT transaction rings with 10 or more mixins before the DM decomposition and 34104181 is the same number after the DM decomposition.

Closed Set Attack

  1. Compile the Rust binaries by running cargo build --release (if not already done).

  2. Perform the cascade attack first by running the following command.

    cargo run --release --bin cascade fork-ringct-csparse-edges-2530000.txt fork-ringct-rings-after-cascade-2530000.txt 10

    Note: The significance of the arguments to cascade can be understood by running cargo run -r --bin cascade -- --help or ./target/release/cascade --help.

    The output should look like the following.

    Edge file read in 59.538947568s
Num keyimages = 40351733, Num public keys = 45805316
Zero-mixin rings before CA = 63060
Zero-mixin rings after CA iteration 1 = 63115. Time taken = 232.824592ms.
Zero-mixin rings after CA iteration 2 = 63115. Time taken = 142.609136ms.
No change in number of traceable rings. Exiting cascade attack loop

    The above output shows that 63115 rings were traced by the cascade attack after the first iteration. As there was no change in the number of traceable rings in the second iteration, the program exited.

    Note: The alert reader would have noticed that the number of rings traced by the cascade attack (63115) is equal to the number of rings traced by the DM decomposition. As the DM decomposition achieves the best possible traceability performance, running the clustering algorithm can only hope to identify the closed set of size 5.

  3. Run the clustering algorithm attack by running the following command.

    cargo run --release --bin cluster fork-ringct-rings-after-cascade-2530000.txt fork-ringct-rings-after-cluster-2530000.txt

    Note: The significance of the arguments to cluster can be understood by running cargo run -r --bin cluster -- --help or ./target/release/cluster --help.

    The output should look like the following.

    Rings file read in 60.661705933s
Ring sets created in 10.862469778s
Counted initial number of traceable rings in 120.226064ms
Number of traceable rings = 63115
At beginning of clustering algorithm while loop
1: Cluster of size 5 found at key index 3313858. Search iteration = 1
Number of blocks in fine decomposition: 1
Singletons (traceable keyimages): 0
Number of traceable rings = 63115
Number of closed sets = 1
Number of singleton closed sets = 0
Number of non-singleton closed sets = 1
Closed set size histogram: {5: 1}
Number of public keys in all sets = 5
Number of public keys in non-singleton closed sets = 5
At beginning of clustering algorithm while loop
1: Cluster of size 5 found at key index 3313858. Search iteration = 2
Number of blocks in fine decomposition: 1
Singletons (traceable keyimages): 0
Number of traceable rings = 63115
Number of closed sets = 1
Number of singleton closed sets = 0
Number of non-singleton closed sets = 1
Closed set size histogram: {5: 1}
Number of public keys in all sets = 5
Number of public keys in non-singleton closed sets = 5
Pre attack mixin histogram:
 [63115, 5224, 1556095, 213486, 2251516, 241583, 1515510, 285536, 52644, 62841, 34104183]
Post attack mixin histogram:
 [63115, 5224, 1556096, 213498, 2251506, 241582, 1515511, 285533, 52644, 62843, 34104181]

    Note: The clustering algorithm for this data set can take a long time to finish running. It took 64 hours on our test machine. In contrast, the DM decomposition took 4 hours. The above output can be interpreted as follows.

    • The clustering algorithm does not find any singleton closed sets, other than the 63115 traceable rings output by the cascade attack. The DM decomposition had also rendered 63115 rings traceable. So it does not give better traceability performance for this dataset (except for the shorter running time).
    • There is a single closed set of size 5 that was also found by the DM decomposition.

  4. To calculate statistics related to the clustering algorithm, run the following command.

    cargo run --release --bin stats_cla fork-ringct-csparse-edges-2530000.txt fork-ringct-rings-after-cascade-2530000.txt fork-ringct-rings-after-cluster-2530000.txt

    Note: The significance of the arguments to stats_cla can be understood by running cargo run -r --bin stats_cla -- --help or ./target/release/stats_cla --help.

    The output should look like the following.

    Edge file read in 50.216200804s
Num keyimages = 40351733, Num public keys = 45805316
Initial mixin histogram:
[63060, 1214, 1556222, 141805, 2313832, 179183, 1577210, 294913, 55131, 16364, 34152799]
Post cascade attack rings file read in 62.181589318s
Post cascade attack mixin histogram:
[63115, 5224, 1556095, 213486, 2251516, 241583, 1515510, 285536, 52644, 62841, 34104183]
Cascade traceable ring pre-attack mixin histogram:
[63060, 40, 9, 0, 5, 0, 1, 0, 0, 0, 0]
Pre-attack mixin histogram of rings traced by cascade attack
0 63060
1 40
2 9
3 0
4 5
5 0
6 1
7 0
8 0
9 0
10 0
Total number of rings traced by cascade attack = 63115
Post clustering algorithm rings file read in 62.854710385s
Post clustering algorithm mixin histogram:
[63115, 5224, 1556096, 213498, 2251506, 241582, 1515511, 285533, 52644, 62843, 34104181]
Cluster traceable ring post-attack mixin histogram:
[63060, 40, 9, 0, 5, 0, 1, 0, 0, 0, 0]
Post-attack mixin histogram of rings traced by clustering algorithm
0 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0
10 0
Total number of rings traced by clustering algorithm = 0

    The above output can be interpreted as follows.

    • Out of the 63115 rings traced by the cascade attack, 63060 had zero mixins (there were already traceable) before the attack, 40 had one mixin before the attack, 9 had two mixins, and so on.
    • The clustering algorithm was not able to trace any rings over and above those traced by the cascade attack.

Non-RingCT Analysis

In this chapter, we describe the traceability analysis of non-RingCT transaction upto block height 2,530,000.

Create Edges Table

  1. Run the following command the psql shell to delete any previously created xmr_bigraph_edges table. 
    DROP TABLE xmr_bigraph_edges;

    Note: We delete the previously created xmr_bigraph_edges to recover disk space. The table occupies about 20 GB. If you have ample disk space available, you can skip the deletion. But remember to create the table in the next step with a name different from xmr_bigraph_edges. For example, you can use xmr_bigraph_edges_hardfork.

  2. Create the xmr_bigraph_edges table by running the following query in the psql shell. This query consider transactions upto block height 2530000. 
    CREATE TABLE xmr_bigraph_edges AS SELECT xk.id as keyimage_id, xo.id as output_id, xo.amount as output_amount, xo.index as output_index FROM (SELECT id, ring_amount, UNNEST(fork_indices) AS index FROM xmr_keyimages WHERE ring_amount <> 0 AND block_height <= 2530000) AS xk INNER JOIN xmr_outputs xo ON xk.ring_amount = xo.amount AND xk.index = xo.index;

    Note: The only difference between the above query and the RingCT one in Create Edges Table section is that the clause ring_amount = 0 is replaced by ring_amount <> 0.

Create the Transaction Graph

  1. Run the following query in the psql shell to write the edges file to disk. 
    \COPY (SELECT keyimage_id, output_id FROM xmr_bigraph_edges) TO '/tmp/fork-nonringct-edges-2530000.txt' WITH DELIMITER ' ';
  2. Each row in the fork-nonringct-edges-2530000.txt file represents an edge. The keyimage_id and output_id values that represent the edge are index values from the respective PostgreSQL tables. These index values do not form a contiguous range and can have gaps. But the sparse graph representations we will use work better without gaps in the index ranges.
    • Copy the fork-nonringct-edges-2530000.txt file to the scripts/monero directory.
    • Compile the create_csparse_edges.cpp file located in the scripts/monero directory. Run it with the block height as argument. 
      cd scripts/monero
g++ -O2 create_csparse_edges.cpp 
./a.out 2530000 fork-nonringct
      The output should look like the following. 
      Reading edge file
Finished reading edge file
Number of key images: 19443292
Number of outputs: 20800067
Number of vertices: 40243359
Number of edges: 44196439
Creating keyimage index map
Finished creating keyimage index map
Creating output index map
Finished creating output index map
Adding edges to graph
Finished adding edges to graph
    • Three output files are created.

      • fork-nonringct-csparse-edges-2530000.txt

        The edges in this file are represented as pairs of indices starting from 0 followed by a 1. This is the CSparse format for representing sparse matrices. The 1 corresponds to the value of the matrix entry. In our case, we use this format to represent sparse bipartite graphs.

      • fork-nonringct-index-keyimageid-map-2530000.txt

        This file has pairs of indices and key image IDs per line. It is to translate the result of the transaction graph analysis back to the key image ID space.

      • fork-nonringct-index-outputid-map-2530000.txt

        This file has pairs of indices and output IDs per line. It is to translate the result of the transaction graph analysis back to the output ID space.

DM Decomposition Analysis

  1. Compile the Rust binaries by running cargo build --release (if not already done).

  2. Run the Dulmage-Mendelsohn decomposition program as follows.

    cargo run --release --bin dmdec fork-nonringct-csparse-edges-2530000.txt fork-nonringct-rings-before-dm-2530000.txt fork-nonringct-rings-after-dm-2530000.txt fork-nonringct-blocksizes-2530000.txt fork-nonringct-fine-decomp-2530000.txt

    Note: The significance of the arguments to dmdec can be understood by running cargo run -r --bin dmdec -- --help or ./target/release/dmdec --help.

    The output should look like the following.

    Edge file read in 5.675253986s
Num keyimages = 19443292, Num public keys = 20800067
Matched 19443292 out of 20800067 rows (public keys)
Number of unreachable pubkeys and keyimages = 16526396 16526396
Number of blocks in fine decomposition: 16521000
Singletons (traceable keyimages): 16517926
Closed set size histogram: {1: 16517926, 2: 2301, 3: 600, 4: 48, 5: 22, 6: 8, 7: 15, 8: 11, 9: 8, 10: 5, 11: 5, 12: 4, 13: 6, 14: 4, 15: 6, 16: 5, 17: 5, 18: 4, 20: 3, 21: 2, 22: 1, 24: 1, 26: 1, 27: 1, 40: 1, 43: 1, 50: 1, 55: 1, 103: 1, 106: 1, 119: 1, 122: 1}

    The above output says that out of the 19443292 non-RingCT transaction rings in the data set, 16517926 are traceable, i.e. the true output being spent in these transactions can be identified. Furthermore, Furthermore, there are 2301 closed sets of size 2, 600 closed sets of size 3, and so on.

  3. To calculate statistics related to the DM decomposition analysis, run the following command.

    cargo run --release --bin stats_dm fork-nonringct-csparse-edges-2530000.txt fork-nonringct-rings-before-dm-2530000.txt fork-nonringct-rings-after-dm-2530000.txt

    Note: The significance of the arguments to stats_dm can be understood by running cargo run -r --bin stats_dm -- --help or ./target/release/stats_dm --help.

    The output should look like the following.

    Edge file read in 8.158130482s
Num keyimages = 19443292, Num public keys = 20800067
Pre DM decomposition rings file read in 8.336915518s
Pre DM decomposition mixin histogram:
[12305154, 707819, 2941534, 1345577, 974689, 143811, 406889, 12399, 9523, 6703, 589194]
Post DM decomposition rings file read in 5.167356902s
Post DM decomposition mixin histogram:
[16517926, 1408040, 836524, 165293, 122570, 33646, 38653, 47624, 73866, 80811, 118339]
DM decomposition traceable ring mixin histogram:
[12305154, 628547, 1800799, 965797, 465084, 76061, 219040, 4484, 3706, 2362, 46892]

    The above output can be interpreted as follows.

    • Out of the 16517926 traceable non-RingCT rings, 12305154 had zero mixins (there were already traceable) before the DM decomposition, 628547 had one mixin before the DM decomposition, 1800799 had two mixins, and so on.
    • In the above histograms, we combine all mixin counts of 10 or more. So 589194 corresponds to the number of non-RingCT transaction rings with 10 or more mixins before the DM decomposition and 118339 is the same number after the DM decomposition.

Closed Set Attack

  1. Compile the Rust binaries by running cargo build --release (if not already done).

  2. Perform the cascade attack first by running the following command.

    cargo run --release --bin cascade fork-nonringct-csparse-edges-2530000.txt fork-nonringct-rings-after-cascade-2530000.txt 20

    Note: The significance of the arguments to cascade can be understood by running cargo run -r --bin cascade -- --help or ./target/release/cascade --help.

    The output should look like the following.

    Edge file read in 5.86698341s
Num keyimages = 19443292, Num public keys = 20800067
Zero-mixin rings before CA = 12305154
Zero-mixin rings after CA iteration 1 = 16114012. Time taken = 5.256406281s.
Zero-mixin rings after CA iteration 2 = 16446848. Time taken = 321.346882ms.
Zero-mixin rings after CA iteration 3 = 16498286. Time taken = 119.520885ms.
Zero-mixin rings after CA iteration 4 = 16508535. Time taken = 86.453351ms.
Zero-mixin rings after CA iteration 5 = 16510655. Time taken = 77.153531ms.
Zero-mixin rings after CA iteration 6 = 16511170. Time taken = 76.002733ms.
Zero-mixin rings after CA iteration 7 = 16511327. Time taken = 76.250679ms.
Zero-mixin rings after CA iteration 8 = 16511347. Time taken = 74.742575ms.
Zero-mixin rings after CA iteration 9 = 16511360. Time taken = 71.64062ms.
Zero-mixin rings after CA iteration 10 = 16511362. Time taken = 71.276347ms.
Zero-mixin rings after CA iteration 11 = 16511362. Time taken = 71.379491ms.
No change in number of traceable rings. Exiting cascade attack loop

    The above output shows that 16511362 rings were traced by the cascade attack after the 10th iteration. As there was no change in the number of traceable rings in the 11th iteration, the program exited.

  3. Run the clustering algorithm attack by running the following command.

    cargo run --release --bin cluster fork-nonringct-rings-after-cascade-2530000.txt fork-nonringct-rings-after-cluster-2530000.txt

    Note: The significance of the arguments to cluster can be understood by running cargo run -r --bin cluster -- --help or ./target/release/cluster --help.

    The output should look like the following. The key index values may be different.

    Rings file read in 5.758398987s
Ring sets created in 1.864197658s
Counted initial number of traceable rings in 83.199978ms
Number of traceable rings = 16511362
At beginning of clustering algorithm while loop
1: Cluster of size 506 found at key index 21441. Search iteration = 1
Number of blocks in fine decomposition: 500
Singletons (traceable keyimages): 499
2: Cluster of size 641 found at key index 21450. Search iteration = 1
Number of blocks in fine decomposition: 628
Singletons (traceable keyimages): 627
3: Cluster of size 614 found at key index 23092. Search iteration = 1
Number of blocks in fine decomposition: 597
Singletons (traceable keyimages): 596
4: Cluster of size 352 found at key index 33335. Search iteration = 1
Number of blocks in fine decomposition: 346
Singletons (traceable keyimages): 345
.
.
.
3040: Cluster of size 8 found at key index 18822746. Search iteration = 2
Number of blocks in fine decomposition: 1
Singletons (traceable keyimages): 0
3041: Cluster of size 16 found at key index 18835335. Search iteration = 2
Number of blocks in fine decomposition: 1
Singletons (traceable keyimages): 0
3042: Cluster of size 13 found at key index 19272919. Search iteration = 2
Number of blocks in fine decomposition: 1
Singletons (traceable keyimages): 0
3043: Cluster of size 2 found at key index 19306398. Search iteration = 2
Number of blocks in fine decomposition: 1
Singletons (traceable keyimages): 0
Number of traceable rings = 16517613
Number of closed sets = 9296
Number of singleton closed sets = 6251
Number of non-singleton closed sets = 3045
Closed set size histogram: {2: 2299, 3: 600, 4: 47, 5: 22, 6: 8, 7: 15, 8: 11, 9: 7, 10: 5, 11: 4, 12: 4, 13: 4, 14: 2, 15: 2, 16: 3, 17: 3, 18: 2, 20: 1, 21: 1, 43: 1, 50: 1, 55: 1}
Number of public keys in all sets = 13876
Number of public keys in non-singleton closed sets = 7625
Pre attack mixin histogram:
[16511362, 1411442, 839076, 165559, 122742, 33713, 38693, 47630, 73900, 80811, 118364]
Post attack mixin histogram:
[16517613, 1408036, 836806, 165300, 122598, 33646, 38653, 47624, 73866, 80811, 118339]

    The above output can be interpreted as follows.

    • The clustering algorithm renders 6251 transaction rings traceable. The number of traceable rings increases from 16511362 (after the cascade attack) to 16517613. In comparison, the DM decomposition had rendered 16517926 rings traceable, i.e. 313 rings more than the clustering algorithm.
    • There are 2299 closed sets of size 2, 600 closed sets of size 3, and so on. Note that the maximum size of a closed set found by the clustering algorithm is 55. In contrast, the largest closed set found by the DM decomposition is 122.

  4. To calculate statistics related to the clustering algorithm, run the following command.

    cargo run --release --bin stats_cla fork-nonringct-csparse-edges-2530000.txt fork-nonringct-rings-after-cascade-2530000.txt fork-nonringct-rings-after-cluster-2530000.txt

    Note: The significance of the arguments to stats_cla can be understood by running cargo run -r --bin stats_cla -- --help or ./target/release/stats_cla --help.

    The output should look like the following.

    Edge file read in 6.417090529s
Num keyimages = 19443292, Num public keys = 20800067
Initial mixin histogram:
[12305154, 707819, 2941534, 1345577, 974689, 143811, 406889, 12399, 9523, 6703, 589194]
Post cascade attack rings file read in 5.539708542s
Post cascade attack mixin histogram:
[16511362, 1411442, 839076, 165559, 122742, 33713, 38693, 47630, 73900, 80811, 118364]
Cascade traceable ring pre-attack mixin histogram:
[12305154, 628161, 1797422, 964843, 464238, 75845, 218722, 4469, 3690, 2344, 46474]
Pre-attack mixin histogram of rings traced by cascade attack
0 12305154
1 628161
2 1797422
3 964843
4 464238
5 75845
6 218722
7 4469
8 3690
9 2344
10 46474
Total number of rings traced by cascade attack = 16511362
Post clustering algorithm rings file read in 7.221059516s
Post clustering algorithm mixin histogram:
[16517613, 1408036, 836806, 165300, 122598, 33646, 38653, 47624, 73866, 80811, 118339]
Cluster traceable ring post-attack mixin histogram:
[12305154, 628547, 1800515, 965790, 465062, 76061, 219040, 4484, 3706, 2362, 46892]
Post-attack mixin histogram of rings traced by clustering algorithm
0 0
1 386
2 3093
3 947
4 824
5 216
6 318
7 15
8 16
9 18
10 418
Total number of rings traced by clustering algorithm = 6251

    The above output can be interpreted as follows.

    • Out of the 16511362 rings traced by the cascade attack, 12305154 had zero mixins (there were already traceable) before the attack, 628161 had one mixin before the attack, 1797422 had two mixins, and so on.
    • Out of the 6251 rings traced by the clustering algorithm, 386 had one mixin after the cascade attack and before the clustering algorithm was executed, 3093 had two mixins, and so on.
    • In the above histograms, we combine all mixin counts of 10 or more.
      • So 589194 corresponds to the number of transaction rings with 10 or more mixins before the cascade attack, 118364 is the same number after the cascade attack, and 118339 is the number of rings which had 10 or more mixins after the clustering algorithm was executed.
      • Similarly, 46474 is the number of rings traced by the cascade attack that had 10 or more mixins before the attack. And 418 is the number of rings traced by the clustering algorithm that had 10 or more mixins before the algorithm was executed.