Bitcoin Script to and from Bitcoin BASIC — a compiler and a decompiler

Abstract

Bitcoin Script is a stack machine with no names, no types and no structure a reader can hold. It is also, almost exactly, the machine that sits underneath every infix expression evaluator written for an 8-bit microcomputer: v = v + f/m - v*d becomes the same sequence of stack operations in either.

This standard defines Bitcoin BASIC, a BASIC dialect in one-to-one correspondence with the Script opcode set, and the two translations between them — a compiler that emits Script from the dialect, and a decompiler that renders a deployed locking script back into it. The dialect adds no runtime: every construct either emits opcodes or is resolved at compile time.

The decompiler is the half with no precedent. A compiler reports what an author meant; a decompiler reports what the bytes say — including bytes the reader did not write, fetched from the chain, belonging to somebody else.

Both directions run in a browser, with nothing to install:

https://grafverse.com/basic.html

Paste a locking script and read it back as a program, or write the dialect and compile it. The same implementation is also published on chain, which is for permanence and verification rather than for use.

Motivation

A covenant cannot be amended. Its constants are permanent, its branches are permanent, and the transaction that publishes it is the last moment at which any of it can change. Yet a covenant of useful size cannot be checked by eye: a working one is a few thousand opcodes of stack manipulation, a single significant constant is a two-byte push somewhere inside it, and one edit moves every offset and depth that follows. What gets verified in practice is a mental model of the script rather than the script — and the model is invalidated by the very change it was meant to check.

The consequence is that errors are discovered after publication and funding, when nothing can be altered.

Both halves of the answer are needed, and only one of them is conventional:

• Compiling removes a class of defect at the source. Branch arms that disagree about stack depth, a value left on the altstack in one arm only, a depth counted by hand — none of these are expressible in a higher-level language, so a compiler cannot emit them.
• Decompiling is what makes verification possible at all, and it applies to scripts nobody in possession of the tool wrote. It is the only route by which a third party can review a covenant before trusting value to it.

Relationship to BRC-15 and BRC-106

This standard sits above the existing representations rather than competing with them.

BRC-15 defines an assembly language for Script, and BRC-106 standardises deterministic translation of Script to and from ASM. Both operate at one token per opcode: they are lossless, they preserve the opcode sequence exactly, and they recover no structure. OP_ADD states that an addition occurs; it does not state that a line reads v = v + f/m - v*d, nor which bytes of a script are its mutable state.

Bitcoin BASIC operates on sequences of opcodes, and recovers structure: infix expressions, conditional blocks, named state fields, and loop bodies where the loop survives in the script. It is therefore lossy in spelling and exact in behaviour — a decompiled program recompiles to a script with identical semantics, and frequently to identical bytes.

The layers compose: Bitcoin BASIC to Script, and Script to ASM under BRC-15 or BRC-106.

Scope

Defines the correspondence between the dialect and the opcode set, the obligations of a conforming compiler, the obligations of a conforming decompiler, and the round trip between them.

Does not define a covenant's funding, its authorisation, or where its state lives — those are separate proposals. Does not standardise a source-file format, an editor, or a package layout.

⚠ This standard does not claim the dialect is the only readable representation of Script, nor that BASIC is the best available syntax. It claims that the correspondence is exact, that both directions are implementable, and that the reverse direction is the one currently missing.

Specification

The key words "MUST", "MUST NOT", "SHOULD" and "MAY" are as described in RFC 2119.

1. The correspondence

Every infix language is compiled to a stack machine. An expression parser converts infix to postfix, and the postfix form is a sequence of pushes and operators applied to a stack. Script is that stack machine, with the front end absent: it has the operators, the stack, and no parser.

The correspondence therefore requires no invention. A conforming implementation MUST NOT introduce runtime machinery that Script does not have — no call stack, no heap, no return addresses, no runtime types. Every construct in the dialect MUST either emit opcodes directly or be resolved entirely at compile time.

2. The dialect

A conforming dialect MUST provide, and its decompiler MUST recognise:

