Cryptographically Secure Hash Functions

1.2 — Origin of Blockchain: Cryptographically Secure Hash Functions

Recall first. A normal “checksum” (like CRC32) detects accidental corruption. What would a malicious actor need to be unable to do for a blockchain to be secure? Hold that thought.

Reference-book anchor

Primary reference: Blockchain Technology, Chapter 1, §1.4.5 and Chapter 4, §4.4.4.1 — converted Markdown lines 731–764 and 2753–2789.¹

The book supplies the Module I hash definition, fixed-size output, one-way intuition, nonce/PoW context, and Bitcoin-specific SHA-256/header examples. The resistance distinctions and security caveats below make those claims precise.

Why hashing is the origin of blockchain

The Bitcoin design relies on several primitives—digital signatures, hashing, timestamping, incentives, and proof-of-work—but a cryptographic hash function is the key primitive for sealing block contents and linking blocks.² Hashing makes tampering detectable; it does not by itself authenticate a sender, prevent double spending, or choose the canonical history. If you master this topic, the rest of Module I (Merkle trees, block structure, consensus) becomes straightforward.

What a hash function is

A hash function H maps an input of arbitrary length to a fixed-length output:

H : {0,1}*  →  {0,1}^n

Example: SHA-256 always outputs 256 bits (a 64-character hex string), no matter if you hash the letter a or the entire Bible.

SHA-256("hello") = 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824

Refresher — bits and hex. A bit is 0 or 1. A byte is 8 bits. Hex (base-16) writes each byte as two characters 00–ff. 256 bits = 32 bytes = 64 hex chars. Blockchain hash outputs are almost always shown in hex.

The three security properties (this is the exam core)

A cryptographic hash function is expected to provide three security properties. These are defined precisely by NIST.³⁴ No finite hash output can make collisions mathematically impossible; the goal is to make the relevant attack infeasible.

Why collision resistance is “only” 128 bits: by the birthday bound, finding any collision among many random inputs takes roughly √(2ⁿ) = 2^(n/2) tries. So a 256-bit hash gives 128-bit collision security but 256-bit preimage security.⁴

Keep the three properties distinct

All three properties concern finding equal outputs, but the attacker’s starting information differs:

• Preimage: the attacker starts with a digest and searches for any input that produced it.
• Second preimage: the attacker starts with a particular message x and searches for a different message with the same digest.
• Collision: the attacker is free to choose both different messages.

Do not collapse these into one vague claim of “one-wayness.” They are separate security requirements with different generic work factors; a design or application must ask which attack matters.⁵

Beginner trap. “Collision resistance” does not mean collisions don’t exist — they must (pigeonhole principle: infinite inputs, finite outputs). It means an attacker cannot feasibly find a useful collision with current methods.

Why each property matters in a blockchain

SHA-256: the workhorse

Bitcoin (and the syllabus’s “cryptographically secure hash functions”) centers on SHA-256, specified in NIST FIPS 180-4.³ Key facts:

• Output: 256 bits (32 bytes).
• Internally: processes the message in 512-bit blocks, 64 rounds.
• It is iterated and designed to be one-way — small input changes typically avalanche into a very different output (avalanche effect).
• Bitcoin uses double SHA-256 (SHA256(SHA256(x))) for many block and transaction identifiers. Treat this as a Bitcoin protocol convention, not as a rule that every blockchain or application must double-hash; the security claim must still be tied to the construction being used.

SHA256d(x) = SHA256( SHA256(x) )

Refresher — avalanche effect. Change one bit of the input and ~half the output bits flip. This is why a block’s hash changes completely if any transaction inside it changes — the foundation of tamper-evidence.

What hashing does not provide

A hash is not encryption: it does not hide a message from someone who can guess and hash candidate inputs. It also does not authenticate the author, prove that a real-world event happened, or stop a valid message from being replayed. Those jobs require other mechanisms such as encryption, digital signatures, timestamps, transaction rules, and consensus.

Worked example — tamper evidence

Suppose a block’s header hashes to 0000a3... and contains transaction T. An attacker changes T to T'. What happens to the block hash, and why does this break the chain?

Answer (commit before reading): Because of the avalanche effect, H(T') is expected to differ from H(T); a cryptographic hash does not mathematically guarantee distinct outputs for every pair. The Merkle root (built from transaction hashes) changes with overwhelming probability, so the block header’s hash changes, so the next block’s prev_hash no longer matches. The tamper is detectable at every downstream block unless an infeasible useful collision or second preimage can be found.

Exercise

True or false, and explain in one line each: (a) SHA-256 is collision-free. (b) Knowing H(x) lets you recover x quickly. (c) A 256-bit hash gives 256-bit security against collision attacks.

Exam lens

Three-mark comparison: define preimage, second-preimage, and collision resistance by stating what the attacker is given and what they must find. Then state the generic SHA-256 work factors: approximately 2²⁵⁶ for preimage/second-preimage search and 2¹²⁸ for a generic collision search.

Common traps:

• A collision is mathematically inevitable; finding a useful one is what must be infeasible.
• A hash is not a signature and does not identify the person who supplied the input.
• A 256-bit digest does not mean 256-bit collision security.
• A changed digest detects a changed input; it does not explain which input is correct.

Generation prompt: explain why a one-bit change in a transaction can change a block’s Merkle root, but why hashing alone cannot decide whether two conflicting transactions are valid. The first answer is cryptographic; the second requires ledger rules and consensus.

Rapid revision

• Can I distinguish the inputs and goals of the three resistance properties?
• Can I convert 256 bits into 32 bytes and 64 hexadecimal characters?
• Can I explain the birthday-bound reason for the 2¹²⁸ collision estimate?
• Can I state one thing hashing cannot do?

Key takeaways

• A cryptographic hash maps arbitrary input → fixed output and is one-way.
• The three security pillars: preimage, second-preimage, and collision resistance.
• Collision resistance is the weakest (≈ n/2 bits) and the one attackers target.
• SHA-256 (FIPS 180-4) is a core hash function used in Bitcoin; Bitcoin’s double-SHA256 is a protocol convention, not a universal blockchain requirement.
• Hashing is the root primitive: it makes blocks tamper-evident and linkable.

Sources