Skip to content
Tutorials Center
My learning

Topics

Lesson 11 of 40 ยท Hashing

Using Hashes: Integrity, Fingerprints and Commitments

See what hashes are good for: verifying file integrity, content-addressed storage, commitment schemes and Merkle trees with inclusion proofs, all in live Python.

Once you trust that a hash digest is a tiny, hard-to-forge fingerprint of its input, many problems become easy. Is the downloaded file the one the publisher released? Have I seen this blob before? Can I promise a value now and reveal it later without being able to change my mind? Can I prove one item belongs to a huge set while sending only a few hashes?

This lesson covers four patterns built on cryptographic hash functions: integrity checks, content addressing, commitments and Merkle trees. All are used in production systems, from Git to software updates to certificate transparency logs.

Integrity checks and file checksums

When you publish a file together with its SHA-256 digest, anyone can hash their copy and compare. If a single bit was corrupted in transit, or a mirror swapped the file, the digests differ. For large files, hash in chunks so memory stays small.

There is one important limit: a checksum shows that the file matches the digest, but only if the digest itself came through a trusted channel. If an attacker can change both the file and the digest next to it, the check proves nothing. For tamper resistance against an attacker you need a keyed MAC (MACs and HMAC) or a digital signature (digital signatures) over the digest.

Python Verifying data against a published digest

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Content addressing

If the digest of some data is its name, you get a store where identical content is automatically stored once, and where a name can be checked against the content it returns. This is content-addressed storage. Git names every blob, tree and commit by the hash of its content; Docker layers, IPFS and many backup tools work the same way.

Because a commit's name includes the names of its parents, changing any old commit changes its digest and the digest of every later commit. That property is exactly what the hash chain in the blockchain project builds on.

Python A tiny content-addressed store

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Commitment schemes

A commitment is a digital sealed envelope. You publish a commitment to a value now; later you open it by revealing the value, and everyone can check it. A good scheme has two properties:

  • Hiding: the commitment reveals nothing about the value.
  • Binding: after committing, you cannot open it to a different value.

A hash gives a simple scheme: commitment = H(nonce || value), where the nonce is a long random string. Without the nonce, a hash alone would not hide a value drawn from a small set: the attacker would hash every candidate and compare. The random nonce, kept secret until opening, adds the missing entropy (see randomness and entropy). Binding comes from collision resistance.

sequenceDiagram
    participant A as Alice
    participant B as Bob
    A->>A: choose value v and random nonce r
    A->>B: commitment c = H(r || v)
    Note over A,B: Bob cannot learn v from c
    B->>A: Bob's own guess
    A->>B: opening: r and v
    B->>B: check H(r || v) equals c

Alice is locked in to v at the moment she sends c, and Bob learns v only when she opens.

Python Commit, reveal, verify

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Commitments appear in coin-flipping over the network, sealed-bid auctions, and zero-knowledge proofs (secret sharing and zero-knowledge).

Merkle trees

Suppose you store a million files with an untrusted server and want to check one file later. Keeping a hash per file costs you a million hashes. A Merkle tree reduces that to a single hash. Hash each item to make the leaves; then repeatedly hash pairs of nodes until one node remains: the root. Any change to any leaf changes the root.

To prove that a leaf belongs to the tree, you do not send everything. You send the sibling hash at each level along the path to the root, the inclusion proof. For a million leaves that is only about 20 hashes. The verifier recomputes the path and compares with the trusted root.

flowchart TD
    R["Root = H(N01, N23)"] --> N01["N01 = H(L0, L1)"]
    R --> N23["N23 = H(L2, L3)"]
    N01 --> L0["L0 = H(tx0)"]
    N01 --> L1["L1 = H(tx1)"]
    N23 --> L2["L2 = H(tx2)"]
    N23 --> L3["L3 = H(tx3)"]

To prove tx2, send L3 and N01. The verifier computes L2, then N23, then the root.

Python A Merkle tree with inclusion proofs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The 0x00 and 0x01 prefixes are domain separation: they make sure a leaf can never be confused with an inner node, which closes a known attack where an attacker presents an inner node as if it were data. Certificate transparency logs, Bitcoin blocks and Git-like systems all use Merkle structures; you will build a full proof checker in the hash chain project.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A website publishes a file and its SHA-256 digest on the same unsecured page. What can an attacker who controls the page do?

    A checksum only proves a match with the digest; if the attacker controls the digest too, the check proves nothing. Use a signature or a trusted channel.
  2. 2. In content-addressed storage, what happens if you store the same bytes twice?

    Identical content produces an identical digest, so it maps to the same key.
  3. 3. Why does a hash-based commitment include a random nonce?

    Without the nonce, H(value) can be matched against H(guess) for every possible value. The nonce supplies the missing entropy.
  4. 4. How many hashes does a Merkle inclusion proof contain for about one million leaves?

    The proof holds one sibling per tree level, and a binary tree with a million leaves has about log2(1,000,000), roughly 20, levels.

Summary

  • A digest compared against a trusted value detects corruption and tampering; the digest itself must come from a trusted source or be signed.
  • Content addressing names data by its hash, giving deduplication and built-in verification (Git, Docker, IPFS).
  • A hash commitment H(nonce || value) is hiding thanks to the nonce and binding thanks to collision resistance.
  • A Merkle tree reduces many items to one root; an inclusion proof needs only about log2(n) hashes.
  • Use domain separation (distinct prefixes) so that different roles of a hash cannot be confused.

Next: Hash Attacks: Collisions, Length Extension and Birthday.