• Assignment — LET v = expr, with LET optional. Infix expressions with conventional precedence.
• Conditionals — IF cond THEN … ELSE … on one line, or IF cond THEN opening a block closed by END IF (or ENDIF). The spellings MUST compile to identical bytes. ⚠ The block form is not sugar: a line-scoped arm ends where its line ends, so a loop cannot live in one.
• Verification — VERIFY expr, emitting OP_VERIFY; the covenant's refusals are statements, not side effects.
• Counted loops — FOR i = a TO b [STEP s] … NEXT i, unrolled at compile time (§4.2).
• Fixed-width state — DIM name%width for numeric fields, DIM name$width for opaque bytes, with 1 ≤ width ≤ 75 (§4.3). ⚠ DIM belongs to a distinct compilation mode, not to a free-standing program: a layout is meaningless without the field offset and the peel and rebuild generated around it, and a conforming compiler MUST refuse it outside that mode rather than emit a bare push.
• Two-value results — l, r = SPLIT(x, n), since OP_SPLIT returns two values and no BASIC needed to.
• Line numbers, optional in source and emitted by the decompiler, and &H hexadecimal literals.

⚠ Implementations MAY extend the dialect, but a decompiler MUST NOT emit a construct its own compiler cannot parse. A reader that prints a dialect the writer rejects is two tools, not one.

3. Opcode correspondence

The machine's own words are its opcodes, exactly as every BASIC had words for the machine beneath it. The reference implementation maps 35 of them; a conforming implementation MUST use these names for these opcodes, so that a listing produced by one tool is parsed by another.

⚠⚠ = and SAMEBYTES MUST NOT be given one name. = is OP_NUMEQUAL and compares numbers; SAMEBYTES is OP_EQUAL and compares byte strings. 0, -0 and a zero padded to four bytes are one number and three different byte strings. Merging them erases a distinction that decides whether a covenant accepts a spend.

⚠ BITAND, BITOR and BITXOR are named apart from AND and OR for the same reason: OP_BOOLAND asks whether both operands are non-zero, and is not a bitwise operation.

4. What a covenant compiler must do that no BASIC had to

4.1 Balance the branches

Both arms of an OP_IF MUST leave the stack in the same shape. A conforming compiler MUST verify this and MUST refuse to emit otherwise. Hand-written Script gets this wrong silently, and the resulting failure surfaces far from its cause — typically where a later OP_SPLIT complains about a size.

4.2 Unroll the loops

Script has no backward jump, so there is nothing for a loop to compile to. FOR … NEXT MUST be unrolled at compile time, with the bounds known statically, and a conforming compiler MUST bound the expansion and fail rather than emit an unbounded one. Iteration in a script is spatial; iteration over time is a chain of spends, and is outside this standard.

⚠ A decompiler cannot recover a FOR that was unrolled — the loop is not in the script. It MUST render the unrolled body rather than infer a loop that may not have existed.

4.3 Make the widths the layout

DIM MUST declare a field's byte width, and that width MUST be the width the script carries. A conforming compiler generates both the reading of the state out of the script and its rebuilding, from the declaration alone.

Widths MUST be whole bytes in the range 1 to 75, and a compiler MUST refuse anything outside it. Above 75 a data push requires OP_PUSHDATA1 and a separate length byte, which shifts every offset after that field and breaks the property that the push opcode equals the width — the invariant a third-party reader depends on (see BRC-171).

⚠ The rebuild MUST gather fields by name, not by position: a compiler that reuses or coalesces slots will not leave them in declaration order, and a positional rebuild then assembles a valid-looking script with its state transposed.

4.4 Refuse rather than degrade

Where a construct cannot be expressed in opcodes, a conforming compiler MUST fail with a statement of why, and MUST NOT emit an approximation.

Exponentiation is the worked case. ^ is resolved at compile time in arbitrary-precision integers, is right-associative, and MUST reject a negative exponent and an exponent large enough to exceed what a script number can carry. If either operand is unknown until the script runs, the compiler MUST fail — Script has no power opcode, so there is nothing to emit. The idiom that replaces it is an unrolled loop whose counter supplies the exponent, which is also how the dialect supplies an array:

FOR k = 0 TO 23 : IF slot = k THEN bit = 2 ^ k : NEXT k

Twenty-four comparisons, each with its constant already folded. Script has no arrays; that is one.

5. Reading a script back

A conforming decompiler MUST operate on a script's parsed chunks, MUST NOT require the script to have been produced by the compiler, and MUST NOT modify the script in any way. Names are annotation supplied by the caller — the bytes remain the source of truth.

It MUST accept a declaration of what the stack already holds when the script begins, since a locking script is entered with the unlocking script's pushes already present, and without them a reader cannot know what it is looking at. Where no names are supplied it MUST still produce a correct listing with generated names.

It MUST report, rather than guess, when it can no longer track the stack — a script that reads below the bottom of the stack as the reader models it indicates either a malformed script or a wrong stack declaration, and both are results worth having.

6. Two examples, in both languages

