1
00:00:01,590 --> 00:00:05,010
In the past portion of this lecture,
we looked at credit based systems.

2
00:00:05,010 --> 00:00:07,570
Well, we now turn our attention
to cash based systems.

3
00:00:09,070 --> 00:00:13,610
Cash based systems offer two
advantages over credit based systems.

4
00:00:13,610 --> 00:00:16,180
The first is they provide
better anonymity.

5
00:00:16,180 --> 00:00:18,720
When you use a credit card based system,
the bank

6
00:00:18,720 --> 00:00:22,520
always knows what you're doing because
the credit card is issued in your name.

7
00:00:22,520 --> 00:00:24,270
When you pay for something in cash,

8
00:00:24,270 --> 00:00:28,690
nobody necessarily knows who you
are when you purchase something.

9
00:00:28,690 --> 00:00:32,580
The other thing that cash can enable is
offline transactions, where you don't have

10
00:00:32,580 --> 00:00:37,340
to phone home to a third party in
order to get the transaction approved.

11
00:00:37,340 --> 00:00:39,500
You can give someone cash,
and the transaction is done.

12
00:00:39,500 --> 00:00:41,400
And everyone is satisfied.

13
00:00:41,400 --> 00:00:45,190
Maybe later they go to a third party,
like a bank, to deposit the cash.

14
00:00:45,190 --> 00:00:48,530
But that third party doesn't need to
be present in the transaction itself.

15
00:00:50,220 --> 00:00:53,580
Now these two requirements are sort
of a more extreme version of what

16
00:00:53,580 --> 00:00:55,030
Bitcoin offers.

17
00:00:55,030 --> 00:00:59,930
In Bitcoin it doesn't offer
the same anonymity level as cash.

18
00:00:59,930 --> 00:01:02,370
In Bitcoin it offers pseudonymity.

19
00:01:02,370 --> 00:01:05,460
Which means that some of your
transactions could be tied together if

20
00:01:05,460 --> 00:01:09,430
you use the same Bitcoin addresses
to originate transactions.

21
00:01:09,430 --> 00:01:12,570
Bitcoin also doesn't work
in a fully offline way.

22
00:01:12,570 --> 00:01:16,250
It's true, what you could do is you
could create a Bitcoin transaction.

23
00:01:16,250 --> 00:01:16,920
You could sign it.

24
00:01:16,920 --> 00:01:19,820
You could hand it to someone,
maybe email it to them.

25
00:01:19,820 --> 00:01:24,640
But that person won't be content that that
money won't be double spent until they see

26
00:01:24,640 --> 00:01:26,910
that it's incorporated in the block chain.

27
00:01:26,910 --> 00:01:31,310
So unless if you are online and are able
to broadcast that to the peer to peer

28
00:01:31,310 --> 00:01:34,390
network, or alternatively,
you really trust that person you're

29
00:01:34,390 --> 00:01:38,470
receiving the money from, BitCoin operates
in essentially an online fashion.

30
00:01:40,170 --> 00:01:43,310
The earliest ideas of
applying cryptography to

31
00:01:43,310 --> 00:01:45,170
cash came from David Chaum in 1983.

32
00:01:45,170 --> 00:01:48,890
To think about David Chaum's proposal

33
00:01:48,890 --> 00:01:54,150
let's start with a sort of
predecessor to his actual proposal.

34
00:01:54,150 --> 00:01:58,480
So, imagine that I handed you a $100 bill,
and I also handed you a piece of paper.

35
00:01:58,480 --> 00:02:02,080
And the piece of paper was a contract,
and it said that whoever comes back

36
00:02:02,080 --> 00:02:06,260
to you with this piece of paper,
you'll give that $100 bill to them.

37
00:02:06,260 --> 00:02:09,120
Maybe you'll give them $99
to keep a cut for yourself.

38
00:02:09,120 --> 00:02:09,740
In any case,

39
00:02:09,740 --> 00:02:13,940
I want you to sign this paper saying
that you will honor that arrangement.

40
00:02:13,940 --> 00:02:17,340
And then I'll take that paper with me and
I'll give it to someone else.

41
00:02:17,340 --> 00:02:21,415
If I give it to someone else,
then that paper's effectively worth $100.

42
00:02:21,415 --> 00:02:23,375
Now you might be thinking,
what's the big deal?

43
00:02:23,375 --> 00:02:26,385
All you did is convert one small
piece of paper worth $100,

44
00:02:26,385 --> 00:02:30,215
the bill, into a big piece of paper
worth $100 which is the contract.

45
00:02:30,215 --> 00:02:33,795
But of course, this is a physical analogy
of what you can do in a digital realm.

46
00:02:33,795 --> 00:02:36,345
We are able to do digital signatures and
so

47
00:02:36,345 --> 00:02:39,015
this contract could be a digital object.

48
00:02:39,015 --> 00:02:42,435
As long as people trust that
the person who issued the contract

49
00:02:42,435 --> 00:02:45,440
is willing to honor the contract,
then this system works.

50
00:02:45,440 --> 00:02:49,405
And effectively,
this digital contract is worth $100.

51
00:02:51,937 --> 00:02:55,070
Now there is one problem, however.

52
00:02:55,070 --> 00:02:59,190
The problem is once it's a digital
contract, it's very easy to copy and

53
00:02:59,190 --> 00:03:01,830
paste those bits, so
now you have two contracts.

54
00:03:01,830 --> 00:03:06,150
If each contract's worth $100,
you just doubled your money to $200.

55
00:03:06,150 --> 00:03:09,310
If you send those two contracts
to two different people,

56
00:03:09,310 --> 00:03:11,550
this is called the double
spending problem.

57
00:03:11,550 --> 00:03:14,880
And double spending is a problem
that exists in all ecash systems,

58
00:03:14,880 --> 00:03:18,910
all ecash systems have to have some way
of dealing with double spending problem,

59
00:03:18,910 --> 00:03:19,750
including BitCoin.

60
00:03:22,330 --> 00:03:26,740
So the first attempt at fixing the double
spending problem is to encode a unique

61
00:03:26,740 --> 00:03:29,520
serial number in each contract.

62
00:03:29,520 --> 00:03:33,220
This actually isn't sufficient to
completely solve the problem, but

