The Faults and Shortcomings of the EVM

So, first to give an introduction. I co-founded Qtum which is a project that basically takes the Ethereum Virtual Machine (EVM) and puts it onto a blockchain that isn't Ethereum (along with a ton of other stuff). On my way to doing that I was forced against my will to learn way more than I ever wanted to know about the EVM. What is my main take away from all this learning? Well, I don't like it. I personally think it's an impractical design with an even more impractical implementation. And as a disclaimer, I intend to see through that we add another VM to Qtum which fixes at least most of these problems.

Anyway, so lets cut to the chase. What was the point of the EVM and why was it made in the first place? According to the Design Rationale it was designed for:

  1. Simplicity
  2. Determinism
  3. Compact bytecode size
  4. Specialization for blockchain
  5. Simplicity (uhh?)
  6. Optimizable

And if you skim through that document, you see the reasoning for the EVM is pretty well thought out. So where does it go wrong? Well, it doesn't work with today's technology and paradigms. It's a very good design built for a world that doesn't currently exist. I'll circle back around to this, but lets start with my favorite thing to hate in the EVM

256 bit integers

On most modern processors you have pretty much 4 good choices for fast speedy math:

  1. 8 bit integers
  2. 16 bit integers
  3. 32 bit integers
  4. 64 bit integers

Of course, in some cases 32 bit is faster than 16 bit, and at least in x86 8 bit math is not fully supported (ie, no native division or multiplication), but for the most part if you use one of these sizes you have some guarantees of how many cycles a math operation takes, and it's fast, measured in a couple of nanoseconds if you don't include cache misses and memory latency. Anyway, suffice to say that these are the size of integers that modern processor use "natively", without any translation or other things requiring extraneous operations.

So of course, since the EVM is intended to be optimized for speed and efficiency, it's choice for integer size is:

  1. 256 bit integers

For reference, here's how to add 2 32 bit integers in x86 assembly (ie, the processor your PC has in it)

mov eax, dword [number1]
add eax, dword [number2]

And here's how to add 2 64 bit integers in x86 assembly assuming your processor is 64 bit capable:

mov rax, qword [number1]
add rax, qword [number2]

And here is how to add 2 256 bit integers on a 32 bit x86 computer

mov eax, dword [number]
add dword [number2], eax
mov eax, dword [number1+4]
adc dword [number2+4], eax
mov eax, dword [number1+8]
adc dword [number2+8], eax
mov eax, dword [number1+12]
adc dword [number2+12], eax
mov eax, dword [number1+16]
adc dword [number2+16], eax
mov eax, dword [number1+20]
adc dword [number2+20], eax
mov eax, dword [number1+24]
adc dword [number2+24], eax
mov eax, dword [number1+28]
adc dword [number2+28], eax

Although, adding these 256 bit integers on a 64 bit x86 computer is a bit better

mov rax, qword [number]
add qword [number2], rax
mov rax, qword [number1+8]
adc qword [number2+8], rax
mov rax, qword [number1+16]
adc qword [number2+16], rax
mov rax, qword [number1+24]
adc qword [number2+24], rax

Anyway, suffice to say that working with 256 bit integers is significantly more complex and slow than working with an integer length natively supported by the processor.

The EVM embraces this design though because it is much simpler to only support 256 bit integers, than to add additional opcodes for working with other integer sizes. The only non-256 bit operations are a series of push instructions for pulling data from 1-32 bytes from memory, and a few instructions that work with 8 bit integers.

So, the design rationale for using this inefficient integer size for all operations?

"4 or 8 byte words are too restrictive to store addresses and big values for crypto computations, and unlimited values are too hard to make a secure gas model around."

I must admit, being able to compare 2 addresses with a single operation is pretty cool. However, here is how you would do the same in x86 when in 32-bit mode (without SSE and other optimizations):

mov esi, [address1]
mov edi, [address2]
mov ecx, 32 / 4
repe cmpsd 
jne not_equal
; if reach here, then they're equal

Assuming address1 and address2 are hardcoded addresses, that's around 6 + 5 + 5 = 16 bytes of opcodes, or if the addresses were in the stack, it might be something like 6 + 3 + 3 = 12 bytes of opcodes.

The other justification for the large integer size is "big values for cryptography computations", however, since reading that several months ago I've had a problem figuring out a single use case for 256 bit integers that doesn't involve comparing if an address or hash is equal. Custom cryptography is plainly too expensive to execute on the public blockchain. I searched for over an hour on github trying to find a solidity contract that does anything I'd define as cryptography and I came up with nothing. Almost any form of cryptography is guaranteed to be slow and complex on modern computers, and this makes it non-economical to execute on the public Ethereum blockchain due to gas costs (not to mention the effort of porting any real algorithm to Solidity). However, there are still private blockchains where gas costs do not matter. But if you own your own blockchain you won't want to do this as part of a slow EVM contract, you would use C++, or Go, or any number of real programming languages to implement the cryptography in native code as a pre-compiled smart contract. So this really blows the entire justification for supporting only 256 bit integers out of the water. This I feel is the real foundation of problems with the EVM, but there's a lot more lurking in the less obvious areas.

