blockchainkit.vm#

blockchainkit.vm hub · History · Examples · API reference

Execution: a deterministic stack machine, its languages, contracts, and attacks.

A deterministic 256-bit stack machine and the languages, programs, and models built on it: assembly, reverse Polish notation, bytecode verification, Turing machines, Bitcoin Script, contracts, and attacks.

Every public name below is re-exported by the subpackage: import it as bk.vm.<name>. The plotting helpers are the exception: import them explicitly from blockchainkit.vm.visualizers, which loads Matplotlib.

Types and results#

Instruction type, errors, and result containers for blockchainkit.vm.

blockchainkit.vm.core.base.Instruction#

An (opcode, operand) pair; the operand is None for simple opcodes.

alias of tuple[str, int | None]

class blockchainkit.vm.core.base.TraceStep(pc, opcode, operand, stack, storage, gas_used)[source]#

Bases: object

Machine state just after one executed instruction.

Variables:

  • pc (int) – Index of the instruction that ran.

  • opcode (str) – Its opcode.

  • operand (int or None) – Its operand.

  • stack (tuple of int) – Stack after the instruction, bottom first.

  • storage (collections.abc.Mapping) – Working storage after the instruction (committed only on success).

  • gas_used (int) – Cumulative gas, including this instruction.

Parameters:
pc: int#
opcode: str#
operand: int | None#
stack: tuple[int, ...]#
storage: Mapping[int, int]#
gas_used: int#
exception blockchainkit.vm.core.base.VMError[source]#

Bases: ValueError

Invalid instruction, stack operation, arithmetic operation, or resource limit.

Variables:

trace (tuple of blockchainkit.vm.core.base.TraceStep) – Steps executed before the failure, when execute(..., trace=True) was requested; otherwise empty.

trace: tuple[TraceStep, ...] = ()#
class blockchainkit.vm.core.base.ExecutionResult(stack, storage, gas_used, trace=())[source]#

Bases: object

Final stack, read-only storage, consumed gas, and optional step trace.

Parameters:
stack: tuple[int, ...]#
storage: Mapping[int, int]#
gas_used: int#
trace: tuple[TraceStep, ...] = ()#
class blockchainkit.vm.core.base.VerificationResult(max_depth, errors)[source]#

Bases: object

Outcome of static bytecode verification.

Variables:

  • max_depth (int) – The largest stack height any path can reach.

  • errors (tuple of str) – Every problem found; empty if the program is safe.

Parameters:
max_depth: int#
errors: tuple[str, ...]#
property ok: bool#

True if no path can underflow and every join agrees on the stack height.

class blockchainkit.vm.core.base.TuringRun(outcome, steps, ones)[source]#

Bases: object

How a Turing machine run ended.

Variables:

  • outcome (str) – "halted", "looping" (a configuration repeated, so it never halts), or "unknown" (the step budget ran out first).

  • steps (int) – Steps executed, counting the halting transition.

  • ones (int) – Number of 1s on the tape at the end.

Parameters:
outcome: str#
steps: int#
ones: int#
class blockchainkit.vm.core.base.BusyBeaverResult(steps, ones, machine, counts)[source]#

Bases: object

The longest-running halting machine found by an exhaustive search.

Variables:

  • steps (int) – Its number of steps: the busy-beaver value S if no unknown machine halts later.

  • ones (int) – The 1s it leaves on the tape.

  • machine (dict) – Its rules, (state, symbol) -> (write, move, next_state).

  • counts (dict) – Machines per outcome: "halted", "looping", "unknown".

Parameters:
steps: int#
ones: int#
machine: dict[tuple[str, int], tuple[int, int, str]]#
counts: dict[str, int]#
class blockchainkit.vm.core.base.ScriptResult(valid, stack, error, operations)[source]#

Bases: object

Outcome of validating a Bitcoin-style script pair.

