Okay so like we said each transaction output doesn't just specify a simple public key, it actually specifies a script. So what do I mean by that, what is a script and why do we use scripts? In this section we're going to talk about what the Bitcoin scripting language is, and why script is used instead of simply assigning a public key. Okay, so to understand scripts, I think the easiest way by an example. And we'll take as an example the most common script in Bitcoin, which is to redeem a previous transaction by signing with the correct public key. So this is what the output address would look like in that case. The output address is really a script. In this case the script is gonna have four instructions so what happens to this script? Who runs it? How does the script indicate who has the ability to spend these coins? The secret is that the input address is also a script. So that's a bit of script that you combine with the output address, you simply concatenate them and that gets you one script that has to run successfully in order to claim a Bitcoin. So traditionally, these two scripts are called scriptSig and scriptPubKey, and that's because in the simplest case, the output script just specifies the public key, and the input script specifies a signature with that public key. When a transaction is being validated, the two scripts get pasted together, they get run, and if the concatenated script can run without an errors, this is considered a valid transaction. So, where did this scripting language come from? It doesn't really have a proper name. It's just called Script or the Bitcoin scripting language, and it was built specifically for Bitcoin. It was probably most inspired by a language called Forth, which is an old stack-based simple programming language, but you don't need to understand Forth to understand Bitcoin scripting. The key design properties here were to have something that was quite simple, quite compact, but yet had support for pretty sophisticated cryptography. So there are special purpose instructions to do compute hash functions, and to compute signatures and verify signatures. And this is a stack-based language. And you may have never seen a stack-based language before in your life. But I'll explain in the next slide what that means and why that was chosen. So there are a lot of limits here that are important to keep in mind. In particular there are no loops in the Bitcoin scripting language. Every instruction is executed exactly once in a linear manner. So if you look at a script, just based on the number of instructions in the script, you know exactly how long it might take to run and how much memory it could use. So this is not a turning complete language. It doesn't have the ability to compute arbitrarily powerful functions. And this is by design, because the miners have to run these scripts which are submitted by arbitrary participants in the network. So you don't want to give them the power to submit a script that might have an infinite loop or might run forever. And since it's not a turning complete language, we don't have the halting problem. You can look at any Bitcoin script and be sure that it's going to terminate within a finite number of steps, which is just the number of instructions that are in that script. Okay, now the fun part. We're gonna look at a specific Bitcoin script, and exactly how it's executed. This is the same example as before, this is the most common script in Bitcoin. A script where the sender of coins simply specifies the public key of the recipient, and the recipient of the coins, to redeem them, has to specify a signature using that specified public key. So, the first two instructions in this script are simply data instructions, like I said, and these are the signature and the public key used to generate that signature and these were specified by the recipient in that script sig component or the input script. So executing data instructions is easy in a stack based language. If you see data, you just pushed it unto the stack. And that's the only interaction with memory that you have with a stack based programming language. There's no variables, there's only a stack, so the only thing you can do to write data to memory is to push it onto the stack. So after we've pushed those two values onto these stack, we're gonna start executing the second half of the script which was specified by the sender of the coins. So this is the script pubKey component of the script. And now we're gonna start to actually manipulate some of those values on the stack. So this duplicate instruction, OP_DUP, says, simply take the value that's on the top of the stack, pop it off, and then write two copies back to the stack. So we're just gonna duplicate that public key. The next instruction, HASH160, says, take the top value on the stack and compute a cryptographic hash of it. So this top value is going to be converted from the public key into a hash of the public key. Now we are going to do one more push of data onto this stack, and this data, remember, was specified by the sender of the coins. So this is the public key that the sender specified, had to be used to generate the signature to redeem these coins. So now at the top of this stack we have two values, we have the hash of the public key specified by the sender. And the hash of the public key that was actually used by the recipient when trying to claim the coins. And we'll just run this equal verify command, which just says are the two values at the top of the stack equal. If they aren't, an error's gonna be thrown and the script will stop executing. But we'll assume that they are. We'll assume that the recipient of the coins actually did use the correct public key. That instruction will consume those two data items that are at the top of the stack. So now we're left with two data items on the stack. A signature and a public key. And we've already checked that the public key was the right public key that was specified by the sender of these coins. And now we wanna check that the signature is actually valid. So this is where the power of the Bitcoin scripting language really comes into play. There's one instruction here that lets you verify a signature. So it's easy to write scripts that do signature verification without calling any special library to check the signatures. That's all built in to the Bitcoin scripting language. Now one thing I haven't told you is what is this actually a signature of. What was the input to the signature function? And it turns out there's only one thing you can sign in Bitcoin which is an entire transaction. So this check sig instruction is going to verify that the entire transaction was successfully signed. So in just one go, hopefully the check sig instruction will pop those remaining two items off of the stack, check that the signature is valid. And now we've executed every instruction in the script, there's nothing left on the stack, and if we haven't had any errors, the output of this script will be a simple yes. So every Bitcoin script can only produce two outcomes. It can either execute successfully with no errors, in which case the transaction is valid. If there's any error while the script is executing, the whole transaction will be invalid and shouldn't be accepted into the block chain. So a little bit more about the Bitcoin scripting language. It's very small, there's only room for 256 instructions, cuz each one is given one byte. And of those 15 of them are currently disabled, so you can't use them at all. And 75 of them are reserved. So haven't been assigned any specific meaning yet. But might be instruction that are added later in time. So there's a lot of the basic instructions that you'd expect in any programming language are gonna be there. There's basic arithmetic, basic logic like, if and then. Throwing errors, not throwing errors, returning early. And finally there are crypto instructions like I said. So there are hash functions, instructions for signature verification, and there's a special, very important instruction for multi-signature verification. That's called CHECKMULTISIG. So, this even more powerful than checking just the single signature with one instruction. Bitcoin actually lets you check multiple signatures with one instruction. So, with MULTISIG you specify n public keys, and you specify a parameter t or a threshold, and for this instruction to execute validly, there have to be at least t signatures, t out of n of those public keys, that are valid. So we'll show some examples of what you use MULTISIG for in a second, but it is quite a powerful primitive that in a compact way in the Bitcoin scripting language, you can express the concept that t out of n of these public keys must sign in order for this transaction to be valid. So there's an important bug here. There's a gotcha, which has been there since the beginning of time, which is that in the original implementation of this, the CHECKMULTISIG instruction actually pops an extra data value off the stack and ignores it. So this is just a quirk of the Bitcoin language. It's something that, in programming, you have to deal with by putting an extra dummy variable on to the stack. And at this point it's considered a feature in Bitcoin and that it's not going away. The costs of removing it are much higher than the damage it causes, so this is just a fun bug that everybody in the Bitcoin community gets to live with. So like I've said we have this whole scripting language that let's us specify, in some sense arbitrary conditions that must be met in order to spend coins. But as of today this isn't used very heavily. So if you look at the history of Bitcoin and look at what scripts have actually been used the vast majority, 99.9%, are exactly the same script. Which is in fact the script I showed you in our example of a script execution. A script that just specifies one public key, and requires a signature for that public key in order to spend the coins. There's a few other things that have some use. So MULTISIG gets used a little bit and there is a special type of script called Pay-to-Script-Hash that I'll talk about in just a minute. But other than that there hasn't been too much creativity in terms of what scripts people actually use. And one reason for that is that Bitcoin nodes by default, have a white list of scripts and they refuse to accept scripts that they consider not standard. This doesn't mean that those scripts can't be used at all, it just makes them harder to use, and I'll talk about exactly what that means a little bit later when we talk about the Bitcoin peer-to-peer network. Okay, so I mentioned that some of the scripts are what we call proof-of-burn. So proof-of-burn is actually a script that can never be redeemed. So if you have a proof -of-burn script, It's provable that those coins have been destroyed, there's no possible way for them to be spent. This is quite simple to implement. You just use this code, OP_RETURN, which throws an error if it's ever reached, and what no matter what values you put before then, that instruction will get executed eventually, in which case this program will crash. The data comes after OP_RETURN is never going to be looked at, so this is an opportunity for people to specify arbitrary data in a script. So what is the point of proof-of-burn. Well, there is two main things that this gets used for. The first is to write arbitrary data into the block chain if for some reason you want to write your name, or if you want to time stamp and prove that you knew some data at a specific time, you can create a very low value Bitcoin transaction that's proof-of-burn. So you can destroy a very small amount of currency, and in exchange you can write whatever you want into the block chain, which should be kept around forever. The other example of proof-of-burn we'll talk about in a later lecture on alternate currencies, that it can be way to bootstrap an alternative to Bitcoin by forcing people to destroy Bitcoin in order to gain coins in the new system. So one thing that's funny about this is that the sender of coins has to specify the script exactly. So this might be funny if you're a consumer, you're shopping online, you're about to order something. And you say all right, I'm ready to check out, I'm ready to pay, tell me the address where I should send my coins. And the retailer came back and said oh, well, we're doing something fancy now. We're using MULTISIG, we're going to ask you to send the coins to some complicated script. You might say, I don't know how to do that. That's too complicated. As a consumer, I just want to send to a very simple address. So in response to that problem, there's a really clever hack in Bitcoin, which is that instead of having the sender specify the entire script, the sender can specify just a hash of the script that is gonna be needed to redeem those coins. So this looks like the sender specifying a very simple script which just hashes the top value on the stack and checks to see if it's equal to the required redemption script. So the receiver of those coins, all they have to do, it looks like It's just specify the right script, and then this transaction will verify. So the basic script is very easy to satisfy here. The receiver just has to specify, as a data value, the value of the script that whose hash the sender specified. But after this happens, a special second step of validation is going to occur. Where that top data value from the stack is going to be reinterpreted as instructions, and then it's gonna be executed a second time as a script. So you see there were two stages that happened here, first there was this traditional script which checked that the redemption script had the right hash and then the redemption script will be deserialized and run as a script itself. And here's where the actual signature check is going to happen. So this is called pay to script hash in Bitcoin, as an alternative to the normal mode of operation, which is pay to a public key. And the reason this was so complicated is that this was added to Bitcoin after the fact. This wasn't part of the initial design specification. This is probably the most notable feature that's been added to Bitcoin that wasn't there in the original specification. And it solves a couple of important problems. It removes complexity from the sender, so the recipient can just specify a hash that the sender sends money to. And it actually has a nice efficiency gain as we'll talk about later, since minors have to track the set of output scripts that haven't been redeemed yet. The output scripts are now as small as possible with pay to script hash. Cuz they just specify a hash, and all of the complexity is pushed to the input scripts.
