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
How to de-anonymize Bitcoin
Loading...
来自 Princeton University 的课程
比特币和数字货币技术
1715 个评分
从本节课中
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.
与讲师见面
Arvind NarayananAssistant Professor
Computer Science
All right.
I said several times earlier, that Bitcoin is only pseudonymous and
so all of your transactions or addresses could get linked together.
Let's now go in and see how that might actually happen.
Let's in fact start from WikiLeaks again.
I showed you a quote from them saying Bitcoin is a secure and
anonymous digital currency, and this is actually the page that was taken from.
This is their donations page, and here you'll see that in addition to this blurb
about Bitcoin being secure and anonymous, they have a donation address over here.
This is of course, the hash of a public key.
You've seen things like this in previous lectures, but
they also have this interesting refresh button right next to that.
What do you imagine this refresh button might do?
Well, as you might expect,
if you click on that refresh button, it'll give you an entirely new donation address.
Let's go in and take a look at that.
So, a totally new address popped up on the page.
So what is going on here?
What WikiLeaks is doing, is it's making sure that each time a person visits
the page, each time a person wants to visit the page and make a donation.
They send that donation to a totally new public key that WikiLeaks creates just for
that purpose.
So here Wikileaks is taking advantage of the ability to create new synonyms,
new public keys to their maximum.
Every single transaction that they receive they want to receive it a new address.
And in fact, this is the Bitcoin best practice for
anonymity, to always receive new transactions at a fresh address.
So you might look at this and
think, surely then these different addresses must be unlinkable.
You receive a transaction over here and
then much later you spend it by sending it to someone else.
You receive another transaction at this address and
then you send it to someone else over there.
So how might somebody link?
Well, here's the key.
Let's imagine the scenario.
Alice, a customer, goes to a big box store and wants to buy a teapot.
So in the scenario Alice has a few Bitcoin's lying around
with these different denominations, and the store lists the teapot for
a price of eight Bitcoin's.
That's a pretty expensive teapot at today's exchange rate, so
imagine that's 70 Bitcoins or something, if you like.
Any rate, Alice has these different addresses and wants to pay for the teapot.
How is she going to accomplish this?
She doesn't actually have an address with eight Bitcoins sitting in there.
And so what she's going to do is, she's going to combine several different input
transactions into a single transaction, in order to pay eight Bitcoins to the store.
So this reveals something.
For somebody who's looking at this transaction that gets recorded permanently
in the blockchain,
they're gonna think aha, two different inputs to this transaction.
That could only happen because both of these input addresses are under
the control of the same user, they were able to use their wallet software to
create a transaction that combined both of them into one.
In other words shared spending is evidence of joint control
of two different addresses, and it doesn't stop there.
This is not just about linking two different addresses that are inputs to
a transaction.
You can do that transitively, and
every time Alice has a whole cluster of addresses that have been linked.
And then she creates a new transaction that combines one of those addresses with
a new address, you can add this new address to the cluster.
So this is the first insight behind being able to link transactions together.
And we'll see later on that an anonymity technique called coin join works by
violating exactly this assumption.
But, if you assume that people are just using regular Bitcoin wallet software,
not doing anything special on top of it.
Then this technique tends to be pretty robust, and
this has been explored in a variety of research papers.
And just a note about this lecture, a lot of what we're gonna be discussing today
gets into the frontiers of where the research knowledge are.
So a lot of this, the state of the art may have advanced in a few months or
a few years.
So every time I talk about a technique that we know from a particular research
paper, I'll give you a reference to that paper.
So that you can look it up.
You can look up papers that cite it, and
you can build up that knowledge on your own.
Now in particular, one of the papers that used this technique used it for
a particular purpose.
There was a well publicized Bitcoin theft a few years ago, and
what they wanted to do, the authors of this paper decided to see how this
thief has been moving Bitcoins around between multiple addresses of his own.
And so this is that paper in question,
it's called An Analysis of Anonymity in the Bitcoin System.
So this is one of the first major research efforts
that did what we call transaction graph analysis.
So, you can use the techniques that I showed you in previous slides, and
you can draw a lot of these pretty graphs and deduce that this represents
the thief moving many around between his own different addresses.
This is the thief sending many to someone else and various things like that.
I haven't yet shown you anything that allows you to link any of these clusters
to real world identity, but let's defer that question for a bit.
Let's defer that question and go back to the scenario of Alice and the teapot.
So let's look at it again.
Maybe the teapot has gone up in price to 8.5 centiBitcoins.
So what is Alice gonna do now?
She can't combine any subsets of her transactions or her addresses to produce
the exact amount of change necessary for purchasing this teapot.
So instead what she's going to do is exploit the fact that transactions can
have any number of inputs and outputs, and
create a single transaction that looks like this.
It combines these two inputs to produce this output that goes over here and
another output that goes to an address that she herself owns, and
this is called a change address, which you saw in a previous lecture.
This presents a conundrum for an adversary whose looking at this.
The adversary might be able to deduce that these two addresses belong to
the same user.
You might suspect that one of these addresses also belongs to that same user,
but has no way of knowing which one that is.
In this particular example, the change address is a small amount, but
it doesn't have to be that way at all.
Alice might own an address that has 10,000 Bitcoins, and
might spend a little bit on the teapot, and
might send most of the rest of it back to her at her own change address.
And these transaction outputs don't have any particular ordering in the blockchain.
That order is not meaningful at all.
So it's not clear what the adversary might do.
It's not clear how the adversary might determine
which address is changed in a multi output transaction.
So what is the adversary to do?
There's another pretty cool technique for this again, from a research paper,
which I'll tell you about, but the technique is this.
The authors call this idioms of use, and
they exploit idiosyncratic features of different wallet software.
For example, one thing they found is that most wallet software
use an address as a change address only once.
That means that this in fact seems to sort of follow Bitcoin best practice for
anonymity in a sense.
If you have a new transaction where you need to create a new change address,
don't use an address that you've already used before as a change address.
Create a new address and use it for this purpose.
Now, not all addresses that are outputs of transactions might have this property.
Going back to the example of the big box store,
the store might advertise a long term address at which it wants to receive
Bitcoins instead of receiving Bitcoins at a different address every time.
So, not every non-change address has this property, that it's used only once
as a change address, but every change address does have that property.
So they used this, and they found that it works pretty well.
On the other hand, this has some limitations.
It just happens to be a feature of wallet software, and
so there are a lot of false positives that might creep in
to these clustering techniques, if you use techniques like this.
So, it required a lot of manual intervention.
Nevertheless, they were able to use the technique that I showed you before,
which is clustering shared inputs together,
as well as a few heuristics for a change address detection.
And then what they were able to do, is they were able to look at the entire
Bitcoin transaction graph, and create some giant clusters that they
hypothesized belongs to various major service providers.
And here's what that graph looks like, after applying these two heuristics, and
here's the paper in question.
This is by Sarah Meiklejohn and others, as a whole bunch of authors of this paper.
Now, this graph looks very interesting here.
The sizes of these circles represent
the amount of money flowing into those clusters, and
the number of edges going out of a cluster represent the number of transactions.
Let's try to just stay with this for a second, and see if we can guess what some
of these major service providers and other cluster of nodes might be.
This huge one here that dominates in transaction volume compared to any other
cluster, given that this paper was written in 2013, we might guess that it's Mt Gox,
which was a very prominent exchange at the time, that later went under.
Now, we might also guess that this little one here that only has a little bit of
transaction volume, in spite of having a very large number of transactions
sort of corresponds to the profile of the gambling service, the Satoshi Dice.
Because the way that it works is you send a tiny amount of Bitcoins and
you either win that bet, or you lose that bet, and so
you might get double the Bitcoins, or none of the Bitcoins.
So that's the gambling service of Satoshi Dice.
We might guess that it's this one here, we might guess that it's Mt Gox, and so on,
but this kind of guessing is sub-optimal.
The authors wanted some sort of reliable way of identifying what are the service
providers corresponding to each of these clusters.
How did they do that?
Well, one idea you might have is, you might think oh, why not go to
the Mt Gox website and see what address they advertise for receiving Bitcoins.
Well, that doesn't quite work, because they're going to advertise a new address
for every single transaction, and if you just go to the website,
look at the address, and actually don't complete that transaction, you don't send
Bitcoins there, then they're simply going to discard that address.
They're not going to reuse that address for another customer.
In other words, that address will never get used.
You simply won't find it in the blockchain.
So what's the way around this?
Well, the only way to reliably infer addresses that are associated
with a service provider is to actually transact with that service provider,
which is exactly what the authors did.
They went ahead and
bought a variety of things and interacted in a variety of other ways
with a bunch of service providers comprising 344 transactions in all.
Mining pools, wallet services, exchanges, various merchants,
even gambling sites and so on.
They got a bunch of cool things to show for their efforts and
Meiklejohn informs me that in fact the cupcakes were really good.
At any rate, the author's used this very clever technique to go ahead and
label the major clusters in the graph that I showed you on the previous slide,
and so this is what the labeled graph looks like.
In fact, this was Mt Gox, as we might have guessed.
This was Satoshi Dice, but a lot of the others would have been very difficult
to guess, and by actually transacting with these services,
they were able to identify most of these service providers.
So already now, we've seen something pretty interesting beyond just clustering,
being able to put labels on the clusters.
So the next question is, sure you can do these labels for
these major service providers.
Can you put labels for individuals?
So in other words,
connect little clusters corresponding to individuals to their real life identities.
Well there's a least a couple of different ways in which that can happen.
One is intuitively, what I told you right at the beginning,
you could simply interact at a coffee shop, or with some other merchant.
So they learn some transaction or
some address that corresponds to you and they might use that to tag your cluster.
There are at least a couple of other ways in which this might happen, and
one is that there's high centralization in these service providers.
So the intuition here is that most users in the course of normal usage of Bitcoin
over a period of months or years are going to interact with at least one
of those major service providers that were labeled in the previous graph.
So, if somebody wants to identify a cluster corresponding to
a particular user.
There's a very high chance that they're going to be able to identify a transaction
that ties that cluster with a known labeled cluster.
And then they can go to that service provider and
if they have the appropriate authority, subpoena that service provider, or
if they're a hacker, try to hack into that service provider and so on.
So, this is one major avenue in which regular users can get de-anonymized
because they eventually, inevitably interact with one of these major,
easily identified service providers.
Another one is simply carelessness.
A lot of users end up posting address information in forums.
They might post one of the Bitcoin addresses that they own for
example, to receive donations when they're posting comments on forums.
Now that might be because these users are not worried about getting de-anonymized.
It could also be because they don't realize that posting one of their
addresses is almost going to inevitably allow somebody
to To connect all of their different addresses together.
Okay, so hopefully I've convinced you there are clever ways that an attacker
might utilize in order to not only link different addresses or
transactions belonging to a user, but go from there to real world identity.
And our experience, our history of these denominization algorithms
shows that they only get more powerful with time.
And more auxiliary information as we call it, for
attackers to utilize in order to link together to get to users' identities.
So this is something to worry about if you care about privacy.
Before we look at how to make things better for anonymity,
let's look at a completely different way in which users can get de-anonymized.
So far what we've looked at is all based on
what is available to the attacker in the blockchain.
Right, the part that is permanently and publicly recorded, but
recall that that's not the only part of Bitcoin.
There is also a peer to peer network, in which a lot of messages are sent around
that don't necessarily get permanently recorded in the blockchain.
So the blockchain in networking terminology is called the application
layer, and the peer to peer network is of course, the networking layer.
And so de-anonymization can happen at this totally different layer at
the networking layer.
Well, how could that happen?
Here is an example.
This was first pointed out by Dan Kaminsky a few years ago in a talk at Black Hat.
Here's the peer to peer network.
What he noticed is that when a node creates a transaction and
wants to broadcast it, it's going to connect to a lot of nodes at once and
broadcast that transaction.
And so, if a few nodes on the network put their heads together, they can figure
out that hey, this new transaction, this is the first we heard of it,
and all of us first heard of it from this particular node.
So this must be the node,
this must be the IP address corresponding to the user who created this transaction.
So here you have a linkage not between a cluster and a real world identity.
Instead, you have a linkage between a transaction and IP address, and
of course, IP address is something that's very close to real world identity.
There are a lot of ways to go from there to the next level with finding identity.
So, this is already a serious problem.
Luckily though, this is not a very hard problem to solve.
Why? Because this is
now a problem of communications anonymity, and communicating anonymously
is a problem that has received a lot of attention from the research community.
And as we already saw in the introduction,
there is a good system called Tor that you can use for communicating anonymously.
Now, there's one little caveat.
Tor is intended for what is called low-latency activity,
such as web browsing.
Where there is a large volume of flow, and you don't want to sit around waiting for
too long and you get the response immediately.
So it makes some compromises in anonymity in order to achieve low-latency.
Bitcoin is inherently a high-latency system, because it takes a while for
transactions to propagate through the network, and
especially to get confirmed in the blockchain.
So we don't have this low-latency constraint.
So it's possible that we could come up with a more specific,
fine tuned anonymity network for this particular purpose.
And there are such things called mix nets, the only problem is that Tor is a system
that's most widely deployed and analyzed, and robust, and functional today.
But it's possible that somebody might develop a mixed net solution for
anonymizing your Bitcoin communications,
and if that happens, that would be something to switch to.
So let's summarize what we've learned so far.
We've seen that based on the information in the blockchain, different addresses
could get linked together, could also get linked to identity.
We've also seen that based on the information at the network layer,
a transaction or address could get linked to your IP address.
Luckily, this latter problem is simple to solve.
If you care about your anonymity and privacy when using Bitcoin,
it's a good idea to do it through tour, but the former problem is much trickier,
and that's what we're going to spend the rest of this lecture talking about.