63
00:03:33,220 --> 00:03:35,370
it's a step in the right direction.

64
00:03:35,370 --> 00:03:38,190
Now the problem with the serial
number is that remember

65
00:03:38,190 --> 00:03:41,150
one of the advantages of
cash is that it's anonymous.

66
00:03:41,150 --> 00:03:45,300
But now if you have unique serial numbers
the bank knows who it issued this contract

67
00:03:45,300 --> 00:03:47,150
to, and
they can write down their name, and

68
00:03:47,150 --> 00:03:51,890
they can write down the serial
number that the contract encoded.

69
00:03:51,890 --> 00:03:54,480
And then they can trace this
person as they spend the money.

70
00:03:56,700 --> 00:04:00,340
So David Chaum came up with the digital
equivalent of something called

71
00:04:00,340 --> 00:04:04,230
a blind signature, and
I'll explain it more in paper-based form.

72
00:04:04,230 --> 00:04:09,020
To understand a blind signature, you
could imagine that we take this contract.

73
00:04:09,020 --> 00:04:09,790
But in this case,

74
00:04:09,790 --> 00:04:14,660
instead of it being printed in normal ink,
we print it in invisible ink, okay.

75
00:04:14,660 --> 00:04:18,890
So the bank, we take it to the bank and
we say, will you sign this contract?

76
00:04:18,890 --> 00:04:23,060
And they can't actually read what is
written because it's in invisible ink.

77
00:04:23,060 --> 00:04:24,970
So the ink is providing two properties.

78
00:04:24,970 --> 00:04:27,030
The first is the obvious property,

79
00:04:27,030 --> 00:04:29,990
is that is hides the information
that's in the contract.

80
00:04:29,990 --> 00:04:32,760
But the second property,
which is equally important, is that

81
00:04:32,760 --> 00:04:37,530
whatever I printed on that contract
in invisible ink, I can't change it.

82
00:04:37,530 --> 00:04:38,280
It's locked in.

83
00:04:38,280 --> 00:04:39,300
It's fixed.

84
00:04:39,300 --> 00:04:43,540
And so, if the bank decided to expose it
to see what actually was written there,

85
00:04:43,540 --> 00:04:45,320
then there's no way to change it.

86
00:04:45,320 --> 00:04:47,070
So this is called the binding property.

87
00:04:48,870 --> 00:04:50,420
So this solution, obviously,

88
00:04:50,420 --> 00:04:53,210
solves the problem of the bank
seeing your serial number.

89
00:04:53,210 --> 00:04:54,980
The bank doesn't see your serial number.

90
00:04:54,980 --> 00:04:57,270
However, it creates
an even bigger problem,

91
00:04:57,270 --> 00:04:59,750
which is the bank doesn't see
anything about the contract at all.

92
00:04:59,750 --> 00:05:03,480
It has no idea that it encodes
the fact that it owes someone $100.

93
00:05:03,480 --> 00:05:06,990
The contract might encode that it
owes someone a million dollars.

94
00:05:06,990 --> 00:05:10,980
So the bank wants to be convinced that
this contract is formed correctly,

95
00:05:10,980 --> 00:05:12,480
that the amounts are correct.

96
00:05:12,480 --> 00:05:15,060
But the paradox is,
it can't see the serial number.

97
00:05:16,790 --> 00:05:21,300
Now one solution to this might be that
only the serial number is printed in

98
00:05:21,300 --> 00:05:24,580
invisible ink and the rest of
the contract is printed in regular ink.

99
00:05:25,940 --> 00:05:26,920
So the bank is content.

100
00:05:26,920 --> 00:05:28,860
They can see what the amount is and

101
00:05:28,860 --> 00:05:31,640
the user is content because
they maintain their privacy.

102
00:05:31,640 --> 00:05:34,800
The problem with this is at
a cryptographic level when we transition

103
00:05:34,800 --> 00:05:37,230
into digital signatures we didn't in,

104
00:05:37,230 --> 00:05:40,360
at least in the early eighties
we didn't know how to do this.

105
00:05:40,360 --> 00:05:42,430
Blind signatures back than were all or
nothing.

106
00:05:42,430 --> 00:05:45,780
Either you hid everything that was
being signed or you hid none of it.

107
00:05:45,780 --> 00:05:47,799
And so we needed a different solution.

108
00:05:49,740 --> 00:05:53,810
So the question is how can I convince you
to find something if you can't read it?

109
00:05:53,810 --> 00:05:57,690
And the answer is we can use what's
called the Cut and Choose Protocol.

110
00:05:57,690 --> 00:05:58,940
In this protocol,

111
00:05:58,940 --> 00:06:03,720
what I would do is I would create 100
contracts and hand them to you in a stack.

112
00:06:03,720 --> 00:06:06,970
What you would do is you would pick
one at random from the stack, and

113
00:06:06,970 --> 00:06:08,880
you would reveal the invisible ink.

114
00:06:08,880 --> 00:06:12,080
And when you reveal it, you can check
that at least for that contract,

115
00:06:12,080 --> 00:06:16,170
yes it did encode the fact that you owed
$100 as opposed to a million dollars.

116
00:06:16,170 --> 00:06:18,640
Then you can pick a second
contract out of the pile.

117
00:06:18,640 --> 00:06:20,860
You can reveal it and
make sure it also says $100.

118
00:06:20,860 --> 00:06:23,760
You can keep doing it until
there's one contract left.

119
00:06:24,990 --> 00:06:29,475
When you have this one contract and you're
holding it, even though you don't reveal

120
00:06:29,475 --> 00:06:34,211
the invisible ink, because the other 99
all said $100 and you chose them randomly,

121
00:06:34,211 --> 00:06:38,258
you're pretty sure that this one also
encodes $100, and so you sign it,

122
00:06:38,258 --> 00:06:42,402
convinced to at least to a 99%
probability that it actually says $100.

123
00:06:45,188 --> 00:06:48,120
So how does this help with
the double spending problem?

124
00:06:48,120 --> 00:06:51,670
Well, the cut and choose protocol
allows the bank to sign a contract,

125
00:06:51,670 --> 00:06:54,080
be convinced that it encodes
the right amount, and yet

