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.

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

Inside a Transaction’s 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.

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.

Table 1: Alternate names for Input and Output Scripts

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.

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.

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.

What Bitcoin Script can compute

Let’s take a closer look at the machine that executes our Scripts. The Script Interpreter has not one, but two stacks. Alongside the Main Stack there is the Alt Stack (alternate stack). The OP_TOALTSTACK operation moves the top item of the Main Stack onto the Alt Stack, and OP_FROMALTSTACK moves it back again.

The Script Interpreter reads a Script in a single pass, from start to end. Bitcoin Script does have branching (OP_IF, OP_NOTIF, OP_ELSE, OP_ENDIF), but a branch only decides which instructions to skip on the way forward. Unlike Forth, Bitcoin Script has no JMP (jump) instruction that would take us back to an earlier instruction. This has two important consequences:

Every Script finishes. It is impossible to express an infinite loop in Bitcoin Script.
The number of operations a Script can perform is bounded by its length. One can therefore work out the worst-case cost of running a Script before it is ever executed.

It would be easy to conclude from this that Bitcoin Script can’t repeat a computation. That is not the case. Bitcoin Script repeats computations, but it does so in a different way.

Repetition in time, repetition in space

In most programming languages a loop repeats in time. There is one copy of the loop body, and the program jumps back to the start of it for as long as the data requires. Bitcoin Script repeats in space. The loop body is written out once for each iteration, one copy after the other, and the Script Interpreter passes over each copy exactly once. This is known as an unrolled loop (Figure 10).

Figure 10: A loop repeats in time; an unrolled loop repeats in space

Let’s look at an example. The following Locking Script adds up 1 + 2 + … + n, and will only accept the spend if the total is 6. The value of n is provided by the Unlocking Script. The loop body is written out three times, and each copy starts with OP_DUP OP_IF, so that it only runs while n is still greater than zero.

# Locking Script: only accept n (1 to 3) if 1 + 2 + ... + n = 6.
# The loop body is written out three times. Each copy only runs while n > 0.
OP_0 OP_SWAP                                            # stack: acc=0, n
OP_DUP OP_IF OP_TUCK OP_ADD OP_SWAP OP_1SUB OP_ENDIF    # iteration 1
OP_DUP OP_IF OP_TUCK OP_ADD OP_SWAP OP_1SUB OP_ENDIF    # iteration 2
OP_DUP OP_IF OP_TUCK OP_ADD OP_SWAP OP_1SUB OP_ENDIF    # iteration 3
OP_0 OP_NUMEQUALVERIFY                                  # n must have run out
OP_6 OP_NUMEQUAL                                        # acc must be 6

If we provide an Unlocking Script of OP_3, the stack (the accumulator, followed by n) goes through the following states:

After	acc	n
setup	0	3
iteration 1	3	2
iteration 2	5	1
iteration 3	6	0

At the end n has reached zero and the total is 6, so the spend is valid. If we provide OP_2 instead, the third copy of the loop body is skipped, and our total of 3 fails the final check. If we provide OP_4, then n is still 1 after the last copy has run, and OP_NUMEQUALVERIFY rejects the spend. The Script has room for three iterations, and no more.

All three of these cases are run through a Script Interpreter as part of this site’s tests. The Script shown above is the exact Script that is tested.

Do note what is fixed when the Script is written, and what is decided when it runs:

Fixed by the Script: what one iteration does, and the maximum number of iterations.
Decided by the data: how many iterations actually run, and the values they operate on.

In practice, nobody writes out these copies by hand. A program written in an ordinary programming language generates the Script, and a for loop in that program appends the loop body once for every iteration. The loop is still there. It runs at the time the Script is generated, rather than at the time the Script is executed.

This is also where the Alt Stack earns its keep. A loop body that juggles several values can park the values it isn’t using on the Alt Stack. That way every iteration finds the Main Stack in the same arrangement, and every copy of the loop body can be identical.

