Skip to content
Tutorials Center
My learning

Topics

Lesson 5 of 41 ยท Cryptography Foundations

Hash Pointers and Tamper Evidence

Link records by their hash to build tamper-evident logs. Detect edits, find where history was changed, and see why rewriting a long chain is costly.

An ordinary pointer says where something is. A hash pointer says where something is and what it must look like: it stores the location together with the hash of the data it points to. If someone swaps the data for different content, the hash no longer matches, and you notice at once.

This simple twist turns a plain linked list into a tamper-evident log, the heart of every blockchain. In this lesson you will build one in Python, tamper with it, find exactly where it was changed, and measure what an attacker would have to redo to hide the change.

From pointer to hash pointer

In a normal linked list, each record knows only its predecessor's location. Anyone with write access can replace a record in the middle and nothing will complain.

With a hash pointer, each record stores the hash of the entire previous record, including that record's own hash pointer. That makes every record depend on all earlier ones:

flowchart RL
    R3["Record 3<br/>data: ...<br/>prev hash: H2"] -- "H2 = hash of record 2" --> R2["Record 2<br/>data: ...<br/>prev hash: H1"]
    R2 -- "H1 = hash of record 1" --> R1["Record 1<br/>data: ...<br/>prev hash: none"]

Each arrow carries the hash of the record it points to; the head's hash summarizes the entire history.

If you remember only the hash of the newest record (the head), you can verify the whole log: recompute each hash back to the beginning and compare. One short value commits to everything before it.

Building a log

Let's write the smallest useful version. Each entry contains some text, the previous entry's hash and its own hash computed over both.

Python A tamper-evident log

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 head hash is a fingerprint of all four entries and their order. Publish just that one value somewhere safe (in a newspaper, on a public chain, on a colleague's laptop) and nobody can later change the log without the mismatch showing.

Verifying and locating tampering

Verification recomputes every hash from the data and checks two things per entry: its stored hash matches its content, and its prev matches the previous entry's hash.

Python Find the first bad entry

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 checker points at entry 2, the exact record that was edited. That is more than "something is wrong": it localizes the damage.

The cheater's dilemma: rewriting history

A clever attacker would not leave the evidence behind. After editing entry 2, they could recompute its hash, then entry 3's prev and hash, and so on to the end. The log is internally consistent again.

Python Rewriting the tail

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 attacker succeeded in making the log self-consistent, but they could not avoid changing the head hash. Anyone who saved the old head (a witness) immediately sees that the new log does not match. So hash pointers alone provide tamper evidence only if the head is kept somewhere the attacker cannot edit.

That is exactly the job of a blockchain network: thousands of independent nodes each remember the chain tip. To change history, an attacker would need to rewrite the blocks and convince nodes to switch to the rewritten version. Proof of work makes that expensive, because each block's hash must also satisfy a difficulty rule, so rewriting means redoing a lot of computing for every block after the edit (Proof of Work and Mining).

Cost of rewriting grows with depth

Even in this toy, you can see the work grow: editing entry k in a log of n entries forces you to recompute n - k hashes.

Python How many hashes must be redone?

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.

Hashing alone is cheap, so a plain hash chain is not enough to resist a determined attacker with the whole log. It is the combination with a costly block-creation rule and many independent witnesses that makes real blockchains hard to rewrite.

Beyond lists: hash pointers in trees

Hash pointers work for any structure with pointers, not only lists. Git commits point to their parents by hash (so a commit hash summarizes all history), and a Merkle tree uses hash pointers to summarize thousands of items in one root hash. The next lesson builds one: Merkle Trees and Proofs of Inclusion.

A hash pointer does not stop anyone from editing a copy. It only guarantees that edits cannot go unnoticed by someone holding the right hash. Security comes from who holds the reference values.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does a hash pointer store?

    A hash pointer tells you where the data is and lets you verify that the data you fetched is the data that was originally pointed to.
  2. 2. You edit entry 5 of a 10-entry hash-linked log without fixing anything else. Where will verification first fail?

    Entry 5's content no longer matches its stored hash, and entry 6's stored previous hash no longer matches either.
  3. 3. An attacker edits an old entry and recomputes every later hash. What still gives them away?

    The rewritten log is consistent internally, but its head hash differs from the previously published one, so anyone holding the old head detects the change.
  4. 4. Why does a plain hash chain alone not stop a determined rewriter?

    Hashing is fast. Blockchains add a cost per block (proof of work or stake) and a network of nodes that remember the chain.

Summary

  • A hash pointer pairs a reference with the hash of the referenced data, so any change to the data is detectable.
  • Each log entry includes the hash of the previous one, so the head hash commits to the whole history.
  • Verification recomputes hashes and can point to the first altered entry.
  • An attacker can recompute later hashes, but the head hash changes, so witnesses holding the old head notice.
  • Blockchains add costly block creation and many independent nodes to make rewriting history impractical.

Next: Merkle Trees and Proofs of Inclusion, where hash pointers summarize many transactions at once.