126
00:06:54,080 --> 00:06:56,580
not be able to see
someone's serial number.

127
00:06:56,580 --> 00:07:00,490
So the idea is that you would get
granted one of these contracts.

128
00:07:00,490 --> 00:07:04,435
When you wanted to do a transaction, you
would give this contract to the merchant

129
00:07:04,435 --> 00:07:06,233
that you're buying the goods from,

130
00:07:06,233 --> 00:07:10,019
and then the merchant would turn around
and get it back to the bank right away.

131
00:07:10,019 --> 00:07:14,361
So in Chaum's earliest system this was an
online transaction system, where you had

132
00:07:14,361 --> 00:07:18,275
to phone home to the bank every time you
received one of these contracts, and

133
00:07:18,275 --> 00:07:20,171
we can stop calling them contracts,

134
00:07:20,171 --> 00:07:24,292
we can call them coins, cause that's
another term for what they actually are.

135
00:07:24,292 --> 00:07:27,719
And so when you spend a coin,
the merchants goes to the bank, and

136
00:07:27,719 --> 00:07:31,988
they give it to the bank, and they ask
the bank, have you seen this coin before?

137
00:07:31,988 --> 00:07:33,787
Has it come in before?

138
00:07:33,787 --> 00:07:35,840
Has this serial number been spent before?

139
00:07:35,840 --> 00:07:40,192
And if the bank says no, it hasn't been
spent before, then they honor the contract

140
00:07:40,192 --> 00:07:44,440
component of the coin and they give
the merchant the money that's owed.

141
00:07:44,440 --> 00:07:46,430
If the merchant goes to the bank and

142
00:07:46,430 --> 00:07:49,759
it has been double spent,
then they can at least detect it.

143
00:07:49,759 --> 00:07:52,680
Now the problem is that
if it is double spent,

144
00:07:53,790 --> 00:07:57,640
you have no idea who the buyer is
because it's an anonymous system.

145
00:07:57,640 --> 00:08:03,702
So that's a drawback that people
worked on later to address.

146
00:08:03,702 --> 00:08:06,819
Another draw back of this system,
is that once you spend a coin,

147
00:08:06,819 --> 00:08:08,380
you can't use it again.

148
00:08:08,380 --> 00:08:11,720
So, it's not like an actual cash
system where you mint coins,

149
00:08:11,720 --> 00:08:13,330
you hand it to the first person.

150
00:08:13,330 --> 00:08:16,670
They send it to a second person,
and then the second person can

151
00:08:16,670 --> 00:08:21,180
give it to a third and a fourth and you
can have a whole chain of transactions.

152
00:08:21,180 --> 00:08:25,070
These type of system, every time you
receive a transaction you have to go back

153
00:08:25,070 --> 00:08:27,420
to the bank and essentially cash it in.

154
00:08:27,420 --> 00:08:30,340
Now the bank might issue a fresh coin,
that's fine.

155
00:08:30,340 --> 00:08:35,260
But the point is that these coins are only
living for one transaction at a time.

156
00:08:35,260 --> 00:08:40,190
Now one proposal of fixing the problem
that the bank has to be online

157
00:08:40,190 --> 00:08:45,222
at all times, came in 1988 from
Chaum along with Fiat and Naor.

158
00:08:47,440 --> 00:08:51,504
What they observed is that if you want
to prevent somebody from double spending

159
00:08:51,504 --> 00:08:54,890
a digital object, it's really hard,
it might be impossible.

160
00:08:54,890 --> 00:09:00,650
There's no way to stop people from
copying and pasting digital strings.

161
00:09:00,650 --> 00:09:04,790
However, they also noted that in
traditional finance we have this idea of

162
00:09:04,790 --> 00:09:08,290
checks and the same problem
arises if i write you a check

163
00:09:08,290 --> 00:09:11,070
you have no guarantee that the money
is actually in my account.

164
00:09:11,070 --> 00:09:13,769
Maybe the money is in my account
I write you a check for $100,

165
00:09:13,769 --> 00:09:15,540
I have $100 in my account but

166
00:09:15,540 --> 00:09:20,050
there is nothing stopping me writing
a second check to someone for $100,.

167
00:09:20,050 --> 00:09:22,650
In which case if both
of you try to cash it,

168
00:09:22,650 --> 00:09:26,590
then one of you won't be able to cash it.

169
00:09:26,590 --> 00:09:30,890
So in order to stop bad
checks from circulating,

170
00:09:30,890 --> 00:09:35,560
what the bank system uses is a detection
system, as opposed to a prevention system.

171
00:09:35,560 --> 00:09:40,170
They don't try and stop you from writing
that second check But what they do is

172
00:09:40,170 --> 00:09:44,600
when you write that second check they
are able to detect that it is exists.

173
00:09:44,600 --> 00:09:48,730
They know who you are because you
have a bank account with the bank and

174
00:09:48,730 --> 00:09:52,100
they'll punish you through a penalty for
doing that.

175
00:09:52,100 --> 00:09:53,640
And so the idea of Chaum, Fiat and

176
00:09:53,640 --> 00:09:57,750
Naor is is there some way to do that
type of system in the digital realm?

177
00:09:59,900 --> 00:10:04,360
So if we go back to idea that coins
encode a unique serial number,

178
00:10:04,360 --> 00:10:07,240
we can think about this
serial number looks like.

179
00:10:07,240 --> 00:10:12,230
If the serial number, if the bank
maintains a mapping between customer

180
00:10:12,230 --> 00:10:15,260
names and serial numbers,
then there's no anonymity in the system.

181
00:10:15,260 --> 00:10:18,760
Every time a coin comes back to the bank
they know who it was that spent it.

182
00:10:18,760 --> 00:10:21,600
And since the coin is coming from
a merchant they know where that user

183
00:10:21,600 --> 00:10:23,250
spent the money.

184
00:10:23,250 --> 00:10:29,040
In the original Chaum 83 scheme, the
serial numbers were just random numbers.

185
00:10:29,040 --> 00:10:31,670
There was no link between
the serial number and the bank.

186
00:10:31,670 --> 00:10:34,510
In fact, the bank couldn't even link
them because of the blind signature had

