So there are a variety of
solution to inhibit what we've
been calling transaction graph analysis,
and the first of them is called mixing.
So what is mixing?
Well, the intuition behind this is very,
very simple.
It's the same intuition that
comes up in a lot of contexts,
which is that if you want anonymity,
use an intermediary to route your
communications or your funds or what not.
So let's look at what that
might look like visually.
Here's an intermediary.
And in a second, we'll get to who
these intermediaries might be.
But assume that there
is some intermediary,
some service that allows
users to put in BitCoins.
But the key property
that it gives you is that
after these BitCoins have been put in,
it forgets who put them in, and
treats its entire store of BitCoins
as indistinguishable from each other.
And in fact it might further combine them
all into one giant transaction, or it
might further mix them or split them and
arrange them in different ways, whatever.
But the key property is, that when users
later come in to withdraw their Bitcoins,
it's not tied to the coin
that they put in.
They're going to get some other,
say randomly picked deposit
that the intermediary received.
So when these three users come back,
they're going to withdraw
these coins in a random order.
And so somebody looking at this in the
block chain, who doesn't have the records
that the intermediary might or might not
store just from the publicly available
information in the block chain, is not
going to be able to link the ultimate
input addresses to the ultimate output
addresses corresponding to the same user.
So that's the intuition
behind intermediaries.
Now, looking at this,
does that strike a chord?
Have we seen,
in previous lectures, something that
offers services that are similar to this?
That allows you to deposit BitCoins and
then withdraw them later at a later time.
You might recall that this is
exactly what online wallets do.
There are services where you can
just store your bitcoins online,
until you need them.
And so, you might wonder,
well is that the solution to our problems?
Do online wallets provide anonymity?
Let's think about that.
The answer to this is not obvious.
But I will start by mentioning that it's
taken well-known researchers by surprise.
Here was a post on
the New York Times' Bits blog,
reporting on a preprint of a paper
released by two Israeli researchers,
saying that there was a link between
Dread Pirate Roberts, the pseudonymous
creator of Silk Road which we're going
to see more about, and Satoshi Nakamoto.
This was, of course, very surprising.
But as it turned out, all that had
happened was that they had mistook this
link that went through an intermediary,
and that intermediary just turned out to
be Mount Gox, which you can think of
sort of as an online wallet service.
And so a few days later,
this other post was published at the same
menu, see if you can spot the difference.
They had to retract their study and
I think they had made a very simple
mistake of not accounting for
the presence of this intermediary.
So, it's clear that, at least in some
sense, online wallets provide some sort of
anonymity, because at least somebody tried
to make a connection between an input and
an output address and
completely failed at that.
So let's try to understand exactly
the sense in which online wallets provide
anonymity, and I think a good way
to do that would be to in fact
contrast online wallets with online
services that exist specifically for
the purpose of acting as these
intermediaries for anonymity, and
those are going to be
dedicated mixing services.
We'll talk about mixing services
in much more detail, but
very briefly the two things that
they promise: that you won't get
simply by putting your BitCoins
into an online wallet and
retrieving that again,
is that they promise not to keep records.
It's not just that as a side effect,
they sort of randomly give you BitCoins
that came from some other address, but
they specifically say that they won't keep
records, and so even if they tried to,
they wouldn't know which BitCoins
were the ones you put in.
And so, with a high probability, you're
going to get some other BitCoins back.
And, furthermore, even if someone
came knocking for their records or
if they got hacked and so on,
there would be nothing to find.
There would be no records.
So that's something that
a mixing service promises.
And the other thing is that you
don't need your real-life identity
in order to interact with the services.
And this is in contrast to
most of these online wallets.
Why?
Because online wallets are typically
reputable and in fact,
often regulated businesses.
And this fact has two consequences.
One is that they all typically
require your identity.
In banking,
there is the know your customer principle,
which essentially at a technical level,
translate to learn the customer's
identity and store those records.
And in fact, they will keep records,
if they receive a deposit,
they will keep the link between
the identity and the Bitcoin address.
If they move money around internally, they
will probably keep records of all of that.
And just because when you would draw
your BitCoins they come from a different
address, does not mean that the online
wallet does not know the link.
That link probably does exist in
their records and will exist for
all eternity, even if they don't
explicitly ask for your identity.
Think about this.
To even interact with an online wallet,
you do need a persistent
long term identity.
You can't possibly use
a different pseudonym every time.
Because if you did, they would have no way
of associating an account with you knowing
how many BitCoins they owed you.
Right, so because of that,
even if they didn't ask for your identity,
at the very least, the online
wallet knows the address of every
single deposit that you made of the
bitcoins that you put into the system and
more importantly,
every single withdraw that you made.
And so when you make a series of
withdraws from an online wallet and
precede to spend those bitcoins,
the wallet service can now connect
all of those together in a profile.
And of course it's not just
the wallet service, people who care
about anonymity are also worried
about those records getting hacked.
Insider attacks,
somebody who has a subpoena for
getting those records,
and so on and so forth.
So, with respect to the wallet
service itself, and
whoever they might be cooperating with,
you have no anonymity in this context.
On the other hand,
there is something cool about this.
If you are willing to trust
them with your BitCoins, then
what's going to happen is you're going
to keep them in the wallet service for
much longer than you typically
would with a mix service.
Why?
Because you don't trust in mix
servers as much.
You want to put in your BitCoins and
you want to receive it back
immediately from some other address
at an address of your serving.
Right?
So unlike that, for
an online wallet service you're going
to have a bigger anonymity set.
Why?
Because your anonymity set,
from the point of view of someone
with no privileged information,
from the point of view of someone who's
merely looking at the block chain,
your withdrawal could
look indistinguishable
from every single withdrawal ever
made from that service provider.
So with respect to the wallet service,
you have no anonymity.
With respect to everybody else, you'd have
a bigger anonymity set than you possibly
would with using a mixing service, or at
least with using a single mixing service.
So if we look at this, this looks
suspiciously similar to the kind of
privacy properties that you have
with the traditional banking system.
There are these centralized intermediaries
that know a lot about our transactions.
But from the point of view of a stranger
with no privileged information,
we have a pretty good amount of privacy.
So, even if this gives you
some sort of anonymity,
it's almost at best what you get with
a traditional system, and so those are not
the kind of people who are typically
looking for anonymity in BitCoin anyway.
If they were happy with their anonymity
properties of the traditional system,
And they would have probably
stayed with that system.
And so
generally people who are looking for
anonymity properties in Bitcoin simply
do not want to accept the trust
requirements that these online
wallet services require.
And they don't want the sort of
anonymity properties that it gives you.
They don't want to have to trust
that service with their anonymity.
And in fact,
we've seen that there have been a lot of
closures of these exchanges and services.
And so there's good reason for
believing that if you put all your trust
in an online service,
you might simply lose your money.
Okay, so having rejected online wallets
as an anonymity solution, let's turn
to these dedicated mixing services
that I told you a little bit about.
Before looking at their details, let's
talk about the terminology a little bit.
I like to call it a mix,
some people call it a mixer.
These are really the same thing.
Some people also call them laundries,
I don't like this term at all.
The reason why is because it needlessly
attaches moral meaning to something that's
a purely technical term.
As we've seen earlier,
there are very good reasons why
you might want to protect
your privacy in Bitcoin and
use mixes for entirely good reasons,
for everyday privacy.
Of course,
we must also acknowledge the bad uses.
But it seems a little bit weird
to me to use the term laundry,
that implies that your coins are dirty and
you need to clean them,
and attaching a negative moral
value to the whole thing.
Which, and for that reason, I'm not
going to use that term in this lecture.
We'll go with the technically
neutral term, which is mixing.
So, in talking about mixing,
there are several of us,
about six of us, who got together.
Researchers at Princeton, Concordia, and
Maryland, including all four of us who
are doing this online lecture series.
And analyzed the existing mix ecosystem
and proposed a series of changes for
improving the ways that mixes operate,
both in terms of anonymity and
the trustworthiness of mixes.
So, let's look at those principles.
Before I show you those principles,
as a quick reminder, at a very fundamental
level, how does a mix operate?
It asks for an address at which
you want to receive Bitcoins, and
gives you an address to
send Bitcoins to the mix.
And then,
you both execute that transaction.
It's a swap, basically.
In a second, I'll show you
what that looks like visually.
But what were our principles for
running these mixes properly?
Well, the very first one is that you
might want to use a series of mixes
instead of just a single mix, and
this is a very well-known principle.
Using a series of routers
is the same principle in
the anonymous communication system TOR.
And it's a good idea, because it allows
you to not have to trust a single mix.
But instead, be sure that as long as
any one of these mixes is promising
to delete its records, then you
have a good guarantee of anonymity.
And in particular, mixes should implement
a standard API so that this could be
very easy for clients to accomplish, and
right now, this is not quite the case.
And this is our paper for your reference.
So, now let's go in and
look at what a series of mixes would
look like visually, so, here it is.
Here is a user, who starts with a coin,
or an input address,
that we assume that the adversary has
managed to link to this particular user.
They're going to send it to
the mix at this address and
get back a Bitcoin at this other
output address that they provide.
They freshly generate this output address
and provide that address to the mix.
The mix will hopefully return the same
amount of Bitcoins at this output address,
there's no way for
the user to force the mix to do that.
The user has to trust the mix,
and this is, as we'll see,
a recurring problem with
the whole notion of mixes.
And either immediately or
after a time gap,
it doesn't matter, the user will take
the Bitcoin or Bitcoins of whatever
value they've received at this address and
send it to a different mix.
Which is hopefully not cooperating
with the first mix and
repeat this process over and over again.
So from an adversary's point of view,
looking at the public block chain,
they're merely going to see along
with all of these transactions,
a variety of other mixed transactions
that other users are executing.
And will, hopefully, the adversary will
have no way to tell apart which of those
transactions correspond to
this particular user and
which one corresponds to some other users.
So that's the first principal.
And the second one, if you think about
what I've just said, in order to make that
possible you want to make these
transactions as uniform as possible, so
that this linkability is minimized.
And what does it mean to make these
transactions as uniform as possible?
One important consequence is that
all of these mixed transactions,
not only from a particular mix, but
all of the mixes in this mix ecosystem,
should have the same value.
So we think that all mixes out there
providing service should agree upon
a chunk size.
A standard chunk size, and of course
there can be multiple denominations, but
there can't be too many.
And you can't simply allow the users
to put in whatever amount of Bitcoins
they wish to, that wouldn't work.
So you need this kind of standardization.
In addition to this, we found that there
are a variety of possible attacks in which
a clever adversary might
infer various things.
Not just the amount, even if you remove
the amount, some other properties,
including timing for example, in order
to try to link users input addresses and
output addresses together.
This type of linking can be avoided but
human users,
if they interact with the mix,
are not going to be
able to take into account all of
those possible linking attacks.
So instead, what needs to be done is this
client side software must be automated and
built into desktop wallet software.
So that this desktop wallet
software automatically knows how to
interact with these mixes in order
to preserve the user's anonymity.
So that was our third principle.
Our fourth principle is a subtle one.
Now these mixes,
why do they provide this service?
Typically, it's because
they're a business.
And if they're a business,
they want to be paid.
How are they going to get paid?
Well, it turns out that pretty much
the only way for these mixers to get
paid is to take a cut of the transaction
that the user is sending to the mix.
That seems a bit weird, because if
a mix takes a standard percentage,
then an adversary might be able to use
that to link the input transaction and
the output transaction.
So some current mixes try to
randomize the transaction fee,
they might say we take a random
cut between 1% and 3%.
We found that this is
not a good idea either,
because if you put that
through a chain of mixes.
Then the amount of the value in the chunk
is going to dwindle in a predictable way,
and this is an important side channel for
the adversary.
So what is a way to avoid this?
We proposed that these mixed
fees should be all or nothing.
In other words, the mix should
either swallow the whole chunk
with a small probability, or
should return the whole chunk.
So if the mix wants to charge
a 0.1% mixing fee, this is,
by the way, very different from the
transaction fee that mining notes charge.
This is a mixing fee on top of that.
So if the mix wants to
charge a 0.1% mixing fee,
then 1 out of 1,000 times,
the mix should swallow the entire chunk.
And 999 times out of 1,000,
the mix should return the entire
chunk without taking any mixing fee.
This is a tricky property to accomplish,
which means that the mix should generate
a random number in a way that can convince
the user that the mix has not cheated
in generating this random number.
And has genuinely flipped
a coin which has 99.9%
chance of coming up one
way versus the other.
But we do show how to do this using
cryptography in a way that both
parties can be satisfied
has worked correctly.
We think that really all four of these
principles are necessary to have anything
approaching mathematical confidence
in having a large anonymity set, and
in our ability to resist clever
inferential attacks by an adversary that
looks at the blotching to
try to link input to output.
The sad news is that virtually, none of
the current mixes follow these principles.
They're in a very different model,
where each mix operates
completely independently, and
they have a web interface.
And the user interacts with
them totally manually,
instead of automatically
through their wallet software.
And we'll manually put in the amount.
Instead of standard chunk size,
it's whatever amount
the user chooses typically.
And the mix will take some cut
of that as a mixing fee and
send the rest to the user.
We don't think this is a situation that
gives mixed users a lot of anonymity, but
we think that by moving to a slightly
different model based on these
four principles,
the anonymity properties of the mixed
ecosystem can be dramatically improved.
All right, so
through these four principles we've seen
how the anonymity properties
of mixing can be improved.
But there is still one major
problem which is that users
still have to trust these mixes.
So again we had a few ways that
we talked about in our paper for
what to do about this.
Mixes can do several things to
improve their trustworthiness.
One is that,
simply by staying in business for
a long time, and not stealing user's
money, they can build up a reputation.
You might wonder,
does this reputation count for
anything, because it's simply
a matter of he said, she said.
In fact, a mix operator can claim
that a competing mix operator
stole all their money,
even if that did not in fact happen.
Well, generally,
reputation systems in the real world
manage to operate even though there can
be conflicting claims that are made.
In this context, for example.
Users might learn to only trust the word
of prominent members of the BitCoin
community who they think have the best
interests of the ecosystem at heart.
Another way is that in
the system that we proposed,
the chunk sizes are going to be so small
that in the regular course of mixing,
users are going to mix a pretty
huge number of chunks.
Or at least the system can be
configured in that way, so
the chunk sizes are relatively small.
So in that context, if a mix has even
a one percent probability of stealing
a user's chunk, then after a hundred or
so interactions, with small chunk
sizes with a particular mix.
The user is going to know.
The user is going to detect the theft, and
so the user will learn to
never use this mix again.
And so the system might sort of correct
itself by users, testing mixes for
themselves for trustworthiness.
An important thing to keep mind in here is
that the chunks that users are sending to
mixes have typically already
been through other mixes.
So the mix itself can't know which
user the chunk is coming from.
And so the only thing the mix can do is
to essentially steal randomly from users.
The mix can't steal
from a particular user.
So from a user point of view,
on average, they won't suffer losses
that are more than the average
rate at which the mix steals.
So they don't have to worry that a mix
might particularly have it in for
that particular user, and
steal all of their money.
There's no way that that can happen.
So that's what I mean when I say
users can test this for themselves.
And finally, we proposed a cryptographic
mechanism where the mix can issue sort of
a promissory statement to the user, that
once it receives a chunk at a particular
address it will send a chunk back at some
other address that the user provides.
And so, if the mix fails to keep this
promise, our idea is that the user can
publicize this warranty and everybody will
know that a particular mix is cheated.
And so everybody will stop using this
mix and the mix will lose business.
And in combination, all of these three
mechanisms provide incentives for
mixes to act honestly.
So these were our calculations anyway,
and our proposal.
We haven't proved that this
will work in practice.
That remains to be seen.
All right.
On that note, let's quickly look at
how things are in practice right now.
It doesn't seem that
there are any reputable
services providing dedicated mixing
that users have learned to trust, or
at least enough to use on a regular basis.
In fact, this is from the BitCoin Wiki
where original is also highlighted in red.
I took the liberty of doing that myself.
Mixing services may themselves
be operating with anonymity.
So, if your funds are not delivered,
you have no recourse.
Use at your own discretion.
So, we are proposing moving to a different
model where mixes stay in business,
become reputable businesses, and so on.
That hasn't quite happened yet.
And note that is sort of
a bootstrapping problem here.
If mixes were reputable entities they
would have a big volume of transactions,
and so by interacting with them you'd
get a pretty good anonymity set.
And so users would be more confident
in interacting with them, and
mixes would realize that they're making
more money by staying in business and
taking a small cut,
than by trying to steal
the small amount of money that
they're controlling at any given time.
So mixes would be further
incentivized to stay in business.
So you can imagine that once
a mixed ecosystem gets going,
it will be self sustaining.
But whether or not that can
eventually happen, we can say for
sure that it hasn't quite happened yet.