Mixing

Loading...

En provenance du cours de Princeton University

Bitcoin and Cryptocurrency Technologies

1899 notes

Princeton University

Bitcoin and Cryptocurrency Technologies

1899 notes

To really understand what is special about Bitcoin, we need to understand how it works at a technical level. We’ll address the important questions about Bitcoin, such as: How does Bitcoin work? What makes Bitcoin different? How secure are your Bitcoins? How anonymous are Bitcoin users? What determines the price of Bitcoins? Can cryptocurrencies be regulated? What might the future hold? After this course, you’ll know everything you need to be able to separate fact from fiction when reading claims about Bitcoin and other cryptocurrencies. You’ll have the conceptual foundations you need to engineer secure software that interacts with the Bitcoin network. And you’ll be able to integrate ideas from Bitcoin in your own projects. Course Lecturers: Arvind Narayanan, Princeton University All the features of this course are available for free. It does not offer a certificate upon completion.

À partir de la leçon

Bitcoin and Anonymity

Is Bitcoin anonymous? What does that statement even mean—can we define it rigorously? We'll learn about the various ways to improve Bitcoin's anonymity and privacy and learn about Bitcoin's role in Silk Road and other hidden marketplaces.

Anonymity Basics26:42

How to de-anonymize Bitcoin18:13

Decentralized Mixing14:21

Zerocoin and Zerocash19:47

Tor and the Silk Road11:10

Rencontrer les enseignants

Arvind Narayanan
Associate Professor
Computer Science

So there are a variety of solutions to

what we've been calling transaction graph anonymization.

Or transaction graph analysis, pardon me.

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 whatnot.

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 merge 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 they put in, they're going to get some other, say,

randomly picked deposit that the intermediary receives.

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 blockchain,

who doesn't have the records that the intermediary might or

might not store, just from the publicly available information in the blockchain,

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 SO Crib 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 ModGaks which you can think of sort of as an online wallet service.

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

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 as a side effect they randomly

give you Bitcoins that came from some other address.

But they specifically say that they won't keep records.

So even if they tried to,

they wouldn't know which Bitcoins were the one you put in.

So with the high probability you're going to get some other good coins back.

And furthermore, even if someone came knocking for the 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 these 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, the bill typically require your identity.

In banking there is the know your customer principle, which essentially at

a technical level translates to learn the customers 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 withdraw 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'd 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 withdrawal that you made.

And so, when you make a series of withdrawals from an online wallet and

proceed 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 gonna happen is you're gonna keep them in the wallet service for

much longer than you typically would with a mixed service.

Why? Because

you don't trust in a mixed server as much.

You want to put it in your Bitcoins and you want to receive it back

immediately from some other address, an address of your choosing.

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 blockchain,

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 have a bigger anonymity set

than you possibly would with using a mixing service.

Or at least with using the 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 the essentialized 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 the traditional system.

And so those were not the kind of people who were typically looking for

anonymity in Bitcoin anyway, if they were happy with the anonymity properties

of the traditional system 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 services,

online wallets services require and

they don't want the sort of anonymity properties that it gives.

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 and the reason for this is that

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 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 that got together, researchers at Princeton, Concordia, and

Maryland, including all four of us who are doing this on-line lecture series and

analyse the existing mix ecosystem and proposed a series of changes for

improving the way 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 it 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 wanna 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 and

the anonymous communication system tour, and it's a good idea because

it allows you to not have to trust a single mix but

instead to be sure as long as any one of these mixes

is promising to delete it's records, then you have a good guarantee of anonymity.

And in particular, mixes should implement a standard API so

that this can be very easy for clients to accomplish, and right now,

this 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 will 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 have 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 mix transactions that other users are executing and

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 principle 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 link ability is minimized.

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

from 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 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 in to 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 are 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 outward 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 one out of 1000 times,

the mix should swallow the entire chunk and 999 times out of a 1000,

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 is

not cheated in generating this random number and has genuinely flipped

a coin which has a 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 and has worked correctly.

We think that really all four of these principles are necessary to have anything

approaching mathematical confidence and having a large anonymity set.

And in our ability to resist clever inferential attacks by

an adversary that looks at the botching, 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 will 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.

So this is, we don't think this is a situation that gives mix 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 mixed in 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 users' 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 they 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

that 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 100 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 in mind 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 the 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 it 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 has cheated.

And so everybody will stop using this mix, and the mix will lose business.

In combination, all 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 the original is also highlighted in

red, so I took the liberty of doing that myself.

Mixing services may themselves be operation with anonymity, and so if you're

funds are not delivered you have no recourse, you use at your own discretion.

So we're proposing moving to a different model, where mixes stay in business,

become reputable entities and so on.

That hasn't quite happened yet.

And note that there's a 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.

So users would be more confident in interacting with them, and

mixers 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.

And 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.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2019 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play