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.