Unrolling a loop does come at a cost. Every copy of the loop body is part of the Script, and therefore the size of the Script grows with the maximum number of iterations, whether those iterations run or not. Since a Transaction’s fee is calculated from its size, the fee grows along with it. Bitcoin SV is able to carry large Scripts because the Genesis upgrade removed the consensus limit on the number of operations in a Script. The size limits that a miner applies are policy settings.

How much can one Script compute?

It turns out that anything that can be computed within a known number of steps can be computed by a single Script, with the Script growing in proportion to the number of steps. To see why this is so, consider a Script that simulates a Turing Machine. The machine’s tape is a byte string, OP_SPLIT and OP_CAT read and write that tape at a position held on the stack, and the machine’s transition rules are a fixed block of branches. If we unroll that block once for each step, we end up with a Script whose length grows linearly with the number of steps.

The Theory of Computation has a precise name for this. A Script is a lot like a Boolean circuit. Each one handles inputs up to a given size, and covering larger inputs requires a larger Script. A family of Scripts, all generated by one program, covers every input size. This is known as a non-uniform model of computation. Circuits are known to be as capable as Turing Machines within a bound on the number of steps: a Turing Machine that runs for T steps can be simulated by a circuit of roughly T log T in size (Pippenger and Fischer, 1979).

Why is this interesting? In exchange for writing its bound into the program, Bitcoin Script gains predictability. Whether a Script halts is never in question, and what a Script can cost is known before anyone runs it. Bitcoin therefore has no need to meter computation while it runs.

Ethereum takes the other path. The Ethereum Virtual Machine (EVM) charges gas for each operation it executes, up to a limit set by the sender, and stops the computation when the gas runs out. Both models bound every computation. In Bitcoin the bound is the Script itself, and in Ethereum it is the gas paid at run time.

Unbounded computation: one step per Transaction

What about a computation where we don’t know the number of steps in advance? Such a computation can be spread across Transactions, with one iteration in each Transaction (Figure 11). The Locking Script of each Output holds the program, and the Output also carries the current state of the computation. The Script places a constraint on the Transaction that spends it: that Transaction must create a new Output with the same Script and the next state. A Script of this kind is called a covenant.

You might be wondering how a Locking Script can see the Transaction that spends it. The Unlocking Script provides the spending Transaction’s Sighash preimage, i.e. the data that an OP_CHECKSIG signs. The Locking Script checks that this preimage is genuine by verifying a Signature over it with OP_CHECKSIG, and then reads from it whatever it needs, e.g. the hash of the new Outputs.

Figure 11: A covenant: one step of the computation per transaction

What we have here is a single, fixed program that runs for as many steps as people keep spending its Outputs. The computation stops when the state meets the exit condition, at which point the Script allows an Output without the covenant. Nothing in the program itself bounds the number of steps. The bound comes from outside the program: someone has to keep spending, and every step pays a fee.

This is the same position that an ordinary computer finds itself in. Its programs are bounded by the memory and time that are available, rather than by their own text. Seen in this light, Bitcoin as a whole is a general-purpose computer. Each Script is a bounded step, and the chain of Transactions provides the repetition.

The lineage tokens in libtokensv work in this way. Each token’s Script checks the Transaction that spends it, so that every transfer must carry the same rules forward.

About the two stacks

The two-stack machine is a classic model from the Theory of Computation. It consists of a finite-state control unit with two stacks (Figure 12).

Diagram of a two-stack machine — Figure 12: A two-stack machine

“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.

The two-stack machine gets its power from its control unit, which may return to any of its states and keep running for as long as the computation needs, moving symbols between its two stacks. Bitcoin’s Script Interpreter makes a single pass over its instructions, so this theorem does not carry over to a single Script. Inside a Script, the second stack is an organisational aid rather than a source of computational power. OP_PICK and OP_ROLL can already reach any item on the Main Stack by its position.

Where the picture painted by the theorem does fit Bitcoin is at the level of the Transaction chain. There, the covenant’s program is applied again at every step.

Advantages of this computing model

As we have seen, every Bitcoin Script is guaranteed to finish, and its worst-case cost can be read from the Script itself. This means that no computation needs to be metered while it runs, and no Transaction can tie up the nodes that validate it for longer than its size allows.

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 UTXO (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.