1
00:00:00,910 --> 00:00:04,960
Okay so like we said each transaction
output doesn't just specify a simple

2
00:00:04,960 --> 00:00:08,080
public key,
it actually specifies a script.

3
00:00:08,080 --> 00:00:11,170
So what do I mean by that, what is
a script and why do we use scripts?

4
00:00:11,170 --> 00:00:15,550
In this section we're going to talk about
what the Bitcoin scripting language, and

5
00:00:15,550 --> 00:00:19,230
why script is used instead of
simply assigning a public key.

6
00:00:20,830 --> 00:00:24,350
Okay, so to understand scripts,
I think the easiest way is by an example.

7
00:00:24,350 --> 00:00:28,630
And we'll take, as an example,
the most common script in Bitcoin,

8
00:00:28,630 --> 00:00:34,010
which is to redeem a previous transaction
by signing with the correct public key.

9
00:00:35,180 --> 00:00:38,940
So this is what the output address
would look like in that case.

10
00:00:38,940 --> 00:00:41,170
The output address is really a script.

11
00:00:41,170 --> 00:00:44,760
In this case the script is
going to have four instructions.

12
00:00:44,760 --> 00:00:46,180
So what happens to this script?

13
00:00:46,180 --> 00:00:47,330
Who runs it?

14
00:00:47,330 --> 00:00:51,640
How does this script indicate who has
the ability to spend these coins?

15
00:00:51,640 --> 00:00:55,480
The secret is that the input
address is also a script.

16
00:00:55,480 --> 00:00:59,450
So that's a bit of script that you
combine with the output address,.

17
00:00:59,450 --> 00:01:00,920
You simply concatenate them.

18
00:01:02,080 --> 00:01:06,470
And that gets you one script that has
to run successfully in order to claim

19
00:01:06,470 --> 00:01:07,130
a Bitcoin.

20
00:01:08,230 --> 00:01:12,880
So traditionally these two scripts
are called scriptSig and scriptPubKey.

21
00:01:12,880 --> 00:01:17,630
And that's because, in the simplest case,
the output script just specifies a public

22
00:01:17,630 --> 00:01:22,050
key, and the input script specifies
a signature with that public key.

23
00:01:24,580 --> 00:01:29,280
When a transaction is being validated,
the two scripts get pasted together.

24
00:01:29,280 --> 00:01:30,230
They get run.

25
00:01:30,230 --> 00:01:33,950
And if the concatenated script
can run without any errors,

26
00:01:33,950 --> 00:01:35,770
this is considered a valid transaction.

27
00:01:37,940 --> 00:01:39,890
So where did this scripting
language come from?

28
00:01:41,310 --> 00:01:43,740
It doesn't really have a proper name.

29
00:01:43,740 --> 00:01:46,760
It's just called Script or
the Bitcoin scripting language.

30
00:01:46,760 --> 00:01:49,810
And it was built specifically for Bitcoin.

31
00:01:49,810 --> 00:01:53,610
It was probably most inspired
by a language called Forth,

32
00:01:53,610 --> 00:01:58,250
which is an old stack-based
simple programming language.

33
00:01:58,250 --> 00:02:01,780
But you don't need to understand Forth
to understand Bitcoin scripting.

34
00:02:03,150 --> 00:02:06,650
The key design properties here were to
have something that was quite simple,

35
00:02:06,650 --> 00:02:11,030
quite compact, but yet had support for
pretty sophisticated cryptography.

36
00:02:11,030 --> 00:02:14,650
So there are special purpose instructions
to compute hash functions and

37
00:02:14,650 --> 00:02:17,510
to compute signatures and
verify signatures.

38
00:02:18,910 --> 00:02:21,480
And this is a stack-based language.

39
00:02:21,480 --> 00:02:24,460
And you may have never seen a stack-based
language before in your life, but

40
00:02:24,460 --> 00:02:28,540
I'll explain on the next slide what
that means and why that was chosen.

41
00:02:28,540 --> 00:02:31,520
So there are a lot of limits here
that are important to keep in mind.

42
00:02:31,520 --> 00:02:35,190
In particular there are no loops
in the Bitcoin scripting language.

43
00:02:35,190 --> 00:02:39,030
Every instruction is executed
exactly once, in a linear manner.

