# 01 — Replicated State Machines You already run systems whose correctness depends on one ordered history of writes. A Postgres cluster, a Raft-backed service, a bank ledger — all of them are trying to preserve the fiction that state changed in *some* definite sequence, even when many clients and many machines are involved at once. Blockchains are the same problem pushed further: strangers, open participation, profit from cheating. But the thread starts somewhere familiar — inside a single database, with concurrent transactions and **MVCC**. ## One machine first: MVCC and serializability A database serves many clients at once. Alice transfers money; Bob queries a balance; Carol updates inventory — overlapping, concurrent, interleaved in real time. 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. No interleaving that produces impossible state. ```text Good: as if T1 then T2 then T3 Bad: a schedule where two spends succeed on the same $10 ``` That serial order is the database's implicit **log of state transitions**. Even when nothing is literally appending to a WAL yet, you are asking for a story: *there exists an ordering of these transactions that leads to the state I see.* ### How MVCC helps The naive way to get serial behavior is **two-phase locking (2PL)**: readers and writers take locks; conflicting transactions wait. It works, but hot rows become bottlenecks. **Multi-Version Concurrency Control (MVCC)** takes a different approach. Instead of overwriting a row in place, the engine keeps **versions**. A write creates a new version; old versions stick around until no transaction needs them. A read sees the **newest version visible to this transaction** — typically a consistent snapshot as of 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 gets 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. That counter is doing more work than it looks like. 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 reduces to *one process owning one counter* — cheap, total, and unambiguous, because 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 goes up because most reads never wait for a lock. ### MVCC and serializability are not the same thing This distinction matters, so say it plainly. **MVCC with snapshot isolation** (what Postgres calls `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 anomalies like **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 the `SERIALIZABLE` level 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 | The lesson for what follows: 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 is doing in the vocabulary this module will use. 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 in that order through `apply` yields the state you actually got. The WAL is that order made durable — append each commit, crash, replay the log, recover the same 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. ## Primer: replicated state machines Once a single machine can maintain one serial history (MVCC, isolation, WAL replay), **replication** asks: how do we get *many* machines to maintain the *same* history? At scale, transactions arrive in **blocks** — batches of already-ordered commands. The protocol defines batch execution: ```text new_state = execute(old_state, block) ``` Running `apply` (or `execute`) is easy. Any machine can do it. The hard part is getting many machines to agree 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. Imagine being handed the harder version: ten thousand machines, run by strangers who don't trust each other, need to maintain that same shared ledger. No coordinator, no admin, no support line. If you've built replicated systems — Paxos, Raft, primary-backup — your first instinct is probably "this is a solved problem." And 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. The motivating problem is **double spend**: without a bank, what stops Alice from sending the same coin to Bob and Carol? Blockchains answer by making history expensive to rewrite — through proof-of-work (electricity) or proof-of-stake (bonded capital). The canonical chain is the one that cost the most to produce. 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. The sections below unpack each piece. When something feels confusing, ask which part of that sentence it serves. ## Databases, consensus, and the same pattern Here is a unifying view that makes blockchains less alien: **a database and a consensus protocol are both machinery for replaying an ordered log into state.** ### The log → apply → state pipeline You saw this pattern in the MVCC section: 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**. Execution is deterministic — given the same log, every replica reaches the same state. That is the state machine replication model in one sentence. 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** | |---|---|---|---| | Log | WAL inside one machine | Replicated command log | Chain of blocks | | Who orders writes | One process + isolation (MVCC/SSI) | Elected leader + quorum | Consensus + economics | | Replica trust | N/A (one copy) | Crash faults only | Byzantine, open participation | | Recovery | Replay local log | Replay agreed log | Replay agreed chain | Once you see the table, "blockchain" stops being a new species and becomes **replicated state machine replication under stricter assumptions.** ### Why multiple machines force distributed consensus 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. MVCC is how one machine runs many transactions while preserving the serial fiction — and the whole scheme rests on that one synchronous counter. **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.** The obvious replacement for the counter — timestamps — doesn't work. 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 doesn't 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's 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 (with term numbers as epochs) 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. **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. ### From cooperative replicas to 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.** The next section names what changes when you take that step seriously. ## The problem, stated plainly A blockchain protocol lets a set of mutually distrustful machines maintain a shared state machine. The core question: > How do we let anyone submit transactions, let many parties verify them, agree on one canonical history, and make cheating expensive or impossible? Everything else — tokens, wallets, smart contracts, rollups, bridges, NFTs, DeFi — is built on top of that one problem. ## A replicated database, hostile edition The previous section put databases, Raft, and blockchains on the same diagram. Now zoom in on what **low trust** changes. There's 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 just a batch of ordered transactions: ```text Block = [tx_1, tx_2, tx_3, ...] ``` And the protocol defines: ```text new_state = execute(old_state, block) ``` You recognize this shape from the section above — **state machine replication**: one ordered log, same `apply` everywhere. The twist here is that the replicas are potential adversaries, not cooperative datacenter nodes. That twist relocates all the difficulty. Execution isn't the hard part; any machine can run `apply`. 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. It's worth pausing on how much changed when we dropped the "same team" assumption. 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]] for the full bridge. In **Byzantine** agreement — where nodes may lie, not just crash — you need `n >= 3f + 1` total nodes to tolerate `f` malicious ones: three liars can outvote two honest nodes, but four honest nodes can outvote three liars. Those bounds still aren't enough on their own. 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. ## Why this exists at all: the double spend So what problem actually motivated all this? 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, with a database: ```text Alice balance: 10 Bob balance: 0 Carol balance: 0 ``` One writer, one truth. The bank rejects the second spend, and we're 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. Sit with the key idea for a moment, because it's the foundation everything else rests on: > 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's bonded capital that can be destroyed. Either way, the trick is the same: make history expensive to write, and it becomes expensive to rewrite. ## The four-layer decomposition 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? | | **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 essentially walks through it layer by layer. ## The invariant If one sentence dissolves most confusion in this field, it's this one: > A blockchain is a replicated state machine where correctness comes from cryptographic verification, economic incentives, and a consensus rule for ordering state transitions. Every protocol you'll ever 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 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. What does MVCC buy you over naive locking, and what extra does SSI add for serializability? *(If unsure, revisit "One machine first: MVCC and serializability".)* 2. Draw the log → apply → state pipeline for a database and for Raft. What does consensus contribute in the Raft picture? *(If unsure, revisit "Databases, consensus, and the same pattern".)* 3. Why can't Raft, as-is, run an open cryptocurrency? *(Hint: Raft tolerates crashes, not strategic lying or profit-seeking behavior. If unsure, revisit "From cooperative replicas to low trust".)* 4. What resource makes Bitcoin's history expensive to rewrite, and what's the proof-of-stake analogue? *(If unsure, revisit "Why this exists at all".)* 5. 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: verification between strangers needs tools. What are they? → [[02 Cryptographic Primitives]]