Mixcoin is a Bitcoin mixing protocol proposed by Bonneau et al. which provides strong accountability guarantees [13]. However, in the Mixcoin protocol, the mapping from a user’s input to output address is visible to the mixing server. We modify the Mixcoin protocol to provide guarantees that the input/output address mapping for any user is kept hidden from the mixing server. In order to achieve this, we make use of a blind signature scheme [14,23] as well as an append-only public log. The scheme is fully compatible with Bitcoin, forces mixes to be accountable, preserves user anonymity even against a malicious mix, is resilient to denial of service attacks, and easily scales to many users.