Cryptographic hashing and what it guarantees

A hash function takes an input of any length and returns a string of fixed length. That is a compression, and compression always loses information. A 200-page PDF and a single character both reduce to 32 bytes under SHA-256. So a hash cannot possibly reconstruct its input, and the whole engineering value of the thing rests on a narrower claim: that although many inputs map to the same output in principle, nobody can find two such inputs in practice.

Everything a blockchain does with hashes follows from that claim. Chaining blocks together, committing to a set of transactions, deriving an address from a public key, mining, and the commitments inside zero-knowledge proofs all reduce to the same bet. It is worth understanding exactly what the bet is, and equally worth understanding the things a hash does not give you, because a large share of confused claims about blockchains come from assuming a hash proves more than it does.

What makes a hash function cryptographic

Every hash function is deterministic and fast. A cryptographic hash function adds three resistance properties, and they are not the same property stated three ways.

Preimage resistance. Given an output h, you cannot find any input m with hash(m) = h. The only general attack is to guess inputs and test them, which for a 256-bit output means searching a space of 2^256 possibilities. That number is about 1.16 × 10^77.

Second-preimage resistance. Given a specific input m, you cannot find a different input m' with the same hash. This is what protects a document already in your possession from substitution.

Collision resistance. You cannot find any pair m, m' that collide, where you are free to choose both. This is the most demanding of the three properties to satisfy, and it is also the one that yields first, because the security level it can offer is strictly lower than the other two on account of the birthday bound. If outputs are n bits, a collision surfaces after roughly 2^(n/2) trials rather than 2^n. For SHA-256 that is 2^128, about 3.4 × 10^38 operations. Still far beyond reach, but the security level of a hash function against collisions is half its output length, and that halving is why 256-bit outputs are the modern default rather than 128-bit ones.

To these you add the avalanche property: flipping one bit of the input changes each output bit with probability close to one half, so on average about 128 of the 256 output bits flip. Two inputs that differ by a comma produce outputs with no visible relationship. This is what makes a hash usable as a fingerprint — there is no partial credit, no "close" match, and therefore no way to steer a search toward a target by making small edits.

You can see this yourself in a terminal. printf 'abc' | shasum -a 256 and printf 'abd' | shasum -a 256 return two 64-character hexadecimal strings with nothing in common. Sixty-four hex characters is 32 bytes is 256 bits.

The resistance properties do fail, on a schedule

These are engineering assumptions, not theorems. MD5, designed in 1991, was shown to admit practical collisions by Xiaoyun Wang and co-authors in 2004; today a collision can be produced on a laptop in seconds. SHA-1 held longer, but in 2017 a team from CWI Amsterdam and Google published SHAttered, two distinct PDF files with identical SHA-1 digests, produced with roughly 2^63 hash computations. That is well under the 2^80 the birthday bound would suggest, because the attack exploited structure in SHA-1 rather than searching blindly.

Two lessons follow. First, collision resistance falls before preimage resistance: SHA-1 collisions exist, but nobody can still invert a SHA-1 hash. Second, hash functions get retired, and any long-lived system needs a plan for changing the one it uses. This is one reason serious protocols name their hash function explicitly in the data they commit to, rather than assuming it forever.

SHA-256 belongs to the SHA-2 family, published by NIST in 2001. It has no known practical weakness. SHA-3, standardised in 2015, uses a completely different internal construction (a sponge, rather than the Merkle–Damgård chaining of SHA-2) precisely so that a break of one family would not automatically threaten the other. Ethereum uses Keccak-256, a variant of the SHA-3 design finalised slightly before the standard was published, which is why Ethereum's hash outputs differ from standard SHA3-256 on the same input.

Merkle trees: committing to a set, proving one member

A single hash commits to one blob of data. A Merkle tree commits to a whole set while letting you prove membership of any single element without revealing or transmitting the rest.

Hash each item to form the leaves. Hash each adjacent pair to form the level above. Repeat until one hash remains: the Merkle root. To prove that a particular transaction is in the set, you supply the transaction plus one sibling hash per level, and the verifier recomputes the path upward. If the recomputed root matches the published root, the transaction was in the set.