Variables:

  • valid (bool) – Both scripts ran without error and left a true value on top.

  • stack (tuple of bytes) – The final stack, bottom first.

  • error (str or None) – Why validation failed, if it did.

  • operations (int) – Opcodes and pushes executed. Scripts have no loops, so this never exceeds the combined script length.

Parameters:
valid: bool#
stack: tuple[bytes, ...]#
error: str | None#
operations: int#
class blockchainkit.vm.core.base.ReentrancyResult(withdrawn, deposited, calls, bank_balance)[source]#

Bases: object

What an attacker withdrew from a bank contract.

Variables:

  • withdrawn (int) – Total paid out to the attacker.

  • deposited (int) – What the attacker had deposited.

  • calls (int) – Times withdraw was entered, including re-entries.

  • bank_balance (int) – Funds left in the bank afterwards.

Parameters:

  • withdrawn (int)

  • deposited (int)

  • calls (int)

  • bank_balance (int)

withdrawn: int#
deposited: int#
calls: int#
bank_balance: int#
property stolen: int#

Withdrawn beyond the attacker’s own deposit.

Constructions and protocols#

A bounded deterministic 256-bit stack machine with atomic storage updates.

Instruction encoding: each instruction is a (opcode, operand) pair. Only PUSH, LOAD, STORE, JMP, and JZ take an integer operand. All instructions cost one teaching gas unit unless a schedule says otherwise; this is not an EVM implementation or cost schedule.

blockchainkit.vm.systems.stack_machine.OPERAND_OPCODES = frozenset({'JMP', 'JZ', 'LOAD', 'PUSH', 'STORE'})#

Opcodes that take a 256-bit integer operand.

blockchainkit.vm.systems.stack_machine.STACK_EFFECTS: Mapping[str, tuple[int, int]] = mappingproxy({'PUSH': (0, 1), 'LOAD': (0, 1), 'STORE': (1, 0), 'JMP': (0, 0), 'JZ': (1, 0), 'ADD': (2, 1), 'SUB': (2, 1), 'MUL': (2, 1), 'DIV': (2, 1), 'EQ': (2, 1), 'LT': (2, 1), 'DUP': (1, 2), 'DROP': (1, 0), 'SWAP': (2, 2), 'OVER': (2, 3), 'ROT': (3, 3), 'STOP': (0, 0), 'REVERT': (0, 0)})#

Values each opcode pops and pushes, as (pops, pushes).

Forth writes these as stack diagrams: OVER is ( a b -- a b a ) and ROT is ( a b c -- b c a ).

blockchainkit.vm.systems.stack_machine.OPCODES = frozenset({'ADD', 'DIV', 'DROP', 'DUP', 'EQ', 'JMP', 'JZ', 'LOAD', 'LT', 'MUL', 'OVER', 'PUSH', 'REVERT', 'ROT', 'STOP', 'STORE', 'SUB', 'SWAP'})#

Every opcode the machine accepts.

blockchainkit.vm.systems.stack_machine.check_word(value, name)[source]#

Raise VMError unless value is an int in [0, 2**256).

Parameters:
Return type:

None

blockchainkit.vm.systems.stack_machine.validate_program(program)[source]#

Check every instruction’s shape before anything runs; return the program as a tuple.

Raises:

VMError – An unknown opcode, a missing or extra operand, an operand outside 256 bits, or a jump target outside the program.

Parameters:

program (Iterable[tuple[str, int | None]])

Return type:

tuple[tuple[str, int | None], …]

blockchainkit.vm.systems.stack_machine.execute(program, *, storage=None, arguments=(), gas_limit=10000, stack_limit=1024, gas_costs=None, trace=False)[source]#

Execute a program against a copy of storage, committing only on success.

