tocurrency, signers of a transaction are hidden among

a set of potential signers, called a ring, whose size is

much smaller than the number of all users. The ring-

membership relations specified by the sets of transactions

thus induce bipartite transaction graphs, whose distribu-

tion is in turn induced by the ring sampler underlying the

cryptocurrency.

Since efficient graph analysis could be performed on

transaction graphs to potentially deanonymise signers, it

is crucial to understand the resistance of (the transaction

graphs induced by) a ring sampler against graph analy-

sis. Of particular interest is the class of partitioning ring

samplers. Although previous works showed that they

provide almost optimal local anonymity, their resistance

against global, e.g. graph-based, attacks were unclear.

In this work, we analyse transaction graphs induced by

partitioning ring samplers. Specifically, we show (partly

analytically and partly empirically) that, somewhat sur-

prisingly, by setting the ring size to be at least logarithmic

in the number of users, a graph-analysing adversary is no

better than the one that performs random guessing in

deanonymisation up to constant factor of}, address = {Warschau (Polen)}, author = {Egger, Christoph and Lai, Russell W. F. and Ronge, Viktoria and Woo, Ivy K. Y. and Yin, Hoover H.F.}, booktitle = {Proceedings on Privacy Enhancing Technologies}, doi = {10.56553/popets-2022-0085}, editor = {Kerschbaum, Florian; Mazurek, Michelle}, faupublication = {yes}, pages = {538–557}, peerreviewed = {Yes}, publisher = {Sciendo}, title = {{On} {Defeating} {Graph} {Analysis} of {Anonymous} {Transactions}}, url = {https://petsymposium.org/popets/2022/popets-2022-0085.pdf}, venue = {Sydney}, volume = {2022 (3)}, year = {2022} }