The proof size is logarithmic. With 1,048,576 items (that is 2^20), the tree has 20 levels, so the proof is 20 hashes. At 32 bytes each, that is 640 bytes to prove membership in a set of over a million items, against roughly 33.5 megabytes to send all the leaf hashes. This is the mechanism behind light clients: a wallet that holds only block headers can verify that its transaction was included, given a proof from someone who holds the full block.

A block header therefore does not contain transactions. It contains a Merkle root of them, plus the hash of the previous header. That structure is the subject of the lesson on blocks and the append-only ledger; here the point is that the compression is what makes it work.

What a hash does not guarantee

A hash is not encryption. There is no key and no decryption. If your input has low entropy, the hash gives you nothing, because an attacker simply hashes every candidate and compares. A four-digit PIN has 10,000 possibilities; a modern machine tests all of them in far less than a second. This is why password storage uses a salt (a unique random value per password, so one precomputed table cannot attack many accounts) and a deliberately slow function such as bcrypt, scrypt or Argon2, which are designed to be expensive in time and memory rather than fast.

A hash does not prove a document existed at a time. hash(document) proves only that whoever shows it had the document when they computed it. To bind a document to a moment you need the digest published somewhere with an independent notion of time — a newspaper, a timestamping authority, or a blockchain block whose ordering is agreed by others.

A hash does not prove who made the document. Anyone can hash anything. Attribution requires a signature over the hash, which is the subject of the next lesson.

A hash does not prove you still have the data. If a chain commits to a Merkle root but the underlying data is unavailable, the commitment is intact and useless. This is the data availability problem, and it is the central difficulty in rollup design.

A matching hash on a downloaded file proves nothing if the hash came down the same channel as the file. Whoever could substitute the file could substitute the published digest. Integrity checks are only meaningful when the reference value travels by an independent, authenticated route.

The Swiss angle: hashes with legal weight

Switzerland gave qualified electronic signatures and electronic time stamps a statutory basis under ZertES, the federal act on electronic signature services, administered through providers recognised by the accreditation body. The relevant point for this lesson is what such a service actually does: it does not archive your document. It takes a hash of your document, signs that hash together with a time value, and returns the result. The document never leaves your premises.

That design is only defensible because of second-preimage resistance. The legal claim is "this exact document existed at this time", but the cryptographic object supporting it is a 32-byte digest. If an adversary could construct a different document with the same digest, the time stamp would attest equally to both, and the evidentiary value would collapse. Swiss law recognising qualified time stamps is, in effect, the legal system taking a position on a computational assumption. It also means that when the assumption weakens, as it did for SHA-1, existing stamps need re-stamping under a stronger function rather than quiet reliance.

What to take away

• A cryptographic hash function is a bet that nobody can find collisions or preimages, not a mathematical guarantee that none exist; hash functions have a service life and get retired, as MD5 and SHA-1 were.
• Collision resistance is only half the output length in bits because of the birthday bound, so SHA-256 offers roughly 128-bit collision security and 256-bit preimage security.
• Merkle trees turn a commitment to a large set into a logarithmic membership proof: about 20 sibling hashes, or 640 bytes, for a set of a million items.
• Hashing is not encryption and offers no protection to low-entropy inputs, which is why password storage requires both a per-password salt and a deliberately slow function.
• A hash proves integrity only relative to a reference value obtained through a trustworthy independent channel; the same digest delivered alongside the file proves nothing.

Sources

• National Institute of Standards and Technology, FIPS 180-4, Secure Hash Standard (SHA-2 family), and FIPS 202, SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions.
• Xiaoyun Wang, Dengguo Feng, Xuejia Lai and Hongbo Yu, "Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD" (2004).
• Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini and Yarik Markov, "The First Collision for Full SHA-1" (CRYPTO 2017); the SHAttered project by CWI Amsterdam and Google.
• Ralph Merkle, "A Digital Signature Based on a Conventional Encryption Function" (CRYPTO 1987), the origin of Merkle trees.
• Satoshi Nakamoto, "Bitcoin: A Peer-to-Peer Electronic Cash System" (2008), sections 7 and 8 on Merkle trees and simplified payment verification.
• Jonathan Katz and Yehuda Lindell, Introduction to Modern Cryptography, chapters on hash functions and the birthday bound.
• Swiss federal act on electronic signature services (ZertES) and the associated ordinance, on recognised electronic time stamps.