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 |
When you use wallet software to create a Bitcoin transaction then, typically, you would need to specify a Bitcoin address, which is just a random seeming string of characters when, really, what is happening is that you are creating a scriptPubKey, or locking script, restricting how the coins can be spent. That is what a Bitcoin address actually is — a representation of scriptPubKey. The P2PK scripts mentioned above would create rather long addresses and, instead, an alternative known as P2PKH (pay to public key hash) is standard. This is slightly more complicated, but the locking script only contains a 160 bit hash of the public key rather than the public key itself, resulting in shorter addresses and slightly more security.
| P2PKH — pay to public key hash | |
| scriptSig | <sig> <pubKey> |
| scriptPubKey | OP_DUP OP_HASH160 <pubKeyHash> OP_EQUALVERIFY OP_CHECKSIG |
To explain what this is doing, consider running scriptSig and scriptPubKey one command at a time, and keep track of what is on the stack.
| Command | Stack |
<sig> |
<sig> |
<pubKey> |
<sig> <pubKey> |
OP_DUP |
<sig> <pubKey> <pubKey> |
OP_HASH160 |
<sig> <pubKey> <pubKeyHash> |
<pubKeyHash> |
<sig> <pubKey> <pubKeyHash> <pubKeyHash> |
OP_EQUALVERIFY |
<sig> <pubKey> |
OP_CHECKSIG |
<True> |
The OP_DUP simply places a copy of pubKey at the top of the stack, and OP_HASH160 replaces this with its 160 bit hash. OP_EQUALVERIFY checks that the two elements at the top of the stack are equal (i.e., that pubKeyHash is equal to the hash of pubKey), and removes these from the stack. It stops execution and returns False if they are not equal, otherwise execution continues. Finally, OP_CHECKSIG is as for the simple P2PK script above.
Another very simple script example is one which always returns False. The OP_RETURN command simply stops execution and returns false, so none of the code following it is run, and such an output is impossible to spend. Any coins associated with such a transaction output are lost forever.
| Provably unspendable | |
| scriptPubKey | OP_RETURN … |
You may ask why anyone would ever want to create a transaction output that can never be spent. Sometimes, people want to use a transaction to record some information on the blockchain, rather than to just transact bitcoin, which can be done using an OP_RETURN followed by this information. The value of the output would likely be set to zero. Furthermore, the Bitcoin code understands that such outputs are unspendable, so does not even record it, avoiding some bloat in the utxo set.
A more interesting example is given by multisignature Bitcoin addresses. Consider a 2-of-3 multisig. This has three private keys, which can be held by three separate individuals, any two of which are able to sign a transaction spending the output. So, if one of the people cannot be contacted then it is still possible to access the coins but, if an attacker tries to gain access, they would need to obtain two of the private keys. Bitcoin Script is flexible enough to be able to construct a multisig account using OP_CHECKSIG together with conditional OP_IF commands to specify which of the two private keys the signatures correspond to. However, to simplify matters, there is the opcode OP_CHECKMULTISIG.
| P2MS — pay to multisig | |
| scriptSig | OP_0 <sig1> <sig2> |
| scriptPubKey | OP_2 <pubKey1> <pubKey2> <pubKey3> OP_3 OP_CHECKMULTISIG |
If the above code is run up to, but not including, the OP_CHECKMULTISIG, then the stack contains the following.
<0> <sig1> <sig2> <2> <pubKey1> <pubKey2> <pubKey3> <3> |
Then OP_CHECKMULTISIG will read the 3 from the top of the stack, followed by the three public keys, then the 2 followed by the two signatures. It will check that the signatures are valid for two of the keys, then remove the items from the stack. Finally, it will put TRUE on the stack if the signatures are valid, or False if either is not valid. You could ask what the initial OP_0 is doing. This is never used, but needs to be there because of a bug in the initial implementation of OP_CHECKMULTISIG, which has become part of the consensus. When it pops the arguments off the stack, it also removes one additional stack item, so would fail if we did not have the <0> at the bottom of the stack.
In practice, scripts such as P2MS are not often used. At least, not in the format above. This is because it does not fit into a standard Bitcoin address representation and, containing multiple public keys, the scriptPubKey is rather long. Instead, a very flexible alternative method is used, which has the ability of representing any kind of locking (or, redeem) script, while keeping the scriptPubKey in a standard and relatively short form. This is the P2SH or pay to script hash Bitcoin address type.
| P2SH — pay to script hash | |
| scriptSig | … <redeemScript> |
| scriptPubKey | OP_HASH160 <scriptHash> OP_EQUAL |
Rather than containing the entire redeem script in the scriptPubKey, it only contains its 160 bit hash. Then, the redeem script is serialized into a byte string and pushed onto the top of the stack by scriptSig. If we were to execute the code above, it would check that scriptHash is indeed equal to the hash of redeemScript, returning True or False depending on the result, and the top of the stack would be as follows.
… <redeemScript> <True/False> |
For regular Script execution, that would be it. However, the Bitcoin core code recognises the special format of P2SH addresses. As long as the top of the stack is True, it pops this off along with <redeemScript>, then deserializes and executes redeemScript.
P2SH addresses have various advantages. They are able to handle an arbitrary locking script while keeping the scriptPubKey in a standard short format. This makes it easier on the person paying to the address, as we just give them a standard Bitcoin address to pay into, rather than expecting them to handle a complicated locking script. It also shifts the cost of paying for the additional locking script bytes on the blockchain from the payer to the payee. Furthermore, there is some privacy and security benefit, since the locking script is not visible on the blockchain until the coins are spent. As P2SH handles any type of locking script, this is the standard form for non-P2PKH addresses. However, these have both now been superseded by SegWit addresses, as described below.
I have described some standard kinds of locking scripts above, but Script is quite general. It is possible to use conditional statements to combine different methods of spending coins, as well as time locks to restrict access to be after a specific time or block number. For example, we can have a transaction output that can be only accessed by Alice, so long as she does it within a specified time period, after which Bob can also spend the coins or, maybe, if Alice does not spend the coins within the allotted time period, then it becomes a multisig after which it requires both Bob and Charlie to sign. Clearly, this is a subject about which a lot could be written so, here, I am just sticking to the basic transaction types. See the lecture by Andreas Antonopoulos on advanced bitcoin scripting for a more detailed lesson on the possibilities with scripts.
Segregated Witness
Segregated witness (or SegWit for short) was introduced to Bitcoin in 2017. This is very similar to the approach described above, and makes use of the same Script programming language. For segregated witness addresses, the scriptSig is no longer used and, instead, is replaced by the new witness field. Bitcoin transactions are referred to by their transaction ID, which is a hash of the transaction data. Whereas the scriptSig field is a part of the transaction, so affects the transaction ID, the witness field is removed before computing the hash, so does not contribute to the ID. This solves a problem known as transaction malleability, where signing a transaction changes its ID. If two parties exchange unsigned (or partially signed) Bitcoin transactions off-chain, such as is done with the Lightning Network, then they do not know the transaction ID of the fully signed transactions, so cannot also exchange transactions spending its output. Using SegWit addresses, this problem goes away.
Additionally, the effect of a transaction on the blockchain is to absorb some utxos (transaction ouputs) and create new outputs, which does not involve the scriptSig field. We only need to know the scriptSig when determining if the transaction is valid but, once it is validated and added to the blockchain, the scriptSig and any contained signatures do nothing. Hence, removing this from the transaction ID calculation makes sense.
There are two standard SegWit address types. In both cases, we make use of the scriptPubKey in the transaction output and the witness field in the corresponding input spending the coins. The witness field itself just contains a sequence of byte vectors to be pushed onto the stack, and is not an arbitrary script containing opcodes. The scriptSig is left empty.
The first kind of SegWit address is P2WPKH or pay to witness public key hash corresponding to the legacy P2PKH address type described above. The scriptPubKey contains an OP_0 opcode followed by a 160 bit hash of the public key.
| P2WPKH — pay to witness public key hash | |
| witness | <sig> <pubKey> |
| scriptPubKey | OP_0 <pubKeyHash> |
Unlike the P2PKH script described above, we do not explicitly include the various opcodes to do the verification of the hash and of the signature. This is because the Bitcoin core code recognises this format as P2WPKH and handles it in a special way. It checks that the pubKey at the top of the witness stack does indeed have a hash equal to the pubKeyHash, then it performs the OP_CHECKSIG command automatically.
The second type of SegWit address is P2WSH or pay to witness script hash, corresponding to the legacy P2SH addresses described above. The scriptPubKey contains an OP_0 opcode followed by a 256 bit hash of the locking (or, witness) script.
| P2WSH — pay to witness script hash | |
| witness | <sig_1> … <sig_n> <witnessScript> |
| scriptPubKey | OP_0 <scriptHash> |
Note that the scriptPubKey is of a very similar format to that used for P2WPKH above, with the only difference being the length of the hash. Bitcoin automatically recognises 160 bit hashes as P2WPKH and 256 bit hashes as P2WSH. The top of the witness stack contains the locking script serialised as a byte vector. To validate this, Bitcoin pops witnessScript off the top of the stack, and checks that its hash is equal to scriptHash. If this succeeds, the stack now contains,
<sig_1> … <sig_n> |
Here, <sig_1> through <sig_n> will usually be signatures but, more generally, is just a sequence of stack items to be used by the locking script. Finally, witnessScript is executed to verify that the input is valid. Since P2WSH allows any Script code for witnessScript, it is quite general and, in particular, includes multisig transactions as described above.
Zero Knowledge 