What does Turing-complete mean?
Turing-complete computers can do all the same things any other computer can do. The Commodore 64 is as Turing-complete as this year’s Mac Pro, because even though it has only 64 bytes of RAM, it could perform all the same operations as the Mac if it were given enough time, and if it were fed them the right way. (This doesn’t mean the C64 could run Photoshop 22.0, just very slowly; but if the operations that make up that program were broken up and fed into the C64 in such a way that it could handle them, it could eventually perform them all.)
This Turing-completeness (named for British mathematician and cryptography legend Alan Turing) is what distinguishes “general-purpose computers” from machines that can only perform specific tasks.
General-purpose computing on the blockchain
“Turing-complete” is a less-valuable differentiator now than it used to be, because general-purpose computers are everywhere now; inside most single-purpose devices is a small but Turing-complete computer.
That’s how people run Doom on a smart fridge, or a calculator; inside these devices is a general-purpose computer, and if you can figure out how to communicate with it it will do whatever you tell it. The most interesting version of this tendency is the man who built a Turing-complete computer inside Minecraft, then used it to run Minecraft.
That should be familiar to anyone who’s ever used a virtual machine to run Windows on a Mac or Linux computer; you’re creating a computer whose parts are being virtualized by another computer.
A blockchain-based virtual machine
In a way, that’s what’s happening on the EVM: on nodes across the world, Ethereum is running as a program. Inside that program, using Solidity and building out one block at a time, the Ethereum Virtual Machine performs operations that users request of it.
Unlike a traditional distributed computing network — like the internet, or like the network of Google servers which I used to write and research this post — the Ethereum Virtual Machine consists of nodes on a blockchain, and that imposes costs and restrictions.
Nodes and bottlenecks
Imagine each node in the network like an old-fashioned bank clerk totting up numbers. In a traditional network, each clerk works on a different account, then hands in their work. Their supervisor checks they’re correct (in theory!) and they’re done for the day.
In a blockchain, or a blockchain-based computer like the EVM, things work a little differently. Each clerk checks all the figures for the whole bank; each node does all the calculations on the EVM. Then, the clerks get together at the end of the day and compare figures; only ledgers that are all identical and all the clerks agree on goes into the bank’s ledger, and the clerks are done for the day. On Ethereum, a new block is minted. (This is a simplification that ignores the mining process, but hopefully clarifies the process of blockchain computation.)
Gas and consensus
Now, general-purpose blockchains are more common, though none has Ethereum’s influence or user numbers. But when Ethereum was created, the idea was groundbreaking. However, Ethereum isn’t truly a “blockchain computer” — it’s only “quasi-Turing complete”, remember. There are certain types of operations the EVM can’t do.
That’s because of the “gas” system in Ethereum. Gas is the internal costing system Etheruem came up with to deal with the fact that computational power is limited on the EVM by the fact that it’s a blockchain. Other than this, though, the EVM is Turing-complete, and it will be fully Turing-complete after it transitions over to Proof-of-Stake consensus with Eth 2.0.
Under the hood
The EVM consists of 140 unique instructional codes for operations, called “opcodes”. Opcodes are limited because each consumes 1 byte of computational power, so there can only be 256 (162).
Opcodes can be categorized as:
- Stack-manipulating opcodes (POP, PUSH, DUP, SWAP)
- Arithmetic/comparison/bitwise opcodes (ADD, SUB, GT, LT, AND, OR)
- Environmental opcodes (CALLER, CALLVALUE, NUMBER)
- Memory-manipulating opcodes (MLOAD, MSTORE, MSTORE8, MSIZE)
- Storage-manipulating opcodes (SLOAD, SSTORE)
- Program counter related opcodes (JUMP, JUMPI, PC, JUMPDEST)
- Halting opcodes (STOP, RETURN, REVERT, INVALID, SELFDESTRUCT)
Each opcode is encoded to bytecode and comes with its own gas fee schedule, which is how base gas fees for smart contracts are calculated; creating a “floor” fee for individual units of computation, or “words” (single-byte opcode elements) makes sure bad actors can’t flood the Ethereum blockchain with enormously-complex smart contracts and slow down the network. The spreadsheet showing gas prices for opcodes is here.
EVM in action
The EVM works by taking instructions from cryptographically-signed accounts, and carrying out transactions.
Accounts
There are two types of accounts in Ethereum: external and contract.
External accounts are the accounts of Ethereum users. They’re controlled by public-private key pairs and their address comes from the public key.
Contract accounts are controlled by code stored as part of a smart contract. Their address comes from the creator’s address and amount of their transactions.
Every account has an Ether balance, and any transaction that contains Ether will change that balance. The EVM treats both types of accounts the same.
Transactions
There are two types of transactions: those which result in message calls, and those that result in contract creation.
Message calls can also be thought of as local transactions; only one node is involved and they don’t change states on the network. Code is processed but Eth does not change hands.
Contract creation transactions can also be thought of as state-changing transactions. They use send.transaction and are delayed by the requirement for mining to mint a new block.
The future of the EVM
The EVM might have a limited future. Ethereum is planning to migrate from its current incarnation through a process of sharding and side-chain use, until it moves over to Eth 2.0 (more detail on that process here).
As that process goes on, the Ethereum Virtual Machine will be replaced by Ewasm — the Ethereum Web Assembly. Wasm is built for the web by a consortium of developers from companies including Apple Mozilla, Microsoft and Google. Unlike the EVM, which emphasizes correctness, Ewasm, which is being built as a separate instance of Wasm, is designed to be as quick, efficient and portable.
This will lead eventually to a much faster, more efficient Ethereum — but one that no longer uses the Virtual Machine.