1
00:00:00,000 --> 00:00:03,332
[MUSIC]

2
00:00:03,332 --> 00:00:07,370
So we've talked in the generic manner
about centralization and decentralization.

3
00:00:07,370 --> 00:00:12,240
Let's now talk at a bit more technical
level about Bitcoin and decentralization.

4
00:00:12,240 --> 00:00:15,950
And a key word that's going to come
up again and again here is consensus.

5
00:00:15,950 --> 00:00:18,250
Specifically distributed consensus.

6
00:00:18,250 --> 00:00:19,890
So what am I talking about here?

7
00:00:19,890 --> 00:00:23,580
At a technical level, the key challenge
that you have to solve to build

8
00:00:23,580 --> 00:00:27,640
a distributed e-cash system is
called distributed consensus.

9
00:00:27,640 --> 00:00:30,710
And this is a class of protocols
that's been studied for

10
00:00:30,710 --> 00:00:33,810
decades, in the computer
science literature.

11
00:00:33,810 --> 00:00:38,232
But intuitively, you can think of it as
our goal being to decentralize ScroogeCoin

12
00:00:38,232 --> 00:00:41,913
which is the hypothetical currency
that we saw in the first lecture.

13
00:00:43,270 --> 00:00:46,160
So as I said, there's decades
of research in computer science,

14
00:00:46,160 --> 00:00:50,170
on these consensus protocols, and
the traditional motivating application for

15
00:00:50,170 --> 00:00:53,240
this, is reliability in
distributed systems.

16
00:00:53,240 --> 00:00:54,450
What do I mean by that?

17
00:00:54,450 --> 00:00:58,580
Imagine you're in charge of the back end
for a company like Google, or Facebook.

18
00:00:58,580 --> 00:01:01,970
These companies typically have
thousands or even millions of servers

19
00:01:01,970 --> 00:01:06,060
which form a massive distributive database
that records all of the actions that

20
00:01:06,060 --> 00:01:10,930
happen on the system, like users
comments and likes and posts and so on.

21
00:01:10,930 --> 00:01:14,720
So when a new comment comes in,
the way it'll be recorded,

22
00:01:14,720 --> 00:01:17,710
is that there might be 10 or
15 different nodes

23
00:01:17,710 --> 00:01:21,019
in that massive back end that might
contain copies of this action.

24
00:01:22,110 --> 00:01:26,500
Now what the server needs to make sure is
that that comment either gets recorded in

25
00:01:26,500 --> 00:01:28,490
all copies of that database,
or none of them.

26
00:01:29,660 --> 00:01:33,050
If for some reason, because some
of these nodes might be faulty,

27
00:01:33,050 --> 00:01:35,560
the action gets recorded in none
of the databases, it's okay.

28
00:01:35,560 --> 00:01:38,825
You can go back to the user and say,
"There was a problem saving your post,

29
00:01:38,825 --> 00:01:41,520
would you please try
again?" On the other hand,

30
00:01:41,520 --> 00:01:44,590
if some of the copies of the database
saved it and others didn't,

31
00:01:44,590 --> 00:01:47,770
then you'd be in a lot of trouble because
you'd have an inconsistent database.

32
00:01:47,770 --> 00:01:51,790
So this is the key problem that
motivated the traditional research on

33
00:01:51,790 --> 00:01:55,980
distributed consensus, and you can sort of
see the similarities to Bitcoin here, but

34
00:01:55,980 --> 00:02:00,000
we're going to talk in a bit more detail
about the similarities and differences.

35
00:02:00,000 --> 00:02:03,030
So that was the traditional
motivating application, but

36
00:02:03,030 --> 00:02:08,370
we can also imagine that if we achieved
a distributed consensus protocol and

37
00:02:08,370 --> 00:02:10,700
we were able to use that
to build a massive,

38
00:02:10,700 --> 00:02:15,260
global scale distributed key value
store that maps arbitrary keys or

39
00:02:15,260 --> 00:02:19,690
names to arbitrary values, then that
will enable a lot of applications.

40
00:02:19,690 --> 00:02:23,980
For example, a Distributed Domain Name
System, which is simply a mapping between

41
00:02:23,980 --> 00:02:27,080
human understandable domain
names to IP addresses.

42
00:02:27,080 --> 00:02:31,960
Or a Public Key Directory, which is
a mapping between user email addresses,

43
00:02:31,960 --> 00:02:33,950
let's say, to their public keys.

44
00:02:33,950 --> 00:02:37,950
Or even things like stock trades
because this distributed database

45
00:02:37,950 --> 00:02:41,430
instead of keeping track of
who's paid whom how much money

