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.