Bitcoin: transaction script and the Script language. Guide part 7

This article, which will discuss Bitcoin and scripts, the seventh in a series of insights into the more technical part of Bitcoin, will continue the guide designed to gradually enter the “down the rabbit hole” of the blockchain world.

As far as the bibliography is concerned, it is necessary to mention the book “Mastering Bitcoin” by Andreas Antonopoulos, from which the images have been taken. 

Bitcoin: Transaction script and the Script language

The bitcoin transaction script language is called Script and the UTXO lock and unlock scripts are written in this language: when a transaction is validated the unlock scripts of each input are executed together with the corresponding block script to check whether it meets the spending conditions.

Turing incompleteness. The bitcoin script language contains operators but is arbitrarily delimited: there are no loops or complex flow control features other than conditional flow control, so the language is not complete Turing.

Stateless verification. In the script language of bitcoin transactions there are no preliminary or subsequent execution operations of a script: the information needed to execute a script is contained in the same script, which will execute in a predictable manner, in the same way, on any system (there are operators who can access external information: CSV can check if an input tx has been confirmed by x blocks; CLTV can check the field nLockTime of the tx).

Script construction (lock and unlock). The Bitcoin transaction validation (tx) engine relies on two types of scripts to validate transactions: a lock script and an unlock script.

A lock script is a spending condition put on an output. The block script is called the scriptPubKey script because it contains a public key or a bitcoin address (public key hash).

An unlock script is a script that resolves (or meets) the conditions placed on a lock script and allows spending (or consuming) the output. Unlock scripts are part of every tx input: in most cases, they contain a digital signature produced by the wallet’s private keys. Unlock scripts are called scriptSig, because they usually contain a digital signature.

Each Bitcoin node validates transactions by executing both scripts (lock and unlock). Each input contains an unlock script and refers to a previous UTXO. The validation software copies the unlock script, retrieves the UTXO the input refers to, and copies the lock script from, that UTXO. The unlock and lock scripts are executed in sequence: the input is valid if the unlock script meets the unlock conditions; all inputs are validated independently, as part of a general transaction validation.

The script execution stack. Bitcoin’s script language is called stack-based because it uses a stack, a simple data structure. It allows two operations: push and pop. Push adds an object at the top of the stack, pop removes the object at the top of the stack.

The Script language executes the script from left to right.

1. The numbers (constant data) are pushed on the stack.
2. Operators “push” or “pop” one or more parameters from the stack, acting on them and can “push” a result on the stack. OP_ADD removes (pops) two objects from the stack, adds them up and pushes the sum to the top of the stack.
3. Conditional operators evaluate a given condition, producing a (boolean) result of TRUE (1) or FALSE (0).
4. The operator OP_EQUAL removes two objects from the stack and inserts TRUE if they are the same, FALSE if they are different.

Transactions are valid if the final value is TRUE or any other value other than 0; transactions are invalid if the top value is FALSE or if the script execution is stopped by an operator like OP_VERIFY, OP_RETURN or a conditional terminator like OP_ENDIF.

In the original client (Satoshi Client), the unlock and lock scripts were concatenated and executed in sequence. After 2010 (for security reasons) scripts were executed separately: first the unlock script is executed, then the main stack is copied and the lock script is executed. If the result is TRUE, the unlock script has been successful in resolving the conditions imposed by the lock script, so the input is valid to spend the UTXO.

Pay-to-Public-Key-Hash (P2PKH). Most transactions processed by the network are P2PKH scripts. These outputs contain a lock script that blocks the hashed output of a public key (ergo a bitcoin address). An output locked with a P2PKH script can be unlocked (spent) by presenting a public key and a digital signature created by the corresponding private key. Such an output would have a lock script in this form:

OP_DUP OP_HASH160 <Cafe Public Key Hash> OP_EQUALVERIFY OP_CHECKSIG (where the hash of the public key equals the bitcoin address without the Base58Check code). This lock script can be satisfied with an unlock script in the form:

<Cafe Signature> <Cafe Public Key> and the two scripts together would form the following combination:

<Cafe Signature> <Cafe Public Key> OP_DUP OP_HASH160 <Cafe Public Key Hash> OP_EQUALVERIFY OP_CHECKSIG

