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.