1
00:00:02,270 --> 00:00:06,680
So the fact that this mixed
ecosystem currently doesn't exist

2
00:00:06,680 --> 00:00:11,600
is a big part of the reason why many
people have proposed decentralized mixing.

3
00:00:12,890 --> 00:00:16,080
And there were a variety of reasons for
decentralized mixing,

4
00:00:16,080 --> 00:00:20,190
some of which we've talked about,
in that there is no bootstrapping problem.

5
00:00:20,190 --> 00:00:24,710
So the reason there's no bootstrapping
problem is that in decentralized mixing,

6
00:00:24,710 --> 00:00:27,740
you don't go through a particular
dedicated mix service.

7
00:00:27,740 --> 00:00:31,930
Instead, you find a community of
peers who all want to do mixing.

8
00:00:31,930 --> 00:00:35,760
And somehow without any central
coordination, or at least

9
00:00:35,760 --> 00:00:40,200
a central service that collects your
funds, you manage to mix with each other.

10
00:00:40,200 --> 00:00:43,120
So that avoids the bootstrapping
problem because as long as there is

11
00:00:43,120 --> 00:00:47,280
enough interest from Bitcoin users, they
can meet with each other and start mixing.

12
00:00:47,280 --> 00:00:47,840
How to do that?

13
00:00:47,840 --> 00:00:48,630
We'll see in a second.

14
00:00:50,160 --> 00:00:53,810
Also theft is impossible, and
this is enforced through technical means.

15
00:00:53,810 --> 00:00:57,650
Because nobody is explicitly
sending Bitcoins to another user.

16
00:00:57,650 --> 00:00:59,710
Again, we'll see how this is accomplished.

17
00:01:00,750 --> 00:01:02,800
It could possibly provide
better anonymity, and

18
00:01:02,800 --> 00:01:05,230
we'll look into more
details on that as well.

19
00:01:05,230 --> 00:01:08,850
And finally I just want to point out that
this is just more philosophically aligned

20
00:01:08,850 --> 00:01:09,780
with Bitcoin.

21
00:01:09,780 --> 00:01:13,535
If you can get rid of having to have
a centralized service for some purpose,

22
00:01:13,535 --> 00:01:17,040
then there are a lot of users who
are Bitcoin users who find that appealing.

23
00:01:18,440 --> 00:01:20,110
So how might this work?

24
00:01:20,110 --> 00:01:24,830
The main proposal for a decentralized
mixing is called a Coinjoin.

25
00:01:24,830 --> 00:01:28,230
And this is something that
was proposed by Greg Maxwell,

26
00:01:28,230 --> 00:01:31,439
who's a core Bitcoin developer, who we'll
meet again in the next lecture actually.

27
00:01:32,780 --> 00:01:37,460
So what he proposed is
different users coming together

28
00:01:37,460 --> 00:01:39,580
to create a single Bitcoin transaction.

29
00:01:39,580 --> 00:01:41,340
And what are the outputs
of this transaction?

30
00:01:41,340 --> 00:01:42,020
We'll see in a second.

31
00:01:42,020 --> 00:01:46,340
But somehow, create a single Bitcoin
transaction that combines all of

32
00:01:46,340 --> 00:01:49,004
their inputs, presumably of equal value.

33
00:01:51,200 --> 00:01:52,719
Now let's think about this for a second.

34
00:01:52,719 --> 00:01:58,070
What is necessary in order for these three
users to create a single transaction?

35
00:01:58,070 --> 00:02:01,110
Well one way of thinking about it,
we might imagine that in order to produce

36
00:02:01,110 --> 00:02:04,270
a signature, somebody has to
collect all three private keys.

37
00:02:05,490 --> 00:02:07,240
That's not actually how it works, though.

38
00:02:07,240 --> 00:02:08,110
And Bitcoin,

39
00:02:08,110 --> 00:02:11,619
all the signatures corresponding to
the different inputs are totally separate.

40
00:02:12,690 --> 00:02:15,700
So each input signature
is entirely separate.

41
00:02:15,700 --> 00:02:20,750
So what it allows the users to
easily do is create different