187
00:10:34,510 --> 00:10:38,110
hid the serial numbers in the coin so the
bank didn't even see the serial numbers.

188
00:10:38,110 --> 00:10:40,420
In this case it offers full anonymity.

189
00:10:40,420 --> 00:10:44,670
Now the question is, is there something in
the middle between having no anonymity and

190
00:10:44,670 --> 00:10:48,600
full anonymity where we can allow
partial traceability of coins

191
00:10:48,600 --> 00:10:50,660
particularly in the case
where they're double spent.

192
00:10:52,760 --> 00:10:54,300
So what Chaum, Fiat, and

193
00:10:54,300 --> 00:10:58,750
Naor came up with is the idea that every
coin would include two serial numbers.

194
00:11:00,030 --> 00:11:03,320
These serial numbers would be arranged so
that when you add them together it

195
00:11:03,320 --> 00:11:06,750
actually forms the identity of
the person who withdrew the cash.

196
00:11:09,430 --> 00:11:17,090
Now this is a more general description of
what this technique is, is secret sharing.

197
00:11:17,090 --> 00:11:19,920
And so in a secret sharing
scheme you have a secret and

198
00:11:19,920 --> 00:11:23,460
you split up into m shares and
you give to n people.

199
00:11:23,460 --> 00:11:29,190
And you do it in such a way that if any m
of the n, where m is some number less than

200
00:11:29,190 --> 00:11:33,370
n, as long as m people come together then
they can reconstruct what the secret is.

201
00:11:33,370 --> 00:11:36,400
So you can think of this as
a 2-out-of-2 secret sharing scheme.

202
00:11:36,400 --> 00:11:41,020
But there's any possibility for n and
m is also possible in the system.

203
00:11:43,380 --> 00:11:46,220
So the idea is you would still
go to the bank as normal.

204
00:11:46,220 --> 00:11:48,780
You would give them a contract,
just like in the previous scheme,

205
00:11:48,780 --> 00:11:51,200
the only difference is that there
would be two serial numbers.

206
00:11:51,200 --> 00:11:52,900
Now the bank would do the cut and choose.

207
00:11:52,900 --> 00:11:55,750
You would them 100 coins and
they would open up 99 of them.

208
00:11:55,750 --> 00:11:57,240
And when they open the 99,

209
00:11:57,240 --> 00:12:01,290
they would check that those two numbers
also add up to your actual identity.

210
00:12:01,290 --> 00:12:03,600
So they're certain that in
the contract they sign,

211
00:12:03,600 --> 00:12:09,140
the coin that they sign, that those two
numbers will also add up to your identity.

212
00:12:09,140 --> 00:12:12,060
So the idea is when I spend a coin,

213
00:12:12,060 --> 00:12:16,510
I give it to the merchant and
these serial numbers are still hidden.

214
00:12:16,510 --> 00:12:19,050
The merchant has no idea what
the two serial numbers are.

215
00:12:19,050 --> 00:12:23,220
But what the merchant can do, they can
ask me to reveal one or the other.

216
00:12:23,220 --> 00:12:25,970
You can think of it as the left serial
number or the right serial number.

217
00:12:25,970 --> 00:12:29,290
So they might flip a coin and
ask me to reveal it.

218
00:12:29,290 --> 00:12:31,810
So what happens if I
just spend the coin once,

219
00:12:31,810 --> 00:12:35,340
which is what we want to encourage,
they only learn half of the secret.

220
00:12:35,340 --> 00:12:39,040
So they're either learning a random number
or a random number minus my identity,

221
00:12:39,040 --> 00:12:40,820
which is also a random number.

222
00:12:40,820 --> 00:12:45,930
That's fully masked, so it doesn't reveal
any information about my identity.

223
00:12:45,930 --> 00:12:50,820
Now if I double spend, if I send that
same coin to a second merchant, there,

224
00:12:50,820 --> 00:12:52,290
one of two things can happen.

225
00:12:52,290 --> 00:12:54,730
The second merchant will also
go through the same protocol,

226
00:12:54,730 --> 00:12:57,850
they'll ask me to either reveal
the left share or the right share.

227
00:12:57,850 --> 00:13:00,640
Assuming the first merchant asks for
the left share, and

228
00:13:00,640 --> 00:13:02,320
if the second merchant also asks for

229
00:13:02,320 --> 00:13:07,030
the left share, then what happens is
my identity still isn't revealed.

230
00:13:07,030 --> 00:13:10,820
Now when both of those merchants cash in
their coins, the bank will detect that

231
00:13:10,820 --> 00:13:16,030
double spending occurred, but they won't
have any idea about who actually did it.

232
00:13:16,030 --> 00:13:19,720
However, 50% of the time,
the second merchant will ask for

233
00:13:19,720 --> 00:13:21,100
a different share than the first.

234
00:13:21,100 --> 00:13:24,600
So if the first asks for the left share,
the second might ask for the right share.

235
00:13:24,600 --> 00:13:26,970
In this case, when they both
cash in their coins at the bank,

236
00:13:26,970 --> 00:13:28,980
the bank sees that it's double spending.

237
00:13:28,980 --> 00:13:32,100
Because they have different shares,
they can add those shares together.

238
00:13:32,100 --> 00:13:35,250
Now they know the identity of the person
who did the double spending, and

239
00:13:35,250 --> 00:13:38,008
they can leverage some fee or
punishment against that person.

240
00:13:38,008 --> 00:13:42,980
Now a 50% chance of catching
double-spending isn't that great, and so

241
00:13:42,980 --> 00:13:44,480
is there any way that we can boost this?

242
00:13:45,850 --> 00:13:47,910
So the idea that Chaum, Fiat, and

243
00:13:47,910 --> 00:13:53,800
Naor had is instead of encoding one pair
of numbers, what if we encode, say, ten?

244
00:13:53,800 --> 00:13:56,010
So for example,
let's assume that they have a table,

245
00:13:56,010 --> 00:14:01,250
and here's my real name, and they assign
a serial number to my name, 31337.

246
00:14:01,250 --> 00:14:06,250
And so here's a list of ten numbers, ten
pairs of numbers and if you do the mental

247
00:14:06,250 --> 00:14:09,930
arithmetic, you'll see that in each
case they add up to this number.

