Bitcoin Script
Bitcoin Script is a scripting language built directly into the Bitcoin protocol. It is a stack-based language which takes it’s inspiration from the Forth Programming Language. In this section we will explore exactly how Bitcoin Script is used inside the Bitcoin protocol.
Blocks and Transactions
Previously we looked at how a set of Transactions are assembled into a candidate Block, and how a Transaction Processor (miner) needs to successfully perform a proof-of-work calculation over the data contained in that Block before that Block may be broadcast to other Transaction Processors for acceptance as a valid entry into the “global bitcoin database” known as the blockchain.
The following diagram (Figure 1) shows a high-level schematic of :
- how blocks relate to each other
- how transactions relate to each other
- the positioning of transactions within blocks.
Figure 1: Blocks and Transactions
Note the following:
- Time flows from left-to-right
- Blocks point “backward” in time. I.e. a block references it’s direct ancestor to form a Linked List.
- Transactions also point “backward” in time. Each new transaction references an “earlier” transaction. We will dig a little deeper into the meaning of this “backward pointing” in the next section.
Let us redraw the diagram (Figure 2) , but zoomed in a little to reveal a little more detail about what’s inside the transaction. We are revealing just enough to gain a conceptual grasp of things at this point.
Figure 2: Transaction Inputs and Outputs
Note the following:
- In block a, the transaction Tx a1 has two outputs. One of the outputs is spent, one of the outputs remain unspent.
- In block b, the transaction Tx b1 has two inputs. Each of these inputs are referencing outputs in Tx a1 and Tx a3 respectively.
- The transaction Tx b1 contains both inputs and an output. However, as can be seen here, the input of one Bitcoin Transaction always points to the output of an “earlier” transaction.
Transaction Inputs do not necessarily have to reference Outputs from Transactions in earlier blocks. Transaction Inputs may also reference Outputs from earlier Transactions in the same block. The Bitcoin Node software currently places a limit on the number of transactions that could be chained within the same block, and the different protocol implementations (BTC, BCH and BSV) all have different limits imposed in this regard.
Inside a Transaction’s Input
Figure 3: Format of Transaction Input
Inside a Transaction’s Output
Figure 4: Format of Transaction Output
Input / Output Chaining
Transactions are chained through the values in the metadata contained within Inputs an Outputs (Figure 5)
Figure 5: Relationship of Inputs to Outputs
Script Evaluation
When a Transaction Processor first sees a Transaction on the network, it will perform a validation on that Transaction. This validation is performed over the Inputs within this new Transaction and the Outputs of the referenced Transaction(s). For the purposes of this section we will focus only on the validation step involving the Script portion of the Inputs an Outputs.
Script Evalutation is perform as a two-step process: Concatenation, followed by Execution.
Concatenation
The Input and Output Scripts are concatenated together (Figure 6). This might seem odd, but if you recall that our intention is for this new transaction to be accepted into a block, the Input Script behaves like a key to the Output Script’s lock. Part of the Transaction validation process includes execution of this concatenated Script to check if the combined Scripts leave a value of True on the top of the stack as the final result.
Figure 6: Input/Output Script Concatenation
The Input and Output Scripts are also known by different names. You will possibly see all these names used in different contexts and throughout other texts as well. This guide will use all of them interchangeably depending on context.
| Input Script | Output Script |
|---|---|
| Unlocking Script | Locking Script |
| ScriptSig | ScriptPubkey |
- ScriptSig is so named because this is the only place where we can place an ECDSA Signature for the Transaction being validate. We shall cover Signatures extensively in a later section.
- ScriptPubkey is possibly a reference to the early days of Bitcoin where it was typical to have only a Public Key and an operand for checking a Signature in the Locking Script/(ScriptPubkey). The corresponding /Unlocking Script (ScriptSig) would only contain a Signature.
Let’s consider this scenario of locking an Output with a Public Key, and requiring a Signature in the Unlocking Script. The concatenated Scripts would have the form shown in Figure 7.
Figure 7: Pay-to-Public-Key Script
Execution
Once the Input Script and Output Scripts have been concatenated, the Script Interpreter proceeds with a stack-based execution of the tokens in the Script. In the following diagram (Figure 8), data is pushed onto the stack, and when a Script function is encountered, that function is executed against the data already on the Stack.
Figure 8: Stack Execution - Conceptually
Let us now see how we would execute the specific case of a P2PK (Pay to Public Key) Script (Figure 9). In a P2PK Transaction, the Locking Script is set to the Recipient’s public Key, along with a function that performs signature validation against the public Key. Therefore, in order to unlock the Output, the recipient must provide a valid Signature corresponding to the Public Key provided.
Figure 9: Pay-to-Public-Key Stack Execution
As you can see, at the end of the execution we have a [True] value remaining on the stack. This means that the Script portion of the transaction has passed validation.
Twostack PDA
In the tradition of Forth, Bitcoin Script has two stacks which may participate within the Script Evaluation. The addition of a second stack might seem trivial, however it transforms Bitcoin’s Script Interpreter from a Pushdown Automata to a Two-Stack Pushdown Automata.
Without delving too deep into the Theory of Computation, we will focus on accurate labelling, allowing the reader to perform self-study into these areas.
A PDA(Pushdown Automata) is FSM+Stack (Finite State Machine with a Stack)
Bitcoin’s Script Interpreter has a second stack, referred to as the Alt Stack (alternate stack). This makes the Bitcoin Script Interpreter a 2-Stack PDA. Why is this interesting ? The Minsky Theorem.
The Minsky Theorem
“If a language L is accepted by a Turing Machine, then L is accepted by a two-stack machine” - Theorem (8.13) - Introduction to Automata Theory, Languages, and Computation - Hopcroft, Motwani & Ullman.
Figure 10: Diagram of the Minsky Model
The above theorem is covered in much detail, along with proofs in the referenced text. Replicating the proof of the theorem here is beyond the scope of this guide.
The short of it, is that as a two-stack machine, the Bitcoin Script Interpreter has Turing Equivalence. Bitcoin Script is extremely powerful, and capable of expressing highly complex computations. In later sections we will dive a little deeper in how we can do some very interesting things with Bitcoin Script indeed.
Do note that due to the nature of Finite State Machines, the size of the program (Script), is a limiting factor on the scope of usefull computations that one is able to express within Bitcoin Script. I.e, the smaller the script, the more constrained the different types of computations one can perform.
Limitations of Bitcoin Script
To the extent that Bitcoin Script does not have a looping construct, it becomes a little more cumbersome to perform computations that require iterations. The typical way in which one would achieve this is by “unrolling the loops”. I.e. duplicating the function within Script, and using the Altstack to store-and-retrieve the result of each computation. This is most similar to how a tail-recursive function uses the stack.
This can be tedious, and the reader is advised to look towards using a high-level scripting language like Scrypt Studio wherein the loop can be expressed in the scripting language, and wherein a compiler will compile that high-level language into it’s Bitcoin Script equivalent by “unrolling” the loop. We will cover Scrypt more in depth within a later section.
Bitcoin Script programs can grow rather large for more complicated computations. This directly translates into higher fees when broadcasting transactions containing large scripts.
Advantages of this computing model
Unlike Forth, Bitcoin Script lacks a JMP(JUMP) instruction. This is the primary reason why it is impossible to express an infinite loop in Bitcoin Script. It also means that every Bitcoin Script program is guaranteed to halt.
Ethereum’s Solidity programming language does allow infinite loops. The Ethereum Virtual Machine (EVM) counters the potential of locking up the EVM by essentially charging for computation based on predicted run-time. This means that all computations are limited by the amount of fees committed to those computations, rather than by the size of the program as in Bitcoin’s case.
Within Bitcoin, computations are only executed/validated when a new Transaction is broadcast to the network. This means that “state”, or the “current state” of a computation is always known by the value expressed in a UXTO (unspent transaction output). Other blockchain models follow a “distributed computer” model wherein all the nodes in the network (even non-mining nodes), must recompute the state of all the contracts/programs in order to resolve the current state of the system as a whole. In this sense, the Bitcoin model of computation can be seen as much more efficient.
Due to the aforementioned situation of having global state encapsulated within the UTXO database, computations on Bitcoin become massively “parallelizable”, since different nodes in the network are free to focus on computations that are only useful to their specific use-cases.