Chapter III · Part I — Primitives
Hashes & One-Way Functions 🧬
A hash function is a blender for bits: any input — a poem, a movie, your tax return — becomes exactly 32 bytes of digital fingerprint. The same input always yields the same fingerprint, yet the fingerprint tells you nothing usable about the input, and finding any collision is beyond anyone's budget.
The contract
🔍 Deeper dive · three attack flavors, three defenses
"Breaking" a hash means different things — keep them apart, because they damage different systems:
Note the asymmetry in costs: attackers get the "buy one get one free" birthday discount on collisions — explained below.
One flipped bit, total chaos
Change "cat" to "bat" and the hashes share nothing — not style, not prefix, not statistics. This is the avalanche effect, and it's why hashes behave like idealized random oracles: there's no gradient to slide down, no "getting warmer" for an attacker.
Pigeonhole alert — why collisions must exist (but don't worry)
Infinite inputs, only 2²⁵⁶ outputs — so collisions are mathematically unavoidable. The security question is whether anyone can find one. Thanks to the birthday paradox, generic collision search costs ~2¹²⁸ hashes; no entity on Earth can do that. Finding a preimage costs ~2²⁵⁶. These numbers are the load-bearing walls of everything else in this course.
🔍 Deeper dive · inside the blender (Merkle–Damgård)
How does any length become exactly 256 bits? SHA-256 runs an assembly line: split the data into 512-bit blocks; a compression function mixes each block into a running 256-bit state, initialized from fixed "nothing-up-my-sleeve" constants; padding appends the message length so different sizes can't trivially collide. The avalanche you watched is the mixer doing its job — every output bit depends on every input bit, diffusively, block after block. One consequence worth noticing: hashing is inherently sequential over blocks, which is why doubling a file doubles the hash time (and why miners grind trillions of short messages rather than one long one).
🔍 Deeper dive · the birthday paradox, honestly
How many people must be in a room before two probably share a birthday? Not 365 — just 23 (~50%). Collisions are about pairs, not targets: with k hashed items there are k(k−1)/2 pairs, each a mini-lottery ticket. So collisions appear around √(2ⁿ) hashes: for SHA-256 that's 2¹²⁸ — still absurd for attackers, but exactly why collision security is half the output length, and why 128-bit-output hashes are retired for anything collision-sensitive. When Chapter 8 builds "approved sets" out of hashes, this is the margin protecting them.
🧪 The Hash Grinder
Here's how a hash becomes a proof of work: pick a difficulty (say, "the fingerprint must start with 16 zero bits") and grind nonces 0, 1, 2, … until you stumble on one that qualifies. You can't be clever — the avalanche effect forbids it — you can only burn compute. Verifying your find takes one hash. Bitcoin mining is exactly this game; so is the Fiat–Shamir transform you'll meet in Chapter 6.
🔍 Deeper dive · fast hashes are for data, slow hashes for passwords
SHA-256 is engineered to be fast — ideal for mining, commitments, signatures. For passwords, fast is a bug: an attacker with a GPU tries billions of candidates per second against a leaked hash file. Password storage therefore uses deliberately slow, memory-hard functions (Argon2, bcrypt, scrypt) plus a per-user salt — randomization that makes precomputed "rainbow tables" useless. Notice the theme forming across chapters: randomization (salt, nonce, blinding) is the antidote whenever the secret space is small enough to guess. Commitments next chapter rely on exactly this.
Where hashes carry ZK
- Commitments (next chapter): a hash of your sealed value — binding by collision resistance.
- Fiat–Shamir (Chapter 6): the hash replaces the verifier's coin flips, making proofs non-interactive.
- STARKs (Chapter 7): hash-based proofs with no trusted setup — quantum-agnostic security.
- Merkle trees (Chapter 8): prove a value is in an approved set without revealing which — the engine of selective disclosure.
📌 Week 3 — key takeaways
- A cryptographic hash is deterministic, fixed-length, avalanche-unpredictable, one-way and collision-resistant.
- Three attack flavors to keep apart: preimage (~2²⁵⁶), second preimage (~2²⁵⁶), collision (~2¹²⁸ via the birthday paradox).
- Merkle–Damgård explains the magic: block-by-block compression of a running state turns any input length into 256 bits.
- Small secret spaces (coins, passwords, birthdates) must be salted/randomized before hashing — otherwise guess-and-check wins. You'll see this again as commitment nonces and blinding factors.
- Proof-of-work = hashing-as-lottery: no strategy beats grinding nonces; verification is a single hash. Fiat–Shamir (Chapter 6) reuses the same ungrindability for a completely different job.
🎯
Checkpoint: Fingerprints of Data
SHA-256 is called "one-way" because…
- it only works on data flowing in one direction across a network.
- computing the hash is easy, but inverting it (hash → input) is infeasible.
- it can only be run once per machine.
- its output can't be hashed again.
Preimage resistance: the blender has no "reverse" setting. Note this is a computational statement — easy forward, hard backward — the same asymmetry as the discrete log from Chapter 2.
You flip one character in a 10 GB file. Its SHA-256…
- changes in the same character's position.
- changes slightly — a few output bytes.
- changes completely, as if re-randomized.
- stays the same; SHA-256 ignores single edits.
Avalanche: roughly half the output bits flip with no discernible pattern — you saw it live in the demonstrator.
Why does proof-of-work difficulty translate directly to "energy spent"?
- Because the avalanche effect makes each try statistically independent — there's no shortcut but grinding nonces one by one.
- Because hashes get harder to compute over time.
- Because the network charges a fee per hash.
- Because nonces must be purchased.
Each nonce is a fresh lottery ticket with probability 2⁻ᵈifficulty of winning. Expected work is fixed; verification is a single hash — that asymmetry is the point.
Given only h = SHA-256("attack at dawn"), an attacker wants to find any message m with SHA-256(m) = h. Best known strategy?
- Read the message out of the hash's structure.
- Invert the compression function step by step.
- Ask the hash nicely.
- Brute-force candidate messages, ~2²⁵⁶ tries in the worst case.
Preimage search is the only generic attack. For short human-guessable messages a dictionary attack works — which is exactly why commitments (next chapter) mix in a big random nonce.