44
00:02:39,030 --> 00:02:42,510
So if you look at a script just based on
the number of instructions in the script

45
00:02:42,510 --> 00:02:46,870
you know exactly how long it might take
to run and how much memory it could use.

46
00:02:48,850 --> 00:02:50,990
So this is not a Turing-complete language.

47
00:02:52,370 --> 00:02:56,060
It doesn't have the ability to compute
arbitrarily powerful functions.

48
00:02:56,060 --> 00:02:59,140
And this is by design because
the miners have to run these scripts,

49
00:02:59,140 --> 00:03:02,360
which are submitted by arbitrary
participants in the network.

50
00:03:02,360 --> 00:03:05,180
So you don't want to give them the power
to submit a script that might have

51
00:03:05,180 --> 00:03:07,490
an infinite loop or might run forever.

52
00:03:09,180 --> 00:03:11,080
And since it's not
a Turing-complete language,

53
00:03:11,080 --> 00:03:12,960
we don't have the halting problem.

54
00:03:12,960 --> 00:03:15,180
You can look at any Bitcoin script and

55
00:03:15,180 --> 00:03:19,350
be sure that it's going to terminate
within a finite number of steps,

56
00:03:19,350 --> 00:03:22,720
which is just the number of
instructions that are in that script.

57
00:03:22,720 --> 00:03:24,060
Okay, now the fun part.

58
00:03:24,060 --> 00:03:28,000
We're going to look at a specific Bitcoin
script and exactly how it's executed.

59
00:03:29,240 --> 00:03:30,880
This is the same example as before.

60
00:03:30,880 --> 00:03:33,130
This is the most common script in Bitcoin,

61
00:03:34,430 --> 00:03:40,470
a script where the sender of a coin simply
specifies the public key of the recipient.

62
00:03:40,470 --> 00:03:41,920
And the recipient of the coins,

63
00:03:41,920 --> 00:03:46,900
to redeem them, has to specify a signature
using that specified public key.

64
00:03:49,270 --> 00:03:54,550
So the first two instructions in this
script are simply data instructions,

65
00:03:54,550 --> 00:03:55,240
like I said.

66
00:03:55,240 --> 00:03:59,900
And these are the signature and the public
key used to generate that signature.

67
00:03:59,900 --> 00:04:04,710
And these were specified by the recipient
in that scriptSig component,

68
00:04:04,710 --> 00:04:05,860
or the input script.

69
00:04:07,780 --> 00:04:12,260
So executing data instructions is
easy in a stack-based language.

70
00:04:12,260 --> 00:04:14,699
If you see data,
you just push it onto the stack.

71
00:04:16,750 --> 00:04:20,527
And that's the only interaction with
memory that you have in stack-based

72
00:04:20,527 --> 00:04:22,130
programming language.

73
00:04:22,130 --> 00:04:23,080
There's no variables.

74
00:04:23,080 --> 00:04:24,190
There's only a stack.

75
00:04:24,190 --> 00:04:27,890
So the only thing you can do to write data
to memory is to push it onto the stack.

76
00:04:30,770 --> 00:04:33,950
So after we've pushed those
two values onto the stack,

77
00:04:35,380 --> 00:04:37,880
we're going to start executing
the second half of the script,

78
00:04:37,880 --> 00:04:40,940
which was specified by
the sender of the coins.

79
00:04:40,940 --> 00:04:43,650
So this is the script pubKey
component of the script.

80
00:04:45,330 --> 00:04:46,230
And now, we're going to start to

81
00:04:46,230 --> 00:04:48,390
actually manipulate some of
those values on the stack.

82
00:04:50,220 --> 00:04:55,780
So this duplicate instruction,
OP_DUP says simply take the value that's

83
00:04:55,780 --> 00:05:00,660
on the top of the stack, pop it off, and
then write two copies back to the stack.

84
00:05:01,970 --> 00:05:05,269
So we're just going to
duplicate that public key.

85
00:05:05,269 --> 00:05:10,111
The next instruction,
HASH160, says take the top

86
00:05:10,111 --> 00:05:15,277
value on the stack and
compute a cryptographic hash of it.

87
00:05:15,277 --> 00:05:20,103
So this top value is going to
be converted from the public

