Implementing the Ethereum Virtual Machine (Part I)

An exploration of what Clojure can offer the EVM.

Introduction

What’s Ethereum?

Ethereum is a blockchain — a distributed, immutable data structure — with support for general purpose (i.e Turing complete) on-chain computation. From the Yellow Paper:

Ethereum is a…technology on which all transaction based state machine concepts may be built. Moreover it aims to provide to the end-developer a tightly integrated end-to-end system for building software on a hitherto unexplored compute paradigm in the mainstream: a trustful object messaging compute framework.

Parameterized smart contracts (i.e. code) are committed to the blockchain, addressed, and may be invoked via user-generated transactions, or instructions in other smart contracts.

Great, and the EVM?


pragma solidity ^0.4.0;
contract C {
    function isSix(uint8 num)
    returns (bool) {
        return num == 6;
    }
}

The EVM, or Ethereum Virtual Machine, is a sandboxed virtual stack machine embedded within each full Ethereum node, responsible for executing contract bytecode. Contracts are typically written in higher level languages, like Solidity, then compiled to EVM bytecode.

Aside from arithmetic & control flow, the EVM supports ephemeral off-stack memory, inter-invocation value storage, as well as the ability to delegate to other contracts.

All EVM instructions are quantified in terms of an abstraction of their complexity — each operation consumes some amount of gas, deducted from the resources made available by the contract’s invoker. Execution only proceeds if sufficient gas remains.

The EVM instruction set consists of around 65 logically distinct operations — ~160 total instructions, when considering the variants of each. The word size is substantial, at 256 bits — wide enough to store cryptographic hashes or private keys in a single word.

Objectives

There’s plenty of EVM implementations around, including some excellent pure-functional attempts1 — in spite of them, I wanted to explore a specific, compact implementation strategy, while learning more about how the Ethereum platform operates at the lowest level.

My hypothesis is that Clojure’s particularly well suited to problems like this, and the EVM, being self-contained — and approachable in layers — lends itself to an episodic exploration of exactly why.

1 As with most things, the readability of the implementations is, generally, inversely proportional to their degree of real-world ambition. Life comes at you fast.

Scope

In this first installment, we’ll disregard contract invocation and gas, and focus on disassembling and interpreting general purpose EVM bytecode, without using higher-order organizational constructs (contracts, functions).

In a follow-up post, we’ll introduce metering of execution via a gas model, work towards implementing and testing the full set of instructions, and potentially look at performance optimizations in the bytecode interpreter.

Terminology

This discussion uses instruction and operation interchangeably, with the latter being preferred in code, as it’s less awkward to abbreviate.


Similarly, execution/interpretation and instruction pointer/program counter are used synonymously.

Walkthrough

The nascent EVM implementation we’re discussing can be found at nervous-systems/sputter on Github, though the relevant portions are reproduced inline.

Bytecode

Let’s look at the EVM program 0x60 0x01 0x60 0x02 0x01. Its ethereum-go disassembler output is reproduced in the left column:

000000: PUSH1 0x01 Push the 1 byte value 0x01
000002: PUSH1 0x02 Push the 1 byte value 0x02
000004: ADD Pop two stack items, push their sum

Before discussing any subtleties, we’ll blindly jump into writing a function that’ll disassemble byte arrays into a representation we may be able to interpret:

(ns sputter.vm
  (:require [sputter.op       :as op]
            [sputter.op.table :as op.table]
            [sputter.word     :as word]
            [sputter.state    :as state]))

(defmulti disassemble-op (fn [op bytes] (::op/mnemonic op)))

(defmethod disassemble-op :default [op bytes] op)

Here we define a multimethod, disassemble-op, dispatching on the :sputter.op/mnemonic key of its op argument. The default implementation — invoked when there’s no more specific match for an input — returns the op map untouched.

(defn- read-op [bytes i]
  (let [op (-> (get bytes i) (bit-and 0xFF))]
    (-> op op.table/ops (assoc ::pos i) (disassemble-op bytes))))