46
00:02:41,430 --> 00:02:45,120
would keep track of who's transferred
what units of which stock to whom.

47
00:02:46,160 --> 00:02:50,740
And the cool thing about this is that now
that Bitcoin has solved the distributive

48
00:02:50,740 --> 00:02:55,210
consensus problem in a certain sense that
we'll try to understand in this lecture,

49
00:02:55,210 --> 00:02:56,450
we can also go ahead and

50
00:02:56,450 --> 00:02:59,820
try to think about solutions to all
of these other related problems.

51
00:02:59,820 --> 00:03:02,505
And in fact, there are many Altcoins.

52
00:03:02,505 --> 00:03:05,940
In Altcoins, we'll have several
more lectures about Altcoins.

53
00:03:05,940 --> 00:03:10,700
But very briefly, Altcoins are systems
built on Bitcoin like principles

54
00:03:10,700 --> 00:03:12,350
to achieve perhaps
slightly different goals.

55
00:03:12,350 --> 00:03:15,190
Sometimes currency systems,
sometimes not currency systems,

56
00:03:15,190 --> 00:03:16,900
such as one of these applications.

57
00:03:16,900 --> 00:03:21,210
And so, given that we can solve
distributed consensus now, and

58
00:03:21,210 --> 00:03:24,250
given that we can build a global
distributed key value store,

59
00:03:24,250 --> 00:03:26,749
it enables a lot of these
other cool applications.

60
00:03:28,720 --> 00:03:30,880
Let's go to a technical definition now.

61
00:03:30,880 --> 00:03:34,430
The technical definition of distributed
consensus is really quite simple.

62
00:03:34,430 --> 00:03:37,330
Imagine that there is a fixed number,
n, of nodes or

63
00:03:37,330 --> 00:03:41,730
processes, and
each of these nodes has some input value.

64
00:03:41,730 --> 00:03:46,230
And then a consensus protocol happens,
and the two

65
00:03:46,230 --> 00:03:50,560
requirements on this consensus protocol
are that the protocol should terminate and

66
00:03:50,560 --> 00:03:54,640
all correct nodes should decide on
some value, the consensus value.

67
00:03:54,640 --> 00:03:55,150
Right?
And

68
00:03:55,150 --> 00:03:57,908
I said correct nodes because some
of the nodes might be faulty or

69
00:03:57,908 --> 00:04:00,070
even outright malicious.

70
00:04:00,070 --> 00:04:03,390
And the second requirement is that
this value that they agree upon

71
00:04:03,390 --> 00:04:06,230
cannot be an arbitrary value but
it should be

72
00:04:06,230 --> 00:04:10,820
a value that was proposed as input by
at least one of these correct nodes.

73
00:04:10,820 --> 00:04:13,310
So it's really that simple, but

74
00:04:13,310 --> 00:04:16,120
let's try to see what this might
mean in the context of Bitcoin.

75
00:04:17,250 --> 00:04:21,080
So to understand how distributed
consensus could work in Bitcoin,

76
00:04:21,080 --> 00:04:24,870
let's start with a reminder that
Bitcoin is a peer-to-peer system.

77
00:04:24,870 --> 00:04:25,370
Right?

78
00:04:25,370 --> 00:04:28,820
So what I mean when I say that
Bitcoin is a peer-to-peer system.

79
00:04:28,820 --> 00:04:33,690
Is that when Alice wants to pay Bob,
what she does is she's going to broadcast

80
00:04:33,690 --> 00:04:38,800
a transaction to all of the Bitcoin nodes
that comprise the peer-to-peer network.

81
00:04:38,800 --> 00:04:41,390
And you can see here
the structure of the transaction.

82
00:04:41,390 --> 00:04:45,120
This is similar to Goofy coin that
we saw in the first lecture and

83
00:04:45,120 --> 00:04:49,450
what a transaction is going to have is
it's going to have Alice's signature.

84
00:04:49,450 --> 00:04:52,610
Which the other nodes need in order
to know that it really in fact came

85
00:04:52,610 --> 00:04:54,120
from Alice.

86
00:04:54,120 --> 00:04:56,320
It's going to have Bob's public key,

87
00:04:56,320 --> 00:05:00,180
which also acts as his address at
which he wants to receive Bitcoins.

88
00:05:01,440 --> 00:05:03,430
And further, it contains a hash.

89
00:05:03,430 --> 00:05:04,740
What is this hash?

90
00:05:04,740 --> 00:05:08,040
Recall this notion of hash pointers
that we saw in the first lecture.

91
00:05:08,040 --> 00:05:13,070
So this hash, is a way for
Alice to link together this transaction or

