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.