cess to the corresponding RSA decryption key d, it is not possible for anyone to retrieve e at this point. The key property is that the second part of the puzzle, c, is a symmetric key encryption of signature σ using e as the key. That is, if B could decrypt the RSA encryption and retrieve e, he would be able to use it to decrypt c, retrieve e, and post the necessary release transaction to claim the bitcoins escrowed by M.

Then, during a payment phase, B will utilize A to get a solution for the puzzle. For this, B sends A a blinded version of z, by choosing randomness r and sending z′ = re z mod N. Then A sends z′ to M, asking him to provide a solution e′ for this version of the puzzle. M can do this easily, since he holds the decryption key d. (Note that M cannot link this interaction with B as z′ is randomized and cannot be related to z.) This involves an interactive fair-exchange protocol between A and M which allows A to get the puzzle’s solution while allowing M to obtain a release transaction for the escrow they set up during the previous phase, signed only by her. Finally, A sends e to B who computes e =e′ r and checks whether ee= z mod N (in which case he “accepts” A’s payment). The fair exchange protocol guarantees that A gets the solution to the RSA puzzle if-and-only-if M gets a release on the escrowed transaction.

Lastly, during a cash-out phase, M signs his part of the release transaction for the escrow A set up and B uses e to retrieve the encrypted signature by M on their escrow, which he additionally signs himself. Both parties post the signed release escrow transactions claiming the escrowed values and this concludes the protocol, since the bitcoins “traveled” from A to B via M.

Assuming k sender/recipient pairs during a single TumbleBit epoch, all of which mix the same value, the anonymity property achieved by TumbleBit guarantees that M cannot deduce the corresponding sender for a given recipient, based on his entire epoch view (expect with probability 1/k). To avoid leaking additional information based on the timing of different protocol phases, all mixing transaction phases are synchronized and take a predetermined amount of time. Moreover, the fair-exchange protocol guarantees that as “something to hide”).

There exist multiple providers (for example, Bitmixer,c Bitlaunder,d Helixe) that offer this service for a small mixing fee with varying degrees of adoption. However, the most notable problem is that this approach requires “blindly trusting” the mixer. What if the mixer goes out of business? What if it is forced (for example, via a subpoena) to reveal the actual transaction links? Most importantly, what if it simply steals the coins? All these are valid issues and have indeed been, to some extent, observed in practice (for example, see Möser27).

Avoiding coin theft by the mixer. To mitigate the problem of coin theft by the mixer, Bonneau et al. proposed Mixcoin, 8 a Bitcoin mixer that holds the provider accountable. Theft is still possible but it can be reported via the use of signed warrants. In particular, before receiving A’s coins, the mixer signs a statement of “if A sends me x BTC by time t1, I will send x′BTC back to B by time t2” (where x′ is slightly smaller than x to account for a mixing fee) and sends this statement (with off-chain communication) to A. In case the mixer does not follow up on its end, A can publish this warrant damaging its reputation.

The first solution to truly avoid the
possibility of coin theft was CoinSwap, 21
whose main building block is a timed-
escrow protocol between two parties
(also known as a 2-of- 2 escrow). At a
high level, a timed-escrow protocol
that transfers money from Alice to Bob
is implemented with the following
transactions. The initial transaction is
posted by Alice and places a number
of bitcoins in escrow for a time win-
dow t. For Bob to claim these coins,
a release transaction must be posted,
signed by both Alice and Bob, before
time t. Otherwise, the funds return to
Alice. CoinSwap avoids coin theft by
the mixer using two correlated timed-
escrow protocols, one between the
payer and the mixer and one between
the mixer and the recipient, such that
the recipient receives the money if and
only if the mixer receives money from
the sender. The downside of Coinswap
is it requires multiple rounds of inter-
action and waiting for the validation of
c https://bitmixer.io
d https://bitlaunder.com
e https://helix-light.com
at least two blocks in the blockchain.
Moreover, like Mixcoin, it also exposes
the participants’ identities to the mixer.
Hiding users’ identities from the
mixer. Blindcoin37 is an extension to
Mixcoin that utilizes blind signatures
for the warrants. Blind signatures11
operate like regular cryptographic sig-
natures but allow a party to sign a mes-
sage without knowing the message’s
exact content. A user A that wishes to
mix her coins initially provides only
a commitment to a fresh address she
owns, “blinded” by a random value.
After receiving the warrant from the
mixer, A can remove the randomness
and publish the address to a public log
that contains all addresses to which
the mixer must forward coins for that
epoch. This completely hides the link
between input and output address of a
user even from the mixer itself, achiev-
ing full unlinkability. However, since
Blindcoin builds on Mixcoin it can
only offer a limited notion of security: a
cheating mixer can steal a participant’s
coins, but the participant can prove
that a theft took place thus damaging
the mixer’s reputation.
Achieving full security and unlink-
ability. A more recent proposal is
TumbleBit, 16 which simultaneously
achieves full unlinkability and avoids
coin theft. TumbleBit merges tech-
niques from secure two-party compu-
tation and zero-knowledge proofs in
order to protect the user’s privacy and
the validity of the transaction (includ-
ing enforcing the mixer to carry it out
honestly). At the core of TumbleBit is
the notion of an RSA puzzle. In order
for a party A to anonymously send a
number of bitcoins to party B (assum-
ing B has just established a fresh public
address) via a mixer M, the interaction
proceeds in three phases as follows.

First, during an escrow phase, A posts an initial escrow transaction for a number of bitcoins to M and B contacts M requesting that M post a similar initial escrow transaction toward him. Assume that the signature that B needs from M in order to claim the escrowed value is σ. Moreover, B obtains from M (via an off-chain protocol execution) an RSA puzzle that consists of two values z, c. The former is z = ee mod N for some e where N, e is the public RSA key of M (that is, z is a deterministic RSA “ encryption” of e). Recall that without ac-