92
00:05:13,070 --> 00:05:19,190
this coin to her receipt of this coin
from someone else previously, all right.

93
00:05:19,190 --> 00:05:21,950
So those are the things.that are contained
in this data structure that we

94
00:05:21,950 --> 00:05:22,880
call a transaction,

95
00:05:22,880 --> 00:05:26,630
and she's going to broadcast that to
all of the Bitcoin peer to peer nodes.

96
00:05:28,090 --> 00:05:31,219
And notice something funny here,
Bob's computer is nowhere in this picture.

97
00:05:32,590 --> 00:05:36,630
Now Bob, if he wants to be notified that
this transaction did in fact happen and

98
00:05:36,630 --> 00:05:39,310
that he got paid,
he might want to run a Bitcoin node

99
00:05:39,310 --> 00:05:43,470
that's one of these peer-to-peer nodes
in order to listen in on the network and

100
00:05:43,470 --> 00:05:45,590
be sure that he's received
that transaction.

101
00:05:45,590 --> 00:05:50,000
But his listening is not in fact
necessary for him to receive the funds.

102
00:05:50,000 --> 00:05:53,620
The Bitcoins will be his whether or
not he is running a node on the network.

103
00:05:53,620 --> 00:05:57,640
So given this peer to peer
system what is it exactly

104
00:05:57,640 --> 00:06:00,150
that the nodes might want
to reach consensus on?

105
00:06:00,150 --> 00:06:04,050
Well, given that a variety of users are
broadcasting these transactions through

106
00:06:04,050 --> 00:06:08,490
the network, what everybody wants to reach
consensus on is exactly which transactions

107
00:06:08,490 --> 00:06:13,670
were broadcasted and the order in
which these transactions happened.

108
00:06:13,670 --> 00:06:16,080
So what does that mean specifically?

109
00:06:16,080 --> 00:06:18,770
How consensus could work in Bitcoin,
is that,

110
00:06:18,770 --> 00:06:23,270
at any given time, all the nodes in
the peer-to-peer network would have

111
00:06:23,270 --> 00:06:27,270
a sequence of blocks of transactions
that they've reached consensus on.

112
00:06:27,270 --> 00:06:32,500
So recall that in ScroogeCoin, for
optimization purposes for efficiency, we

113
00:06:32,500 --> 00:06:36,610
put transactions into blocks and we link
these blocks together on a block chain.

114
00:06:36,610 --> 00:06:38,920
So we're utilizing
a similar principal here.

115
00:06:38,920 --> 00:06:41,250
We can do consensus on
transactions one by one.

116
00:06:41,250 --> 00:06:44,020
That would be okay,
it would just be inefficient.

117
00:06:44,020 --> 00:06:47,940
So instead we do consensus
on a block by block basis.

118
00:06:47,940 --> 00:06:51,438
So at any give point all these nodes
in the peer to peer network would have

119
00:06:51,438 --> 00:06:54,860
the sequence of blocks that
they have agreed upon already.

120
00:06:54,860 --> 00:06:58,750
And each node would then have a set
of outstanding transactions that it

121
00:06:58,750 --> 00:07:00,080
has heard about.

122
00:07:00,080 --> 00:07:04,140
So recall that, for these transactions
consensus has not yet happened.

123
00:07:04,140 --> 00:07:08,280
And so almost by definition, each node
might have a slightly different version

124
00:07:08,280 --> 00:07:10,760
of the outstanding transactions
that it's heard about.

125
00:07:10,760 --> 00:07:12,250
The peer to peer network is not perfect,
so

126
00:07:12,250 --> 00:07:14,959
some node may have heard about
a transaction but not other nodes.

127
00:07:15,960 --> 00:07:19,000
So given that we have the setup,
what could happen

128
00:07:19,000 --> 00:07:23,400
is that you have this sequence of
blocks that everybody has agreed upon.

129
00:07:23,400 --> 00:07:26,040
A block is just a series of transactions.

130
00:07:27,470 --> 00:07:30,670
And now there are these,
let's say these three nodes in the system.

131
00:07:30,670 --> 00:07:33,300
Each of whom proposes,
each of whom has an input,

132
00:07:33,300 --> 00:07:35,439
instead of outstanding transactions
that it's heard about.

133
00:07:36,800 --> 00:07:41,560
And they execute together as
some consensus protocol and for

134
00:07:41,560 --> 00:07:45,300
the consensus protocol to succeed,
you can select any valid block,

135
00:07:45,300 --> 00:07:48,220
even if it's a block that was
proposed by only one node.

136
00:07:48,220 --> 00:07:49,670
And for a block to be valid,

