  We consider the privacy of interactions between individuals in a network. For
many networks, while nodes are anonymous to outside observers, the existence of
a link between individuals implies the possibility of one node revealing
identifying information about its neighbor. Moreover, while the identities of
the accounts are likely hidden to an observer, the network of interaction
between two anonymous accounts is often available. For example, in blockchain
cryptocurrencies, transactions between two anonymous accounts are published
openly. Here we consider what happens if one (or more) parties in such a
network are deanonymized by an outside identity. These compromised individuals
could leak information about others with whom they interacted, which could then
cascade to more and more nodes' information being revealed. We use a
percolation framework to analyze the scenario outlined above and show for
different likelihoods of individuals possessing information on their
counter-parties, the fraction of accounts that can be identified and the
idealized minimum number of steps from a deanonymized node to an anonymous node
(a measure of the effort required to deanonymize that individual). We further
develop a greedy algorithm to estimate the \emph{actual} number of steps that
will be needed to identify a particular node based on the noisy information
available to the attacker. We apply our framework to three real-world networks:
(1) a blockchain transaction network, (2) a network of interactions on the dark
web, and (3) a political conspiracy network. We find that in all three
networks, beginning from one compromised individual, it is possible to
deanonymize a significant fraction of the network ($>50$%) within less than 5
steps. Overall these results provide guidelines for investigators seeking to
identify actors in anonymous networks, as well as for users seeking to maintain
their privacy.