(defn disassemble
  "Byte array -> mapping between offsets and instructions."
  [bytes]
  (loop [i    0
         prog (sorted-map)]
    (if (<= (count bytes) i)
      prog
      (let [op   (read-op bytes i)
            prog (assoc prog i op)
            i    (+ i 1 (::op/width op 0))]
        (recur i prog)))))

The op.table/ops entries are namespaced maps holding the fully qualified operation mnemonic and the numeric opcode. The entry for 0x60 (PUSH1) looks something like this:

#:sputter.op{:mnemonic :sputter.op/push1
             :code     0x60}

There’s no additional metadata to attach to our ADD instruction, so the :default disassemble-op implementation will do fine — but there’s no clause which’ll correctly handle PUSH1 — we’d need to read its parameter and instruct disassemble to not process it as an opcode.

PUSH1 is the first in the PUSH family of operations, which place increasing numbers of bytes on the stack, as single words — from PUSH1/0x60 (1 byte values), to PUSH32/0x7f, which works with 32 byte values.

In the sputter.op namespace, the op mnemonics :sputter.op/push1 through :sputter.op/push32 are all derived from the parent keyword :sputter.op.group/push, which allows us to write a single multimethod for that family of operators:

(defmethod disassemble-op :sputter.op.group/push [op bytes]
  (let [size  (inc (- (::op/code op) op.table/push-min))
        start (inc (::pos op))
        n     (util/byte-slice bytes start size)]
    (assoc op
      ::op/width size
      ::op/data  (word/->Word n))))

op.table/push-min holds the opcode for PUSH1 — as the PUSH* codes are sequential, we subtract its value from the specific opcode we’re disassembling, increment it, and read that many bytes (one, for PUSH1) into a Word.

Word provides the VMWord protocol, an uninteresting abstraction responsible for sign-explicit representation/manipulation of units of data. In my single concession to brevity, I’m excepting it from further exploration.

Let’s disassemble the example program from above:

(disassemble (byte-array [0x60 0x01 0x60 0x02 0x01]))
;; =>
{0 #:sputter.op{:mnemonic :sputter.op/push1
                :code     0x60
                :width    1
                :data     #:Word{1}}
 2 #:sputter.op{:mnemonic :sputter.op/push1
                :code     0x60
                :width    1
                :data     #:Word{2}}
 4 #:sputter.op{:mnemonic :sputter.op/add
                :code     0x01}}

We’re using a map, rather than a vector, in order to retain the instruction offsets after lifting the parameter data into the op maps — this’ll allow us to avoid re-writing JUMP instructions later on.

All operations have a minimum width of one — the byte occupied by the opcode. An explicit width in an operation map describes the size of the associated data in bytes, if any — 1 for PUSH1, none for ADD.

Execution

Let’s define an immutable protocol/interface to organize the minimum amount of state we’re interested in tracking while interpreting bytecode.

(ns sputter.state
  (:require [sputter.word :as word])
  (:refer-clojure :exclude [pop]))