137
00:07:49,670 --> 00:07:53,340
all of these transactions have to have
the right cryptosignatures and so on.

138
00:07:55,420 --> 00:07:58,110
So you could select any
of these valid blocks and

139
00:07:58,110 --> 00:08:00,990
the consensus protocol
would still be okay.

140
00:08:00,990 --> 00:08:04,240
If some transaction somehow didn't make
it into this particular block that

141
00:08:04,240 --> 00:08:07,610
gets chosen as the result of a consensus
protocol it could just wait and

142
00:08:07,610 --> 00:08:09,310
get into the next block.

143
00:08:09,310 --> 00:08:12,150
So, maybe this green block
gets selected and now

144
00:08:12,150 --> 00:08:15,989
it gets added to the consensus block chain
and then the protocol proceeds and routes.

145
00:08:17,330 --> 00:08:20,690
So if you took the traditional
theory of distributed consensus and

146
00:08:20,690 --> 00:08:24,930
applied that to Bitcoin, this is the sort
of system that you might end up with.

147
00:08:24,930 --> 00:08:27,910
Now this has some similarities
to how Bitcoin works, but

148
00:08:27,910 --> 00:08:29,970
it's not exactly how Bitcoin works.

149
00:08:29,970 --> 00:08:30,980
And why is that?

150
00:08:30,980 --> 00:08:32,560
And the reason for this is simple.

151
00:08:32,560 --> 00:08:36,160
Doing things this way is a really
hard technical problem for

152
00:08:36,160 --> 00:08:37,490
a variety of reasons.

153
00:08:37,490 --> 00:08:39,530
There are some obvious ones.

154
00:08:39,530 --> 00:08:43,420
Nodes might crash and
nodes might outright be malicious, but

155
00:08:43,420 --> 00:08:45,530
also because the network
is highly imperfect.

156
00:08:45,530 --> 00:08:49,980
It's a peer to peer system, not all pairs
of nodes are connected to each other,

157
00:08:49,980 --> 00:08:52,490
there could be faults in
the network because of

158
00:08:52,490 --> 00:08:54,930
poor internet connectivity and so on.

159
00:08:54,930 --> 00:08:58,602
And finally, there's going to be a lot of
latency in the system because all of these

160
00:08:58,602 --> 00:09:00,173
things happen over the internet.

161
00:09:00,173 --> 00:09:04,468
They're not even within a single
data center or something like that.

162
00:09:04,468 --> 00:09:09,420
And one particular consequence of this
high latency is that there is no notion

163
00:09:09,420 --> 00:09:10,495
of global time.

164
00:09:10,495 --> 00:09:13,111
What does this mean and
why is this important?

165
00:09:13,111 --> 00:09:17,639
It means that not all nodes can agree
to a common ordering of events,

166
00:09:17,639 --> 00:09:20,490
simply based on observing timestamps.

167
00:09:20,490 --> 00:09:22,070
It just doesn't work like that.

168
00:09:22,070 --> 00:09:27,120
So you can't possibly design your protocol
by saying things like take the node that

169
00:09:27,120 --> 00:09:31,060
sent the first message in step one and
have that node do something in step two.

170
00:09:31,060 --> 00:09:34,910
You just can't work like that
because not all nodes will agree

171
00:09:34,910 --> 00:09:38,850
on which message was sent first in
the first half of the protocol.

172
00:09:38,850 --> 00:09:43,210
So this really puts serious constraints on
what sorts of algorithms you can really

173
00:09:43,210 --> 00:09:45,179
put into your consensus protocols.

174
00:09:46,290 --> 00:09:48,610
And in fact, because of these constraints,

175
00:09:48,610 --> 00:09:52,580
a lot of the literature on distributed
consensus is somewhat pessimistic, and

176
00:09:52,580 --> 00:09:55,060
many impossibility
results have been proved.

177
00:09:55,060 --> 00:09:58,400
I'm just going to name a couple of
these in case you want to look them up.

178
00:09:58,400 --> 00:10:00,530
But I won't go into too much detail.

179
00:10:00,530 --> 00:10:02,820
One impossibility result
that's very well known and

180
00:10:02,820 --> 00:10:06,330
pretty simple to understand is called
the Byzantine Generals Problem.

181
00:10:06,330 --> 00:10:10,616
And a much more subtle one, known for the
names of the authors who first proved it,

182
00:10:10,616 --> 00:10:14,310
it's called the Fischer-Lynch-Paterson
Impossibility Result.

183
00:10:14,310 --> 00:10:19,030
Under some conditions which include the
nodes acting in a deterministic manner,