42
00:02:20,750 --> 00:02:24,440
inputs that correspond to different users,
and also different output addresses that

43
00:02:24,440 --> 00:02:28,359
correspond to different users, and
randomize the order between them.

44
00:02:30,060 --> 00:02:33,680
So in this situation, maybe the users
participating in the protocol might

45
00:02:33,680 --> 00:02:37,350
necessarily have to know which input
address corresponds to which output

46
00:02:37,350 --> 00:02:40,900
address, although we'll see in
a second if we can avoid that as well.

47
00:02:40,900 --> 00:02:43,700
But certainly,
someone looking at the block chain,

48
00:02:43,700 --> 00:02:46,480
looking at only this single transaction.

49
00:02:46,480 --> 00:02:49,520
Even if they realize that this
is a Coinjoin transaction,

50
00:02:49,520 --> 00:02:52,610
will not be able to find the mapping
between the input and the output.

51
00:02:53,670 --> 00:02:54,340
It's that simple.

52
00:02:54,340 --> 00:02:55,550
That's the essence of Coinjoin.

53
00:02:56,810 --> 00:02:59,750
Of course,
this is just one round of mixing.

54
00:02:59,750 --> 00:03:03,708
On top of this, you have to apply the same
principles that we talked about before.

55
00:03:03,708 --> 00:03:07,700
So the principles that I discuss,
they're not only for centralized mixes.

56
00:03:07,700 --> 00:03:10,890
They apply essentially with
very few modifications,

57
00:03:10,890 --> 00:03:12,080
even to the Coinjoin scenario.

58
00:03:13,210 --> 00:03:15,250
So you want to do a sequence of Coinjoins.

59
00:03:15,250 --> 00:03:19,040
You want to make sure that these
chunk slices are standardized so

60
00:03:19,040 --> 00:03:22,060
that you don't introduce new
side channels, etc., etc.

61
00:03:23,620 --> 00:03:24,120
Okay.

62
00:03:24,120 --> 00:03:26,590
But let's look into this
single transaction, though.

63
00:03:26,590 --> 00:03:28,130
Exactly how would this work?

64
00:03:28,130 --> 00:03:30,700
There are a lot of details
that are still not clear.

65
00:03:30,700 --> 00:03:33,280
So let's look at this in algorithmic form.

66
00:03:33,280 --> 00:03:37,020
So if we write it out like this,
what needs to happen

67
00:03:37,020 --> 00:03:41,900
is that a group of peers who all want
to mix somehow need to find each other.

68
00:03:41,900 --> 00:03:43,820
That's the first difficulty.

69
00:03:43,820 --> 00:03:48,370
And then they have to exchange their input
and output addresses with each other.

70
00:03:48,370 --> 00:03:52,890
And one of these users, it doesn't matter
who, will construct this transaction,

71
00:03:52,890 --> 00:03:56,450
not yet a signed transaction,
but just the transaction that

72
00:03:56,450 --> 00:03:59,662
corresponds to these different inputs
going to these different outputs.

73
00:03:59,662 --> 00:04:05,350
And then they'll pass it around to collect
signatures from each of the peers.

74
00:04:05,350 --> 00:04:09,860
Now if the peer who
constructed the transaction

75
00:04:09,860 --> 00:04:12,330
were disruptive and, for example,

76
00:04:12,330 --> 00:04:16,730
left out one of the peer's outputs,
then the whole thing will collapse.

77
00:04:16,730 --> 00:04:22,210
Because when that particular peer gets
the transaction in order to sign it,

78
00:04:22,210 --> 00:04:26,450
they will simply refuse to sign, and the
process will not be able to go forward.

79
00:04:27,890 --> 00:04:30,750
But if everything is okay,
everybody acts honestly,

80
00:04:30,750 --> 00:04:33,470
then the transaction is constructed and
now any peer,

81
00:04:33,470 --> 00:04:37,220
again it doesn't matter who, can
broadcast the transaction to the network.

82
00:04:37,220 --> 00:04:39,610
Two of them could do it independently,
it doesn't matter.

