Patents Wiki
Back to briefings
PaperBlockchain

The state machine that promised to replace every other one

Satoshi Nakamoto solved two problems in one paper. The first was obvious to anyone who read the financial press: a peer-to-peer digital cash system that no government could shut down. The second was quieter, stranger, and arguably more durable. He had built a working model of decentralized consensus, a way for thousands of strangers who had never met to agree, with high probability and no central authority, on a single ordered history of events. Most of the people working on the technical frontier of cryptocurrency have begun to suspect that the consensus engine is the more interesting artifact. The currency is what pays the bill for running it.

For two years after the Bitcoin genesis block in January 2009, that engine was a one-trick pony. You could embed a small set of arithmetic and signature checks in a transaction script, but you could not, in any general way, write code that ran across the network. As applications started to multiply around Bitcoin, they hit the same wall over and over. Colored coins, name registries, derivative contracts, prediction markets, decentralized exchanges: each one had to either fork the chain, bolt a meta-protocol on top of Bitcoin, or build something out of reach of the limited scripting primitives that Bitcoin's design tolerated.

In late November 2013, a 19-year-old writer and programmer named Vitalik Buterin proposed a different answer. The cleanest path forward, he argued, was to drop the fiction that a blockchain had to be a ledger for one specific kind of asset. A blockchain is a deterministic state machine that everyone in the network agrees to step forward one tick at a time. If the state is a general purpose object, the consensus engine is a general purpose computer. The paper that landed that month, under the modest title Ethereum: A Next-Generation Smart Contract and Decentralized Application Platform, sketched out a system that would expose the state machine itself as a programmable surface. The canonical PDF on the official mirror is dated 2014, and the formal specification that followed, the "Yellow Paper" by Dr. Gavin Wood, has been the protocol's reference document ever since.

That paper is the one to read in October 2014, and it is the document that reorganized the conversation about what a blockchain could be.

The briefing registry

  • Title: Ethereum: A Next-Generation Smart Contract and Decentralized Application Platform
  • Author: Vitalik Buterin
  • Document type: Pre-launch design paper
  • Versions in circulation: a 2013 draft and a longer 2014 version; the canonical PDF metadata on the current ethereum.org mirror is dated 2014
  • Companion formal specification: Ethereum: A Secure Decentralised Generalised Transaction Ledger (the "Yellow Paper"), authored by Dr. Gavin Wood
  • Source: Ethereum Whitepaper (2014 PDF)
  • Repository of record: ethereum.org/whitepaper
  • Reading lens: October 2014. The network is not yet live. The crowdsale is forthcoming.

What Bitcoin script could not do

The strongest frame for reading the whitepaper is to start with what was already on the shelf in 2013. Bitcoin's scripting language was deliberately small. It supported signature checks, hashlocks, timelocks, multisignature thresholds, and a small toolkit of arithmetic and comparison operators. The reason it stayed small was defensive: a script was evaluated by every full node, so any construct that could run forever, or read unbounded resources, would let an attacker grind the network to a halt.

Buterin itemized four concrete failures that came out of this constraint. The scripting language was not Turing-complete, which made multi-stage contracts clumsy. Scripts were value-blind, with no way to express partial withdrawals or proportional payments. Scripts were state-blind, in the sense that the only state a UTXO knew was spent or unspent, which made it hard to build any contract that had to remember something between calls. Scripts were also blockchain-blind, unable to read the block number or the previous hash, which made randomness, bet settlement, and commit-reveal protocols hard to assemble.

The deeper issue was that the architecture had nowhere to put a fix. Anything that wanted more than what Bitcoin script offered had to build a meta-protocol on top of Bitcoin and live with the cost of using Bitcoin transactions as a transport layer. Colored coins did this. Mastercoin did this. Namecoin did this. The pattern was the same each time: build an alternative state transition function, then write it on top of a Bitcoin transaction. The metal was good and the ceiling was low.

A state machine with a programmable surface

The conceptual move in the whitepaper is small enough to fit on a napkin. Take Bitcoin's model of APPLY(S, TX) -> S' and replace the implicit state, which is the set of unspent transaction outputs, with an explicit state object, which is the set of all accounts. Each account holds a nonce, an ether balance, optional code, and optional storage. The state transition function now does whatever the contract code says, as long as the code is well-formed and the sender can pay the fee. The blockchain becomes a deterministic computer that the network runs in lockstep.