Parameters:

  • program (collections.abc.Iterable of tuple) – (opcode, operand) pairs. For binary operations the top value is the right operand: PUSH 7; PUSH 2; SUB produces 5.

  • storage (collections.abc.Mapping, optional) – Initial 256-bit integer keys and values. Never mutated by execution.

  • arguments (collections.abc.Sequence of int) – Initial stack, bottom first: the call’s inputs, like a contract’s call data.

  • gas_limit (int) – Maximum total gas, including STOP.

  • stack_limit (int) – Maximum stack depth.

  • gas_costs (collections.abc.Mapping, optional) – Per-opcode gas prices overriding the default of one unit each, for experiments with a cost schedule. Unlisted opcodes cost one unit; every price must be at least one, so gas always bounds the run.

  • trace (bool) – Record a TraceStep after every executed instruction, in ExecutionResult.trace on success or VMError.trace on failure.

Returns:

Deterministic stack, storage, gas used, and the trace if requested.

Return type:

blockchainkit.vm.core.base.ExecutionResult

Raises:

VMError – Malformed program, stack underflow or overflow, division by zero, REVERT, or running out of gas. Storage is then left unchanged.

Examples

>>> from blockchainkit.vm import execute
>>> execute([("PUSH", 7), ("PUSH", 2), ("SUB", None)]).stack
(5,)
>>> [step.stack for step in execute([("PUSH", 7), ("DUP", None)], trace=True).trace]
[(7,), (7, 7)]
>>> execute([("MUL", None)], arguments=(6, 7)).stack
(42,)

A two-pass assembler: write programs as text, with labels for jump targets.

Each line holds one instruction, an opcode with an optional operand, or a label ending in :. # starts a comment. A jump may name a label instead of an address; the first pass records where each label points, the second replaces label names by those addresses.

Example:

# Sum 1 + 2 + ... + n, with n in slot 0 and the sum in slot 1.
loop:
    LOAD 0
    JZ done
    LOAD 1
    LOAD 0
    ADD
    STORE 1
    LOAD 0
    PUSH 1
    SUB
    STORE 0
    JMP loop
done:
    STOP
blockchainkit.vm.systems.assembler.assemble(source)[source]#

Translate assembly text into (opcode, operand) instructions.

Operands are decimal or 0x hexadecimal integers, or labels for JMP and JZ.

Examples

>>> from blockchainkit.vm import assemble
>>> assemble('''
... start:
...     PUSH 0x10   # sixteen
...     JZ start
... ''')
(('PUSH', 16), ('JZ', 0))
Parameters:

source (str)

Return type:

tuple[tuple[str, int | None], …]

Reverse Polish notation (Łukasiewicz 1924; Hamblin 1957) and its compilation.

Łukasiewicz wrote logical formulas with the operator first, which needs no parentheses: + 1 * 2 3. Hamblin saw that the reversed form, 1 2 3 * +, is exactly the order in which a stack machine computes: push operands, and let each operator replace the top two values by its result. Dijkstra’s shunting-yard algorithm (1961) converts ordinary infix notation to that order, which is how expressions become stack-machine code.

blockchainkit.vm.systems.expressions.to_rpn(expression)[source]#

Convert an infix expression to reverse Polish notation (shunting yard).

Supports non-negative integers, + - * / with the usual precedence and left associativity, and parentheses.

Examples

>>> from blockchainkit.vm import to_rpn
>>> to_rpn("(1 + 2) * 3 - 4")
('1', '2', '+', '3', '*', '4', '-')
Parameters:

expression (str)

Return type:

tuple[str, …]

blockchainkit.vm.systems.expressions.compile_expression(expression)[source]#

Compile an infix expression to stack-machine instructions via RPN.

Each number becomes PUSH and each operator its opcode. Arithmetic is then the machine’s: modulo 2**256, with / as floor division.

Examples

>>> from blockchainkit.vm import compile_expression, execute
>>> execute(compile_expression("(1 + 2) * 3 - 4")).stack
(5,)
Parameters:

expression (str)

Return type:

tuple[tuple[str, int | None], …]

Static bytecode verification (Gosling 1995; the Java virtual machine).

