# 02 — Cryptographic Primitives [[01 Replicated State Machines]] left us with a puzzle: agreement requires verification, and verification here has to work between total strangers — no shared server, no prior contact, no one to vouch for anyone. What tools could possibly work under those constraints? It turns out you need surprisingly few. Four, in fact: **hashes**, **signatures**, **commitments**, and **zero-knowledge proofs**. You don't need to become a cryptographer to use them well — you need to know precisely what each one buys you, which is a much smaller ask. ## Hash functions A hash maps arbitrary data to a fixed-size output: ```text hash("hello") = 2cf24d... ``` The properties that matter for our purposes: - Deterministic — same input, same output, everywhere. - Preimage-resistant — given a hash, you can't figure out what input produced it. - Collision-resistant — you can't craft two different messages with the same fingerprint. - Avalanche — a one-bit input change scrambles the whole output. Put those together and you get something valuable: a fingerprint anyone can check and no one can forge. That's what powers block IDs, [[Merkle Trees]], proof-of-work, commitments, and address derivation. When a blockchain "points to" data, it points with a hash — which is exactly why tampering with anything breaks everything downstream of it. ## Digital signatures A user holds: ```text private_key public_key address = hash(public_key) ``` They sign transactions with the private key, and anyone can verify: ```text verify(public_key, message, signature) == true ``` What this buys is worth savoring: authorization without any identity infrastructure. No account table, no password database, no login service. Whoever holds the key *is* the account. If you've spent years building auth systems, notice the inversion. Authentication is usually a service you run; here it's a mathematical fact the network checks. Elegant — and it comes with a sharp edge, because there's no "forgot password" flow and no one to call. That single design choice generates most of wallet engineering, as we'll see in [[07 Wallets and Account Abstraction]]. One distinction is worth flagging early, because products get it wrong constantly: > Signing a transaction is not "logging in." It can authorize irreversible movement of assets. This is why wallet UX is security-critical, and why the phrase "please sign this" should always prompt the question: sign *what*, exactly? ## Commitments A **commitment** locks in a value now so you can prove later you didn't change it: ```text commitment = hash(secret || nonce) ``` Publish `commitment` today. Reveal `secret` and `nonce` tomorrow. Anyone recomputes the hash and checks it matches. The **nonce** is fresh randomness — it makes the commitment uniquely yours and stops low-entropy secrets like "yes" from being guessable before reveal. ### The properties that matter Same pattern as hash functions: name what you get, then use it. - **Binding** — once you publish the commitment, you cannot later open it to a *different* value without breaking collision resistance. The promise is locked. - **Hiding** — before the reveal, the commitment should not leak the secret. Low-entropy secrets ("yes"/"no") leak even with a nonce; high-entropy secrets plus a random nonce stay hidden until opening. - **Verifiable** — given the commitment and the revealed data, *anyone* can check consistency locally. No trusted auditor, no phone call to a notary. Binding is the load-bearing one for blockchains. Hiding matters for sealed bids, commit-reveal randomness, and privacy. Verifiable is what turns a private promise into a *public* one strangers can audit. ### Commit → reveal → audit Walk through the timeline — the magic is in the order of operations. **Step 1 — Commit.** You publish `C = hash(secret || nonce)` before anyone knows `secret` or `nonce`. The world has a fingerprint of your answer, frozen in time. **Step 2 — Reveal.** Later you publish `secret` and `nonce`. Anyone computes `hash(secret || nonce)` and compares to `C`. **Step 3 — Audit.** Two outcomes, and only two: ```text hash(secret || nonce) == C → you kept your promise hash(secret || nonce) != C → you changed your story, or someone tampered ``` No third option. You don't need to trust the committer's word at reveal time — you trust the math you could run yourself. That's what "auditable" means here: the check is local, deterministic, and repeatable by every node on the network. **Concrete example — sealed bid.** Alice commits `hash(bid || nonce)` before the auction closes. Bob commits his bid the same way. After the deadline, both reveal bid and nonce. Everyone verifies hashes match. Alice cannot see Bob's bid before committing her own (hiding, if bids are well-randomized), and neither can change their bid after seeing the other's (binding). The auction outcome is auditable from public commitments plus public reveals. **What you cannot do after committing.** To open a commitment to a different value, you'd need a collision — a different `(secret, nonce)` pair with the same hash. Collision resistance says you can't. The commitment is a *credible threat* about what you will later reveal. ### Causal threads pinned by entropy Step back from the mechanics. What is a commitment *really* doing? [[01 Replicated State Machines]] already named the hard problem: strangers with divergent clocks need a single history, and timestamps won't give it to them. **Causal order** — "this happened before that" — has to be reconstructed from evidence everyone can check, not from `NOW()` on anyone's machine. A commitment is one way to spin that thread. Before you commit, many futures are still open. You could bid $50 or $500. You could pair your bid with any of trillions of possible nonces. Each `(secret, nonce)` pair lands somewhere in a vast space of possible digests. Nothing in the public record yet says which branch you took. At commit time, you **spend entropy**: draw fresh randomness, mix it with your secret, publish the hash. ```text C = hash(secret || nonce) ^^^^^^ ^^^^^ intent entropy — makes this commitment THIS event, not a guessable template ``` That publish is a **causal knot**. You have pinned one branch of possibility into a digest that: - **Could not have been computed after the fact** from public knowledge alone — the nonce was private until reveal, so an adversary watching the world unfold cannot retroactively forge "I committed to X before I saw Y." - **Admits only one opening** — binding means the reveal must supply the same `(secret, nonce)` pair. A valid opening is causally downstream of the commit; swap the order and verification fails. - **Identifies a unique moment of choice** — without entropy, `hash("yes")` is guessable and carries no real timestamp in disguise. With entropy, the commitment is a needle in an enormous haystack; matching it later is evidence that *this specific choice* was locked in *before* the reveal. ```text many possible (secret, nonce) pairs | | commit: publish C = hash(secret || nonce) v one frozen digest ----happens-before----> reveal: (secret, nonce) | | | v +-------- only this opening verifies ---------+ ``` Each commitment-reveal pair is a **thread of causal ordering**: a verifiable happened-before edge strangers can audit without trusting anyone's clock. The commit must precede the reveal in any story that makes sense — not because a server said so, but because the math only works in that direction. Chain those threads and architecture appears — block hashes, Merkle roots, state roots, each a digest that must be published before anything can reference or open against it. Same pattern every time: **entropy mixed with content, published early, opened later.** This is not global consensus by itself. You still need agreement on *which* commitments landed on the canonical chain ([[04 Consensus]]). But commitments are the primitive that turns "I decided before I knew" from rhetoric into something every node can verify. ### Where you'll see them - A [[Merkle Trees|Merkle root]] commits to an entire dataset — change one leaf, the root changes; inclusion proofs audit membership against that root. - A rollup **state root** commits to all L2 balances and storage; the L1 contract holds the commitment while the rollup proves or asserts a valid transition. - [[Data Availability]] commitments let light clients verify published data without downloading everything. Strangers need ordering without a shared clock ([[01 Replicated State Machines]]). Commitments use entropy and hashing to make happened-before relationships auditable — then consensus picks which chain of knots is canonical. ## Zero-knowledge proofs The most magical-sounding of the four — and the one where intuition matters more than the algebra. ### The four-color map intuition The **four color theorem** says every planar map can be colored with four colors so no two adjacent regions share one. Suppose someone hands you a giant map and claims: "I colored this correctly. Trust me." You care about a **global property**: *every* border between neighbors respects the rule. But inspecting the whole map is expensive — millions of regions, most of them far from you. You don't want to re-color the entire world just to audit one claim. And the prover may not want to show you the full coloring — trade secrets, privacy, sheer size. So you run a different game: **repeated local observations**. ```text Round 1: Verifier points at two adjacent regions (a border). Prover reveals only those two colors. Check: are they different? Round 2: Verifier picks another random border. Prover reveals those two colors. Check again. Round 3: ... ``` Each round is tiny — two colors, one adjacency check. Anyone can do it. But each round tests a **local constraint** that must hold if the global claim is true. Now the logic that makes this powerful: - If the map really is a valid 4-coloring, every local check passes. Always. - If the prover is cheating — even *one* bad border somewhere on the map — that edge is a landmine. Pick it and you catch them. - After enough random rounds, a liar gets caught with overwhelming probability, while you still haven't seen the full map. That is how you **discern a global property from repeated local observations**. You never swallowed the whole structure. You sampled constraints at random until cheating became statistically impossible. **Zero-knowledge** enters when the prover also randomizes what you see — permuting color names between rounds, for instance — so each spot check convinces you the coloring is valid without teaching you the coloring itself. You learn "this claim is credible," not "region 47,291 is blue." ### What this buys in a blockchain Real zk systems replace hand-waved map spot-checks with cryptographic rounds — but the shape is the same. A rollup operator claims a **global statement**: > "I know inputs that take state root A to state root B, and every transaction in between followed the rules." The **witness** is the heavy stuff: all the transactions, execution traces, intermediate storage — the full map. Re-running all of that on L1 is the verifier staring at every region. A zero-knowledge proof is the compressed audit: many local consistency checks (balances didn't go negative, signatures verified, contract rules held at each step) folded into one small artifact. ```text Statement: "valid transition A → B" (global claim — cheap to state) Witness: txs + execution traces (the full map — huge, often private) Proof: a few kilobytes (the distilled spot-checks) Verify: check(proof) == true (local work, fast, no re-execution) ``` The verifier learns the statement holds. They do **not** learn the witness — unless the protocol chooses to reveal parts of it. Verification stays cheap even when the computation attested to was enormous. That combination — **global assurance from local checks, without re-running the world** — is what underwrites zk-rollups, privacy protocols, and light clients that check proofs instead of trusting servers ([[09 Scaling - Rollups and Data Availability]]). ### The properties that matter Same pattern again: - **Completeness** — if the statement is true and the prover is honest, verification succeeds. - **Soundness** — a cheating prover can't convince you of a false statement (except with negligible probability — the "enough random rounds" idea made cryptographic). - **Zero-knowledge** — the proof reveals no more than "the statement is true." The witness stays hidden. - **Succinct** — verification cost is tiny compared to doing the original computation. The audit is smaller than the work it attests to. ### Validity proofs vs fraud proofs One distinction to carry forward: - A **validity proof** (ZK rollup) says: "the math guarantees this transition is correct." Every batch must pass before state updates. Like the map game, but with cryptography substituting for random spot-checks — the proof *is* the overwhelming audit. - A **fraud proof** (optimistic rollup) says: "here's the new state; if it's wrong, someone will challenge it within a window." Nobody proved correctness up front — they posted a claim and bet on being caught. Cheaper when honesty is the default, slower and game-theoretic when it isn't. The polynomial machinery underneath (R1CS, STARKs, PLONKish arithmetization) can wait unless you join a ZK team. For architecture conversations, the four-color intuition is enough: **global claims, local constraints, repeated checking, witness stays hidden, verifier does almost no work.** ## The composition Step back and admire how little was needed: | **Primitive** | **What it buys** | |---|---| | Hash | Tamper-evident fingerprints | | Signature | Authorization without an authority | | Commitment | Binding promises + verifiable happened-before edges | | ZK proof | Global assurance from local checks, without re-execution | Four tools, all checkable locally by anyone, none requiring trust in any institution. The natural next question is what you can build with them. ## Learning outcomes Questions worth trying on: - Could you explain, without jargon, why a hash pointer makes history tamper-evident? - Could you explain why blockchains need no password database — and what replaces the "forgot password" flow? (The honest answer is a little uncomfortable, which is exactly why it's worth being able to give.) - Could you explain the four-color map game — how repeated local border checks convince you of a global property without seeing the whole map? - If someone says "the contract is committed to that state," could you say precisely what was promised, when it was locked in, and how anyone checks it later? - Could you explain how a commitment creates a happened-before edge — and why entropy is what makes that edge unique rather than guessable? - Could you give a colleague the two-sentence difference between a validity proof and a fraud proof? - For a zk-rollup batch: what is the statement, what is the witness, and what does the verifier actually do? - And the thread to pull forward: you can now fingerprint data and sign claims. How do those assemble into a *history* nobody can quietly edit? ## Checkpoint 1. Which property of hash functions makes proof-of-work possible? Which makes commitments **binding**? Which helps **hiding**? *(If unsure, revisit "Hash functions" and "Commitments".)* 2. Walk through commit → reveal → audit for a sealed bid. At which step does binding matter? Hiding? Entropy? *(If unsure, revisit "Commitments".)* 3. Why is signing arbitrary data dangerous in a way that signing a login challenge isn't? *(If unsure, revisit "Digital signatures" — this thread returns in [[07 Wallets and Account Abstraction]].)* 4. What does a Merkle root commit to, and what does an inclusion proof consist of? *(If unsure, see [[Merkle Trees]].)* 5. In the four-color map intuition: what is the global property, what is one local check, and why does zero-knowledge mean you learn less than the full coloring? *(If unsure, revisit "Zero-knowledge proofs".)* **Exercise.** With any scripting language: hash a string, flip one character, hash again — watch the avalanche. Then chain ten hashes, each including the previous one. Modify entry three and observe exactly how far the damage propagates. Congratulations: you've built the skeleton of a blockchain, and it took twenty minutes. ## Resources - **Boneh & Shoup, *A Graduate Course in Applied Cryptography*** — the serious reference. Read selectively: hash functions, signatures, commitments. Resist proving every theorem. - **zk-learning materials** — for the shape of validity proofs: witness, statement, succinct verification. Secondary unless you're heading toward proving infrastructure. --- Next: four tools in hand — how do they compose into a tamper-evident history? → [[03 Blocks, Hashes, and History]]