184
00:10:19,030 --> 00:10:21,620
what they proved is that
consensus is impossible,

185
00:10:21,620 --> 00:10:23,890
even with a single faulty process.

186
00:10:23,890 --> 00:10:28,020
So despite these impossibility results
there are a few well known protocols and

187
00:10:28,020 --> 00:10:31,230
Paxos is probably one of the better known.

188
00:10:31,230 --> 00:10:35,060
What Paxos does is it
makes certain compromises.

189
00:10:35,060 --> 00:10:37,810
What it gives you is that it
never produces an inconsistent

190
00:10:37,810 --> 00:10:39,830
result which would be really bad.

191
00:10:39,830 --> 00:10:43,700
But it accepts the trade-off that under
certain conditions, albeit rare ones,

192
00:10:43,700 --> 00:10:46,169
the protocol can get stuck and
fail to make any progress.

193
00:10:47,650 --> 00:10:49,510
But here's the interesting thing.

194
00:10:49,510 --> 00:10:52,330
These impossibility results were,
you know,

195
00:10:52,330 --> 00:10:53,780
they were proved in a different model.

196
00:10:53,780 --> 00:10:57,511
They were intended to study distributed
data bases and this model doesn't carry

197
00:10:57,511 --> 00:11:02,390
over that well to, this is a setting
that Bitcoin operates under so

198
00:11:02,390 --> 00:11:07,894
these results really tell us more about
the model than about the problem, in fact.

199
00:11:07,894 --> 00:11:10,520
What Bitcoin does is that it

200
00:11:10,520 --> 00:11:15,140
violates a lot of the assumptions that go
into these models, and because of that,

201
00:11:15,140 --> 00:11:19,450
consensus in Bitcoin [LAUGH] ironically
works better in practice than in theory.

202
00:11:19,450 --> 00:11:22,741
What this really means is that
the theory that was developed for

203
00:11:22,741 --> 00:11:26,095
a different set of problems needs
to catch up in order to be able to

204
00:11:26,095 --> 00:11:28,850
say really interesting
things about Bitcoin.

205
00:11:28,850 --> 00:11:32,520
But nevertheless, that theory is
quite important because, for example,

206
00:11:32,520 --> 00:11:37,910
it can help us predict unforeseen attacks,
and really be able to come to

207
00:11:37,910 --> 00:11:41,720
strong guarantees on the nature of
consensus and security in Bitcoin.

208
00:11:43,390 --> 00:11:44,840
So what are these different assumptions,

209
00:11:44,840 --> 00:11:47,130
what are some things that
Bitcoin does differently?

210
00:11:47,130 --> 00:11:51,100
Well, first of all,
it introduces the idea of incentives.

211
00:11:51,100 --> 00:11:55,130
And this is very different from any
previous system for distributed consensus.

212
00:11:55,130 --> 00:11:59,340
And this is only possible in Bitcoin
because it is a currency and you can use

213
00:11:59,340 --> 00:12:02,880
that currency to give incentives to
the participants for acting honestly.

214
00:12:04,506 --> 00:12:08,273
And so Bitcoin doesn't quite solve the
distributed consensus problem in a general

215
00:12:08,273 --> 00:12:11,139
sense, but it solves it in
the context of the currency system.

216
00:12:12,140 --> 00:12:13,780
The other thing that it does differently,

217
00:12:13,780 --> 00:12:16,460
is that it really embraces
the notion of randomness.

218
00:12:16,460 --> 00:12:19,840
And what I mean by that is one of
the things it does is, it does away with

219
00:12:19,840 --> 00:12:23,900
the notion of a specific starting
point and ending point for consensus.

220
00:12:23,900 --> 00:12:27,130
Instead, consensus happens
over a long period of time,

221
00:12:27,130 --> 00:12:29,500
about an hour in the practical system.

222
00:12:29,500 --> 00:12:33,750
But even at the end of that time,
you're not 100% sure that a transaction or

223
00:12:33,750 --> 00:12:37,830
a block that your interested in has
made it into the consensus block chain.

224
00:12:37,830 --> 00:12:42,820
Instead, as time goes on your probability
goes up higher and higher and

225
00:12:42,820 --> 00:12:46,770
the probability that you're wrong in
making an assumption about a transaction

226
00:12:46,770 --> 00:12:48,060
goes down exponentially.

227
00:12:49,360 --> 00:12:53,518
So that's the kind of inherently
probabilistic guarantee that Bitcoin gives

228
00:12:53,518 --> 00:12:56,731
you and that's why it's able
to completely get around these

229
00:12:56,731 --> 00:13:00,774
traditional impossibility results
on distributed consensus protocols.