One expression. The stack already holds v, force, mass and nv.

10 nv = v + force / mass

010379  push 3, OP_PICK      v
010379  push 3, OP_PICK      force
010379  push 3, OP_PICK      mass
96      OP_DIV               force / mass
93      OP_ADD               v + that
77      OP_NIP               discard the slot nv used to occupy

12 bytes, 9 opcodes. Infix became postfix, which is the whole of the correspondence in §1: the parser is the only thing Script was missing, and precedence decided the order of two opcodes.

A balanced conditional. The stack holds grip, demand and force.

10 force = 0
20 IF demand > grip THEN force = grip ELSE force = demand

00 77                     OP_0, OP_NIP            force = 0
010179 010379 a0          pick demand, pick grip, OP_GREATERTHAN
63                        OP_IF
  010279 0079 6b 75 6c      pick grip   → assign force
67                        OP_ELSE
  010179 0079 6b 75 6c      pick demand → assign force
68                        OP_ENDIF
77                        OP_NIP

29 bytes, 25 opcodes. ★ Note that both arms emit the same seven-opcode shape, differing only in which value they pick. That is §4.1 in the output: the compiler takes the union of what either arm assigns and makes both arms produce all of it, so the stack leaves the conditional identical either way. Hand-written Script is where this goes wrong, and it goes wrong silently — a mismatch surfaces much later, wherever the first opcode happens to read a slot that has moved.

Indexing without arrays. Noughts and crosses packs nine squares base 3 into two bytes — 0 empty, 1 for X, 2 for O — so a square is read by arithmetic rather than by lookup:

DIM board%2      REM  nine squares packed base 3
DIM turn%1       REM  whose move it is — 1 or 2

place = 0
IF move = 0 THEN place = 1
IF move = 1 THEN place = 3
IF move = 2 THEN place = 9
REM  … through to 6561
VERIFY place > 0                      REM  ★ the bounds check is free

VERIFY MOD(board / place, 3) = 0      REM  the square is empty
p = turn
board = board + p * place             REM  playing a move is an addition
turn = 3 - p                          REM  and the turn flips by arithmetic

★ Two properties fall out of the encoding rather than being enforced by extra code. A move outside 0…8 selects no constant, so place stays 0 and the bounds check costs nothing — and because the turn is read from state and written back as 3 - p, no party can play twice or play as the other. A base-4 packing of the same game is 105 bytes smaller, and gives up exactly this: a shift accepts an out-of-range index that a table of comparisons refuses.

Bounded and unbounded, from one source. Rule 110 is the same program with one number changed:

DIM cells%4      REM  31 cells, one bit each, wrapped into a ring
DIM gen%2

FOR g = 1 TO <generations>
  new = 0
  FOR i = 0 TO 30
    l = MOD(cells / 2 ^ MOD(i + 1, 31), 2)
    c = MOD(cells / 2 ^ i, 2)
    r = MOD(cells / 2 ^ MOD(i + 30, 31), 2)
    new = new + ((c OR r) AND NOT(l AND c AND r)) * 2 ^ i
  NEXT i
  cells = new
  gen = gen + 1
NEXT g

<generations> = 1 gives one generation per transaction; = 8 gives eight generations in one script, at 19,655 bytes. Both were run and arrive at the same state. Every 2 ^ … is folded at compile time because i is a loop counter, so the divisors are constants and there is no runtime index at all — which is why this program, alone among the four, needs neither a comparison table nor a shift. The eight-row rule table collapses to one line of boolean algebra.

7. The round trip

A program produced by the decompiler MUST recompile. The recompiled script MUST be semantically identical to the original; it SHOULD be byte-identical where the source construct survives in the script.

★ A disagreement between the two representations is the deliverable, not a defect in the tools. The static model held by the compiler is a stated hypothesis about a stack; the script interpreter is the referee. Where they differ, the difference is reported at the instruction that causes it rather than at the opcode that eventually fails — which is the shortest available path from a symptom to a cause.

8. Conformance

1. Every name in §3 maps to its stated opcode, and = / SAMEBYTES are distinct. (§3)
2. Both spellings of a conditional compile to identical bytes. (§2)
3. Branch arms are checked for equal stack shape, and emission is refused otherwise. (§4.1)
4. FOR is unrolled with static bounds and a bounded expansion. (§4.2)
5. DIM widths are the widths carried, and the rebuild gathers by name. (§4.3)
6. A construct with no opcode is refused with a reason, never approximated. (§4.4)
7. The decompiler reads scripts it did not produce, modifies nothing, and reports loss of stack tracking rather than guessing. (§5)
8. Decompiled programs recompile to semantically identical scripts. (§7)

