Ethereum Virtual Machine

The following article is a technical dive into the backbone of Ethereum, the EVM. The primary reference for this article is the Ethereum Yellow Paper and StackOverflow.

States

The Ethereum network is not just distributed ledger (a bookeeping like system and Bitcoin is the best example of this) but a distributed state machine. All a state machine really means (at a high level) is a program that transitions between various “states” where transitions are caused by actions (inputs and outputs) from one state to another (in the case of Ethereum: transactions). A “state” can be thought of as a snapshot of the entire system and all of it’s settings at one point. You cannot modify a “state” no deviation is allowed. Thus the “state” of Ethereum is composed of all of it’s accounts and their respective balances and the status of the blockchain.

Modified Merkle Patricia Tree

Patricia Trie

The data mangement system of Ethereum is the Modified Merkle Patricia Tree. A trie is an ordered tree data structure where a node’s position in the trie defines the key with which it is associated. A Patricia trie is a trie where each node in the trie has a parent node and two child nodes (there is a binary choice at each node). A Patricia trie also has a key value pairing where the key is the path so the nodes that share the key prefix are in the same path.

In the below diagram you can see the five nodes and how they are stored in the tree and how a search for the node “toasting” would play out. The key balue below are the values in between the nodes.

Credit StackOverflow

Merkle Trie

Merkle trie is a binary tree of hashes where the leaf nodes store data. The lowest child nodes contain hashes of the data. Parent nodes store the child nodes hashes and the hashed value of the sum of the child hashes. Merkles trees allow for Merkle proofs. A Merkle proof to see if a node is valid in the tree can be demonstrated as such:

1. Take the hash of the node in the tree using a one way hash function.
2. Recalculate the hash of the parent node.
3. Apply this process until the root node is reached.
4. Check if that root hash is the same.

Likewise, when checking if two tries are identical, just by checking if the root hash is the same is sufficient.

Credit Wikipedia

Modified Merkle Patricia Trie

The Modified Merkle Patricia Trie is simply a tree structure built on the above where the Merkle tree structure is retained (cryptographically immutable) and the hash is also used as the key that refers to the node. There are three types of nodes to the MMPT (extension, branch and leaf). More detailed explanation can be found in the yellow paper.

State Trie Architecture

In Ethereum’s case, the key value mapping for the state trie, transactions trie and receipts trie are all stored using the Modified Merkle Patricia Tree. Thus the root hash in these tries can be thought of as a condensed snapshot of the state of the system. Any change downstream in the trees will modify the root hash and invalidate the block.

Reference StackOverflow

World State Trie

The world state trie is a mapping between all the addresses and their account states. It is a global state that is constantly updated by transaction executions. The leaf node in the world state trie contains the account storage trie (linked via the storageRoot which points to the root node in the acount storage trie). The account storage trie stores information about accounts and has the four fields: nonce, balance, storageRoot, and codeHash. The root of the world state is the stateRoot and is stored in every block.

Transaction Trie

The transaction trie contains the transactions in Ethereum. The root of the world state is the transactionsRoot and is stored in every block.

Receipt Trie

The receipt trie records the outcome of successful transactions. The root of the world state is the receiptsRoot and is stored in every block.

Execution

The rules to change the Ethereum system between states is managed by the Ethereum Virtual Machine (EVM). The EVM is a Turing complete virtual machine intrinsically bound by execution costs (gas). The EVM is a layer that sits between the executing code and the executing machine.

Programs on Ethereum are written in a higher level language (Solidity) which is then compiled into opcodes which are a set of simple instructions to execute a specific task. Opcodes range from:

• Arithmetic and comparisons such as ADD, SUB AND, OR
• Memory-manipulating such as MLOAD, MSTORE
• Storage-manipulating such as SLOAD, SSTORE
• Program counter related such as JUMP
• Halting such as STOP, RETURN, INVALID

and others. The opcodes are encoded to bytecode that the EVM utilises for execution.

At the start of execution the memory is empty and the program counter is zero. The EVM then executes the transaction computing the system state (the World state) and the machine state for each loop. On each cycle, machine state is updated with the appropriate gas amount reduced from the remaining gas, and the program counter updated.

At the end of each loop, there are three outcomes:

1. The machine reaches an exceptional state (for example insufficient gas, invalid instructions) and so is halted with any computations so far not counted.
2. The machine reaches a controlled halt (the end of the execution process). The remaining gas after this execution is returnned and the resultant output.
3. The sequence continues.