So the fact that this mixed
ecosystem currently doesn't exist
is a big part of the reason why many
people have proposed decentralized mixing.
And there were a variety of reasons for
decentralized mixing,
some of which we've talked about,
in that there is no bootstrapping problem.
So the reason there's no bootstrapping
problem is that in decentralized mixing,
you don't go through a particular
dedicated mix service.
Instead, you find a community of
peers who all want to do mixing.
And somehow without any central
coordination, or at least
a central service that collects your
funds, you manage to mix with each other.
So that avoids the bootstrapping
problem because as long as there is
enough interest from Bitcoin users, they
can meet with each other and start mixing.
How to do that?
We'll see in a second.
Also theft is impossible, and
this is enforced through technical means.
Because nobody is explicitly
sending Bitcoins to another user.
Again, we'll see how this is accomplished.
It could possibly provide
better anonymity, and
we'll look into more
details on that as well.
And finally I just want to point out that
this is just more philosophically aligned
with Bitcoin.
If you can get rid of having to have
a centralized service for some purpose,
then there are a lot of users who
are Bitcoin users who find that appealing.
So how might this work?
The main proposal for a decentralized
mixing is called a Coinjoin.
And this is something that
was proposed by Greg Maxwell,
who's a core Bitcoin developer, who we'll
meet again in the next lecture actually.
So what he proposed is
different users coming together
to create a single Bitcoin transaction.
And what are the outputs
of this transaction?
We'll see in a second.
But somehow, create a single Bitcoin
transaction that combines all of
their inputs, presumably of equal value.
Now let's think about this for a second.
What is necessary in order for these three
users to create a single transaction?
Well one way of thinking about it,
we might imagine that in order to produce
a signature, somebody has to
collect all three private keys.
That's not actually how it works, though.
And Bitcoin,
all the signatures corresponding to
the different inputs are totally separate.
So each input signature
is entirely separate.
So what it allows the users to
easily do is create different
inputs that correspond to different users,
and also different output addresses that
correspond to different users, and
randomize the order between them.
So in this situation, maybe the users
participating in the protocol might
necessarily have to know which input
address corresponds to which output
address, although we'll see in
a second if we can avoid that as well.
But certainly,
someone looking at the block chain,
looking at only this single transaction.
Even if they realize that this
is a Coinjoin transaction,
will not be able to find the mapping
between the input and the output.
It's that simple.
That's the essence of Coinjoin.
Of course,
this is just one round of mixing.
On top of this, you have to apply the same
principles that we talked about before.
So the principles that I discuss,
they're not only for centralized mixes.
They apply essentially with
very few modifications,
even to the Coinjoin scenario.
So you want to do a sequence of Coinjoins.
You want to make sure that these
chunk slices are standardized so
that you don't introduce new
side channels, etc., etc.
Okay.
But let's look into this
single transaction, though.
Exactly how would this work?
There are a lot of details
that are still not clear.
So let's look at this in algorithmic form.
So if we write it out like this,
what needs to happen
is that a group of peers who all want
to mix somehow need to find each other.
That's the first difficulty.
And then they have to exchange their input
and output addresses with each other.
And one of these users, it doesn't matter
who, will construct this transaction,
not yet a signed transaction,
but just the transaction that
corresponds to these different inputs
going to these different outputs.
And then they'll pass it around to collect
signatures from each of the peers.
Now if the peer who
constructed the transaction
were disruptive and, for example,
left out one of the peer's outputs,
then the whole thing will collapse.
Because when that particular peer gets
the transaction in order to sign it,
they will simply refuse to sign, and the
process will not be able to go forward.
But if everything is okay,
everybody acts honestly,
then the transaction is constructed and
now any peer,
again it doesn't matter who, can
broadcast the transaction to the network.
Two of them could do it independently,
it doesn't matter.
The transaction will of
course be counted only once.
So that's it, that's the whole protocol.
The entire security property comes
from each peer checking that their
output address is represented,
and that their output, of course,
receives at least as much value
as went in from their input.
So that seems simple enough.
But what are the remaining problems here?
Well, there are three problems.
One is, how did this group
of peers find each other?
Right?
And the second is that, as I described
in the previous slide, this protocol
involves each of these peers finding out
the mapping between inputs and outputs.
Or at least one of those peers,
so that seems like a problem.
In fact, I want to point out
that this is a worse problem for
decentralized mixes than for
centralized mixes.
And why is that?
In the centralized mixing case,
you could hope that these different mixes
are run by entirely different entities
who are not colluding with each other.
And at least in some cases, these will
be reputable real life entities who you
would imagine have incentives
not to collude with each other
because they have different goals,
or for whatever reason.
Again, the reasoning is similar to Tor.
You have a variety of different types
of people who are running Tor nodes,
they don't all have the same incentives.
So we imagine that they're not all
going to collude with each other, and
also that they're not all going to
get compromised by the same attacker.
A similar principle holds for
decentralized mixes, and
that only works because you know something
about the identities of these mixes.
So these mixes,
having known identities and
being reputable entities,
helps anonymity in this case.
We don't have that luxury
with decentralized mixes,
because we have no idea who
any of these peers are.
Right?
So it could be a single attacker,
creating lots of Sybil accounts,
and accounts in the sense of just
creating lots of Sybils, and trying to get
into every single Coinjoin transaction
that's ever carried out in order to
learn these input output mappings.
And so even if you do a series of
Coinjoins, it might be the case that in
each of those Coinjoins, at least one
of the participants was an attacker, or
was controlled by the same attacker.
In which case,
your entire anonymity is lost.
So that seems like a problem.
And a third problem, and kind of a tricky,
one is denial of service.
What does this mean?
Well, it could happen that after
providing the input output pairs,
one of the nodes disappears and
refuses to sign the resulting transaction.
So the transaction is not
able to proceed forward.
And secondly,
even after creating the signature.
Before the transaction can get broadcast
to the network, and confirmed in a block
chain, one of the nodes, who might be
malicious, might take this input and
spend it in some other transaction
that's unrelated to this Coinjoin.
And so this Coinjoin will look
like a double spend attempt and
will be rejected by the Bitcoin network.
So that's another way in which you can
launch denial of service against Coinjoin.
So now let's look at what are some
possible solutions to each of
these three problems.
Well, the first one, how to find peers,
is a very simple solution.
It's not a perfect solution, but
people consider this to be somewhat okay.
You simply use an untrusted server.
It's sort of like a watering hole,
where different users can connect and
find each other.
But the server is not
necessarily involved in any way
that the users have to trust
in running the protocol.
All right.
And as we're going to see,
each of these steps for
solving these problems introduces
a little bit of engineering complexity.
So this already requires a whole
peer-to-peer protocol for
finding these Coinjoined peers
on top of the Bitcoin protocol.
And we're going to see similar factors
that introduce engineering complexity for
solving each of the other problems.
So the next one,
how do we solve the anonymity problem?
Well, there's a simple strawman solution.
You can frame the anonymity
problem in this way.
You need to communicate the set
of inputs to all the peers and
also you need to communicate
the set of outputs, but
break the linkage between the input and
the output.
Now this becomes a communications
anonymity problem
instead of a Bitcoin anonymity problem.
Because its simply the matter of
communicating these output addresses
that needs to be unlinked from
communication of the input addresses.
So a strawman's solution to that,
since we already have seen Tor
a little bit, is simply this.
These peers come together, they exchange
input addresses, and they disconnect and
then reconnect over Tor after awhile and
then exchange the output addresses.
So this is pretty simple, but
it may not be very robust in practice.
A better solution might be to build
a special purpose anonymous routing
mechanism for these participants
to utilize just for this protocol.
And there are things called decryption
mixed-nets that allow you to do
exactly that, and
such solutions have been proposed.
So let's move to the third problem
which is a denial of service attack.
Let's think about it this way.
What's a traditional solution
to a denial of service attack?
Well, one possible solution to denial
of service is to make it a little bit
expensive for the client to connect
to the server and to receive service.
Well this is not a client-server model,
it's a peer-to-peer model.
But we can still try to
adapt the same principles.
And that's the principle behind the first
two of the proposed solutions for
denial of service.
Either a proof of work,
or a proof of burn.
So what do I mean by this?
Proof of work is simply
repurposing the algorithm behind
Bitcoin's proof of work to
require each of these peer nodes
to do a little bit of computational work
before they can join a Coinjoin protocol.
And the rationale is that if the adversary
is going to disrupt every Coinjoin
that exists out there, they're going
to be burning a lot of computing power,
which will make it very expensive for
them.
Proof of burn is a similar concept.
It's also called fidelity
bonds in Bitcoin.
It allows you to irreversibly
destroy some Bitcoins that you
own by sending it to an unspendable
address, thereby proving that
you've made a little bit of an expensive
signal in order to get into the system.
So that's the rationale between
the first two solutions.
The second two solutions,
next to the third and fourth, also have
a similar rationale, which is to identify
the one or more malicious participants
who launched the denial of service,
to kick them out, and to run the Coinjoin
with the remaining participants.
And that could be done if you trust
the server a little bit to carry it out.
It could also be done in
a purely decentralized manner,
like this paper called
CoinShuffle proposed.
And they came up with a cryptographic
blaming protocol for doing this.
And it involves something
called zero knowledge,
where you learn at least one
of the players who misbehaved
without necessarily learning
much more about what happened.
And then the rest of the peers
can then redo the protocol.
At various points,
I've talked about side channels, so
let's look at an example of that.
And I want to point out that these
side channels can be very tricky.
Not all the mixing in
the world can save you from
what I call high-level flows
that could be identifying.
And here's a neat example of this.
Let's say user Alice receives
a very specific amount of Bitcoins,
let's say on a weekly basis as income.
And has the habit of
always automatically and
immediately transferring let's say
5% of that to her retirement amount.
All right, so
think about the patterns that will
be visible on the block chain here.
No matter what she does
to obscure the link
between the addresses at which
she receives her income and
the address to which she transfers to her
retirement account, the patterns here
are going to be uniquely identifying
because this is a very specific value.
And the 5% of that is also
going to be a specific value.
And there's also a timing pattern.
Every time money appears here, every
time money goes to this address as well.
So this is a problem.
How do we protect ourselves from this?
Well, one suggestion that
has been proposed is,
not only in the context of mixing.
But even in the context of regular
Bitcoin wallets, where users are not even
trying to do any mixing, is by Mike Hearn
and he calls this merge avoidance.
Merge avoidance is as very simple idea.
When users want to do payments,
the proposal is that instead of creating
a giant transaction that combines
as many inputs as necessary
in order to pay the entire payment to
a single address, why not have a protocol
by which the receiver can provide multiple
output addresses, as many as necessary.
And the sender and
receiver can agree upon denominations.
And the sender can avoid
combining different inputs and
can make a variety of
different transactions that
send money from different input
addresses to different output addresses.
So this avoids a lot of the problems
both of high-level flows, because
even these multiple input and output
addresses cannot be linked to each other.
So an adversary might not even be able to
observe the fact that this is a high-level
flow that's happening, but
also avoids problems like
clustering addresses together because
of evidence of shared spending.
And this is a proposal that one could
think about incorporating right now into
Bitcoin-based payment flows in order
to improve anonymity for everyone.