Java’s virtual machine checks downloaded code before running it, so the interpreter can skip run-time checks. The verifier follows every path through the program, tracking how many values are on the stack at each instruction, without running anything. It rejects code that could underflow the stack on some path, or that reaches the same instruction with different stack heights along different paths (as a loop that pushes on every turn does). Code that passes has a known maximum stack depth.

blockchainkit.vm.systems.verifier.verify_bytecode(program, *, arguments=0)[source]#

Check stack safety on every path and compute the maximum stack depth.

This is abstract interpretation: the abstract state at an instruction is a single number, the stack height on entry. Starting from arguments at instruction 0, the verifier propagates heights along every edge (both outcomes of JZ) until nothing changes.

Parameters:
Returns:

max_depth and the list of problems found; ok if there are none.

Return type:

blockchainkit.vm.core.base.VerificationResult

Examples

>>> from blockchainkit.vm import verify_bytecode
>>> verify_bytecode([("PUSH", 1), ("ADD", None)]).errors
('pc 1: ADD needs 2 values but only 1 can be on the stack',)
>>> verify_bytecode([("PUSH", 1), ("PUSH", 2), ("ADD", None)]).max_depth
2

Turing machines (1936), the halting problem, and Radó’s busy beaver (1962).

A Turing machine reads one cell of an unbounded tape, and according to its state and the symbol there, writes a symbol, moves left or right, and changes state. Turing proved that no program can decide, for every machine, whether it halts. Radó turned that into numbers: the busy beaver S(n) is the most steps any halting n-state, 2-symbol machine takes from a blank tape. S grows faster than any computable function, so no fixed budget can separate “still running” from “never halts”. Blockchains respond the way Radó’s search must: they cap the work (gas) and stop there.

blockchainkit.vm.systems.turing.Rule#

move is -1 (left) or +1 (right); state "H" halts.

Type:

(write, move, next_state)

alias of tuple[int, int, str]

blockchainkit.vm.systems.turing.HALT = 'H'#

The halting state.

Type:

str

blockchainkit.vm.systems.turing.run_turing_machine(rules, *, max_steps=1000, start='A')[source]#

Run a 2-symbol machine from a blank tape for at most max_steps steps.

The transition into the halting state counts as a step, as in Radó’s definition. If the machine returns to an earlier configuration (same state, head position and tape), it provably runs forever. Otherwise, when the budget runs out, the outcome is unknown.

Examples

>>> from blockchainkit.vm import run_turing_machine
>>> champion = {("A", 0): (1, 1, "B"), ("A", 1): (1, -1, "B"),
...             ("B", 0): (1, -1, "A"), ("B", 1): (1, 1, "H")}
>>> run = run_turing_machine(champion)
>>> run.outcome, run.steps, run.ones
('halted', 6, 4)
Parameters:
Return type:

TuringRun

blockchainkit.vm.systems.turing.enumerate_machines(states)[source]#

Yield every states-state, 2-symbol machine: (4 (states + 1)) ** (2 states) of them.

>>> from blockchainkit.vm import enumerate_machines
>>> sum(1 for _ in enumerate_machines(1))
64
Parameters:

states (int)

Return type:

Iterator[dict[tuple[str, int], tuple[int, int, str]]]

blockchainkit.vm.systems.turing.busy_beaver(states, *, max_steps=100)[source]#

Search every machine with states states for the longest halting run.

Each machine runs for at most max_steps steps. The answer equals S(states) only if every machine classified as unknown really runs forever, which this search cannot prove; that gap is the halting problem. Feasible here for 1 or 2 states (20,736 machines for 2).

Examples

>>> from blockchainkit.vm import busy_beaver
>>> busy_beaver(1).steps
1
Parameters:

  • states (int)

  • max_steps (int)

Return type:

BusyBeaverResult

Bitcoin-style Script (2009): spending conditions as tiny stack programs.

