Optimising the Ethereum Virtual Machine

The Ethereum Virtual Machine (EVM) is a simple but powerful, Turing complete 256bit Virtual Machine that allows anyone to execute arbitrary EVM Byte Code. The EVM is part of the Ethereum Protocol and plays a crucial role in the consensus engine of the Ethereum system. It allows anyone to execute arbitrary code in a trust-less environment in which the outcome of an execution can be guaranteed and is fully deterministic. Executing code within the Ethereum network takes time, and execution is generally pretty slow compared to other VMs. For every instruction, there’s a cost associated, and an internal counter keeps track of the total cost, which is charged to the user. When a user initiates an execution through a transaction, they reserve some cash, which is the maximum amount they’re willing to pay.

When a transaction has been broadcasted to the network validators may take the transaction and apply it to their current state, executing the associated code. The validator will make sure that:

1. The transaction is valid (e.g. encoding, sender signature, etc.);
2. The sender has enough funds to pay for the execution;
3. The EVM didn’t throw any exceptions during the execution.

The internal unit for keeping track of execution cost is called Gas and is the Ethereum network’s cost unit, paid exclusively with Ether— Ethereum’s own crypto-currency. The Gas mechanism solves two major issues:

1. A validator is guaranteed to receive a maximum of the initial pre-paid amount, even if the execution fails;
2. Sidestep the halting problem, i.e. an execution can not run longer than the pre-paid amount would allow. Instead of looping indefinitely the execution would exhaust the available resources that it has at its disposal.

One the characteristics of the EVM is that, unlike most VMs, it operates on 256bit integers and requires 256bit arithmetic. Because of the 256bit nature of the EVM the gas can theoretically be 2²⁵⁶-1 but actually never will because the amount of computation required and the cost incurred by such an execution would be too much for anyone to pay. Instead of using 2²⁵⁶ we can use 2⁶⁴, which modern day CPUs have native support for and can generally be optimised by the compiler (unlike unlimited size big integers) and even though 2⁶⁴ is still in the upper ranges of “too costy” it’s a very nice constraint to have and allows us to hardcap the gas on something the computer can “natively” understand.

The go-ethereum repository implements — among the Ethereum client and tool suite — the Ethereum Protocol in the Go language. It contains two implementation of the EVM, one extremely simple byte code interpreter that simple loops over the byte code and a JIT-like interpreter that compiles the byte code in to manageable data types and structures. The JIT implementation has received a full gas-to-64-bit overhaul and seen some very impressive improvements:

benchmark                      old ns/op     new ns/op    delta
BenchmarkVmAckermann32Tests-4  5797850       1767258      -69.52%
BenchmarkVmFibonacci16Tests-4  35884955      10848056     -69.77%

To compare the result of the overal performance gained by the JIT-EVM I’ve also compared them to the byte-code EVM:

benchmark                      old ns/op     new ns/op    delta
BenchmarkVmAckermann32Tests-4  7431330       1767258      -76.22%
BenchmarkVmFibonacci16Tests-4  45639966      10848056     -76.23%

Among the many changes in the JIT and conversions from *big.Int to uint64, I fixed one of the bottlenecks in particular. During the execution of the program each instruction would perform the necessary steps to calculate the gas and memory consumption required. For instruction we perform the following operation:

if gas.Cmp(amount) < 0 {
     return OutOfGasErr
}
gas.Sub(gas, amount)

At first glance this operation seems pretty harmless but upon further inspection I concluded that most of the time is spent here, calculating whether the operation would succeed or not.

Another optimisation I did was changing how the gas is calculated when growing memory. For each word (32 bytes), there’s a cost associated for the expansion of the memory. The EVM uses a Quadratic-memory gas calculation formula:

(memSizeWords ^ 2) / QuadCoefficient + (MemWords * MemGas)

Like the gas-counter, this was also using big integer arithmetic, and since we’ve already capped the gas counter, the memory fee associated with the expansion could never go beyond 2⁶⁴-1.

Next steps

Converting many of the big integer arithmetic to uint64 has gained us a tremendous amount of performance, but I don’t think we should stop there. Next I’d like to do further research in to Symbolic Execution and whether it makes sense to do something similar in our EVM.

If you’d like to track progress on my optimisations please see PR #2572 on the go-ethereum repository.