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 csparse-edges-1541236.txt rings-after-cascade-1541236.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 6.780508534s
Num keyimages = 23164745, Num public keys = 25126033
Zero-mixin rings before CA = 12209675
Zero-mixin rings after CA iteration 1 = 15985204. Time taken = 4.434802555s.
Zero-mixin rings after CA iteration 2 = 16285257. Time taken = 277.680441ms.
Zero-mixin rings after CA iteration 3 = 16322672. Time taken = 111.501964ms.
Zero-mixin rings after CA iteration 4 = 16328236. Time taken = 87.87365ms.
Zero-mixin rings after CA iteration 5 = 16329045. Time taken = 83.504531ms.
Zero-mixin rings after CA iteration 6 = 16329176. Time taken = 83.173992ms.
Zero-mixin rings after CA iteration 7 = 16329215. Time taken = 82.656612ms.
Zero-mixin rings after CA iteration 8 = 16329215. Time taken = 82.576734ms.
No change in number of traceable rings. Exiting cascade attack loop

    The above output shows that 16329215 rings were traced by the cascade attack after 7 iterations. As there was no change in the number of traceable rings in the 8th iteration, the program exited.

  3. Run the clustering algorithm attack by running the following command.

    cargo run --release --bin cluster rings-after-cascade-1541236.txt rings-after-cluster-1541236.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 6.888624255s
Ring sets created in 2.083401154s
Counted initial number of traceable rings in 87.942429ms
Number of traceable rings = 16329215
At beginning of clustering algorithm while loop
1: Cluster of size 491 found at key index 21441. Search iteration = 1
Number of blocks in fine decomposition: 485
Singletons (traceable keyimages): 484
2: Cluster of size 593 found at key index 21450. Search iteration = 1
Number of blocks in fine decomposition: 580
Singletons (traceable keyimages): 579
3: Cluster of size 555 found at key index 23092. Search iteration = 1
Number of blocks in fine decomposition: 538
Singletons (traceable keyimages): 537
4: Cluster of size 346 found at key index 33335. Search iteration = 1
Number of blocks in fine decomposition: 340
.
.
.
3009: Cluster of size 2 found at key index 22416538. Search iteration = 2
Number of blocks in fine decomposition: 1
Singletons (traceable keyimages): 0
3010: Cluster of size 2 found at key index 22868731. Search iteration = 2
Number of blocks in fine decomposition: 1
Singletons (traceable keyimages): 0
3011: Cluster of size 15 found at key index 22868933. Search iteration = 2
Number of blocks in fine decomposition: 1
Singletons (traceable keyimages): 0
3012: Cluster of size 8 found at key index 22868960. Search iteration = 2
Number of blocks in fine decomposition: 1
Singletons (traceable keyimages): 0
Number of traceable rings = 16334967
Number of closed sets = 8765
Number of singleton closed sets = 5752
Number of non-singleton closed sets = 3013
Closed set size histogram: {2: 2278, 3: 596, 4: 44, 5: 23, 6: 8, 7: 14, 8: 11, 9: 7, 10: 4, 11: 4, 12: 4, 13: 3, 14: 2, 15: 2, 16: 2, 17: 3, 18: 2, 20: 1, 21: 1, 43: 1, 50: 1, 55: 1}
Number of public keys in all sets = 13230
Number of public keys in non-singleton closed sets = 7478
Pre attack mixin histogram:
[16329215, 1416089, 2372296, 279613, 2369745, 186294, 73721, 13095, 23646, 13068, 87963]
Post attack mixin histogram:
[16334967, 1413031, 2370099, 279384, 2369606, 186257, 73690, 13086, 23615, 13071, 87939]

    The above output can be interpreted as follows.

    • The clustering algorithm renders 5752 transaction rings traceable. The number of traceable rings increases from 16329215 (after the cascade attack) to 16334967. In comparison, the DM decomposition had rendered 16335308 rings traceable, i.e. 341 rings more than the clustering algorithm.
    • There are 2278 closed sets of size 2, 596 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 csparse-edges-1541236.txt rings-after-cascade-1541236.txt rings-after-cluster-1541236.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.987560875s
Num keyimages = 23164745, Num public keys = 25126033
Initial mixin histogram:
[12209675, 707786, 4496490, 1486593, 3242625, 319352, 432875, 21528, 30067, 17724, 200030]
Post cascade attack rings file read in 6.91789017s
Post cascade attack mixin histogram:
[16329215, 1416089, 2372296, 279613, 2369745, 186294, 73721, 13095, 23646, 13068, 87963]
Cascade traceable ring pre-attack mixin histogram:
[12209675, 625264, 1776192, 951984, 451230, 73980, 202100, 4282, 3490, 2162, 28856]
Pre-attack mixin histogram of rings traced by cascade attack
0 12209675
1 625264
2 1776192
3 951984
4 451230
5 73980
6 202100
7 4282
8 3490
9 2162
10 28856
Total number of rings traced by cascade attack = 16329215
Post clustering algorithm rings file read in 6.917414066s
Post clustering algorithm mixin histogram:
[16334967, 1413031, 2370099, 279384, 2369606, 186257, 73690, 13086, 23615, 13071, 87939]
Cluster traceable ring post-attack mixin histogram:
[12209675, 625641, 1779134, 952855, 451959, 74186, 202360, 4296, 3506, 2178, 29177]
Post-attack mixin histogram of rings traced by clustering algorithm
0 0
1 377
2 2942
3 871
4 729
5 206
6 260
7 14
8 16
9 16
10 321
Total number of rings traced by clustering algorithm = 5752

    The above output can be interpreted as follows.

    • Out of the 16329215 rings traced by the cascade attack, 12209675 had zero mixins (there were already traceable) before the attack, 625264 had one mixin before the attack, 1776192 had two mixins, and so on.
    • Out of the 5752 rings traced by the clustering algorithm, 377 had one mixin after the cascade attack and before the clustering algorithm was executed, 2942 had two mixins, and so on.
    • 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 cascade attack, 87963 is the same number after the cascade attack, and 87939 is the number of rings which had 10 or more mixins after the clustering algorithm was executed.
      • Similarly, 28856 is the number of rings traced by the cascade attack that had 10 or more mixins before the attack. And 321 is the number of rings traced by the clustering algorithm that had 10 or more mixins before the algorithm was executed.