⚠ Item 8 is the one that is worth measuring rather than asserting, and the measurement MUST include the number that recompile byte-identically — an implementation that recompiles to equivalent-but-different scripts every time has a defect its own test suite will not report.

Implementations

There are two copies of the reference implementation, and they exist for different reasons.

To use it — the workbench: https://grafverse.com/basic.html · compiles, decompiles, and reads a script straight off the chain. It requires no installation and no build; the page carries a prebuilt bundle.

To verify it, or to have it outlast this document — the archive. Published on chain so that a standard's reference implementation is a payload rather than a link:

payload   8e0a79e00ef3c38cf3c4fa33c7d8032cc5def3853c0e798730c48217f00a369a
archive   f308f18b952360b46d207beb8539bb202d704ab80e23c39425c76f024d908175   200,280 B · 15 files

The archive was recovered from that transaction, unpacked, and its test suites run: 42/42, 18/18 and 10/10. Verification is therefore reproducible from the txid alone rather than from a repository that may move.

★ The compiler and the decompiler import only an opcode-number table and a type that erases at runtime. An implementation in another language needs a list of opcode numbers and nothing more. Cryptography appears in the reference implementation solely where covenants authorise spends, which is not part of this standard.

The round trip, measured: of 15 decompiled programs, 15 recompile and 9 are byte-identical. The six that differ contain unrolled loops, which cannot read back as loops (§4.2). A hand-written covenant of 1,672 bytes and 1,108 opcodes renders as a listing; a 1,428-byte covenant renders as 216 lines.

Four covenants are included as tests, each answering the absence of arrays differently, and all deployed or interpreter-validated as real spends:

⚠ The base-4 result is not free: a shift does not supply the bounds check that a comparison did.

Turing completeness, stated exactly

Rule 110 is Turing complete by Cook's proof. Compiled from this dialect it runs two ways, and both were measured: eight generations unrolled into one script (19,655 bytes), and eight generations as eight chained spends (23,792 bytes across eight scripts). Both arrive at exactly the same state.

The distinction that matters is between a script and a chain of them, and it is usually stated backwards.

A single script is total: it provably halts. Its step count is bounded before it runs.

⚠ But it is not true that a script cannot iterate. A script iterates perfectly well — Rule 110 advances thirty-one cells every generation, unrolled, inside one script. What a script cannot do is run an unknown number of times, and that is the only thing the chain is needed for. The chain does not supply the looping. It supplies the not knowing when to stop.

A chain of covenant spends is unbounded in that count, so Rule 110 compiled from this dialect and advanced by such a chain is a universal computation: covenant-chained Script is Turing complete in the same qualified sense that any physical computer is.

⚠ The qualification is the tape, not the loop. Universality requires unbounded working storage; the deployed instance carries 31 cells and is therefore a finite automaton, however long it runs. The construction generalises — a covenant may carry more state at each spend than it carried at the last, and nothing in the transaction model bounds that — but a conforming implementation SHOULD state which of the two it has built, because a fixed-width state machine and an unbounded one are different claims.

★ And the absence of an in-script loop follows from what the machine is for, rather than from a shortfall in its language. Bitcoin is a timestamp server: its function is to order events in time. A program that never finishes produces no event to order — the transaction carrying its result is never built, and a script that failed to terminate would never be validated into a block. A timestamp server has no unbounded time to offer a computation that will never finish.

So the model does not exclude unbounded computation. It requires unbounded computation to be presented one halting step at a time, which is the condition under which each step can be validated by everybody and paid for by somebody. What reads as a missing language feature is the same property that makes the result verifiable.

⇒ Where an iteration is placed is then an economic question rather than a question of capability, and the answer differs per program. Rule 110's body dominates its frame 4.3 to 1, so unrolling eight generations into one script buys only 1.21×. A covenant whose frame dominates its body by 13 to 1 gained roughly tenfold from the same change.

References

• BRC-15 — Bitcoin Script Assembly Language, the token-level representation this composes above
• BRC-106 — Bitcoin Script ASM Format, for deterministic Script ↔ ASM translation
• BRC-21 — Push TX, used by the covenants included as tests, though not required by this standard
• Matthew Cook, Universality in Elementary Cellular Automata (2004), for Rule 110
• Bitcoin SV opcode semantics for the opcodes named in §3

The reference implementation and its test suite were written by Claude (Opus 5).