The white paper's term for this was "autonomous agent." A contract account is not a thing that gets fulfilled or complied with, the way a paper contract is. It is a small persistent program with its own balance and its own key-value storage that lives inside the execution environment and does one thing every time someone sends it a message: it runs its code. The contrast with Bitcoin's UTXO model is sharper than it sounds. A UTXO is a coin-shaped note that ceases to exist when spent. An Ethereum account is a long-lived locus of state that other agents can poke by sending messages.

The cleverer part is what happens at the boundary between the contract and the network. Every transaction carries two extra fields beyond the standard recipient, value, and signature. STARTGAS declares the maximum number of computational steps the transaction is allowed to take. GASPRICE declares the fee per step. Before any code runs, the sender's account is debited STARTGAS * GASPRICE ether. If execution runs out of gas, every state change is reverted, but the miner keeps the fee. This makes the system self-policing against infinite loops, without giving up the ability to write loops at all. It is the mechanism that makes a Turing-complete language safe to run on a shared computer.

How the engine turns

The diagram below walks the path of a single transaction from the sender through the EVM to its new home in the state trie. The numbers in the dark box trace the worked example from the whitepaper: a sender with enough ether to cover the fee, a contract call with 10 ether of value, and 2000 gas of compute budget at a gas price of 0.001 ether.

Core Architecture/Flow

The state on the left, S[0], S[1], ..., S_FINAL, is not stored in the block. Every node recomputes it from the genesis state, transaction by transaction, and then summarizes it by a single root hash. The summary lives in the block header. The summary is a Merkle Patricia trie root, which is the data structure the paper introduces in place of Bitcoin's binary Merkle tree. The Patricia version supports insertion and deletion, which is what you need when an account that did not exist before suddenly does.

The middle column shows the two account types. Externally owned accounts are controlled by private keys and have no code. Contract accounts have code and storage and activate when they receive a message. The same APPLY(S, TX) rule applies to both, because both are rows in the same state.

The right side is the per-node EVM. At any moment, the full computational state is described by an eight-tuple: (block_state, transaction, message, code, memory, stack, pc, gas). The instruction at pc is read, executed, and pc is incremented. Operations manipulate the stack, scratch into memory, and reach into the contract's persistent storage. Gas decrements on every operation. When gas hits zero, execution reverts and the miner keeps the fee. When code reaches STOP or RETURN, the state changes are committed.

The dark box at the bottom is the paper's own worked example. A sender with 1000 ether sends 10 ether, plus 2000 gas at 0.001 ether per gas, plus 64 bytes of data, to a contract. The contract reads the first 32 bytes as a key, the second 32 bytes as a value, and stores the value at that key. The trace at the bottom of the diagram shows the seven-step walk: fee debit, byte-fee subtraction, value transfer, code execution at 187 gas, gas refund, and the final state. The numbers come straight out of the paper.

What the paper actually claims

The whitepaper does not hedge on its scope, and the claims cluster into four groups.

First, it claims a generalized abstraction. The same chain should host sub-currencies, financial derivatives, name registries, decentralized file storage, voting systems, decentralized autonomous organizations, and prediction markets, without rebuilding the underlying consensus each time. The proof of the claim is in the worked examples sprinkled through the paper, including a token system in a few lines of Serpent, a hedging contract against ETH/USD volatility, a Namecoin-style registrar, a "decentralized Dropbox" that pays nodes for storage, and a DAO with three transaction types and a 67% supermajority rule.

Second, it claims Turing-completeness without the usual denial-of-service exposure. The defense is the gas mechanism, and the paper spends several pages showing that a Turing-incomplete language is not actually a way out of the problem, because the same halting behavior can be smuggled in through cross-contract calls and recursive structures. The argument is more subtle than it looks, and it set the template for how EVM gas costs would be argued about for years afterward.

Third, it claims a faster block time than Bitcoin through a modified GHOST protocol. Sompolinsky and Zohar had proposed GHOST in late 2013 to make short block intervals safer, by counting stale blocks ("uncles") toward the chain's total work. Buterin's contribution was to also pay uncles. The literal rule from the paper: the miner of the including block gets an additional 3.125% added to its coinbase reward, and the miner of the uncle gets 93.75% of a standard coinbase reward. Uncle depth is capped at seven levels to keep the computation bounded.

