Checksum

A checksum detects corruption by running the bytes through a deterministic function that produces a small fixed-size fingerprint, storing or transmitting that fingerprint next to the data, and recomputing it on the other side: if the two fingerprints disagree, at least one bit changed in transit or at rest, and the receiver rejects the copy instead of silently returning garbage.

The problem it solves

Bits rot. A DRAM cell flips under a cosmic ray, a disk sector degrades, a NIC or switch mangles a frame, a buggy driver writes the wrong block. None of these announce themselves — the read succeeds and hands back plausible-looking bytes. A checksum turns silent corruption into a loud, catchable error: you compare a cheap fingerprint you trust against one you recompute, and a mismatch means "do not use this data."

Cryptographic vs. non-cryptographic — the distinction that matters

The single most common misconception is that checksums are computed with cryptographic hashes like MD5 or SHA-256. In real distributed systems they usually are not. Integrity checks against accidental corruption overwhelmingly use fast, non-cryptographic functions:

• CRC-32 / CRC-32C — Ethernet frames, HDFS (per 512-byte chunk), Kafka (per record batch, CRC32C), many disk formats. CRC-32C has a dedicated x86 instruction (crc32) running at many GB/s.
• Adler-32 / Fletcher — zlib, rsync's rolling checksum, ZFS's fletcher4 default.
• xxHash — modern hot paths that want maximum throughput.

Cryptographic hashes are the exception, used only when you need a property a CRC cannot give: collision/preimage resistance against a malicious actor, or a stable content identity (Git object IDs, dedup keys, container image digests). A CRC is trivial for an attacker to recompute after editing your data; SHA-256 is not. So the rule is: CRC/xxHash for accidents, cryptographic hash (or HMAC/signature) for adversaries and identity.

Where a checksum sits: on-wire vs. at-rest

The same idea guards two different boundaries, and mature systems check at both because each catches failures the other misses:

• On-wire — TCP's 16-bit checksum, Ethernet's CRC-32, TLS record MACs. Protects data in flight between two endpoints.
• At-rest — HDFS block checksums, ZFS/Btrfs per-block checksums, S3 object ETags. Protects data while stored, and re-verified on every read (this is how ZFS detects and self-heals bit-rot from a good replica).

Worked example 1 — CRC by polynomial long division

CRC treats the message as coefficients of a binary polynomial and takes the remainder after mod-2 (XOR) division by a fixed generator. Take data 1101011 and generator G = 1011 (degree 3, so the checksum is 3 bits). First append 3 zeros, then repeatedly XOR G wherever the leading bit is 1:

The last 3 bits are the remainder: 110. Transmit data + remainder = 1101011110. The receiver divides the whole thing by 1011; because we appended the remainder, the division now comes out to remainder 000 → clean. Any single-bit flip, and most burst errors, force a non-zero remainder. That is the entire mechanism: a clean channel leaves remainder 0.

Worked example 2 — one bit flips, the checksum avalanches

Real integrity checks work on bytes. Take the ASCII string HELLO and flip a single bit in the first byte: H is 0x48 = 0100 1000; flip the low bit → 0x49 = I, giving IELLO. Recompute CRC-32 (the standard zlib/IEEE polynomial):

One flipped bit changes the entire 32-bit fingerprint — a good checksum avalanches, so the receiver's recomputed value (0xFC244D86) will not match the stored 0xC1446436 and the read is rejected. Contrast a naive checksum that just XORs or sums bytes: two compensating bit flips (e.g. add 1 to one byte, subtract 1 from another) cancel out and slip through undetected. That is why CRC's polynomial division, not a plain byte-sum, is the workhorse.

Pitfalls

