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.