# 01 — Replicated State Machines Picture Carol at a teller window on a busy afternoon. She asks a question that sounds trivial: "What's my balance?" Behind that question is an assumption so familiar we rarely notice it. She is not asking for a menu of plausible answers. She is not asking which timeline she is in. She expects **one number** — the number that matches *some* story about what happened to her money before she walked in. A story where deposits, transfers, and fees happened in an order, even though she never watched that order unfold. The teller does not invent that number; the ledger has **rules** for reading entries, and those rules always produce the same balance from the same history. The bank does not pause while she asks. A transfer to Bob clears. A payment from Alice posts. Someone in the back office adjusts inventory that has nothing to do with Carol. The building is full of overlapping work — concurrent, interleaved, simultaneous in real time. Carol's question still demands a single reply. That tension — many things happening at once, one authoritative history underneath — is older than blockchains. It is the tension behind every ledger, every database, every replicated service you have ever used: the world feels parallel, but the books must read as if they were written in *some* definite sequence. This module is the origin story of how systems keep that promise — and of what happens when you refuse to trust anyone to enforce it. The question underneath everything is not merely "how do we put a transaction in a log?" It is deeper: > How do we turn concurrent proposed state changes into one canonical, replayable history? You will watch that same question get harder three times. First on one machine, with **MVCC** and a local WAL. Then across cooperative machines, with **Raft**. Finally among strangers who may profit from lying — with a **blockchain**. The trust assumptions weaken at each step. The shape stays the same: a **log** of entries, **rules** for reading them, a **state** those rules produce. Consensus fights over the log; the rulebook is a story for a later module. --- ## One machine, many stories ### The impossible schedule A database serves many clients at once. The guarantee you usually want is **serializability**: the result should be the same as if those transactions had run **one at a time**, in *some* serial order. ```text Good: as if T1 then T2 then T3 Bad: a schedule where two spends succeed on the same $10 ``` Even before anyone appends to a write-ahead log, you are already asking for a story: *there exists an ordering of these transactions that leads to the state I see.* That serial order is the database's implicit **log of state transitions** — a script the engine knows how to run. Every transaction is an **instruction**: move ten dollars, reserve inventory, accrue interest. The database engine embeds the **rules** for what each instruction means. Two clerks who know those rules and read the same entries in the same order must compute the same balances. That determinism is easy to take for granted on one machine; it becomes load-bearing once the log is replicated among strangers. ### MVCC — versions instead of waiting The naive way to get serial behavior is **two-phase locking**: readers and writers take locks; conflicting transactions wait. It works. Hot rows become bottlenecks. **Multi-Version Concurrency Control (MVCC)** takes a different path. Instead of overwriting a row in place, the engine keeps **versions**. A write creates a new version; old versions linger until no transaction needs them. A read sees the **newest version visible to this transaction** — typically a consistent snapshot from when the transaction started. ```text Row balance for Alice: v1: $100 (txn 41) v2: $80 (txn 52 overwrote after txn 41 committed) v3: $60 (txn 60) Txn 55 (started before txn 60): still reads v2 → $80 Txn 60: reads v3 → $60 ``` Pause on those numbers — 41, 52, 60. Where do they come from? Every transaction receives a **transaction id (xid)** at birth, handed out by a **synchronous counter**: one atomic integer, incremented under a lock, owned by the one database process. Version visibility is xid arithmetic ("was txn 52 committed before txn 55's snapshot?"). The serial order the engine enforces is, roughly, commit order over xids. The entire ordering problem, on one machine, reduces to this: *one process owns one counter.* Cheap. Total. Unambiguous. There is exactly one place in the universe where "next" gets decided. Hold onto that counter. The rest of this module is what happens when you lose it. Readers do not block writers; writers do not block readers on the same row. Throughput rises because most reads never wait for a lock. ### Snapshot isolation is not yet serializability **MVCC with snapshot isolation** (Postgres `REPEATABLE READ`) gives each transaction a stable snapshot for its whole life. You will not see another transaction's in-progress writes. You *can* still get **write skew** — two transactions each read consistent data, make compatible-looking decisions, and together produce a state no serial order would allow. **True serializability** means *no* such anomaly: there must exist *some* serial order that explains the outcome. Postgres achieves this at `SERIALIZABLE` with **Serializable Snapshot Isolation (SSI)** — MVCC snapshots plus conflict detection that aborts transactions when their reads and writes could not have happened in any serial order. | Isolation level | What you get | |---|---| | Read committed | See only committed data; each statement may see newer commits | | Repeatable read (MVCC snapshot) | Stable snapshot for the transaction; not always serializable | | Serializable (SSI on top of MVCC) | Serializable — equivalent to some one-at-a-time order | A production database is already machinery for **enforcing (or approximating) one serial history of state changes** while pretending to be concurrent. The engine picks valid orderings, detects conflicts, aborts when it must. On one machine, that problem is mostly solved. ### From serial order to state machine Name what the database has been doing all along. There is a **state** — rows, balances, indexes. Each committed transaction is a **transition**: ```text State_1 = apply(State_0, tx_1) State_2 = apply(State_1, tx_2) State_3 = apply(State_2, tx_3) ``` Serializability means: the committed transactions could be relabeled `tx_1, tx_2, tx_3, ...` in *some* order, and replaying them through `apply` yields the state you actually got. Think of `apply` as the engine's **replay rule** — not yet the full interpreter you will meet when blocks carry programs ([[05 Execution and Smart Contracts]]), but the same idea at ledger scale: read the next line, update the books, repeat. The **WAL** is that order made durable — append each commit, crash, replay the log, recover the same state. Durability is the WAL's job: once ordered, the history survives process death. So the single-database version of the through-line is: > Given many concurrent transactions, which serial history explains the final state? You have been looking at a **state machine** all along. The hard part on one machine is concurrency without breaking the serial fiction. The hard part across machines is getting everyone to agree on the *same* fiction when there is no single database process in charge. --- ## Many machines, one log Once a single machine can maintain one serial history, **replication** asks the next question: how do we get *many* machines to maintain the *same* history? At scale, transactions arrive in **blocks** — batches of already-ordered commands: ```text new_state = execute(old_state, block) ``` At chain scale the log is **batched into blocks**; `execute` is the batch form of the same replay idea. Running those rules is the easy column — any honest machine that knows the rulebook and reads the same log in the same order reaches the same state. The hard part is agreement on: 1. Which transactions are valid 2. In what order they happened 3. Which history is canonical 4. When that history is final enough to trust If you know distributed systems, this is **state machine replication** — the same serial-order idea from MVCC, but now the log is replicated and `apply` runs on every replica. Raft and Paxos solve that when replicas are cooperative. Blockchains solve it when they are not. ### The same pipeline, three times Same problem, less trust in who may write the log each time: > Databases, Raft, and blockchains are successive answers to converting concurrent proposed state transitions into a canonical, replayable log under progressively weaker trust assumptions. ```text single-machine ordering → cooperative distributed ordering → adversarial distributed ordering ``` You saw the pattern on one machine: committed transactions form a serial order; replaying them recovers state. A relational database makes it durable with a **transaction log** (WAL, binlog, redo log — names vary). Recovery after a crash is literally "replay the log from the last checkpoint." ```text log: [INSERT Alice=10] [UPDATE Bob+=5] [DELETE Carol] ... | | | state: State_0 ---------> State_1 -----> State_2 -----> ... ``` A **consensus protocol** does the same thing across machines. Raft or Paxos does not magically sync databases — it agrees on an **ordered log of commands**. Each replica runs the same `apply` in the same order: ```text replica A: log [cmd1, cmd2, cmd3] --> apply --> state S replica B: log [cmd1, cmd2, cmd3] --> apply --> state S replica C: log [cmd1, cmd2, cmd3] --> apply --> state S ``` The consensus layer's job is only the middle column: **one canonical order**. The replay rules are public and deterministic — given the same log, every replica reaches the same state. Disagreement means someone lied about the log, the order, or what the rules produced; not that the rules themselves are mysterious. A blockchain fits the same diagram. Blocks are log segments; transactions are commands; chain state is what you get after replay. The difference is not the shape. It is who is allowed to write the log, and what happens when replicas disagree about more than crashes. | | **Single-node DB** | **Raft / Paxos cluster** | **Blockchain** | |---|---|---|---| | **Core problem** | Serialize concurrent transactions | Agree on one command log | Canonicalize adversarial proposed history | | **Who orders?** | Local engine / xid / commit machinery | Elected leader + quorum | Consensus + incentives | | **What is the log?** | WAL inside one machine | Replicated command log | Chain of blocks | | **Threat model** | One trusted process / machine | Cooperative nodes, crash faults | Byzantine, open participation | | **Recovery** | Replay local log | Replay agreed log | Replay agreed chain | "Put it in a log" undersells what each system must decide. Every stage answers some mix of: 1. **Validity** — is this proposed transition allowed *under the rulebook*? 2. **Ordering** — where does it sit relative to other transitions? 3. **Durability** — once ordered, can it be recovered and replayed? 4. **Replication** — who else gets the same log? 5. **Finality** — when should observers stop treating the log as provisional? 6. **Adversary model** — who can lie, reorder, censor, equivocate, or rewrite? A single DB mostly owns (1)–(3) inside one process. Raft adds (4) under crashes. Blockchains keep the shape and make (5)–(6) first-class — and fold cryptography and economics into how (1)–(4) are enforced. MVCC, Raft, and blockchains are different machinery; the thread is who may decide the next log entry, and under what threat model. Finality gets its own deep treatment in [[04 Consensus]] and [[Finality]]. ### When you lose the counter On a single machine, ordering is almost free. One process accepts writes; the xid counter hands every transaction its place in line; the WAL fixes a durable sequence; `NOW()` means whatever that machine's clock says. **Multiple machines** break it. There is no shared counter to increment. **No shared writer.** Many processes can propose commands. Without agreement, replica A's log is `[tx1, tx2]` and replica B's is `[tx2, tx1]` — same transactions, different states after `apply`. You need a protocol whose output is: *this is the one log we all replay.* **No shared clock.** Timestamps seem like an obvious replacement for the counter. They are not. Each machine's clock drifts; "later" on one machine may be "earlier" on another. **Lamport clocks** patch part of this: every message carries a counter, every receiver bumps its own to `max(local, received) + 1`, so causally related events order correctly. **Vector clocks** go further and let you *detect* concurrency — one counter per machine, and two events are concurrent exactly when neither's vector dominates the other. But notice what vector clocks give you: a **partial order**. They can tell you `A happened-before B` or `A and B are concurrent`; they cannot break the tie. The xid counter never had ties, because one process owned it. Distributed, you can reconstruct causality but not a total order — something still has to *choose*. **Raft's answer: re-centralize the counter, carefully.** Raft does not distribute the ordering decision at all — it elects a **leader**, and the leader hands out log positions exactly like the xid counter did: slot 1, slot 2, slot 3, one process deciding "next." What is distributed is *fault tolerance around* the counter: the leader must replicate each entry to a quorum before it counts, and if the leader dies, an election installs a new counter-owner without losing the committed prefix. Paxos differs in mechanics, same shape. The counter survives; it just wears a crash helmet. So the Raft version of the through-line is: > Given multiple cooperative machines, how do we agree on one command log? **Partial failure and asynchrony.** Messages delay, partitions happen, nodes crash mid-operation. The FLP result says you cannot have perfect deterministic consensus in the worst case — so real systems choose timeouts, leaders, quorums, or probabilistic finality. See [[Distributed Systems Bridges]]. In short: **multiple machines + no authoritative counter + need for one history ⇒ distributed consensus.** The database world solved this for *cooperative* replicas inside a datacenter, by rebuilding the counter behind an election. Blockchains ask the same question for *uncooperative* replicas across the open internet — where no one can be trusted to hold the counter at all. What replaces it is the subject of [[03 Blocks, Hashes, and History]] and [[04 Consensus]]: **the log itself becomes a linked structure**, each entry cryptographically pointing at its predecessor, so that order is not assigned by an authority but *claimed* by construction and then arbitrated by consensus. You discover the order by walking the links, not by asking the counter. --- ## When the replicas are not on your team Imagine being handed the harder version. Ten thousand machines, run by strangers who do not trust each other, must maintain the same shared ledger. No coordinator. No admin. No support line. If you have built replicated systems — Paxos, Raft, primary-backup — your first instinct may be "this is a solved problem." It nearly is — except for one assumption buried in all of those protocols: the replicas are on the same team. Raft assumes replicas that **crash**, not replicas that **lie**, **collude**, or **profit** from doing so. Pull that assumption out and watch how much of the machinery survives. ### High trust vs low trust Raft and Paxos assume a **high-trust** model: - The replica set is **known and permissioned** (these five nodes, not "anyone on the internet"). - Failures are **benign** — nodes crash or drop messages; they do not forge log entries or lie about what they applied. - Misbehavior has **no upside** — there is no profit in equivocating, only risk of being removed from the cluster. That is appropriate inside your infrastructure. You operate the replicas. You care about availability, not about strangers mining value from reordering your writes. A **low-trust** (or **adversarial**) model drops those assumptions: - **Open participation** — anyone can run a node, propose blocks, validate. - **Byzantine behavior** — replicas may lie, withhold data, censor transactions, or collude. - **Economic incentives** — misbehavior can be *profitable* (double-spend, rewrite history, extract ordering rent). Low trust does not mean "nobody trusts anybody about everything." It means the protocol cannot assume a fixed, honest replica set. Correctness must come from things every node can check locally (signatures, hashes, execution) plus rules that make cheating cost more than honesty pays (work, stake, slashing). That is the step from "replicated state machine" to "blockchain": **same log-replay pattern, but consensus must work when the replicas are not on your team.** On a public chain, those replicas are called **nodes**, gossiping the same protocol across a peer-to-peer mesh ([[03 Blocks, Hashes, and History]]). The core question — the third stage of the through-line — is: > Given open, adversarial participants, how do we let anyone propose log entries while still converging on one canonical replayable history? Verification, finality, and making cheating expensive are how that answer is made to stick. Everything else — tokens, wallets, smart contracts, rollups, bridges, NFTs, DeFi — is built on top of that one problem. ### A replicated database, hostile edition There is a state, and transactions transform it: ```text State_1 = apply(State_0, tx_1) State_2 = apply(State_1, tx_2) State_3 = apply(State_2, tx_3) ``` A block is a batch of ordered transactions: ```text Block = [tx_1, tx_2, tx_3, ...] new_state = execute(old_state, block) ``` You recognize this shape — **state machine replication**: one ordered log, same replay rules everywhere. The twist is that the replicas are potential adversaries, not cooperative datacenter nodes. The replay rules are still the easy column. Any machine can run them. The hard part is getting thousands of adversarial machines to agree on: 1. Which transactions are valid. 2. In what order they happened. 3. Which chain is canonical. 4. When history is final enough to rely on. Raft tolerates replicas that crash. Here, replicas lie, collude, censor, and — this is the genuinely new part — *profit* from doing so. The classical results still apply, but they need unpacking. In 1985, Fischer–Lynch–Paterson proved (**FLP**) that no *deterministic* consensus protocol can guarantee both safety and liveness if messages may be delayed arbitrarily and even one process can crash — which is why blockchains use probabilistic finality, timeouts, and economic penalties rather than pure agreement. See [[Distributed Systems Bridges]]. In **Byzantine** agreement — where nodes may lie, not just crash — you need `n >= 3f + 1` total nodes to tolerate `f` malicious ones. The point is not ordinary majority rule. Quorums of size `2f + 1` must **overlap in at least one honest node**, so two conflicting decisions cannot both gather valid quorums without forcing some honest node to sign both. Misbehavior can't merely be detectable; it has to be *expensive*. Consensus, in other words, acquires an economy. Hold onto that thought — it explains more of what follows than any other single idea. And underneath it all, one sentence worth keeping in your pocket: > A blockchain is a replicated state machine where correctness comes from cryptographic verification, economic incentives, and a consensus rule for ordering state transitions. When something feels confusing, ask which part of that sentence it serves. --- ## Why anyone built this painful machine So what problem actually forced all this machinery into existence? **Digital scarcity without a central server.** Digital files copy for free. If Alice holds a digital coin, what stops her from sending the same coin to both Bob and Carol? A bank solves this trivially: ```text Alice balance: 10 Bob balance: 0 Carol balance: 0 ``` One writer, one truth. The bank rejects the second spend. Done. Bitcoin's founding question was whether you could get that same guarantee with **no bank anywhere in the picture**. Its answer: **proof-of-work** — nodes compete to find a hash below a difficulty target; winning lets you propose the next block. Costly to compute, trivial to check. The whitepaper describes the network as timestamping transactions by hashing them into a chain of proof-of-work, so that changing history requires redoing the work. The key idea: > The canonical history is the one that required the most economically costly resource to produce. For Bitcoin, that resource is computation and electricity. For proof-of-stake systems, it is bonded capital that can be destroyed. Either way: make history expensive to write, and it becomes expensive to rewrite. That cost is why Stripe and Postgres usually win. A public chain buys you something those systems cannot honestly promise: agreement among adversaries without a privileged operator. If you already have a trusted operator, cooperative replicas, or only need tamper *evidence*, do not pay for planetary consensus — see [[Blockchain Home#When not to use a blockchain|when not to use a blockchain]]. The double-spend problem is the reason the painful machine exists; it is not a reason to run every app on one. --- ## The four layers — a map for what comes next One more tool before moving on. A blockchain is usually four protocols glued together: | **Layer** | **Question it answers** | |---|---| | **Networking** | How do nodes gossip transactions and blocks? | | **Consensus** | Which block/history is canonical? | | **Execution** | Given a block, how does the state change? *(The **interpreter** for the log — deterministic `apply` at first, the EVM later.)* | | **Data availability** | Can validators/users actually obtain the data needed to verify the state? | Bitcoin fuses these into one simple chain. Ethereum separates them more clearly, especially after proof-of-stake and rollups. Keep this table handy — the rest of the vault walks through it layer by layer. Every protocol you will evaluate is a different set of answers to: who orders transactions, who verifies execution, who stores data, who pays, who can cheat, who notices, who can recover, and what the user has to trust. More on that framing in [[Trust Assumptions]]. --- ## Learning outcomes A few questions worth trying on — out loud, ideally, or to a patient colleague: - Could you state the through-line in one sentence — concurrent proposed transitions → one canonical replayable log — and name what weakens at each stage (single machine → cooperative replicas → open adversaries)? - Could you explain what serializability guarantees, and how MVCC snapshot isolation differs from true serializability? - Could you trace the ordering authority across the three systems: the xid counter, Raft's leader-assigned log slots, and a blockchain's hash pointers — and say what each gains and loses? - Could you explain why vector clocks alone can't replace the xid counter — what they give you, and what's still missing? - Could you explain how a Postgres WAL and a Raft log are the same pattern — and where a blockchain block chain fits on that diagram? - Could you explain why multiple machines with divergent clocks force distributed consensus, not just "sync the databases"? - Could you state the difference between high-trust (Raft) and low-trust (blockchain) replication in one paragraph? - Could you explain why a blockchain is "just" state machine replication — and pinpoint exactly where the "just" falls apart? - Could you state the double-spend problem, and why it's trivial with a bank and genuinely hard without one? - Could you explain why "the chain with the most work wins" makes history hard to rewrite, in one paragraph, without hand-waving? - Can you name the four layers, and say what fails if each one fails? - And here's a thread to pull on as you go: agreement requires verification — but what makes verification between total strangers possible in the first place? ## Checkpoint Try these before moving on. If an answer feels wobbly, the pointer tells you where to look. 1. State the three evolving questions — single DB, Raft, blockchain — in one sentence each. What trust assumption dropped between each pair? *(If unsure, revisit "One machine, many stories through When the replicas are not on your team".)* 2. What does MVCC buy you over naive locking, and what extra does SSI add for serializability? *(If unsure, revisit "One machine, many stories".)* 3. Draw the log → apply → state pipeline for a database and for Raft. What does consensus contribute in the Raft picture? *(If unsure, revisit "Many machines, one log".)* 4. Why can't Raft, as-is, run an open cryptocurrency? *(Hint: Raft tolerates crashes, not strategic lying or profit-seeking behavior. If unsure, revisit "When the replicas are not on your team".)* 5. What resource makes Bitcoin's history expensive to rewrite, and what's the proof-of-stake analogue? *(If unsure, revisit "Why anyone built this painful machine".)* 6. Which of the four layers does a mempool belong to? An indexer? *(If unsure, sit with the four-layer table — full answers arrive in [[06 Transaction Lifecycle and MEV]] and [[08 Nodes, RPCs, and Indexers]].)* **Exercise.** In ten lines of pseudocode, sketch `execute(old_state, block)` for a toy coin with balances. Then write down every way a malicious node could lie about the result. Keep that list — the next few modules answer it item by item, and it's satisfying to cross them off. ## Resources - **Bitcoin whitepaper** — short, dense, and still the cleanest statement of the double-spend problem, proof-of-work, hash chains, and probabilistic finality. Don't overstay; it teaches the skeleton. - **Stanford CS251** — the best academic map: consensus, contracts, economics, scaling. With your background it reads as "distributed systems with adversarial economics," which is exactly right. --- Next: strangers must agree they ran the same rulebook on the same log. That requires tools for verification — what are they? → [[02 Cryptographic Primitives]]