Script:   Testing Bitcoin Riddles
1 Basic Syntax
1.1 Opcodes’s Operand:   Script Machine
s-machine
1.2 Pushdata Statement
1.3 Opcodes
1.4 Summary:   Grammar of Script
2 REPL support
7.7

Script: Testing Bitcoin Riddles

Yuhao Zhang

 #lang bs package: bs

Script or (Bitcoin Script) is a language used by Bitcoin’s scripting system. It is a stack based language read from left to right.

1 Basic Syntax

Script is composed by a series of opcodes and pushdata statements. Both opcodes and pushdata statements are used to manipulate datas stored in a script machine. Opcodes and pushdata statements are read from left to right.

1.1 Opcodes’s Operand: Script Machine

A script machine is a data structure for storing current script states

struct

(struct s-machine (main-stk alt-stk tran-state level))

  main-stk : stack?
  alt-stk : stack?
  tran-state : boolean?
  level : (listof boolean?)
A script machine is a data structure that stores the states of current running script program. It has a main stack main-stk, an alternative stack alt-stk, a current transaction state tran-state and a list level representing the current if-block level.

When tran-state is being marked as #f, Script will stop further execution and report invalid transaction.

1.2 Pushdata Statement

A pushdata statement is used to push data onto the main stack of script machine. It needs to specify the size of data being pushed, and the data itself in hexadecimal format (e.g. 0x0102).

For example, to push hexadecimal data 0x01020304 onto the main stack, we write

4 0x01020304

In the above example, the data size specifier is written in decimal. It can also be written in hexadecimal format, like

0x04 0x01020304

You can also specify your pushdata statements with a opcode-like size restrictor: one from OP_PUSHDATA1, OP_PUSHDATA2, OP_PUSHDATA3 and OP_PUSHDATA4.

OP_PUSHDATA1 2 0x0102

The number followed after OP_PUSHDATA indicates the size specifiers’s size upper limit. For instance, with OP_PUSHDATA2 you can only specify a data with size not larger than 2562 - 1 = 65535 bytes, which also means your data size specifier should be an integer range between 0 and 65535.

1.3 Opcodes

Opcodes are procedures manipulating datas on the script machine. For example, OP_3 puts hexadecimal data 0x03 as bytes onto the main stack main-stk; opcode OP_VERIFY might change the transaction state tran-state. Checkout bitcoin wiki for details of different opcodes for now.

Some opcodes needs meta data from transactions in order to operate, like OP_CHECKSIG and OP_MULTICHECKSIG, etc. These opcodes are not supported by this implementation.

1.4 Summary: Grammar of Script

 

program

 ::= 

whitespace* expression {whitespace+ expression}*

 

expression

 ::= 

opcode  |  pushdata-statement

 

pushdata-statement

 ::= 

pushdata-op size hex

 

  |  

size hex

 

pushdata-op

 ::= 

OP_PUSHDATA1  |  OP_PUSHDATA2

 

  |  

OP_PUSHDATA3  |  OP_PUSHDATA4

 

size

 ::= 

hex  |  dec

 

opcode

 ::= 

OP_ADD  |  OP_SUB  |  ...

 

whitespace

 ::= 

  |  \n

 

hex

 ::= 

0x {hex-symbol hex-symbol}+

 

dec

 ::= 

digit+

 

hex-symbol

 ::= 

digit  |  hex-alphabet

 

digit

 ::= 

0  |  1  |  2  |  3  |  4

 

  |  

5  |  6  |  7  |  8  |  9

 

hex-alphabet

 ::= 

A  |  B  |  C  |  D  |  E  |  F

 

  |  

a  |  b  |  c  |  d  |  e  |  f

2 REPL support

Script support REPL, so you can continue your experiment with Script in The Interactions Window.