• The TCP checksum is weak, and that is not enough. TCP's 16-bit ones-complement sum misses whole classes of errors; Stone & Partridge's classic 2000 study found roughly 1 in 16 million to 1 in 10 billion segments arrive corrupt yet pass the checksum. On petabyte-scale traffic that is real, regular corruption. This is the end-to-end argument (Saltzer, Reed & Clark, 1984) in action: the correctness of the data can only be fully guaranteed by the endpoints that actually produce and consume it, so a per-hop check at the transport or link layer reduces but never eliminates the need for an application-level check — which is exactly why HDFS, Kafka, and databases add their own end-to-end application checksums on top of TCP/Ethernet.
• Storing the checksum next to the data can defeat it. If a bug (or a torn write) updates data and checksum together, both stay consistent and the corruption is invisible. ZFS deliberately stores each block's checksum in its parent block pointer, not inline, so a single bad write cannot forge a matching pair.
• Detection is not correction. A checksum says "this is broken," nothing more. Recovery requires redundancy — another replica, RAID, or erasure coding. Systems that checksum without a recovery path just fail more loudly.
• Using a CRC where you needed a cryptographic hash is a security hole. An attacker who alters your data simply recomputes the CRC. Anything defending against tampering needs a keyed MAC (HMAC) or signature, not a bare checksum.
• Scope and framing bugs. Checksumming the payload but not the header, recomputing after a transform so the stored value no longer matches, or getting endianness/length boundaries wrong — these produce checksums that pass on corrupt data or fail on good data.
• Collisions on short/weak checksums. A 16-bit checksum has only 65,536 values; a truncated or additive checksum collides far more easily than its bit-length suggests, letting some corruptions masquerade as valid.

When to use which — and when NOT to

The decision is almost entirely "what am I defending against, and how fast must it be?"

• Choose CRC-32C (or xxHash) when you are detecting accidental corruption at high throughput: storage blocks, network frames, Kafka batches, HDFS chunks. You gain GB/s speed and strong guarantees against bit flips and burst errors; you pay nothing meaningful in CPU. Do not use it where an adversary can edit the data, because a CRC is not secret and trivially recomputed.
• Choose a cryptographic hash (SHA-256) or HMAC/signature when a malicious actor might tamper, or when you need a stable content identity (dedup keys, Git blobs, image digests). You gain collision/preimage resistance; you pay ~10-50x more CPU and a larger digest. Do not reach for it just to catch cosmic-ray bit flips on a hot path — it is wasted cycles, and for authenticity a bare hash still isn't enough (use HMAC).
• Choose a rolling checksum (Adler-32) when you must cheaply slide a window across data to find matching chunks — rsync computes a weak rolling checksum per offset and only falls back to a strong MD5 hash on candidates. You gain O(1) window updates; you pay in collision rate, which is why it is paired with a stronger second check.

Alternatives to a checksum entirely: if you need to recover corrupted data, not just detect it, prefer an error-correcting code (ECC memory, Reed-Solomon/erasure coding) — it costs extra parity storage and encode/decode CPU but repairs damage in place. If you need to prove who produced the data, prefer a digital signature over any checksum. A plain checksum is the right tool only when detect-and-refetch is an acceptable response.

Takeaways

• A checksum is detect-only: fingerprint the bytes, store/send the fingerprint, recompute and compare; a mismatch means reject and refetch — recovery needs separate redundancy.
• Real systems use fast non-cryptographic functions (CRC-32C, Adler, xxHash) for accidental corruption; cryptographic hashes are reserved for adversaries and content identity.
• Check at both boundaries — on-wire and at-rest — because the transport checksum (e.g. TCP's weak 16-bit sum) demonstrably lets corruption through at scale.
• Store the checksum where a single bad write can't forge a matching pair (ZFS puts it in the parent block pointer), and never use a bare checksum where an attacker can recompute it.

Sources: Grokking the System Design Interview (checksum building block); J. Stone & C. Partridge, "When the CRC and TCP Checksum Disagree" (SIGCOMM 2000); Apache Hadoop HDFS and Apache Kafka documentation (CRC-32C data integrity); ZFS end-to-end checksum design (Bonwick & Moore). CRC and CRC-32 values independently verified with Python's zlib. Re-authored and deepened for this guide.