248
00:14:11,560 --> 00:14:15,980
So what happens is when I spend a coin,
these numbers are originally hidden.

249
00:14:15,980 --> 00:14:18,330
And the merchant gets to
go through the list and

250
00:14:18,330 --> 00:14:22,400
they get to pick from each pair, whether
they want to see the left number or

251
00:14:22,400 --> 00:14:26,460
the right pair, but they do this for
all ten instead of just one single pair.

252
00:14:26,460 --> 00:14:30,110
So for example, the merchant might ask for
the left, the left, the right, the left,

253
00:14:30,110 --> 00:14:30,880
and so on.

254
00:14:32,070 --> 00:14:35,210
Now when I go to a second merchant,
we do the same protocol.

255
00:14:35,210 --> 00:14:38,250
They're initially hidden, but
the second merchant gets to also,

256
00:14:38,250 --> 00:14:41,260
for each pair, ask for
either the left or the right.

257
00:14:41,260 --> 00:14:45,560
And what will happen with overwhelming
probability is that at some point

258
00:14:45,560 --> 00:14:49,770
going through these pairs, the two
merchants will ask for different shares.

259
00:14:49,770 --> 00:14:55,180
So for example in the second row, and also
in a lot of other rows in this example,

260
00:14:55,180 --> 00:14:59,590
if they ask for the left share and
the right share, and

261
00:14:59,590 --> 00:15:02,340
in that case you can add
together those two shares and

262
00:15:02,340 --> 00:15:05,580
reveal the identity of
the person who spent the money.

263
00:15:05,580 --> 00:15:08,650
And so this works to boost
the probability from one half

264
00:15:08,650 --> 00:15:10,570
to actually any number that you want.

265
00:15:10,570 --> 00:15:13,510
If you have N pairs,

266
00:15:13,510 --> 00:15:17,430
then the probability of getting
caught is 1 minus 2 to the minus N.

267
00:15:17,430 --> 00:15:21,690
And so it goes up to for
example 99.999% if you use 20 pairs.

268
00:15:24,040 --> 00:15:28,240
Now, this doesn't solve the problem of
being able to spend a coin more than once.

269
00:15:28,240 --> 00:15:32,990
Once you spend your coin, the merchant
still has to go back to the bank, and

270
00:15:32,990 --> 00:15:34,890
they have to cash that coin in.

271
00:15:34,890 --> 00:15:35,870
And you can think about why.

272
00:15:35,870 --> 00:15:39,940
Why can't the merchant accept a
transaction, and then, take that coin and

273
00:15:39,940 --> 00:15:41,360
turn around and spend it?

274
00:15:41,360 --> 00:15:46,340
Well the answer is that that coin encodes
the identity of the original spender.

275
00:15:46,340 --> 00:15:50,890
Okay so if the merchant were able to
re-spend that coin then let's say they

276
00:15:50,890 --> 00:15:54,920
double spent it, then it would be the
original person who was issued the coin,

277
00:15:54,920 --> 00:15:57,490
whose identity is encoded in that coin.

278
00:15:57,490 --> 00:16:01,362
Now you might also think is there some
attack here where, I receive a coin and

279
00:16:01,362 --> 00:16:02,450
than I turn around and

280
00:16:02,450 --> 00:16:05,859
try to double spend it to falsely
blame the person who gave it to me.

281
00:16:05,859 --> 00:16:10,388
But because I don't know what
the other numbers are that are hidden,

282
00:16:10,388 --> 00:16:13,510
I only know the one path
of opening up the pairs,

283
00:16:13,510 --> 00:16:17,670
that's all I can do if I turn around and
try and spend it myself.

284
00:16:17,670 --> 00:16:19,195
I can only open up the same pairs.

285
00:16:21,986 --> 00:16:25,170
Now, there's a couple of ways
we can improve this protocol.

286
00:16:25,170 --> 00:16:27,430
One thing is the efficiency is really bad.

287
00:16:27,430 --> 00:16:31,000
If we think about the idea of
using 20 pairs of serial numbers,

288
00:16:31,000 --> 00:16:33,280
in that case we have 40 serial numbers,
okay?

289
00:16:33,280 --> 00:16:37,720
20 pairs but remember when you go to
the bank initially, you hand them, say,

290
00:16:37,720 --> 00:16:40,710
a 100 coins and
they're going to open at 99.

291
00:16:40,710 --> 00:16:44,010
Now, in that case you have a 1%
chance of deceiving the bank.

292
00:16:44,010 --> 00:16:45,700
And that's probably too high.

293
00:16:45,700 --> 00:16:47,630
You probably want a lot smaller than that.

294
00:16:47,630 --> 00:16:51,560
So you're more likely to go to the bank
with 1,000 coins or 10,000 coins.

295
00:16:51,560 --> 00:16:53,690
And they're going to open all of them but
one.

296
00:16:53,690 --> 00:16:57,220
And so, if you think about serial numbers,
40 serial numbers on each coin,

297
00:16:57,220 --> 00:16:59,040
and then you're handing a thousand coins,

298
00:16:59,040 --> 00:17:01,830
you're handing over 4,000
serial numbers to the bank.

299
00:17:01,830 --> 00:17:07,940
So, this is a large digital object that
you're giving to the bank to audit.

300
00:17:07,940 --> 00:17:12,140
So, what happened over the ensuing years
is that a bunch of cryptographers look at

301
00:17:12,140 --> 00:17:16,790
this problem, and sort of in parallel to
this eCache systems being developed, there

302
00:17:16,790 --> 00:17:20,160
were some advancements in an area called
zero knowledge proofs, which were talked

303
00:17:20,160 --> 00:17:24,520
about in the earlier lecture in this
series when you talked about zero coin.

304
00:17:24,520 --> 00:17:28,020
In this case,
they slowly replaced all these cut and

305
00:17:28,020 --> 00:17:30,530
choose with more compact
zero knowledge proofs.

306
00:17:30,530 --> 00:17:31,220
So it's very easy.

307
00:17:31,220 --> 00:17:34,070
You just go to the bank, you hand them
one contract, and then you prove in zero

308
00:17:34,070 --> 00:17:36,840
knowledge, for example,
that encodes 100 and then you're done.