88
00:05:20,103 --> 00:05:23,114
key into a hash of the public key.

89
00:05:23,114 --> 00:05:26,573
Now we're going to do one more
push of data onto the stack.

90
00:05:26,573 --> 00:05:30,103
And this data, remember,
was specified by the sender of the coins.

91
00:05:30,103 --> 00:05:33,660
So this is the public key that
the sender specified had to be used to

92
00:05:33,660 --> 00:05:36,259
generate the signature
to redeem these coins.

93
00:05:38,420 --> 00:05:40,870
So now at the top of
the stack we have two values.

94
00:05:40,870 --> 00:05:44,204
We have the hash of the public key
as specified by the sender and

95
00:05:44,204 --> 00:05:48,310
the hash of the public key that was
actually used by the recipient when trying

96
00:05:48,310 --> 00:05:49,421
to claim the coins.

97
00:05:52,775 --> 00:05:56,283
And we'll just run this EQUALVERIFY
command, which just says,

98
00:05:56,283 --> 00:05:58,850
are the two values at
the top of the stack equal?

99
00:06:00,040 --> 00:06:01,810
If they aren't,
an error is going to be thrown, and

100
00:06:01,810 --> 00:06:03,960
the script will stop executing.

101
00:06:03,960 --> 00:06:05,110
But we'll assume that they are.

102
00:06:05,110 --> 00:06:09,600
We'll assume that recipient of the coins
actually did use the correct public key.

103
00:06:11,200 --> 00:06:14,970
That instruction will consume those
two data items that are at the top of

104
00:06:14,970 --> 00:06:15,500
the stack.

105
00:06:15,500 --> 00:06:20,891
So now we're left with two data items on
the stack, a signature and a public key.

106
00:06:20,891 --> 00:06:24,343
And we've already checked that the public
key was the right public key that was

107
00:06:24,343 --> 00:06:26,128
specified by the sender of these coins.

108
00:06:26,128 --> 00:06:30,080
And now we want to check that
the signature is actually valid.

109
00:06:30,080 --> 00:06:33,980
So, this is where the power of the Bitcoin
scripting language really comes into play.

110
00:06:33,980 --> 00:06:37,850
There's one instruction here that
let's you verify a signature.

111
00:06:37,850 --> 00:06:41,690
So it's easy to write scripts
that do signature verification

112
00:06:41,690 --> 00:06:44,940
without calling any special
library to check the signatures.

113
00:06:44,940 --> 00:06:47,300
That's all built in to
the Bitcoin scripting language.

114
00:06:49,530 --> 00:06:52,580
Now one thing I haven't told you is
what is this actually a signature of.

115
00:06:52,580 --> 00:06:54,510
What was the input to
the signature function?

116
00:06:55,770 --> 00:06:58,640
And it turns out there's only
one thing you sign in Bitcoin,

117
00:06:58,640 --> 00:07:00,860
which is an entire transaction.

118
00:07:00,860 --> 00:07:05,610
So this CHECKSIG instruction is going
to verify that the entire transaction

119
00:07:05,610 --> 00:07:06,900
was successfully signed.

120
00:07:08,580 --> 00:07:13,208
So in just one go hopefully the CHECKSIG
instruction will pop those remaining two

121
00:07:13,208 --> 00:07:16,624
items off of the stack,
check that the signature is valid.

122
00:07:16,624 --> 00:07:19,573
And now we've executed every
instruction in the script.

123
00:07:19,573 --> 00:07:21,593
There's nothing left on the stack.

124
00:07:21,593 --> 00:07:24,410
And if we hadn't had any errors,

125
00:07:24,410 --> 00:07:28,350
the output of this script
will be a simple yes.

126
00:07:28,350 --> 00:07:31,170
So every Bitcoin script can
only produce two outcomes.

127
00:07:31,170 --> 00:07:34,520
It can either execute
successfully with no errors,

128
00:07:34,520 --> 00:07:37,520
in which case the transaction is valid.

129
00:07:37,520 --> 00:07:40,630
If there's any error while
the script is executing, the whole

130
00:07:40,630 --> 00:07:44,100
transaction will be invalid and shouldn't
be accepted into the block chain.

131
00:07:47,260 --> 00:07:49,540
So, a little bit more about
the Bitcoin scripting language.