More specifically, starting with the script:

<sig> <PubK> DUP HASH160 <PubKHash> EQUALVERIFY CHECKSIG

First: the signature goes to the top of the stack (stack, from above: <sig>)

 <PubK> DUP HASH160 <PubKHash> EQUALVERIFY CHECKSIG

Second: the public key passes at the top of the stack (stack, from above: <PubK> <sig>)

DUP HASH160 <PubKHash> EQUALVERIFY CHECKSIG

Third: the DUP operator duplicates the object at the top of the stack and places the result on top (stack, from top: <PubK> <PubK> <sig>)

HASH160 <PubKHash> EQUALVERIFY CHECKSIG

Fourth: the operator HASH160 “hashes” the object at the top of the stack (first with SHA256 and then with RIPEMD160) and puts the result on top (stack, from the top: <PubKHash> <PubK> <sig>)

<PubKHash> EQUALVERIFY CHECKSIG

Fifth: PubKHash value passes on top (stack, from top: <PubKHash> <PubKHash> <PubK> <sig>)

EQUALVERIFY CHECKSIG

Sixth: the operator EQUALVERIFY compares the two PubKHash removing them from the stack in case they are equal (stack, top: <PubK> <sig>)

CHECKSIG

Seventh: the CHECKSIG operator controls the match between the on top public key and the signature, removing them and “pushing” the value TRUE if  they “match” (stack, from top: TRUE)

Digital Signatures (ECDSA). The algorithm for digital signatures used in Bitcoin is Elliptic Curve Digital Signature Algorithm, or ECDSA, based on the mathematics of elliptical curves for coupling private and public keys, which uses the script functions OP_CHECKSIG, OP_CHECKSIGVERIFY, OP_CHECKMULTISIG, and OP_CHECKMULTISIGVERIFY.

A digital signature is a mathematical scheme consisting of two parts:

• an algorithm to create a signature from a message, using a private key (the key it signs);
• an algorithm that allows anyone to verify the signature, give the message and a public key.

In the implementation of the ECDSA algorithm in Bitcoin the message that is signed is the transaction, or rather a hash of a specific subset of data in the transaction. The key signing is the private key, and the result is the signature:

\(\(Sig = F_{sig}(F_{hash}(m), dA)\)\)

where:

• dA is the signing private key
• m is the transaction or parts of it
• Fhash is the hashing function
• Fsig is the signing algorithm 
• Sig is the resulting signature

The Fsig function creates a Sig signature which is composed of two values, R and S, which once calculated are “serialised” in an encoding scheme called Distinguished Encoding Rules, or DER. For example:

3045022100884d142d86652a3f47ba4746ec719bbfbd040a570b1deccbb6498c75c4ae24cb02204b9f039ff08df09cbe9f6addac960298cad530a863ea8f53982c09db8f6e381301

This signature is a serialised byte-stream of the R and S values produced by a wallet to prove ownership of the private key to spend an output. The format consists of 9 elements:

• “30”-indicating the start of a DER sequence
• “45”-the length of the sequence, 69 bytes
• “02”-an integer value follows 
• “21”-the length of the integer, 33 bytes
• R-00884d142d86652a3f47ba4746ec719bbfbd040a570b1deccbb6498c75c4ae24cb
• “02”-another integer follows
• “20”-the length of the integer (32 bytes)
• S-4b9f039ff08df09cbe9f6addac960298cad530a863ea8f53982c09db8f6e3813
• “01” A suffix indicating the type of hash used (SIGHASH_ALL)

Checking the signature. To verify the signature it is necessary to have the signatures R and S, the serialised transaction and the (corresponding) public key: the verification algorithm takes the message (a hash of the transaction or part of it), the public key of the signatory and the signature (the values R and S), and reports TRUE if the signature is valid for the message and the public key.

Bitcoin addresses, balances and other abstractions

Transactions do not contain bitcoin addresses “in themselves”, but operate through lock and unlock scripts. Ergo should not be concretely spoken about balances if not indirectly since each wallet shows them: they are abstractions that simply derive from the primitive components of the transactions.