309
00:17:36,840 --> 00:17:39,710
You don't have to give them 100 coins,
you just give them one and

310
00:17:39,710 --> 00:17:42,470
the proof is very succinct and it's short.

311
00:17:42,470 --> 00:17:48,490
Another area of research was the idea
of adding divisibility to the coins.

312
00:17:48,490 --> 00:17:51,660
So in Chaum's original scheme in Chaum,
Faite, and

313
00:17:51,660 --> 00:17:56,070
Nior, if you got issued a coin that
was worth $100 and you went and

314
00:17:56,070 --> 00:17:59,210
bought, you wanted to buy
something that was say only $75,

315
00:17:59,210 --> 00:18:02,670
there was no way to split
that coin into $75 and $25.

316
00:18:02,670 --> 00:18:05,550
All you could do is go back to
the bank cash in that $100 and

317
00:18:05,550 --> 00:18:09,720
ask for a $75 coin and a $25 coin.

318
00:18:09,720 --> 00:18:13,240
So Okamoto and
Ohta they had some interesting ideas,

319
00:18:13,240 --> 00:18:16,330
it uses Merkel trees
which show up in BitCoin

320
00:18:16,330 --> 00:18:20,930
to create a system that was divisible
where you could actually subdivide

321
00:18:20,930 --> 00:18:24,300
the coin that are issued without
involving the bank in the process.

322
00:18:27,000 --> 00:18:29,570
Now Chaum took his ideas and
he commercialized them.

323
00:18:29,570 --> 00:18:31,330
He formed a company in
1989 called DigiCash.

324
00:18:31,330 --> 00:18:36,650
And this was probably
the earliest company that's

325
00:18:36,650 --> 00:18:41,570
dealt with online transaction or try to
solve the problem of online transaction.

326
00:18:41,570 --> 00:18:43,470
They had a better five year head start.

327
00:18:43,470 --> 00:18:45,240
On other companies like First Virtual and

328
00:18:45,240 --> 00:18:47,980
CyberCash that we talked about
in the earlier lectures.

329
00:18:49,710 --> 00:18:52,410
The actual cash in their
system was called e-cash and

330
00:18:52,410 --> 00:18:54,970
they had another system called cyberbucks.

331
00:18:54,970 --> 00:18:56,960
And there were a couple banks
that actually implemented it.

332
00:18:56,960 --> 00:18:58,210
There were a few in the US.

333
00:18:58,210 --> 00:19:00,400
There was at least one in Finland.

334
00:19:00,400 --> 00:19:00,990
In this case,

335
00:19:00,990 --> 00:19:05,330
in the e-cash systems, because it uses
Chaum's protocols, clients are anonymous.

336
00:19:05,330 --> 00:19:07,620
So, the bank can't trace the money.

337
00:19:07,620 --> 00:19:10,440
When the money comes back, the coin
comes back, it has a serial number, and

338
00:19:10,440 --> 00:19:15,890
the bank doesn't know which user's
serial number that was issued to.

339
00:19:15,890 --> 00:19:17,500
However, the merchants aren't.

340
00:19:17,500 --> 00:19:21,750
The merchants, because they have to return
coins as soon as they receive them,

341
00:19:21,750 --> 00:19:24,550
the bank knows all the information
about the merchants.

342
00:19:24,550 --> 00:19:27,360
How much money's coming in at what time,
etc.

343
00:19:29,645 --> 00:19:33,925
This is what the screenshot
looked like from the software.

344
00:19:33,925 --> 00:19:39,115
And so you can see here, there's a wallet
and it shows you your balance and then

345
00:19:39,115 --> 00:19:43,672
here's all the coins that you have that
have been issued to you from the bank.

346
00:19:43,672 --> 00:19:47,862
And because you can't split coins, because
there's no way to split them up, what

347
00:19:47,862 --> 00:19:51,902
the bank does is they issue you a whole
set of coins in different denominations.

348
00:19:51,902 --> 00:19:55,262
So, for example, you might get eight
pennies, eight two cent coins,

349
00:19:55,262 --> 00:19:57,792
eight four cent coins, etc., etc.

350
00:19:57,792 --> 00:20:02,150
So that you can always sort of reconstruct
the right amount of change to pay for

351
00:20:02,150 --> 00:20:03,930
the exact amount of a transaction.

352
00:20:05,240 --> 00:20:07,990
When you filled out a transaction what
would happen is you would browse to

353
00:20:07,990 --> 00:20:08,600
a website.

354
00:20:08,600 --> 00:20:11,650
So for example,
this is to make a donation to Epic.

355
00:20:11,650 --> 00:20:17,650
And if you wanted to donate the money
you would click the link on the website.

356
00:20:17,650 --> 00:20:21,670
And what it would do is it would open
a server connection back to your computer.

357
00:20:21,670 --> 00:20:25,480
And so your computer had to have
the full ability to be online and

358
00:20:25,480 --> 00:20:28,040
accept incoming server connections.

359
00:20:28,040 --> 00:20:29,600
It had to be running http.

360
00:20:29,600 --> 00:20:32,170
It had to have a port open to receive it.

361
00:20:32,170 --> 00:20:34,060
You had to have a full IP address.

362
00:20:34,060 --> 00:20:36,910
And if it was successful,
the connection was successful,

363
00:20:36,910 --> 00:20:39,703
then your wallet service would
launch on your computer and

364
00:20:39,703 --> 00:20:42,848
then you were able to approve
the transaction and send the money.

365
00:20:44,848 --> 00:20:48,970
Now there were certain variants
to DigiCash that were pursued.

366
00:20:48,970 --> 00:20:53,320
One thing that was sort of
controversial about DigiCash,

367
00:20:53,320 --> 00:20:55,430
is that the technology was patented,

368
00:20:55,430 --> 00:21:00,650
in specifically the blind signature scheme
that was used, had a patent filed on it.

369
00:21:00,650 --> 00:21:03,860
And so that stopped other
people from developing e-cash

370
00:21:03,860 --> 00:21:06,090
systems that use the same protocol.

371
00:21:06,090 --> 00:21:09,370
There were a bunch of cryptographers
that hung out on a mailing list called