83
00:04:39,610 --> 00:04:41,640
The transaction will of
course be counted only once.

84
00:04:42,780 --> 00:04:44,740
So that's it, that's the whole protocol.

85
00:04:44,740 --> 00:04:48,564
The entire security property comes
from each peer checking that their

86
00:04:48,564 --> 00:04:52,321
output address is represented,
and that their output, of course,

87
00:04:52,321 --> 00:04:55,592
receives at least as much value
as went in from their input.

88
00:04:57,984 --> 00:04:59,492
So that seems simple enough.

89
00:04:59,492 --> 00:05:02,000
But what are the remaining problems here?

90
00:05:02,000 --> 00:05:04,060
Well, there are three problems.

91
00:05:04,060 --> 00:05:06,530
One is, how did this group
of peers find each other?

92
00:05:07,620 --> 00:05:08,150
Right?

93
00:05:08,150 --> 00:05:13,900
And the second is that, as I described
in the previous slide, this protocol

94
00:05:13,900 --> 00:05:17,810
involves each of these peers finding out
the mapping between inputs and outputs.

95
00:05:17,810 --> 00:05:21,190
Or at least one of those peers,
so that seems like a problem.

96
00:05:21,190 --> 00:05:23,470
In fact, I want to point out
that this is a worse problem for

97
00:05:23,470 --> 00:05:26,840
decentralized mixes than for
centralized mixes.

98
00:05:26,840 --> 00:05:27,880
And why is that?

99
00:05:27,880 --> 00:05:32,470
In the centralized mixing case,
you could hope that these different mixes

100
00:05:32,470 --> 00:05:36,360
are run by entirely different entities
who are not colluding with each other.

101
00:05:36,360 --> 00:05:40,922
And at least in some cases, these will
be reputable real life entities who you

102
00:05:40,922 --> 00:05:44,940
would imagine have incentives
not to collude with each other

103
00:05:44,940 --> 00:05:48,550
because they have different goals,
or for whatever reason.

104
00:05:48,550 --> 00:05:50,480
Again, the reasoning is similar to Tor.

105
00:05:50,480 --> 00:05:54,750
You have a variety of different types
of people who are running Tor nodes,

106
00:05:54,750 --> 00:05:56,486
they don't all have the same incentives.

107
00:05:56,486 --> 00:05:59,700
So we imagine that they're not all
going to collude with each other, and

108
00:05:59,700 --> 00:06:02,970
also that they're not all going to
get compromised by the same attacker.

109
00:06:04,100 --> 00:06:07,130
A similar principle holds for
decentralized mixes, and

110
00:06:07,130 --> 00:06:11,110
that only works because you know something
about the identities of these mixes.

111
00:06:11,110 --> 00:06:13,230
So these mixes,
having known identities and

112
00:06:13,230 --> 00:06:15,929
being reputable entities,
helps anonymity in this case.

113
00:06:17,380 --> 00:06:20,040
We don't have that luxury
with decentralized mixes,

114
00:06:20,040 --> 00:06:22,300
because we have no idea who
any of these peers are.

115
00:06:23,440 --> 00:06:25,470
Right?
So it could be a single attacker,

116
00:06:25,470 --> 00:06:29,850
creating lots of Sybil accounts,
and accounts in the sense of just

117
00:06:29,850 --> 00:06:34,590
creating lots of Sybils, and trying to get
into every single Coinjoin transaction

118
00:06:34,590 --> 00:06:39,150
that's ever carried out in order to
learn these input output mappings.

119
00:06:39,150 --> 00:06:43,270
And so even if you do a series of
Coinjoins, it might be the case that in

120
00:06:43,270 --> 00:06:47,890
each of those Coinjoins, at least one
of the participants was an attacker, or

121
00:06:47,890 --> 00:06:50,070
was controlled by the same attacker.

122
00:06:50,070 --> 00:06:52,240
In which case,
your entire anonymity is lost.

123
00:06:52,240 --> 00:06:54,990
So that seems like a problem.

124
00:06:54,990 --> 00:07:00,200
And a third problem, and kind of a tricky,
one is denial of service.

