Each transaction output doesn’t just specify a public key. It actually specifies a script. What is a script, and why do we use scripts? In this section we’ll study the Bitcoin scripting language and understand why a script is used instead of simply assigning a public key.
The most common type of transaction in Bitcoin is to redeem a previous transaction output by signing with the correct key. In this case, we want the transaction output to say, “this can be redeemed by a signature from the owner of address X.” Recall that an address is a hash of a public key. So merely specifying the address X doesn’t tell us what the public key is, and doesn’t give us a way to check the signature! So instead the transaction output must say: “this can be redeemed by a public key that hashes to X, along with a signature from the owner of that public key.” As we’ll see, this is exactly what the most common type of script in Bitcoin says.
OP_DUP OP_HASH160 69e02e18… OP_EQUALVERIFY OP_CHECKSIG
Figure 3.4. an example Pay-to-PubkeyHash script, the most common type of output script in Bitcoin
But what happens to this script? Who runs it, and how exactly does this sequence of instructions enforce the above statement? The secret is that the inputs also contain scripts instead of signatures. To validate that a transaction redeems a previous transaction output correctly, we combine the new transaction’s input script and the earlier transaction’s output script. We simply concatenate them,
and the resulting script must run successfully in order for the transaction to be valid. These two scripts are called scriptPubKey and scriptSig because in the simplest case, the output script just specifies a public key (or an address to which the public key hashes), and the input script specifies a signature with that public key. The combined script can be seen in Figure 3.5.
Bitcoin scripting language. The scripting language was built specifically for Bitcoin, and is just called ‘Script’ or the Bitcoin scripting language. It has many similarities to a language called Forth, which is an old, simple, stack-based, programming language. But you don’t need to understand Forth to understand Bitcoin scripting. The key design goals for Script were to have something simple and compact, yet with native support for cryptographic operations. So, for example, there are special-purpose instructions to compute hash functions and to compute and verify signatures.
The scripting language is stack-based. This means that every instruction is executed exactly once, in a linear manner. In particular, there are no loops in the Bitcoin scripting language. So the number of instructions in the script gives us an upper bound on how long it might take to run and how much memory it could use. The language is not Turing-complete, which means that it doesn’t have the ability to compute arbitrarily powerful functions. And this is by design — miners have to run these
scripts, which are submitted by arbitrary participants in the network. We don’t want to give them the power to submit a script that might have an infinite loop.
<sig>
<pubKey>
————– OP_DUP OP_HASH160
<pubKeyHash?> OP_EQUALVERIFY OP_CHECKSIG
Figure 3.5. To check if a transaction correctly redeems an output, we create a combined script by appending the scriptPubKey of the referenced output transaction (bottom) to the scriptSig of the redeeming transaction (top). Notice that <pubKeyHash?> contains a ‘?’. We use this notation to indicate that we will later check to confirm that this is equal to the hash of the public key provided in the redeeming script.
There are only two possible outcomes when a Bitcoin script is executed. It either executes successfully with no errors, in which case the transaction is valid. Or, 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.
The Bitcoin scripting language is very small. There’s only room for 256 instructions, because each one is represented by one byte. Of those 256, 15 are currently disabled, and 75 are reserved. The reserved instruction codes haven’t been assigned any specific meaning yet, but might be instructions that are added later in time.
Many of the basic instructions are those you’d expect to be in any programming language. There’s basic arithmetic, basic logic — like ‘if’ and ‘then’ — , throwing errors, not throwing errors, and returning early. Finally, there are crypto instructions which include hash functions, instructions for signature verification, as well as a special and important instruction called CHECKMULTISIG that lets you check multiple signatures with one instruction. Figure 3.6 lists some of the most common instructions in the Bitcoin scripting language.
The CHECKMULTISIG instruction requires specifying n public keys, and a parameter t, for a threshold. For this instruction to execute validly, there have to be at least t signatures from t out of n of those public keys that are valid. We’ll show some examples of what you’d use multisignatures for in the next section, but it should be immediately clear this is quite a powerful primitive. We can express in a compact way the concept that t out of n specified entities must sign in order for the transaction to be valid.
Incidentally, there’s a bug in the multisignature implementation, and it’s been there all along. The CHECKMULTISIG instruction pops an extra data value off the stack and ignores it. This is just a quirk of
the Bitcoin language and one has to deal with it by putting an extra dummy variable onto the stack. The bug was in the original implementation, and the costs of fixing it are much higher than the damage it causes, as we’ll see later in Section 3.5. At this point, this bug is considered a feature in Bitcoin, in that it’s not going away.
Executing a script. To execute a script in a stack-based programming language, all we’ll need is a stack that we can push data to and pop data from. We won’t need any other memory or variables. That’s what makes it so computationally simple. There are two types of instructions: data instructions and opcodes. When a data instruction appears in a script, that data is simply pushed onto the top of the stack. Opcodes, on the other hand, perform some function, often taking as input data that is on top of the stack.
Now let’s look at how the Bitcoin script in Figure 3.5 is executed. Refer to Figure 3.7, where we show the state of the stack after each instruction. The first two instructions in this script are data instructions — the signature and the public key used to verify that signature — specified in the scriptSig component of a transaction input in the redeeming transaction. As we mentioned, when we see a data instruction, we just push it onto the stack. The rest of the script was specified in the scriptPubKey component of a transaction output in the referenced transaction.
First we have the duplicate instruction, OP_DUP, so we just push a copy of the public key onto the top of the stack. The next instruction is OP_HASH160, which tells us to pop the top value, compute its cryptographic hash, and push the result onto the top of the stack. When this instruction finishes executing, we will have replaced the public key on the top of the stack with its hash.
Next, we’re going to do one more push of data onto the stack. Recall that this data was specified by the sender of the referenced transaction. It is the hash of a public key that the sender specified; the corresponding private key must be used to generate the signature to redeem these coins. At this point, there are two values at the top of the stack. There is the hash of the public key, as specified by the sender, and the hash of the public key that was used by the recipient when trying to claim the coins.
At this point we’ll run the EQUALVERIFY command, which checks that the two values at the top of the stack are equal. If they aren’t, an error will be thrown, and the script will stop executing. But in our example, we’ll assume that they’re equal, that is, that the recipient of the coins used the correct public key. That instruction will consume those two data items that are at the top of the stack, And the stack now contains two items — a signature and the public key.
We’ve already checked that this public key is in fact the public key that the referenced transaction specified, and now we have to check if the signature is valid. This is a great example of where the Bitcoin scripting language is built with cryptography in mind. Even though it’s a fairly simple language in terms of logic, there are some quite powerful instructions in there, like this “OP_CHECKSIG” instruction. This single instruction pops those two values off of the stack, and does the entire signature verification in one go.
But what is this a signature of? What is the input to the signature function? It turns out there’s only one thing you can sign in Bitcoin — an entire transaction. So the “CHECKSIG” instruction pops the two values, the public key and signature, off the stack, and verifies that is a valid signature for the entire transaction using that public key. Now we’ve executed every instruction in the script, and there’s nothing left on the stack. Provided there weren’t any errors, the output of this script will simply be true indicating that the transaction is valid.
What’s used in practice. In theory, Script lets us specify, in some sense, arbitrary conditions that must be met in order to spend coins. But, as of today, this flexibility isn’t used very heavily. If we look at the scripts that have actually been used in the history of Bitcoin so far, the vast majority, 99.9 percent, are
exactly the same script, which is in fact the script that we used in our example. As we saw, this script just specifies one public key and requires a signature for that public key in order to spend the coins. There are a few other instructions that do get some use. MULTISIG gets used a little bit as does a special type of script called Pay-to-Script-Hash which we’ll discuss shortly. But other than that, there hasn’t been much diversity in terms of what scripts get used. This is because Bitcoin nodes, by default, have a whitelist of standard scripts, and they refuse to accept scripts that are not on the list. This doesn’t mean that those scripts can’t be used at all; it just makes them harder to use. In fact this distinction is a very subtle point which we’ll return to in a bit when we talk about the Bitcoin peer-to-peer network.
Proof of burn. A proof-of-burn is a script that can never be redeemed. Sending coins to a
proof-of-burn script establishes that they have been destroyed since there’s no possible way for them to be spent. One use of proof-of-burn is to bootstrap an alternative to Bitcoin by forcing people to destroy Bitcoin in order to gain coins in the new system. We’ll discuss this in more detail in Chapter
- Proof-of-burn is quite simple to implement: the OP_RETURN opcode throws an error if it’s ever reached. No matter what values you put before OP_RETURN, that instruction will get executed eventually, in which case this script will return false.
Because the error is thrown, the data in the script that comes after OP_RETURN will not be processed. So this is an opportunity for people to put arbitrary data in a script, and hence into the block chain. If, for some reason, you want to write your name, or if you want to timestamp and prove that you knew some data at a specific time, you can create a very low value Bitcoin transaction. You can destroy a very small amount of currency, but you get to write whatever you want into the block chain, which should be kept around forever.
Pay-to-script-hash. One consequence of the way that Bitcoin scripts works is that the sender of coins has to specify the script exactly. But this can sometimes be quite a strange way of doing things. Say, for example, you’re a consumer shopping online, and you’re about to order something. And you say, “Alright, I’m ready to pay. Tell me the address to which I should send my coins.” Now, say that the company that you’re ordering from is using MULTISIG addresses. Then, since the one spending the coins has to specify this, the retailer will have to come back and say, “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 simple address.”
Bitcoin has a clever solution to this problem, and it applies to not just multi-sig addresses but to any complicated condition governing when coins can be spent. Instead of telling the sender “send your coins to the hash of this public key”, the receiver can instead tell the sender “send your coins to the hash of this script. Impose the condition that to redeem those coins, it is necessary to reveal the script that has the given hash, and further, provide data that will make the script evaluate to true.” The sender achieves this by using the Pay-to-script-hash (P2SH) transaction type, which has the above semantics.
Specifically, the P2SH script simply hashes the top value on the stack, checks if it matches the provided hash value, then executes a special second step of validation: that top data value from the stack is reinterpreted as a sequence of instructions, and executed a second time as a script, with the rest of the stack as input.
Getting support for P2SH was quite complicated since it wasn’t part of Bitcoin’s initial design specification. It was added after the fact. 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. In our example above, Alice need not worry that Bob is using multisig; she just sends to Bob’s P2SH address, and it is Bob’s responsibility to specify the fancy script when he wants to redeem the coins.
P2SH also has a nice efficiency gain. Miners have to track the set of output scripts that haven’t been redeemed yet, and with P2SH outputs, the output scripts are now much smaller as they only specify a hash. All of the complexity is pushed to the input scripts.