A coin is locked by a locking script; to spend it, one supplies an unlocking script. The unlocking script runs first, then the locking script runs on the stack it left, and the spend is valid if no step fails and the top of the stack is true. Script deliberately has no loops, so a script of n operations runs at most n steps and needs no gas.

Teaching differences from Bitcoin: stack items are byte strings, but numbers are big-endian; OP_HASH256 (double SHA-256) replaces OP_HASH160 in pay-to-public-key-hash; and OP_CHECKSIG checks a blockchainkit Schnorr signature over an explicit message rather than a transaction digest.

blockchainkit.vm.systems.script.ScriptItem = bytes | str#

A data push (bytes) or an opcode name such as "OP_DUP" (str).

blockchainkit.vm.systems.script.OPCODES = frozenset({'OP_CHECKLOCKTIMEVERIFY', 'OP_CHECKSIG', 'OP_DROP', 'OP_DUP', 'OP_ELSE', 'OP_ENDIF', 'OP_EQUAL', 'OP_EQUALVERIFY', 'OP_FALSE', 'OP_HASH256', 'OP_IF', 'OP_RETURN', 'OP_SHA256', 'OP_TRUE', 'OP_VERIFY'})#

Every opcode the interpreter accepts.

blockchainkit.vm.systems.script.encode_public_key(public)[source]#

A public key as stack bytes (uncompressed point encoding).

Parameters:

public (tuple[int, int])

Return type:

bytes

blockchainkit.vm.systems.script.encode_signature(signature)[source]#

A signature as stack bytes: the commitment point, then the 32-byte response.

Parameters:

signature (SchnorrSignature)

Return type:

bytes

blockchainkit.vm.systems.script.number(value)[source]#

Encode a non-negative integer as minimal big-endian bytes (0 is empty).

Parameters:

value (int)

Return type:

bytes

blockchainkit.vm.systems.script.verify_script(unlocking, locking, *, message=b'', locktime=0)[source]#

Run the unlocking script, then the locking script on its stack, and judge the spend.

Parameters:
Return type:

blockchainkit.vm.core.base.ScriptResult

Notes

Running the scripts separately matters: until 2010 Bitcoin concatenated them, and the unlocking script OP_TRUE OP_RETURN ended execution early with true on top, spending any coin (CVE-2010-5141).

Examples

>>> from blockchainkit.crypto import sha256
>>> from blockchainkit.vm import verify_script
>>> verify_script([b"secret"], ["OP_SHA256", sha256(b"secret"), "OP_EQUAL"]).valid
True
blockchainkit.vm.systems.script.p2pkh_locking(public)[source]#

Pay to public-key hash: OP_DUP OP_HASH256 <hash> OP_EQUALVERIFY OP_CHECKSIG.

The coin names only the hash of a key; the spender reveals the key and a signature.

Parameters:

public (tuple[int, int])

Return type:

tuple[bytes | str, …]

blockchainkit.vm.systems.script.p2pkh_unlocking(signature, public)[source]#

The matching unlocking script: <signature> <public key>.

Parameters:
Return type:

tuple[bytes | str, …]

blockchainkit.vm.systems.script.htlc_locking(payment_hash, recipient, refund, timeout)[source]#

A hash time-locked contract.

The recipient can claim with a signature and the preimage of payment_hash (SHA-256); after timeout, the sender can take a refund with its own signature:

OP_IF
    OP_SHA256 <payment_hash> OP_EQUALVERIFY <recipient>
OP_ELSE
    <timeout> OP_CHECKLOCKTIMEVERIFY OP_DROP <refund>
OP_ENDIF
OP_CHECKSIG
Parameters:
Return type:

tuple[bytes | str, …]

Small contracts written for the stack machine.

  • vending_machine(): Szabo’s (1994) example of a contract enforced by a mechanism rather than a court: pay at least the price and an item and your change come out; otherwise nothing happens.

  • batch_transfer(): the token function behind the 2018 BeautyChain (BEC) exploit, where count * value overflowed 256 bits.