125
00:07:00,200 --> 00:07:01,240
What does this mean?

126
00:07:01,240 --> 00:07:05,370
Well, it could happen that after
providing the input output pairs,

127
00:07:06,510 --> 00:07:09,670
one of the nodes disappears and
refuses to sign the resulting transaction.

128
00:07:11,290 --> 00:07:13,250
So the transaction is not
able to proceed forward.

129
00:07:14,970 --> 00:07:18,030
And secondly,
even after creating the signature.

130
00:07:18,030 --> 00:07:22,156
Before the transaction can get broadcast
to the network, and confirmed in a block

131
00:07:22,156 --> 00:07:25,870
chain, one of the nodes, who might be
malicious, might take this input and

132
00:07:25,870 --> 00:07:29,610
spend it in some other transaction
that's unrelated to this Coinjoin.

133
00:07:29,610 --> 00:07:32,620
And so this Coinjoin will look
like a double spend attempt and

134
00:07:32,620 --> 00:07:34,420
will be rejected by the Bitcoin network.

135
00:07:35,530 --> 00:07:38,660
So that's another way in which you can
launch denial of service against Coinjoin.

136
00:07:40,020 --> 00:07:42,900
So now let's look at what are some
possible solutions to each of

137
00:07:42,900 --> 00:07:43,800
these three problems.

138
00:07:45,170 --> 00:07:49,650
Well, the first one, how to find peers,
is a very simple solution.

139
00:07:49,650 --> 00:07:54,940
It's not a perfect solution, but
people consider this to be somewhat okay.

140
00:07:54,940 --> 00:07:58,140
You simply use an untrusted server.

141
00:07:58,140 --> 00:08:01,500
It's sort of like a watering hole,
where different users can connect and

142
00:08:01,500 --> 00:08:02,390
find each other.

143
00:08:02,390 --> 00:08:05,990
But the server is not
necessarily involved in any way

144
00:08:05,990 --> 00:08:08,042
that the users have to trust
in running the protocol.

145
00:08:08,042 --> 00:08:10,465
All right.

146
00:08:10,465 --> 00:08:12,835
And as we're going to see,
each of these steps for

147
00:08:12,835 --> 00:08:16,205
solving these problems introduces
a little bit of engineering complexity.

148
00:08:16,205 --> 00:08:19,297
So this already requires a whole
peer-to-peer protocol for

149
00:08:19,297 --> 00:08:22,540
finding these Coinjoined peers
on top of the Bitcoin protocol.

150
00:08:22,540 --> 00:08:26,694
And we're going to see similar factors
that introduce engineering complexity for

151
00:08:26,694 --> 00:08:28,596
solving each of the other problems.

152
00:08:30,513 --> 00:08:33,612
So the next one,
how do we solve the anonymity problem?

153
00:08:33,612 --> 00:08:38,100
Well, there's a simple strawman solution.

154
00:08:38,100 --> 00:08:40,930
You can frame the anonymity
problem in this way.

155
00:08:40,930 --> 00:08:44,010
You need to communicate the set
of inputs to all the peers and

156
00:08:44,010 --> 00:08:46,480
also you need to communicate
the set of outputs, but

157
00:08:46,480 --> 00:08:48,940
break the linkage between the input and
the output.

158
00:08:48,940 --> 00:08:52,130
Now this becomes a communications
anonymity problem

159
00:08:52,130 --> 00:08:55,080
instead of a Bitcoin anonymity problem.

160
00:08:55,080 --> 00:08:59,480
Because its simply the matter of
communicating these output addresses

161
00:08:59,480 --> 00:09:02,300
that needs to be unlinked from
communication of the input addresses.

162
00:09:03,310 --> 00:09:04,750
So a strawman's solution to that,

163
00:09:04,750 --> 00:09:08,830
since we already have seen Tor
a little bit, is simply this.

164
00:09:08,830 --> 00:09:15,000
These peers come together, they exchange
input addresses, and they disconnect and

165
00:09:15,000 --> 00:09:19,440
then reconnect over Tor after awhile and
then exchange the output addresses.