Fourth, it claims a state-based storage model that should be comparable in size to Bitcoin's UTXO set, despite the added expressiveness. Between adjacent blocks, almost the entire state trie is unchanged, so unchanged subtrees can be referenced once and reused. The state trie, not the full transaction history, becomes the only thing a full node must store, which the paper claims would give Bitcoin a 5x to 20x storage reduction if it adopted the same approach.

The paper also proposes a denomination scheme that became canonical: 1 wei, 10^12 szabo, 10^15 finney, 10^18 ether. The issuance model is a presale of 1000 to 2000 ether per bitcoin, with 0.099x of the amount sold going to early contributors, 0.099x held in long-term reserve, and 0.26x of the supply issued per year to miners in perpetuity. The paper's authors anticipate a future switch to proof-of-stake, and they bake in a "social contract" rule that the supply expansion cannot exceed a deterministic function of years since the genesis block.

Why it mattered in the room

The clearest evidence that the paper landed where Buterin wanted it is what got built in the eighteen months after the public draft went around. Dr. Gavin Wood wrote the Yellow Paper, the formal specification of the EVM, then led the development of the first functional Ethereum client, released in January 2014 as "PoC-1." Anthony Di Iorio, Mihai Alisie, and others joined the project. The Ethereum presale opened on 22 July 2014 and ran for 42 days, raising roughly 31,500 bitcoin in exchange for about 60 million ether. By the time the network was scheduled to go live in 2015, the design choices the paper had committed to, account-based state, a Turing-complete bytecode, gas-metered execution, and a modified GHOST consensus, were already load-bearing parts of a working stack.

The most consequential design choice may be the one the paper spends the least time on. By making the state object a general ledger of accounts with code, the system made it natural to treat contracts as first-class senders and recipients. A contract can hold ether, call another contract, send a message that triggers further messages, and even create new contracts at runtime. Every one of those primitives is visible in the paper, sketched in plain text. They are the primitives that, once the network goes live, developers will use to build lending markets, exchanges, and governance systems that have no precedent in the Bitcoin world. The whitepaper does not predict any specific applications. It builds the surface they can live on.

Open questions, unresolved in the paper

The paper is honest about the things it does not solve. Scalability is the most prominent. The argument that "every transaction needs to be processed by every node" gets called out as a centralization risk. If the chain grows large enough that only a few professional node operators can afford to run full validation, the system starts to look like a federation rather than a peer-to-peer network. The paper's near-term mitigations are that the mining algorithm forces miners to run full nodes, and that the block can commit to intermediate state roots so that an honest verifier can publish a proof of invalidity if a miner submits a bad block. Both mitigations are partial fixes, and the paper flags the longer-term answer as a problem for later work.

Turing-completeness is treated as a controlled risk rather than a solved one. The contract-to-contract reentrancy pattern is not on the paper's radar, though it is the kind of subtle interaction that the EVM's message-passing design makes possible. The author expects that gas limits will bound the damage from bad code, which is true in the narrow sense that an attacker can only drain a contract up to the gas budget of the calling transaction, but it remains to be seen whether gas alone is sufficient defense against every class of exploit that creative adversaries will devise.

The mining algorithm the paper proposes, where miners execute randomly chosen transactions from the last N blocks to construct the proof-of-work, is described as untested. The author flags the risk that clever optimizations could let specialized hardware reappear, and offers the consolation that anyone can "poison the well" by deploying contracts designed to stump ASICs. The honest reading is that the paper was a starting point, and the consensus layer would need its own iteration cycle. The eventual switch to proof-of-stake, which the paper mentions as a likely future change, is itself a concession that the 2014 mining design was provisional.

Finally, the paper is silent on a number of things that are likely to dominate the discussion once real money starts moving through the system. There is no discussion of how contract upgrades should work in practice, beyond a brief mention of "de-facto mutability" through indirection. There is no governance framework for protocol changes. There is no analysis of what happens when real money starts sitting in contracts with bugs. The whitepaper gives the field a coordinate system. It does not, and could not, hand the field a finished map.

Sources