132
00:07:50,830 --> 00:07:51,970
It's very small.

133
00:07:51,970 --> 00:07:57,170
There's only room for 256 instructions
because each one is given one byte.

134
00:07:57,170 --> 00:08:02,630
And of those, 15 of them are currently
disabled, so you can't use them at all.

135
00:08:02,630 --> 00:08:08,050
And 75 of them are reserved, so haven't
been assigned any specific meaning yet but

136
00:08:08,050 --> 00:08:11,030
might be instructions that
are added later in time.

137
00:08:11,030 --> 00:08:14,740
So there's a lot of the basic instructions
that you would expect in any programming

138
00:08:14,740 --> 00:08:16,150
language are going to be there.

139
00:08:16,150 --> 00:08:19,880
There's basic arithmetic,
basic logic like if and

140
00:08:19,880 --> 00:08:24,440
then, throwing errors,
not throwing errors, returning early.

141
00:08:24,440 --> 00:08:27,190
And finally there are crypto instructions,
like I said.

142
00:08:27,190 --> 00:08:30,890
So there are hash functions,
instructions for signature verification.

143
00:08:30,890 --> 00:08:34,374
And there's a special very
important instruction for

144
00:08:34,374 --> 00:08:36,655
multi-signature verification.

145
00:08:36,655 --> 00:08:39,905
That's called, CHECKMULTISIG.

146
00:08:39,905 --> 00:08:40,413
So this,

147
00:08:40,413 --> 00:08:44,729
even more powerful than checking just
a single signature with one instruction,

148
00:08:44,729 --> 00:08:48,860
Bitcoin actually lets you check multiple
signatures with one instruction.

149
00:08:48,860 --> 00:08:53,172
So with MULTISIG,
you specify end public keys, and

150
00:08:53,172 --> 00:08:56,998
you specify a parameter,
t, or a threshold.

151
00:08:56,998 --> 00:09:01,049
And for this instruction to execute
validly, there have to be at

152
00:09:01,049 --> 00:09:05,260
least t signatures, t out of n of
those public keys that are valid.

153
00:09:07,040 --> 00:09:10,630
So we'll show some examples of what
you'd use MULTISIG for in a second, but

154
00:09:10,630 --> 00:09:14,250
this is quite a powerful primitive that,

155
00:09:14,250 --> 00:09:18,880
in a compact way in the Bitcoin scripting
language, you can express the concept that

156
00:09:18,880 --> 00:09:23,480
t out of n of these public keys must sign
in order for this transaction to be valid.

157
00:09:24,630 --> 00:09:26,230
So there's an important bug here.

158
00:09:26,230 --> 00:09:30,890
There's a gotcha, which has been
there since the beginning of time,

159
00:09:30,890 --> 00:09:34,900
which is that in the original
implementation of this, the CHECKMULTISIG

160
00:09:34,900 --> 00:09:40,010
instruction actually pops an extra data
value off the stack and ignores it.

161
00:09:40,010 --> 00:09:42,030
So this is just a quirk
of the Bitcoin language.

162
00:09:42,030 --> 00:09:44,960
It's something that in programming
you have to deal with by

163
00:09:44,960 --> 00:09:48,050
putting an extra dummy
variable onto the stack.

164
00:09:48,050 --> 00:09:51,570
And at this point it's considered
a feature in Bitcoin in that

165
00:09:51,570 --> 00:09:52,720
it's not going away.

166
00:09:52,720 --> 00:09:56,410
The costs of removing it are much
higher than the damage it causes, so

167
00:09:56,410 --> 00:10:00,430
this is just a fun bug that everybody in
the Bitcoin community gets to live with.

168
00:10:02,710 --> 00:10:07,290
So like I've said, we have this whole
scripting language that lets us specify,

169
00:10:07,290 --> 00:10:11,990
in some sense, arbitrary conditions that
must be met in order to spend coins.

170
00:10:13,820 --> 00:10:17,970
But as of today,
this isn't used very heavily.

171
00:10:17,970 --> 00:10:19,700
So if you look at
the history of Bitcoin and

172
00:10:19,700 --> 00:10:23,875
look at what scripts have actually
been used, the vast majority,

