Cryptocurrencies such as Bitcoin make use of public key cryptography, in order to restrict the ability to spend a coin to the owner. Recall the idea from the earlier post on this subject: A prospective Bitcoin holder — Alice — has to first select a key pair. This consists of a private key, which must be kept secret, and a public key. If she purchases some bitcoin from another party — Bob — he needs to create a transaction on the blockchain paying this to an address corresponding to the public key. When Alice is ready to spend her coins, she creates a new transaction with the input, and signs it using her private key. Using the public key, anyone can verify that the digital signature is valid but, since only Alice can create a valid signature, only she is able to spend her coins.

For added flexibility, Bitcoin does not hard-code this procedure and, instead, makes use of a simple stack-based programming language called Script. A program, or script, in this language consists of a sequence of commands, usually written from left to right and which are executed in order. Each command in this language takes one of two forms. They can be of the form <data>, which simply adds the hardcoded data to the top of the stack. Such data is always a byte vector, which can also be used to represent a variable length integer or a Boolean true/false flag. Or, it is one of a finite set of defined opcodes, written with the prefix OP_. An example program performing digital signature verification can be written with just three commands.

<sig> <pubKey> OP_CHECKSIG

The first two commands push the digital signature ‘sig’ and the public key ‘pubKey’ onto the stack. The final OP_CHECKSIG performs signature verification, using the signature and key from the stack. The result is that it removes these from the stack and replaces them with True if the signature is valid, and False if it is not. So, the result of this program is that we have True or False on the stack depending on whether the signature is valid or not.

Note, I did skip a rather important part of digital signatures. The whole idea is that Alice is signing a message, so the verification procedure clearly requires this message as an input. However, the OP_CHECKSIG opcode only takes two arguments, the signature and the public key. This is simply because it implicitly uses the transaction that is spending the coins as the message.

I will not go over the full specification and possibilities of Script here but, instead, outline some of the ways in which it is used. For more details, see the Bitcoin Wiki.

I start by describing the original (or legacy) approach, before explaining the more recent segregated witness method. The idea is that a transaction output contains some script which plays the part of the public key restricting how the coin is spent, and is called a locking script, or the ‘scriptPubKey’. The corresponding transaction input spending these coins contains a redeem script corresponding to the digital signature, called the ‘scriptSig’. This is as in figure 1 below, showing two transactions and their input and output fields.

When validating the transaction, we execute them in turn, first the scriptSig from the transaction input and then the scriptPubKey from the corresponding transaction output. If the script finishes execution with the item at the top of the stack equal to True, then the transaction input is valid, otherwise it is rejected as invalid. Also, Script does not contain any loop constructs, and is always executed from left to right. This means that it is not Turing complete, but is a very important part of the design. As each command can only be executed at most once, it is not possible to have scripts that take a long time to run, and possibly never terminate, which would cause serious problems for validation.

We can take the final two commands of the simple script above (i.e., everything other than the signature) as the scriptPubKey, so that Bob includes this in his transaction output. To spend this coin, Alice creates a transaction with the digital signature <sig> as the scriptSig. Together, they create the three line script above, which validates only if Alice creates a valid signature. Alice could use a more complicated scriptSig if she likes but, in order for it to validate, it needs to leave a correct signature on the stack, and nothing else. So, scriptPubKey is a function determining if the transaction input is valid, and scriptSig simply pushes the required arguments on the stack.

This very simple type of locking script described above is known as P2PK, or pay to public key, but is considered obsolete.

P2PK — pay to public key
scriptSig	<sig>
scriptPubKey	<pubKey> OP_CHECKSIG

Continue reading “Bitcoin Script” →