166
00:09:20,530 --> 00:09:24,440
So this is pretty simple, but
it may not be very robust in practice.

167
00:09:24,440 --> 00:09:28,350
A better solution might be to build
a special purpose anonymous routing

168
00:09:28,350 --> 00:09:32,570
mechanism for these participants
to utilize just for this protocol.

169
00:09:32,570 --> 00:09:35,510
And there are things called decryption
mixed-nets that allow you to do

170
00:09:35,510 --> 00:09:38,330
exactly that, and
such solutions have been proposed.

171
00:09:40,380 --> 00:09:43,150
So let's move to the third problem
which is a denial of service attack.

172
00:09:44,310 --> 00:09:45,190
Let's think about it this way.

173
00:09:45,190 --> 00:09:48,990
What's a traditional solution
to a denial of service attack?

174
00:09:48,990 --> 00:09:53,140
Well, one possible solution to denial
of service is to make it a little bit

175
00:09:53,140 --> 00:09:58,540
expensive for the client to connect
to the server and to receive service.

176
00:09:58,540 --> 00:10:02,250
Well this is not a client-server model,
it's a peer-to-peer model.

177
00:10:02,250 --> 00:10:05,380
But we can still try to
adapt the same principles.

178
00:10:05,380 --> 00:10:09,988
And that's the principle behind the first
two of the proposed solutions for

179
00:10:09,988 --> 00:10:11,219
denial of service.

180
00:10:12,290 --> 00:10:14,970
Either a proof of work,
or a proof of burn.

181
00:10:14,970 --> 00:10:16,260
So what do I mean by this?

182
00:10:16,260 --> 00:10:20,260
Proof of work is simply
repurposing the algorithm behind

183
00:10:20,260 --> 00:10:23,790
Bitcoin's proof of work to
require each of these peer nodes

184
00:10:23,790 --> 00:10:27,576
to do a little bit of computational work
before they can join a Coinjoin protocol.

185
00:10:29,198 --> 00:10:33,030
And the rationale is that if the adversary
is going to disrupt every Coinjoin

186
00:10:33,030 --> 00:10:36,660
that exists out there, they're going
to be burning a lot of computing power,

187
00:10:36,660 --> 00:10:38,100
which will make it very expensive for
them.

188
00:10:39,900 --> 00:10:42,230
Proof of burn is a similar concept.

189
00:10:42,230 --> 00:10:45,270
It's also called fidelity
bonds in Bitcoin.

190
00:10:45,270 --> 00:10:50,200
It allows you to irreversibly
destroy some Bitcoins that you

191
00:10:50,200 --> 00:10:56,150
own by sending it to an unspendable
address, thereby proving that

192
00:10:56,150 --> 00:11:00,060
you've made a little bit of an expensive
signal in order to get into the system.

193
00:11:01,160 --> 00:11:03,540
So that's the rationale between
the first two solutions.

194
00:11:03,540 --> 00:11:04,960
The second two solutions,

195
00:11:04,960 --> 00:11:09,880
next to the third and fourth, also have
a similar rationale, which is to identify

196
00:11:11,640 --> 00:11:15,920
the one or more malicious participants
who launched the denial of service,

197
00:11:15,920 --> 00:11:19,440
to kick them out, and to run the Coinjoin
with the remaining participants.

198
00:11:20,580 --> 00:11:23,730
And that could be done if you trust
the server a little bit to carry it out.

199
00:11:23,730 --> 00:11:26,730
It could also be done in
a purely decentralized manner,

200
00:11:26,730 --> 00:11:29,410
like this paper called
CoinShuffle proposed.

201
00:11:29,410 --> 00:11:33,400
And they came up with a cryptographic
blaming protocol for doing this.

202
00:11:33,400 --> 00:11:35,740
And it involves something
called zero knowledge,

203
00:11:35,740 --> 00:11:38,980
where you learn at least one
of the players who misbehaved

204
00:11:38,980 --> 00:11:43,440
without necessarily learning
much more about what happened.

205
00:11:43,440 --> 00:11:46,430
And then the rest of the peers
can then redo the protocol.