173
00:10:23,875 --> 00:10:28,850
99.9% are exactly the same script, which
is in fact the script I showed you in our

174
00:10:28,850 --> 00:10:33,350
example of a script execution, a script
that just specifies one public key and

175
00:10:33,350 --> 00:10:36,540
requires a signature for that public
key in order to spend the coins.

176
00:10:37,700 --> 00:10:40,820
There's a few other things
that have some use.

177
00:10:40,820 --> 00:10:43,460
So MULTISIG gets used a little bit.

178
00:10:43,460 --> 00:10:47,200
And there's a special type of script
called Pay-to-Script-Hash that I'll talk

179
00:10:47,200 --> 00:10:48,210
about in just a minute.

180
00:10:50,610 --> 00:10:51,694
But other than that,

181
00:10:51,694 --> 00:10:56,040
there hasn't been too much creativity in
terms of what scripts people actually use.

182
00:10:57,120 --> 00:11:00,856
And one reason for that is that Bitcoin
nodes by default have a whitelist of

183
00:11:00,856 --> 00:11:05,720
scripts, and they refuse to accept
scripts that they consider not standard.

184
00:11:05,720 --> 00:11:07,960
This doesn't mean that those
scripts can't be used at all.

185
00:11:07,960 --> 00:11:09,490
It just makes them harder to use.

186
00:11:09,490 --> 00:11:12,260
And I'll talk about exactly what that
means a little bit later when we

187
00:11:12,260 --> 00:11:14,340
talk about the Bitcoin
peer-to-peer network.

188
00:11:15,470 --> 00:11:19,645
Okay so I mentioned that some of the
scripts are what we call proof-of-burn.

189
00:11:19,645 --> 00:11:23,830
So proof-of-burn is actually
a script that can never be redeemed.

190
00:11:23,830 --> 00:11:25,740
So if you have a proof of burn script,

191
00:11:25,740 --> 00:11:28,092
it's provable that those
coins have been destroyed.

192
00:11:28,092 --> 00:11:30,936
There's no possible way for
them to be spent.

193
00:11:30,936 --> 00:11:32,516
This is quite simple to implement.

194
00:11:32,516 --> 00:11:37,190
You just use this code OP_RETURN, which
throws an error if it's ever reached.

195
00:11:38,860 --> 00:11:42,850
And no matter what values you put before
then, that instruction will get executed

196
00:11:42,850 --> 00:11:45,970
eventually, in which case
this program will crash.

197
00:11:45,970 --> 00:11:50,302
The data that comes after OP_RETURN
is never going to be looked at, so

198
00:11:50,302 --> 00:11:54,940
this is an opportunity for people to
specify arbitrary data in a script.

199
00:11:54,940 --> 00:11:57,238
So what is the point of proof-of-burn?

200
00:11:57,238 --> 00:12:00,750
Well, there's two main things
that this gets used for.

201
00:12:01,800 --> 00:12:05,450
The first is to write arbitrary
data into the block chain.

202
00:12:06,625 --> 00:12:09,470
If for
reason you want to write your name, or

203
00:12:09,470 --> 00:12:13,650
if you want to time stamp and prove
that knew some data at a specific time,

204
00:12:13,650 --> 00:12:17,930
you can create a very low value Bitcoin
transaction that's proof-of-burn.

205
00:12:17,930 --> 00:12:22,820
So you destroy a very small amount of
currency, and in exchange you can write

206
00:12:22,820 --> 00:12:26,219
whatever you want into the block chain,
which should be kept around forever.

207
00:12:27,540 --> 00:12:31,830
The other example of proof-of-burn we'll
talk about in a later lecture on alternate

208
00:12:31,830 --> 00:12:37,790
currencies, but it can be a way to
bootstrap an alternative to Bitcoin

209
00:12:37,790 --> 00:12:42,400
by forcing people to destroy Bitcoin in
order to gain coins in the new system.

210
00:12:43,990 --> 00:12:47,930
So one thing that's funny about this is
that the sender of coins has to specify

211
00:12:47,930 --> 00:12:49,920
the script exactly.

212
00:12:49,920 --> 00:12:52,220
So this might be funny
if you're a consumer.

213
00:12:52,220 --> 00:12:53,517
You're shopping online.

