Script, a mini programming language

Source 1: Learn Me a Bitcoin — What is Script?

Source 2: Scripts (general & simple), John Newbery

What is Script?⌗

Script is a mini programming language used as a locking mechanism for transaction outputs:

A locking script is placed on every output.
An unlocking script must be provided to unlock an output when spending it.

If the full script is valid, the output is unlocked and can be spent.

What does the language consist of?⌗

The language is very basic and consists of two elements:

Data: e.g. Public Keys and Signatures
OPCODES: e.g. CHECKSIG or HASH160

A full list of bitcoin OPCODES can be found here.

How do you run a Script?⌗

First you need the two scripts: locking and unlocking. The unlocking script is placed to the left (i.e. "before") the "locking* script and the script is then executed from left to right.

Note	Remember that since 2012 the scripts are not simply concatenated and then run as one, but first the unlocking script is evaluated individually, then the locking script.

Script is executed using a stack-based approach, where script items can be pushed onto the (top of the) stack, or popped off (the top) of the stack. OPCODES can manipulate poped elements in various ways.

These can be condensed into two basic rules to follow when evaluating a script:

Data is always pushed onto the stack
OPCODES can pop elements off the stack, do somthing with them an optionally push new elements back onto the stack.

What makes a Script valid?⌗

A script is valid if the top and only element left on the stack is a 1 (or greater).

The script is invalid if:

The final stack is empty
The top element is on the stack is 0
There is more than one element left on the stack at the end of execution.
The script exits prematurely (e.g. OP_RETURN in a NULL DATA script).

Where is Script used?⌗

Scripts are put on every output and therefore are required for every input that is being spent in a transaction.

Why do we use Script?⌗

Why did Satoshi add script? A chain of digital signatures allows a digital coin to be transferred from one person to another. But what if I want my coin to be spendable when 2-of-3 people sign, it might be an escrow or some cold wallet service, how do I do that? What if I want my coin to be spendable when someone presents a secret, like the preimage to a hash digest?

Instead of creating lots of special transaction types, Satoshi added a generic scripting language to bitcoin. It specifies encumberances or conditions for spending coins.

Scripts allow us to create a huge number of different types of contractual transactions with a limited number of primitives, and so provide a "compact" way to reason about the validity of transactions without having to special-case large numbers of (new) transaction formats and maintain them.

You could create scripts like the following:

Maths puzzle — provide two numbers that sum to 8:

ADD 8 EQUAL
Hash puzzle — provide something that hashes to the same result as what’s inside the locking script:

SHA256 92071a437571e418df15ca4bd36c242eeaad0a60e38f1cfacc5bb2bb192189d8 EQUAL
Hash collision puzzle — provide two different strings of data that produce the same hash result:

2DUP EQUAL NOT VERIFY SHA256 SWAP SHA256 EQUAL

Peter Todd has posted some bounties for various types of hash collision in this bitcointalk.org post.

Greg Maxwell had a nice response as to how these work on reddit:

Many people aren’t aware of it but the backend Bitcoin system has no concept of "addresses". Instead when you make a transaction it specifies small bits of forth-like program code that provides rules that redeemer of the coins must satisfy to spend the coins.

The normal 1xxx addresses are just template for a ECDSA checking script. There are also 3xxx addresses where the address is a hash of an arbitrary script and the redeemer provides the script matching the hash and satisfies it.

This can enable powerful applications like "trustless escrows" with no mediator trusted to hold the coins or bindings to external zero knowledge proof systems. [Edit, a couple years later: We’ve demonstrated this kind of zero knowledge proof transaction now.]

In the posting linked here the author has paid funds to be redeemed by someone who can provide collisions for a non-linear (SHA1, RIPEMD160, SHA256, RIPEMD160(SHA256()), SHA256(SHA256()), and ABS() are the respective bounties)

Anyone who has Bitcoin can add to these bounties by simply sending funds to the respective 3xxx address which is a hash of the rules that check for a collision for the given function. The Bitcoin system itself arbitrates the rules, so there is no other party that must be trusted to pay or whom could withdraw the bounty after you begin your effort.