EVM's Memory Model

The EVM has 3 main places you can put data

  1. Stack
  2. Temporary memory
  3. Permanent memory

The stack has certain limits, so sometimes you need to use temporary memory instead of very expensive permanent memory. There is no allocate instruction or anything like that in the EVM. You claim memory by writing to it. This may seem pretty clever, but it's also extremely sinister. For instance, if you write to address 0x10000, your contract just allocated 64Kwords (ie, 64K of 256 bit words) of memory and paid the gas costs as if you had used all 64Kwords of memory. Well, easy workaround, just track the last memory address you use and increment it when you need more. That works decently, unless you happen to need at one point a lot of memory and then you don't need that memory anymore. Let's say you do some crazy algorithm that uses 100 words of memory. So, you allocate that, use the memory, whatever and pay for 100 words of memory... then you exit that function. Now you're back in some other function and it needs just 1 word of memory for scratch space or something, so it allocates another word. You're now using 101 words of memory. There is no way to free memory. You can in theory decrease that special pointer you were keeping track of for the last space of memory, but that only works if you know that entire block of memory will never be referenced again and can safely be reused. If out of those 100 words, you need the word at 50 and the word at 90, then you must copy those to another location (like the stack) and then that memory can be freed. There is no tools provided by the EVM to help with this. The technical term for it is memory fragmentation. It is up to you to vet that each function doesn't use that memory that was allocated and globally accessible, and if you reuse that memory and something got through your vetting process, then your contract now has a potentially critical state corruption bug. So your options are basically either open yourself up to a large class of memory reuse bugs, or pay more gas for memory even though you have already allocated more than you need.

Additionally, allocating memory does not have a linear cost. If you have allocated 100 words of memory and you allocate 1 more word, it is significantly more expensive than allocating that 1st word of memory when your program starts. This aspect greatly amplifies the economic cost of being on the safe side, compared to opening yourself up to more contract bugs for greatly decreased gas costs.

So, why use memory at all? Why not use the stack? Well, the stack is ridiculously limited.

EVM's Stack

The EVM is a stack-based machine. That means it uses a stack for most of it's operations, rather than a set of registers. Stack based machines are typically much simpler to optimize, but result in more opcodes being needed for most operations when compared to a similar register based machine.

Anyway, so the EVM has a lot of different operations, most of which operate on the stack alone. Notice the SWAP and DUP series of instructions. These go up to 16. Now try to compile this contract:

pragma solidity ^0.4.13;

contract Something{

    function foo(address a1, address a2, address a3, address a4, address a5, address a6){
        address a7;
        address a8;
        address a9;
        address a10;
        address a11;
        address a12;
        address a13;
        address a14;
        address a15;
        address a16;
        address a17;
    }
}

You'll be met with this error:

CompilerError: Stack too deep, try removing local variables.