206
00:11:47,640 --> 00:11:50,710
At various points,
I've talked about side channels, so

207
00:11:50,710 --> 00:11:53,200
let's look at an example of that.

208
00:11:53,200 --> 00:11:57,040
And I want to point out that these
side channels can be very tricky.

209
00:11:57,040 --> 00:12:00,040
Not all the mixing in
the world can save you from

210
00:12:00,040 --> 00:12:03,120
what I call high-level flows
that could be identifying.

211
00:12:03,120 --> 00:12:04,860
And here's a neat example of this.

212
00:12:04,860 --> 00:12:08,770
Let's say user Alice receives
a very specific amount of Bitcoins,

213
00:12:08,770 --> 00:12:11,180
let's say on a weekly basis as income.

214
00:12:11,180 --> 00:12:14,230
And has the habit of
always automatically and

215
00:12:14,230 --> 00:12:18,169
immediately transferring let's say
5% of that to her retirement amount.

216
00:12:19,280 --> 00:12:19,840
All right, so

217
00:12:19,840 --> 00:12:23,050
think about the patterns that will
be visible on the block chain here.

218
00:12:23,050 --> 00:12:25,920
No matter what she does
to obscure the link

219
00:12:25,920 --> 00:12:30,220
between the addresses at which
she receives her income and

220
00:12:30,220 --> 00:12:34,980
the address to which she transfers to her
retirement account, the patterns here

221
00:12:34,980 --> 00:12:39,638
are going to be uniquely identifying
because this is a very specific value.

222
00:12:39,638 --> 00:12:43,430
And the 5% of that is also
going to be a specific value.

223
00:12:43,430 --> 00:12:44,970
And there's also a timing pattern.

224
00:12:44,970 --> 00:12:49,790
Every time money appears here, every
time money goes to this address as well.

225
00:12:51,060 --> 00:12:52,420
So this is a problem.

226
00:12:52,420 --> 00:12:54,760
How do we protect ourselves from this?

227
00:12:54,760 --> 00:12:57,860
Well, one suggestion that
has been proposed is,

228
00:12:57,860 --> 00:12:59,800
not only in the context of mixing.

229
00:12:59,800 --> 00:13:03,820
But even in the context of regular
Bitcoin wallets, where users are not even

230
00:13:03,820 --> 00:13:08,350
trying to do any mixing, is by Mike Hearn
and he calls this merge avoidance.

231
00:13:08,350 --> 00:13:11,240
Merge avoidance is as very simple idea.

232
00:13:11,240 --> 00:13:16,370
When users want to do payments,
the proposal is that instead of creating

233
00:13:16,370 --> 00:13:20,260
a giant transaction that combines
as many inputs as necessary

234
00:13:20,260 --> 00:13:25,310
in order to pay the entire payment to
a single address, why not have a protocol

235
00:13:25,310 --> 00:13:30,800
by which the receiver can provide multiple
output addresses, as many as necessary.

236
00:13:30,800 --> 00:13:33,810
And the sender and
receiver can agree upon denominations.

237
00:13:35,080 --> 00:13:38,140
And the sender can avoid
combining different inputs and

238
00:13:38,140 --> 00:13:41,500
can make a variety of
different transactions that

239
00:13:41,500 --> 00:13:44,699
send money from different input
addresses to different output addresses.

240
00:13:46,010 --> 00:13:50,770
So this avoids a lot of the problems
both of high-level flows, because

241
00:13:50,770 --> 00:13:53,970
even these multiple input and output
addresses cannot be linked to each other.

242
00:13:53,970 --> 00:13:57,840
So an adversary might not even be able to
observe the fact that this is a high-level

243
00:13:57,840 --> 00:14:02,470
flow that's happening, but
also avoids problems like

244
00:14:02,470 --> 00:14:06,219
clustering addresses together because
of evidence of shared spending.

245
00:14:08,060 --> 00:14:12,821
And this is a proposal that one could
think about incorporating right now into

246
00:14:12,821 --> 00:14:17,521
Bitcoin-based payment flows in order
to improve anonymity for everyone.