Both are assembled with assemble() and run with execute().

blockchainkit.vm.systems.programs.STOCK = 0#

Storage slots of the vending machine.

blockchainkit.vm.systems.programs.PRICE = 1#

Storage slots of the vending machine.

blockchainkit.vm.systems.programs.REVENUE = 2#

Storage slots of the vending machine.

blockchainkit.vm.systems.programs.vending_machine()[source]#

A vending machine: argument payment; storage holds stock, price and revenue.

On success the stock drops by one, the revenue grows by the price, and the change payment - price is left on the stack. Paying too little, or buying from an empty machine, reverts, so neither side can be cheated.

Examples

>>> from blockchainkit.vm import execute, vending_machine
>>> result = execute(vending_machine(), arguments=(5,), storage={0: 3, 1: 2})
>>> result.stack, dict(result.storage)
((3,), {0: 2, 1: 2, 2: 2})
Return type:

tuple[tuple[str, int | None], …]

blockchainkit.vm.systems.programs.batch_transfer(sender, recipients, *, checked=False)[source]#

Pay value (the one argument) from sender to each recipient.

Balances live in storage, one slot per account. Like BeautyChain’s batchTransfer, the program computes amount = count * value, checks the sender’s balance against amount, debits amount once and credits value to every recipient. The multiplication wraps modulo 2**256: with two recipients and value = 2**255, amount is 0, every check passes, and each recipient receives 2**255 tokens from nothing. checked=True adds the SafeMath test amount / count == value, which rejects the overflow.

Examples

>>> from blockchainkit.vm import batch_transfer, execute
>>> program = batch_transfer(1, [2, 3])
>>> dict(execute(program, arguments=(10,), storage={1: 100}).storage)
{1: 80, 2: 10, 3: 10}
Parameters:
Return type:

tuple[tuple[str, int | None], …]

Reentrancy: the DAO attack (2016).

The DAO’s withdrawal code sent ether before zeroing the caller’s balance. Sending ether to a contract runs that contract’s code, so the attacker’s contract called withdraw again from inside the payment, while its balance still showed the full deposit, and again, until the funds ran out or the call stack’s depth limit stopped it. About 3.6 million ether were drained in June 2016.

The fix is the checks-effects-interactions order: check the conditions, update the contract’s own state, and only then call out. A re-entrant call then finds a zero balance and gets nothing.

This module models the two orders directly in Python: the bank’s state is two numbers, and “sending” calls the attacker’s fallback.

blockchainkit.vm.systems.reentrancy.drain_bank(other_deposits, attacker_deposit, *, checks_effects_interactions=False, max_depth=1024)[source]#

Let an attacker that re-enters on every payment withdraw from a bank.

Parameters:

  • other_deposits (int) – Funds belonging to everyone else.

  • attacker_deposit (int) – The attacker’s own deposit, at least 1.

  • checks_effects_interactions (bool) – False: the vulnerable order (pay, then zero the balance). True: zero the balance before paying.

  • max_depth (int) – Maximum call depth (1024 in Ethereum then), bounding the recursion.

Return type:

ReentrancyResult

Examples

>>> from blockchainkit.vm import drain_bank
>>> drain_bank(90, 10).stolen, drain_bank(90, 10, checks_effects_interactions=True).stolen
(90, 0)

Plotting#

Plotting helpers for blockchainkit.vm: execution traces and stack heights.

blockchainkit.vm.visualizers.plots.plot_execution_trace(trace, *, max_rows=30, ax=None)[source]#

Tabulate the stack, storage, and gas after each executed instruction.

Parameters:
Return type:

matplotlib.axes.Axes

blockchainkit.vm.visualizers.plots.plot_stack_height(trace, *, label=None, ax=None)[source]#

Plot the stack height after each executed instruction.

The peak is the stack space the run needed: what a hardware stack must provide, and what static verification bounds in advance.

Parameters:
Return type:

matplotlib.axes.Axes