# 02 — Cryptographic Primitives A stranger hands you a piece of paper. It says: "Alice paid Bob ten dollars." No bank logo. No notary stamp. No phone number to call and ask. Just bytes — and the claim that those bytes mean something about the world. [[01 Replicated State Machines]] left you here: many machines must agree on one replayable history, but nobody gets to be the trusted clerk. So verification has to work **between total strangers** — locally, cheaply, repeatably. What tools could possibly do that? Surprisingly few. Four carry almost the whole load: **hashes**, **signatures**, **commitments**, and **zero-knowledge proofs**. You do not need to become a cryptographer to use them well. You need to know what each one buys — which is a much smaller ask. --- ## Fingerprints that cannot be forged ### Hash functions A hash maps arbitrary data to a fixed-size output: ```text hash("hello") = 2cf24d... ``` The properties that matter: - **Deterministic** — same input, same output, everywhere. - **Preimage-resistant** — given a hash, you cannot recover the input. - **Collision-resistant** — you cannot craft two different messages with the same fingerprint. - **Avalanche** — flip one bit in the input; the whole output scrambles. Put those together and you get a **fingerprint anyone can check and no one can forge**. Block IDs, [[Merkle Trees]], proof-of-work, commitments, and addresses all lean on the same move: point at data with a hash, and tampering anywhere breaks the pointer downstream. --- ## Authorization without an identity department ### Digital signatures A user holds: ```text private_key public_key address = hash(public_key) ``` They sign with the private key. Anyone verifies: ```text verify(public_key, message, signature) == true ``` What this buys: **authorization without identity infrastructure**. No account table, no password database, no login service. Whoever holds the key *is* the account. If you have built auth systems, notice the inversion. Authentication is usually a service you operate; here it is a mathematical fact the network checks. Elegant — and sharp-edged. There is no forgot-password flow and no one to call. That single choice generates most of wallet engineering ([[07 Wallets and Account Abstraction]]). One distinction products get wrong constantly: > Signing a transaction is not "logging in." It can authorize irreversible movement of assets. "Please sign this" should always prompt: sign *what*, exactly? --- ## Promises frozen in time ### Commitments A **commitment** locks in a value now so you can prove later you did not 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** (salt) is fresh cryptographic randomness — kept private until reveal — mixed with the secret so the digest does not look like a guessable template. **Binding** — once published, you cannot open to a different value without breaking collision resistance. **Hiding** — before reveal, the commitment should not leak the secret. `hash("yes")` alone is offline-guessable. A **long, random nonce kept secret until reveal** restores hiding even for low-entropy values — an attacker must search the nonce space, not the secret space. **Verifiable** — given commitment and reveal, anyone checks locally. No notary required. ### Commit → reveal → audit **Step 1 — Commit.** Publish `C = hash(secret || nonce)` while `secret` and `nonce` stay private. **Step 2 — Reveal.** Later publish both. **Step 3 — Audit.** ```text hash(secret || nonce) == C → promise kept hash(secret || nonce) != C → story changed, or tampering ``` **Sealed bid.** Alice commits `hash(bid || nonce)` before the auction closes. After the deadline, both reveal. Neither could change a bid after seeing the other's (binding); well-randomized bids stay hidden until then (hiding). ### Causal knots [[01 Replicated State Machines]] named the problem: strangers with divergent clocks need one history, and timestamps will not give it to them. **Causal order** must be reconstructed from evidence everyone can check. A commitment spins that thread. Before you commit, many futures are open. At commit time you **spend entropy** — draw randomness, mix with your secret, publish the hash. ```text C = hash(secret || nonce) ^^^^^^ ^^^^^ intent entropy — this commitment is THIS event, not a template ``` That publish is a **causal knot**: a verifiable happened-before edge strangers can audit without trusting anyone's clock. Chain block hashes, Merkle roots, state roots — same pattern: entropy mixed with content, published early, opened or verified later. Consensus still picks *which* chain of knots is canonical ([[04 Consensus]]). ### Where you'll see them - [[Merkle Trees|Merkle root]] — commits to a whole dataset; change one leaf, root changes. - Rollup **state root** — commits to L2 state on L1. - [[Data Availability]] — commitments let light clients verify publication without downloading everything. --- ## Global claims, local checks ### The four-color map The **four color theorem** says every planar map can be colored with four colors so adjacent regions differ. Someone hands you a giant map: "I colored this correctly. Trust me." You care about a **global property** — every border respects the rule. Inspecting the whole map is expensive. The prover may not want to show the full coloring. So you play a different game: **repeated local observations**. ```text Round 1: Verifier points at two adjacent regions. Prover reveals only those two colors. Check: different? Round 2: Another random border. Check again. ``` If the coloring is valid, every local check passes. If there is even one bad border, random rounds eventually find it. After enough rounds, cheating becomes statistically impossible — while you still have not seen the full map. **Zero-knowledge** enters when the prover permutes color names between rounds: you learn the claim is credible, not the coloring itself. ### What this buys on a chain A rollup operator claims: > "I know inputs that take state root A to state root B, and every step followed the rules." The **witness** is the heavy stuff — transactions, traces, storage. Re-running all of that on L1 is staring at every region. A zero-knowledge proof is the compressed audit: ```text Statement: "valid transition A → B" (global claim — cheap to state) Witness: txs + execution traces (the full map — huge) Proof: a few kilobytes (distilled checks) Verify: check(proof) == true (fast, no re-execution) ``` That combination 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 - **Completeness** — honest true statements verify. - **Soundness** — false statements fail (except with negligible probability). - **Zero-knowledge** — the proof reveals no more than "the statement holds." - **Succinct** — verification is cheap relative to the work attested. ### Guardrails The map game is an intuition pump, not a description of deployed SNARKs and STARKs: - **Non-interactive.** Most chain proofs use Fiat–Shamir-style transforms — one artifact to check, not a live game. - **Zero-knowledge ≠ succinct validity.** Rollup validity proofs often prove correct execution without hiding state. Privacy is optional. - **Not naive sampling.** Modern proofs use algebraic machinery; soundness is cryptographic, not "spot-check until unlikely." - **Validity vs fraud.** Optimistic rollups post a claim and rely on **fraud proofs**; ZK-style rollups post **validity proofs** ([[09 Scaling - Rollups and Data Availability]]). Circuit engineering (R1CS, STARKs, PLONK) can wait unless you join a ZK team. For architecture: four-color intuition plus the guardrails above. ### Validity proofs vs fraud proofs - **Validity proof** (ZK rollup) — math guarantees correctness before state updates; usually non-interactive. - **Fraud proof** (optimistic rollup) — state posted; wrongness challenged in a window. Cheaper when honesty is default; slower and game-theoretic when not. --- ## The composition | **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, none requiring trust in an institution. The next question: how do they assemble into a *history* nobody can quietly edit? ## 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? - Could you explain the four-color map game — global property from local border checks? - If someone says "the contract is committed to that state," could you say 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 makes that edge unique? - Could you give 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, what does the verifier do? - And the thread to pull forward: you can fingerprint data and sign claims. How do those compose into tamper-evident *history*? ## Checkpoint 1. Which hash property makes proof-of-work possible? Which makes commitments **binding**? Which helps **hiding**? *(If unsure, revisit "Fingerprints that cannot be forged and Promises frozen in time".)* 2. Walk commit → reveal → audit for a sealed bid. When does binding matter? Hiding? Entropy? *(If unsure, revisit "Promises frozen in time".)* 3. Why is signing arbitrary data dangerous in a way that signing a login challenge isn't? *(If unsure, revisit "Authorization without an identity department" — 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 intuition: global property, one local check, and what zero-knowledge withholds? *(If unsure, revisit "Global claims, local checks".)* **Exercise.** Hash a string, flip one character, hash again — watch the avalanche. Chain ten hashes. Modify entry three and observe how far damage propagates. You have built the skeleton of a blockchain in twenty minutes. ## Resources - **Boneh & Shoup, *A Graduate Course in Applied Cryptography*** — read selectively: hashes, signatures, commitments. - **zk-learning materials** — witness, statement, succinct verification; secondary unless you head toward proving infrastructure. --- Next: four tools in hand — how do they compose into a tamper-evident history? → [[03 Blocks, Hashes, and History]]