(defprotocol VMState
  "EVM execution state"
  (advance [state offset]
    "Increment the instruction pointer by `offset`.
     Returns a new state.")
  (instruction [state]
    "Return the instruction at pointer.")
  (push [state value]
    "Push `value` onto the stack.
     Returns a new state.")
  (pop [state num]
    "Pop up to `num` values from the stack.
     Returns vector of `[new-state popped]`."))

The protocol is our abstraction, and the record, below, which provides it, is our data structure. We anticipate growing the protocol to cover concerns which’ll benefit from polymorphic dispatch (e.g. experimenting with gas calculation models, or garnishing the state for testing).

(defrecord State [program pointer stack]
  VMState
  (advance [state offset]
    (update state :pointer word/add (word/->Word offset)))
  (instruction [state]
    (program (word/unsigned pointer)))
  (push [state value]
    (update state :stack conj value))
  (pop [state num]
    (let [[h t] (split-at num stack)]
      [(assoc state :stack (apply list t)) h])))

(defn map->State [& [defaults]]
  (State. (:program defaults {})
          (:pointer defaults word/zero)
          (:stack   defaults '())))

The instruction pointer is represented as a Word, which’ll make more sense once we’ve implemented the JUMP* family of operations.

Let’s construct a state for our test program:

(state/map->State
  {:program (disassemble
              (byte-array [0x60 0x01 0x60 0x02 0x01]))})
;; =>
{:program
  {0 #:sputter.op{:mnemonic :sputter.op/push1
                  :width    1
                  :data     #:Word{1}}
   2 #:sputter.op{:mnemonic :sputter.op/push1
                  :width    1
                  :data     #:Word{2}}
   4 #:sputter.op{:mnemonic :sputter.op/add}}
 :pointer #:Word{0}
 :stack   ()}

Stepwise Execution

Back in sputter.vm, step is a function accepting a State, executing a single instruction, and returning a new State (after adjusting the stack and/or instruction pointer):

(defn step [state]
  (if (::terminated? state)
    state
    (if-let [op (state/instruction state)]
      (let [[state popped] (state/pop state (::op/stack-pop op))]
        (-> state
            (op/operate (assoc op ::op/popped popped))
            (state/advance (+ 1 (::op/width op 0)))))
      (assoc state ::terminated? true))))

We elided :sputter.op/stack-pop when going through the op representations earlier — it’s an operation-specific constant integer describing the number of stack entries consumed by each execution.

For convenience, we centralize stack consumption, attaching the consumed values to the op map’s :sputter.op/popped key, before delegating to individual operator implementations.

Operators

Similarly to disassemble-op, the operate multimethod takes a State and an operation map, and dispatches on the operation’s mnemonic. Methods are required to return a new State:

(ns sputter.op
  (:require [sputter.word  :as word]
            [sputter.state :as state]))

(defmulti operate (fn [state op] (::mnemonic op)))

(defmethod operate :sputter.op.group/push [state op]
  (state/push state (::data op)))

(defmethod operate ::add [state op]
  (state/push state (apply word/add (::popped op))))

We rely on the keyword derivation we leveraged earlier to provide a single, identical implementation for all PUSH* opcodes — placing the operator’s data on the stack.

For :sputter.op/add, we use the ::popped vector provided to us by step, which’ll always contain two values, as the op has a ::stack-pop of 2.

Turning the Crank

(def state
  (state/map->State
    {:program (disassemble
                (byte-array [0x60 0x01 0x60 0x02 0x01]))}))

(step state)
;; =>
{:program
  {0 #:sputter.op{:mnemonic :sputter.op/push1
                  :width    1
                  :data     #:Word{1}}
   ...}
 :pointer #:Word{2}
 :stack   (#:Word{1})}

The represenation of the program is unchanged, though the listing’s abbreviating it to the previously executed instruction, for clarity.

The pointer is at 2 due to (step) advancing the instruction pointer by 1 + the op’s data width.

(step (step state))
;; =>
{:program
  {2 #:sputter.op{:mnemonic :sputter.op/push1
                  :width    1
                  :data     #:Word{2}}
   ...}
 :pointer #:Word{4}
 :stack   (#:Word{2} #:Word{1})}

And the final ADD:

(step (step (step state)))
;; =>
{:program
  {4 #:sputter.op{:mnemonic :sputter.op/add}
   ...}
 :pointer #:Word{5}
 :stack   (#:Word{3})}

Awesome. Using step, we can trivially define a function which runs a program to termination. As there’s no lookahead in step, it terminates immediately when passed a State with a pointer that’s fallen off the end:

(defn execute [state]
  (->> state
       (iterate step)
       (drop-while (complement ::terminated?))
       first))

(execute state)
;; =>
{:sputter.vm/terminated? true
 :stack                  (#:Word{3})
 ...}

Bonus Round: Control Flow

A slightly more complex program:

(disassemble
  (byte-array [0x60 0x02 0x5b 0x60 0x01 0x90
               0x03 0x80 0x60 0x02 0x57]))
;; =>
{0  #:sputter.op{:mnemonic :sputter.op/push1
                 :data     #:Word{2}}
 2  #:sputter.op{:mnemonic :sputter.op/jumpdest}
 3  #:sputter.op{:mnemonic :sputter.op/push1
                 :data     #:Word{1}}
 5  #:sputter.op{:mnemonic :sputter.op/swap1}
 6  #:sputter.op{:mnemonic :sputter.op/sub}
 7  #:sputter.op{:mnemonic :sputter.op/dup1}
 8  #:sputter.op{:mnemonic :sputter.op/push1
                 :data     #:Word{2}}
 10 #:sputter.op{:mnemonic :sputter.op/jumpi}}

Or, to put it more transparently:

000000: PUSH1 0x02 Establish a loop counter — 2
000002: JUMPDEST Begin loop body
000003: PUSH1 0x01
000005: SWAP1
000006: SUB
'(1 2) -> '(2 1)
000007: DUP1 Duplicate the counter
000008: PUSH1 0x02
000010: JUMPI
Jump to op 2 if the counter is non-zero

Operators

JUMPDEST, which marks a valid JUMP* target, is a no-op:

(defmethod operate ::jumpdest [state op]
  state)

SWAP*, as you might expect, exchanges the first and nth stack entries, e.g.:

'(1 2)   -> '(2 1)   -- SWAP1
'(1 2 3) -> '(3 2 1) -- SWAP2

Similarly to PUSH*, a single implementation suffices for all SWAP* instructions, as the semantics are equivalent to swapping the first and last of the consumed stack entries — the only difference is in the number of values popped — a detail handled by step.

(defmethod operate :sputter.op.group/swap [state op]
  (let [[h & t] (::popped op)
        state   (state/push state h)]
    (reduce state/push state t)))

SUB[tract] is more or less identical to ADD, from a distance:

(defmethod operate ::sub [state op]
  (state/push state (apply word/sub (::popped op))))

DUP* duplicates the nth stack entry at the top of the stack, e.g.:

'(1 2) -> '(1 1 2) -- DUP1
'(1 2) -> '(2 1 2) -- DUP2

DUP*‘s implementation is similar to SWAP* — we reinstate the consumed entries, and duplicate the last at the top of the stack.

(defmethod operate :sputter.op.group/dup [state op]
  (-> (reduce state/push state (::popped op))
      (state/push (last (::popped op)))))

JUMPI is a conditional jump — it consumes two stack values, and jumps to the instruction at the top of the stack, if the word behind it is non zero.

Our implementation relies on a new State function, position — an absolute implementation of advance, returning a new State with pointer set to the given instruction.

(defmethod operate ::jumpi [state op]
  (let [[pos v] (::popped op)]
    (cond-> state (not (word/zero? v)) (state/position pos))))

If the test value is zero, we return the state as-is.

Execution

(def state
  (state/map->State
     {:program (disassemble
                 (byte-array [0x60 0x02 0x5b 0x60 0x01 0x90
                              0x03 0x80 0x60 0x02 0x57]))}))

(execute state)
;; =>
{:pointer                #:Word{11}
 :stack                  (#:Word{0})
 :sputter.vm/terminated? true
 ...}

At termination, we see the final value of the loop counter. Let’s examine the intermediate stack states — I’ve removed the Word record markers from the output, to improve readability:

(->> (iterate step state)
     (take-while (complement ::terminated?))
     (map :stack))
;; =>
'(()
  (2)      ;; counter
  (2)      ;; start loop
  (1 2)    ;; push 0x01
  (2 1)    ;; swap
  (1)      ;; sub
  (1 1)    ;; dup
  (2 1 1)  ;; push jump addr
  (1)      ;; jump to 'start loop'
  (1 1)
  (1 1)
  (0)
  (0 0)
  (2 0 0)
  (0))

Done!

Finishing Up

We don’t yet have a rigorous definition of program termination, and a number of checks (e.g. JUMP validity) were omitted in the service of clarity and terseness. Similarly, the implementation of, say, multiplication, or signed arithmetic operations were excluded, as they’d be unlikely to meaningfully contribute to an understanding of the overall solution.

In the coming weeks, I’ll flesh out the implementation with the above details, and write-up an approach to some of the more interesting problems.

Github: nervous-systems/sputter.