This error occurs because once an item is 16 levels deep in the stack, it is effectively impossible to access without popping items off the stack. The official "solution" for this problem is to use less variables and make functions smaller. Various workarounds also include stuffing variables into a struct or array and using the memory keyword (which isn't able to be applied to normal variables for... reasons?). So, lets fix our contract to use some memory based structs:

pragma solidity ^0.4.13;

contract Something{
    struct meh{
        address x;
    }
    function foo(address a1, address a2, address a3, address a4, address a5, address a6){
        address a7;
        address a8;
        address a9;
        address a10;
        address a11;
        address a12;
        address a13;
        meh memory a14;
        meh memory a15;
        meh memory a16;
        meh memory a17;
    }
}

And the result is..

CompilerError: Stack too deep, try removing local variables.

But we replaced these variables with memory? Doesn't that fix it? Well, no. Because now instead of storing 17 256 bit integers on the stack, we are storing 13 integers and 4 256 bit memory addresses (ie, references) to a 256 bit slot of memory. Part of this is a Solidity problem, but the primary problem is that the EVM is missing a way to access arbitrary items on the stack. Every other VM implementation I know of works around this basic problem by either

  1. Encouraging small stack sizes and making it easy to swap stack items to memory or alternative storage (like local variables, in .NET)
  2. Implementing a pick instruction or similar that allows access to any arbitrary stack slot

However, in the EVM, the stack is the only free place of memory for data and computation, any other place has a direct cost in the form of gas. So, this directly discourages small stack sizes, because anywhere else is more expensive... so we arrive at basic language implementation problems like this.

Bytecode size

In the rationale document it's stated their goal was for EVM bytecode to be both simple and compact. However, this is like saying that you prefer to write code that is both descriptive and concise. They are fundamentally differing goals accomplished in fundamentally different ways. A simple instruction set is accomplished by limiting the number of operations, and keeping operations concise and simplistic. Meanwhile, a compact bytecode that produces small programs is accomplished by making an instruction set that performs as many operations as possible in as few bytes of code as possible.

Ultimately, despite "compact bytecode size" being a goal in their rationale, the actual implementation of the EVM does not attain that goal in any sense. It is instead focused on a simplistic instruction set that is easy to create a gas model around. And I'm not saying this is wrong or bad, only that one of their primary goals of the EVM is fundamentally at ends with the other goals of the EVM. Also, one number given in that document is that a C program takes over 4000 bytes in order to implement "hello world". This is definitely not the case and glosses over the different environments and optimizations that take place in C programs. In the C program they measured, I expect there was also ELF data, relocation data, and alignment optimizations - aligning code and data on certain boundaries such as 32 byte or 4kb can have a measurable impact on the performance of the program on physical processors. I personally have built a simplistic bare bones C program that compiles to 46 bytes of x86 machine code, and a simple greeter type program which compiles to ~700 bytes, while Solidity's example compiles to over 1000 bytes of EVM bytecode.

I understand the need for a simplistic instruction set for security reasons, but it causes significant bloat on the blockchain. Passing over this as if EVM smart contract bytecode is as small as possible is detrimental. It could clearly be made much smaller by including a standard library and supporting opcodes that do a batch of common operations rather than needing to execute several opcodes for such a thing.

256 bit integers (again)

But really, 256 bit integers are awful. And the most ridiculous part is they are used in places where they have no reasonable use. It's effectively impossible to use more than 4B (32 bits) units of gas, so what integer size is used for specifying and counting gas? 256 bits of course. Memory is fairly expensive, so what's the address size for memory addresses in the EVM? 256 bit of course, for when your contract needs more words of memory than there are atoms in the universe. I would complain about using 256 bit integers for both addresses and values in permanent storage, but this actually provides some interesting abilities to use a hash for some data and have no worries about conflicts in the address space, so I guess that gets a pass. Every single instance where you could use any integer size, the EVM calls for 256 bits. Even JUMP uses 256bit, but in their defense they do limit the highest jump destination to 0x7FFFFFFFFFFFFFFF and effectively limit the jump destination to a signed 64 bit integer. And then for currency values themselves. The smallest unit of ETH is wei, so we arrive at the total coin supply (in wei) is 1000000000000000000 * 200000000 (200M is an estimate, currently the supply is ~92M).. And so, if we subtract that number from 2 to the power of 256 (maximum value storable by a 256 bit integer), we get.. 1.157920892373162e+77. Just enough space to send more wei than will ever exist plus a magnitude greater than the number of atoms in the universe. Basically, 256 bit integers are incredibly impractical and unnecessary for almost any application that the EVM is designed for.

Lack of standard library

If you've ever developed a Solidity smart contract, this is probably one of the first things you encountered as a problem. There is no standard library, at all. If you want to determine if two strings are equal, there is no strcmp or memcmp or anything like that, you must write the code yourself or copy code from the internet. The Zepplin Project is making this situation bearable by providing a standard library that contracts can use (either by including it in the contract itself or by calling an external contract). However, the limitations of this approach is apparent when considering that it is cheaper to use two SHA3 operations and then compare the resulting hashes, than it is to loop through the bytes of a string (32 bytes at a time) to determine if they are equal. Having a standard library of precompiled contracts that use native code with set, reasonable gas prices would be greatly beneficial to the entire smart contract ecosystem. Without this though, people instead copy and paste code from open source code, with unknown security implications. In addition to this people will optimize their code, trying to find shortcuts and reductions in gas usage, even at the risk of potentially compromising the security profile of their contract.

The economics and game theory of gas

I plan on making a full blog post about this topic, but the EVM doesn't just make good practices hard, but also expensive. For instance, it costs quite a bit of gas to store data on the blockchain. This means it can be incredibly expensive to cache any amount of data within a smart contract. So, instead it is computed with each contract execution. Over time more gas is consumed and blockchain nodes waste more time executing the same code to compute the same data. Furthermore, there is very little actual cost to data stored on the blockchain. It does not directly increase the size of the blockchain (in either Ethereum or Qtum). The real cost is the data which enters the blockchain in the form of data sent to contracts, as that is what directly increases the size of the blockchain. It is almost cheaper in Etheruem to enter 32 bytes of data into the blockchain in the form of a transaction (23176 gas) than it costs to store 32 bytes in a contract (20,000), and it is significantly cheaper when scaling that 64 bytes of data (29704 gas for tx compared to 80,000 gas for storage). There is a "virtual" cost to data stored in a contract, but it is much less than most people assume. It is basically just the cost of iterating through the database storing data for the entire blockchain. The RLP and LevelDB database system used by both Qtum and Ethereum is very efficient at handling this however, and ongoing costs are no where close to linear.

Another part of the EVM that encourages inefficient code is that it is not possible to call a specific function in a smart contract. This is for security, as being able to directly call a function like withdraw() in an ERC20 contract would be bad. However, this is needed for standard libraries to be efficient. Instead of simply being able to load a specific piece of code from an external contract, it's all or nothing, and execution always starts at the first byte of the code, there is no way to jump around and skip all of the Solidity ABI bootstrap code. So, in the end this encourages for small functions to be duplicated (because they are more expensive to call externally), and to deploy as many functions in a contract as possible. There is no cost difference for calling a 100 byte contract or a 10,000 byte contract, despite all of the code needing to be loaded into memory either way.

And finally, it is not at all possible to access the storage of a contract directly. The contract code must be fully loaded from disk, executed, the code must load the data from the storage that you requested, and then finally return it to the calling contract while making sure not to use variable size arrays. Oh, and if you need some back and forth because you didn't know the exact data you needed, at least it's in cache so it's cheap for nodes, but there is no discount on the gas price for calling the external contract a second time. It's possible to access an external contract's storage without needing to completely load its code. In fact, it's just as cheap computationally as accessing the current contract's storage, so why make it so expensive and discourage efficiency?

Lack of debugging and testability

This problem lies not just on the fault of the EVM's design, but also its implementations. Of course, some projects are striving to make this as easy as possible, like Truffle. However, the EVM's design does not make this at all easy. The only exception available is "OutOfGas", there are no logging facilities, no easy way to call external native code (such as for test helpers and mocking data), and the Ethereum blockchain itself is difficult to create a private testnet with, and the private blockchain has different parameters and behavior. Qtum at least has a leg up here thanks to "regtest" mode, but testing the EVM with mock data etc is still incredibly hard since no implementation is really stand-alone. And there are no debuggers I know of that work at Solidity level, there are at least 1 EVM assembly debuggers I know of though, but that is far from user friendly. There is no symbol format or debug data format established at all for EVM and/or Solidity, and I've found no EIPs or other effort to begin working toward a standardized debug format like DWARF.

Floating point numbers

One common thing I see people say when the lack of floating point support comes up is "well no one should be handling currency values using floating point numbers". This is incredibly narrow-minded though. There are many practical use cases for floating point numbers such as risk modeling, scientific computations, and cases where ranges and approximations are more important than exact values. Saying the potential applications of smart contracts to only handling currency values is unrealistic and needlessly limiting.

Immutable code

One of the major things that contracts need to be designed for is upgradeability, because it's not a matter of if a contract needs changed, but rather when. In the EVM code is completely immutable, and because it uses the Harvard Architecture of computing, it is not possible to load code into memory and then execute it. Code and data are completely separate things treated differently. So, the only option for upgrading a contract is to deploy a completely new contract, duplicating all of the code and make the old contract redirect to it. Patching pieces of the contract and partially (or wholly) replacing the code is not possible.

Conclusion

I finished my beer (well, hard cider) and I think my rant is coming to an end. The EVM at this point is a necessary evil. It was the first in this space, and like most things that come first (like Javascript), there are many problems. And it's design is very unconventional, and is why I don't think we will see any conventional programming languages ported to the EVM. It's design is actively hostile to the many common language paradigms that have been established over the past 50+ years. This includes things like JUMPDEST making jump table optimizations difficult, no tail-recursion support, strange and inflexible memory model, difficult to understand DELEGATECALL model for external code, lack of commonly used opcodes such as bitwise shifts, inflexible stack size limits, and of course the 256 bit integers. These aspects make porting traditional languages to the EVM at best inefficient and at worst impossible. This I assume is why all EVM languages currently are built specifically for the EVM and with all of it's unconventional models in mind. It is a sad state of affairs really.

I mean this entire post not as an assault or anything to the designers of the EVM, it's just how things are. Hindsight is always 20/20 and I know I've seen many regrets from them about certain aspects of the EVM's design. I don't wish to attack them (even if my sarcastic tone might seem like it sometimes), but rather I want to bring these faults to the attention of the greater blockchain developer community, so that they will not be repeated, and hopefully also provide some insight into all of the "why can't I do this in Solidity" type questions at the same time. The EVM has an incredible design that we are still learning the benefits and pitfalls of, and it's obvious that we have a long way to go before smart contracts can be as efficient and powerful as we all know they can be. The EVM was the first contender in this space, and ultimately we're still learning and discovering all of the use cases of smart contracts and what kind of design benefits them most. We've come a long way, but there's still a long way to go.

Posted: 8/13/2017 4:51:44 AM

Comments

Posting comments is currently disabled(probably due to spam)