A fundamental limitation of Bitcoin and its variants is that the movement of coin between addresses can be observed by examining the public block chain. This record enables adversaries to link addresses to individuals, and to identify multiple addresses as belonging to a single participant. Users can try to hide this information by mixing, where a participant exchanges the funds in an address coin-for-coin with another participant and address. In this paper, we describe the weaknesses of extant mixing protocols, and analyze their vulnerability to Sybil-based denial-of-service and inference attacks. As a solution, we propose Xim, a two-party mixing protocol that is compatible with Bitcoin and related virtual currencies. It is the first decentralized protocol to simultaneously address Sybil attackers, denial-of-service attacks, and timing-based inference attacks. Xim is a multi-round protocol with tunably high success rates. It includes a decentralized system for anonymously finding mix partners based on ads placed in the block chain. No outside party can confirm or find evidence of participants that pair up. We show that Xim’s design increases attacker costs linearly with the total number of participants, and that its probabilistic approach to mixing mitigates Sybil-based denial-of-service attack effects. We evaluate protocol delays based on our measurements of the Bitcoin network.