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-