Implementing the Ethereum Virtual Machine (Part II)

An exploration of what Clojure can offer the EVM.

In the first instalment, we walked through a sketch of an immutable EVM implementation in Clojure. While limited to flow control and a few of the EVM’s arithmetic primitives, there was plenty to discuss.

As promised, I’ve expanded the implementation to provide support for gas, memory & storage — enough for it to successfully execute a few hundred of Ethereum’s VM test specifications.

There’s a fair amount of ground to cover, and it’s likely that comprehension would be aided by a passing familiarity with previously-covered details. While relevant portions of code are reproduced inline, the full project lives at nervous-systems/sputter on Github.

The Word and The Flesh

Although not described in any detail in the previous post, the VMWord protocol indirects all manipulation of on-stack EVM values (32 byte words). Skimming over it’ll help us reason about some of the higher level constructs to come:

(ns sputter.word
  (:require [sputter.util            :as util]
            [sputter.util.biginteger :as b])
  (:import [java.math BigInteger])
  (:refer-clojure :exclude [zero? or mod]))

(defprotocol VMWord
  (add [word x] [word x m]
    "`word` + `x` [% `m`]")
  (sub [word x]
    "`word` - `x`")
  (mul [word x] [word x m]
    "`word` * `x` [% `m`]")
  (mod [word x]
    "`word` % `x`")
  (div [word x]
    "`word` / `x`")
  ...
  (as-vector [word]
    "A fixed length, zero-padded byte vector representation
     of `word`'s underlying bytes.")
  (as-biginteger [word]
    "A [[java.math.BigInteger]] representation of `word`'s
     underlying bytes."))

Implementation

The only VMWord implementation in the project is written in terms of java.math.BigInteger — basically an immutable byte array interface, with some arithmetic functionality.

In the future, I may try an alternate approach using transient vectors, though haven’t yet succumbed to the urge to write a byte-wise version of each word operation.

(def size      32)
(def max-value (-> b/one (b/<< (* size 8)) (b/- b/one)))

(defn- truncate [word]
  (b/and word max-value))

(extend-type BigInteger
  VMWord
  (add
    ([word x]   (-> word (b/+ x) truncate))
    ([word x m] (-> word (b/+ x) (mod m))))
  (sub [word x]
    (-> word (b/- x) truncate))
  ...
  (as-biginteger [word]
    word))

...

(defn ->Word [x]
  (cond
    (word?   x) x
    (number? x) (biginteger x)
    (string? x) (BigInteger. 1 (util/hex->bytes x))
    (coll?   x) (BigInteger. 1 (byte-array x))
    :else       (BigInteger. 1 x)))

The b namespace alias refers to sputter.util.biginteger — transparent utilities for manipulating BigIntegers without unwieldy interop.

Example

Notation

In listings, values represented as e.g. <0xfa> are 32 byte words, with leading zeroes omitted. Values of the form <0xfa...fa> are words comprised of 32 identical bytes, with no leading zeroes.

As a reminder of how the VM works, let’s do some simple arithmetic:

(vm/execute
  (state/map->State
    {:program (vm/disassemble "0x60ff60ee01600202")
     :gas     1000}))
;; =>
#:State{:stack '(<0x3da>) ...}

Inlining the stack and removing PUSH instructions, the disassembled program is equivalent to:

ADD <0xee> <0xff>  ;; => <0x1ed>
MUL <0x02> <0x1ed> ;; => <0x3da>

Which is indeed what we see remaining on the stack after the execute call, above!

As we’ll be dealing with operation maps later on, let’s remind ourselves what they look like — the first instruction from the disassembled program, PUSH1 <0xff>:

#:State{
 :program {
   0 #:sputter.op{:variant   1
                  :mnemonic  :sputter.op/push
                  :stack-pop 0
                  :width     2
                  :data      <0xff>}
   ...}
...}

My Memory’s an Ocean

The EVM provides ephemeral, byte-addressed memory for off-stack storage of intermediate values. A selection of the relevant operators:

MSTOREStore a word, starting at the given byte position.
MSTORE8Store a byte at the given byte position.
MLOADLoad a word from the given byte position.
MSIZEPush the size (in bytes) of active memory onto the stack.

MSIZE calculates the number of bytes1 required to hold all previous writes, and service all previous reads without bounds violations — MLOAD may extend the memory (and affect subsequent MSIZE calls) if the read extends beyond the range of previous writes.

In addition to the above, there exist operators which bypass the stack and perform arbitrarily wide memory reads/writes2. As there’s no guarantee these values are constrained by the word size, we’ll benefit from providing a more general, lower-level interface.

1 Rounded up to the nearest word.
2 e.g. RETURN, which we’ll implement, as well as CALL, SHA3.

Interface

(defprotocol VMMemory
  "Ephemeral byte-addressed data store."
  (insert [mem dest-byte byte-vec n]
    "Copy `n` right-most bytes from `byte-vec` to position
     `dest-byte` in `mem`.
     Returns `mem`.")
  (recall [mem from-byte n-bytes]
    "Read `n-bytes` from `mem`, starting at `from-byte`,
     extending if necessary, to avoid bounds violation.
     Returns vector of `[extended-mem byte-vec]`")
  (words [mem]
    "Return the number of words in `mem`"))

When deciding the underlying data structure, the priorities were immutability, straightforward resizing, and intuitive representation — I experimented with a range of eccentric strategies, before settling on byte vectors — for both the memory itself, and the inputs/outputs of insert & recall.

Utility functions — insert-word, insert-byte, recall-word — are implemented trivially in terms of the above protocol.

Example Usage

(let [aa (apply vector-of :byte (repeat word/size 0xaa))
      cc (apply vector-of :byte (repeat word/size 0xcc))]
 (-> (->Memory [])
     (insert 0         aa word/size)
     (insert word/size cc word/size)))

The above ought to give us a memory with the following data, as a contiguous vector — the representation here is idealized:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc

If we were to then insert <0xbb...bb> at position 16:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbcccccccccccccccccccccccccccccccc

Implementation

(ns sputter.state.memory
  (:require [sputter.word            :as word]
            [clojure.core.rrb-vector :as rrb]))

(defn- expand
  "Right-pad `mem` with zeroes until `byte-pos`."
  [mem byte-pos]
  (let [need (- byte-pos (count mem))]
    (cond-> mem
      (pos? need) (rrb/catvec (into (vector-of :byte)
                                (repeat need 0))))))

(extend-type (type (rrb/vector))
  VMMemory
  (insert [mem dest-byte byte-vec n]
    (let [data (rrb/subvec byte-vec (- (count byte-vec) n))
          mem  (expand mem (+ dest-byte n))]
      (-> mem
          (rrb/subvec 0    dest-byte)
          (rrb/catvec data (rrb/subvec mem (+ dest-byte n))))))
  (recall [mem from-byte n-bytes]
    (let [end (+ from-byte n-bytes)
          mem (expand mem end)]
      [mem (rrb/subvec mem from-byte end)]))
  (words [mem]
    (int (Math/ceil (/ (count mem) word/size)))))

(defn ->Memory [x]
  (into (rrb/vector-of :byte) x))

rrb-vector provides logarithmic concatenation and copy-based, logarithmic slicing for vectors.

Operators

As in the previous article, operators are implemented via the sputter.op/operate multimethod, taking a VMState and an op map & dispatching on the latter’s ::mnemonic key, before returning a new VMState.

(ns sputter.op
  (:require [sputter.state.memory :as mem]
            [sputter.util.memory  :as util.mem]
            [sputter.state        :as state]))

...

(defmethod operate ::mstore [state op]
  (let [[pos word] (::popped op)
        insert     (case (::variant op)
                     8   util.mem/insert-byte
                     nil util.mem/insert-word)]
    (insert state pos word)))

The op map’s ::popped key holds any stack entries popped prior to execution, while its optional ::variant key holds any numeric suffix from the operator mnemonic — e.g. 8 for MSTORE8.

You’ll notice that we’re executing these memory functions on our state argument — for convenience, the VMState implementation wraps a discrete VMMemory, and proxies its methods.

Finally, the remainder of the memory operators:

(defmethod operate ::mload [state op]
  (let [[pos]        (::popped op)
        [state word] (util.mem/recall-word state pos)]
    (state/push state word)))

(defmethod operate ::msize [state op]
  (let [n-bytes (* (mem/words state) word/size)]
    (state/push state (word/->Word n-bytes))))

(defmethod operate ::return [state op]
  (let [[state i] (apply mem/recall state (::popped op))]
    (assoc state :sputter/return i)))

RETURN is going to be helpful in verifying the VM — it terminates execution, setting the result to an arbitrarily wide slice of the memory.

Example

Let’s run a program, to get a feel for how this works in real life.

(vm/execute
  (state/map->State
    {:program (vm/disassemble "0x60ff60005260ee601e53601e6002f3")
     :gas     1000}))
;; =>
#:State{:sputter/return [0xee 0xff] ...}

Inlining the stack, the program disassembles to:

MSTORE  <0x00> <0xff>
MSTORE8 <0x1e> <0xee>
RETURN  <0x1e> <0x02>

In the first operation, we store the word <0xff> (31 zero bytes, followed by one 0xff byte) at byte position zero:

00000000000000000000000000000000000000000000000000000000000000ff

We then set the byte behind 0xff to 0xee, using MSTORE8:

000000000000000000000000000000000000000000000000000000000000eeff

Finally, starting at 0x1e (30 — the offset of the 0xee byte) we instruct RETURN to read two bytes, hence the return value of [0xee 0xff].

The Persistence of Memory

Full Ethereum nodes maintain local, persistent, off-chain state in Merkle-Patricia Tries, mapping addresses to account declarations. In addition to bookkeeping data, account declarations encompass any values persisted by previous invocations of the contract.

The EVM’s SSTORE instruction inserts a word at some position in the storage for the contract’s address (i.e. the recipient of the transaction being executed), while SLOAD retrieves a word at some position from same. Storing zero is equivalent to eviction, and retrieval of an unstored entry results in zero. Unlike memory, storage is word addressed, rather than byte addressed.

At this stage in the VM implementation, we don’t have a need for persistent storage, but do want to support SSTORE and SLOAD, in order to interact with the Ethereum VM tests — which use it (as well as RETURN) as a means of verifying transaction results.

Interface

(ns sputter.state.storage)

(defprotocol VMStorage
  "Word-addressed storage, keyed by Ethereum address.
   Zero values and missing values are indistinguishable."
  (retrieve [storage addr pos]
    "Load the word at `pos` from `addr`'s storage.")
  (store [storage addr pos word]
    "Store `word` at `pos` in `addr`'s storage.")
  (stored [storage addr]
    "Return the number of words in `addr`'s storage."))

Stub Implementation

We provide the VMStorage protocol for vanilla maps:

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

(extend-type (type {})
  storage/VMStorage
  (retrieve [m addr pos]
    (get-in m [addr pos] word/zero))
  (store [m addr pos word]
    (if (word/zero? word)
      (update m addr dissoc pos)
      (assoc-in m [addr pos] word)))
  (stored [m addr]
    (count (m addr))))

While not shown here, we proxy VMStorage on our State record, similarly to VMMemory. As well as accepting literal addresses, the State implementation of retrieve & store expands the keyword :recipient into the transaction recipient’s address, before delegating to the functionality above. This gets operators off the hook for tracking details about the invocation when interacting with storage:

(-> (map->State {:message {:recipient <0xabab...ab>}})
    (storage/store :recipient 2 <0xcdcd...cd>))
;; =>
#:State{:storage {<0xabab...ab> {2 <0xcdcd...cd>}}
        :message {:recipient <0xabab...ab>}
        ...}

This Turnpike Sure is Spooky at Night

Each EVM instruction costs zero or more gas (i.e. fuel units), to execute. These costs can be thought of as an abstraction of each operator’s algorithmic complexity and memory utilization. For some of the more complex operators, the cost may be influenced by the values of arguments, or the execution state (e.g. X gas upfront + Y gas for each word-sized memory extension, or similar).

In practice, the cost of a transaction is the product of the consumed gas and the gas price (set by the transaction’s sender), the result of which is to anchor the virtual gas units to some tiny fraction of an ether.


We don’t yet care about the price portion of the calculation — we’re dealing only in virtual gas units.

Implementation

We need to be able to calculate the cost of an operation, track the cumulative cost of a transaction (a sequence of operations), and terminate insufficiently funded transactions.

The implementation was guided by the desire to avoid interleaving an operator’s logic with any consideration of its cost. In the few cases where an operator’s cost is dependent on some understanding of its run-time effects, we accomplish this by interrogating the execution state in the gas calculation.

Calculating Costs

We contain the cost model in a trivial protocol:

(defprotocol GasModel
  (fixed-cost [_ mnemonic]
    "Return the up-front cost of the op named `mnemonic`.")
  (variable-cost [_ op state]
    "Return the cost of executing `op` against `state`.

     Does not include any fixed cost component."))

The implementation makes a distinction between costs which can be determined before considering the arguments or effects of an instruction (fixed), and those which can’t (variable). The sum of both is the total cost of the instruction.

(defrecord EthGasModel [constants by-op]
  GasModel
  (fixed-cost [_ mnemonic]
    (by-op mnemonic))
  (variable-cost [_ op state]
    (op->variable-cost
     (assoc op :sputter/state state)
     constants)))

Both constants and by-op are maps of keywords → integer gas costs. constants contains symbolic keys helpful in variable cost calculations (e.g. {:per-memory-word 3}), while by-op is keyed on operator mnemonics (e.g. {:sputter.op/pop 2 ...}). The op->variable-cost multimethod is a private implementation detail we’ll return to later on.

For convenience, we provide a record which contains the values defined in Ethereum’s formal specification, The Yellow Paper:

(def yellow-paper
  (->EthGasModel gas.yellow/constants gas.yellow/by-op))

Tracking Cumulative Cost

Let’s look at the implementation of VMState‘s only gas-related function, deduct-gas:

(defrecord State [program pointer memory gas ...]
  VMState
  (deduct-gas [state n]
    (if (neg? (- gas n))
      (assoc  state :sputter/error :gas-insufficient)
      (update state :gas - n)))
  ...)

When a transaction is initiated, we construct a State record where the gas argument holds the transaction’s gas limit — the maximum number of virtual gas units we can consume. On each instruction, it’s the VM’s responsibility to query the GasModel from above, and direct the State to deduct the appropriate amount.

Tying It All Together

Let’s revisit the central function, sputter.vm/step, which takes a state, executes the instruction at the pointer, and returns a state pointing to the following instruction, or holding some indication of a termination condition:

(defn step
  [state & [{:keys [gas-model]
             :or   {gas-model gas/yellow-paper}}]]
  (if (terminated? state)
    (assoc state ::terminated? true)
    (let [op     (state/instruction state)
          f-cost (gas/fixed-cost gas-model (::op/mnemonic op))]
      (s/state-> state
        (state/deduct-gas f-cost)
        (operate          op gas-model)))))

state-> is trivial variant of Clojure’s ->, short-circuiting if the state contains a :sputter/error key — operate is only invoked if deduct-gas is successful.

In turn, operate pops the op’s arguments & runs any operator-specific behaviour via the sputter.op/operate multimethod:

(defn- operate [state op gas-model]
  (let [pop-n          (::op/stack-pop op)
        [state popped] (state/pop state pop-n)]
    (if (< (count popped) pop-n)
      (assoc state :sputter/error :stack-underflow)
      (let [op     (assoc op ::op/popped popped)
            v-cost (gas/variable-cost gas-model op state)]
        (s/state-> state
          (state/deduct-gas v-cost)
          (op/operate       op)
          (state/advance    (::op/width op)))))))

gas/variable-cost is obviously invoked with a state representing the environment prior to the execution of the operation we’re costing — that, combined with the work implied by the op map (details of the operator, its consumed stack arguments, etc.) is sufficient to ascertain its cost.

Variable Cost in More Detail

Back in sputter.gas, we elided the body of op->variable-cost, the multimethod invoked by GasModel/variable-cost. Let’s look at what it’s doing:

(defmulti ^:private op->variable-cost
  (fn [op constants] (::op/mnemonic op)))

(defmethod op->variable-cost :default [_ _] 0)

We may as well jump right in to the behaviour for costing memory operations. As hinted at in the memory section, there’s no difference between the variable cost component for memory reads vs. writes — we can use the same calculation for both:

(defn- mem-op->byte-width [op]
  (case (::op/mnemonic op)
    ::op/return (second (::op/popped op))
    ::op/mstore (if-let [variant (::op/variant op)]
                  (/ variant 8)
                  word/size)
    word/size)))

(defn- mem-fee
  "Fee for storing `words` with the given `per-word` cost."
  [words per-word]
  (-> words (* words) (quot (* word/size 16)) (+ (* words per-word))))

(derive ::op/mstore ::mem-extend)
(derive ::op/mload  ::mem-extend)
(derive ::op/return ::mem-extend)

(defmethod op->variable-cost ::mem-extend [op constants]
  (let [width      (mem-op->byte-width op)
        [addr]     (::op/popped op)
        prev-words (-> op :sputter/state mem/words)
        curr-words (int (Math/ceil (/ (+ addr width) word/size)))]
    (max 0 (- (mem-fee curr-words (:per-memory-word constants))
              (mem-fee prev-words (:per-memory-word constants))))))

mem-op->byte-width determines the extent of a read or write — in the event we’re calculating the cost of RETURN, it’s the second stack value (width in bytes). For MLOAD and vanilla MSTORE, the result is 32 (the word size). MSTORE8 has a byte width of 1.

mem-fee implements the scaling behaviour described in an uncharacteristically helpful section of the Yellow Paper.

The op->variable-cost method figures out the fee difference between the number of words contained in the state’s memory prior to executing op, and the number of words which will exist after (curr-words).

I Can’t Do My Homework Anymore

Let’s wrap up with an attempt to test some of the new functionality.

To aid authors in verifing their implementations, Ethereum provides an infernal suite of VM tests: JSON documents describing inputs, code and outputs, grouped by operator.

sputter.test.util supports reading JSON test specs from the filesystem, translating them into VMStates, and comparing the results of their evaluation with expectations, e.g.:

(ns sputter.test.util
  ...)

(defn- test->State [t]
  (let [exec (:exec t)]
    (state/map->State
     {:program (vm/disassemble (:code exec))
      :gas     (hex->biginteger (:gas exec))
      :message {:recipient (word/->Word (:address exec))}
      :storage (map->Storage (:pre t))})))

...

(defn- run-vm-test [test-name test]
  (let [state (test->State test)
        post  (vm/execute state)]
    (assert-error   test-name test post)
    (assert-gas     test-name (:gas test) post)
    (assert-storage test-name (map->Storage (:post test)) post)
    (assert-return  test-name (:out test) post)))

...

sputter.vm-test groups these by operation, e.g.:

(ns sputter.vm-test
  (:require [clojure.test :refer [deftest]]
            [sputter.test.util :as test.util]))

(deftest add
  (test.util/run-vm-tests #"^add\d+$"))

(deftest addmod
  (test.util/run-vm-tests #"^addmod[^_]+$"))

...

Where each runs any number of individual VM tests, matched by filename. We’re doing pretty well so far:

$ lein test
...
Ran 17 tests containing 756 assertions.
0 failures, 0 errors.

Closing Time

In the next instalment, we will likely look at contract delegation via CALL, and refactoring the implementation so code can be retrieved by address.

Github: nervous-systems/sputter.