P2P Mixing and Unlinkable Bitcoin Transactions

Author(s):
Tim Ruffing, Pedro Moreno-Sanchez, Aniket Kate

Download: Paper (PDF)

Date: 27 Feb 2017

Document Type: Reports

Additional Documents: Slides Video

Associated Event: NDSS Symposium 2017

Abstract:

Starting with Dining Cryptographers networks (DC-nets), several peer-to-peer (P2P) anonymous communication protocols have been proposed. However, despite their strong anonymity guarantees, none of them have been employed in practice so far: Most protocols fail to simultaneously address the crucial problems of slot collisions and disruption by malicious peers, while the remaining ones handle f malicious peers with O(f2) communication rounds. We conceptualize these P2P anonymous communication protocols as P2P mixing, and present a novel P2P mixing protocol, DiceMix, that needs only four communication rounds in the best case, and 4 + 2f rounds in the worst case with f malicious peers. As every individual malicious peer can force a restart of a P2P mixing protocol by simply omitting his messages, we find DiceMix with its worst-case complexity of O(f) rounds to be an optimal P2P mixing solution.

On the application side, we employ DiceMix to improve anonymity in crypto-currencies such as Bitcoin. The public verifiability of their pseudonymous transactions through publicly available ledgers (or blockchains) makes these systems highly vulnerable to a variety of linkability and deanonymization attacks. We use DiceMix to define CoinShuffle++, a coin mixing protocol that enables pseudonymous peers to perform unlinkable transactions in a manner fully compatible with the current Bitcoin system. Moreover, we demonstrate the efficiency of our protocols with a proof-of-concept implementation. In our evaluation, DiceMix requires less than eight seconds to mix 50 messages (160 bits, i.e., Bitcoin addresses), while the best protocol in the literature requires almost three minutes in the same setting.

Finally, we present a deanonymization attack on existing P2P mixing protocols that guarantee termination in the presence of disruptive peers. We generalize the attack to demonstrate that no P2P mixing protocol simultaneously supports arbitrary input messages, provides anonymity, and terminates in the presence of disruptive peers. DiceMix resists this attack by requiring fresh input messages, e.g., cryptographic keys never used before.