372
00:21:09,370 --> 00:21:10,820
the cypherpunks mailing list.

373
00:21:10,820 --> 00:21:13,470
This later transitioned into
the cryptography mailing list.

374
00:21:13,470 --> 00:21:16,680
And you'll know the cryptography mailing
list as the place where [FOREIGN]

375
00:21:16,680 --> 00:21:19,800
originally posted the White Paper and
introduced BitCoin.

376
00:21:19,800 --> 00:21:23,470
So, but before it made that transition,
the cypherpunks,

377
00:21:23,470 --> 00:21:28,470
they implemented a version of e-cash,
of David's e-cash,

378
00:21:28,470 --> 00:21:33,920
that was called MagicMoney, and
MagicMoney was only for experimental use,

379
00:21:33,920 --> 00:21:37,290
so it did violate the patents, but because
it was non-commercial, you could use it to

380
00:21:37,290 --> 00:21:40,810
experiment with, and it was sort of
a fun piece of software to play with.

381
00:21:40,810 --> 00:21:42,960
The interface was all text space.

382
00:21:42,960 --> 00:21:47,040
You could send transactions by email.

383
00:21:47,040 --> 00:21:50,100
You would just copy and
paste literally into email.

384
00:21:50,100 --> 00:21:54,510
Hopefully, you'd use a PGP key to
protect the transaction in transit, and

385
00:21:54,510 --> 00:21:56,740
you could email it to another user.

386
00:21:56,740 --> 00:21:59,940
The other user would import it
into a file on their computer,

387
00:21:59,940 --> 00:22:03,960
which was called allcoins.dat,
which sounds a little bit like wallet.dat,

388
00:22:03,960 --> 00:22:06,509
which is what Bitcoin
uses to store its coins.

389
00:22:07,680 --> 00:22:12,230
Another proposal by Ben Laurie with
contributions from lots of other people is

390
00:22:12,230 --> 00:22:13,220
called Lucre and

391
00:22:13,220 --> 00:22:16,060
in this scheme what they did is they
targeted the blind signature scheme.

392
00:22:16,060 --> 00:22:19,190
And they tried to come up with an
alternative which wouldn't be covered by

393
00:22:19,190 --> 00:22:22,610
the patent, and then you can keep
the rest of the system largely the same.

394
00:22:23,660 --> 00:22:28,420
Another problem that's interesting
that arises when you use DigiCash is,

395
00:22:28,420 --> 00:22:30,860
as we mentioned, you can't make change.

396
00:22:30,860 --> 00:22:33,390
And so, if you need to make change,
you have to go back to the bank,

397
00:22:33,390 --> 00:22:36,960
and you have to get the bank to
reissue the right set of coins, so

398
00:22:36,960 --> 00:22:39,680
that you can make exact change for
something.

399
00:22:39,680 --> 00:22:44,920
Ian Goldberg had the idea that maybe
the merchant could send you coins back,

400
00:22:44,920 --> 00:22:49,740
if they had some coins so
that you might overpay for the item, but

401
00:22:49,740 --> 00:22:51,330
then you would get some coins back.

402
00:22:51,330 --> 00:22:53,758
However, this introduces
a problem with anonymity.

403
00:22:53,758 --> 00:22:57,520
Remember, in e-cash,
the senders are anonymous.

404
00:22:57,520 --> 00:22:59,170
However, the merchants aren't.

405
00:22:59,170 --> 00:23:02,850
And when the merchant sends cash back,
technically, they're the sender, so

406
00:23:02,850 --> 00:23:04,070
they're anonymous.

407
00:23:04,070 --> 00:23:07,050
And you, as the person who has
to turn this cash into the bank,

408
00:23:07,050 --> 00:23:08,370
are not anonymous.

409
00:23:08,370 --> 00:23:11,890
And so there's no way to do that system
without breaking the anonymity of

410
00:23:11,890 --> 00:23:13,080
the original.

411
00:23:13,080 --> 00:23:17,370
User trying to buy the goods and so he
had a different proposal where there were

412
00:23:17,370 --> 00:23:20,880
different types of coins to allow
these types of transactions to occur,

413
00:23:20,880 --> 00:23:24,580
allow you to get the change back and
preserve the anonymity of the user.

414
00:23:27,170 --> 00:23:28,370
Now why did DigiCash fail?

415
00:23:29,710 --> 00:23:34,300
The main problem with DigiCash is,
it was hard to persuade the banks and

416
00:23:34,300 --> 00:23:36,070
the merchants to adopt it.

417
00:23:36,070 --> 00:23:40,350
People didn't want to use it, and because
no merchants, or not a lot of merchants

418
00:23:40,350 --> 00:23:44,610
were using it to accept money,
then users didn't want to use it either.

419
00:23:44,610 --> 00:23:48,160
It also didn't support
user to user transactions.

420
00:23:48,160 --> 00:23:50,110
At least,
it didn't support them very well.

421
00:23:50,110 --> 00:23:54,176
It was really centered on the user
to merchant transaction, and so

422
00:23:54,176 --> 00:23:57,225
if merchants weren't on
board with this system,

423
00:23:57,225 --> 00:24:01,231
then there was no way to really
bootstrap interest in the system.

424
00:24:01,231 --> 00:24:05,309
As a side note, BitCoin, because it
allows both user-to-merchant and

425
00:24:05,309 --> 00:24:09,391
user-to-user transaction,
BitCoin probably part of it's success,

426
00:24:09,391 --> 00:24:14,210
could be attributed to the fact that
it supported user-to-user transactions.

427
00:24:14,210 --> 00:24:15,940
So there was something to
do do with your BitCoin.

428
00:24:15,940 --> 00:24:21,270
At least send it to other users, while
the community tried to drum up support for

429
00:24:21,270 --> 00:24:23,040
BitCoin and get merchants to accept it.

430
00:24:24,870 --> 00:24:27,990
So, at the end of the day, DigiCash lost,
and the credit card companies won.

431
00:24:29,030 --> 00:24:30,830
In the later years of the company,

432
00:24:30,830 --> 00:24:36,440
DigiCash also experimented with
tamper-resistant hardware.

433
00:24:36,440 --> 00:24:38,200
In this case, they had devices.