214
00:12:53,517 --> 00:12:56,360
You're about to order something, and you
say, all right, I'm ready to check out.

215
00:12:56,360 --> 00:12:58,010
I'm ready to pay.

216
00:12:58,010 --> 00:13:01,270
Tell me the address where
I should send my coins.

217
00:13:01,270 --> 00:13:05,110
And the retailer came back and said,
oh well, we're doing something fancy now.

218
00:13:05,110 --> 00:13:06,650
We're using MULTISIG.

219
00:13:06,650 --> 00:13:11,156
We're going to ask you to send
the coins to some complicated scripts.

220
00:13:11,156 --> 00:13:13,001
You might say,
I don't know how to do that.

221
00:13:13,001 --> 00:13:14,920
That's too complicated.

222
00:13:14,920 --> 00:13:19,150
As a consumer, I just want to
send to a very simple address.

223
00:13:19,150 --> 00:13:23,270
So in response to that problem,
there's a really clever hack in Bitcoin,

224
00:13:23,270 --> 00:13:27,220
which is that instead of having the sender
specify the entire script, the sender can

225
00:13:27,220 --> 00:13:31,960
specify just a hash of the script that is
going to be needed to redeem those coins.

226
00:13:33,540 --> 00:13:36,510
So this looks like the sender is
specifying a very simple script

227
00:13:37,510 --> 00:13:40,460
which just hashes the top
value on the stack and

228
00:13:40,460 --> 00:13:43,360
checks to see if it's equal to
the required redemption script.

229
00:13:45,360 --> 00:13:48,887
So the receiver of those coins,
all they have to do, it looks like,

230
00:13:48,887 --> 00:13:55,550
is just specify the right script, and
then this transaction will verify.

231
00:13:55,550 --> 00:13:58,320
So the basic script is
very easy to satisfy here.

232
00:13:58,320 --> 00:14:01,540
The receiver just has to
specify is the data value

233
00:14:01,540 --> 00:14:05,350
the value of the script whose
hash the sender specified.

234
00:14:07,300 --> 00:14:12,030
But after this happens, a special second
step of validation is going to occur

235
00:14:13,710 --> 00:14:17,750
where that top data value from the stack
is going to be reinterpreted as

236
00:14:17,750 --> 00:14:23,240
instructions, and then it's going to
be executed a second time as a script.

237
00:14:23,240 --> 00:14:26,320
So we see there are two
stages that happened here.

238
00:14:26,320 --> 00:14:29,360
First there was this traditional
script which checked

239
00:14:29,360 --> 00:14:31,399
that the redemption script
had the right hash.

240
00:14:32,470 --> 00:14:37,120
And then the redemption script will be
deserialized and run as a script itself.

241
00:14:37,120 --> 00:14:39,690
And here is where the actual
signature check is going to happen.

242
00:14:42,010 --> 00:14:44,810
So this is called Pay to
Script Hash in Bitcoin,

243
00:14:44,810 --> 00:14:48,599
as an alternative to the normal mode of
operation, which is Pay to a Public Key.

244
00:14:50,400 --> 00:14:51,310
And the reason this was so

245
00:14:51,310 --> 00:14:55,140
complicated is that this was
added to BitCoin after the fact.

246
00:14:55,140 --> 00:14:58,730
This wasn't part of the initial
design specification.

247
00:14:58,730 --> 00:15:01,880
This is probably the most notable feature
that's been added to Bitcoin that

248
00:15:01,880 --> 00:15:03,860
wasn't there in
the original specification.

249
00:15:05,390 --> 00:15:08,169
And it solves a couple
of important problems.

250
00:15:09,340 --> 00:15:11,330
It removes complexity from the sender.

251
00:15:11,330 --> 00:15:15,000
So the recipient can just specify
a hash that the sender sends money to.

252
00:15:15,000 --> 00:15:19,530
And it actually has a nice efficiency
gain, as we'll talk about later, since

253
00:15:19,530 --> 00:15:24,010
miners have to track the set of output
scripts that haven't been redeemed yet.

254
00:15:24,010 --> 00:15:28,700
The output scripts are now as small as
possible with Pay to Script Hash, because

255
00:15:28,700 --> 00:15:33,602
they just specify a hash, and all of the
complexity is pushed to the input scripts.