The SHA1 bounty has address 37k7toV1Nv4DfmQbmZ8KuZDQCYK9x5KpzP

A disassembly of its script is:

OP_2DUP OP_EQUAL OP_NOT OP_VERIFY OP_SHA1 OP_SWAP OP_SHA1 OP_EQUAL

Or, in English: Duplicate the last two elements on the stack ([A] [B] → [A] [B] [A] [B]), then compare if the top two elements are equal and push the result, if they’re not equal remove the result and continue processing, then compute the SHA1 of the top element on the stack ([A] [B] → [A] [sha1(B)]), then swap the top two elements ([sha1(B)] [A]), then compute the SHA1 of the top element ([sha1(B)] [sha1(A)]), and compare the result. If the final state is true the script passes and the spend is permitted.

— Greg Maxwell

Standard Scripts ⌗

Despite being able to create a variety of different locking scripts with various combinations of OPCODES, most nodes will only relay a handful of “standard scripts”:

P2PK (Pay To Public Key)

scriptSig: <pubkey> OP_CHECKSIG
scriptPubkey: <sig>

P2PKH (Pay To Public Key Hash)

scriptSig: OP_DUP OP_HASH160 <PubKeyHash> OP_EQUALVERIFY OP_CHECKSIG
scriptPubkey: <sig> <pubkey>

P2MS (Pay To Multisig)

scriptSig: <m> <A pubkey> [B pubkey] [C pubkey...] <n> OP_CHECKMULTISIG
scriptPubkey: OP_0 <A sig> [B sig] [C sig...]

P2SH (Pay To Script Hash)

scriptSig: OP_HASH160 <Hash160(redeemScript)> OP_EQUAL
scriptPubkey: <sig> [sig] [sig...] <redeemScript>

P2WPKH (Pay to Witness Public Key Hash)

witness:      <signature> <pubkey>
scriptSig:    (empty)
scriptPubKey: 0 <20-byte-key-hash>
              (0x0014{20-byte-key-hash})

The signature is verified as:

<signature> <pubkey> CHECKSIG

P2WSH (Pay to Witness Script Hash)
```
witness:      0 <signature1> <1 <pubkey1> <pubkey2> 2 CHECKMULTISIG>
scriptSig:    (empty)
scriptPubKey: 0 <32-byte-hash>
              (0x0020{32-byte-hash})
```
The last item in the witness (the "witnessScript") is popped off, hashed with SHA256, compared against the 32-byte-hash in scriptPubKey, and deserialized:
```
1 <pubkey1> <pubkey2> 2 CHECKMULTISIG
```
Next the script is executed with the remaining data from witness:
```
0 <signature1> 1 <pubkey1> <pubkey2> 2 CHECKMULTISIG
```

NULL DATA (a.k.a. an OP_RETURN transaction)

Pubkey Script: OP_RETURN <0 to 83 bytes of data>
(Null data scripts cannot be spent, so there's no signature script.)

Standard script types can be found for v0.21.0 in src/script/standard.cpp. Note that P2W{K|S}H is sub-divided into V0 (segwit), V1 (taproot) and UNKNOWN, which is the magic that permits soft-forking updates of new witness versions — un-upgraded nodes think unknown versions are standard so accept them into mempool and relay them.

BIP 141 has more detail on changes to scripts in SegWit.

Note	an OP_RETURN transaction is relayed and mined by default in Bitcoin Core 0.9.0 and later and adds arbitrary data to a provably unspendable pubkey script, that full nodes don’t have to store in their UTXO database.

Note	Non-standard scripts are valid, they are just not actively relayed. If you want a transaction with a non-standard script to be added to the blockchain, you either need to send it directly to a miner who will mine it for you, or mine it on to the blockchain yourself.

Summary ⌗

Every output is given a “locking script”.
You must then provide an “unlocking script” in the transaction that wants to spend that output.

When a node receives the spending transaction, it will combine both of these scripts together and run them. If a 1 is left on the top of the stack after the script has completed (and nothing else), then the script is valid and the output can be spent.

The script is actually a predicate. It’s just an equation that evaluates to true or false. Predicate is a long and unfamiliar word so I called it script.

— Satoshi Nakamoto