434
00:24:38,200 --> 00:24:41,370
They might be a small device that
was usually called a wallet, or

435
00:24:41,370 --> 00:24:43,890
it might be some sort of card and

436
00:24:43,890 --> 00:24:46,740
what they were trying to solve
is this double-spending problem.

437
00:24:46,740 --> 00:24:49,865
And in this case they weren't trying
to just merely detect the existence of

438
00:24:49,865 --> 00:24:50,440
double-spending.

439
00:24:50,440 --> 00:24:52,930
They were trying to actually prevent it.

440
00:24:52,930 --> 00:24:56,240
So in this hardware, there might be
a counter that encodes your balance, and

441
00:24:56,240 --> 00:24:58,850
every time you spend money,
the counter decreases.

442
00:24:58,850 --> 00:25:02,170
If you load the card with more money,
then the counter goes up.

443
00:25:02,170 --> 00:25:06,480
But the point is there is no way to
physically or digitally go in and

444
00:25:06,480 --> 00:25:07,720
tamper with that counter.

445
00:25:07,720 --> 00:25:11,960
So if that counter goes to zero, then that
card stops being able to spend money.

446
00:25:13,190 --> 00:25:17,920
Now there were a bunch of companies that
looked at this tamper-resistant hardware,

447
00:25:17,920 --> 00:25:19,670
in addition to DigiCash.

448
00:25:19,670 --> 00:25:25,020
DigiCash worked later with a company
called Cafe which was based in Europe.

449
00:25:25,020 --> 00:25:28,300
There was also another company formed
called Mondex that was later acquired

450
00:25:28,300 --> 00:25:29,560
by MasterCard.

451
00:25:29,560 --> 00:25:31,960
And Visa had their own
variant called VisaCash.

452
00:25:32,970 --> 00:25:34,800
So this is the Mondex system.

453
00:25:34,800 --> 00:25:37,280
Mondex consisted of a card.

454
00:25:37,280 --> 00:25:41,510
This is a smart card with a chip and
there were also these wallet units and

455
00:25:41,510 --> 00:25:43,350
you could load either of them with cash.

456
00:25:43,350 --> 00:25:46,950
So you can get the cards and they would
have some amount of cash on them and

457
00:25:46,950 --> 00:25:49,460
you can have wallets that
would also have cash on them.

458
00:25:49,460 --> 00:25:53,080
And if you wanted to do
user-to-user swap of money,

459
00:25:53,080 --> 00:25:56,450
what would happen is the first user
would put their card into the wallet,

460
00:25:56,450 --> 00:25:59,780
you could move money off of
the card onto the wallet.

461
00:25:59,780 --> 00:26:02,080
Then you'd stick the second
card in the wallet and

462
00:26:02,080 --> 00:26:05,120
you'd move the money off the wallet
onto the second card and so

463
00:26:05,120 --> 00:26:09,380
you could exchange cash in the way,
and it was anonymous.

464
00:26:10,850 --> 00:26:15,440
Now, Mondex actually trialed their
technology in a bunch of communities.

465
00:26:15,440 --> 00:26:19,860
One community is actually a city very
close to where I grew up, in Guelph,

466
00:26:19,860 --> 00:26:21,000
Ontario.

467
00:26:21,000 --> 00:26:25,150
And, needless to say, because it
doesn't exist today, this technology,

468
00:26:25,150 --> 00:26:28,690
you know what the end of the story is,
which is that it didn't really catch on.

469
00:26:28,690 --> 00:26:32,900
And the main problem with it is that
cards, Mondex cards, they're like cash.

470
00:26:32,900 --> 00:26:35,760
If you lose them or
they get stolen, the money's gone.

471
00:26:35,760 --> 00:26:38,500
And if there was some sort of
malfunction with the card,

472
00:26:38,500 --> 00:26:40,120
if the card reader wouldn't read it,

473
00:26:40,120 --> 00:26:44,340
there's no way to determine whether
that card had balance on it or not.

474
00:26:44,340 --> 00:26:45,030
And so Mondex,

475
00:26:45,030 --> 00:26:47,990
typically what they would do in these
scenarios is they would incur the cost.

476
00:26:47,990 --> 00:26:51,050
They would assume that
the card was loaded and

477
00:26:51,050 --> 00:26:55,250
then they would remunerate the user for
that lost money.

478
00:26:55,250 --> 00:26:57,530
But that cost the company a lot of money.

479
00:26:57,530 --> 00:27:01,660
The wallet itself was also sort
of a larger foreign factor.

480
00:27:01,660 --> 00:27:03,070
It was slow.

481
00:27:03,070 --> 00:27:07,560
In order to process, it was much faster
to pay with credit card or with cash.

482
00:27:07,560 --> 00:27:10,340
And retailers hated having
a bunch of these terminals.

483
00:27:10,340 --> 00:27:13,480
They just wanted to have one terminal for
your VISA card.

484
00:27:13,480 --> 00:27:15,530
And they didn't want to have
two different terminals.

485
00:27:16,650 --> 00:27:21,060
So for all of these reasons,
the Mondex experiment was not successful.

486
00:27:21,060 --> 00:27:24,430
However, what was successful is
if you remember these cards,

487
00:27:24,430 --> 00:27:26,150
we have these small chips on them.

488
00:27:26,150 --> 00:27:28,230
So this is a smart card technology.

489
00:27:28,230 --> 00:27:31,510
Today in a lot of countries,
including Canada where I live,

490
00:27:31,510 --> 00:27:35,710
every single credit card and every single
debit card now has this technology on it.

491
00:27:35,710 --> 00:27:38,370
They all are based on smart cards.

492
00:27:38,370 --> 00:27:39,760
It's used for a different purpose.

493
00:27:39,760 --> 00:27:42,080
It's not used to prevent double-spending.

494
00:27:42,080 --> 00:27:43,450
It's used for authentication,

495
00:27:43,450 --> 00:27:47,410
so you prove that you know the pin
that's associated with your account.

496
00:27:47,410 --> 00:27:52,018
But this technology was adopted and
Mondex was using it long before

497
00:27:52,018 --> 00:27:56,968
the wider banking industry made it
a standard for bank-issued cards.